プログラミング再入門

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

SICP 5.5.7 Interfacing Compiled Code to the Evaluator / Exercise 5.51

LISP Scheme

ノート

Exercise 5.51

5.2ではレジスタマシン・シミュレータをSchemeで実装したが、これをC言語で実装するなら5.4のExplicit Evaluatorは基本的には何も変換する必要はない筈なのできっと問題の意図とは異なる。そうすると『レジスタマシン相当の実行環境をC言語で作って、それを使ったExplicit Evaluatorを同じくC言語で実装する』と解釈する。
ただ、今更Cですか？と言う気もするし、折角Macを使っているので、ここはswiftにチャレンジしてみる。

変換の大まかな方針：

  1. レジスタは変数だけど、save / restoreは言語の関数呼び出しの仕組みに任せる
  2. レジスタマシンのレジスタはSchemeと同じく何でも入ったので、これをうまく実装する必要がある
    1. 代数データ型？　swiftだとenum。
    2. 数値はとりあえず整数のみ。
  3. リストは必ずしもconsセルで表現しなくても良いかも。swiftの配列でも（ある程度？）表現出来る。
  4. 環境はハッシュテーブル（swiftだとDictionary）が使えそう。
  5. gotoとbranchはエラーでREPLに強制的に戻る時以外は基本的には分岐と関数呼び出しに割り振れそう。

【データの表現】

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

    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"
        }
    }
}

enum Result : Printable {
    case EXPRESSION(Expression)
    case ERROR(String)
    
    var description: String {
        switch self {
        case let .EXPRESSION(exp):
            return exp.description()
        case let .ERROR(err):
            return err
        }
    }
}

ExpressionはPrintableにしようとしたけど、何故かLISTの部分で落ちるので仕方なくこの形に。
Resultはswiftに例外がなかったので、エラーの時には戻り値で表現する為。

【パーサー】

swiftでパーサーコンビネータとか出来そうだけど、LISPの場合は括弧以外は基本的にはスペースで単語が区切れていて、そこまでのものは必要なさそうなので単純に実装してみる。

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))
    }
}

tokenizeは括弧とダブルクォートで囲まれた文字列のみ特別扱いして、それ以外はスペース区切り。parse_tokenはそれをExpressionに変換するだけ。Expressionの文字列にする時にはダブルクォートを削除する。

【環境】

swiftのDictionary（配列）は値セマンティクスで関数に渡す時にコピーが作られてしまうが、クロージャや関数の定義に関しては都合が悪い。4.1.6節での議論も関連。再帰関数を作る時にはクロージャを作る時に取り込む環境は、その瞬間の環境のスナップショット（コピー）ではだめで参照である必要がる。クロージャ作成時には参照している環境に自分自身がまだ登録されていないので、その後に書き換えられる必要があるから。
swiftで参照を使うためにはオブジェクトにする必要があるので環境はクラスとして定義する。環境を拡張する時に親となる環境も参照した時点より後に変化するため、親子関係も参照を使う。

class Environment {
    var frame = Dictionary<String, Expression>()
    var parent:Environment? = nil

    func add(sym:String, exp:Expression) {
        frame[sym] = exp
    }
    
    func value(sym:String) -> Result {
        switch frame[sym] {
        case let .Some(exp):
            return Result.EXPRESSION(exp)
        default:
            if parent != nil {
                return parent!.value(sym)
            } else {
                return Result.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
    }
}

【tagged list】
SchemeでのMetacircular EvaluatorとかExplicit Control Evaluatorの真似をしてtagged listを使う。

func tagged_list(exp: Expression, tag:String) -> Bool {
    switch exp {
    case let .LIST(list):
        switch list[0] {
        case let .SYMBOL(sym):
            if (sym == tag) {
                return true
            } else {
                return false
            }
        default:
            return false
        }
    default:
        return false
    }
}

func is_quoted(exp: Expression) -> Bool {
    return tagged_list(exp, "quote")
}

func is_assignment(exp: Expression) -> Bool {
    return tagged_list(exp, "set!")
}

func is_definition(exp: Expression) -> Bool {
    return tagged_list(exp, "define")
}

func is_if(exp: Expression) -> Bool {
    return tagged_list(exp, "if")
}

func is_lambda(exp: Expression) -> Bool {
    return tagged_list(exp, "lambda")
}

func is_begin(exp: Expression) -> Bool {
    return tagged_list(exp, "begin")
}

func is_primitive_procedure(exp: Expression) -> Bool {
    return tagged_list(exp, "primitive")
}

func is_compound_procedure(exp: Expression) -> Bool {
    return tagged_list(exp, "procedure")
}

【Explicit Control Evaluator】
代数データ型をenumで表現するとコードのそこら中に同じswitch文が沢山書く事になったので、ちょっと纏める便利関数を作った。

func if_expression(value: Result)(op: (Expression -> Result)) -> Result {
    switch value {
    case let .EXPRESSION(exp):
        return op(exp)
    case .ERROR:
        return value
    }
}

func is_expression(value: Result) -> Bool {
    switch value {
    case .EXPRESSION:
        return true
    case .ERROR:
        return false
    }
}

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

func if_symbol(exp: Expression)(op: (String -> Result)) -> Result {
    switch exp {
    case let .SYMBOL(sym):
        return op(sym)
    default:
        return Result.ERROR("Invalid symbol: " + exp.description())
    }
}

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

本題の評価器のポーティング。概ねストレートに置き換えているつもり。

func eval_dispatch(exp:Expression, inout env:Environment) -> Result {
    switch exp {
    case .BOOLEAN:
        return Result.EXPRESSION(exp)
    case .NUMBER:
        return Result.EXPRESSION(exp)
    case .STRING:
        return Result.EXPRESSION(exp)
    case let .SYMBOL(sym):
        return ev_variable(sym, env)
    case .LIST:
        if (is_quoted(exp)) {
            return ev_quote(exp)
        } else if (is_assignment(exp)) {
            return ev_assignment(exp, &env)
        } else if (is_definition(exp)) {
            return ev_definition(exp, &env)
        } else if (is_if(exp)) {
            return ev_if(exp, &env)
        } else if (is_lambda(exp)) {
            return ev_lambda(exp, &env)
        } else if (is_begin(exp)) {
            return ev_begin(exp, &env)
        } else { // application
            return ev_application(exp, &env)
        }
    default:
        return Result.ERROR("Unknown expression @eval_dispatch")
    }
}

func ev_variable(sym:String, env:Environment) -> Result {
    return env.value(sym)
}

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

func assign_variable(sym:String, exp: Expression, inout env: Environment) -> Result {
    return if_expression (eval_dispatch(exp, &env )) (op: {newValue in
        env.add(sym, exp: newValue)
        return Result.EXPRESSION(Expression.SYMBOL("ok"))
    })
}

func ev_assignment(exp: Expression, inout env: Environment) -> Result {
    return if_list (exp) (op: {list in
        if_symbol (list[1]) (op: {sym in
            if_expression (env.value(sym)) (op: {exp in // check if the variable (sym) exists
                assign_variable(sym, list[2], &env)
            })
        })
    })
}

func ev_definition(exp: Expression, inout env: Environment) -> Result {
    return if_list (exp) (op: {list in
        switch list[1] {
        case let .LIST(form):
            return if_symbol (form[0]) (op: {sym in
                assign_variable(sym, Expression.LIST([Expression.SYMBOL("lambda"), Expression.LIST(cdr(form)), list[2]]), &env)})
        case let .SYMBOL(sym):
            return assign_variable(sym, list[2], &env)
        default:
            return Result.ERROR("Bad definition: " + exp.description())
        }
    })
}

func ev_if(exp: Expression, inout env: Environment) -> Result {
    return if_list(exp) (op: {list in
        if_expression (eval_dispatch(list[1], &env)) (op: {exp in
            switch exp {
            case let .BOOLEAN(b):
                if (b) {
                    return eval_dispatch(list[2], &env)
                } else {
                    return eval_dispatch(list[3], &env)
                }
            default:
                return Result.ERROR("Bad condition: " + exp.description())
            }
        })
    })
}

func ev_lambda(exp: Expression, inout env: Environment) -> Result {
    return if_list (exp) (op: {list in
        if_list (list[1]) (op: {parameters in
            Result.EXPRESSION(
                Expression.LIST([
                    Expression.SYMBOL("procedure"),
                    Expression.LIST(parameters),
                    Expression.LIST(cdr(cdr(list))),
                    Expression.ENVIRONMENT(env)]))
        })
    })
}

func ev_sequence(list: [Expression], inout env: Environment) -> Result {
    if (list.count > 2) {
        for exp in Array(list[0...(list.endIndex - 2)]) {
            let result = eval_dispatch(exp, &env)
        }
    }
    return eval_dispatch(list[list.endIndex - 1], &env)
}

func ev_begin(exp: Expression, inout env: Environment) -> Result {
    return if_list(exp) (op: {list in
        ev_sequence(cdr(list), &env)
    })
}

func apply_primitive_procedure(exp: Expression, argl: [Expression]) -> Result {
    return if_list(exp) (op: {list in
        switch list[1] {
        case let .PRIMITIVE(op):
            return Result.EXPRESSION(op(argl))
        default:
            return Result.ERROR("Invalid primitive procedure")
        }
    })
}

func compound_apply(op: Expression, argl: [Expression]) -> Result {
    return if_list (op) (op: {list in
        switch list[1] {
        case let .LIST(parameters):
            switch list[2] {
            case let .LIST(body):
                switch list[3] {
                case let .ENVIRONMENT(env):
                    var newEnv = env.extend(parameters, values: argl)
                    return ev_sequence(body, &newEnv)
                default:
                    return Result.ERROR("Invalid compound procedure env")
                }
            default:
                return Result.ERROR("Invalid compound procedure body")
            }
        default:
            return Result.ERROR("Invalid compound procedure parameters")
        }
    })
}

func ev_application(exp: Expression, inout env: Environment) -> Result {
    return if_list(exp) (op: {list in
        if_expression (eval_dispatch(list[0], &env)) (op: {op in
            var argl: [Expression] = []
            for result in cdr(list).map({exp in eval_dispatch(exp, &env)}) {
                switch result {
                case let .EXPRESSION(exp):
                    argl.append(exp)
                case .ERROR:
                    return result
                }
            }
            if (is_primitive_procedure(op)) {
                return apply_primitive_procedure(op, argl)
            } else if (is_compound_procedure(op)) {
                return compound_apply(op, argl)
            } else {
                return Result.ERROR("Unknown procedure type: " + op.description())
            }
        })
    })
}

defineの扱いは、(define func (lambda (arg) ...)となっていれば普通の変数の定義と同じに出来るが、(define (func arg) ...)の形だと変換が必要になる。Schemeではreadがよしなにlamdaに変換してくれていたが、ここは自前でやらなければならない。パースする手前では難しいのでev_definitionで対応せざるを得ない。

【プリミティブ】

引数の型がどうしてもExpressionの配列となってしまい、そのまま呼び出せないのでラッパーが必要。

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)
    }
}

【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 read_eval_print_loop(inout env: Environment) -> () {
    while (true) {
        print(";;; EC-Eval input: ")
        println(eval_dispatch(read(), &env))
    }
}

Schemeのreadがよしなにやってくれていたもう一つの機能：シングルクォートをquote式に変換する事、をこのレベルで実装。

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)
}

【動作確認】
とりあえず最小のプリミティブで実現出来るテスト。

var global_env = Environment()

global_env.add("+", exp: Expression.LIST([
    Expression.SYMBOL("primitive"),
    Expression.PRIMITIVE(plus)]))
global_env.add("=", exp: Expression.LIST([
    Expression.SYMBOL("primitive"),
    Expression.PRIMITIVE(equal)]))
global_env.add("-", exp: Expression.LIST([
    Expression.SYMBOL("primitive"),
    Expression.PRIMITIVE(minus)]))
global_env.add("*", exp: Expression.LIST([
    Expression.SYMBOL("primitive"),
    Expression.PRIMITIVE(multiply)]))

read_eval_print_loop(&global_env)

動作結果

;;; EC-Eval input: (define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
ok
;;; EC-Eval input: (factorial 5)
120
;;; EC-Eval input: