Grafförminskning

Den här artikeln handlar om termen datavetenskap. För användning av grafteorin, se transitiv reduktion .

Inom datavetenskap implementerar grafreduktion en effektiv version av icke-strikt utvärdering, en utvärderingsstrategi där argumenten till en funktion inte omedelbart utvärderas . Denna form av icke-strikt utvärdering är också känd som lat utvärdering och används i funktionella programmeringsspråk . Tekniken utvecklades först av Chris Wadsworth 1971.

Motivering

Ett enkelt exempel på att utvärdera ett aritmetiskt uttryck följer:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&= &((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6 \\&{}&=&8+6\\&{}&=&14\end{aligned}}$

Ovanstående reduktionssekvens använder en strategi känd som yttersta trädreduktion. Samma uttryck kan utvärderas med reduktion av innersta trädet, vilket ger reduktionssekvensen:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&= &((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6 \\&{}&=&8+6\\&{}&=&14\end{aligned}}$

Observera att reduktionsordningen görs explicit genom tillägg av parenteser. Detta uttryck kunde också helt enkelt ha utvärderats från höger till vänster, eftersom addition är en associativ operation.

Representerat som ett träd ser uttrycket ovan ut så här:

Det är härifrån termen trädminskning kommer. När det representeras som ett träd kan vi tänka oss innersta reduktion som att arbeta nerifrån och upp, medan yttersta fungerar uppifrån och ner.

Uttrycket kan också representeras som en riktad acyklisk graf , vilket gör att underuttryck kan delas:

När det gäller träd gäller även yttersta och innersta reduktion för grafer. Därför har vi grafreduktion .

Nu kan utvärdering med yttersta grafreduktion fortgå enligt följande:

Observera att utvärdering nu bara kräver fyra steg. Den yttersta grafreduktionen kallas lat utvärdering och den innersta grafreduktionen kallas ivriga utvärdering .

Reduktion av kombinatorgrafer

Combinator graph reduction är en grundläggande implementeringsteknik för funktionella programmeringsspråk , där ett program omvandlas till en kombinatorrepresentation som mappas till en riktad grafdatastruktur i datorns minne, och programexekveringen består sedan av att skriva om delar av denna graf ("reducera " it) för att gå mot användbara resultat.

Historia

Konceptet med en grafreduktion som gör att utvärderade värden kan delas utvecklades först av Chris Wadsworth i hans 1971 Ph.D. avhandling. Denna avhandling citerades av Peter Henderson och James H. Morris Jr. i 1976 års artikel, "A lazy evaluator" som introducerade begreppet lazy evaluation. 1976 David Turner lata utvärderingar i SASL med hjälp av kombinatorer. SASL var ett tidigt funktionellt programmeringsspråk som först utvecklades av Turner 1972.

Se även

• Grafförminskningsmaskin
• SECD-maskin

Anteckningar

•   Bird, Richard (1998). Introduktion till funktionell programmering med Haskell . Prentice Hall. ISBN 0-13-484346-0 .

Vidare läsning

•    Peyton Jones, Simon L. (1987). Implementering av funktionella programmeringsspråk . Prentice Hall. ISBN 013453333X . LCCN 86020535 . Hämtad 2022-04-15 .