Graf reduktion

I datalogi, graf reduktion implementerer en effektiv version af ikke-streng evaluering, en evaluering strategi, hvor argumenterne til en funktion ikke umiddelbart vurderes. Denne form for ikke-streng evaluering er også kendt som doven evaluering og bruges i funktionelle programmeringssprog. Teknikken blev først udviklet af Chris Wadsworth i 1971.

Motivation

Et simpelt eksempel på vurdering af et aritmetisk udtryk følger:

Ovenstående sekvens reduktion anvender en strategi kaldet yderste træ reduktion. Det samme udtryk kan evalueres ved hjælp inderste træ reduktion, hvilket gav sekvensen reduktion:

Bemærk, at reduktionen ordre er udtrykkeligt ved tilsætning af parenteser. Dette udtryk kunne også have været simpelthen evalueret højre til venstre, fordi tilføjelse er en associativ operation.

Repræsenteret som et træ, udtrykket ovenfor ser sådan ud:

Det er her, reduktionen sigt træet kommer fra. Når repræsenteret som et træ, kan vi tænke på inderste reduktion som arbejder nedefra og op, mens yderste værker fra toppen og ned.

Udtrykket kan også repræsenteres som en graf, så sub-udtryk til at blive delt:

Som for træer, yderste og inderste reduktion gælder også for grafer. Derfor har vi graf reduktion.

Nu evaluering med yderste graf reduktion kan gøre følgende:

Bemærk, at evalueringen nu kun kræver fire trin. Yderste graf reduktion omtales som dovne evaluering og inderste graf reduktion omtales som ivrige evaluering.

Combinator graf reduktion

Combinator graf reduktion er en grundlæggende implementering teknik til funktionelle programmeringssprog, hvor et program konverteres til en combinator repræsentation, som er knyttet til en rettet graf datastruktur i computerens hukommelse, og udførelse Programmet består derefter af omskrive dele af denne graf, således at bevæge sig i retning brugbare resultater.

Historie

Begrebet en graf reduktion, der tillader evalueret værdier, der skal deles blev først udviklet af Chris Wadsworth i hans 1971 Ph.D. afhandling. Denne afhandling blev citeret af Peter Henderson og James H. Morris Jr. i 1976 side, "En doven evaluator", der introducerede begrebet dovne evaluering. I 1976 David Turner indarbejdet doven evaluering i SASL hjælp combinators. SASL var en tidlig funktionel programmeringssprog først udviklet af Turner i 1972.

  0   0
Forrige artikel Arkaba Station

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha