BESLUIT

In deze cursus zijn bijna alle primitieve dataypes, procedures en controlestructuren van Scheme aan bod gekomen. Enkele in dit document niet gebruikte numerieke primitieven werden overgeslagen. Zie de definitie van SCHEME We besluiten met enkele bedenkingen over de historie en verdiensten van LISP.

Geschiedenis van LISP

LISP (LISt Processing) is samen met Fortran één van de oudste hogere programmeertalen. De taal werd eind jaren vijftig door John McCarthy (een van de founding fathers van de AI) ontworpen als een taal voor het beschrijven en oplossen van symbolische wiskundige problemen zoals symbolische differentiatie en integratie van algebraïsche expressies en recursieve vergelijkingen (in plaats van de numerieke wiskundige problemen waar Fortran uitstekend geschikt voor was).

Bijvoorbeeld, de recursieve wiskundige definitie voor de functie faculteit,

0! = 1
n! = n(n-1)!

staat heel dicht bij de manier waarop de functie in LISP geïmplementeerd wordt:

> (define (! n)   
    (if (< n 2)        
        1                 
        (* n (! (- n 1)))))

> (! 4)                 
24

Tot het midden van de jaren tachtig ontstond een proliferatie van LISP varianten en dialecten. In Figuur 1 staat een gedeeltelijke stamboom van LISP. Common Lisp (Steele, 1990) is een poging om een standaard te ontwikkelen die de beste en meest gebruikte elementen van veel van de verschillende bestaande dialecten verenigde. Deze standaard zorgde tegelijk voor het in onbruik raken van illustere voorgangers als Franz Lisp, Interlisp en ZetaLisp. Sommige dialecten slagen er in voort te leven naast Common Lisp omwille van interessante eigenschappen. SCHEME, bijvoorbeeld, is een kleinere, meer `pure' vorm van LISP. Common LISP biedt een grote keuze aan primitieve en complexe datastructuren (arrays, hash-tables, strings, bitstrings, structures, objects, ...) en controlestructuren (verschillende iteratie constructies, conditionele constructies, input- en output-primitieven, ...). Dat is ideaal voor de ontwikkeling van complexe software systemen. Voor onderwijsdoeleinden, daarentegen, is de eenvoudige definitie van SCHEME beter geschikt.

Stamboom Lisp dialecten

Een functionele declaratieve taal

LISP is een declaratieve taal (zoals PROLOG), in tegenstelling tot de meeste hogere programmeertalen (Pascal, Basic, Fortran, Algol, C) die imperatief zijn (een opeenvolging van imperatieve commando's, subroutine aanroepingen en toekenningen van waarden aan variabelen). PROLOG is een relationele declaratieve taal (gebaseerd op de declaratieve beschrijving van relaties tussen entiteiten), en LISP is een applicatieve of functionele declaratieve taal, gebaseerd op functietoepassing. Het onderscheid is natuurlijk niet zo duidelijk als we zouden willen. Het is best mogelijk om functioneel te programmeren in Pascal, of imperatief in LISP. Het gaat hier om de programmeerstijl die het meest natuurlijk is voor de verschillende talen.

LISP en AI

LISP werd snel de meest gebruikte programmeertaal van onderzoekers en ontwikkelaars op het gebied van Kunstmatige Intelligentie (Artificial Intelligence, AI). Dat is ze trouwens nog steeds in de VS en grote delen van Europa. Sinds de jaren tachtig werd PROLOG een sterk alternatief, vooral in Japan en Europa. Niet alleen zijn er een aantal praktische en programmeertechnische voordelen bij het gebruik van LISP voor AI die we elders beschrijven, LISP belichaamt ook de belangrijkste theoretische hoeksteen van de hedendaagse AI en Cognitiewetenschap: intelligent gedrag is het resultaat van symboolmanipulatie. Deze stelling is bekend onder de namen Physical Symbol System Hypothesis (PSSH) of Representational Theory of Mind.

Vereenvoudigd komt de PSSH (Newell, 1980) hierop neer:

1. Primitieve mentale concepten worden gerepresenteerd in een intelligent systeem door fysieke symbolen.
2. Complexe mentale concepten worden gerepresenteerd als structuren van fysieke symbolen.
3. Intelligentie (een verzameling intelligente functies) is het resultaat van de manipulatie van structuren van fysieke symbolen. Die manipulatie gebeurt door programma's.
4. Programma's kunnen gerepresenteerd worden als fysieke symbool structuren. Op die manier kan een intelligent systeem leren (door de manipulatie van symboolstructuren die programma's representeren).

De primitieve datastructuren van LISP (symbolen en lijsten) laten een gemakkelijke implementatie van symboolstructuren en van de compositionele aard van complexe concepten toe, terwijl (samengestelde) functietoepassing een natuurlijke manier is om symboolstructuurmanipulatie uit te drukken. Bovendien worden programma's en data op dezelfde manier gerepresenteerd in LISP (als lijsten: vergelijk de data '(1 2 3) met het `programma' (+ 2 3)) wat de weg opent naar modificatie of constructie van programma's door programma's.

De LISP programmeeromgeving

Naast het parallellisme tussen het ontwerp van LISP en de theoretische basis van AI en cognitiewetenschap, zijn er een aantal eigenschappen van LISP die het tot een bijzondere en belangrijke taal voor AI onderzoek maken, zelfs voor onderzoekers die andere hogere programmeertalen kennen.

• LISP is de moedertaal van de AI. Het leeuwendeel van bestaande AI programma's is geschreven in LISP, en ondanks een geleidelijke groei van het aandeel van Prolog zal dat nog lang zo blijven. Iemand die AI onderzoek wil gaan doen zal dus onvermijdelijk in contact komen met LISP programma's, en zal de taal ten minste passief moeten beheersen. Deze vaststelling roept natuurlijk de vraag op waarom LISP dan wel zo populair is in AI kringen.
• LISP is interactief. Programma's kunnen incrementeel en interactief ontwikkeld worden. De gebruiker krijgt onmiddellijke feedback van het systeem. De LISP programmeur definieert relatief kleine onderdelen van een programma als afzonderlijke functies in de editor, test deze uit (vaak zonder de editor te verlaten), en combineert ze in andere functies. Vergelijk dit met de traditionele edit-compile-load-execute cyclus:
  1. Schrijf de source code van een volledig programma in een editor.
  2. Compileer de source code, stel de compile-time fouten vast. Herhaal 1 en 2 tot alle compile-time fouten opgelost zijn.
  3. Laad de gecompileerde versie van het programma en voer ze uit. Stel de run-time fouten vast, en herhaal 1, 2 en 3 tot al deze fouten opgelost zijn.

  In het ideale geval, waarbij weinig of geen compile-time en run-time fouten worden gemaakt, is een interactieve programmeeromgeving waarschijnlijk niet uitzonderlijk voordelig. De praktijk wijst uit dat er weinig programmeurs zijn die een programma van de eerste keer correct kunnen neerschrijven. Het soort problemen waarmee we ons bezig houden in de AI leent zich trouwens meestal niet tot een aanpak waarbij het volledige programma op papier gespecificeerd en ontworpen wordt vooraleer men begint te implementeren. Een prototyping aanpak waarbij specificatie, ontwerp, implementatie en testen tegelijk en incrementeel gebeuren is meestal meer aangewezen. De interactieve mogelijkheden van LISP zijn hierbij bijzonder nuttig.

• LISP is ingebed in krachtige programmeeromgevingen. Samen met een LISP systeem krijgt de programmeur meestal toegang tot een unieke verzameling gereedschap voor de ontwikkeling van programma's die de produktiviteit verhoogt en de ontwikkeling van complexe en grote programma's vergemakkelijkt: tracers, steppers, en inspectors laten toe datastructuren en het verloop van de controle in programma's te bestuderen; debuggers vergemakkelijken het opsporen en interactief oplossen van fouten; LISP editors laten toe LISP code in de editor te evalueren en te inspecteren en helpen bij het formatteren (indentatie, tonen welke haakjes bij elkaar horen, enz.) en documenteren van de code; profilers verzamelen gegevens over de performantie van programma's. Verder zijn er meestal on-line help- en documentatiesystemen, krachtige zoekfuncties, hulpmiddelen voor het snel ontwikkelen van een grafische interface naar een ontwikkeld programma, mogelijkheden stand-alone toepassingen te ontwikkelen die alleen de noodzakelijke code en data gebruiken, en mogelijkheden om vanuit LISP data of functies geschreven in talen als Fortran, C en Pascal te gebruiken (foreign function interface). Vaak zijn deze tools in LISP geschreven zodat ze uitbreidbaar en aanpasbaar zijn door de gebruiker. Er is automatisch geheugenbeheer (garbage collection), en tegelijk uitgebreide mogelijkheden om de efficiëntie te verhogen door middel van compiler declaraties.
• LISP is expressief, flexibel en elegant. LISP is uitbreidbaar. Het is relatief gemakkelijk om met behulp van macro's de syntaxis van LISP te veranderen, controle- en datastructuren toe te voegen, of om in LISP interpreters te schrijven voor allerlei talen en formalismen (wat in de AI vaak nodig is). AI systemen zijn complexe systemen waarin diverse modules interageren. Elke module spreekt z'n eigen taal, er bestaat geen formalisme waarmee alle problemen en hun oplossing op een natuurlijke manier kunnen worden gerepresenteerd. Daarom is het belangrijk een gemakkelijk uitbreidbare programmeertaal te hebben.

  Door de wiskundige basis van LISP (functietoepassing, recursie, lambda calculus) is LISP een elegante taal: de ontwikkelde code is modulair, en functies zijn first class datastructuren waarmee alles kan gebeuren wat met andere datastructuren kan. Data en programma hebben dezelfde vorm. De wiskundige fundering maakt het ook mogelijk (maar niet verplicht) een puur functionele programmeerstijl te hanteren, wat voordelig is bij het bewijzen van correctheid van programma's.

Lisp is niet alleen de moedertaal van de AI, het is ook een goede keuze voor om het even welk type van complexe, slecht-gedefinieerde problemen, en voor elk programmeerproject waar produktiviteit een rol speelt. De meeste moderne LISP compilers zijn ook efficiënt genoeg, zelfs voor specifieke number crunching toepassingen.

Toch mogen we niet blind zijn voor het feit dat ondanks het bestaan van standaarden voor SCHEME en Common Lisp, en de al eerder genoemde voordelen, LISP nooit doorgebroken is als implementatiemedium voor de productie van industriële software systemen. Lisp omgevingen worden bijna uitsluitend gebruikt bij prototyping van complexe software systemen. Om aantrekkelijk te zijn voor de software engineering markt moet nog verder gewerkt worden aan de programmeeromgeving (vooral m.b.t. de gewoontes en wensen van software engineers), aan verdere standaardisering, en aan de opleiding van Lisp programmeurs. De veelgeprezen flexibiliteit van LISP maakt het helaas ook mogelijk om slechte en inefficiënte code te schrijven. Voor een recent overzicht van de standaardiseringspogingen van Lisp en een originele visie op de mogelijkheden van en mythes en misverstanden rond Lisp, zie Richard P. Gabriel (1991).

Prolog versus LISP

Prolog en LISP zijn beide declaratief, en worden beide gebruikt in AI toepassingen. Het debat over de respectievelijke voor- en nadelen van PROLOG en LISP bij de ontwikkeling van AI-systemen heeft vaak iets van een religieuze oorlog. Het is aan te raden een agnostisch standpunt in te nemen.

Prolog heeft een impliciet redeneermechanisme (unificatie en depth first backward chaining van regels), en is daarom ideaal voor een klasse van problemen die veel voorkomt in de AI (o.m. in parsing, planning en expertsystemen).

LISP is neutraal m.b.t. het redeneermechanisme, en is daarom meer algemeen toepasbaar. Voor de PROLOG klasse van problemen zou in LISP een expliciete unificatie en backward chaining controlestructuur geschreven worden. LISP kan dus omschreven worden als een wat minder `hoge' programmeertaal dan PROLOG, maar tegelijk wat meer flexibel dan Prolog. (Prolog staat op het niveau van een extensie van LISP).