Trampoline.ceylon

/* Usage Example:
Whole fibonacci(Whole n) {
	Trampoline<Whole> fibonacciHelper(Whole n) {
		if (n==zero || n==one) {
			return Return(n);
		} else {
			return Call<Whole>(() => fibonacciHelper(n - one), [[fibonacciHelper(n - two), Whole.plus]]);
		}
	}
	
	return fibonacciHelper(n).result;
}
*/
import ceylon.collection {
	ArrayList
}

shared variable Integer constructionCounter = 0;

shared abstract class Trampoline<Type>
		of Return<Type> | Call<Type> {
	shared new () {
		++constructionCounter;
	}
	shared formal Type result;
	shared restricted formal Call<Type>|Type computeResult(Call<Type> previous);
}

shared class Return<Type>(shared actual Type result)
		extends Trampoline<Type>() {
	shared restricted actual Call<Type>|Type computeResult(Call<Type> previous) {
		variable Type result = this.result;
		
		while (exists [operand, operator] = previous.list.pop()) {
			switch (operand)
			case (is Type) {
				/*switch (operator)
				case (is Type(Type, Type)) {
					result = operator(result, operand);
				}
				// Case is not disjoint: Type(Type)(Type) and Type(Type, Type) have intersection <Type&Type(Type)>(*<Type[2]|[Type]>) (use else case)
				else case (is Type(Type)(Type)) {
					result = operator(result)(operand);
				}
				else {
					throw AssertionError("Weird shit just happened");
				}*/
				result = operator(result)(operand);
			}
			// Case is not disjoint: Trampoline<Type> and Type have intersection Type&Trampoline<Type> (use else case)
			else case (is Trampoline<Type>) {
				previous.list.push([result, operator]);
				return Call<Type>(() => operand, previous.list);
			} 
			else {
				throw AssertionError("Weird shit just happened");
			}
		}
		
		return result;
	}	
}

shared class Call<Type>
		extends Trampoline<Type> {
	Trampoline<Type>() bounce;
	shared restricted ArrayList<[Type|Trampoline<Type>, /*Type(Type, Type)|*/Type(Type)(Type)]> list;
	
	shared new (Trampoline<Type>() bounce, {[Type|Trampoline<Type>, /*Type(Type, Type)|*/Type(Type)(Type)]*} elements = [])
			extends Trampoline<Type>() {
		this.bounce = bounce;
		this.list = ArrayList<[Type|Trampoline<Type>, /*Type(Type, Type)|*/Type(Type)(Type)]> { elements = elements; };
	}
	
	shared actual Type result {
		variable Call<Type> previous = this;
		
		while (true) {
			value current = previous.bounce();
			value nextOrResult = current.computeResult(previous);
			
			switch (nextOrResult)
			case (is Call<Type>) {
				previous = nextOrResult;
			}
			// Case is not disjoint: Type and Call<Type> have intersection Call<Type>&Type (use else case)
			else case (is Type) {
				return nextOrResult;
			}
		}
	}
	
	shared restricted actual Call<Type>|Type computeResult(Call<Type> previous) {
		list.addAll(previous.list);
		return this;
	}
}