Create a gist now

Instantly share code, notes, and snippets.

Full code listing for a post
enum Expression<Recur> {
case Variable(String)
case Abstraction(String, Recur)
case Application(Recur, Recur)
func map<Other>(transform: Recur -> Other) -> Expression<Other> {
switch self {
case let .Variable(x):
return .Variable(x)
case let .Abstraction(x, body):
return .Abstraction(x, transform(body))
case let .Application(a, b):
return .Application(transform(a), transform(b))
}
}
}
class Box<T> {
init(_ value: T) { self.value = value }
let value: T
}
protocol FixpointType {
typealias Fixed
var body: Fixed { get }
}
struct Term: FixpointType {
let boxedBody: Box<Expression<Term>>
var body: Expression<Term> {
return boxedBody.value
}
}
extension Expression where Recur : FixpointType {
func destructure() -> Expression<Recur.Fixed> {
return map { $0.body }
}
}
func evaluate(expression: Expression<Term>) {
switch expression.destructure() {
case let .Application(.Abstraction(variable, body), argument):
// substitute argument for variable in body
break
default:
// throw an error
break
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment