Lambda Calculus in Swift

church.swift

//
//  main.swift
//  church
//
//  Created by Dan Kogai on 6/15/14.
//  Copyright (c) 2014 Dan Kogai. All rights reserved.
//

/* Operators */

// SUCC := λnfx.f (n f x)
// ((t1 -> t) -> t2 -> t1) -> (t1 -> t) -> t2 -> t
func succ<T1,T,T2>(n:(T1->T)->T2->T1)->(T1->T)->T2->T {
    return {(f:T1->T)->T2->T in {(x:T2)->T in f(n(f)(x))}}
}
// ADD := λm n f x. m f (n f x)
// (t2 -> t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t
func add<T2,T1,T,T3>(m:T2->T1->T)->(T2->T3->T1)->T2->T3->T {
    return {(n:T2->T3->T1)->T2->T3->T in
        {(f:T2)->T3->T in {(x:T3)->T in m(f)(n(f)(x))}}}
}
// MUL := λm n f. m (n f)
// (t1 -> t) -> (t2 -> t1) -> t2 -> t
func mul<T1,T,T2>(m:T1->T)->(T2->T1)->T2->T {
    return {(n:T2->T1)->T2->T in {(f:T2)->T in m(n(f))}}
}
// POW
// t1 -> (t1 -> t) -> t
func pow<T1,T>(m:T1)->(T1->T)->T {
    return {(n:T1->T)->T in n(m)}
}
// 0
func c0<T>(f:(T)->T)->(T)->T {
    return {(x:T)->T in x}
}
// 1
func c1<T>(f:(T)->T)->(T)->T {
    // return {(x:T)->T in f(x)}
    return {(x:T)->T in succ(c0)(f)(x)}
}
// 2
func c2<T>(f:(T)->T)->(T)->T {
    // return {(x:T)->T in f(f(x))}
    return {(x:T)->T in succ(c1)(f)(x)}
}
// 3
func c3<T>(f:(T)->T)->(T)->T {
    // return {(x:T)->T in f(f(x))}
    return {(x:T)->T in add(c1)(c2)(f)(x)}
}
// see if it works
let v = succ(succ(mul(add(c2)(c3))(pow(c2)(c3))))({x in x+1})(0)
println(v)