SLED - Schemy LISP voor DOS

Kenmerken

• Scheme-achtige LISP-interpreter voor DOS (of DOSBox).
• Werkt in 16-bit Real Mode.
• Klein geheugenmodel (Small Memory Model).
• Staartaanroep-optimalisatie (Tail-Call Optimization - TCO).
• Lexicale scoping.
• Mark & Sweep Garbage Collector.
• Trampoline-evaluator.
• Ongeveer 1,1K regels code (C89).
• 8 speciale vormen (Special Forms).
• 21 ingebouwde functies.
• Standaardbibliotheek met 21 functies.
• Executable van 11K.
• Open-source (0BSD).

Over SLED

Voor een overzicht van de beschikbare symbolen, speciale vormen, ingebouwde functies en de standaardbibliotheek, zie de index.

Gegevens

Er zijn twee fundamentele gegevenstypen: Pairs (paren) en Atoms (atomen/niet-paren). Atomen komen voor in drie varianten: Symbolen, Closures (functies) en enkele Speciale Symbolen.

Symbolen

Symbolen zijn unieke namen en bestaan uit een combinatie van maximaal 16 van de volgende tekens: a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 0 - . ? _ waarbij de punt (.) niet het eerste teken mag zijn.

Daarnaast kan elk printbaar ASCII-teken deel uitmaken van een symbool wanneer het wordt voorafgegaan door het escape-teken \ (backslash), met uitzondering van (, ), ' en $. Voorbeeld: This\ is\ a\ sym\!

Hoofdletters worden geaccepteerd, maar worden omgezet naar kleine letters, tenzij het teken is geëscaped.

Speciale Symbolen

Er zijn enkele vooraf gedefinieerde speciale symbolen die door SLED worden beheerd, zoals nil, wat "lege lijst" betekent. Zie de index voor details.

Quote

Een quote betekent "niet evalueren". Via de speciale vorm quote wordt een symbool geregistreerd: (quote sym)

Voor het gemak kan de korte syntax ' worden gebruikt: 'sym

In essentie verklaart quoting iets als data in plaats van code.

Pairs (Paren)

Paren bestaan uit een kop (head) en een staart (tail), die elk een atoom of een ander paar bevatten. Een paar kan als data worden gemaakt met de punt (.): '(a . x) of als resultaat van de ingebouwde functie cons: (cons 'a 'x)

De elementen van een paar (kop en staart) zijn onveranderlijk (immutable).

Lijsten

Een lijst is een reeks paren waarbij elke staart wijst naar een ander paar, behalve de laatste, wiens staart de waarde nil heeft, wat gelijkstaat aan (). Voorbeelden van lijsten:

• nil
• '()
• '(a . nil)
• '(a . (b . nil))

Een lijst kan als data worden gemaakt via: '(a b) of als resultaat van de functie list uit de standaardbibliotheek: (list 'a 'b)

Incorrecte Lijsten (Improper Lists)

Een incorrecte lijst eindigt niet met nil, bijvoorbeeld: (a . (b . (c . d)))

Associatielijsten (Association Lists)

Een associatielijst is een lijst waarbij elk element een paar (associatie) is: ((a . x) (b . y) (c . z)) Het kopgedeelte van zo'n paar wordt de key (sleutel) genoemd en de staart de value (waarde).

S-Expressies

Een symbolische expressie (S-expressie) is een datastructuur gedefinieerd als: Een S-expressie is ofwel een atoom, ofwel een paar van S-expressies. In Lisp, Scheme, en in het bijzonder in SLED, worden S-expressies gebruikt voor zowel data als broncode.

Getallen

Het SLED-systeem bevat geen numerieke typen. Natuurlijke getallen (niet-negatieve gehele getallen) kunnen echter worden geëmuleerd met lijsten:

• '() : nul
• '(nil) : één
• '(nil nil) : twee
• '(nil nil nil) : drie

Dit zijn tally numerals (streepgetallen), waarbij de cardinaliteit de grootte vertegenwoordigt, vergelijkbaar met von Neumann-ordinale getallen. De functies inc, dec en zero? vergemakkelijken teltaken.

Code

In LISP wordt niet-gequoted data geëvalueerd als code.

Bindingen

Een binding koppelt een symbool aan een bepaalde payload van data en wordt aangemaakt via de speciale vorm define: (define a 'x)

Closures

Closures zijn functies samen met een omgeving, en resulteren uit de speciale vorm lambda: (define fun (lambda (arg1 arg2) (print arg1) (print arg2)))

Functie-aanroep

Het eerste element van een niet-gequotede lijst wordt geïnterpreteerd als een expressie die evalueert tot een functie, en de overige elementen als argumenten voor die functie: (fun arg1 arg2)

De functie-evaluatie is eager: eerst worden de argument-expressies geëvalueerd, daarna vindt de functie-aanroep plaats met de geëvalueerde argumenten.

Argumenten

Argumenten worden geëvalueerd en als een lijst van waarden aan een functie doorgegeven. Dit betekent dat functieparameters op verschillende manieren kunnen worden opgezet:

• (lambda x ...) : x is een lijst
• (lambda (x y) ...) : gedestructureerde lijst met elementen x en y
• (lambda (x y . z) ...) : z is een lijst (die standaard nil is)

Optionele argumenten kunnen als een lijst worden doorgegeven, zoals z hierboven.

Recursie

LISP's vertrouwen op recursie in plaats van iteratie. Recursie verwijst naar een functie die zichzelf aanroept. Twee functies van SLED helpen om een stack overflow bij diepe recursies te voorkomen: de trampoline-evaluator en staartaanroep-optimalisatie (TCO). TCO werkt voor lambda, let, begin, if, ifnil en apply. Daarnaast werkt TCO voor cons als de recursie plaatsvindt in het tweede argument.

Fouten

Een fout tijdens de evaluatie van een expressie springt terug naar het hoogste niveau (top-level), waar kan worden getest of er een fout is opgetreden. Een fout kan niet binnen een expressie worden opgevangen.

Ingebouwde Functies

Een set functies is ingebouwd in het SLED-executable om interactie met het systeem en kernfunctionaliteit mogelijk te maken. Zie de index voor details.

Standaardbibliotheek

Naast de kernfuncties is een set typische functies geïmplementeerd als een standaardbibliotheek in het bestand sled.scm. Zie de index voor details. De standaardbibliotheek kan worden uitgebreid met aanvullende eigen definities.

Speciale Vormen

Bepaalde vormen lijken op functies, maar dat zijn ze niet. Deze zogenaamde special forms volgen niet het gedrag van functies, maar gebruiken wel dezelfde syntax. Bijvoorbeeld: if evalueert zijn argumenten niet voordat de vorm wordt opgelost. Zie de index voor details.

Onveranderlijkheid (Immutability)

Speciale symbolen, speciale vormen, ingebouwde functies en de inhoud van de standaardbibliotheek zijn onveranderlijk in SLED. Bovendien kunnen speciale vormen en ingebouwde functies niet worden overschaduwd (shadowed). De standaardbibliotheek en aangrenzende eigen definities kunnen niet opnieuw worden gedefinieerd.

Systeem

SLED is een DOS-applicatie.

Bestandsnamen

Bestandsnamen moeten voldoen aan de DOS 8.3 naamgeving (maximaal 8 tekens voor de bestandsnaam, een punt, maximaal 3 tekens voor de extensie). De aanbevolen extensie voor scripts is .scm vanwege de syntactische gelijkenis met Scheme; bijvoorbeeld de standaardbibliotheek heet sled.scm. De interpreter controleert de extensie echter niet.

Opstarten

De eerste actie die sled onderneemt is het laden van de standaardbibliotheek (sled.scm), die in dezelfde map als het SLED.EXE executable moet staan. Alle symbolen en hun waarden die uit de standaardbibliotheek worden geladen, worden onveranderlijk.

Command-Line Argumenten

Het sled binary heeft vier wederzijds uitsluitende command-line argumenten:

1. C:\> sled /? : Toont de helppagina.
2. C:\> sled code.scm : Pad naar een Lisp-bronbestand dat geladen wordt vóór de REPL start, maar ná de standaardbibliotheek.
3. C:\> sled /B code.scm : "Batch mode", sluit af na uitvoering.
4. C:\> sled /I code.scm : "Ignore errors", gedraagt zich als /B maar gaat door met de uitvoering na een fout.

Het bestandspad moet altijd het laatste argument zijn.

Bestandspad

In de interpreter moeten backslashes (\) in het pad worden geëscaped, aangezien het pad een symbool wordt en een enkele backslash geen toegestaan symboolteken is. C:\> sled to\my\code.scm (load 'to\\my\\code.scm)

Het bestandspad valt ook onder de limiet van 16 tekens.

REPL

Zodra sled is gestart, begint de read-eval-print-loop (REPL) met een prompt: sled> De REPL leest invoer, evalueert deze, print het resultaat en toont opnieuw de prompt. Voorbeeld: sled> (println 'hello _ 'world)

Uitgebreide Tekens

Een valkuil zijn uitgebreide (two-byte) tekens, die niet worden ondersteund. Een voorbeeld is het gebruik van de pijltjestoetsen in de REPL, wat resulteert in een α (alpha) in de standaard input-echo. Deze tekens vervuilen de inputstream en kunnen een fout in een invoerregel veroorzaken, zelfs als ze zijn gewist.

Afsluiten

Er zijn twee reguliere manieren om sled af te sluiten:

1. Het dollarteken $ op het hoogste niveau, wat de parser vertelt om af te sluiten: sled> $
2. De ingebouwde functie (exit), die bij evaluatie afsluit.

Commentaren

Commentaren worden genegeerd door de parser en beginnen met een puntkomma (;). Alle tekens tot de volgende regelafbreking worden genegeerd. Traditioneel geeft het aantal opeenvolgende puntkomma's de semantiek aan, vergelijkbaar met Markdown-koppen:

• ;;;; hoofdtitle
• ;;; sectietitel
• ;; begin van regel
• ; einde van regel

Daarnaast worden blokcommentaren gerealiseerd via de speciale vorm comment: (comment ...) Haken binnen een comment-vorm moeten in balans zijn:

• (comment ()) : OK
• (comment () : → fout

Let op: een comment-vorm kan niet worden gequoted: '(comment test) → fout.

Onderbreken

Om een pure berekening te onderbreken, gebruik je CTRL+Break. Voor het onderbreken van invoer is CTRL+C beschikbaar.

Help

In de REPL kan het symbool ? worden gebruikt om een lijst van speciale vormen, ingebouwde functies en symbolen uit de standaardbibliotheek op te vragen.

Limieten

Als real-mode DOS-programma heeft SLED meerdere beperkingen:

• De heap heeft 12288 nodes.
• De symbolentabel heeft 2048 tekens.
• De standaardbibliotheek verbruikt ongeveer 5% van de nodes en tekens.

Index

Speciale Symbolen

• $ : Sluit de REPL af (werkt alleen vanaf de prompt).
• ? : Overzicht van speciale vormen, ingebouwde functies en standaardbibliotheek (werkt alleen vanaf de prompt).
• ' : Alias voor de speciale vorm quote.
• ans : Bevat het resultaat van de laatste form op het hoogste niveau die een waarde produceerde.
• err : Markeert een foutstatus.
• nil : Vertegenwoordigt de lege lijst en is de enige waarde die als "false" wordt geëvalueerd. Gelijk aan '().
• self : Maakt anonieme recursie mogelijk. Binnen een closure verwijst het naar de omhullende lambda.
• true : Evalueert naar true. Gebruik als generieke "true"-waarde.
• ver : Evalueert naar een symbool dat de versie van SLED aangeeft.

Speciale Vormen

• begin <body1> ... <bodyN> : Evalueert argumenten sequentieel en retourneert de waarde van het laatste argument.
• comment <arg1> ... <argN> : Wordt niet geëvalueerd; dient als blokcommentaar. Haken moeten gebalanceerd zijn.
• define <sym> <arg> : Creëert een nieuwe binding van het tweede argument aan het eerste symbool. Beïnvloedt altijd de globale binding.
• if <arg1> <arg2> [<arg3>] : Evalueert arg1; als dit niet nil is, wordt arg2 geretourneerd, anders arg3 (of nil).
• ifnil <arg1> <arg2> : Retourneert het resultaat van arg1 als dit niet nil is, anders arg2.
• lambda (<arg1> ... <argN>) <body1> ... <bodyN> : Creëert een functie met argumenten als gedestructureerde lijst en een sequentieel geëvalueerd lichaam.
• let (<arg1> <arg2>) <body1> ... <bodyN> : Creëert een scope met één lokale binding. Meerdere bindingen vereisen geneste lets.
• quote <arg> : Retourneert het argument ongeëvalueerd.

Ingebouwde Functies

• apply <fun> <lst> : Evalueert de eerste argument-functie met de tweede argument-lijst als argumenten.
• atom? <arg> : Retourneert true als het argument een atoom is.
• cons <arg1> <arg2> : Retourneert een paar met arg1 als kop en arg2 als staart.
• defined? <sym> : Retourneert true als het symbool is gedefinieerd in de globale scope.
• empty? <arg> : Retourneert true als het argument de lege lijst is.
• env : Print de huidige door de gebruiker gedefinieerde symbolen.
• eof? <arg> : Retourneert true als het argument een EOF (End-Of-File) of EOT (End-Of-Transmission) symbool is.
• equiv? <arg1> <arg2> : Controleert op ondiepe gelijkheid (shallow equality). Gebruik voor atomen.
• error <sym> [<arg>] : Gooit een fout, onderbreekt de evaluatie en print een foutmelding en optionele reden.
• exit : Sluit de interpreter of REPL af.
• gc [<arg>] : Activeert garbage collection. Print node-gebruik als het argument niet nil is.
• head <arg> : Retourneert het kopgedeelte van een cons-cel of lijst (correspondeert met car).
• load <sym> [<arg>] : Evalueert de inhoud van het bestand op het opgegeven pad. Kan maximaal twee keer genest worden.
• newline : Print een regelafbreking.
• print <arg1> ... <argN> : Print argumenten naar de standaard output.
• proc? <arg> : Retourneert true als het argument een closure of ingebouwde functie is (niet voor speciale vormen).
• read : Leest een symbool als een regel invoer vanaf de standaard input.
• restart [<sym>] : Reset en herstart de interpreter; optioneel wordt een bestand geladen. Alle definities gaan verloren.
• symbol? <arg> : Retourneert true als het argument een symbool is.
• tail <arg> : Retourneert het staartgedeelte van een cons-cel (correspondeert met cdr).
• value <sym> : Lost de waarde van het symbool op, rekening houdend met lexicale scope.

Standaard Aliases

• _ : Alias voor het spatie-teken \ .
• br : Alias voor newline.
• nil? : Alias voor empty?.
• not : Alias voor empty? (om resultaten van predicaten om te keren).
• quit : Alias voor exit.
• zero? : Alias voor empty? (voor tally-getallen).

Standaardbibliotheek

• and? <arg1> <arg2> : Binaire predicaat; retourneert true als beide argumenten niet nil zijn.
• append <lst1> <lst2> : Concateneert de tweede lijst aan het einde van de eerste.
• assert <arg> <sym> : Print het tweede argument en veroorzaakt een fout als het eerste argument nil is.
• compose <arg> <fun1> ... <funN> : Pijplijnt unaire functies: het resultaat van de vorige functie is het argument voor de volgende.
• dec <arg> : Retourneert de staart van een lijst (om tally-getallen te decrementeren).
• equal? <arg1> <arg2> : Controleert of argumenten recursief gelijk zijn. Gebruik voor paren en lijsten.
• error? : Thunk-predicaat; retourneert true als de vorige evaluatie in een fout resulteerde.
• get <sym> <lst> : Retourneert de waarde gekoppeld aan het symbool in de associatielijst, anders nil.
• id <arg> : Identiteitsfunctie; retourneert het argument.
• inc <arg> : Voegt nil toe aan het begin van een lijst (om tally-getallen te incrementeren).
• list <arg1> ... <argN> : Bouwt een lijst van de gegeven argumenten.
• list? <arg> : Retourneert true als het argument een correcte lijst is.
• map <fun> <lst> : Past de functie toe op elk element van de lijst en retourneert de lijst met resultaten.
• member <arg> <lst> : Retourneert het paar uit de lijst waarvan de kop gelijk is aan het argument, anders nil.
• or? <arg1> <arg2> : Binaire predicaat; retourneert true als een van de argumenten niet nil is.
• pair? <arg> : Retourneert true als het argument geen atoom is.
• printid <arg1> [<arg2>] : Print het argument (en optioneel een prefix) gevolgd door een regelafbreking, en retourneert het argument.
• println <arg1> ... <argN> : Print argumenten naar de standaard output inclusief een regelafbreking.
• put <sym> <arg> <lst> : Update of voegt een paar toe aan de associatielijst.
• reverse <lst> : Keert de volgorde van de lijst om.
• shorter? <lst1> <lst2> : Retourneert true als de eerste lijst minder elementen heeft dan de tweede.

Gebruik

SLED is gemaakt voor een disk operating system zoals FreeDOS of MS-DOS. Buiten DOS is een emulator zoals DOSBox, DOSBox-X of DOSBox-Staging vereist.

• Op Linux, BSD, MacOS of Unix kan het shell-script ./sled.sh worden uitgevoerd (selecteert automatisch de geïnstalleerde DOSBox).
• Voor het bouwen van SLED is de Microsoft C Compiler of Open Watcom nodig, samen met make.
• Bouwen met MS C 6.0A: make build_msc
• Bouwen met Open Watcom v2: make build_owc
• Uitvoeren: make run
• Tests draaien: make tests
• Benchmark draaien: make bench (Takeuchi-functie).

Links

• DOS
• Kilo LISP
• PC Scheme (Implementatie en vergelijking van LISP-interpreters voor MS-DOS)
• Gratis Lisp-ontwikkelomgevingen voor DOS
• S-expressions

Dit project door gramian is gelicentieerd onder de 0BSD (Zero-Clause BSD) licentie.