SICP 5.5.7 Interfacing Compiled Code to the Evaluator / Exercise 5.52

ノート

Exercise 5.52

C言語でShemeコンパイラを作れと言っているのではなく、この章のコンパイラをCのプログラムを吐く様に改造せよと言っている。
ここでもswiftを使う事にする。

直ぐに気づく問題点は

レジスタマシンやアセンブラのレベルに変換する訳ではないのでプログラムの構造は殆どそのまま変換すれば良い
と言う事は「使うレジスタ」とか「値を保存するレジスタ」とかの指定はおそらく不要。リンケージは要る。
識別子（シンボル）：Schemeでは-とか!とかを識別子の一部に使えるけど、大抵の他の言語では使えないので変換する必要がある。
コンパイラの出力形態：データとしてはリストしか持てないので、おそらくシンボルのリストを作って、最終段で文字列にへ関して出力する事になる。

まずは、Metacircular Evaluatorを手で、しかも極力機械的に変換して、更に補助的な関数を色々と加えて動く所まで持って行く。

実際に作業するにして変換に必要だった作業は以下の通り：

Schemeの変数には型がないので環境も含めて全ての値は一つのデータ型で表す
condはcond->ifでifの連続に変換してコンパイルする
関数名の?は"p"に変換
関数名の->は"_to_"に変換
関数名の!は削除する
関数名が予約後の場合には後ろに"_"を追加
関数の引数は全てExpression型、関数値も全てExpresion型（Ex 5.51のResult型のエラーはExpressionで表現）
defineは変数の定義と関数の定義を別に扱う必要がある。swiftでクロージャーが自分自身を参照出来ないため。
'()はExpression.LIST([])
リンケージがreturnの場合はreturn
シンボル'ok / 'quoteはExpression.SYMBOL("ok")などに変換
true / falseはExpression.BOOLEAN(true) / Expression.BOOLEAN(false)に変換
letはそのままswiftのletを使う
ifをそのままswiftのifに変換すると、predicateの部分はExpression型では駄目でBoolにする必要がある。?が付く手続きの戻り値の型を常にBoolとする約束にする事も出来るが、swfitのifの条件式は常にExpression.BOOLEAN(true)と同じかをチェックするコードを吐く事にする。
環境とプリミティブとの橋渡しは実行環境の一部なのでコンパイルの対象とはしない。

関数の定義はクロージャが自分自身を参照出来ないので以下の様なスタイルにする。これだと関数内の関数も問題なく動作する。

var func1: (Int -> Int) = {n in return 0}
func1 = {n in
    var inner: (Int -> Int) = {n in return 0}
    inner = {n in
        if n > 1 {
            return n * inner(n - 1)
        } else {
            return n
        }
    }
    
    return inner(n)
}

func1(6)

また、swiftでは後方で定義される関数や変数を参照出来ないので、クロージャをバインドする変数を最初に全て定義してしまってから、クロージャをバインドし直す形にする。
mutableのリストが作れないので、環境だけはExercise 5.51と同様に環境オブジェクトを使うプリミティブを用意する。

とりあえず動かす事は出来た。こんな感じ。

;;; M-Eval input: (define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
;;; M-Eval value: 
ok
;;; M-Eval input: (factorial 6)
;;; M-Eval value: 
720
;;; M-Eval input:

次に、これと同じコードを吐き出す様にコンパイラを改造する。

元のレジスタマシンはS式がそのままプログラムだったが、swiftにする為には文字列にして、最後に連結して出力する事にする。

(define (print-result instructions)
  (for-each (lambda (s) (if (pair? s)
                            (print-result s)
                            (display s))) instructions))

【target】
これは要らない。

【linkage】
gotoでジャンプする事は無いので、'nextならただ式を吐き出す、'returnなら「return 式」と言う文を吐き出す。compile-linkageは不要で、end-with-linkageをシンプルに以下の様にする。

(define (end-with-linkage linkage instruction-sequence)
  (if (eq? linkage 'return)
      (list "return " insruction-sequence)
      instruction-sequence))

【self-evaluating】
Metacircular Evaluatorには数値のリテラルは出て来ず、文字列しか出て来ない。例えばevalの最後のerrorの呼び出しは

(error "Unknown expression type -- EVAL" exp)

これを

error("Unknown expression type -- EVAL", exp)

こう変換したい。文字列をdisplayすると文字列の中身だけになってしまうので文字列リテラルにする必要がある。一方数値はそのまま出力すれば良いのでcompile-numberとcompile-stringに分割して、self-evaluating?を呼び出す部分もnumber?とstring?に分割する。

(define (compile-number exp linkage)
  (end-with-linkage linkage (list exp)))

(define (compile-string exp linkage)
  (end-with-linkage linkage (list "\"" exp "\"")))

【quoted】
Metacircular Evaluatorのコードに登場するquote（シンボルかquoteされたリスト）は'okとか'quoteとか'lambdaとか。

'ok

は

Expression.SYMBOL("ok")

だし

(tagged-list? exp 'quote)

は

tagged_list_p(exp, Expression.SYMBOL("quote"))

と変換したので、一つのシンボルであればそのままExpressionにする。リストであればシンボルのリストに変換する。

(define (compile-symbol exp)
  (list "Expression.SYMBOL(\"" exp "\")"))

(define (compile-list l)
  (cond ((symbol? l) (compile-symbol l))
        ((not (null? l)) (list "Expression.LIST([" (add-between (map compile-list l) ",") "])"))
        (else (list "Expression.LIST([])"))))

(define (compile-quoted exp linkage)
  (end-with-linkage linkage (compile-list (text-of-quotation exp))))

【variable】
Metacircular Evaluatorのプログラムの変数あるいは手続き名。手作業コンパイルの時と同様に変換しなければならない。
変数名は定義している部分と参照している部分があり、evalを通るのは参照している側だけなので、compile-variableと名前を変換する手続きは分離する。

(define (generate-identifier sym)
  (define (replace str)
    (cond ((equal? str "var") "var_")
          ((equal? str "operator") "operator_")
          ((equal? str "true") "true_")
          ((equal? str "false") "false_")
          (else
           (let ((lst (string->list str)))
             (list->string (map (lambda (c) 
                                  (cond ((equal? c #\-) #\_)
                                        ((equal? c #\?) #\p)
                                        ((equal? c #\!) #\b)
                                        ((equal? c #\>) #\_)
                                        (else c))) lst))
             ))))
  (string->symbol (replace (symbol->string sym))))

(define (compile-variable exp linkage)
  (end-with-linkage linkage (list (generate-identifier exp))))

この手続きの都合（mapを使っているので一文字を一文字にしか変換できない）により->は__、!はbに、?はpに変換する事にする。

Racketではtrueとfalseは予約語の様にあらかじめ定義されたシンボルでquoteの必要がないのであたかも変数の様に書かれる。しかもこれらはswiftでも予約語なので_を付けて変換した上で、true_とfalse_を定義しておく。

var true_ = Expression.BOOLEAN(true)
var false_ = Expression.BOOLEAN(false)

【assignment】
Metacircular Evaluatorのコードにset!は登場しないが、単に代入で良いはず。ただし変数名は変換が必要。

(define (compile-assignment exp linkage)
  (list (generate-identifier (assignment-variable exp)) " = " (compile (assignment-value exp) 'next)))

代入文は値を持たないはずなのでlinkageのコードは吐かない。

【definition】
変数の場合は単に代入文で良いが、手続きの場合は一旦変数を一時的な手続きで初期化してから代入し直す必要がある（再帰をサポートする為）。手続きをバインドする変数は、後方で定義される手続きを呼び出せるようにする為にコードの最初に定義する必要がある。predefined-variablesに登録しておき、最後に別途出力する事にする。

(define predefined-variables (make-hash))

(define (generate-arg-type-list n)
  (define (generate-list n)
    (if (= n 0)
        '()
        (cons "Expression" (generate-list (- n 1)))))
  (apply string-append (add-between (generate-list n) ",")))

(define (compile-definition exp linkage)
  (let ((value (definition-value exp)))
    (if (lambda? value)
        (begin
          (dict-set! predefined-variables (generate-identifier (definition-variable exp))
                     (string-append ": (" (generate-arg-type-list (length (lambda-parameters value)))
                    ") -> Expression = {_ in Expression.SYMBOL(\"undefined\")}"))
          (list (generate-identifier (definition-variable exp)) " = " (compile value 'next)))
        (list "var " (compile-assignment exp linkage)))
    ))

(define (print-pridefined-variables)
  (for-each (lambda (k) (display "var ")(display k)(display (dict-ref predefined-variables k))(newline)) (dict-keys predefined-variables)))

【if】
ifの形式に変換するだけ。書式も殆ど変わらない。

(define (compile-if exp linkage)
  (list "if " (compile (if-predicate exp) 'next) ".isTrue() {"
        (compile (if-consequent exp) linkage)
        "} else {"
        (compile (if-alternative exp) linkage)
        "}"))

【begin】
ここは元のコードとあまり変わらない。文を区切るセミコロンを挟む必要がある。

(define (compile-sequence seq linkage)
  (if (last-exp? seq)
      (compile (first-exp seq) linkage)
      (add-between (list
                    (compile (first-exp seq) 'next)
                    (compile-sequence (rest-exps seq) linkage)) ";")))

【lambda】
クロージャの形式に変換するだけ。

(define (compile-lambda exp linkage)
  (list "{" (add-between (map symbol->string (lambda-parameters exp)) ",") " in "
        (compile-sequence (lambda-body exp) 'return) "}"
  ))

【application】
引数をコンパイルして関数呼び出しの形に変換するだけ。

(define (compile-application exp linkage)
  (end-with-linkage linkage (list (compile (operator exp) 'next) "(" (add-between (map (lambda (operand) (compile operand 'next)) (operands exp)) ",") ")")))

【let】
expand-clausesがletを使っているのでcompileもletをサポートする必要がある。ただ、letを単にラムダ式に展開して、そのまま呼び出す事は出来ないので、普通に変数を定義する文にコンパイルする。

(define (let? exp) (tagged-list? exp 'let))
(define (let-variables exp) (cadr exp))
(define (let-body exp) (cddr exp))

(define (compile-let exp linkage)
  (list (add-between (map (lambda (v) (list "var " (compile (car v) 'next) " = " (compile (cadr v) 'next))) (let-variables exp)) ";")
        ";"
        (compile-sequence (let-body exp) linkage)))

【compile】
ここは殆どtargetを省略しただけ。

(define (compile exp linkage)
  (cond ((number? exp)
         (compile-number exp linkage))
        ((string? exp)
         (compile-string exp linkage))
        ((quoted? exp) (compile-quoted exp linkage))
        ((variable? exp)
         (compile-variable exp linkage))
        ((assignment? exp)
         (compile-assignment exp linkage))
        ((definition? exp)
         (compile-definition exp linkage))
        ((if? exp) (compile-if exp linkage))
        ((lambda? exp) (compile-lambda exp linkage))
        ((begin? exp)
         (compile-sequence (begin-actions exp)
                           linkage))
        ((cond? exp) (compile (cond->if exp) linkage))
        ((let? exp) (compile (let->combination exp) linkage))
        ((application? exp)
         (compile-application exp linkage))
        (else
         (error "Unknown expression type -- COMPILE" exp))))

これを使って4.1.1〜4.1.3のコードをコンパイルして行く。出力されたコードをX-codeの方に手動でコピペするするところがちょっと情けない。
例えば

(print-result
 (compile
  '(define (eval exp env)
     (cond ((self-evaluating? exp) exp)
           ((variable? exp) (lookup-variable-value exp env))
           ((quoted? exp) (text-of-quotation exp))
           ((assignment? exp) (eval-assignment exp env))
           ((definition? exp) (eval-definition exp env))
           ((if? exp) (eval-if exp env))
           ((lambda? exp)
            (make-procedure (lambda-parameters exp)
                            (lambda-body exp)
                            env))
           ((begin? exp) 
            (eval-sequence (begin-actions exp) env))
           ((cond? exp) (eval (cond->if exp) env))
           ((application? exp)
            (apply (eval (operator exp) env)
                   (list-of-values (operands exp) env)))
           (else
            (error "Unknown expression type -- EVAL" exp)))) 'return))(newline)

の出力結果

eval = {exp,env in if self_evaluatingp(exp).isTrue() {exp} else {if variablep(exp).isTrue() {lookup_variable_value(exp,env)} else {if quotedp(exp).isTrue() {text_of_quotation(exp)} else {if assignmentp(exp).isTrue() {eval_assignment(exp,env)} else {if definitionp(exp).isTrue() {eval_definition(exp,env)} else {if ifp(exp).isTrue() {eval_if(exp,env)} else {if lambdap(exp).isTrue() {make_procedure(lambda_parameters(exp),lambda_body(exp),env)} else {if beginp(exp).isTrue() {eval_sequence(begin_actions(exp),env)} else {if condp(exp).isTrue() {eval(cond__if(exp),env)} else {if applicationp(exp).isTrue() {apply(eval(operator_(exp),env),list_of_values(operands(exp),env))} else {error("Unknown expression type -- EVAL",exp)}}}}}}}}}}}

最後にpredefined-variablesを出力してコンパイルしたコードの先頭に挿入する。

(print-pridefined-variables)

var beginp: (Expression) -> Expression = {_ in Expression.SYMBOL("undefined")}
var condp: (Expression) -> Expression = {_ in Expression.SYMBOL("undefined")}
var definition_value: (Expression) -> Expression = {_ in Expression.SYMBOL("undefined")}
var cond_else_clausep: (Expression) -> Expression = {_ in Expression.SYMBOL("undefined")}
（以下省略）

サポートする部分のコードは以下の通り。

enum Expression {
    case BOOLEAN(Bool)
    case NUMBER(Int)
    case STRING(String)
    case SYMBOL(String)
    case LIST([Expression])
    case ENVIRONMENT(Environment)
    case PRIMITIVE(([Expression]->Expression))
    case ERROR(String)
}

extension Expression {
    var list: Optional<[Expression]> {
        switch self {
        case let .LIST(l):
            return .Some(l)
        default:
            return .None
        }
    }

    var environment: Optional<Environment> {
        switch self {
        case let .ENVIRONMENT(e):
            return .Some(e)
        default:
            return .None
        }
    }

    var primitive: Optional<([Expression] -> Expression)> {
        switch self {
        case let .PRIMITIVE(p):
            return .Some(p)
        default:
            return .None
        }
    }
    
    func description() -> String {
        switch self {
        case let .BOOLEAN(b):
            return b.description
        case let .NUMBER(n):
            return n.description
        case let .STRING(s):
            return "\"" + s + "\""
        case let .SYMBOL(s):
            return s
        case let .LIST(list):
            return "(" + join(" ", list.map({$0.description()})) + ")"
        case let .ENVIRONMENT(env):
            return env.description()
        case let .PRIMITIVE(p):
            return "procedure"
        case let .ERROR(s):
            return s
        }
    }
    
    func isTrue() -> Bool {
        switch self {
        case let .BOOLEAN(b):
            return b
        default:
            return false
        }
    }
}

func == (a: Expression, b: Expression) -> Bool {
    switch (a, b) {
    case let (.BOOLEAN(x), .BOOLEAN(y)):
        return x == y
    case let (.NUMBER(x), .NUMBER(y)):
        return x == y
    case let (.STRING(x), .STRING(y)):
        return x == y
    case let (.SYMBOL(x), .SYMBOL(y)):
        return x == y
    case let (.ERROR(x), .ERROR(y)):
        return y == y
    default:  // LIST, PRIMITIVE, ENVIRONMENT
        return false
    }
}

func error(msg: String, args: Expression...) -> Expression {
    return Expression.ERROR(msg + ":" + " ".join(args.map({$0.description()})))
}

class Environment {
    var frame = Dictionary<String, Expression>()
    var parent:Environment? = nil
    
    func add(sym:String, exp:Expression) -> Expression {
        frame[sym] = exp
        return Expression.ENVIRONMENT(self)
    }
    
    func value(sym:String) -> Expression {
        switch frame[sym] {
        case let .Some(exp):
            return exp
        default:
            if parent != nil {
                return parent!.value(sym)
            } else {
                return error("Unbound variable: " + sym)
            }
        }
    }
    
    func extend(vars: [Expression], values: [Expression]) -> Environment {
        var newEnv = Environment()
        newEnv.parent = self
        
        for (variable, value) in Array(Zip2(vars, values)) {
            switch variable {
            case let .SYMBOL(sym):
                newEnv.add(sym, exp: value)
            default:
                continue
            }
        }
        return newEnv
    }
    
    func description() -> String {
        return frame.description
    }
}

func extend_environment(variables: Expression, values: Expression, base_env: Expression) -> Expression {
    switch (variables, values, base_env) {
    case let (.LIST(vars), .LIST(vals), .ENVIRONMENT(env)):
        return Expression.ENVIRONMENT(env.extend(vars, values: vals))
    default:
        return error("Wrong environment")
    }
}

func lookup_variable_value(variable: Expression, environment: Expression) -> Expression {
    switch (variable, environment) {
    case let (.SYMBOL(sym), .ENVIRONMENT(env)):
        return env.value(sym)
    default:
        return error("Wrong variable reference")
    }
}

func set_variable_valueb(variable: Expression, value: Expression, environment: Expression) -> Expression {
    switch (variable, environment) {
    case let (.SYMBOL(sym), .ENVIRONMENT(env)):
        return env.add(sym, exp: value)
    default:
        return error("Wrong variable reference")
    }
}

func define_variableb(variable: Expression, value: Expression, environment: Expression) -> Expression {
    return set_variable_valueb(variable, value, environment)
}

// Primitive Procedures
func _car<Any>(list: [Any]) -> Any {
    return list[0]
}

func _cdr<Any>(list:[Any]) -> [Any] {
    if list.endIndex == 1 {
        return []
    } else {
        return Array(list[1...(list.count - 1)])
    }
}

func apply_number(argl:[Expression], op:((Int, Expression)->Int)) -> Expression {
    switch argl[0] {
    case let .NUMBER(initialValue):
        return Expression.NUMBER(_cdr(argl).reduce(initialValue, combine: op))
    default:
        return Expression.BOOLEAN(false)
    }
}

func plus(argl:[Expression]) -> Expression {
    return apply_number(argl, {value, arg in
        switch arg {
        case let .NUMBER(n):
            return value + n
        default:
            return value
        }
    })
}

func minus(argl:[Expression]) -> Expression {
    return apply_number(argl, {value, arg in
        switch arg {
        case let .NUMBER(n):
            return value - n
        default:
            return value
        }
    })
}

func multiply(argl:[Expression]) -> Expression {
    return apply_number(argl, {value, arg in
        switch arg {
        case let .NUMBER(n):
            return value * n
        default:
            return value
        }
    })
}

func equal_aux(initValue:Int, argl:[Expression]) -> Bool {
    if (argl.count > 0) {
        switch argl[0] {
        case let .NUMBER(n):
            return n == initValue && equal_aux(initValue, Array(argl[1..<argl.endIndex]))
        default:
            return false
        }
    } else {
        return true
    }
}

func equal(argl:[Expression]) -> Expression {
    switch argl[0] {
    case let .NUMBER(initialValue):
        return Expression.BOOLEAN(equal_aux(initialValue, Array(argl[1..<argl.endIndex])))
    default:
        return Expression.BOOLEAN(false)
    }
}

func symbolp(exp: Expression) -> Expression {
    switch exp {
    case .SYMBOL:
        return Expression.BOOLEAN(true)
    default:
        return Expression.BOOLEAN(false)
    }
}

func pairp(exp: Expression) -> Expression {
    switch exp {
    case .LIST:
        return Expression.BOOLEAN(true)
    default:
        return Expression.BOOLEAN(false)
    }
}

func numberp(exp: Expression) -> Expression {
    switch exp {
    case .NUMBER:
        return Expression.BOOLEAN(true)
    default:
        return Expression.BOOLEAN(false)
    }
}

func stringp(exp: Expression) -> Expression {
    switch exp {
    case .STRING:
        return Expression.BOOLEAN(true)
    default:
        return Expression.BOOLEAN(false)
    }
}

func eqp(a: Expression, b: Expression) -> Expression {
    return Expression.BOOLEAN(a == b)
}

func if_list(exp: Expression)(op: ([Expression] -> Expression)) -> Expression {
    switch exp {
    case let .LIST(list):
        return op(list)
    default:
        return error("Internal software error @op_list: " + exp.description())
    }
}

func not(exp: Expression) -> Expression {
    switch exp {
    case .BOOLEAN(let b):
        return Expression.BOOLEAN(!b)
    default:
        return exp
    }
}

func nullp(exp: Expression) -> Expression {
    return if_list (exp) (op: {list in
        Expression.BOOLEAN(list.isEmpty)
    })
}

func list(args: Expression...) -> Expression {
    return Expression.LIST(args)
}

func cons(car: Expression, cdr:Expression) -> Expression {
    return if_list (cdr) (op:{list in
        var result = list
        result.insert(car, atIndex: 0)
        return Expression.LIST(result)
    })
}

func car(exp: Expression) -> Expression {
    return if_list (exp) (op: {list in
        list[0]
    })
}

func cdr(exp: Expression) -> Expression {
    return if_list (exp) (op: {list in
        Expression.LIST(_cdr(list))
    })
}

func cadr(exp: Expression) -> Expression {
    return if_list (exp) (op: {list in
        car(Expression.LIST(_cdr(list)))
    })
}

func caadr(exp: Expression) -> Expression {
    return car(cadr(exp))
}

func cddr(exp: Expression) -> Expression {
    return cdr(cdr(exp))
}

func caddr(exp: Expression) -> Expression {
    return car(cddr(exp))
}

func cdadr(exp: Expression) -> Expression {
    return cdr(cadr(exp))
}

func cdddr(exp: Expression) -> Expression {
    return cdr(cdr(cdr(exp)))
}

func cadddr(exp: Expression) -> Expression {
    return car(cdddr(exp))
}

func primitive_procedurep(proc: Expression) -> Expression {
    switch proc {
    case .PRIMITIVE:
        return Expression.BOOLEAN(true)
    default:
        return Expression.BOOLEAN(false)
    }
}

func apply_primitive_procedure(proc: Expression, args: Expression) -> Expression {
    switch (proc, args) {
    case let (.PRIMITIVE(p), .LIST(a)):
        return p(a)
    default:
        return error("invalid primitive application")
    }
}

実行環境のサポートは以下の通り

func skip_spaces(input: String) -> String {
    if input.hasPrefix(" ") {
        return skip_spaces(input.substringFromIndex(advance(input.startIndex, 1)))
    } else {
        return input
    }
}

func find_string_end(input: String) -> Int {
    var i = 1
    for c in input.substringFromIndex(advance(input.startIndex, 1)) {
        if c != "\"" {
            i++
        } else {
            break
        }
    }
    return i + 1
}

func find_word_end(input: String) -> Int {
    var i = 0
    for c in input {
        if c != " " && c != ")" {
            i++
        } else {
            break
        }
    }
    return i
}

func tokenize_one(input: String) -> (String, String) {
    var w = skip_spaces(input)
    var i : Int
    if w.hasPrefix("(") || w.hasPrefix(")") {
        i = 1
    } else if w.hasPrefix("\"") {
        i = find_string_end(w)
    } else {
        i = find_word_end(w)
    }
    
    return (w.substringToIndex(advance(w.startIndex, i)), w.substringFromIndex(advance(w.startIndex, i)))
}

func tokenize(input: String) -> [String] {
    let (word, rest) = tokenize_one(input)
    var list: [String] = [word]
    if rest.isEmpty || skip_spaces(rest).isEmpty {
        return list
    } else {
        return list + tokenize(rest)
    }
}

func parse_list(tokens:[String]) -> ([Expression], [String]) {
    if tokens[0] == ")" {
        return ([], _cdr(tokens))
    } else {
        let (val, rest) = parse_token(tokens)
        var (list, beyond_list) = parse_list(rest)
        list.insert(val, atIndex: 0)
        return (list, beyond_list)
    }
}

func parse_token(tokens: [String]) -> (Expression, [String]) {
    if tokens.isEmpty {
        return (Expression.LIST([]), [])
    } else if tokens[0] == ")" {
        return (Expression.LIST([]), _cdr(tokens))
    } else if tokens[0] == "(" {
        let (list, rest) = parse_list(_cdr(tokens))
        return (Expression.LIST(list), rest)
    } else if let n = tokens[0].toInt() {
        return (Expression.NUMBER(n), _cdr(tokens))
    } else if (tokens[0] == "true") {
        return (Expression.BOOLEAN(true), _cdr(tokens))
    } else if (tokens[0] == "false") {
        return (Expression.BOOLEAN(false), _cdr(tokens))
    } else if (tokens[0].hasPrefix("\"")) {
        var str = tokens[0].substringToIndex(advance(tokens[0].startIndex, count(tokens[0].utf16) - 1)).substringFromIndex(advance(tokens[0].startIndex, 1)) // get rid of quotation marks
        return (Expression.STRING(str), _cdr(tokens))
    } else {
        return (Expression.SYMBOL(tokens[0]), _cdr(tokens))
    }
}

func parse(input: String) -> Expression {
    let tokens = tokenize(input)
    let (value, rest) = parse_token(tokens)
    return value
}

func expand_quote(tokens: [String]) -> [String] {
    if tokens.isEmpty {
        return []
    } else if tokens[0] == "'(" {
        return ["(", "quote"] + expand_quote(_cdr(tokens))
    } else if tokens[0].hasPrefix("'(") {
        return ["(", "quote", tokens[0].substringFromIndex(advance(tokens[0].startIndex, 2))] + expand_quote(_cdr(tokens))
    } else if tokens[0].hasPrefix("'") {
        return ["(", "quote", tokens[0].substringFromIndex(advance(tokens[0].startIndex, 1)), ")"] + expand_quote(_cdr(tokens))
    } else {
        return [tokens[0]] + expand_quote(_cdr(tokens))
    }
}

func expand_syntax_sugar(tokens: [String]) -> [String] {
    return expand_quote(tokens)
}

// REPL
func nest(tokens: [String]) -> Int {
    return tokens.reduce(0, combine: {n, token in
        switch token {
        case "(":
            return n + 1
        case ")":
            return n - 1
        default:
            return n
        }
    })
}

func read_line() -> String {
    var str = NSString(data: NSFileHandle.fileHandleWithStandardInput().availableData, encoding: NSUTF8StringEncoding)! as String
    return str.substringToIndex(advance(str.startIndex, count(str.utf8) - 1)) + " "  // replace new line to a space
}

func read() -> Expression {
    var input = ""
    while (true) {
        input = input + read_line()
        let tokenized = tokenize(input)
        let n = nest(tokenized)
        if n < 0 {
            return Expression.SYMBOL("Parentheses mismatch")
        } else if n == 0 {
            let (value, rest) = parse_token(expand_syntax_sugar(tokenized))
            return value
        }
    }
}

func user_print(object: Expression) {
    if compound_procedurep(object).isTrue() {
        println(list(Expression.SYMBOL("compound-procedure"), procedure_parameters(object), procedure_body(object), Expression.SYMBOL("<procedure-env>")).description())
    } else {
        println(object.description())
    }
}

var the_global_environment = Expression.ENVIRONMENT(Environment())
if the_global_environment.environment != nil {
    the_global_environment.environment!.add("true", exp: Expression.BOOLEAN(true))
    the_global_environment.environment!.add("false", exp: Expression.BOOLEAN(false))
    the_global_environment.environment!.add("+", exp: Expression.PRIMITIVE(plus))
    the_global_environment.environment!.add("-", exp: Expression.PRIMITIVE(minus))
    the_global_environment.environment!.add("*", exp: Expression.PRIMITIVE(multiply))
    the_global_environment.environment!.add("=", exp: Expression.PRIMITIVE(equal))
}

func driver_loop() {
    print(";;; M-Eval input: ")
    let input = read()
    let output = eval(input, the_global_environment)
    println(";;; M-Eval value: ")
    user_print(output)
    return driver_loop()
}

driver_loop()

サポートコード
print-pridefined-variablesの出力
その他のcompileの結果をprint-resultで出力したもの
下記の実行環境サポート

の順でX-codeにコピペして実行。

実行結果。

;;; M-Eval input: (define (factorial n)
(if (= n 0)
1
(* (factorial (- n 1)) n)))
;;; M-Eval value: 
ok
;;; M-Eval input: (factorial 6)
;;; M-Eval value: 
720
;;; M-Eval input:

まぁ簡単なプログラムしかコンパイルはしていないけど、一応これで動いている。

あとがき

手元に残っているソースファイルの日付を見ると2009年6月4日。第２章の終わりまで読み進めたところで、どうもSchemeの知識が足りなさすぎる感じがしたので一旦中断。『Schem手習い』『Scheme修行』等を経て、2012年にもう一度最初の問題からやる直して全ての問題に取り組む決意を以って再開。このブログにSICPのノートをつけ始めたのは2012年5月19日。今日は2015年4月25日。ほぼ６年掛けて、再開後も３年を掛けて漸く最後まで辿り着いた。そもそも最後の5.5.7節だけで３ヶ月は要した。一応全ての問題に回答した筈。第４章の最後の問題だけ微妙だけど。あまりにも長く掛かったので自分のプログラミングに変化があるのか良く分からなくなっているが、Racketで実行していた関係でmutable/immutableを明確に区別して考える癖がついている気がするし、値を返さない文（set!とか）がとても特殊に感じる様になった。Scheme以外の言語を触っていてもifが値を返さないのがとても不便に感じたり。言語処理系を勉強するだけでなく、遅延評価や論理プログラミングなども実際に手を動かして中で何が起きているのかも勉強する事ができた。
さて、この後はCTMCPに行くか、関数型プログラミング入門に行くかまだ思案中。

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 5.5.7 Interfacing Compiled Code to the Evaluator / Exercise 5.52

ノート

Exercise 5.52

あとがき