[swift] Lambda Calculus on swift-2

lambda.swift

// Untyped Lambda Calculus on swift-2
enum Expr {
    case Num(Int)
    case Ref(String)
    indirect case Lam(String, Expr)
    indirect case App(Expr, Expr)

    func eval(env: Env) -> Val {
        switch self {
        case let .Num(v): return Val.Number(v)
        case let .Ref(n): return env.get(n)
        case let .Lam(p, b): return Val.Closure(env, p, b)
        case let .App(e, a): return e.eval(env).apply(a.eval(env))
        }
    }
}

enum Val {
    case Nil
    case Number(Int)
    case Closure(Env, String, Expr)
    case Native(Int->Int)

    func apply(v: Val) -> Val {
        switch self {
        case let .Closure(env, param, body):
            return body.eval(env.put(param, v))
        case let .Native(f):
            switch v {
            case .Number(let n): return Val.Number(f(n))
            default: return Val.Nil // type error case
            }
        default: return self
        }
    }
}

enum Env {
    case End
    indirect case Map(String, Val, Env)
                       
    func get(name: String) -> Val {
        switch self {
        case .End: return Val.Nil
        case let .Map(n, v, next): return n == name ? v : next.get(name)
        }
    }
    func put(n: String, _ v: Val) -> Env {
        return .Map(n, v, self)
    }
}


// example
// env with builtin: sq(n) => n*n
let top = Env.End.put("sq", Val.Native({(a: Int) -> Int in a * a}))
// (\a => (sq (sq a)) 10 ==> 10000
let prog = Expr.App(Expr.Lam("a",
                             Expr.App(Expr.Ref("sq"),
                                      Expr.App(Expr.Ref("sq"),
                                               Expr.Ref("a")))),
                    Expr.Num(10))

// eval 
print(prog.eval(top))

stlc.swift

// Symply Typed Lambda Calculus on swift-2

// syntax tree elements
class Expr<T> {
    func eval(env: Env) -> Val<T> {return Nil<T>()}
}
class Num: Expr<Int>, CustomStringConvertible {
    let value: Int
    init (_ value: Int) {self.value = value}
    override func eval(env: Env) -> Val<Int> {return Obj(value)}
    var description: String {get {return "\(value)"}}
}
class Ref<R>: Expr<R>, CustomStringConvertible {
    let name: String
    init (_ name: String) {self.name = name}
    override func eval(env: Env) -> Val<R> {return lookup(env, name)}
    var description: String {get {return "\(name)<\(R.self)>"}}
}
class Lam<A, B>: Expr<A->B>, CustomStringConvertible {
    let name: String
    let body: Expr<B>
    init (_ name: String, _ body: Expr<B>) {self.name = name; self.body = body}
    override func eval(env: Env) -> Val<A->B> {return Clo(env, name, body)}
    var description: String {
        get {return "{\\\(name)<\(A.self)> -> \(body)}"}
    }
}
class App<A, B>: Expr<B>, CustomStringConvertible {
    let fun: Expr<A->B>
    let arg: Expr<A>
    init (_ fun: Expr<A->B>, _ arg: Expr<A>) {self.fun = fun; self.arg = arg}
    override func eval(env: Env) -> Val<B> {
        return apply(fun.eval(env), arg.eval(env))
    }
    var description: String {get {return "(\(fun) \(arg))<\(B.self)>"}}
}


// runtime values
class Val<T>: CustomStringConvertible {
    var description: String {get {return "\(self.dynamicType)"}}
}
class Nil<T>: Val<T> {
} // as programming error
class Obj<T>: Val<T> {
    let value: T
    init (_ value: T) {self.value = value}
    override var description: String {get {return "\(value): \(T.self)"}}
} // as builtin
class Clo<A, B>: Val<A->B> {
    let env: Env
    let name: String
    let body: Expr<B>
    init (_ env: Env, _ name: String, _ body: Expr<B>) {
        self.env = env; self.name = name; self.body = body
    }
    override var description: String {get {
        return "\(name): \(A.self) -> \(body)"
    }} 
}
func apply<A, B>(fun: Val<A->B>, _ arg: Val<A>) -> Val<B> {
    switch fun {
    case let c as Clo<A, B>: return c.body.eval(c.env.put(c.name, arg))
    case let f as Obj<A->B>:
        switch arg {
        case let a as Obj<A>: return Obj(f.value(a.value))
        default: return Nil<B>()
        }
    default: return Nil<B>()
    }
}


// environment table
class Env: CustomStringConvertible {
    func put<V>(name: String, _ value: Val<V>) -> Env {
        return Map(name, value, self)
    }
    //func look<V>(name: String) -> Val<V> {return Nil<V>()}
    //[WORKAROUND] swift2 has no wildcard type param
    //  use generic method instead of wildcard (only for self defined types)
    func nextEnv() -> Env {return self}
    //[WORKAROUND] swift2 has no wildcard type param
    func entry() -> String {return ""}
    var description: String {get {
        var s = "{\n  \(self.entry())"
        var c = self.nextEnv()
        while (true) {
            switch c {
            case is End: return "\(s)\n}"
            default:
                s += "\n  \(c.entry())"
                c = c.nextEnv()
            }
        }
    }} 
}
class End: Env {}
class Map<T>: Env {
    let name: String
    let value: Val<T>
    let next: Env
    init (_ name: String, _ value: Val<T>, _ next: Env) {
        self.name = name; self.value = value; self.next = next
    }
    override func nextEnv() -> Env {return next}
    //[WHY?] error: "method does not override any method from its superclass"
    //override func look<V>(name: String) -> Val<V> {return Nil<V>()}
    override func entry() -> String {return "'\(name)' => \(value)"}
}
func lookup<R>(env: Env, _ name: String) -> Val<R> {
    switch env {
    case let m as Map<R> where m.name == name: return m.value
    case is End: return Nil<R>()
    default: return lookup(env.nextEnv(), name)
    }
}

//[Usage]
// env with builtin functions
let top = End().put("sq", Obj<Int->Int>() {a in a * a})
print(""); print(top); print(lookup(top, "sq") as Val<Int->Int>)

// basics syntax
let p1 = App(Ref<Int->Int>("sq"), Num(10))
print(""); print(p1); print(p1.eval(top))
let p2 = Lam<Int, Int>("a", Num(10))
print(""); print(p2); print(p2.eval(top))
let p3 = App(Lam("a", Num(10)), Num(5))
print(""); print(p3); print(p3.eval(top))
let p4 = App(Lam("a", Ref<Int>("a")), Num(5))
print(""); print(p4); print(p4.eval(top))
let p5 = App(Lam("a", App(Ref<Int->Int>("sq"), Ref("a"))), Num(5))
print(""); print(p5); print(p5.eval(top))

//expression type mismatches become type error on compile time
//let p0 = App(Ref<Int->Int>("a"), Ref<Int>("b")) // <= ok
//let p0 = App(Ref<Int->Int->Int>("a"), Ref<Int>("b")) // <= ok
//let p0 = App(Ref<Int>("a"), Ref<Int>("b")) // <= compile error
//let p0 = App(Ref<(Int->Int)->Int>("a"), Ref<Int>("b")) // <= compile error

// a little complex tree
let prog = App(Lam("a",
                   App(Ref<Int->Int>("sq"),
                       App(Ref<Int->Int>("sq"), Ref("a")))),
               Num(10))
print(""); print(prog); print(prog.eval(top))


// Example: binary operator
let top2 = top.put("div", Obj<Int->Int->Int>() {a in {b in a / b}})
print(""); print(top2); print(lookup(top2, "div") as Val<Int->Int->Int>)
let prog2 = App(App(Ref<Int->Int->Int>("div"), Num(10)), Num(5))
print(""); print(prog2); print(prog2.eval(top2))