Anteckningar om Lisp som funktionellt programmeringsspråk

1. Datatyper i Lisp

De grundläggande abstrakta datatyperna (ADTer) i Lisp kan anses vara atomer och listor. Dessa datatyper används både för representation av program och data.

För att fullständigt beskriva en ADT krävs enligt Cleaveland kännedom om

Specifikationen anger hur program kan använda ADTer, dvs hur de funktioner och procedurer som "innesluter" data används.

2. Syntax och semantik

Syntax beskriver "utseendet" eller "formen" hos ett språk (i vårt fall för representationen av funktioner och data).Semantiken beskriver "betydelsen" eller "meningen" hos ett språk (i vårt fall vad våra procedurer "gör" eller vilka värden våra funktioner returnerar och betydelsen av ett dataobjekt).

Implementationen behöver vi inte intressera oss för om vi bara vill använda atomer och listor.

3. Listor

Syntaxen för listor kan beskrivas som

        list ::= (listinnehåll) | ()

        listinnehåll::=element | element listinnehåll

        element ::= lista | atom

Således kan en lista antingen vara tom eller innehålla element. Dessa element kan vara antingen atomer eller listor. En atom kan ses som Lisps minsta odelbara enhet till vilken t ex värden eller funktionsdefinitioner kan bindas.

Exempel

        (A B C)

        () 

        (A B (C D) ())

4. Värden för atomer

Värdet av de numeriska atomer är de tal som de representerar (med andra ord, helt enkelt som man tror:

Exempel
2 betyder två, osv.

Andra värderingsregler:

"Bokstavsatomer", literals, saknar fördefinierade värden, men vi kan binda värden till dem.

Man kan, av teoretiska skäl, på NIL och T å ena sidan, och sant och falskt å andra.

5. Funktioner på listor

För att kunna hantera data har vi följande funktioner (på en icke-exekverbar, men väl läsbar syntax):

first[l] en funktion som tar ett argument, en lista. Funktionen returnerar det första elementet i listan.
rest[l] en funktion som tar ett argument, en lista.Funktionen returnerar hela listan förutom det första elementet.
concat[x;l] en funktion som tar två argument, ett listelement (dvs en atom eller en lista) och en lista.Funktionen returnerar en lista där x är insatt först i l.
atom[x] en funktion som tar ett argument från valfri domän (dvs av valfri typ). Funktionen avgör om x är en atom eller inte. Funktionen returnerar sant eller falskt.
endp[l] en funktion som tar ett arguement, en lista. Funktionen returnerar sant om l är den tomma listan, falskt annars.
numberp[a] en funktion som tar ett argument, en atom. Funktionen returnerar sant om a är en numerisk atom, falskt annars.
Exempel



        concat[A;(B C)]                 (A B C)

        first[concat[(B D);(C E)]]      (B D)

        atom[(A B)]                     NIL
Notera att Lisp-funktionerna inte påverkar sina argument. De motsvarar således, mycket fritt hållet, funktioner med värdeöverförda parametrar.

6. Primitiver.

Dessa grundläggande funktioner för manipulering av en datatyp kallas ibland primitiver.

De primitiver som returnerar "större" sammansatta objekt kallas konstruktorer, de primitiver som returnerar delar av objekt kallas selektorer och de som returnerar sanningsvärden kallas predikat.

7. Likhet.

Utöver primitiver för en viss domän behövs en jämförelse:

eq[x;y] en funktion som tar två argument, båda atomer. Funktionen returnerar sant om dessa var lika, annars falskt.

8. Andra funktioner

Du kan vidare anta existensen av de enkla aritmetiska och logiska funktionerna.

Dessa behövs egentligen inte för att utföra beräkningar men gör många problem mycket lätthanterligare. (Egentligen kan även endp uteslutas, endp[x] är identiskt med eq[x;NIL]).

9. Lisprepresentation av funktionsanrop

Både funktioner och data representeras i Lisp som listor. Lisp evalueras (beräknas, utvärderas) så, att

  1. Den atom som står direkt efter en vänsterparentes tolkas som namnet på en funktion.
  2. Resten av elementen i listan evalueras till värden som fungerar som argument till funktionen.
Exempel
        (EQ 1 1)                    ==> T

        (ATOM 1)                    ==>  T

        (CONCAT 1 (CONCAT 2 ()))    ==>  (1 2)

        (ATOM (CONCAT 1 ())         ==> NIL

        (ATOM T)                    ==> T

        (+ 1 5)                       ==>  6
Vi låter ==> betyda "returnerar".

Således utvärderas parametrarna till en funktion innan de överförs. Detta kallas värdeöverföring, eng. Call-By-Value (CBV).

10. Quote

Då vi vill kunna representera data som listor, och inte utvärdera data som funktioner, måste vi kunna ange att data inte ska utvärderas. Detta sker med funktionen quote. Quote tar ett argument och returnerar detta "bokstavligt", dvs inte utvärderat.

Exempel

        (FIRST (QUOTE (A B)))           ==>    A.

        (QUOTE (+ 1 5))                 ==> (+ 1 5)

        (+ 1 5)                         ==> 6

        (CONCAT (QUOTE A) (QUOTE (B)))  ==> (A B)

(QUOTE X) kan förkortas till 'X

. Exempel

(CONCAT 'X '(A B))                      ==> (X A B)

(EQ 'A 'B)                              ==> NIL

(CONCAT (FIRST '(FUNKTIONELL DAT)) '(PROGRAMMERING))        
                  ==> (FUNKTIONELL PROGRAMMERING)

11. Styrstruktur

Den viktigaste styrstrukturen i lisp är cond-konstruktionen.

Cond

Den skrivs i Commonlisp-syntax 

        (COND (villkor1 värde1)
              (villkor2 värde2)
              (villkor3 värde4)
                  . . . . . . .

              (villkorn värden))

Cond- konstruktionen utvärderas enligt följande:

  1. Om villkor1 evalueras till T retuerneras värde1.

  2. Annars, om NIL returnerats av villkor1, så evalueras villkor2. Om detta blir T returneras värde2, osv.

Naturligtvis måste något av villkoren utvärderas till T och samtliga villkor måste ge värden i T,NIL

Exempel

        (COND ((EQ 1 2) 5)
              (T 6))                          ==> 6

        (COND ((ATOM (FIRST '(A B)))  'C)
              (T NIL))                        ==> C
Argumenten till COND-konstruktionen utvärderas alltså inte enligt CBV.

12. Funktionsdefinitioner

För att skapa nya funktioner (eller exaktare: binda funktionskroppar till atomer i den globala omgivningen) används i Commonlisp funktionen defun. Syntaxen för defun är

(DEFUN namn  (parametrar) funktionskropp)
När defun evalueras "skapas" en funktion.

Exempel

        (DEFUN ALLRA-FOERST (X)
               (FIRST (FIRST X)))
Ett "anrop" till allra-forst kan t ex bli

        (ALLRA-FOERST '((A B) C))   ==> A
Exempel
        (DEFUN FAC (N)
           (COND ((EQ N 0) 1)
                (T (* N (FAC (- N 1))))))

        (FAC 3)             ==> 6

13. Allens syn på listor

En liknande syn framförs av Alleni the Anatomy of Lisp. Allen beskriver en tänkt maskin (abstrakt maskin) som fungerar som en Lisp, där S-uttryck och atomer är de grundläggande datatyperna. Problem ur verkligheten uppfattar Allen som lämpade att avbilda på ADTen sekvenser. Således söker Allen en avbildning av sekvenser på S-uttryck. (S-uttryck gick ju att bearbeta på maskinen.) Denna avbildning kallar Allen listor.

Läs i gärna Allen. Allen beskriver i kap 1.2 S-uttryck, i kap 1.3 olika representationer av S-uttryck. Dessa avsnitt bör läsas noggrannt.

14. Några nyttiga funktioner

equal[x;y] predikat (dvs funktion som returnerar sanningsvärde), som tar två argument, från valfri domän (dvs av valfri typ). Funktionen returnerar T om dessa är lika, NIL annars.
numberp[a] predikat, som tar ett argument, en atom. Funktionen returnerar T om a är en numerisk atom, NIL annars.
member[e;l] funktion som tar två argument, det första av valfri typ, det andra en lista. Om e finns i l returneras listan l med början vid det funna värdet, NIL annars. Notera att member inte är det predikat som avgör om elementet e ingår i listan l. Predikatet bör heta member-p. Skriv det själv!
+,-,*,/ Aritmetik. Fungerar precis som man tror.
and, or, not Logiska konnektiv (ungefär: logiska funktioner). Fungerar precis som man tror.
append[l1;l2] funktion av två argument, båda listor. Funktionen returnerar en lista vars "början" utgörs av elementen i l1 och vars fortsättning utgörs av elementen i l2.
second[x], third[x], fourth[x] etc. Selektorer, dvs funktioner som returnerar delar av sina argument. Fungerar precis som man tror.
last[l] funktion av ett argument, en lista. Funktionen returnerar en lista, som innehåller det sista elementet i l.
list[x1;x2; ....;xn] funktion av flera argument, där argumenten kan vara antingen listor eller atomer. Funktionen returnerar en ny lista som innehåller x1...xn som element. 
  Anders Berglund			office	    + 46 (18) 471 31 67
  Information Technology		mobile	    + 46 (70) 425 02 11
  Department of Computer Systems        fax, dept   + 46 (18) 55 02 25
  P.O. Box 325				
  S-751 05 Uppsala			
  Sweden				
  e-mail: Anders.Berglund@docs.uu.se