Programmeringuppgift 4

Lös 1 av nedanstående uppgifter

a. Turingmaskin

Skriv en funktion i Lisp som modellerar en universell Turing-maskin.

Funktionen ska ta två argument: en godtycklig Turing-maskin, M, och en godtycklig tejp. Funktionen ska returnera en tejp, med samma innehåll som M skulle ge för input-tejpen. Programmera gärna M.

I din rapport ska finnas en kortfattad diskussion om erfarenheterna att implementera en icke-funktionell ("goto-") maskin i ett funktionellt språk.

b. Multinationellt företag

Insatiable Enterprises, Inc., är ett decentraliserat företag som består av ett stort antal oberoende dotterföretag placerade runt hela världen. Varje dotterföretag består i sig av avdelningar och/eller ett antal dotterföretag. Varje avdelning består av ett antal personer och/eller projekt i vilka det ingår ett antal personer. En person har ett efternamn och ett visst födelsedatum.

För att hantera problemställningarna kring företaget är följande primitiver givna:
company-p[x] är sann om x är ett företag eller ett dotterföretag
division-p[x] är sann om x är en avdelning
project-p[x] är sann om x är ett projekt
person-p[x] är sann om x är en person
name-before-p[x;y] är sann om namnet x kommer före namnet y med avseende på bokstavsordning
parts-of[x] om x är ett företag returneras en lista av alla dotterföretag och/eller avdelningar
om x är en avdelning returneras en lista av personer och/eller projekt
om x är ett projekt returneras en lista av personer
last-name[person] returnerar en persons efternamn
date-of-birth[person] returnerar en persons födelsedatum, såsom en lista bestående av år månad och dag, i den ordningen, ex. (1964 5 29)

Insatiables VD tycker om tårta. Skriv en funktion åt henne som skapar en lista av listor, där dellistorna innehåller alla anställda med samma födelsedag ordnade i bokstavsordning efter sitt efternamn. Dellistorna ska dessutom vara ordnade efter födelsedag (se exemplet nedan). Insatiables VD kan sedan spika upp födelsedagsbarnen på anslagstavlan, en dellista för varje dag.
(Förhoppningsvis känner sig någon manad att bjuda dem på en tårta!)

Exempel Vi har följande personer (aningen osannolikt - medhålles!):
Namn Födelsedag
Andersson (1963 5 29)
Höök (1964 5 29)
Janson (1963 11 27)
Gurka (1945 5 29)
Åhs (1932 11 27)
Berglund (1956 4 15)

Som svar vill vi ha en lista av tre dellistor. Berglund ensam i den första dellistan. Anderson, Gurka och Höök i den ordningen i den andra dellistan. I den tredje dellistan vill vi ha Janson följt av Åhs. (Varje person representerad av efternamn och födelsedatum.)
Maj är nämligen före november på året och den 4:e november är före den 27 november.

Du ska använda och implementera de funktioner som finns angivna i uppgiften.

Anvisningar

Uppgiften får lösas individuellt eller i grupper om två. Uppgiften ska redovisas skriftligt med Programmet ska i sin helhet spegla en god programmeringsed för funktionella språk Ingen felhantering behövs.

Handledning ges av Kjell Post, på anslagna tider. Uppgiften lämnas till Kjell Post.

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 425 02 11
Sweden                                 Fax (work):   +46 18 55 02 25
                                       

Senast ändrad: 08/30/97 19:08:33