Declaratieve Talen/OplossingenVraagjes

OPGELET: Deze oplossingen zijn op geen enkele manier nageken door een prof/assistent. Er zitten dus mogelijks fouten in. Als je er vindt, gelieve deze dan te corrigeren ;)

Bespreek het verschil tussen unificatie en pattern matching

Het basisidee is dat pattern matching in 1 richting werkt en unificatie in beide richtingen. Je kan dus bijvoorbeeld een ongebonden variabele unificeren met een andere variabele als volgt: X = Y, X = 5. Y was nog niet gebonden maar heeft uiteindelijk toch de waarde 5. In Haskell, dat met pattern matching werkt, zou er een fout gegeven worden by X = Y.

Wat doet backtracking in Prolog?

Backtracking is een mechanisme dat toelaat alle mogelijke oplossingen voor een query te vinden. Er wordt bij het uitvoeren van een query namelijk een uitvoeringsboom opgesteld waar elk element van de boom een deelquery is. Als zo'n deelquery slaagt, wordt er aan een ongebonden variabele een waarde gegeven en wordt de uitvoeringsboom uitgediept. Als een deelquery faalt wordt er aan de laatst toegekende ongebonden variabele een andere waarde gegeven. Als alle mogelijke waarden geprobeerd zijn faalt de deelquery en wordt er terug naar boven 'gebacktracked'.

Wat zijn de voor en nadelen van luie uitvoering in Haskell?

+ Mogelijkheid tot oneindige datastructuren (bvb take 5 [1..] of fibs)

+ Hogere performantie: onnodige berekeningen worden vermeden (bvb head (map (2 *) [1 .. 10]) enkel het eerste element van de lijst wordt berekend)

- IO wordt moeilijker omdat voor IO een strikte volgorde nodig is

- Debuggen wordt moeilijker

- Het wordt moeilijker om de snelheid en het geheugengebruik tijdens de runtime van je programma te voorspellen

Hoe is in Haskell sprake van generisch programmeren?

Haskell heeft typeklassen zoals Eq (equivalentie) en Show (vergelijkbaar met een toString() in Java). Als je bijvoorbeeld een nieuw type BTree aanmaakt als volgt:

 data BTree a = Leaf a | Node (BTree a) a (BTree a) deriving (Eq, Show).

BTree heeft dan sowieso een definitie van == en show voor elke BTree van type T als T zelf deze operaties ondersteund. Een eenvoudiger voorbeeld van generisch programmeren is bijvoorbeeld de functie

 lengte :: [a] -> Integer.

a is hier een generisch type parameter. De functie lengte is als volgt verder gedefinieerd:

 lengte [] = 0
 lengte (h:r) = 1 + lengte r

Deze functie kan dus gebruikt worden voor elk type a en is dus generisch.

Wanneer doet Prolog aan garbage collection

Prolog doet aan garbage collection als er gebacktracked wordt in de uitvoeringsboom. Takken die volledig uitgediept zijn (en dus niet meer nodig) worden verwijderd uit de uitvoeringsboom en de bijhorende variabelen worden dus verwijderd uit het geheugen.

Bespreek meta-programmatie in Prolog

De twee basispredicaten voor meta-programmatie zijn =.. en call. Een simpel voorbeeld is een implementatie van map:

 map(FunctionName,[H|T],[NH|NT]):-
     Function=..[FunctionName,H,NH],
     call(Function), map(FunctionName,T,NT).

map(_,[],[]). = .. laat dus toe een een predicaat samen met zijn argumenten op te slaan in een lijst. call roept dan het predicaat (1e element van de lijst) op met de meegegeven argumenten (andere elementen van de lijst). Een ander handig predicaat is clause(H,B) dat in de huidige kennisbank van Prolog zoekt naar een clause met een hoofd dat unificeert met H en een body dat unificeert met B. Als de clause geen body heeft is B true.

Wat is de functie van typeklassen in Haskell (en Mercury)

Typeklassen zoals Eq, Show en Read laten toe om voor verschillende types een bepaalde gemeenschappelijke functie te definieren. Bijvoorbeeld de gelijkheid == is voor bijna elk type handig maar is ook voor bijna elk type verschillend. In plaats van verschillende equivalentie functies zoals

 equalsInteger:: Integer -> Integer -> Bool

en

 equalsString :: String -> String -> Bool

te definieren kan je met behulp van typeklassen een instantie van Eq aanmaken voor Integers en String. Een vb:

 instance Eq Integer where  
       x == y   =  x `integerEq` y