Evaluering av uttryck

En formell beskrivning av ett funktionellt språk som påminner väldigt mycket om Erlang. Vi bygger upp det från grunden för att förstå vilka egenskaper språket har och vid vilka tillfällen vi har ett val att göra som bestämmer hur vårt språk skall definieras.

Innan föreläsningen skall ni ha kommit igång med Erlang så at ni kan börja experimentera med dess topp-loop och skriva mycket enkla funktioner.  Ni skall ha läst igenom kapitel 1 och 2 i kursboken.

• evaluation.pdf 
• functions.pdf

Observera att föreläsningen inte går igenom Erlang från en praktiskt aspekt, den kunskapen får ni från kursboken. 

Efter föreläsningen

Ta och börja på den första inlämningsuppgiften - det gäller att starta i tid. Se till så att ni kommit så långt att övningstillfället nästa vecka blir väl utnyttjat för att få till de sista pusselbitarna.

För den vetgirige

Den presentation som ges under föreläsningen kan tyckas vara formell och inkludera det mesta men vi har faktiskt utelämnat en del saker. För den som vill läsa lite mer om hur man kan definiera funktionella språk i termer av lambdakalkyl och se ge en operationell semantik till sitt språk kan titta på följande referenser:

• The Implementation of Functional Programming Languages, Simon L. Peyton Jones är en klassisk bok i sammanhanget. Man behöver inte läsa hela men man kan titta igenom de första kapitlen och se att väldigt mycket följer vårt angreppssätt. I boken ges ett apråk "Miranda" en beskrivning genom att det översätts till lambdakalkyl. Uttryck i lambdakalkylen ges sen en betydelse genom att översättas till operationer i en abstrakt maskin.  
• Simon Peyton Jones är väl värd att lyssna på, här ett framträdande på TEDx: Teaching Creative Computer Science.

Hur fuskade vi

Jag nämnde att vi utelämnat en del saker och vi har faktiskt varit lite otydliga. I vår beskrivning av språket har vi egentligen inte givet en fullständig operationell semantik. Vi har varit lite yviga när vi sagt "den hör regeln får vi tillämpa om ..."  eller "först evaluerar vi det hör och sen ..". Om vi skulle gen en korrekt operationell semantik så skulle vi inte ha lämnat sådan luckor i beskrivningen. När vi går från vår beskrivning av språket till en implementation så måste vi hitta lösningar för dessa luckor. I vårt fall är det inte så svårt och jag vet att dessa luckor går att fylla, men om vi verkligen skulle spika en definition av vårt språk så skulle vi naturligtvis vilja veta 1/ att de går att göra 2/ vilken komplexitet dessa lösningar har.

Vi skulle kunna utöka beskrivningen av vårt språk till exempel genom att tala om, inte ett uttryck eller sekvens under evaluering utan om en stack av uttryck. Att evaluera en mönster-matchning skulle i så fall betyda att vi lägger evalueringen av högerledet på stacken mm. Vi kommer att parar mer om detta senare i kursen.

En annan genväg vi tog var att inte prata om hur funktionsuttryck skall hanteras. Om vi har mönstermatchningen "X = fun(Y) -> Y + Z end" så skall vi ju enligt våra nuvarande regler evaluera "fun(Y) -> 2 + Z end" och få en datastruktur. Vi har dock inga funktioner i vår domän så det blir ju lite problematiskt.  Vi måste också knyta funktionen till en omgivning så att vi vet vad "Z" är och det blir ännu mer huvudbry. Allt kommer dock att lösa sig så var inte oroliga.