━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
課題c (定義と参照)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●目標

        プログラム中で変数の値を 定義・参照 できるようにする．

●課題一覧

        c1 環境の設計と実装
        c2 評価器での環境の利用
        c3 インタプリタの作成
        c4 言語の拡張
        c5 応用プログラムの作成

●注意

        実験時間内に課題が終わらない場合には，次回に持ち越さずに，
        授業以外の時間を使って今回の課題を仕上げておく．

──────────────────────────────────────

●課題cの準備

        キーと値の対応を管理する辞書(あるいは写像)のデータ構造とアルゴリズム
        について調査(復習)して，実装方法についての基礎知識を事前に補っておく．

        言語処理系の作成は，すべて ~/proglang ディレクトリで実施する．

        $ cd ~/proglang/

        必要なら，前回作成したファイルの予備を作る．

        $ cp -r ~/proglang ~/proglang-b

──────────────────────────────────────

●基本課題c1 (環境の設計と実装)

        課題b3では，変数が固定の値をもつ場合の式の評価を扱ったが，この課題では，
        通常のプログラミング言語と同様に，プログラム中で変数の値を定義できる
        ようにする．

        SS言語での定義の例を以下に示す．

        (def year 2020)
        (def days (if (= (% year 4) 0) 366 365))
        (def hours (* days 24))

        この三つの定義の実行後に，year, days, hours を評価すると，それぞれ
        2020, 366, 8784 という値が得られるようにしたい．

        SS言語の処理系では，変数とその値との対応を記憶して，式の評価に利用する．
        この対応のことを環境(environment)という．環境の基本的な機能は，
        (1) 変数の値の登録
        (2) 変数の値の(登録されている場合の)参照
        (3) 環境の表示 (動作確認・デバッグ 用)
        の三つである．

        環境を扱うための，以下のヘッダとプログラムのファイルを ~/proglang/ に保存する．
        ・environment.h (環境の基本操作のヘッダ)
        ・environment.c (環境の基本操作のソース)
        ・c1.c (環境の基本操作の利用例)

        名前と値との対応を管理するための環境のデータ構造を設計し，
        environment.h にその基本操作の仕様を(tree.h 等と同じ形式で)記述せよ．
        また，environment.c に環境の基本操作を実現する関数を定義して，
        この基本操作が正しく動作することをプログラムファイル c1.c で確認せよ．

        値が登録済みの変数に登録しようとする場合や，値が未登録の変数を
        参照しようとする場合の動作も，自分で設計して実装すること．
        今後，必要に応じて，上記の三つの基本機能以外の操作を追加してもよい．

        基本課題のみ実施する場合，値として整数だけを扱えばよい．
        発展課題では，データ式の評価結果が数以外に名前やリストにもなり得るので，
        変数に対応する値としては，評価結果の構文木(へのポインタ)を記憶する．

●基本課題c2 (評価器での環境の利用)

        課題b3で作成した評価器 evaluator.c に手を加えて，変数の値の定義と
        変数の値の参照の機能を実現する．

        (def 名前 式) の形のプログラムが与えられたときには，式の値を評価して，
        変数と評価結果の値との対応を環境に登録するようにせよ．
        ただし，名前がSS言語のキーワード(if, def など特別な意味をもつもの)や
        組み込み関数の名前(+ や not など)の場合にはエラーとすること．

        関数 evaluator() で(変数の)名前を評価するとき，環境に登録された値を
        返すようにせよ．ただし，環境に名前が登録されてない場合にはエラーと
        すること．

        必要に応じて，evaluate() の引き数の与え方や値の返し方を変えてもよい．

        値の定義や参照を利用する SS 言語プログラムの文字列を入力として，
        構文解析後に評価器での値の計算や誤り処理が適切にできるかを，
        プログラムファイル c2.c を使って(必要に応じて加工して)テストせよ．

        ・c2.c (環境の基本操作の利用例)

        基本課題では課題c1で挙げた例以外に，例えば，次のプログラムを試すとよい．

        (def x -100)
        (def y (- x 100))
        (if (< x y) x y)

        また，発展課題b4でリスト処理を実装した場合には，次の例などを試すとよい．

        (def list0 (data (2 4 6 9 11)))
        (def list1 (rest (rest list0)))
        (if (null? list1) (head list1))

●基本課題c3 (インタプリタの作成)

        これまでに作成した言語処理系の機能を統合して，SS言語のプログラムを
        読み込み，解釈・実行するインタプリタ(interpreter)を作成せよ．

        インタプリタのプログラムファイルの名前は ss.c とする．
        実行コマンド ss にファイル名の引き数を指定した場合には，
        SS言語のプログラムをテキストファイル(拡張子は .ss)から読み込んで実行し，
        引き数がない場合にはプログラムをキーボード(標準入力)から受け付けること．
        実行例を以下に示す．

        > (def x -100)
        -100
        > x
        -100
        > (def y (- x 100))
        -200
        > y
        -200
        > (if (< x y) x y)
        -200

        行頭の > は入力の受け付けを表すプロンプトである．
        プログラムをファイルから読む場合には，読んだ行をプロンプトの後に
        表示してから結果を表示し，入力をファイル終端(EOF)まで読んだら
        インタプリタを終了すること．

        ./ss                                    # 標準入出力を利用
        ./ss PROGRAM.ss                         # 入力にファイルを利用

        標準入出力を使う実行ファイルの動作をコマンドで繰り返し確認するには，
        シェルのリダイレクションの機能を使うとよい．標準入出力をファイルに
        切り替えてコマンドを実行できる．

        ./ss < PROGRAM.ss                       # 標準入力にファイルを利用
        ./ss < PROGRAM.ss > RESULT.txt          # 標準出力をファイルに保存
        ./ss < PROGRAM.ss | tee RESULT.txt      # 標準出力をファイルにも保存

        この形式のコマンドを Makefile に指定すれば，自動実行もできる．
        なお，プログラムをリダイレクションにより標準入力から読む場合には，
        キーボードからの入力の場合と同じで，言語処理系側では読んだ行の
        表示処理はしなくてよい．

●発展課題c4 (言語の拡張)

        この課題は必須ではないので，余力のある場合に実施する．

        (fun (名前 名前*) 式) の形の関数定義を扱えるように評価器を拡張せよ．
        この拡張により，例えば次のような関数を定義して使えるようにする．
        上から順に，最小値，階乗，最大公約数，リストの長さ，リストの連結，の
        関数を定義している．
        
        (fun (min x y) (if (< x y) x y)))
        (fun (fact n) (if (= n 0) 1 (* n (fact (- n 1))))))
        (fun (gcd m n) (if (= n 0) m (gcd n (% m n))))
        (fun (length l) (if (null? l) 0 (+ 1 (length (rest l)))))
        (fun (append l1 l2) (if (null? l1) l2 (cons (head l1) (append (rest l1) l2))))

        (do 文* 式) の形の局所定義を使えるように評価器を拡張せよ．

        (fun (ins-sort l) (do (fun (ins a l) (if (null? l) (cons a l) (do (def b (head l)) (if (< a b) (cons a l) (cons b (ins a (rest l))))))) (if (null? l) l (ins (head l) (ins-sort (rest l))))))

        この例では，挿入ソート ins-sort の関数を定義するときにだけ使う
        挿入の補助関数 ins や要素 b を局所的な名前として定義して使っている．

        fun による関数の仮引数や do 内で定義された名前のように，局所変数を
        扱うには，環境に階層的な構造をもたせて，有効な名前を場面に応じて
        適切に切り替える必要がある．

        なお，課題で明示されていない言語仕様については，仕様を適切に定めた上で
        言語処理系を実装すること．

        余力があれば，必要に応じて組み込み関数を追加したり，
        新たな機能を追加したりして，SS言語の機能をさらに拡張せよ．

●応用課題c5 (応用プログラムの作成)

        この課題は必須ではないので，余力のある場合に実施する．

        実験で作成した SS 言語のインタプリタで実行できる，自作の応用プログラムを
        作成せよ．実現した言語機能を十分に活かせる例を作ること．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
実験のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/