The Coding Swede: Började skriva en Lisp-interpretator i C#

Bakgrund

Det här inlägget ska klargöra, (för dig, men också för mig själv), varför jag började försöka skriva en Lisp-interpretator i C# och hur långt jag kommit hittills.

Mycket kort Lisp-intro

Lisp är ett gammalt programmeringsspråk, det specades 1960 och är det näst äldsta högnivåspråket som fortfarande används (Fortran är äldst). Namnet är ett sammandrag av LISt Processing. Det finns många dialekter av språket, där de mest kända är Common Lisp, Scheme, Racket och Clojure.

Nåt som gör att Lisp ser en aning egendomligt ut är att uttryck avgränsas av parenteser och att det är prefix-noterat. Att skapa en variabel och binda det till värdet av en beräkning kan i ett krystat exempel i C# se ut såhär:

int x = 1 + 2;

I Lisp skrivs det såhär:

(define x (+ 1 2))

Prefix-notationen innebär att operatorn kommer först i ett uttryck och sen dess argument. Det kan se lite avigt ut när man är van med annat.

Varför är "list" en del av Lisps namn då? Jo, programkoden utgörs av listor, som byggs upp av enkellänkade par. Uttrycket ovan representeras internt med den här strukturen:

Hur jag kom i kontakt med Lisp

När jag började på högskolan i Linköping så möttes man, som jag minns det, av en mängd mattekurser. När man tagit sig igenom dem, så var det äntligen dags att programmera! Men mycket snart upptäckte vi att det skulle göras i gamla dammiga Common Lisp 😱 När det fanns C++ och Java?!? Men, det var nog vettigt, det gav förståelse för att programmeringsspråk är verktyg som har olika styrkor och svagheter och att inte fastna för mycket i ett enda. Jag kan dock inte påstå att jag har använt just Lisp utanför skolan än.

Så, varför skriva en egen interpretator?

Ja, varför? Det har säkert gjorts massor av gånger förr, så det finns förmodligen absolut noll behov av en till. Det var nog mest bara för att se om jag kan. Och dels för att jag gäckas av att jag på flera ställen sett utvecklare referera till den gamla boken "Structure and Interpretation of Computer Programs" som nån slags holy grail. Jag hade den som kursbok på högskolan, men det känns som att jag aldrig fick nån riktig "kontakt" med den.

Eftersom den anses så speciell så har jag några gånger på senare tid försökt läsa den, men det har inte gått att hålla intresset uppe. Andra halvan av boken handlar om att implementera en Lisp-interpretator i Lisp, en så kallad "metacircular interpreter", så jag tänkte att en ingång som skulle kunna göra boken mer intressant är att faktiskt utveckla en själv, men i C# istället. Hittills tycker jag att det fungerat bra, det har naturligt väckts en hel del frågeställningar som jag får leta reda på svaren på. Tanken var från början att göra så mycket som möjligt utan stöd från boken eller nätet för att inte bli påverkad för mycket eller få för många svar direkt så att jag skulle tappa intresset. Men jag fastnade fort och använder boken helt fritt och har även sökt på nätet en hel del, men fortfarande restriktivt för att inte bli serverad för mycket 😊

Resultat hittills

Såhär i efterhand, när jag är en bit på vägen, så hade varit lite intressant om jag skrivit nån slags notering om mina tankar efter varje sittning med detta. Men det har jag inte gjort, så det får bli en liten sammanfattning av var jag är nu och de minor jag kan minnas.

Ha alltid med ett Environment-objekt

När jag började så skapade jag bara en Evaluator-klass och skickade in Lisp-uttryck till den, till exempel addition.

var result = Eval("(+ 1 2)");

Det gick bra, till en början. Sen behövde jag spara värden på variabler, hur skulle jag hantera dem? Det hade säkert gått att spara även dem i evaluatorn, men det blev snabbt enligt bokens förslag en egen klass för omgivningen "Environment".

var env = new Environment();

var result = Eval("(define x (+ 1 2))", env);

Nu kunde variabelvärden sparas till och hämtas från Enviroment-objektet.

I samband med detta förstod jag att även funktionen "+" ska kunna sparas som ett värde på en variabel och därmed slås upp och hämtas från Environment. Då började jag få problem med att jag skickade runt uttryck som strängar och jag kunde inte spara "+"-funktionen som en sträng i Environment.

Uppdelning i lexer, parser och evaluator

Den som skriver en "metacircular interpreter" stöter inte på problemet med hur data ska representeras, eftersom den redan arbetar med Lisp-data. Men när man skriver interpretatorn i ett eget språk så uppstår frågan hur data ska representeras. Min start där allt var strängar höll inte. Efter lite sökande på nätet stötte jag på https://amirkamil.github.io/project-scheme-parser/ som beskriver att processen kan delas upp i tre steg, lexing, parsing och evaluation.

Lexer

En lexer tar en sträng och delar upp den i tokens. Skickar man in strängen nedan i min lexer

"(define x (+ 1 2))"

så delar den upp strängen i en lista med tokens: [(, define, x, (, +, 2, 3, ), )]

Parser

Parsern tar sedan dessa tokens och gör om dem till listobjekt. Till detta har jag klassen ListExpression, som ärver av Expression och sparar två Expression-värden internt, left och right.

public class ListExpression : Expression

{

private readonly Expression? _left;

private readonly Expression? _right;

public ListExpression(Expression? left, Expression? right)

{

_left = left;

_right = right;

}

Evaluator

Nu har evaluatorn ett listobjekt att jobba med. Huvudfunktionen Eval i den ser just nu ut enligt nedan.

public Expression Eval(Expression expression, Environment env)

{

if (IsSelfEvaluating(expression))

return expression;

else if (expression is VariableExpression ve)

return env.GetValue(ve.Value);

else if (SpecialFormAssignment.Recognises(expression))

return SpecialFormAssignment.Evaluate(expression, this, env);

else if (SpecialFormIf.Recognises(expression))

return SpecialFormIf.Evaluate(expression, this, env);

else if (SpecialFormAnd.Recognises(expression))

return SpecialFormAnd.Evaluate(expression, this, env);

else if (SpecialFormOr.Recognises(expression))

return SpecialFormOr.Evaluate(expression, this, env);

else if (expression is ListExpression list)

{

var evaluatedOperator = Eval(Operator(list), env);

var evaluatedOperands =

EvalOperands(Operands(list), env).ToList();

return Apply(evaluatedOperator, evaluatedOperands, env);

}

throw new Exception(

$"Can not evaluate the expression '{expression}'");

}

Den hanterar hittills:

Självevaluerande uttryck.
Bool och nummer, ska nog lägga till sträng-hantering med.
Variabeluppslag
Tilldelning av värde till variabel
If
Uttryck
Just nu endast +, - och specialformerna and och or.
(Ett vanligt uttryck evaluerar alla argument, en specialform evaluerar bara de argument som behöver evalueras.)

Så det finns en hel del kvar att göra, dels mängdgöra där stöd för flera matematiska operatorer är en del, t ex < > = * /, men det som är lite mer spännande är nog att lägga till stöd för att definiera egna metoder. Och eftersom det här inte på nåt sätt är ett försök att göra en komplett implementation av Lisp (eller egentligen Scheme) så kommer jag nog gå i riktning mot det som jag för tillfället känner mig mest nyfiken på att utforska.

Prova på eller titta på kod

Testa kan du göra genom att köra programmet som ligger här.

Plus och minus