PLAI by Shriram Krishnamurthiを5章まで読んだ

「Programming Languages: Application and Interpretation by Shriram Krishnamurthi」というPDFを読んでいます。http://cs.brown.edu/~sk/Publications/Books/ProgLangs/
これは、言語処理系に関する本のようです。インターネットで調べたところCPS変換についても詳しく書かれているようです。

使用するプログラミング環境はRacketで、言語はplai-typedという型付きのSchemeのような言語です。本の題名を略すとPLAIとなるので、そこから名付けているのだと思います。LISPの基本が理解できれば、読んでいくうちにわかるので、plai-typedについての知識は全く必要ありません。

わかりやすい英語で書かれていて、英語の苦手な僕でも、辞書を引きながら読み進むことができています。普段、英語をあまり読まないので、とても勉強になっています。

5章までで、以下の簡単なインタープリタを作成します。

#lang plai-typed

(define-type ExprC
  [numC (n : number)]
  [idC (s : symbol)]
  [appC (fun : symbol) (arg : ExprC)]
  [plusC (l : ExprC) (r : ExprC)]
  [multC (l : ExprC) (r : ExprC)])

(define-type FunDefC
  [fdC (name : symbol) (arg : symbol) (body : ExprC)])

(define (subst [what : ExprC] [for : symbol] [in : ExprC]) : ExprC
  (type-case ExprC in
    [numC (n) in]
    [idC (s) (cond
               [(symbol=? s for) what]
               [else in])]
    [appC (f a) (appC f (subst what for a))]
    [plusC (l r) (plusC (subst what for l) (subst what for r))]
    [multC (l r) (multC (subst what for l) (subst what for r))]))

(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefC
  (cond
    [(empty? fds) (error 'get-fundef "reference to undefined function")]
    [(cons? fds) (cond
                   [(equal? n (fdC-name (first fds))) (first fds)]
                   [else (get-fundef n (rest fds))])]))

(define (interp [e : ExprC] [fds : (listof FunDefC)]) : number
  (type-case ExprC e
    [numC (n) n]
    [idC (_) (error 'interp "shouldn't get here")]
    [appC (f a) (local ([define fd (get-fundef f fds)])
                  (interp (subst a
                                 (fdC-arg fd)
                                 (fdC-body fd))
                          fds))]
    [plusC (l r) (+ (interp l fds) (interp r fds))]
    [multC (l r) (* (interp l fds) (interp r fds))]))

以下のように実行します。

> (define double (fdC 'double 'x (plusC (idC 'x) (idC 'x))))
> (interp (appC 'double (numC 3)) (list double))
- number
6