andyglick/valence

Abstract Binding Trees

Valence

Abstract Binding Trees for designing programming languages in Swift.

The implementation is heavily inspired by Jon Sterling et al.'s ABT library that powers, among other things, the JonPRL language.

Introduction

One way of thinking about an ABT is that it is an AST that is aware of binding structure. Another would be that it is a tree representation of binding-aware abstract syntactic structure.

In addition to the standard structural and organizational advantanges, ABTs manage the ins and outs of keeping track of variable bindings and scopes through a system of arities à la Martin Löf. This particular implementation also handles the checking of symbol sorts automatically and hence allows for multiple kinds of syntax to coexist in the binding structure.

Working With ABTs

We'll begin by defining the binding structure of a simple calculator language. The first thing to define are the Sorts of terms that can be constructed. Here, because we don't make a distinction between, say, types and terms, we only have one sort: TERMs.

import Valence

enum CalculatorSort : Sort {
	case TERM
	
	var description : String {
		return "term"
	}
	
	static func ==(l : CalculatorSort, r : CalculatorSort) -> Bool {
		return true
	}
}

Next we'll define the set of operators available to the calculator. Operators are tagged with a sort for organizational purposes and can calculate an arity per operation that describes its binding structure.

enum CalculatorOperator : Operator {
	typealias OperatorSort = CalculatorSort

	case Num(Int)
	case Plus
	case Times
	case Let

	// An `Arity` specifies an operator of sort `S` with 
	// arguments of valences.
	//
	// A `Valence` is an expression of sort `S` that binds 
	// symbols and variables around an operator.
	var arity : Arity<CalculatorSort> {
		switch self {
		// Numbers
		case .Num(_):
			// Constants are operators that take no arguments.
			return Arity([], .TERM)
		// `+` has two arguments.
		case .Plus:
			return Arity([
				// The LHS
				Valence([], [], .TERM),
				// The RHS
				Valence([], [], .TERM),
			], .TERM)
		// `*` has two arguments.
		case .Times:
			return Arity([
				// The LHS
				Valence([], [], .TERM),
				// The RHS
				Valence([], [], .TERM),
			], .TERM)
		// `let` binds a single argument 
		case .Let:
			return Arity([
				Valence([], [.TERM], .TERM),
			], .TERM)
		}
	}

	var description : String {
		switch self {
		case let .Num(i):
			return "\(i)"
		case .Plus:
			return "plus"
		case .Times:
			return "times"
		case .Let:
			return "let"
		}
	}
	
	static func ==(l : CalculatorOperator, r : CalculatorOperator) -> Bool {
		switch (l, r) {
		case let (.Num(i), .Num(j)):
			return i == j
		case (.Plus, .Plus):
			return true
		case (.Times, .Times):
			return true
		case (.Let, .Let):
			return true
		default:
			return false
		}
	}
}

And we're done!

typealias CalculatorTerm = AbstractBindingTree<Named, Named, Named, CalculatorOperator, ()>

System Requirements

Valence supports OS X 10.9+, iOS 8.0+, tvOS 9.0+, and watchOS 2.0+.

License

Valence is released under an MIT license.