Lisp hackers have all defun

Innan jag börjar babbla, vilket jag för en gångs skull kommer göra till en alldeles synnerlig grad i det här inlägget, så kommer här litet kuriosa.

XKCD1

"Lisp has jokingly been called 'the most intelligent way to misuse a computer'. I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts."

Edsger Dijkstra

"SQL, Lisp, and Haskell are the only programming languages that I've seen where one spends more time thinking than typing."

Philip Greenspun

Så. Medan jag de senaste veckorna lagt alldeles för mycket tid på att lära mig alldeles för litet av C++ och Qt, särskilt i proportion till mängden kod som samtidigt blivit till, så har jag förstås funderat över hur jag ska göra med projektet (H.VHS) i framtiden. Två idéer har därmed klarnat.

  1. Att separera fram- och bakändorna är värt besväret, inte minst därför att jag förr eller senare kommer vilja ha samma funktionalitet, fast i terminalformat.
  2. Metoderna för att trolla fram information om strömmar, både sådan avsedd för människor och sådan avsedd för nedladdare, bör kunna skrivas på ett så aktivt och "dynamiskt" sätt som möjligt.

I Qt är den till synes enklaste lösningen på det andra problemet att exponera QObject för QScript kod, vilket lämpligen görs på ett sådant sätt att metoderna tycks vara skrivna i ett någorlunda lättfattligt, specialiserat skriptspråk, "dynamiskt" i den bemärkelsen att man kan ändra i metoderna utan att behöva kompilera om själva programmet, och att metoderna kan uppdateras genom att man helt enkelt ersätter metod-filer med nya versioner som hämtas från något repository.

I praktiken innebär detta att H.VHS blir inte mycket mera än en glorifierad skripttolk. Vid den punkten stöter tanken alltså samman med följande lilla regel, som tillskrivs samme Philip Greenspun som yttrat det sista bland citaten ovan.

"Greenspun's Tenth Rule of Programming: any sufficiently complicated C or Fortran program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp."

Förvisso skulle jag bli omätligt imponerad av mig själv om jag lyckades implementera hälften av Common Lisp, hur illa det än fungerade, men ännu hellre slipper jag att ens komma i närheten. Beroende på hur man ser på saken så är Common Lisp ett mycket litet eller ett mycket stort programspråk – det beror på om alla funktionsbibliotek ska räknas till språket eller inte. (Parallellt kan man fråga sig om till exempel strftime() är en del av C eller inte.)

Man kan dessutom nöja sig med mycket mindre än halva Common Lisp. För flera år sedan gick jag ett par duster med språket (en av flera utmärkta böcker finns online här), men lyckades båda gångerna glömma allting eftersom andra intressen tog överhanden. Tredje gången jag försökte så gick jag en annan väg, och provade Scheme i stället. Scheme är en Lisp-dialekt, sådana finns det flera, och dessutom en relativt liten och konsekvent sådan. Nu är det mitt favoritspråk.

Scheme passar också perfekt för det jag kommit fram till att bakändan av H.VHS ska göra. Det är visserligen ett tolkat skriptspråk, men kan i regel kompileras till maskinkod. Samtidigt behåller i regel kompilerade Scheme-program möjligheten att tolka skriptfiler. Till på köpet är kärnan i vad som gör Lisp till Lisp att det är ett idealiskt språk att göra nya språk i. Det passar helt enkelt perfekt.

En annan fördel, kanske den största, är att om man använder något Lisp-språk, så sällar man sig till den kanske enda gruppen kodare som är självgoda nog att se ned på både Python och Perl.

Den stora nackdelen är förstås att det är så få som pratar Scheme, eller Lisp över huvud taget. Och jag kan väl erkänna att när jag inte lekt med språket på något år, så lyckas inte heller jag se skogen för alla parenteser.

XKCD2

Vad är det här med parenteserna då? Tja, "vanliga" programspråk, alltså alla de som (på ett ungefär) härstammar från FORTRAN (1954) i stället för LISP (1958), de körs på ett sådant sätt att man börjar med den första raden, och trallar sedan vidare tills man nått den sista.

Lisp är däremot (mer eller mindre) funktionellt, tillsammans med några andra udda fåglar, och körs inifrån-och-ut. Kanske beror skillnaden på att FORTRAN kom till som en abstraktion för hur datorer faktiskt fungerade, medan LISP egentligen bara var tänkt som ett mindre klumpigt alternativ till den helt teoretiska Turing-maskinen. Lisp står närmare matematiken än tekniken. För de flesta andra språken, bland annat just C++, gäller definitivt det motsatta.

Ett exempel. Av någon anledning vill jag ha en funktion som tar emot ett heltal x och returnerar en jeopardy-fråga, enligt följande regler.

x är positivt och jämnt: "Vad är roten ur [x*x]?"
x är negativt och jämnt: "Vad är noll minus roten ur [x*x]?"
x är udda: "Vad är roten ur [(x-1)*(x-1)] plus ett?"
x är 0: "What is mind? No matter. What is matter? Never mind."

Utan att försöka skapa särskilt elegant kod i någotdera språk, utan snarare demonstrativ, så kommer här varianter i C++ och Scheme.

Här är utmatningen.

Vad är roten ur 16 plus ett?
Vad är noll minus roten ur 1?
Vad är roten ur 40000?
What is mind? No matter. What is matter? Never mind.
Vad är roten ur 4 plus ett?

Vad hände förresten där på slutet? ;-)

Här är en Scheme-variant:

Körning resulterar i (nästan) samma output:

Vad är roten ur 16 plus ett?
Vad är noll minus roten ur 1?
Vad är roten ur 40000?
Vad är roten ur 4611686009837453316 plus ett?

Som synes så kan Scheme, till skillnad från C++, hantera tal i vilken storlek som helst, så länge datorns minne räcker.

Förutom parenteserna, och det faktum att ett funktionsanrop i Scheme blir (jeopardy x) i stället för jeopardy(x), så lägger en obekant betraktare ganska snabbt märke till prefix-notationen. Det som skrivs "5+6+7+8.5" i språk som C++ skrivs i Scheme alltså i stället "(+ 5 6 7 8.5)".

De här två sista skillnaderna är kanske allt som egentligen håller folk borta från Scheme, har jag en känsla av. Och kanske ett par saker till: rekursion och lambda.

Fundera över följande lilla söta snutt C++ (modifierad från Wikipedia), som räknar ut summan av fibonacci-seriens första 7 tal:

Det ser visserligen litet märkligt ut för att vara C++, men så vitt jag kan förstå så är det numera giltigt. Men helt säker är jag inte. Resultatet blir i vilket fall att summan av talen i termer skrivs ut. [&](int x) { total += x; } är en anonym funktion, en lambda, som skapas där den står och sedan försvinner.

På Scheme kan man säga samma sak så här:

(let loop …) är för övrigt en omskrivning av en omskrivning av ett lambda-anrop. I själva verket skapas här en anonym funktion som tar emot en parameter ("termer"), sedan tilldelas variabeln loop en pekare till funktionen, så att den till sist kan anropa sig själv med hjälp av namnet loop. (Värt att tänka på i sammanhanget är att i Scheme så är alla variabler pekare, eller rättare sagt: De är symboler.)

Tack vare att rekursionen sker på slutet av funktionen, så blir det ändå en iteration, precis som med for_each, eftersom den nya instansen av funktionen kan ersätta den föregående i minnet utan att något går förlorat.

Men nu gör jag inte Scheme någon fullständig rättvisa. En något mera exakt motsvarighet till C++-koden ovan ser ut så här:

Men eftersom vi, som första parameter till apply, vill skicka en funktion som returnerar summan av sina parametrar, så är det förstås egentligen enklare att bara använda funktionen + direkt, i stället för att stoppa den i en lambda som ovan.

Om detta är möjligt ens i den nya C++0x-standarden vet jag faktiskt inte. Och det finns förstås massor av roligare saker man kan göra än så här. Scheme-kod är strukturerad i sitt eget data-format, vilket innebär att alla Scheme-program också är nästlade listor (motsvarande arrays eller vektorer). Kombinationen av detta och att kompilerad Scheme-kod kan köra icke-kompilerad Scheme-kod, medför att man kan exponera hela programspråket för användaren på det här viset:

Och – självfallet – att alla Scheme-program kan programmera om sig själva under tiden de körs. Eftersom jag vill pressa fram något slags skriptspråk till bakändan på H.VHS, så kan något annat knappast passa bättre; här är ju en fullständig programspråksmiljö redan på plats.

Att jag sedan tänker sätta ett filter mellan eventuella skript-kodare och (read) hör väl till saken – det finns sätt att skripta man hellre ber andra lära sig än det frenetiskt parentetiserande.

Hur, till slut, kan man integrera Scheme med C++-kod? Relativt lätt: Chicken Scheme är en Scheme-implementation som inte kompilerar direkt till maskinkod, utan till C-kod som sedan kan köras genom till exempel gcc. Det är alltså enkelt att arbeta med eller åt C-funktioner, liksom det är lätt att inkludera C-stumpar i Scheme-koden.

Något annat som är kul med Scheme är att man faktiskt får något att blogga om. Nästa gång det händer lovar jag att slänga fram något mera strukturerat innehåll än det här.

  1. 0 x) "Vad är roten ur ") ((= 0 x) "What is mind? No Matter. What is matter? Never mind.") (else "Vad är noll minus roten ur "
  2. or (and ( 0 x) (even? x
  3. 0 x) (number->string (* (- x 1) (- x 1
  4. and ( 0 x) (odd? x
  5. = x 0) "") (else "?"
  6. termer '(1 1 2 3 5 8 13
  7. termer '(1 1 2 3 5 8 13
  8. termer '(1 1 2 3 5 8 13