2. Ämnesbeskrivningar

2.1. Lambda-kalkyl

2.1.1 Inledning

Lambda-kalkylen är ett sätt att beskriva funktioner så att de kan hanteras mekaniskt. Lambda-kalkylen kan alltså för de funktionella språken jämföras med automatateorin för imperativa.

Lambdakalkylen ger också en beskrivning av begreppen beräkning och beräkningsordning.

Grundläggande i lambdakalkylen är tre regler för förenkling/beräkning, alfa, beta och eta-reglerna. Med vissa val av representationer, om alla objekt, även de naturliga talen, avbildas på funktioner, kan alla beräknningar utföras med dessa tre regler.

2.1.2 Projekt

Skriv en funktion som reducerar ett lambdauttryck så långt det går. Avbilda de naturliga talen på lambda-uttryck och räkna ut uttryck såsom 1+1=2 i denna representation.

2.1.3 Litteratur

Avsnitten om lambdakalkyl och denotationssemantik i nedanstående böcker: Stoy, Denotional Semantics, MIT Press

Petersson, Beräknebarhet för dataloger, Aquila

Barklund, Kursmaterial för Program och Maskinsemantik, utdrag

Gamla föreläsningsanteckningar, vissa böcker i utdrag i kursbiblioteket

2.2. Logikprogrammering

2.2.1 Inledning

Programmeringsspråket Prolog är baserat på logik. Ett Prologprogram kan läsas och förstås som logik, eller, om man hellre vill, som en beskrivning av vad som ska göras. Det fruktbara sättet att se programmet brukar dock vara som logik.

Allt som kan sägas i "vanlig predikatlogik" kan alltså också sägas i Prolog. Vissa predikatlogiska formler måste emellertid skrivas om innan de blir exekverbara såsom Prologprogram.

Studera följande lilla Prologprogram. 


universitetslarare(X) :- trevlig(X).
universitetslarare(X) :- tokig(X).

trevlig(roger).
trevlig(lars).
trevlig(jan).

tokig(anders).

vis(lars).

studierektor(X) :- universitetslarare(X), vis(X).
Programmets sista rad kan läsas som:

För alla X gäller, att X är studierektor om X är universitetslärare och X är vis.
eller
Om någon X är vis och detta X är universitetslärare, så är detta X studierektor.

Raderna i prologprammen är implicit allkvantifierade. Raderna läses alltså som om det stode en allkvantor (") följt av radens variabler först på raden. Symbolen :- motsvarar u, kommatecken motsvarar &.

Man kan se ett Prologprogram som en databas, mot vilken man kan ställa frågor. Prologintepretatorn härleder svaren på de ställda frågorna.

Exempel. 

universitetslarare(anders)?
yes

universitetslarare(batman)?
no

tokig(X)?      X är en variabel, tolkningen här är
               "Vilket X, dvs vem, är tokig?"
X = anders

Prolog-program kan ge mnga svar, ty en relation är en många-till-många-mappning: 

universitetslarare(X)?
X=christer
more
X=tina
more?
X=janne
more?
X=anders
more?
no
För att göra detta visar Prologinterpretatorn med hjälp av resolution (en logisk härledningsmetod) att vi från programmet (en mängd av satser) kan härleda en sats (den fråga vi ställde till programmet), samt för vilka objekt detta gäller.

Prologprogram har ingen given beräkningsriktning i den bemärkelse att ingen parameter är bestämd som "in-" respektive "ut-"parameter. Prologprogram kan således "räkna baklänges".

Studera nedanstående exempel:



larare_till(platon,sokrates).	    Lärare till Platon är Sokrates
larare_till(aristoteles,platon).

larjunge_till(X,Y):-larare_till(Y,X).	Lärjunge till X är Y om Y är lärare till X.
med frågorna och svaren: 
larare_till(platon,A)?
A=sokrates
larare_till(A,platon)?
A=aristoteles
larjunge_till(A,platon)?
A=sokrates
larjunge_till(A,B)?
A=sokrates B=platon
more?
A=platon B=aristoteles
more?
no

2.2.2 Projekt för två enhet:

Tre missionärer och tre kannibaler ska korsa en flod. En båt finns tillgänglig och den rymmer två personer. Båten kan navigeras av en eller två personer, och det spelar ingen roll om den navigeras av missionärer eller kannibalerna, alla kan navigera. Missionärerna fruktar, att om kannibalerna vid något tillfälle skulle vara fler på samma strand än missionärerna, så skulle kannibalerna skaffa sig en festmåltid av missionärskött.

Hitta ett sätt för de sex personerna att korsa floden lugna.

Idé 1: Ett av flera sätt att lösa uppgiften är att definiera ett predikat tillstand(KannibalerNorr,KannibalerSyd,MissionärerNorr,MissionärerSyd,VarärBåten), som är giltigt då variablerna är instansierade till värden som representerar ett möjligt tillstånd. Eventuellt kan ytterligare argument behövas.

Idé 2: Du kan finna följande idé användbar (den kommer nog att förenkla det slutgiltiga programmet) . Definiera ett icke-deterministiskt predikat plus(X,Y,Z), som givet ett eller två parametervärden, beräknar det eller de saknande värdena. Om du representerar de naturliga talen med efterfäljarefunktionen s, så att 0,1,2,3.... skrivs 0, s(0), s(s(0)), s(s(s(0)))....blir predikatet lätt att definiera. En sådan representation av de naturliga talen är godtagbar i din lösning.

Kommentar: Vi antar , på klassiskt utbildningsmaner, att uppgiften innehåller all information om problemet. Således finns inga vadställen, inga helikoptrar eller broar tillgängliga, ej heller kan missionärerna påverka kannibalerna att ändra sina antagna vanor. Ett intressant fält inom AI-forskning idag är studier av de situationer där den här typen av förenklingar inte kan göras, dvs där man vill modellera en verklig (eller åtminstone verkligare) situation. Hur formaliserar man lämpligt otillräcklig eller motsägelsefull kunskap? Vilka metoder för slutsatsdragning är tillämpliga?

Du behöver inte bekymra dej huruvida ditt program verkligen ger alla lösningar interaktivt (men den måste ge minst några lösningar), eller om samma lösning kan förekomma två gånger, om du söker alla lösningar.

2.2.3 Litteratur:

Sterling-Shapiro, The Art of Prolog, MIT Press
Bratko, Prolog programming for Artificial Intelligence, Addison-Wesley.
Båda dessa böcker täcker väl stoffet och är bra läroböcker.

2.2.4 Förslag till arbetsgång:

Följ den bok du väljer. Du måste naturligtvis skriva flera program, förmodligen ganska många, innan det "lönar sig" att ge sig på projektet.

2.3. Programmeringsspråket Haskell

2.3.1 Inledning

Haskell är ett typat funktionellt språk, med teoretiska riktiga och tilltalande språkkonstruktioner för användning av högre ordningens funktioner. Haskell har lat evaluering, och är anpassat för oändliga strukturer. Dessa begrepp finns beskrivna i ett tidigare avsnitt.

Ett par exempel kan illustrera den mycket kompakta programkoden. Om du läser denna "som matematik" och inte "som data", är den lättförståelig.

Exempel 1 

[n * n | n <- [0 ..]]       		en lista av kvadraten av alla heltal från 0

Exempel 2 


[r | r <- [1 .. n div 2]; n mod r = 0]  en lista av faktoriseringen av n, ty 
			                r är varje tal mellan 1 och n/2 och n 
                   		        modulo r är noll

Exempel 3 

quicksort[]=[]
quicksort(x:xs) = quicksort[y | y <- xs; y<x]
                 ++[x]
                ++ quicksort[z | z <- xs; z>=x]
Läs så här:
quicksort av en tom lista är en tom lista.
quicksort av en lista som kan delas upp i ett första element x och en rest xs är
quicksorteringen av en listan av alla y i xs, sådana att y<x, appendat med listan av x,
appendat med listan av alla z i xs, sådana att y>=x.

2.3.2 Tillgänglighet

Språket finns som freeware och uppfyller högt ställda krav på driftssäkerhet. Det är tillgängligt på SUNarna.

En del tips finns.

2.3.3 Litteratur:

Bra kompendium som kan köpas/kopieras.

2.3.4 Förslag till uppgift:

Studera följande talserie av primtal: 
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ....
Primtalen kommer "ibland" parvis 
<3,5>, <5,7>, <11,13>, <17,19>, <29,31> ...
Skriv en funktion som genererar denna (möjligtvis?) oändligt långa lista av tal. Ditt program ska använda algoritmen Erathosetenes såll, som återfinns i läroböcker i algebra. Programmet ska på ett meningsfullt sätt använda sig av lat evaluering.

2.4. Programmeringsspråket FP

2.4.1 Inledning

Ett exempel på ett FP-program, med ett försök till förklaring: Funktionen subset tar en lista med två dellistor (en bild av mängder) och avgör om den ena är en delmängd av den andra:

DEF Subset AS distl | EACH member END | and;

Läs ungefär så här i ett exempel "anrop" exempel:
show <<4,2,5,1,3> <1,2,3>> : Subset

Distribuera den ena listans element över den andra:
<<<4,2,5,1,3>,1 > <<4,2,5,1,3>2,> <<4,2,5,1,3>3,>> : EACH member END | and

Applicera medlem på varje på så sätt producerat par <lista, element>:
< T, T, T> : and

Applicera and på alla element i den skapade listan:
T

2.4.2 Tillgänglighet

Språket finns i en dialekt IFP som freeware och har enstaka, små buggar. Det är tillgängligt på SUNarna.

En del tips finns.

2.4.3 Litteratur

En bra artikel om de bärande idéerna. En vettig manual.

Båda i kursbiblioteket.

2.4.4 Uppgift

Samma uppgift som i Haskell, se 2.3.4. Uppgiften ska i FP lösas utan rekursion, utom i de fall rekursion noggrant kan motiveras. Din lektion bör bygga på små exempel, i stigande svårighet. Det finns inga skäl att göra en fullständig genomgång av alla fördefinierade funktioner i FP.

Du bör under din lektion välja att hålla dig till en syntax, exvis IFP, men du ska även prata om grundläggande idéer, exvis från Bacchus artikel.

2.5. Programmeringsspråket Erlang

2.5.1 Inledning

Erlang är utvecklat av Ellemtel för att skapa prototyper av parallella distribuerade realtidssystem. Språket är funktionellt, men med vissa begrepp, speciellt unifiering (matchning), från logikprogrammeringsspråk. Språket har en väl utvecklad felhantering.

2.5.2 Tillgänglighet

Språket finns tillgängligt på SUNarna.

2.5.3 Litteratur

Anges av handledaren.

2.5.3 Förslag till uppgift

Skriv en distribuerad "simulator" som löser det välkännda dining philosophers problem för ett givet antal filosofer. (För en beskrivning av problemet se valfri lärobok i operativsystem eller sök på nätet.)

Simulatorn skall vara distribuerad på minst två olika maskiner.

2.6. En interpretator för Lisp i Lisp

2.6.1 Inledning

En komplett interpretator för Lisp i Lisp kan beskrivas som meta-cirkulär. För att förklara en sådan behöver vi beskrivningar av syntax, omgivning (en funktion utvärderas i en omgivning där eventuella fria variabler, dvs variabler som inte finns i variabellistan har värden), objekt och funktioner. För operationer på dessa finns Lisp-funktionerna eval och apply.eval tar en godtycklig Lisp-form, avgör om den är en "vanlig funktion" - i så fall ska den utvärderas av apply , annars av eval .

Exempel

Användarsnittet i en Lisp-interpretator kan beskrivas så här 


(do forever
  (print (eval (read))))
där eval tar en programspråkskonstruktion i Lisp och returnerar värdet av denna. Idé om hur eval kan se ut 

(defun eval (e env)
  (cond ((isconst e) (denote e)
        ((isvar e) (lookup e env)) 
        ((iscond e)
         (evcond (arg e) env))
        ((isquote e) (dequote e))
        ((isfunc+arg e)
         (apply (func e)
                (evalarg (arglist e)
                         env)
                env))))
där

apply applicerar en funktion på utvärderade argument

evalarg utvärderar argument

2.6.2 Uppgift

2.6.3 Litteratur

Allen, The Anatomy of Lisp. Boken kan lånas för kopiering.

Darlington m.fl., Functional Programming and its Applications, kap "Interpreters for Functional Languages", s 253. Boken kan lånas för kopiering.

2.7. Lispinterpretator i Prolog

I denna uppgift ska du implementera en Lisp-interpretator i Prolog i stället för i Lisp. Du får, om du vill, vilket rekommenderas, använda Prolog-syntax för din Lisp.

2.8. Valfri uppgift inom predikatlogik

Valfri uppgift inom predikatlogik. 

Anders Berglund                        Office: Room 1254
Department of Computer Systems         E-mail: Anders.Berglund@docs.uu.se
Box 325                                Phone (work): +46 18 471 31 67
S-751 05 Uppsala                       Mobile phone: +46 70 582 45 80
Sweden                                 Fax (work):   +46 18 55 02 25
                                       

Senast ändrad: 09/21/98