2010.txt

From: Takuo Watanabe <takuo@cs.titech.ac.jp>
To: announce@psg.cs.titech.ac.jp
Date: Thu, 15 Apr 2010 16:32:43 +0900
Subject: Programming Project for Newcomers (2010)
--

Folks

Here is the description of programming project for newcomers.
(written in Japanese, sorry)

新4年生むけに毎年行っているプログラミングプロジェクトの案内です．
もちろんM1以上の人が参加してもかまいません．


問題：Scheme（サブセット）のインタプリタを作成してください．
作成する Scheme の文法と，最低限用意する関数を以下に挙げます．

記述言語は Scheme を含む任意の言語とします．
構文解析をしなくてよいのでSchemeを使うのが簡単でしょう．

今年のハイライト: (1)マクロ機能の実装と(2)末尾呼び出しの最適化

(1)マクロ機能
今回実装してもらうマクロ機能では，マクロは以下のように定義します．

(define-macro (positive x)
 (list '> x 0))

プログラム中に (positive e) という式が出てきた場合，これが
(list '> e 0) の実行結果で置き換えられ（これを「マクロが展開される」
といいます），その後で式の評価が行われます．例えば
    (if (positive (+ (g x) 1)) (foo) (bar))
という式の場合，まずマクロが展開されて
    (if (> (+ (g x) 1) 0) (foo) (bar))
という形の式が得られて，それからこの式が評価されます．

次に，以下のような関数定義との違いについて説明しておきます．

(define (positive x)
 (> x 0))

関数定義の場合は，(positive e) という式を評価する場合は，まず
eを評価して，その結果の値が関数 positive の引数になります．一方
もしこれがマクロなら，e は評価されずに (> e 0) という形の式に
展開され，それから展開後の式が評価されます．

引数を評価しなくてすむので，関数定義と違って以下のような定義も
可能です．

(define (let*-expander vars body)
 (if (null? vars)
     (cons 'begin body)
     (list 'let (list (car vars)) (let*-expander (cdr vars) body))))

(define-macro (let* vars . body)
 (let*-expander vars body))

これは let を使って let* を定義した例です．このようにマクロを
使うことで，さまざまな構文をユーザが自分で定義することができます．

Schemeには define-syntax (let-syntax) というマクロ定義機構がありますが，
これは展開の前後で変数名がぶつからないようにする hygienic マクロと呼ばれる
もので，ちょっと実装は難しいと思います．今回実装してもらうのは Common-Lisp
風のマクロです．ちなみにCommon-Lispだと上の例は以下のようになります．

(defun let*-expander (vars body)
 (if (null vars)
     (cons 'begin body)
     (list 'let (list (car vars)) (let*-expander (cdr vars) body))))

(defmacro let* (vars &rest body)
 (let*-expander vars body))


(2)末尾呼び出しの最適化
末尾呼び出しの最適化(Tail Call Optimization, TCO)とは，関数本体の
末尾の位置(tail position)に関数呼び出しがある場合，コールスタックを
消費せずにその呼び出された関数に制御を移すことです．例えば

(define (even? x)
 (if (= x 0) #t (odd? (- x 1))))
(define (odd? x)
 (if (= x 1) #t (even? (- x 1))))

のような関数 even?, odd? の場合，0以上の引数に対しスタックオーバー
フローを起こさずに計算できなくてはなりません．


ほかの要件は以下の２つです．
・構文に合致しない入力はエラーとすること．
・実行時エラーによってインタプリタが停止してしまわないように
  すること(できる範囲で)．

Schemeで実装する場合は，作成したインタプリタ上で作成したインタ
プリタが実行できるようにするとなお結構です．

期間は約１ヶ月とします．できあがったらゼミの時間にデモをして
もらいます．

A. 文法

非終端記号:
       大文字[A-Z]で始まる名前

終端記号:
       開き括弧 (
       閉じ括弧 )
       ピリオド .
       小文字[a-z]で構成される名前
       シングルクオート ' で囲まれた文字列

X*  要素Xの0個以上のくりかえし
X+  要素Xの1個以上のくりかえし
[X] 要素Xは高々1個

Toplevel ::= Exp
           | Define
           | (define-macro (Id Id* [. Id]) Body)
           | (load String)                      ファイルの内容を読み込む

Define ::= (define Id Exp)
         | (define (Id Id* [. Id]) Body)

Exp ::= Const                                   定数
      | Id                                      変数
      | (lambda Arg Body)                       λ抽象
      | (Exp Exp*)                              関数適用
      | (quote S-Exp)                           クオート (注1)
      | (set! Id Exp)                           代入
      | (let [Id] Bindings Body)                let
      | (letrec Bindings Body)                  letrec
      | (if Exp Exp [Exp])                      条件式(if)
      | (begin Exp*)                            逐次実行
      | (while Exp Exp*)                        whileループ



Body ::= Define* Exp+

Arg ::= Id
      | (Id* [Id . Id])

Bindings ::= ((Id Exp)*)

S-Exp ::= Const
        | Id
        | (S-Exp* [S-Exp . S-Exp])

Const ::= Num
        | Bool
        | String
        | ()

Num: 最低限10進整数はサポートすること

Bool ::= '#t'
       | '#f'

String: ダブルクオートで囲まれた文字列 (注1)

Id ::= [0-9A-Za-z!$%&*+-./<=>?@^_]+   (注3)

(注1) (quote X) だけでなく 'X という記法もサポートすること．
(注2) バックスラッシュ \ によるエスケープをサポートすること．
(注3) 数値となるものをのぞくこと．


B. 関数（最低限）

整数
 number?, +, -, *, /, =, <, <=, >, >=

リスト
 null?, pair?, list?, symbol?,
 car, cdr, cons, list, length, memq, last, append,
 set-car!, set-cdr!

ブール値
 boolean?, not

文字列
 string?, string-append,
 symbol->string, string->symbol, string->number, number->string

関数
 procedure?

比較
 eq?, neq?, equal?

シンボル生成用関数

 gensym : 0個の引数をとり，新しいシンボルを返す．マクロを定義する際に
          新しい変数が導入されることがあるが，そのとき既存の式の変数名と
          衝突しないようにするために用いられる．


C. マクロ: 以下は define-macro を使って定義すること．

  (let* Bindings Body)                       (注4)
  (cond (Exp Exp+)* [(else Exp+)])           (注5)
  (and Exp*)
  (or Exp*)
  (do ((Id Exp Exp)*) (Exp Exp*) Body)
  (do* ((Id Exp Exp)*) (Exp Exp*) Body)

(注4) let* は let の0個以上の繰り返しではなく let* という名前である．
(注5) 節は(else節を含めて)最低1個はあること．else節は高々1個とすること．

以上．