64KBのメモリでできるLISPyなこと (2019)
LISPy things you can do in 64K bytes of core (2019) (t3x.org)
要約
この記事は、初期のLISP実装が直面したメモリの制約について論じています。IBM 704やPDP-1といった初期のコンピュータでは、限られたメモリ空間（数万ワード）でLISPシステムとプログラムが動作していました。現代のKilo LISPのような実装では、64KBという非常に小さなメモリ空間でも、当時のシステムと同等かそれ以上の機能を実現できることを示しています。
全文翻訳
64KBのメモリでできるLISPyなこと
ここで「64KBのメモリで」とは、LISPシステム、ランタイムスタック、およびコンスプール（cons pool）全体で64KBを意味します。これは、基本的なDEC PDP-11や、tiny-modelのPCDOSプログラムでLISPシステムが得られるスペース量です。おそらく、LISPの最初の実装が使用できたスペースよりも少し少ない量です。
LISPが1960年に初めて実装されたIBM 704電子データ処理機は、36ビットワードの32Kワードのコアメモリを持っていました[1]。これは、ビットごとに1つの小さなフェライトリングを意味します。そのため、合計で36×32768=1,183,608個の小さなトロイドが、それほど小さくないスチールフレームに収められていました。704は、強化された床と産業用空調を備えたかなり広々とした部屋を必要としました。典型的な設置の総重量は約10トンでした。
LISPシステム自体は12Kワードのコアを占め、1ワードで完全なコンスセル（cons cell）を保持できたため[1]、このマシンはLISPに20Kセル未満のスペースを提供しました。しかし、MITのIBM 704はかなり装備の整ったマシンでした。多くの704システムは、8Kワードや4Kワードのメモリしか搭載していませんでした[2]。これはLISPシステムを実行するには少なすぎます。以下は[1]からのLISP 1.0のサンプルプログラムです。
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))))))) ))
()
プログラムは通常、可能な限り少ない行数で入力されていました。なぜなら、パンチカードにパンチしたり、紙にエコーバックするテレタイプで入力する必要があったからです。オペレーター（DEFINE）、引数（DEFINEの場合は二重括弧内）、および環境は、3つの別々の式でLISPシステムに供給する必要がありました。
しかし、LISPを実行していたより小さなコンピュータもありました。1964年にはPDP-1 LISPがあり、これはDECのPDP-1コンピュータの実装で、18ビットストレージの4096ワードという少ないシステムでも動作し、システム自体は約2000ワードを使用していました[3]。PDP-1でさえ、コンスセルは1つのワードに収まったため、システムには約2000セルのスペースが利用可能でした。以下は[3]からのPDP-1 LISPのサンプルプログラムです。はい、PDP-1 LISPは小文字を使用していました。
(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)))))
以下で使用されるLISPシステムはKilo LISPです。これはANSI C（C89）で書かれたポータブルな実装で、64KBのメモリで動作する非常に小さなPCDOS実行可能ファイルにコンパイルできます。LISPシステム自体は約13KBを占め、8192個のコンスセル用のスペースを残します。各セルは5バイト（16ビットのcar、16ビットのcdr、および3ビットのタグ、後者は8ビットに切り上げ）を割り当てます。以下はサンプルプログラムです。
(setq assoc
(lambda (x a)
(cond ((null a) nil)
((eq x (caar a)) (car a))
(else (assoc x (cdr a))))))
Kilo LISPシステムは、大規模なIBM 704システムよりも半分以下のコンスセルを提供し、最小限のPDP-1の約4倍のスペースを提供します。もちろん、古いコンピュータは遅かったです。IBM 704のクロックスピードは40kHz（0.04 MIPS）で、PDP-1は150kHz（0.15 MIPS）で動作していましたが、当時のこれらのマシン上のLISPシステムは注意深く手作業で作成されたアセンブリ言語プログラムであり、そのハードウェアは通常、クロックサイクルごとに1つの命令を実行しました。
今日では、おそらく安価なスマートフォンでIBM 704とPDP-1の両方をエミュレートでき、元のハードウェアの速度の数倍で動作させながら、お気に入りのジャンプ＆ランゲームをプレイすることもできます。したがって、704やPDP-1は以下のすべてのサンプルプログラムを実行できたかもしれませんが、間違いなく時間がかかったでしょう。このエッセイの残りの部分は、メモリの側面に焦点を当て、実行時間は無視します。
古代のLISPがどのようなものかについての最初の印象はこちらです。