Scheme演習 第6回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治
[Table of Contents] [Index] [携帯版]

インタプリタとは
  • インタプリタとは、ある言語で書かれた式を受け取り、決められた意味に従ってその式を評価するプログラムである。
(define (tashizan-interpreter)
  (define (base-eval exp)
    (cond ((number? exp) exp)
          ((and (pair? exp) (eq? (car exp) 'tashizan))
             (+ (base-eval (cadr exp)) (base-eval (caddr exp))))
          (else "syntax error")))
  (display " ")
  (let ((answer (base-eval (read))))  ; ここで入力待ち
    (display "= ")
    (write answer))
  (newline)
  (tashizan-interpreter))
> (tashizan-interpreter)
 (tashizan 1 (tashizan 2 3))
= 6
 (+ 1 2)
= "syntax error"
  • tashizan-interpreter は、数字とシンボルtashizan を言語として使って書かれた式を受け取り、tashizan は数値の和を意味するとして計算をしてくれるインタプリタである
  • tashizan-interpreter 自身は Scheme で書かれており、このように通常はインタプリタが読む言語と、インタプリタ自身が書かれている言語は異なる
  • そこで最終回の今回は、Scheme を読むインタプリタが Scheme 自身ではどのように書くことができるかを見る
  • このような自分自身の言語で書かれたインタプリタのことをmetacircular インタプリタという
  • Scheme は、扱うデータ(リスト)とプログラムが同じ格好をしているので、左解析などの細かいことを気にせずに、インタプリタの枠組を理解することができる

トップレベルループ
  • インタプリタを走らせるのは、トップレベルの read-eval-print ループである
(define (REP-loop)
  (display "input  > ")
  (let ((answer (base-eval (read) init-env)))
    (display "output : ")
    (write answer))
  (newline)
  (REP-loop))
> (REP-loop)
input  > (+ 1 2)
output : 3
input  >
  • インタプリタの本体、入力された式を評価するのが次の base-eval である。
  • インタプリタを聞関数の名前としては普通 eval が良く使われるが eval という関数は元々存在しているので、ここでは base-eval という名前になっている

dispatcher
  • base-evalは入力された式の種類に応じて dispatch を行なう。
  • load はシンタックス形式ではないが、特殊な処理なので独自に評価する
(define (base-eval exp env)
  (cond ((number? exp)           exp)
        ((boolean? exp)          exp)
        ((string? exp)           exp)
        ((symbol? exp)           (eval-var exp env))    ; 3 節
        ((eq? (car exp) 'define) (eval-define exp env)) ; 3 節
        ((eq? (car exp) 'lambda) (eval-lambda exp env)) ; 3 節
        ((eq? (car exp) 'set!)   (eval-set! exp env))   ; 3 節
        ((eq? (car exp) 'quote)  (eval-quote exp env))  ; 3 節
        ((eq? (car exp) 'if)     (eval-if exp env))     ; 3 節
        ((eq? (car exp) 'load)   (eval-load exp env))   ; 5 節
        (else (eval-application exp env))))             ; 4 節

シンタックス形式
  • 以下に、変数の評価と各種シンタックス形式の処理関数をあげる
  • トップレベルの初期環境は init-env である
  • これを直接扱うインターフェースget 、define-value! 、set!-value! は前回までの課題で作成したものを使用すればよい
  • ただし、自分で作った補助関数で、今回すでに定義されている関数と同じ名前のものがあった場合には、名前を変更しておくこと
(define init-env (list (list
  (cons 'car      (list *primitive* 'car))
  (cons 'cdr      (list *primitive* 'cdr))
  ...
)))

*primitive*と*lambda*
  • *primitive* と *lambda* は、特殊な唯一の値として用いられるポインタである
(define *lambda* (list 'lambda))
(define *primitive* (list 'primitive))

変数
  • 変数は、get で環境からペアを取り出して cdr 部分の値を返す
    • その変数が宣言されていなければエラーである
(define (eval-var exp env) ; exp = var
  (let ((pair (get exp env)))
    (if (pair? pair)
        (cdr pair)
        (error (list 'eval-var: 'unbound 'variable: exp)))))

define
  • define 文は、define-value! で現在の環境の最外フレームに新しい変数を宣言する。
(define (eval-define exp env) ; exp = (define var body)
  (let* ((var (cadr exp))
         (body (caddr exp))
         (value (base-eval body env)))
    (define-value! var value env) ; env の最外フレームに(var . value)を加える。
    var))

lambda
  • lambda 関数は、そのパラメタ、本体、及びそのときの環境をひとまとめにして返す
  • これは第4回のλ-closure にあたる
    (ただし、そのときの簡易的な実装とは違い、*lambda*は唯一のポインタである)
  • この環境が、この関数の lexical scoping を与える環境である
  • ここでは本体を評価していないことに注意。
(define (eval-lambda exp env) ; exp = (lambda params body)
  (let ((params (cadr exp))
        (body   (caddr exp)))
    (list *lambda* params body env)))
input  > (lambda (x) (+ x 1))
output : ((lambda) (x) (+ x 1) (((car (primitive) car)...

set!
  • set! は set!-value! で現在の環境を最外フレーム以外も探索して、変数の値を上書きする
  • こちらは変数が宣言されていなければdefineとみなされる。
(define (eval-set! exp env) ; exp = (set! var body)
  (let* ((var (cadr exp))
         (body (caddr exp))
         (value (base-eval body env)))
    (set!-value! var value env))) ; env の var を value に書き換える。

quote
  • quote は、quote された式を評価せずにそのまま結果として返す
(define (eval-quote exp env) ; exp = 'body = (quote body)
  (cadr exp))
input  > '(+ 1 2)
output : (+ 1 2)
input  > (+ 1 2)
output : 3

if
  • if 文は、まず条件部を評価し、その結果に従って then 部分、あるいは else 部分を評価する
(define (eval-if exp env) ; exp = (if pred-part then-part else-part)
  (let ((pred-part (cadr exp))
        (then-part (caddr exp))
        (else-part (cadddr exp)))
    (if (base-eval pred-part env)
        (base-eval then-part env)
        (base-eval else-part env))))

関数適用
  • シンタックス形式と違って、関数適用の場合は、まず引数をすべて評価する
  • 関数も base-eval に与えられるが、そこで返されるのは *primitive* あるいは *lambda* というポインタのついた式であり、その本体部分は評価されていない
  • 引数の評価が終わったら、base-apply を呼んでその関数部分を引数部分に対して適用する
(define (eval-application exp env) ; exp = (f a b c ...)
  (let ((lst (map (lambda (e) (base-eval e env)) exp)))
    (base-apply (car lst) (cdr lst))))

関数の種類
  • base-apply で適用される関数には
    • car や cdr といった primitive 関数
    • ユーザが defineやlambda を使って定義した関数
    の2種類がある

primitive関数
  • primitive 関数は、あらかじめ init-env 中に作られており、*primitive* というポインタで primitive であることを判別している。
  • 適用される関数が primitive 関数の場合は、そのまま所定の処理が行なわれる。
  • これが、その言語の処理できる基本的な語彙を与えることになる。
input  > (car '(1 2))
...
| > (base-apply '((primitive) car) '((1 2)))
...
output : 1

ユーザ定義関数
  • 一方、適用される関数がユーザ定義の関数の場合には、その関数の本体をbase-eval を使って再帰的に評価していくことになる
  • その際、局所フレームを作成し、パラメタの値を実際に与えられた引数で束縛 (bind) してから評価を行なう
  • extend は前回までの課題で作成したものを使用すればよい
input  > ((lambda (x) (+ x 1)) 2)
...
| > (base-apply '((lambda) (x) (+ x 1) (((car (primitive) car) (cdr (primiti...
...
| > (base-eval '(+ x 1) '(((x . 2)) ((car (primitive) car) (cdr (primitive) ...
...
| > (base-apply '((primitive) +) '(2 1))
...
output : 3

base-apply
(define (base-apply operator operand)
  (cond ((and (pair? operator) ; <============== primitive はここ
              (eq? (car operator) *primitive*))
         (let ((name (cadr operator)))
           (cond ((eq? name 'car)        (car (car operand)))
                 ((eq? name 'cdr)        (cdr (car operand)))
                 ((eq? name 'cadr)       (cadr (car operand)))
                 ((eq? name 'caddr)      (caddr (car operand)))
                 ((eq? name 'cadddr)     (cadddr (car operand)))
                 ((eq? name 'cons)       (cons (car operand)
                                               (cadr operand)))
                 ((eq? name 'list)       operand)
                 ...
                 (else
                  (error (list 'base-apply: 'unknown 'primitive: name))))))
        ((and (pair? operator) ; <============== lambda はここ
              (eq? (car operator) *lambda*))
         (let ((lambda-params (cadr operator))
               (lambda-body   (caddr operator))
               (lambda-env    (cadddr operator)))
           (base-eval lambda-body
                      (extend lambda-env lambda-params operand)))); 環境を拡張
        (else
         (error (list 'base-apply: 'not 'a 'function: operator)))))

Load
  • 詳細は省略するが、この実装ではファイル名の拡張子scmは省略できないことに注意
(define (eval-load exp env) ; exp = (load filename)
  (define port (open-input-file (cadr exp)))
  (define (load-local)
    (let ((input (read port)))
      (if (eof-object? input)
          (begin (close-input-port port) 'done)
          (begin (base-eval input env)
                 (load-local)))))
  (load-local))

レポート課題6

問1
  • 今回のインタプリタ(プログラム全体は 6.scm を参照)の REP-loop やbase-eval などを改良し、(exit) でインタプリタを終了できるようにせよ
    • ただし、同時に Gambit Scheme をも終了したりはしないこと

問2
  • インタプリタのプロンプトに対して (lambda (x) x) などと入力すると、結果として環境まで一緒に表示されてしまう。
    環境は時に circular にもなったりするので、これは問題である
  • REP-loop を書き換えて、λclosure だったら、その環境部分は表示しないようにせよ。

問3
  • 今の段階では、
(define f (lambda (x) (cons x x)))
    の形の宣言は受け付けてくれるが、
(define (f x) (cons x x))
    は受け付けてくれない
  • eval-define を拡張して、この形の宣言も受けとれるようにせよ

問4
(let ((a1 e1) (a2 e2) ... (an en)) body)
は、
((lambda (a1 a2 ... an) body) e1 e2 ... en)
と等価である
  • そこで、base-eval に eval-let への dispatch を加えるとともに eval-let を作り、let 文をサポートせよ

問5
  • begin 文をサポートせよ
  • また、これを使って、define文やlambda文や let 文の body 部に、式の列を書けるようにせよ

問6(成績に考慮しない)
  • インタプリタ中で使用されている関数 error が実際に呼び出されると、インタプリタは終了してしまう。
    そこで、そのようなエラーが出たときは何のエラーが出たかを表示するとともに、返り値を入力できるようにせよ。
    • 1引数を受け取る関数 error 自体を再定義するだけでできる
input  > (define (f x) (* x x))
output : f
input  > (f y)
(eval-var: unbound variable: y)
input return value > 3
output : 9
input  > (+ 1 (2 3))
(base-apply: not a function: 2)
input return value > 5
output : 6

問7(成績に考慮しない)
  • このインタプリタに、このインタプリタ自体を読み込めるようにせよ
    • 具体的には、eval-cond、eval-let*、eval-map、eval-and、eval-orなど、インタプリタ内で使用したすべてのシンタックス形式をサポートし、primitive 関数は init-envとbase-applyに追加する
      • eval-and、eval-orは引数の数が可変個であることと、引数の評価の途中で返り値が#tあるいは#fに決定したら、残りの引数の評価をしないことに注意せよ
  • その上で、実際に何かプログラムを走らせ、gsi 上で実行した場合と、インタプリタを1段入れた場合、2段入れた場合で、どのくらい実行時間に差が出るかを試してみよ(timeは使わなくても良い)


This page is generated by mtd2html.