Full code listing for a post

Expression.swift

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