0. ヘッダー

B4 課題発表

A toy scheme interpreter written in scheme

Yuchi Yamaguchi
2025/06/03

作ったもの
1. eta の紹介


🐤 eta


A toy scheme interpreter
written in Scheme

📝 変換とは関係ありません
📝 粘性係数とも関係ありません
📝 学習率でもありません

  

[repo]

eta の機能

✅ 第一級継続

(全体継続, マルチショット)

✅ 末尾再帰最適化

✅ REPL

✅ Stack Trace

center

[1] eta の基本的な機能

[2] eta の実行プロセス

  • Overview
  • 各プロセスと主要なデータ構造

[3] eta の特徴的な実装

  • CPS によるevaluator の実装
  • 末尾再帰最適化の実装
  • call/cc の実装
  • エラー報告
  • REPL の実装

[4] まとめ

2. eta の基本的な機能

2. eta の基本的な機能

文法
1. eta の基本的な機能

定義: https://github.com/abap34/eta/blob/main/devdocs/grammar.md

;; 平方根をニュートン法で求める
(define (sqrt-newton x)
  (define (improve guess) (/ (+ guess (/ x guess)) 2))
  (define (good-enough? guess)　(< (abs (- (* guess guess) x)) 0.0001))
  (define (try guess) 
  (if (good-enough? guess) guess
        (try (improve guess))))
  (try 3.4))

(display (sqrt-newton 2))
基本機能・特殊形式のサポート
1. eta の基本的な機能

基本的な Scheme の機能をサポート.

(例) 再帰

(define (fact n)
    (if (= n 1)
        1
        (* n (fact (- n 1)))))

(display "5! = ")
(display (fact 5))

(例) named-let

(define (fib n)
  (let loop ((i n) (a 0) (b 1))
    (if (= i 0)
        a
        (loop (- i 1) b (+ a b)))))

(display (fib 10))
stdlib
1. eta の基本的な機能

✅ eta 自身で書かれた stdlib も整備

  • io.eta: 入出力
  • logical.eta: 論理演算
  • math.eta: 数学関数
  • list.eta: リスト操作
  • higher-order.eta: 高階関数
  • vector.eta: ベクトル操作
example
1. eta の基本的な機能

examples/alife.eta ... ライフゲームの pulsar パターンを描画するプログラム

デモ

発展的な機能
1. eta の基本的な機能

より (その実装が) 発展的な機能もサポート 👍

✅ REPL

✅ call/cc,

✅ 末尾再帰最適化

✅ Stack Trace など


▶ 実装も含めてあとのセクションで

2. eta の実行プロセス

[2] eta の実行プロセス


  • Overview
  • 各プロセスと主要なデータ構造
Overview of eta
  • 一般的な処理系の構成
  • 開発の歴史的経緯により let*, letrec, cond などは Desugar を使って実現 (後述)
Overview of eta
1. eta の実行プロセス

2 つの実行インターフェース

1. REPL (Read-Eval-Print Loop) ─ (eta コマンドで起動)
2. スクリプト実行 ─ (eta --script <filanem> で filename の中身を実行)

REPL

REPL
(eta)

同じ環境を使い回して
入力・評価・出力を繰り返す

✅ 複数行入力
✅ 便利コマンド

👉 詳細は [3] eta の特徴的な実装

スクリプト実行

スクリプト実行
(eta --script <filename>)

スクリプトを読み込んで実行する.

(どうでもいい話) Desugar or Macro?
2. eta の実行プロセス

例えば cond は 👉 のようなマクロで
実現できる.

⇩

stdlib にこのマクロを入れてしまってサポートしてしまうのもあり

; cond マクロの実装例 (racket)
(define-syntax cond
    (syntax-rules (else)
      ((cond)
       #f)
      ((cond (else expr ...))
       (begin expr ...))
      ((cond (test expr ...) rest ...)
       (if test
           (begin expr ...)
           (cond rest ...)))))
  

(cond
   ((= 1 2) (display "1 is not equal to 2"))
   ((= 1 1) (display "1 is equal to 1"))
   ((= 2 3) (display "2 is not equal to 3")))
Desugar or Macro?
2. eta の実行プロセス

マクロを使うには
マクロを実装する必要がある😦

⇩

最初から衛生的マクロをサポートするつもりだった

⇩

マクロの完成を待つと本格的なプログラムが書けるまで時間がかかりそう

⇩

とりあえず Desugar を使って実装しておいたもの

Overview of eta

というわけで 👉

Tokenize

文字列を Token のリストに変換.

(struct Token (typ val loc))
desc example
typ トークンの種類 'IntToken, 'IdToken
val トークンの値 x, 42, "hello", let, +
loc トークンの位置 (後述) example.eta:(1, 2) - (3, 4)
Parse
1. eta の実行プロセス

Token のリストを Expr ( 位置と eval しやすい用の head がついたリスト) に変換

(struct Expr (head args loc))
desc example
head ノードの種類 'ConstHead, 'IfHead
args 式の引数 (head に応じたリスト) (list name value)
loc 式の位置 (後述) example.eta:(1, 2) - (3, 4) 
; parse.rkt#parse-begin

; Begin ::= (begin Exp*)
(define parse-begin 
  (map-parser
   (sequence
    (label "LParen" lparen)
    (label "begin" (keyword "begin"))
    (label "Exp*"  (zero-or-more (parser-ref parse-exp)))
    (label "RParen" rparen))
    (lambda (result)
      (let ([args (third result)]
            [loc (create-span-location
                  (loc (first result))
                  (loc (last result)))])
        (make-begin loc args)))))
Desugar
2. eta の実行プロセス

Desugar...

Expr を Desugar して単純な形の Expr に変換.

例) and の Desugar処理 ((and a b c) → (if a (if b c #f) #f))

; desugar.rkt#desugar-and-expressions

(define (desugar-and-expressions args loc)
  (make-ifthenelse loc
    (desugar (first args))
    (if (null? (rest (rest args)))
        (desugar (second args))
        (desugar-and-expressions (rest args) loc))
    (make-const loc 'BoolConstNode #f)))
Desugar
2. eta の実行プロセス


Desugar により Expr の head は限られたもののみになる.
これらの評価だけ書けば OK.

; interp.rkt#eval-expr
(define (eval-expr expr env k stack #:tail? [tail? #f])  
  (let ([head (Expr-head expr)])
    (cond
      [(equal? head 'ConstHead)  (eval-const expr env k stack)]
      [(equal? head 'IdHead)     (eval-var expr env k stack)]
      [(equal? head 'AppHead)    (eval-app expr env k stack #:tail? tail?)]
      [(equal? head 'LambdaHead) (eval-lambda expr env k stack)]
      [(equal? head 'QuoteHead)  (eval-quote expr env k stack)]
      [(equal? head 'DefineHead) (eval-define expr env k stack)]
      [(equal? head 'IfHead)     (eval-if expr env k stack #:tail? tail?)]
      [(equal? head 'SetHead)    (eval-set! expr env k stack)]
      [(equal? head 'BodyHead)   (eval-body expr env k stack #:tail? tail?)]
      [(equal? head 'CallCCHead) (eval-call/cc expr env k stack #:tail? tail?)]
      [(equal? head 'LoadHead)   (eval-load expr env k stack #:tail? tail?)])))
Evaluate
1. eta の実行プロセス

Evaluate における主要なデータ構造

  1. Env (環境) (eval/env.rkt)
  2. CallFrame, CallStack (コールスタック) (eval/stack-frame.rkt)
  3. RuntimeValue (実行時の値) (eval/runtime-value.rkt)
Env
2. eta の実行プロセス

(Env frame parent)

✅ 親への参照を持つ ハッシュテーブル.
✅ 親の環境との差分を保持.

(struct Env (frame parent))

(define (env-lookup env name)
  (let loop ([e env])
    (cond
      [(not e)  (make-runtime-error (format "Undefined variable: ~a" name))]
      [(hash-has-key? (Env-frame e) name) (hash-ref (Env-frame e) name)]
      [else (loop (Env-parent e))])))
CallFrame, CallStack
2. eta の実行プロセス

CallFrame

desc
proc 呼び出した手続き
args 実引数
loc call-cite の位置
parent 親のコールフレーム
tail? 末尾呼び出しかどうか

CallStack ... CallFrame のリスト

💡 エラー発生時にStackTrace に変換 👉

; error.rkt#StackTraceEntry
(struct StackTraceEntry (func-name location))

; stack-frame.rkt#call-stack->stack-trace
(define (call-stack->stack-trace stack)
  (if (call-stack-empty? stack)
      '()
      (map (lambda (frame)
             (let ([proc (CallFrame-proc frame)]
                   [loc (CallFrame-loc frame)])
               (make-stack-trace-entry 
                (extract-function-name proc) loc)))
           (CallStack-frames stack))))
RuntimeValue
2. eta の実行プロセス

✅ インタプリタ側で見えている値は
全て RuntimeValue として管理.

✅ タグ付きで 実行時 にいろいろ検査

(struct RuntimeValue (tag value))
desc example
tag 値の種類を表すタグ 'IntTag, 'StringTag
value 実際の値を表す racket のオブジェクト 42, "hello" 
(define (RuntimeValueTag? tag)
  (or (equal? tag 'IntTag)
      (equal? tag 'FloatTag)  
      (equal? tag 'StringTag)
      (equal? tag 'BooleanTag)
      (equal? tag 'NilValueTag)
      (equal? tag 'PairTag)
      (equal? tag 'SymbolTag)
      (equal? tag 'EtaBuiltinTag)
      (equal? tag 'EtaClosureTag)
      (equal? tag 'EtaStructTag)
      (equal? tag 'VectorTag)
      (equal? tag 'VoidTag)
      (equal? tag 'UndefinedTag)
      (equal? tag 'EtaContinuationTag)))
Evaluation の実装
2. eta の実行プロセス

✅ AST を直接評価する方式.

例) 識別子の評価

; interp.rkt#eval-var

(define (eval-var expr env k stack)
  (let* ([var-args (Expr-args expr)]
         [name     (first var-args)]
         [result   (env-lookup env name)])        
    (if (EtaError? result)
        (k (localize-error-location result (Expr-loc expr)) stack)
        (k result stack))))
3. eta の特徴的な実装

[3] eta の特徴的な実装


  • CPS による evaluator の実装
  • call/cc の実装
  • 末尾再帰最適化の実装
  • エラー報告
  • REPL の実装
Evaluation の実装
1. eta の特徴的な実装

eval-* 系の基本的なシグネチャ:

(define (eval-<head> expr env k stack #:tail? [tail? #f])
  ...
  (let ([<args> (Expr-args expr)])
    ...
    (k <result> stack)))
  • expr: 評価する部分式
  • env: 環境
  • stack: コールスタック
  • tail?: 末尾呼び出しかどうか
  • k: 継続
call/cc の実装
3. eta の特徴的な実装


✅ CPS (Continuation-Passing Style) で評価を実装

CPS Evaluation

感激の様子 (https://github.com/abap34/eta/pull/30)

Evaluation の実装
3. eta の特徴的な実装

call/cc の実装すごく簡単に 🙌 ※ (簡略化 ver)

(define (eval-call/cc expr env k stack tail)
  (let ([proc-expr (first (Expr-args expr))]
        [loc (Expr-loc expr)])  
    (eval-expr 
     proc-expr 
     env
     (lambda (proc-value new-stack)
       (if (RuntimeError? proc-value)
           (k proc-value new-stack)
           (let ([reified-cont (make-continuation k new-stack)])
             (apply-proc proc-value (list refied-cont) env k new-stack)
               [else 
                (k (make-error) new-stack)]))))
     stack)))
末尾再帰最適化の実装
3. eta の特徴的な実装

✅ 各評価で末尾かをチェック

例) eval-body-of-body

; interp.rkt#eval-body-of-body

(define (eval-body-of-body expr-list env k stack #:tail? [tail? #f])
  (if (null? expr-list)
      (k ... stack)
      (let loop ([exprs expr-list]
                 ...)
        (if (null? exprs)
            (k (first result) current-stack)
            (let ([is-last-expr? (null? (rest exprs))]) ; <- 末尾かチェック
              (eval-expr ... new-stack)))
                current-stack
                #:tail? (and tail? is-last-expr?)))))))
末尾再帰最適化の実装
3. eta の特徴的な実装

▶︎ 末尾呼び出しなら CallStack に新しく Frame を積まずに置換する

; stack-frame.rkt#call-stack-push
(define (call-stack-push stack frame)
    (cond 
      [(>= (CallStack-current-depth stack) (MAX-STACK-DEPTH))
       (make-runtime-error "Stack overflow: maximum stack depth exceeded")]

      [(and (CallFrame-tail? frame) (not (call-stack-empty? stack)))
       (CallStack (cons frame (cdr (CallStack-frames stack)))
                 (CallStack-current-depth stack))]
      
      [else
       (CallStack (cons frame (CallStack-frames stack))
                  (+ 1 (CallStack-current-depth stack)))]))
末尾再帰最適化の実装
3. eta の特徴的な実装

以下のようなプログラムを実行すると...

(set-max-stack-depth! 90)

(define (fact-with-tco n)
  (define (fact-iter n acc)
    (if (= n 1)
        acc
        (fact-iter (- n 1) (* n acc))))
  (fact-iter n 1))


(define (fact-without-tco n)
    (if (= n 1)
        1
        (* n (fact-without-tco (- n 1)))))
3. eta の特徴的な実装

デモ

エラー報告
3. eta の特徴的な実装

✅ エラー報告に謎のこだわり

エラー報告 ─ overview
3. eta の特徴的な実装

📝 エラーは 3つに分類 (ref: error.rkt)

  1. TokenizeError: トークン化に失敗
    • インタプリタが raise
  2. ParseError: パースに失敗
    • インタプリタが raise
  3. RuntimeError: 実行時エラー
    • インタプリタが raise (例: Stack Overflow, Type Error etc)
    • ユーザが raise (ビルトイン: error)
エラー報告 ─ overview
1. eta の特徴的な実装

どれも

  • type: エラーの種類
  • message: エラーメッセージ
  • location: エラーが発生した場所

を持つ. (+ RuntimeError は stack-trace も持つ)

(struct RuntimeError EtaError (stack-trace))
(struct TokenizeError EtaError ())
(struct ParseError EtaError ())
エラー報告 ─ Location の追跡
3. eta の特徴的な実装

eta では ほぼ全ての※

  • Token
  • Expr
  • *Error
    ...

が Location を持つように実装されている！

; location.rkt#Location
(struct Location (file sline scol eline ecol))

※ 例外的に、eval 関数によって作られる Token, Expr などはダミーの位置情報を保持しています。

エラー報告 ─ Location の追跡
3. eta の特徴的な実装
  1. Tokenize 時に Location を付与
(define (make-token typ val sline scol eline ecol)
  (Token typ val (Location file sline scol eline ecol)))

(define (read-symbol pos line col)
      ...
    (let* ((end (loop pos))
           ...(make-token token-type lexeme 
           line col line (+ col (- end pos)))
              end line (+ col (- end pos))))) 
              ; ^^^ 位置情報を付与
  1. parse 時にも Location を追跡
; App ::= (Exp Exp*)
(define parse-app 
  (map-parser
   (sequence
    (label "LParen" lparen)
    (label "Exp" (parser-ref parse-exp))
    (label "Exp*" (zero-or-more (parser-ref parse-exp)))
    (label "RParen" rparen))
    (lambda (result)
      (let ([op (second result)]
            [args (third result)]
            [loc (create-span-location
                  (loc (first result))
                  (loc (last result)))])
        (make-app loc op args)))))

...

エラー報告

▶︎ 位置情報付きで raise!

; interp.rkt#eval-app
...
(k (make-runtime-error
    (format 
    "Application of non-function: ~a" 
    (RuntimeValue-tag operator-value))
    (Expr-loc operator-expr))
    op-stack)
...
エラー報告 ─ Stack Trace
3. eta の特徴的な実装

✅ RuntimeError に スタックトレースを付与

... エラー時に stack が見えている eval-* がつけてあげる

; interp.rkt#collect-stack-trace-for-error

(define (collect-stack-trace-for-error error stack)
  (if (RuntimeError? error)
      (add-stack-trace-to-error 
        error (call-stack->stack-trace stack))
        error))

同様の仕組み... localize-error-location

エラー報告 ─ Stack Trace

💪 Stack Trace
を表示できるように！

(https://github.com/abap34/eta/pull/43)
REPL の実装

いくらか機能をつけた REPL を実装

✅ multiline input
✅ 各種コマンド

multiline input
3. eta の特徴的な実装

  1. 括弧列が balanced であって
  2. 文字列が閉じられている

ときのみ入力を終了する

; input-reader.rkt

(struct StringState (in-string? escaped?))
(struct ParseState (balance string-state))

(define (input-needs-continuation? input [initial-state (ParseState 0 (StringState #f #f))])
  (let* ([final-state (count-bracket-balance input initial-state)]
         [balance (ParseState-balance final-state)]
         [str-state (ParseState-string-state final-state)]
         [in-string? (StringState-in-string? str-state)])
    (or (> balance 0)     ; Unclosed brackets
        in-string?        ; Unclosed string
        )))
multiline input
  1. 文字列が閉じていないので次の行へ
  2. 空行
  3. 文字列が閉じていないので次の行へ
  4. 文字列は閉じたが
    括弧列が balanced ではないので次の行へ
  5. 括弧列が balanced なので入力終了
感想
5. まとめ・感想
  • たくさん書いたおかげで Scheme への苦手意識がなくなってよかった
  • CPS が謎のまどろっこしいスタイルからお道具箱入りしてよかった
  • 継続を完全に理解できてよかった

![center h:400](img/image-15.png)