|
De programmeertaal LISP is nu ook voor de ACORN ATOM beschikbaar. Het programma wordt op tape geleverd en is 5.5K groot (machinecode) met bijbehorend 3K data. De machinecode staat op positie #8200 tot aan #9B00, en data op #2800 - #3400. Voor de 12K ATOM past dit net (er is niet veel werkruimte meer over), met 16K uitbreiding en 1K (piggypacking) werkt alles prima. Ontstaan van LISP:Jaren geleden hield men zich al bezig met het (theoretische) probleem "berekenbaarheid". Dit probleem houdt in: is er een formele definitie te vinden waarmee men voor een willekeurig probleem kan aantonen of het m.b.v. een rekenautomaat (bijv. een ATOM) berekenbaar ofwel oplosbaar is. LISP is een gewone programmeertaal net als alle andere talen zoals BASIC, met als enig verschil dat hij op het eerste gezicht totaal onleesbaar lijkt. Het eigenlijke verschil tussen LISP en andere talen is, dat bijv. BASIC een "ITERATIEVE" taal is, d.w.z. er worden opdrachten (statements) achter elkaar uitgevoerd en LISP is een "FUNCTIONELE" taal, d.w.z. er worden functies toegepast op "argumenten".
Er kan dus pas wat worden uitgerekend binnen haakjes, als alles wat tussen nog meer haakjes staat al is uitgerekend. LISP wordt LISt Processing genoemd, omdat alles wat LISP kent: ("FUNCTIENAAM" "ARGUMENT0" "ARGUMENTn") op te vatten is als een lijst met n+2 elementen. LISP interpreteert elke lijst als volgt: Het eerste element van de lijst is de functie naam en alles wat daar achter komt zijn de argumenten van die functie. Is een willekeurig argument ook weer een lijst (haakjes!!), dan wordt deze weer hetzelfde bekeken (functie plus argumenten). Is een bepaald argument niet iets tussen haakjes, dan wordt hiervan de "waarde genomen” (in het voorbeeldje, X heeft de waarde 7). De waarde van zoiets kan bij LISP een getal zijn of weer een lijst met allemaal haakjes. Formeler gezegd: LISP kent:
Tezamen vormen deze twee de zogenaamde "symbolische expressies". Een SEXPR (afkorting) is dus of een lijst of een atoom. Een voorbeeld van een SEXPR is de bovenbeschreven functie. LISP heeft een aantal standaard functies tot zijn beschikking staan, waarmee nieuwe functies gedefinieerd kunnen worden. Dit is een van de sterke kanten van LISP. Vergelijk bijvoorbeeld de "DEF FN" van sommige BASICs en de "FUNCTION" van PASCAL. Programma's in LISP geschreven zijn over het algemeen veel korter dan programma's geschreven in andere talen. LISP programma's zijn echter meestal langer als het gaat om numerieke toepassingen waarin veel gerekend moet worden met eenvoudige datastructuren zoals ARRAYS etc.
LISP kent maar 1 datastructuur en dat is de symbolische expressie (of de LIJST). Het leuke is nu, dat een LISP programma zelf OOK die datastructuur bezit. N! (N FACULTEIT) is in ATOM BASIC als volgt te berekenen: 10 INPUT"N="N 20 R-1 30 IF N=0 GOTO 70 40 FOR H-1 TO N 50 R=R*H 60 NEXT H 70 PRINT"N!="R 80 END Toch een heel gedoe met een loop en wat testwerk. Met LISP gaat dat heel anders. De definitie van N! is: 0! = 1 N! .N*(N-1)! Dus in LISP schrijf je op: COND ((EQ N 0) 1) (T(TIMES N (FAC(DIFFERENCE N 1))) Het geheel heet "FAC”. De functie: "COND" is de "IF" van BASIC " " : "TIMES" vermenigvuldigt “ " ; "EQ" test op gelijkheid “ " : "T" is "TRUE" " " : "DIFFERENCE" is de "-" van BASIC Nog even herhalen, een LISP programma is een lijst. Een lijst is: 1: Een eventueel leeg woord of 2: Een lijst van lijsten. Als een lijst niet een enkel woord is, dan staan de elementen van die lijst tussen haakjes. Bijvoorbeeld: ( EEN TWEE DRIE) of ( VIER (( VIJF ZES ))) etc. Het eerste element van een lijst is de FUNCTIENAAM en de eventuele andere elementen zijn de argumenten van de functie die bij die naam behoren. Alle LISP INTERPRETATOREN beschikken over een redelijk groot aantal standaard functies. Met behulp van deze standaard functies kan de gebruiker zijn eigen functies samenstellen en zo een LIST programma schrijven. Dit klinkt misschien ingewikkeld of omslachtig, maar in BASIC gebeurt precies hetzelfde, alleen wordt er dan niet gepraat over functies, maar over statements. Zo wordt bijv A=123 in BASIC een "assignment" statement of "toekenning opdracht" genoemd, maar met hetzelfde recht kan je praten in LISP over een functie bijv. "GEEFWAARD” die twee argumenten heeft. Hier zijn dat "A" en "123". De waarde van de functie zelf is niet van belang. QUOTE Dit is een simpele functie met een (1) argument. de waarde van de functie IS het argument. Toets maar eens in: ( QUOTE HALLO ) het antwoord is: HALLO Dit lijkt misschien eigenaardig of nutteloos. maar bedenk, dat LISP altijd van woorden de WAARDE probeert uit te rekenen (“evalueren"). Als je in had getoetst: HALLO dan had LISP de WAARDE van HALLO geprobeerd te vinden, en dat was 'm waarschijnlijk niet zo best gelukt. Misschien verduidelijkt het volgende voorbeeld iets. Als je in BASIC intoets: A=X dan krijgt A niet de waarde “X" (de letter X), maar de WAARDE van de letter X (of variabele), en dat is bij BASIC dan altijd een getal. Wil je in BASIC iets LETTERLIJK hebben, dan zet je het tussen QUOTES: $A="HALLO" Nu heeft A de waarde HALLO. en niet de waarde van HALLO, wat dat dan ook zijn mag. Twee andere belangrijke standaard functies zijn:
( CAR ( QUOTE ( DIT IS EEN LIJST )))
heeft als waarde DIT. Let op het gebruik van QUOTE !!
Het argument van CAR is:
( QUOTE ( DIT IS EEN LIJST ))
en LISP gaat dat evalueren.
Het resultaat is: ( DIT IS EEN LIJST )
(zie de functie QUOTE) en hiervan wordt het eerste element genomen. dus: DIT.
Hadden we ingetypt:
( CAR ( DIT IS EEN LIJST))
dan had LISP het woordje 'DIT' weer als een functie met als argumenten IS,
EEN en LIJST, en dan was alles in de war gelopen waarschijnlijk.
Bij CDR gebeurt er dit:
( CDR ( QUOTE ( DIT IS EEN LIJST ))) De waarde is nu:
( IS EEN LIJST )
De functies mogen ook door elkaar gebruikt worden:
( CAR ( CDR ( QOUTE ( DIT IS EEN LIJST ))))
Dit heeft als waarde; IS.
Om veel typewerk te vermijden zijn in ATOM LISP de functies
CAR,CDR,CAAR, CDAR,CADR,CDDR opgenomen.
Deze laatste vier functies vervangen:
( CAR ( CAR …….
( CDR ( CAR …….
( CAR ( CDR …….
( CDR ( CDR …….
CAR en CDR splitsen een lijst in tweeën, de volgende functie knoopt ze weer aan elkaar:
CONS
Dit is een functie met twee argumenten.
De waarde van CONStruct is een lijst gelijk aan het tweede argument met ervoor het
eerste argument geplakt. Bijv.
( CONS ( QUOTE DIT) ( QUOTE ( IS EEN LIJST )))
heeft als waarde:
( DIT IS EEN LIJST )
In ATOMLISP mag je om nog meer typwerk te vermijden in plaats van:
( QUOTE ZOMAARIETS ) ook wel
‘ ZOMAARIETS typen, dat scheelt ook weer wat haakjes.
Stel dat LIJST een normale niet lege lijst is, en ook niet enkel een woord,
dan geldt er voor CAR, CDR en CONS dat:
( CONS ( CAR LIJST) ( CDR LIJST )) = LIJST
Let op bij CONS, dat het antwoord bij:
( CONS '( DIT IS) ‘ ( EEN LIJST))
niet
( DIT IS EEN LIJST )
maar
(( DIT IS) EEN LIJST )
is! ! Het eerste argument wordt TOEGEVOEGD als nieuw eerste element van de tweede lijst! !
Nog een voorbeeldje:
(CONS(CADR LIJST)(CONS(CAR LIJST)(CDDR LIJST)))
heeft als waarde:
( IS DIT EEN LIJST )
Het woord 'LIJST' heeft de waarde ( DIT IS EEN LIJST ).
Dit laatste voorbeeldje was al bijna niet meer te lezen door de haakjes.
Er is dan ook een nette manier gevonden om LISP programma"s leesbaar op te schrijven in de
volgende vorm:
( FUNCTIENAAM ARGUMENT 1
ARGUMENT
:
ARGUMENTn)
Dus het laatste voorbeeld had er dan zo uitgezien:
( CONS ( CADR LIJST )
( CONS ( CAR LIJST )
( CDDR LIJST )))
Dit is al heel wat leesbaarder. In ATOMLISP is een functie opgenomen, een zogenaamde "PRETTY PRINTER" of "SUPER PRINTER" die dat ook doet. Z'n naam is SPRINT. Dat vergemakkelijkt alles een beetje, en vermijdt een hoop getel van al die haakjes.
Deze keer de predicaten van LISP. Predidaten zijn functies net als alle andere functies, met als enig verschil, dat de functie maar twee waarden kan hebben: WAAR of ONWAAR. In BASIC zijn dat de "TESTABLE EXPRESSlONS"
(zie de ATOM handleiding). In LISP wordt dit voorgesteld door 'T' voor waar en 'NIL' voor onwaar.
ATOM: deze functie is T als z'n argument een atoom is, anders NIL
LISTP: deze functie is het omgekeerde van ATOM
NULL: test of z'n argument NIL is, zo ja, dan T anders NIL
NOY : is gelijk aan NULL
EQ: test of z'n beide argumenten atomen zijn en gelijk zijn.
Een paar predicaten speciaal voor getallen:
GREATERP: test of z'n eerste argument groter is als z'n tweede.
LESSP: het omgekeerde van GREATERP.
MlNUSP: test of het argument negatief is of niet.
ZEROP: test of z'n argument NUL (niet verwarren met NIL) is.
De hoofdletter P aŕn het eind van de predicatennamen staat voor "predicaat".
Een paar voorbeeldjes:
(GREATERP 32) = T
(LESSP 32) = NIL
(ATOM 'A) = T
(NOT(LISTP 'A) = T
(NULL(NULL(NULL NIL))) = T
(ZEROP 0) = T
(EQ 3 3) = T
(EQ 'A 'A) = T
(EQ 'A 'B) = NIL
Een van de werkpaarden van LISP is de functie COND ("condition" te vergelijke met IF THEN ELSE).
De structuur van de functie COND is even wennen:
(COND((TEST1)(WAARDE1))
((TEST2)(WAARDE2))
: :
((TESTn)(WAARDEn))
Dit kan vertaald worden als volgt:
IF TEST1 = WAAR THEN FUNCTIEWAARDE = WAARDE1 ELSE
IF TEST2 = WAAR THEN FUNCTIEWAARDE = WAARDE2 ELSE …… etc.
Als geen enkele test waar is, dan is de functiewaarde NIL.
Een voorbeeldje:
Stel we willen het maximum bepalen van twee getallen X en Y.
(COND((LESSP X Y)Y)
(T X))
Een andere veel gebruikte functie is DEFUN (functie definitie).
De structuur is als volgt:
( DEFUN FUNCTIENAAM ( ARGUMENT 1 ... ARGUMENTn) FUNCTE1 )
Willen we bijvoorbeeld de functie MAXIMUM definieren, dan gaat dat als volgt:
( DEFUN MAXIMUM ( X Y )
(COND((LESSP X Y)Y)
(T X))
We kunnen deze functie gewoon gebruiken zoals andere functies, bijv.:
(MAXIMUM 15).
Om een waarde aan iets toe te kennen kent LISP twee functies: SETQ en SET.
Voor de duidelijkheid even terug naar BASIC.
Als we intypen A=B, dan wordt de waarde van A gelijk aan de waarde van B.
Typen we in $A="B" dan wordt de waarde van A gelijk gesteld aan B.
De strudtuur van SET~ en SET is als volgt:
(SET(Q) ARGUMENT1 ARGUMENT2)
SET Q geeft dan de waarde van ARGUMENT2 aan ARGUMENT1en SET geeft de waarde
van ARGUMENT2 aan de WAARDE (!!) van ARGUMENT1.
Laten we er een beetje mee spelen:
(SETQ A 'B) A HEEFT DE WAARDE B
(SET A 'C) DE WAARDE VAN A(= B) HEEFT NU DE WAARDE C OFWEL B HEEFT DE WAARDE C
(SETQ A B) A HEEFT NU DE WAARDE DIE B OOK HAD OFWEL C.
De letter Q aan het eind van SETQ staat voor QUOTE. In LISP's spraakgebruik heet het,
dat SETQ zijn eerste argument automatisch QUOTE (werkwoord) en dus niet evalueert.
Laten we eens een wat groter voorbeeld bekijken, en een beetje met de verzamelingenleer gaan rommelen. Als conventie spreken we af, dat in LISP een verzameling geen lijst is en een element van een verzameling een atoom is. Dus (A B C D E) is een verzameling en A en B zijn elementen uit deze verzameling. ( ) is ook een verzameling namelijk de lege verzameling. Laten we eens een functie definieren die bepaalt of een atoom een element is van een bepaalde verzameling. (DEFUN MEMBER(X Y) (COND((NULL Y)NIL) ((EQ X(CAR Y))T) (T(MEMBER X(CDR Y))))) Je kan de functie als volgt lezen: X is een atoom en Y is en verzameling. Is Y de lege verzameling, dan kan X daar geen element van zijn. Anders als X het eerste element is van Y dan T. Anders kijken we of X een element is van de rest van de verzameling Y ('t was niet het eerste element). Als we een element toe willen voegen aan een verzameling, dan moeten we dus eerst kijken of dat element er al inzit, zo ja dan doen we niets, anders voegen we het element toe (dubbele postzegels beschouwn we niet als een element van de postzegel verzameling).(DEFUN INSET(X Y) (COND((EMBER X Y)Y) (T(CONS X Y)))) Als we een element willen verwijderen kijken we eerst of er wel iets te verwijderen valt. Zo ja dan halen we het er uit anders doen we niets. (DEFUN OUTSET(X Y) (COND((NULL Y)NIL) ((EQ X(CAR Y))(CDR Y)) (T(CONS(CAR Y)(OUTSET X(CDR Y)))))) We kunnen nu werken met EEN verzameling en EEN element. Nu met twee verzamelingen. Willen we de vereniging van twee verzamelingen weten, ofwel het hele handeltje op een hoopje en de dubbele er uit halen, dan kan dat als volgt: (DLFUN UNION(X Y) (COND((NULL X)Y) (T(UNION(CDR X)(INSET(CAR X)Y))))) De truuk is als volg1: we halen steeds een element uit X en voegen dat toe aan Y totdat X leeg is. Als we alle elementen van een verzameling Y willen hebben die niet in een verzameling X zitten dan kan dat als volgt: (DEFUN DIFF(X Y) (COND((NULL X)Y) (T(DIFF(CDR X)(OUTSET(CAR X)Y))))) En alle elementen die OF in X OF in Y zitten krijgen we als volgt te pakken: (DEFUN SYMDIFF(X Y) (UNION(DIFF X Y) (DIFF Y X))) Alle elementen die in beide verzamelingen zitten zijn als volgt op te sporen: (DEFUN INTER(X Y) (SYMDIFF(UNION X Y) (SYMDIFF X Y))) Wat is nu het practisch nut van al deze functies? We kunnen het begin maken van een DATA BASE. Ih de praktijk zal niemand een DATA BASE in LISP gaan schrijven, maar als prototype voldoet LISP uitstekend. Werkt het eenmaal in LISP dan kan het hele handeltje omgeschreven worden naar een andere snellere taal. Deze manier van software ontwikkeling bij grote projecten is in de praktijk de meest gebruikelijke. Eerst uittesten in een logische theoretische taal en werkt dat eindelijk dan omBchrijven naar een of andere rare productie- taal zoalB PL1 of RPG2 of COBOL of FORTRAN noem maar op. Laten we een beetje gaan rommelen met bovenbeschreven functies. Stel we hebben drie kleine clubs, CLUB1, CLUB2 en CLUB3.(SETQ CLUB1 '(JAN PIET KLAAS MARIE)) (SETQ CLUB2 '(KEES ANDRE MARION NELLIE)) (SETQ CLUB3 '(JOOP GERARD)) JAAP meldt zich aan als nieuw lid bij CLUB3: (SET Q CLUB3 (INSET 'JAAP CLUB3)) JOOP was vergeten dat hij al lid was: (SET Q CLUB3 (INSET 'JOOP CLUB)) JOOP wil ook lid worden van CLUB2 en KEES ook van CLUB1 en CLUB)3 : (SET Q CLUB2 (INSET 'JOOP CLUB2)) (SET Q CLUB1 (INSET 'KEES CLUB1)) (SET Q CLUB3 (INSET 'KEES CLUB3)) NELLIE heeft er geen zin meer in: (SET Q CLUB2 (OUTSET 'NELLIE CLUB2)) En ga zo maar door. Vragen alB: wie zit er in CLUB1 of CLUB3 maar niet in CLUB2. CLUB1 en CLUB2 fuseren maar de mensen die ook in CLUB) zitten hebben daar geen sin in en gaan er uit ...etc. zijn gemakkelijk te beantwoorden en administratief bij te werken m.b.v. dit kleine aantal LISP functies. Nog een paar voorbeeldjes om de RECURSIE van LISP te laten zien. Hoe plak je twee lijsten aan elkaar? (CONS LIJST1 LIJST2) werkt niet kijk maar(SET Q LIJST1 '(A B C)) (SET Q LIJST2 '(C D E)) (CONS LIJST1 LIJST2) = ((A B C)C D E) De eerste lijst wordt het eerste element van lijst twee. Zo gaat het wel: ( DEFUN PLAKAAN ( X Y) (COND((NULL X)Y) (T(CONS(CAR X) (PLAKAAN(CDR X)Y))))) Hoe draai je een lijst om: (DEFUN DRAAIOM(X) (COND((NULL X)X) (T(PLAKAAN(DRAAIOM(CDR X)) (CONS(CAR X)NIL))))) Hoe bepaal je of twee lijsten gelijk zijn: (DEFUN GELIJK(X Y) (COND((EQ X Y)T) ((ATOM X)NIL) ((ATOM Y)NIL) ((GELIJK(CAR X)(CAR Y)(GELIJK(CDR X)(CDR Y))) (T NIL)) Hoe zie je of een lijst achterstevoren gelijk is ae-n de lijst zelf: (DEFUN SPIEGEL(X) (GELIJK X(DRAAIOM X))) Hoe krijg je het laatste element van een lijst te pakken: (DEFUN LAATSTE(X) (CAR(DRAAIOM X))) Om te weten te komen welke functies ATOM LISP kent, kan je intypen: (OBLIST). Dit is een functie die als waarde een lijst geeft met als elementen de namen van alle (eventueel door de gebruiker gedefinieerde) functies. OBLIST is een afkorting van DEFINED OBJECTS LIST. In het rekenwerk is LISP niet zo sterk, de volgende functies zijn standaard gedefinieerd:(PLUS X Y) = X+Y (DIFFERENCE X Y) = X-Y (TIMES X Y) = X*X (QUOTIENT X Y) = X/X (REMAINDER X Y) = X%Y In de eerste LISP interpretatoren waren alleen PLUS en DIFFERENCE gedefinieerd de rest werd met behulp van deze twee gedefinieerd: (DEFUN TIMES(X Y) (COND((ZEROP X)Y) (T(PLUS X(TIMES(DIFFERENCE X 1)Y))))) (DEFUN QUOTIENT(X Y) (COND((LESSP X Y)0) (T(PLUS 1(QUOTIENT(DIFFERENCE X Y)Y))))) (DEFUN REMAINDER(X Y) (DIFFERENCE X(TIMES Y(QUOTIENT X Y))) Ik hoop dat deze chaotische en/of moeilijke LISP aflevering een beetje duidelijk heeft kunnen maken wat LISP is en wat de programmeer discipline is die LISP met zich mee brengt. Vele mensen vinden LISP of afschuwelijk of zijn net als ik een LISP freak. Succes ermee, Jos Horsmeyer. |
