読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

SICP 読書ノート#51 - RubyでSchemeインタプリタをつくろう(10) - 導出された式 (pp.213-228)

SICP Scheme Ruby

derived expression(導出された式)や§4.1.1〜4.1.4の練習問題を解いていきます。

問題 4.1

関数適用の際の引数の評価は左から?右から?という問題。

自前の処理では以下のようにoperands.mapとしているので左から。右からとするならイテレーションの順序を入れ替えればよい。

  class Application < Base
    def eval(env)
      procedure = @operator.eval(env)
      arguments = @operands.map { |operand| operand.eval(env) }
      procedure.apply(arguments)
    end
  end

defineによる手続き定義

(define (<var> <p1> .. <pn>)
  <body)

は、

(define <var>
  (lambda (<p1> .. <pn>)
    <body))

の構文シュガーなのでそのように変換させる。

class Generator
  def self.generate(node)

      # snip...

      when "define"
        if operands[0].class == Parser::Node
          variable = self.generate(operands[0])
          value = self.generate(operands[1])
        else
          variable = self.generate(operands[0][0])
          params = operands[0][1..-1].map { |param| self.generate(param) }
          body = operands[1..-1].map { |exp| self.generate(exp) }
          value = SpecialForm::Lambda.new(params, body)
        end
        return SpecialForm::Definition.new(variable, value)

テスト。

[3] pry(main)> repl.run
> (define (fact n)
    (if (< n 1)
      1
      (* n (fact (- n 1)))))
> (fact 5)
=> 120

問題 4.2

a.

Louisの主張は「関数適用(application)をdefineなどの特殊形式(special forms)より前に持ってくれば解釈系の処理効率が上がる」ということだが、そうすると、

  1. 関数適用の際にdefineの名前を持つ手続きを環境から探す
  2. 探してもヒットせず例外が発生

となり上手くいかない。

b.

面倒なので略。

問題 4.3

すでにデータ主導で実装したつもりなので略。

問題 4.4

特殊形式でandとorを実装する。

  class And < Base
    def initialize(predicates)
      @predicates = predicates
    end

    def eval(env)
      if @predicates.empty?
        true
      else
        @predicates.each do |predicate|
          return false if predicate.eval(env) == false
        end
        @predicates.last
      end
    end
  end

  class Or < Base
    def initialize(predicates)
      @predicates = predicates
    end

    def eval(env)
      if @predicates.empty?
        false
      else
        @predicates.each do |predicate|
          return predicate if predicate.eval(env) != false
        end
        @predicates.last
      end
    end
  end

導出された式

特殊形式へ構文変換できる式をderived expressions(導出された式)と呼ぶ。

例えばcondの構文は、

(cond (<p1> <s1>)
      (<p2> <s2>)
      (else <sx>))

以下のifの構文と等価である。

(if <p1>
    <s1>
    (if <p2>
        <s2>
        <sx>))

そこで処理系でも同じような構文変換を行う。

  class Cond
    def initialize(predicates, sequences)
      @clauses = predicates.zip(sequences)
    end

    def eval(env)
      cond_to_if(@clauses).eval(env)
    end

    private
    def cond_to_if(clauses)
      predicate = clauses[0][0]
      sequence = clauses[0][1]

      if predicate == nil
        false
      elsif predicate.name == "else"
        sequence
      else
        SpecialForm::If.new(predicate,
                            sequence,
                            cond_to_if(clauses[1..-1]))
      end
    end
  end

問題 4.5

letからlambdaへの関数適用の形で構文変換できる。

以下のように実装。われながら良いコードだと思う。

  class Let
    def initialize(variables, expressions, body)
      @variables = variables
      @expressions = expressions
      @body = body
    end

    def eval(env)
      let_to_combination().eval(env)
    end

    private
    def let_to_combination()
      SpecialForm::Application.new(SpecialForm::Lambda.new(@variables, @body),
                                   @expressions)
    end
  end

テスト。一発で動いてちょっと感動。

[3] pry(main)> repl.run
> (let ((x 1) (y 2)) (+ x y))
=> 3
> (let ((addone (lambda (n) (+ n 1))))
    (addone 5))
=> 6

ただし、factのbodyの環境からはfactが見えないので再帰はできない。

> (let ((fact (lambda (n)
        (if (< n 1) 1 (* n (fact (- n 1)))))))
    (fact 5))
"lookup_variable_value: unbound variable; fact"

問題 4.6

condの(<test>=><recipient>)の仕様について。使いどころがよくわからないのでスキップ。

問題 4.7

(let* ((<v1> <e1>)
       (<v2> <e2>)
       (<v3> <e3>))
  <body>)

は、

(let ((<v1> <e1>))
  (let ((<v2> <e2>))
    (let ((<v3> <e3>))
       <body>)))

と等価であるため、以下のようになる。

module DerivedExp
  class LetAster
    def initialize(variables, expressions, body)
      @clauses = variables.zip(expressions)
      @body = body
    end

    def eval(env)
      let_aster_to_nested_let(@clauses).eval(env)
    end

    private
    def let_aster_to_nested_let(clauses)
      if clauses.empty?
        @body
      else
        variable = clauses[0][0]
        expression = clauses[0][1]
        DerivedExp::Let.new([variable],
                            [expression],
                            let_aster_to_nested_let(clauses[1..-1]))
      end
    end
  end
end

また、Let#new()の引数bodyに対して配列を渡せないためeval_sequenceの修正も必要。(このデバッグが結構大変だった…)

    def eval_sequence(seq, env)
      if seq.class == Array
        seq.map { |exp| exp.eval(env) }.last
      else
        seq.eval(env) ## 追加
      end
    end

問題 4.8

named letの実装。

(let <name> ((<v1> <e1>)
             (<v2> <e2>)
             (<v3> <e3>))
  <body>)

は、

(begin
  (define <name> (lambda (<v1> <v2> <v3>) <body>)
  (<name> <e1> <e2> <e3>)))

と等価であるので、letを以下のように拡張した。

  class Let
    def initialize(name, variables, expressions, body)
      @name = name
      @variables = variables
      @expressions = expressions
      @body = body
    end

    def eval(env)
      let_to_combination().eval(env)
    end

    private
    def let_to_combination()
      if @name != nil
        SpecialForm::Begin.new(
          [SpecialForm::Definition.new(@name,
                                       SpecialForm::Lambda.new(@variables, @body)),
           SpecialForm::Application.new(@name, @expressions)])
      else
        SpecialForm::Application.new(SpecialForm::Lambda.new(@variables, @body),
                                     @expressions)
      end
    end
  end

テスト。

> (define (fib n)
    (let fib-iter ((a 1)
        (b 0)
        (count n))
      (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))
> fib(10)
=> 55

問題 4.9

いちばん簡単そうなwhileを実装する。

問題4.8のnamed letを使うことで

(while <predicate>
  <body>)

は、

(let loop ()
  (if <predicate>
      (begin
        <body>
        (loop))
      false))

に変換可能なので、derived expressionとして実装できる。

  class While
    def initialize(predicate, body)
      @predicate = predicate
      @body = body
    end

    def eval(env)
      while_to_named_let().eval(env)
    end

    private
    def while_to_named_let()
      DerivedExp::Let.new(Builtin::Variable.new("loop"),
                          [],
                          [],
                          SpecialForm::If.new(
                            @predicate,
                            SpecialForm::Begin.new(
                              @body + [SpecialForm::Application.new(
                                        Builtin::Variable.new("loop"),
                                        [])]
                            ),
                            Builtin::Variable.new("false")))
    end
  end

テスト。

> (define i 0)
> (while (< i 5)
    (print i)
    (set! i (+ i 1)))
1
2
3
4
=> false
> i
=> 5

問題 4.10

新しい構文の設計で考えられるのは、

  • 中間記法を使う
  • S-Expressionから、PythonのようにI-Expressinにする

自前の処理系はすでに構文解析と評価を分離したので、構文解析さえ修正すればできそう。でも面倒なので略。

問題 4.11

Hashテーブル使えって話だよね。§3.3.3で出てきたのでそれを使えばいいと思う。

自前の処理系は最初からHashで実装しているので特になし。

問題 4.12

内部手続きscan()を共通化できる。

自前の処理系はすでにframes.eachで走査させていて、これ以上共通化しても過剰かなと思うので略。

問題 4.13

束縛する側のdefineがそうであるようにunbind!も最初のフレームからだけでいいんじゃないのかな。実装はスキップします。

問題 4.14

Evaはユーザー関数としてmapを定義した模様。真っ当だと思う。

Louisは基本手続きとしてどう組み込んだかよくわからないけど、動作がおかしいのはmapが処理系のmapとしてではなく被実装言語側のSchemeのmapとして動いちゃったとかかな?

よくわからないのでググったら以下のような理由らしい。

Louis Reasoner の方法で実行した場合

;; (primitive-proceduresにmap手続きを追加しておく)
(map (lambda (x) x) '(1 2 3 4 5))

; *** ERROR: invalid application: ((procedure (x) (x) (((false true car cdr cons null? map) #f #t (primitive #<subr car>) (primitive #<subr cdr>) (primitive #<subr cons>) (primitive #<subr null?>) (primitive #<subr map>)))) 1)
; Stack Trace:
; _______________________________________
;   0  (eval input the-global-environment)
;         At line 491 of "C:/home/tmurata/scheme/4.Z.scm"

となる。

基盤Lispのmapからは第一引数が手続きでなく通常のリストに見えているため、うまくいっていない。(手続きの先頭に'procedureというタグが付いているため)

自前の処理系ではどうなるかprimitive procedureとして組み込んでみた。

  class Map
    def self.apply(arguments)
      if arguments.length < 2
        raise "map: airty mistatch; " + arguments.to_s
      end
      proc = arguments[0]
      lists = arguments[1..-1]
      self.iter(proc, lists)
    end

    private
    def self.iter(proc, lists)
      if lists[0] == nil
        nil
      else
        firsts = lists.map { |list| list.car }
        rests = lists.map { |list| list.cdr }
        Builtin::Pair.new(proc.apply(firsts),
                          self.iter(proc, rests))
      end
    end

テスト。特に問題なく動いた。

> (map + (list 1 2 3))
=> (1 2 3)
> (map + (list 1 2 3) (list 4 5 6) (list 7 8 9))
=> (12 15 18)
> (map cons (list 1 2 3) (list 4 5 6))
=> ((1 . 4) (2 . 5) (3 . 6))

そろそろ次に進みたいけど、自前の処理系のquoteのバグが取れずに苦戦中。。。


※「SICP読書ノート」の目次はこちら