Scheme編 入替えプログラム ~動かない~
Lispのひとの話からプログラムに必要なところを抜き出します。
まずは、Conditional Expressionsについてです。
(p₁ → e₁, ⋯ , pₙ → eₙ)がconditional expressionsのかたちです。
pは、propositional expressionsでeは任意のexpressionsです。
次は、S-expressionsについてです。
Atomic symbolsはS-expressionsです。
Atomic symbolsには、大文字と数字とそれらに埋め込まれた空白とからなる文字列が使われます。
e₁とe₂がS-expressionsなら(e₁∙e₂)もS-expressionsです。
(∙)はordered pairです。
次は、Listについてです。
リストは、S-expressionsで表現できます。
(m₁, m₂, ⋯, mₙ)は
(m₁∙(m₂∙(⋯(mₙ∙NIL)⋯)))になります。
NILはatomic symbolで、Listの終端に使われます。
最後は、functionsについてです。
functionsは、普通の記法で書きます。ただし、S-expressionsの関数と区別するために名前と変数は小文字にし、()を[]に、,を;にします。これをM-expessionsといいます。
eq [x; y]は、xとyがatomicのときに定義され、xとyが同じsymbolならT、違うならFです。
car [x]は、xがatomicでないときに定義されます。car [(e₁∙e₂)] = e₁です。
cdr [x]は、xがatomicでないときに定義されます。cdr [(e₁∙e₂)] = e₂です。
cons [x; y]は、任意のxとyについて定義されます。cons [e₁; e₂]= (e₁∙e₂)です。
こうやってまとめて書くと、かしこくなった気がしますが、実際には、ただ写しているだけで、よく分かっていません。
さて、実際にプログラムを作ってみます。
入れ替えを手でやるときは、"program"の後ろから一文字づつ順番に書いていきます。
これをLispの形にすると・・・一番後ろの文字を取り出した残りがうまく作れません。
発想を転換して、"program"の前から一文字づつ取り出して逆さまに並べることにします。
入れ替えのfunctionをirekaeとすると、
irekae [x; y] = (eq [x; NIL] → y, T → irekae [cdr [x]; cons [car [x]; y])
Church's λ-notationにより、
irekae = λ[[x; y]; (eq [x; NIL] → y, T → irekae [cdr [x]; cons [car [x]; y])]
irekaeはirekaのなかにでてくるので、
label [irekae; λ[[x; y]; (eq [x; NIL] → y, T → irekae [cdr [x]; cons [car [x]; y])]]
これに、programを代入すると、
label [irekae; λ[[x; y]; (eq [x; NIL] → y, T → irekae [cdr [x]; cons [car [x]; y])]][[(P∙ (R∙ (O∙ (G∙ (R∙ (A∙ (M∙ NIL))))))); NIL]]
M-expressionsをS-expressionsに訳すと、
((LABEL, IREKAE, (LAMBDA, (X, Y), (COND, ((EQ, X, NIL), Y), (T, (IREKAE, (CDR, X), (CONS, (CAR, X), Y)))))), ((P,R,O,G,R,A,M), NIL))
さっそくschemeに入れてみたいと思います。
もらったメモを見ながら、
> busybox ed : a [S-expressionsを入れます] . : w irekae : q > sbcl --load irekae
なんだか英語がたくさんでてきてよくわかりませんが、うまく動いてないことだけは確かです。
こうなるかもと思ってましたのでショックはありません。本当です。
LispとSchemeは、古典と現代文みたいに違うのかもしれません。
Schemeは一休みです。
"コンピュータのしくみを理解するための10章"の読書が進み、内容が少し理解できるようになったので、アセンブラ言語に戻りたいと思います。