ノート Exercise 5.52 C言語でShemeコンパイラを作れと言っているのではなく、この章のコンパイラをCのプログラムを吐く様に改造せよと言っている。 ここでもswiftを使う事にする。直ぐに気づく問題点は レジスタマシンやアセンブラのレベルに変換する訳では…
ノート Exercise 5.51 5.2ではレジスタマシン・シミュレータをSchemeで実装したが、これをC言語で実装するなら5.4のExplicit Evaluatorは基本的には何も変換する必要はない筈なのできっと問題の意図とは異なる。そうすると『レジスタマシン相当の実行環境をC…
ついに最終節 ノート REPLからコンパイラを呼び出して、REPLの環境で実行する。 explicit controller machineはインタープリタだが、コードをコンパイルする組み込みの手続きを用意する。変数として格納されている手続きをオペレータとしてprocに入れた後に…
ノート Compiling linkage code compile-linkageは各式を命令に変換した後、次の命令への繋ぎを生成する。 引数が'returnの時はレジスタcontinueの内容にジャンプ、'nextであれば何もしない、その他であれば引数をラベルとみなしてそのラベルにジャンプする…
ノート 前節のインタープリタのプログラムは機械語のプログラムと捉えることができる。 ソースプログラムと機械語とを橋渡しする方法には二つある。 一つはインタープリタ。インタープリタの基本的な命令は機械語のサブルーチンとして実現されていて、ソース…
ノート ここに書いてあるドライバーループは既に実装として使っている。しかもExcersese 5.25では少し変更もしている。 Exercise 5.25の結果でもちゃんと例は動作する。 (define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) ;;; EC-E…
ノート 第４章のMetacircular evaluatorをレジスタマシンで実現する。 Registers and operations 第４章で実装した各シンタックスに対応する手続きをそのままレジスタマシンに移植する事も出来るが、ポイントがズレてしまうので各シンタックスに対応する処理…
ノート レジスタマシンとしてのScheme評価器を実装する前に、メモリ割り当てに関する問題を片付けておく。 一つの問題はペア（セル）をどう表現するのか。もう一つの問題は実際には有限のメモリサイズをあたかも無限にあるかの様に見せる技術。 5.3.1 Memory…
ノート パフォーマンスを測る為の仕組みをシミュレータに組み込む。 Exercise 5.14 0を入力すると終了する様にfactorial-machineを改造して実行する。 > (define factorial-machine (make-machine (list (list '= =) (list '- -) (list '* *) (list 'read re…
ノート make-execution-procedureはレジスタマシン言語の命令毎のディスパッチャ。各命令毎に実行する為の手続きを返す手続きが定義されている。 Assign instructions 命令に指定されているレジスタ、式をローカル変数に保存して引数無しの手続きを返す。値…
ここからはシミュレータの解説。モデルとしては完全にオブジェクト指向的。 ノート make-machineではメッセージパッシングに応答する手続きを作る。つまりメソッドを持ったオブジェクト。実際にはmake-new-machineがオブジェクトを作り、make-machineではそ…
いよいよ本題な感じ。 ノート Exercise 5.7 実装してみないことには何も分からないので、先の節の実装を写経してシムレータを作成してから実行してみる。 Racketではペアはimmutableでset-cdr!は使えないので、instructionのペアのメソッドを以下の様にmpair…
ノート 昔懐かしいBASICの世界。共通部分を括り出す。 括り出すステップ： それぞれのGCD計算部分の先頭にgcd-1、gcd-2のラベル、GCD計算部分を抜けた所にafter-gcd-1、after-gcd-2のラベルをつけている状態 レジスタはGCDの計算区間でしか使用しないので共…
ノート プログラムの実行環境についてsubstitution model、environment model、metacircular evaluatorと見て来たが、一番核心の部分はベースのLispシステムに委ねて解説されていない。この章ではプロセッサとそのマシン語に相当するレジスタ・システムをLis…
4.4章のサンプルを動かしたり、問題を解く為に既に写経してあるけど、中身を読んだ訳ではないので。 ノート 4.4.4.1 The Driver Loop and Instantiation ドライバーループは入力がassert!で始まれば事実かルールを保存、そうでなければクエリとして扱う。qev…
ノート 明らかにquery evaluatorは何らかの探索を行う。 一つの方法は非決定論的プログラミングでambを使った実装。もう一つはストリームを使う実装。（ここではストリームで実装する） query systemは大きく分けて二つの操作からなる：パターンマッチと単一…
Nondeterministic Computingで少し雰囲気を感じつつ、ついに論理プログラミングに到達。 第５章はまた毛色が違う話なので、ここが一つの到達点なのかな。 ノート 数学はdeclarative（宣言的）、コンピュータサイエンスはimperative（命令的）。 高級言語にな…
ここで漸く実装部分。 ノート 普通のschemeの式であれば値が返るか、永久に返って来ないか、エラーで止まる。非決定論的schemeではそれに加えて行き止まりに辿り着いた時に選択ポイントまで戻って評価をやり直すと言う動作が追加される。 バックトラックを実…
ノート 非決定論的プログラムの例。 組み合わせ生成とフィルタリングする部分をシステム側に隠す事で、プログラムはより抽象化されて問題をストレートに表現出来る。 Logic Puzzles 『ニコリ』の推理パズル。 プリミティブにequal?を足してmemberを定義。abs…
ここは全く予備知識の無い分野。Prologへの布石の様に思える。 ノート 非決定論的コンピューティング？ 評価器に「automatic search」を組み込む。遅延評価よりも言語に対して大きな変更となる。非決定論的コンピューティングは『生成してテストする』タイプ…
ノート 遅延リストとしてのストリーム。3.5.1節で導入したストリームはdelay、cons-streamと言う構文を使ってストリームを作ったため、ストリームには普通のリスト用の手続きは使えず、ストリーム用の手続きを使う必要があった。 遅延評価のシステムではこれ…
ノート プリミティブは正格のまま複合手続きを非正格として評価器を変更する。 評価を遅らせる手続きの引数はサンク（thunk：脚注にその由来。「考えた」）を作る。サンクを評価する事をフォースすると言う。 名前渡し（call-by-name）は引数をそのまま手続…
ノート 4.2.1 Normal Order and Applicative Order Wikipediaの訳語によると『正規順序と適用順序』。 正規順序は引数を簡約する前に手続きを適用する。適用順序は手続きを適用する前に引数を簡約する。脚注によるとnormal orderとlazy evaluationと言う言葉…
ノート 我々の評価器は評価しながら実行し、評価した結果は残っていないので再帰であっても同じ式であっても何度でも評価するので非効率。 analyzeの結果として実行部としてベースのLispの手続きを返してenvの元で実行する。analyze-sequenceはちょっと複雑…
ノート 内部定義。 テキストの評価器はdefineが出て来る度にその定義を環境に保存するが、それとは違う方法を取る事も出来る。 テキストの例のodd?のスコープは手続きf全体であって、fのスコープのうちodd?が定義されて以降ではない。と言う事はeven?とodd?…
ノート プログラムを電子回路の様に理解する事も可能だし、何だか分からないけど凄い機械と理解しても良いが、評価器は評価器が扱うデータ構造と評価されるプログラムを繋ぐものと捉えられる。 プログラミング言語のユーザーにプログラム内でその言語を評価…
漸く核心の手続き評価部分。 ノート 評価器はプログラムを最終的にプリミティブによるプログラムまで簡約するので、最終的にはプリミティブをベースのLisp上で実行する事になる。最初の環境を用意する。そこには言語として最初から定義されている値やプリミ…
ノート 前節ではスタブで誤摩化していた部分の実装の続き。定義された手続き、変数、環境など。 Testing of predicates 内部で評価する際に使うtrue?とfalse?の定義。 Representing procedures 手続きを実行する部分は4.1.4まで先送り。 ここでは手続きの内…
ノート 式の表現。 式を解釈して要素を取り出す部分と、要素分解された式を評価する部分とは分離する事が出来る。 tagged-list?は特定のシンボルから始まるリストかどうかをチェックする。 definition-variableはexpの第２要素がシンボルであれば基本構文な…
どうも普通の言語（と言うかLisp）では実現されていない、更にそこからはみ出たアイデアについて。 Lispで書くLispインタープリタは『Scheme手習い』で経験済み。 ノート Metalinguistic abstraction -- establishing new languages -- 超言語抽象=新しい言…
