Hvad er det lige, der er så godt ved Lisp?

Dette svar falder velsagtens i kategorien ""Det forstår man ikke, før man har prøvet det", men hør mig til ende ;-)

Fordi LISP er et "programmerbart programmeringssprog" (kode er data, som kan manipuleres af kode), så kan man skrive programmer, som kan optimeres på virkeligt sjove (og værdifulde) måder.

Et klassisk eksempel er implementationen af en algoritme, der kan tegne en 3D-scene med et vilkårligt antal belysningkilder (en såkaldt raytracer). Den kan skrives i LISP på en sådan måde, at man kan skrive et andet LISP program, som indlæser det første program og spytter et nyt program ud, som er optimeret til eksempelvis to belysningskilder. Dette nye program vil altså være en specialiseret udgave af det generelle program, optimeret til et bestemt vinkling af input. Det sjove (og værdifulde) er da også, at det nye program vil være meget hurtigere.

Man kan altså skrive en generel implementation af en algoritme, og derefter spytte alle mulige varianter ud, som er specialiseret (og optimret) til særlige formål.

The bottom line: Det er lettere at skrive partielle evaluatorer i LISP end i noget andet sprog, og det kan -- for visse typer problemer -- øge en udviklers produktivitet med en faktor helt-vildt-meget.

Og, nej, selvom de færreste af os (inklusive undertegnede) nogensinde bliver stillet opgaver, hvor brugen af en partiel evaluator er lige til højrebenet, så bruger de fleste af os resultatet af partielle evaluatorer hver eneste dag: De fleste compilere har nemlig, på et eller andet tidspunkt i deres udviklingsforløb, været en tur igennem en partiel evaluator ... som oftest skrevet i en variant af LISP. Det viser sig nemlig, at en compiler er en partiel evaluering af en fortolker, og at det er meget nemmere at skrive en fortolker end en compiler.

Lisp er ikke med moderne øjne et særligt fantastisk sprog. Men det er nok populært, fordi man på en god måde kan lave funktionsprogrammering - en alternativ måde at tænke programmer i forhold til tilstandsmaskine modellen, som er det almindelige grundlag for de mere klassiske imperative sprog, hvor man hele tiden ændrer i det underliggende lager.
Eksempler på moderne funktionsprogrammeringssprog er f.eks. ML og Haskell.
Lisp er egentlig ikke tænkt som et funktionsprogrammeringssprog. I 1977 skrev John Backus en ret revolutionerende Turing award tale, (http://worrydream.com/refs/Backus-CanProgrammingBeLiberated.pdf) som overbeviste mange om det gode og nyttige ved at forsøge at skrive programmer på den måde. Lisp var det ad de daværende "hovedsprog" hvor man lettest kunne skrive software på den måde.
Og siden er det vel bare blevet hængende.

Lisp (og andre funktions programmeringssprog) er specielt velegnede til problemer, der kan formuleres og løses med del-og-hersk strategier/induktionsbeviser.
Det er også meget nemt at lave højere ordens logik, continuation passing style, lazy evaluation, currying og andre avancerede konstruktioner i de funktionsorienterede sprog, hvis man har den slags tricks i sin værktøjskasse.
Lisp specifikt er også meget velegnet til at skrive Domæne Specifikke Sprog (DSLer), fordi man på en nem måde kan udvide sproget. Lidt som preprocessoren i C, men meget kønnere og stærkere.

Har du eksempler på hvor partiel evaluering har været nyttigt i praksis? Jeg kender til en håndfuld gamle eksempler (http://www.diku.dk/OLD/forskning/topps/activities/PartialEvaluation.html), og har også selv brugt til partiel evaluator til en forenklet udgave af Scheme, men det har aldrig virket som specielt robuste løsninger.

Jeg brugte selv en del år på at kode Lisp engang. Selvom jeg nutildags mest bruger Haskell (og mener at mange af de fordele Lisp har er replikeret i funktionssprogene sidenhen), så synes jeg dette blogindlæg meget hurtigt afviser potentielle fordele uden hverken personlig erfaring, eller specielt meget kildemateriale. En trold på et blogindlægt er en interessant kilde.

En af de største bestående fordele ved Lisp er makrosystemet. En håndfuld eksempler fra min egen tid er bl.a. denne parser - en typisk LR-parser (der parser Common Lisp). En LR-parser er typisk et mareridt at skrive i hånden grundet de mange tilstande, hvorfor man normalt bruger parsergeneratorer som YACC (eller ANTLR i Java-land). Disse generatorer er dog afkoblet det sprog resten af ens program er skrevet i, hvilket giver besværlig fejlsøgning og en generelt dårlig brugsoplevelse. I Java-land kan man løse problemet ved at sætte en horde af programmører til at skrive værktøjer i diverse IDE'er der forsøger at skjule den grundlæggende inelegance, og det kan fungerer godt nok. I Lisp valgte vi at definere en håndfuld makroer til at håndtere de forskellige tilstande og handlinger i parseren - reelt et meget enkelt DSL til skrivning af LR-parsere. Det er meget lettere at lære vores DSL og derefter forstå parseren, end det ville være at forstå en LR-parser skrevet direkte uden brug af makroer.

Vi benyttede lignende tricks til at definere indenteringsregler og tab-completion-regler. Makroer er i sagens natur blot syntaktisk sukker, men når de bruges smagfuldt, kan de gøre koden langt mere læsbar.

Desuden vil jeg gerne tage afstand fra at Lisp skulle være specielt koncist eller kryptisk i forhold til andre sprog. Min erfaring er at Lisp typisk fylder godt på det lokale plan (og dertil har traditionen siden midt-80'erne været lange navne), men at Lisp giver en mulighed for at definere abstraktioner der giver en pladsbesparelse for større programmer. Det er ikke noget der giver afkast hvis man bare skriver et par hundrede linjer kode, men i større programmer giver det ofte mening at definere enkle DSLer og syntaktiske abstraktionslag.

Hvis jeg skal være meget kritisk ved blogindlægget (og det skal jeg), så indikerer følgende citat at forfatteren ikke kan have brugt meget mere end en toiletpause på at sætte sig ind i Lisp:

Kort sagt virker det som om, at Lisp gav bedre mening for 30-50 år siden, hvor det havde unikke features som garbage collection, og hvor mere resourcebegrænsede maskiner gjorde, at et simpelt, kompakt og fleksibelt sprog havde store fordele.

Lisp var oprindeligt kendt for at være stort og langsomt, endda i et sådan omfang at man designede hardware specialiseret til at håndtere dets sære krav som automatisk spildopsamling og dynamisk typesikring. C, Pascal, APL, Forth og deslige var de enkle sprog til resourcebegrænsede maskiner (ofte delte), hvor Lisp-programmer gerne lagde beslag på en hel maskine.

Nutildags er Lisp ikke specielt stort i forhold til andre sprog, og implementeringerne er typisk af ret høj kvalitet, så ydelsen plejer at være i den høje ende af de dynamiske typede sprog.

Tilbage i universitetstiden kodede jeg en del i Scheme og tror derfor jeg har en over middel forståelse af Lisp og famillien af sprog. Men jeg har aldrig forstået den moderne facination der giver sig udtryk i Clojures popularitet.

Jeg mener at kendskab til fuktionsprogrammering gør en til en bedre programmør og alle de større sprog har eller er igang med at få mere eller mindre påklistret understøttelse for funktionsprogrammering. Men hvis jeg idag skulle anbefale et mere rent eksempel på et sprog der understøtter FP ville jeg pege på noget ala Haskell.

Skal man lege med programmer der arbejder med programmer har Lisp nogle fordele, som jeg ikke er sikker på der er nogle alternative sprog der har. Men skal man mere end at lege så ville jeg nok vælge et sprog som er lidt mere levende (måske Clojure?)

Common Lisp Object System (CLOS) er et interessant bekendtskab da det adskiller sig væsentligt fra objekt-orienteret programmering ala C++ – jeg kender det dog kun på anden hånd. De to interessante features er nok en Metaobjekt Protocol (MOP) som giver mulighed for introspektion og en dynamisk objekt-struktur og en fleksibilitet der er forløberen til Aspekt-orienteret programmering, der har hypet lidt her og der.

Så det fede ved Lisp-familien er ikke som brugbart sprog, men fordi der er nogle tendenser der med tiden er ved at blive introduceret i andre sprog.

Problemet med at komme med konkrete eksempler er nok, at de fleste er "problem-problemer", der stammer fra den akademiske verden.

Constant folding (og en lang række lignende teknikker) er et klassisk eksempel på noget, der ville være hysterisk bøvlet at lave i et "normalt" programmeringssprog, men som nærmest er trivielt i LISP. Det er da netop også derfor, at folk, som roder med programmeringssprog, ofte bruger LISP. Vi andre får først glæde af det, når resultatet af den slags eksperimenter når frem til vores oversættere og fortolkere.

Alt i alt vil jeg dog anbefale, at man lærer sig lidt LISP af cirka de samme grunde som når Poul-Henning Kamp anbefaler, at man lærer sig maskinkode: Man bliver simpelhen en bedre udvikler, fordi man forstår mere af, hvad der foregår :-D

Det var et repræsentativt eksempel på, at Lisp-fortalere har det med at udtrykke sig på en arrogant måde.

Selvom der selvfølgelig er ubehøvlede Lisp-fortalere, så tror jeg ikke længere det er værre end med så mange andre programmeringssprog, religioner, eller økonomiske doktriner. Det var mest en trend der eksisterede omkring årtusindeskiftet or årene derefter, og jeg tror det skyldes at Paul Graham skrev en række essays om at Lisp-programmører var klogere end andre programmører (lidt forenklet).

Det er du så ikke enig med alle Lisp-fortalere i. Fra Peter Norvig himself:

Det er ikke det Peter Norvig siger. For det første kan jeg ikke se hvor i det oprindelige materiale det nævnes at det er et Java-program der er på 614 linjer - derimod nænves det "The C, C++, and Java programs ranged from 107 to 614 lines, with a median of 244 and a mean of 277". Mit gæt er faktisk at det er et C-program der er så stort, og at det skyldes manuel resursehåndtering. Hvis det er et Java-program, så tror jeg mere det skyldes et overkompliceret J2EE-style design, og det siger nok mere om Java-programmøren end om Java.

Det er klart at Lisp klarer sig okay når det sammenligned med så relativt klodsede sprog som C, C++ og Java, især de udgaver der var tilgængelige omkring år 2000. Hvis man skrev programmet i Python, så tror jeg ikke det ville være større end Lisp-udgaven. Hvis man skrev det i Perl eller Ruby ville det fylde mindre. Lisp har i denne sammenligning primært en fordel ved ikke at kræve manuel resursestyring (ift. C og C++), og ikke at kræve typeangivelser eller brug af klassehiearkier (ift. Java). Muligvis havde Common Lisp også en standardbibliotek-fordel i år 2000.

Jeg mener, tjek kroppen fra en af Norvig's funktioner:

(let ((n 1))  
  (loop for i from 0 below (length word)   
        for ch = (char word i) do  
        (when (alpha-char-p ch) (setf n (+ (* 10 n) (char->digit ch)))))  
  n)

I Python er det noget i stil med:

n = 1  
for ch in word:  
  if ch.isalpha:  
    n = n * 10 + ch.ord() - '0'.ord()  
return n

Samme antal linjer i dette tilfælde, men det ser stadigvæk mere koncist ud, især fordi Lisp har tradition for disse meget lange og eksplicitte ord. Det kan man selvfølgelig mene er en god ting (det gør jeg), men det ændrer ikke på at det ikke er helt rigtigt at kalde Lisp for et synderligt koncist sprog. F.eks. ville dette være den idiomatiske Haskell-løsning:

foldl (\n ch -> n * 10 + ord ch - ord '0') 1 (filter isAlpha word)

Du, Troels... er det Lisp-arrogancen, der skinner igennem?

Snarere Haskell-arrogancen, for det er mange år siden jeg har følt behov for at forsvare Lisp's dyd på Internettet! Nutildags er Emacs Lisp den eneste Lisp jeg lejlighedsvist koder i, og det er ikke just noget der giver grobund for den store kærlighed.

Min pointe er, at der i dag er sprog, som tilbyder mange af de features, som dengang var unikke for Lisp (garbage collection, fx), og som derudover har ting, som ville have været prohibitivt dyre at lave i 1960'erne rent compilermæssigt.

Med andre ord muliggjorde Lisp, at man kunne få adgang til sprogkonstruktioner, som det ville have været omfangsrigt at lave i en compiler til andre sprog. Lisps syntaks er ekstremt simpel, og derfor minimalt resourcekrævende at håndtere. While-eksemplet i blogindlægget er et fint eksempel - man kan selv udvide sproget med nye konstruktioner uden at gøre compileren mere kompleks.

Det er sandt, og de var også hvad alle mine eksempler handlede om. Lisp har en homogen syntaks som er nem at udvide uden at udvidelserne føles malplaceret. Omvendt er der forskellige udvidelser til C (f.eks. OpenMP) der for det første kræver et indgreb i en C-oversætter, og derudover er syntaktisk klodsede. I OpenMP's tilfælde skal man kode via #pragma'er. Se også den moderne stil med brug af @annotationer, som vistnok er udbredt i Java og Python.

Constant folding (og en lang række lignende teknikker) er et klassisk eksempel på noget, der ville være hysterisk bøvlet at lave i et "normalt" programmeringssprog, men som nærmest er trivielt i LISP.

Hvad mener du? Så vidt jeg kan se udførte selv den første oversætter (FORTRAN I) constant-folding (side 9 i PDFen, højre søjle). Det er også noget der bliver gjort af stort set enhver oversætter nutildags, og det er ganske enkelt at implementere i de fleste sprog. Teknisk set er constant folding måske at opfatte som partiel evaluering, men det er noget enklere end de teknikker jeg normalt ville kalde for partiel evaluering.

det ændrer ikke på at det ikke er helt rigtigt at kalde Lisp for et synderligt koncist sprog. F.eks. ville dette være den idiomatiske Haskell-løsning

Det er vel mere retteligt den idiomatiske funktionelle løsning. Modulo syntax ville jeg skrive det samme i Scheme, SML og, hvis jeg var i et funktionelt humør, Perl.

Jeg har programemret meget i LISP og Scheme, men gør det ikke længere, for mere moderne programmeringssprog såsom ML og Haskell er bedre end LISP til de ting, som LISP blev designet til (behandling af ikke-numerisk data).

LISPs syntaks har tre fordele:

1. Et program er sin egen datarepræsentation, så det er nemt at manipulere programmer. Partiel evaluering er nævnt, men også refactoring tools kan nemt skrives.

2. Den er let at lære udenad: Man behøver ikke at huske særegen syntaks for hver enkelt sætningsstruktur.

3. Man skal ikke huske operatorpræcedens osv: Man kan altid se, hvor en sprogkonstruktion begynder og ender.

Men umiddelbar synes jeg, at det er relativt svage fordele:

Punkt 1 løses bedre ved at have en standardiseret (og overskuelig) datastruktur for abstrakt syntaks (og en parser, man kan kalde til at indlæse kode i dette format, og en pretty-printer, der kan konvertere den interne repræsentation til tekst), så man let kan skrive programmanipulerende kode (som f.eks. en IDE). Desværre har ingen nuværende mainstreamsprog en sådant standardiseret abstrakt syntaks, hvis man ser bort fra HTML og XML-baserede sprog, hvor kode ligesom i LISP er skrevet direkte som en datastruktur.

Punkt 2 kan sagtens klares uden de mange parenteser: Man skal blot lave en konsistent og ikke for stor grammatik for sproget. Punkt 3 ligeledes. Specielt skal antallet af præcedensregler minimeres.

LISP var det første programmeringssprog med dynamiske typer. Nogle vil sige, at det kun har en type, men her er jeg ikke enig: Hvis du f.eks. forsøger at bruge et tal som en funktion eller omvendt, får du en køretidsfejl og ikke bare udefineret opførsel. Der laves altså typecheck, men på køretid.

Nogle fremhæver netop de dynamiske typer som en fordel ved LISP: Man kan ikke alene manipulere programmer nemt, man kan også lave generisk kode, der manipulerer alle former for data. Endvidere behøver man ikke at erklære typerne af variable og funktioner. Noget lignende fremhæves i dag for scriptingsprog med dynamiske typer, men her har man ofte brug for reflection for at opnå samme grad af uniform databehandling som LISP.

Men også her er jeg uenig. Når typecheck først udføres på køretid, skal der overordentlig meget afprøvning til, før man kan være sikker på, at programmet ikke har typefejl. Og mange af de fordele, som dynamiske typer giver, fås med global typeinferens (så man undgår at skulle erkære typer), polymorfi og typeklasser (som kan bruges til generisk programmering).

Hvad mener du? Så vidt jeg kan se udførte selv den første oversætter (FORTRAN I) constant-folding (side 9 i PDFen, højre søjle). Det er også noget der bliver gjort af stort set enhver oversætter nutildags,

Du har fuldstændig ret! Af en eller anden bizar grund blev "constant folding" til "currying" oppe i mit hoved, og det var det, jeg havde i tankerne, da jeg skrev løs.

I øvrigt kan min anbefaling for at "lære sig lidt LISP" udvides til " eller lidt Haskell", da sidstnævnte nok er betydeligt mere praktisk anvendeligt :-)

At være koncis sammenlignet med C, C++ og Java anno 2000 er altså ikke det samme som at være koncis i almindelighed. Det er ikke en rimelig sammenligning (og jeg tror ikke Peter Norvig har ret når han antager at det største program er i Java). Bare fordi Peter Norvig har skrevet det, så er det jo ikke sikkert at det passer.

Med undtagelse af makroer (som vitterligt er noget særligt), så kan de fleste af Lisp's koncisions-bringende funktionaliteter findes i stort set alle moderne højniveausprog. Meget af Lisp's gamle ry stammer fra at det var det første sprog det havde mange af disse funktionaliteter (som du i øvrigt selv siger, og hvilket også lader til at være oplevelsen for de fleste af de Lisp-programmører der har bidraget til debatten).

Jeg tror dog det du i virkeligheden interesserer dig mest for, er om du skal prøve Clojure. Det ved jeg ikke meget om - det kom til efter jeg selv holdt op med at kode i Lisp. Det er givetvis meget smart hvis man gerne vil have adgang til Java-biblioteker.

Hvis vi spørger helt specifikt om Clojure som moderne og levende sprog, så tror jeg at fordelene kan opsummeres således:

• Simpel syntax – måske for primitiv til nogen smag. At programmer har en naturlig repræsentation som værdier i sproget tror jeg derimod ikke er relevant.

• Dynamisk typning – Ikke deklarations-helvedet fra C og folk forstår ikke forskellen mellem dynamisk typning og type inferens ala SML og Haskell.

• Naturligt funktionprogrammering – ikke påklistret som i sprog der først har fået det meget sent og uden at man skal høre på Haskell-folkets obskure monade-snak.

• Adgang til Java-miljøet – hvis det er sjovere end adgang til C libraries gennem libffi

Jeg må tilstå at syntaksen er for primitiv til min smag. Derfor har jeg forlængst sagt farvel til Lisp-lignende sprog.

Hvordan et typesystem bør virke kan vi sikkert diskutere i lang tid. Skal jeg vælge mellem dynamisk typning ala Lisp eller statisk typning ala C, så føler jeg mig mest produktiv med dynamiske typer, men jeg ville helt klart foretrække et typesystem ala SML med generiske typer deducerede af oversætteren.

Er F# stadigvæk en ting man bruger? Det er så godt nok ikke Java, men .net.

Og som Troels også antyder. Meget af det gode ry som Lisp-familien har, skyldes at at der en gruppe rigtig smarte folk der har har Lisp som deres primære sprog – herunder store dele af det amerikanske AI-community op igennem 80'erne.