Het artikel analyseert de geheugenbeperkingen van LISP-systemen door de jaren heen, met een focus op het gebruik van 'cons-cellen' binnen zeer beperkte hardware.
- IBM 704 (1960): Deze machine beschikte over 32K woorden aan 36-bit kerngeheugen. Het LISP-systeem nam 12K woorden in beslag, wat ruimte bood aan circa 20.000 cons-cellen.
- PDP-1 (1964): Een compactere implementatie die werkte met 4096 woorden aan 18-bit opslag, waarbij ongeveer 2000 woorden beschikbaar waren voor het systeem en 2000 voor cellen.
- Kilo LISP: Een portable ANSI C (C89) implementatie voor PC-DOS die binnen 64 KB geheugen draait. Het systeem verbruikt 13 KB, waardoor er ruimte overblijft voor 8192 cons-cellen.
Daarnaast wordt de enorme sprong in rekenkracht benadrukt; waar de IBM 704 en PDP-1 werkten in de kHz-range en zwaar leunden op handmatig geschreven assembly, kan moderne hardware deze systemen tegenwoordig moeiteloos emuleren.
LISP-mogelijkheden in 64 KB kerngeheugen
De IBM 704
De IBM 704 elektronische gegevensverwerkingsmachine aan het M.I.T., waarop LISP in 1960 voor het eerst werd geïmplementeerd, had 32K woorden aan 36-bit kerngeheugen [1]. In dit geval betekent dit concreet één minuscule ferrietring per bit. Er waren dus in totaal $36 \times 32768 = 1.183.608$ kleine torussen ondergebracht in een niet zo klein stalen frame. De 704 vereiste een vrij ruime kamer met versterkte vloeren en industriële airconditioning. Het totale gewicht van een typische installatie was ongeveer 10 ton.
Het LISP-systeem zelf nam 12K woorden van het kerngeheugen in beslag en één woord kon een volledige cons-cel bevatten [1], waardoor de machine iets minder dan 20K cellen aan ruimte bood aan LISP. Veel 704-installaties hadden echter slechts 8K woorden of zelfs 4K woorden aan geheugen [2] — te weinig om een LISP-systeem te draaien.
Hieronder volgt een voorbeeldprogramma van LISP 1.0 uit [1]:
DEFINE
(( (SUBST (LAMBDA (X Y Z) (COND ((ATOM Z) (COND ((EQ Y Z) X)
(T Z))) (T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))) ))
()
Let op dat programma's meestal op zo weinig mogelijk regels werden getypt, omdat ze op ponskaarten moesten worden geperforeerd of via een teletype moesten worden ingevoerd die de invoer op papier kopieerde. De operator (DEFINE), de argumenten (in dubbele haakjes in het geval van DEFINE) en een omgeving moesten in drie afzonderlijke expressies aan het LISP-systeem worden geleverd.
De PDP-1
Er waren echter kleinere computers die LISP draaiden. In 1964 was er PDP-1 LISP, een implementatie voor de PDP-1 computer van DEC. Deze draaide op systemen met slechts 4096 woorden aan 18-bit opslag, waarbij het systeem zelf ongeveer 2000 woorden gebruikte [3]. Ook op de PDP-1 paste een cons-cel in een enkel woord, waardoor er ongeveer 2000 cellen beschikbaar waren voor het systeem.
Hier is een voorbeeldprogramma van PDP-1 LISP uit [3] (PDP-1 LISP maakte gebruik van kleine letters):
(rplacd (quote r1) (quote (expr (lambda (m l) (cond ((null l) m)
(t (r1 (cons (car l) m) (cdr l))))))))
(rplacd (quote reverse) (quote (expr (lambda (l) (r1 nil l)))))
Kilo LISP
Het LISP-systeem dat in het vervolg zal worden gebruikt is Kilo LISP. Dit is een portable implementatie geschreven in ANSI C (C89) die kan worden gecompileerd tot een tiny model PC-DOS executable dat draait in 64 KB geheugen.
Het LISP-systeem zelf neemt ongeveer 13 KB in beslag, waardoor er genoeg ruimte overblijft voor 8192 cons-cellen. Elke cel reserveert 5 bytes (16 bits car, 16 bits cdr en 3 bits tag, waarbij die laatste wordt afgerond naar 8 bits).
Hier is een voorbeeldprogramma:
(setq assoc
(lambda (x a)
(cond ((null a) nil)
((eq x (caar a)) (car a))
(else (assoc x (cdr a))))))
Vergelijking en Context
Het Kilo LISP-systeem biedt minder dan de helft van de cons-cellen van een grote IBM 704-installatie, maar ongeveer vier keer zoveel ruimte als een minimale PDP-1.
Natuurlijk waren oude computers traag: de IBM 704 had een kloksnelheid van 40 kHz (0,04 MIPS) en de PDP-1 werkte op 150 kHz (0,15 MIPS). Echter, de LISP-systemen op die machines waren zorgvuldig handmatig geschreven assembly-programma's en hun hardware voerde doorgaans één instructie per klokcyclus uit.
Tegenwoordig kun je waarschijnlijk een IBM 704 en een PDP-1 emuleren op een goedkope smartphone, waarbij beide draaien op een veelvoud van de snelheid van de originele hardware, terwijl je ondertussen je favoriete jump-and-run spel speelt. Hoewel een 704 of een PDP-1 waarschijnlijk alle volgende voorbeeldprogramma's zou kunnen draaien, zouden ze daar zeker de tijd voor nemen. De rest van dit essay zal zich concentreren op het geheugenaspect en de aanlooptijden negeren.
Hier is een eerste indruk van hoe antiek LISP aanvoelt.
LISP-mogelijkheden in 64 KB kerngeheugen
De IBM 704
De IBM 704 elektronische gegevensverwerkingsmachine aan het M.I.T., waarop LISP in 1960 voor het eerst werd geïmplementeerd, had 32K woorden aan 36-bit kerngeheugen [1]. In dit geval betekent dit concreet één minuscule ferrietring per bit. Er waren dus in totaal $36 \times 32768 = 1.183.608$ kleine torussen ondergebracht in een niet zo klein stalen frame. De 704 vereiste een vrij ruime kamer met versterkte vloeren en industriële airconditioning. Het totale gewicht van een typische installatie was ongeveer 10 ton.
Het LISP-systeem zelf nam 12K woorden van het kerngeheugen in beslag en één woord kon een volledige cons-cel bevatten [1], waardoor de machine iets minder dan 20K cellen aan ruimte bood aan LISP. Veel 704-installaties hadden echter slechts 8K woorden of zelfs 4K woorden aan geheugen [2] — te weinig om een LISP-systeem te draaien.
Hieronder volgt een voorbeeldprogramma van LISP 1.0 uit [1]:
DEFINE
(( (SUBST (LAMBDA (X Y Z) (COND ((ATOM Z) (COND ((EQ Y Z) X)
(T Z))) (T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))) ))
()
Let op dat programma's meestal op zo weinig mogelijk regels werden getypt, omdat ze op ponskaarten moesten worden geperforeerd of via een teletype moesten worden ingevoerd die de invoer op papier kopieerde. De operator (DEFINE), de argumenten (in dubbele haakjes in het geval van DEFINE) en een omgeving moesten in drie afzonderlijke expressies aan het LISP-systeem worden geleverd.
De PDP-1
Er waren echter kleinere computers die LISP draaiden. In 1964 was er PDP-1 LISP, een implementatie voor de PDP-1 computer van DEC. Deze draaide op systemen met slechts 4096 woorden aan 18-bit opslag, waarbij het systeem zelf ongeveer 2000 woorden gebruikte [3]. Ook op de PDP-1 paste een cons-cel in een enkel woord, waardoor er ongeveer 2000 cellen beschikbaar waren voor het systeem.
Hier is een voorbeeldprogramma van PDP-1 LISP uit [3] (PDP-1 LISP maakte gebruik van kleine letters):
(rplacd (quote r1) (quote (expr (lambda (m l) (cond ((null l) m)
(t (r1 (cons (car l) m) (cdr l))))))))
(rplacd (quote reverse) (quote (expr (lambda (l) (r1 nil l)))))
Kilo LISP
Het LISP-systeem dat in het vervolg zal worden gebruikt is Kilo LISP. Dit is een portable implementatie geschreven in ANSI C (C89) die kan worden gecompileerd tot een tiny model PC-DOS executable dat draait in 64 KB geheugen.
Het LISP-systeem zelf neemt ongeveer 13 KB in beslag, waardoor er genoeg ruimte overblijft voor 8192 cons-cellen. Elke cel reserveert 5 bytes (16 bits car, 16 bits cdr en 3 bits tag, waarbij die laatste wordt afgerond naar 8 bits).
Hier is een voorbeeldprogramma:
(setq assoc
(lambda (x a)
(cond ((null a) nil)
((eq x (caar a)) (car a))
(else (assoc x (cdr a))))))
Vergelijking en Context
Het Kilo LISP-systeem biedt minder dan de helft van de cons-cellen van een grote IBM 704-installatie, maar ongeveer vier keer zoveel ruimte als een minimale PDP-1.
Natuurlijk waren oude computers traag: de IBM 704 had een kloksnelheid van 40 kHz (0,04 MIPS) en de PDP-1 werkte op 150 kHz (0,15 MIPS). Echter, de LISP-systemen op die machines waren zorgvuldig handmatig geschreven assembly-programma's en hun hardware voerde doorgaans één instructie per klokcyclus uit.
Tegenwoordig kun je waarschijnlijk een IBM 704 en een PDP-1 emuleren op een goedkope smartphone, waarbij beide draaien op een veelvoud van de snelheid van de originele hardware, terwijl je ondertussen je favoriete jump-and-run spel speelt. Hoewel een 704 of een PDP-1 waarschijnlijk alle volgende voorbeeldprogramma's zou kunnen draaien, zouden ze daar zeker de tijd voor nemen. De rest van dit essay zal zich concentreren op het geheugenaspect en de aanlooptijden negeren.
Hier is een eerste indruk van hoe antiek LISP aanvoelt.
Groetjes,