Waarom is luie evaluatie nuttig?

Ik vraag me al lang af waarom luie evaluatie nuttig is. Ik moet nog iemand het me uitleggen op een manier die logisch is; meestal komt het neer op “vertrouw me”.

Opmerking: ik bedoel niet memo’s.

Antwoord 1, autoriteit 100%

Voornamelijk omdat het efficiënter kan — waarden hoeven niet te worden berekend als ze niet worden gebruikt. Ik kan bijvoorbeeld drie waarden doorgeven aan een functie, maar afhankelijk van de reeks voorwaardelijke expressies, kan alleen een subset daadwerkelijk worden gebruikt. In een taal als C zouden alle drie de waarden sowieso worden berekend; maar in Haskell worden alleen de noodzakelijke waarden berekend.

Het maakt ook coole dingen mogelijk, zoals oneindige lijsten. Ik kan geen oneindige lijst hebben in een taal als C, maar in Haskell is dat geen probleem. Oneindige lijsten worden vrij vaak gebruikt in bepaalde gebieden van de wiskunde, dus het kan handig zijn om ze te kunnen manipuleren.

Antwoord 2, autoriteit 72%

Een handig voorbeeld van luie evaluatie is het gebruik van quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Als we nu het minimum van de lijst willen vinden, kunnen we definiëren

minimum ls = head (quickSort ls)

Die eerst de lijst sorteert en dan het eerste element van de lijst neemt. Door luie evaluatie wordt echter alleen het hoofd berekend. Als we bijvoorbeeld het minimum van de lijst [2, 1, 3,]nemen, zal quickSort eerst alle elementen uitfilteren die kleiner zijn dan twee. Dan doet het daar snel op sorteren (teruggeven van de singleton-lijst [1]), wat al genoeg is. Vanwege luie evaluatie wordt de rest nooit gesorteerd, wat veel rekentijd bespaart.

Dit is natuurlijk een heel eenvoudig voorbeeld, maar luiheid werkt op dezelfde manier voor programma’s die erg groot zijn.

Er is echter een keerzijde aan dit alles: het wordt moeilijker om de runtime-snelheid en het geheugengebruik van uw programma te voorspellen. Dit betekent niet dat luie programma’s langzamer zijn of meer geheugen in beslag nemen, maar het is goed om te weten.

Antwoord 3, autoriteit 70%

Ik vind luie evaluatie nuttig voor een aantal dingen.

Ten eerste zijn alle bestaande luie talen puur, omdat het heel moeilijk is om over bijwerkingen te redeneren in een luie taal.

Met zuivere talen kunt u redeneren over functiedefinities met behulp van vergelijkingsredeneringen.

foo x = x + 3

Helaas komen er in een niet-luie omgeving meer instructies niet terug dan in een luie omgeving, dus dit is minder handig in talen als ML. Maar in een luie taal kun je gerust redeneren over gelijkheid.

Ten tweede zijn veel dingen zoals de ‘waardebeperking’ in ML niet nodig in luie talen zoals Haskell. Dit leidt tot een grote opruiming van de syntaxis. ML-achtige talen moeten trefwoorden als var of fun gebruiken. In Haskell vallen deze dingen samen tot één begrip.

Ten derde kun je door luiheid zeer functionele code schrijven die in stukjes kan worden begrepen. In Haskell is het gebruikelijk om een ​​functietekst te schrijven zoals:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Hiermee kunt u ‘top-down’ werken door de hoofdtekst van een functie te begrijpen. ML-achtige talen dwingen je om een ​​lette gebruiken die strikt wordt geëvalueerd. Daarom durf je de let-clausule niet naar het hoofdgedeelte van de functie te ‘heffen’, want als het duur is (of bijwerkingen heeft), wil je niet dat het altijd wordt geëvalueerd. Haskell kan de details expliciet naar de waar-clausule ‘duwen’ omdat hij weet dat de inhoud van die clausule alleen zal worden geëvalueerd als dat nodig is.

In de praktijk hebben we de neiging om bewakers te gebruiken en die verder in te klappen om:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Ten vierde biedt luiheid soms een veel elegantere uitdrukking van bepaalde algoritmen. Een luie ‘quick sort’ in Haskell is een one-liner en heeft het voordeel dat als je alleen naar de eerste paar items kijkt, je alleen kosten betaalt die evenredig zijn aan de kosten om alleen die items te selecteren. Niets verhindert u om dit strikt te doen, maar u zou het algoritme waarschijnlijk elke keer opnieuw moeten coderen om dezelfde asymptotische prestatie te bereiken.

Ten vijfde: luiheid stelt je in staat om nieuwe besturingsstructuren in de taal te definiëren. Je kunt geen nieuwe ‘if .. then .. else ..’-achtige constructie in een strikte taal schrijven. Als u een functie probeert te definiëren zoals:

if' True x y = x
if' False x y = y

in een strikte taal zouden beide takken worden geëvalueerd, ongeacht de waarde van de voorwaarde. Het wordt nog erger als je kijkt naar loops. Alle strikte oplossingen vereisen de taal om u een soort offerte of expliciete lambda-constructie te bieden.

Ten slotte, in dezelfde geest, kunnen enkele van de beste mechanismen voor het omgaan met bijwerkingen in het typesysteem, zoals monaden, echt alleen effectief worden uitgedrukt in een luie omgeving. Dit kan worden gezien door de complexiteit van F#’s Workflows te vergelijken met Haskell Monads. (Je kunt een monade in een strikte taal definiëren, maar helaas faal je vaak voor een of twee monadewetten vanwege een gebrek aan luiheid en Workflows in vergelijking met een hoop strikte bagage.)

Antwoord 4, autoriteit 28%

Er is een verschil tussen normale volgorde-evaluatie en luie evaluatie (zoals in Haskell).

square x = x * x

De volgende uitdrukking evalueren…

square (square (square 2))

… met enthousiaste evaluatie:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

… met normale bestellingsevaluatie:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

… met luie evaluatie:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Dat komt omdat luie evaluatie naar de syntaxisstructuur kijkt en boomtransformaties uitvoert…

square (square (square 2))
           ||
           \/
           *
          / \
          \ /
    square (square 2)
           ||
           \/
           *
          / \
          \ /
           *
          / \
          \ /
        square 2
           ||
           \/
           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

… terwijl normale volgorde-evaluatie alleen tekstuele uitbreidingen doet.

Daarom worden we, wanneer we luie evaluatie gebruiken, krachtiger (evaluatie eindigt vaker dan andere strategieën), terwijl de prestatie gelijk is aan enthousiaste evaluatie (tenminste in O-notatie).

Antwoord 5, autoriteit 26%

Luie evaluatie gerelateerd aan CPU op dezelfde manier als garbage collection gerelateerd aan RAM. Met GC kun je doen alsof je een onbeperkte hoeveelheid geheugen hebt en dus zoveel objecten in het geheugen opvragen als je nodig hebt. Runtime zal automatisch onbruikbare objecten terugwinnen. Met LE kun je doen alsof je onbeperkte rekenbronnen hebt – je kunt zoveel berekeningen doen als je nodig hebt. Runtime zal gewoon geen onnodige (voor bepaalde gevallen) berekeningen uitvoeren.

Wat is het praktische voordeel van deze “doen alsof” modellen? Het ontslaat de ontwikkelaar (tot op zekere hoogte) van het beheer van bronnen en verwijdert enige standaardcode uit uw bronnen. Maar belangrijker is dat u uw oplossing efficiënt kunt hergebruiken in een bredere reeks contexten.

Stel je voor dat je een lijst met nummers S en een nummer N hebt. Je moet het nummer N vinden dat het dichtst bij nummer M ligt in lijst S. Je kunt twee contexten hebben: enkele N en een lijst L van N’s (ei voor elk N in L zoek je de dichtstbijzijnde M op in S). Als u luie evaluatie gebruikt, kunt u S sorteren en binair zoeken toepassen om de dichtstbijzijnde M tot N te vinden. Voor een goede luie sortering zijn O(size(S))-stappen nodig voor enkele N en O(ln(size(S))* (size(S) + size(L))) stappen voor gelijk verdeelde L. Als je geen luie evaluatie hebt om de optimale efficiëntie te bereiken, moet je een algoritme voor elke context implementeren.

Antwoord 6, autoriteit 26%

Als je Simon Peyton Jones gelooft, is luie evaluatie per seniet belangrijk, maar alleen als een ‘haarshirt’ dat de ontwerpers dwong om de taal zuiver te houden. Ik heb sympathie voor dit standpunt.

Richard Bird, John Hughes en in mindere mate Ralf Hinze zijn in staat om verbazingwekkende dingen te doen met een luie evaluatie. Het lezen van hun werk zal je helpen het te waarderen. Goede uitgangspunten zijn Bird’s magnifieke Sudoku-oplosser en Hughes’ paper over Waarom functioneel programmeren belangrijk is.

Antwoord 7, autoriteit 13%

Overweeg een boter-kaas-en-eieren-programma. Dit heeft vier functies:

• Een functie voor het genereren van zetten die een huidig ​​bord neemt en een lijst met nieuwe borden genereert, elk met één toegepaste zet.
• Vervolgens is er een “zetboom”-functie die de functie voor het genereren van zetten toepast om alle mogelijke bordposities af te leiden die hieruit zouden kunnen volgen.
• Er is een minimax-functie die door de boom loopt (of mogelijk slechts een deel ervan) om de beste volgende zet te vinden.
• Er is een bordevaluatiefunctie die bepaalt of een van de spelers heeft gewonnen.

Dit zorgt voor een mooie duidelijke scheiding van zorgen. Met name de functie voor het genereren van zetten en de functies voor het evalueren van het bord zijn de enige die de spelregels moeten begrijpen: de functies voor het genereren van zetten en minimax zijn volledig herbruikbaar.

Laten we nu proberen schaken te implementeren in plaats van boter-kaas-en-eieren. In een “gretige” (d.w.z. conventionele) taal zal dit niet werken omdat de verplaatsingsboom niet in het geheugen past. Dus nu moeten de functies voor het evalueren van het bord en het genereren van zetten worden gemengd met de zetboom en de minimax-logica, omdat de minimax-logica moet worden gebruikt om te beslissen welke zetten moeten worden gegenereerd. Onze mooie strakke modulaire structuur verdwijnt.

Echter in een luie taal worden de elementen van de verplaatsingsboom alleen gegenereerd als reactie op de eisen van de minimax-functie: de hele verplaatsingsboom hoeft niet te worden gegenereerd voordat we minimax los laten op het bovenste element. Dus onze strakke modulaire structuur werkt nog steeds in een echt spel.

Antwoord 8, autoriteit 12%

Hier zijn nog twee punten die volgens mij nog niet ter sprake zijn gekomen in de discussie.

1. Luie is een synchronisatiemechanisme in een gelijktijdige omgeving. Het is een lichtgewicht en gemakkelijke manier om een ​​verwijzing naar een berekening te maken en de resultaten ervan te delen met vele threads. Als meerdere threads proberen toegang te krijgen tot een niet-geëvalueerde waarde, zal slechts één van hen deze uitvoeren, en de anderen zullen dienovereenkomstig blokkeren en de waarde ontvangen zodra deze beschikbaar komt.

2. Luiheid is fundamenteel voor het afschrijven van datastructuren in een pure omgeving. Dit wordt door Okasaki in detail beschreven in Puur functionele gegevensstructuren, maar het basisidee is dat luie evaluatie een gecontroleerde vorm van mutatie is die essentieel is om ons in staat te stellen bepaalde typen gegevensstructuren efficiënt te implementeren. Hoewel we vaak spreken van luiheid die ons dwingt om het pure haarshirt te dragen, is de andere manier ook van toepassing: het zijn een paar synergetische taalkenmerken.

Antwoord 9, autoriteit 11%

Als u uw computer aanzet en Windows niet elke map op uw harde schijf opent in Windows Verkenner en niet elk afzonderlijk programma start dat op uw computer is geïnstalleerd, totdat u aangeeft dat een bepaalde map nodig is of een bepaald programma nodig, dat is een “luie” evaluatie.

“Luie” evaluatie is het uitvoeren van bewerkingen wanneer en wanneer ze nodig zijn. Het is handig als het een functie is van een programmeertaal of bibliotheek, omdat het over het algemeen moeilijker is om luie evaluatie zelf uit te voeren dan om alles vooraf te berekenen.

Antwoord 10, autoriteit 9%

1. Het kan de efficiëntie verhogen. Dit is het voor de hand liggende, maar het is niet echt het belangrijkste. (Merk ook op dat luiheid ook de efficiëntie kan doden– dit feit is niet meteen duidelijk. Door echter veel tijdelijke resultaten op te slaan in plaats van ze onmiddellijk te berekenen, kunt u een enorme hoeveelheid RAM gebruiken.)

2. Hiermee kun je flow control-constructies definiëren in normale code op gebruikersniveau, in plaats van dat het hard gecodeerd is in de taal. (Java heeft bijvoorbeeld for-lussen; Haskell heeft een for-functie. Java heeft uitzonderingsbehandeling; Haskell heeft verschillende soorten uitzonderingsmonaden. C# heeft goto; Haskell heeft de vervolgmonade…)

3. Hiermee kunt u het algoritme voor het genererenvan gegevens loskoppelen van het algoritme om te beslissen hoeveelgegevens te genereren. U kunt één functie schrijven die een notioneel oneindige lijst met resultaten genereert, en een andere functie die zoveel van deze lijst verwerkt als nodig is. Sterker nog, u kunt vijfgeneratorfuncties en vijfconsumentenfuncties hebben, en u kunt elke combinatie efficiënt produceren – in plaats van handmatig 5 x 5 = 25 functies te coderen die combineren beide acties tegelijk. (!) We weten allemaal dat ontkoppeling een goede zaak is.

4. Het dwingt je min of meer om een ​​purefunctionele taal te ontwerpen. Het is altijd verleidelijk om snelkoppelingen te nemen, maar in een luie taal maakt de geringste onzuiverheid je code wildonvoorspelbaar, wat sterk pleit tegen het nemen van snelkoppelingen.

Antwoord 11, autoriteit 8%

Overweeg dit:

if (conditionOne && conditionTwo) {
  doSomething();
}

De methode doSomething() wordt alleen uitgevoerd als conditionOne waar is enconditionTwo waar is.
In het geval dat conditionOne onwaar is, waarom moet u dan het resultaat van conditionTwo berekenen? De evaluatie van conditionTwo is in dit geval tijdverspilling, vooral als uw aandoening het resultaat is van een methodeproces.

Dat is een voorbeeld van de luie evaluatie-interesse…

Antwoord 12, autoriteit 6%

Een groot voordeel van luiheid is de mogelijkheid om onveranderlijke datastructuren te schrijven met redelijke afgeschreven grenzen. Een eenvoudig voorbeeld is een onveranderlijke stapel (met F#):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack
let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

De code is redelijk, maar het toevoegen van twee stapels x en y kost O (lengte van x) tijd in de beste, slechtste en gemiddelde gevallen. Het toevoegen van twee stapels is een monolithische bewerking, het raakt alle knooppunten in stapel x.

We kunnen de gegevensstructuur herschrijven als een luie stapel:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack
let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazywerkt door de evaluatie van code in zijn constructor op te schorten. Eenmaal geëvalueerd met behulp van .Force(), wordt de geretourneerde waarde in de cache opgeslagen en opnieuw gebruikt bij elke volgende .Force().

In de luie versie zijn appends een O(1)-bewerking: het retourneert 1 knooppunt en onderbreekt het daadwerkelijke opnieuw opbouwen van de lijst. Wanneer je de kop van deze lijst krijgt, zal het de inhoud van het knooppunt evalueren, waardoor het gedwongen wordt de kop terug te geven en één schorsing te creëren met de resterende elementen, dus het nemen van de kop van de lijst is een O(1) operatie.

Dus onze luie lijst wordt voortdurend opnieuw opgebouwd, u betaalt pas de kosten voor het opnieuw opbouwen van deze lijst als u alle elementen ervan hebt doorlopen. Met luiheid ondersteunt deze lijst O(1) consing en appending. Interessant is dat, aangezien we knooppunten pas evalueren als ze zijn geopend, het heel goed mogelijk is om een ​​lijst te maken met potentieel oneindige elementen.

Voor de bovenstaande gegevensstructuur hoeven de knooppunten niet opnieuw te worden berekend op elke traversal, dus ze verschillen duidelijk van de standaard IEnumerables in .NET.

Antwoord 13, autoriteit 5%

Dit fragment laat het verschil zien tussen luie en niet-luie evaluatie. Natuurlijk kan deze fibonacci-functie zelf worden geoptimaliseerd en luie evaluatie gebruiken in plaats van recursie, maar dat zou het voorbeeld bederven.

Laten we aannemen dat we MEIde eerste 20 getallen ergens voor moeten gebruiken, zonder luie evaluatie moeten alle 20 getallen vooraf worden gegenereerd, maar met luie evaluatie zullen ze worden gegenereerd als dat nodig is alleen. U betaalt dus alleen de rekenprijs als dat nodig is.

Voorbeelduitvoer

Niet luie generatie: 0.023373
Luie generatie: 0,000009
Niet luie output: 0.000921
Luie uitgang: 0,024205

import time
def now(): return time.time()
def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)
before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()
before3 = now()
for i in notlazy:
  print i
after3 = now()
before4 = now()
for i in lazy:
  print i
after4 = now()
print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)

Antwoord 14, autoriteit 5%

Luie evaluatie is het handigst bij gegevensstructuren. U kunt een array of vector inductief definiëren door alleen bepaalde punten in de structuur te specificeren en alle andere uit te drukken in termen van de hele array. Hierdoor kunt u zeer beknopte gegevensstructuren genereren met hoge runtime-prestaties.

Om dit in actie te zien, kun je een kijkje nemen in mijn neurale netwerkbibliotheek genaamd instinct. Het maakt veel gebruik van luie evaluatie voor elegantie en hoge prestaties. Ik ben bijvoorbeeld helemaal af van de traditioneel dwingende activeringsberekening. Een simpele luie uitdrukking doet alles voor mij.

Dit wordt bijvoorbeeld gebruikt in de activeringsfunctieen ook in het backpropagation-leeralgoritme (ik kan maar twee links plaatsen, dus je moet de functie learnPatopzoeken in de AI.Instinct.Train.Deltamodule zelf). Traditioneel vereisen beide veel gecompliceerdere iteratieve algoritmen.

Antwoord 15, autoriteit 4%

Andere mensen hebben al de belangrijkste redenen gegeven, maar ik denk dat een nuttige oefening om te helpen begrijpen waarom luiheid belangrijk is, is om te proberen een fixed-pointfunctie in een strikte taal.

In Haskell is een functie met een vast punt supereenvoudig:

fix f = f (fix f)

dit wordt uitgebreid tot

f (f (f ....

maar omdat Haskell lui is, is die oneindige reeks berekeningen geen probleem; de evaluatie gebeurt “van buiten naar binnen”, en alles werkt wonderwel:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

Belangrijk is dat het er niet toe doet dat fixlui is, maar dat flui is. Als je al een strikte fhebt gekregen, kun je ofwel je handen in de lucht gooien en opgeven, of het uitbreiden en dingen opruimen. (Dit lijkt veel op wat Noah zei over het feit dat het de bibliotheekis die streng/lui is, niet de taal).

Stel je nu voor om dezelfde functie in strikte Scala te schrijven:

def fix[A](f: A => A): A = f(fix(f))
val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Je krijgt natuurlijk een stack overflow. Als je wilt dat het werkt, moet je het argument fcall-by-need maken:

def fix[A](f: (=>A) => A): A = f(fix(f))
def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)
val fact = fix(fact1)

Antwoord 16, autoriteit 3%

Ik weet niet hoe u momenteel over de dingen denkt, maar ik vind het nuttig om luie evaluatie te zien als een bibliotheekprobleem in plaats van een taalfunctie.

Ik bedoel dat ik in strikte talen luie evaluatie kan implementeren door een paar datastructuren te bouwen, en in luie talen (tenminste Haskell), kan ik om strengheid vragen wanneer ik dat wil. Daarom maakt de taalkeuze je programma’s niet echt lui of niet-lui, maar beïnvloedt het gewoon wat je standaard krijgt.

Als je er zo over nadenkt, denk dan aan alle plaatsen waar je een datastructuur schrijft die je later kunt gebruiken om data te genereren (zonder er al te veel naar te kijken), en je zult veel zien van gebruikt voor luie evaluatie.

Antwoord 17, autoriteit 3%

Luie evaluatie is de vergelijkingsredenering van de arme man (die idealiter zou kunnen worden verwacht door eigenschappen van code af te leiden uit eigenschappen van de betrokken typen en bewerkingen).

Voorbeeld waar het best goed werkt: sum . take 10 $ [1..10000000000]. Wat we niet erg vinden om teruggebracht te worden tot een som van 10 getallen, in plaats van slechts één directe en eenvoudige numerieke berekening. Zonder de luie evaluatie zou dit natuurlijk een gigantische lijst in het geheugen creëren om alleen de eerste 10 elementen te gebruiken. Het zou zeker erg traag zijn en zou een fout in het geheugen kunnen veroorzaken.

Voorbeeld waar het niet zo goed is als we zouden willen: sum . take 1000000 . drop 500 $ cycle [1..20]. Die in feite de 1 000 000-nummers optelt, zelfs als ze in een lus zijn in plaats van in een lijst; toch moetworden teruggebracht tot slechts één directe numerieke berekening, met weinig voorwaarden en weinig formules. Wat een stuk beter zou zijndan het optellen van de 1.000.000 nummers. Zelfs als in een lus, en niet in een lijst (d.w.z. na de ontbossingsoptimalisatie).

Een ander ding is, het maakt het mogelijk om te coderen in tail recursie modulo consstijl, en het werkt gewoon.

zie gerelateerd antwoord.

18, Autoriteit 2%

Onder andere, laten luie talen multidimensionale oneindige gegevensstructuren toe.

Tijdens het schema, Python, enz. Sta single dimensionale oneindige gegevensstructuren toe met streams, u kunt alleen langs één dimensie doorkruisen.

Luiheid is handig voor de hetzelfde frons-probleem , maar het is de moeite waard om de Coroutines-verbinding te vermelden in die link.