Luie evaluatie

In programmeertalen is luie evaluatie (in het Engels: lazy evaluation) een evaluatie-strategie. Het wordt soms ook Call-by-need genoemd. Het idee is dat een uitdrukking pas geëvalueerd wordt wanneer ze daadwerkelijk nodig is. Voorbeelden van programmeertalen die een luie evaluatie hanteren zijn Haskell en Scala.

Overzicht

De voordelen van luie evaluatie zijn: verbeterde prestaties door het vermijden van overbodige berekeningen, het vermijden van foutieve situaties in gecombineerde expressies en de mogelijkheid om om te gaan met oneindige datastructuren. Ook is het mogelijk controlestructuren als functies te definiëren in plaats van ingebouwde structuren.

Programmeertalen die gebruikmaken van luie evaluatie kunnen verder onderverdeeld worden in talen die een call-by-name of een call-by-need-evaluatiestrategie gebruiken. De meeste luie programmeertalen, zoals Haskell, maken gebruik van een call-by-needstrategie omwille van de snelheid maar bij theoretische berekeningen met luie evaluatie gebruikt men call-by-name omwille van de eenvoud.

Het tegenovergestelde van luie evaluatie is strikte evaluatie (in het Engels: strict evaluation).

Voorbeelden

Oneindige lijsten

Een voorbeeld van luie evaluatie in Haskell waarbij gebruik wordt gemaakt van een oneindige lijst:

takeWhile (<10) (map (+1) [1..])

De notatie [1..] geeft een oneindige lijst van gehele getallen vanaf 1. Het opbouwen van deze oneindige lijst is niet mogelijk in talen met strikte evaluatie maar door luie evalutie is het wel mogelijk er berekeningen mee uit te voeren. De hogere-ordefunctie map past een functie toe op alle elementen in een lijst (in dit geval wordt bij elk element in de oneindige lijst één opgeteld). De functie takeWhile neemt elementen van het begin van een lijst zolang een bepaalde voorwaarde geldt (in dit geval zolang de elementen kleiner zijn dan 10).

Door luie evaluatie zal eerst het eerste element van de lijst berekend worden door één keer de functie (+1) toe te passen op het eerste element van de lijst (1). Als deze (1+1 = 2) aan de voorwaarde "kleiner dan 10" voldoet dan zal het volgende element berekend worden. Op deze wijze wordt een nieuw element van de oneindige lijst pas berekend als het echt nodig is voor het antwoord. Wanneer de voorwaarde niet meer geldt, wordt de rest van de lijst ook niet meer uitgerekend.

Rij van Fibonacci

Door luie evaluatie is het mogelijk om de lijst met Fibonaccigetallen als volgt te definiëren (met behulp van corecursie):

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

waarbij : een functie is om een element op kop van een lijst te zetten, tail een functie om de gehele lijst behalve het eerste element te verkrijgen en zipWith een functie om twee lijsten met elkaar te verbinden met behulp van een andere functie (de plus-operator in dit geval). Deze aanpak wordt in lineaire tijd uitgevoerd.