Implement deferred word, conditional resolution

Due to the non-trivial way tokens were previously processed the compiler could not safely perform tail-call elimination. Thus the _slang_ evaluation depth was restricted by the maximum call stack size.

This issue is mitigated by introducing deferred word resolution - i.e. pushing expanded tokens onto a buffer stack and processing them in an explicit loop.

This change ties into the implementation of the language's conditional primitive. The previous implementation did implicitly not support direct nesting of conditional expressions such as:

	truthA if
		mainBranch
		truthB if
			secondaryMainBranch
		then else
	then
		alternativeBranch
	else

This issue is now made explicit by disallowing direct nesting of conditionals as depicted above. Appropriate exceptions are generated when required and the conditional primitive is reimplemented in a more robust fashion under the assumption that this rule holds. Note that nesting is still fully supported iff. the nested conditional is contained in a deferredly evaluated word. As a positive side effect this will make it slightly harder to generate unreadable code by forcing developers to write simpler words.

The main change of the conditional primitive lies in deferring branch token processing until the conditional expression is concluded by `else`. This is achieved by capturing non-dropped tokens in an internal buffer akin to how the word definition operator `§` is implemented.
The branch buffer is discharged after `else` is evaluated. Discharging is triggered via the newly introduced `result` method of the primitive evaluation module. This avenue for injecting tokens into the processing stream may be used by further primitives in the future.

6 files changed, 193 insertions, 155 deletions

diff --git a/repl.d b/repl.d
index b68b46a..df2905d 100644
--- a/repl.d
+++ b/repl.d
@@ -1,69 +1,60 @@
 import std.stdio;
 import std.string;
-import std.conv;
 import std.variant;
 import std.typecons;
 
-import std.container : SList;
-
 import src.stack;
 
 static import definition = src.definition;
 static import primitives = src.primitives.eval;
 
-template process(T)
-if ( is(T == int) || is(T == bool) ) {
-	void process(T value) {
-		try {
-			if ( !primitives.evaluate(value) ) {
-				stack.push(value);
-			}
-		}
-		catch (Exception ex) {
-			writeln("Error: ", ex.msg);
-		}
-	}
-}
-
-void process(string word) {
+Stack!Token resolve(Token token) {
 	try {
-		if ( !primitives.evaluate(word) ) {
-			if ( word in definition.words ) {
-				foreach ( token; definition.words[word] ) {
-					process(token);
-				}
-			} else {
-				stack.push(word);
-			}
+		if ( primitives.evaluate(token) ) {
+			return primitives.result;
+		} else {
+			return token.visit!(
+				(int    value) => Stack!Token(Token(value)),
+				(bool   value) => Stack!Token(Token(value)),
+				(string word ) => definition.get(word)
+			);
 		}
 	}
 	catch (Exception ex) {
 		writeln("Error: ", ex.msg);
+		return Stack!Token();
 	}
 }
 
-void process(Token token) {
-	token.visit!(
-		(int    value) => process(value),
-		(bool   value) => process(value),
-		(string word ) => process(word)
-	);
+void process(string value) {
+	Stack!Token buffer;
+	Token token = toToken(value);
+
+	if ( !definition.handle(token) ) {
+		buffer = resolve(token);
+	}
+
+	while ( !buffer.empty ) {
+		Token current = buffer.pop;
+
+		if ( !definition.handle(current) ) {
+			Stack!Token resolved = resolve(current);
+
+			if ( !resolved.empty ) {
+				if ( resolved.front == current ) {
+					stack.push(current);
+				} else {
+					buffer.insertFront(resolved[]);
+				}
+			}
+		}
+	}
 }
 
 void main() {
 	while ( !stdin.eof ) {
 		foreach ( token; stdin.readln.split ) {
-			if ( token.isNumeric ) {
-				auto value = parse!int(token);
-
-				if ( !definition.handle(value) ) {
-					process(value);
-				}
-			} else {
-				if ( !definition.handle(token) ) {
-					process(token);
-				}
-			}
+			process(token);
 		}
 	}
 }
diff --git a/src/definition.d b/src/definition.d
index e6a7789..7429f4b 100644
--- a/src/definition.d
+++ b/src/definition.d
@@ -3,11 +3,12 @@ module src.definition;
 import std.string;
 import std.variant;
 import std.typecons;
+
 import std.container : DList;
 
-import src.stack : Token;
+import src.stack;
 
-alias Words = DList!Token[string];
+alias Words = Stack!Token[string];
 
 Nullable!(DList!Token) definition;
 Words                  words;
@@ -30,7 +31,7 @@ void end() {
 	}
 
 	definition.removeFront;
-	words[wordToBeDefined] = definition;
+	words[wordToBeDefined] = Stack!Token(definition[]);
 	definition.nullify;
 }
 
@@ -67,3 +68,11 @@ bool handle(Token token) {
 		(string word ) => handle(word)
 	);
 }
+
+Stack!Token get(string word) {
+	if ( word in words ) {
+		return words[word].dup;
+	} else {
+		return Stack!Token(Token(word));
+	}
+}
diff --git a/src/primitives/conditional.d b/src/primitives/conditional.d
new file mode 100644
index 0000000..ee89ea5
--- /dev/null
+++ b/src/primitives/conditional.d
@@ -0,0 +1,77 @@
+module src.primitives.conditional;
+
+import std.variant;
+import std.typecons;
+import std.container : DList;
+
+import src.stack;
+
+Nullable!(DList!Token) buffer;
+bool                   concluded = true;
+bool                   drop_mode = false;
+
+void capture(Token token) {
+	if ( !drop_mode ) {
+		buffer.insertBack(token);
+	}
+}
+
+bool drop(Token token) {
+	if ( concluded && buffer.isNull ) {
+		return false;
+	}
+
+	if ( token.type == typeid(string) ) {
+		switch ( *token.peek!string ) {
+			case "if"   : eval_if;        break;
+			case "then" : eval_then;      break;
+			case "else" : eval_else;      break;
+			default     : capture(token); break; 
+		}
+	} else {
+		capture(token);
+	}
+
+	return true;
+}
+
+void eval_if() {
+	if ( concluded ) {
+		buffer    = DList!Token();
+		drop_mode = !stack.pop.get!bool;
+		concluded = false;
+	} else {
+		throw new Exception("conditionals may not be nested directly");
+	}
+}
+
+void eval_then() {
+	if ( concluded  ) {
+		throw new Exception("`then` without preceding `if`");
+	} else {
+		drop_mode = !drop_mode;
+	}
+}
+
+void eval_else() {
+	if ( concluded ) {
+		throw new Exception("`else` without preceding `if`");	
+	} else {
+		drop_mode = false;
+		concluded = true;
+	}
+}
+
+bool dischargeable() {
+	return concluded && !buffer.isNull;
+}
+
+Stack!Token discharge() {
+	if ( concluded ) {
+		Stack!Token result = buffer[];
+		buffer.nullify;
+		return result;
+	} else {
+		throw new Exception("unconcluded conditional may not be discharged");	
+	}
+}
diff --git a/src/primitives/impl.d b/src/primitives/core.d
index 9fddee5..5b3d43d 100644
--- a/src/primitives/impl.d
+++ b/src/primitives/core.d
@@ -1,4 +1,4 @@
-module src.primitives.impl;
+module src.primitives.core;
 
 import std.stdio;
 
@@ -6,65 +6,40 @@ import src.stack;
 import src.definition;
 
 Token[string] variables;
-bool          drop_mode;
 
-bool definition_start() {
+void definition_start() {
 	src.definition.start;
-	return true;
 }
 
-bool binary_op_variable_bind() {
-	string name  = stack.pop.get!string;
-	Token  value = stack.pop;
-
+void binary_op_variable_bind() {
+	string name     = stack.pop.get!string;
+	Token  value    = stack.pop;
 	variables[name] = value;
-	return true;
 }
 
-bool unary_op_variable_resolve() {
+void unary_op_variable_resolve() {
 	string name = stack.pop.get!string;
 
 	if ( name in variables ) {
 		stack.push(variables[name]);
 	}
-
-	return true;
-}
-
-bool unary_conditional_if() {
-	drop_mode = !stack.pop.get!bool;
-	return true;
-}
-
-bool n_ary_conditional_then() {
-	drop_mode = !drop_mode;
-	return true;
 }
 
-bool n_ary_conditional_else() {
-	drop_mode = false;
-	return true;
-}
-
-bool binary_op_add() {
+void binary_op_add() {
 	int b = stack.pop.get!int;
 	int a = stack.pop.get!int;
 
 	stack.push(a + b);
-
-	return true;
 }
 
-bool binary_op_multiply() {
+void binary_op_multiply() {
 	int b = stack.pop.get!int;
 	int a = stack.pop.get!int;
 
 	stack.push(a * b);
-
-	return true;
 }
 
-bool binary_op_divide() {
+void binary_op_divide() {
 	int b = stack.pop.get!int;
 	int a = stack.pop.get!int;
 
@@ -73,11 +48,9 @@ bool binary_op_divide() {
 	} else {
 		stack.push(a / b);
 	}
-
-	return true;
 }
 
-bool binary_op_modulo() {
+void binary_op_modulo() {
 	int b = stack.pop.get!int;
 	int a = stack.pop.get!int;
 
@@ -86,52 +59,43 @@ bool binary_op_modulo() {
 	} else {
 		stack.push(a % b);
 	}
-
-	return true;
 }
 
-bool unary_op_io_print() {
+void unary_op_io_print() {
 	writeln(stack.top);
-	return true;
 }
 
-bool unary_op_stack_pop() {
+void unary_op_stack_pop() {
 	stack.pop;
-	return true;
 }
 
-bool unary_op_stack_dup() {
+void unary_op_stack_dup() {
 	stack.push(stack.top);
-	return true;
 }
 
-bool binary_op_stack_swp() {
+void binary_op_stack_swp() {
 	auto b = stack.pop;
 	auto a = stack.pop;
 
 	stack.push(b);
 	stack.push(a);
 
-	return true;
 }
 
-bool binary_cond_lt() {
+void binary_cond_lt() {
 	int b = stack.pop.get!int;
 	int a = stack.pop.get!int;
 
 	stack.push(a < b);
-	return true;
 }
 
-bool binary_cond_eq() {
+void binary_cond_eq() {
 	auto b = stack.pop;
 	auto a = stack.pop;
 
 	stack.push(a == b);
-	return true;
 }
 
-bool integral_value_bool(bool value) {
+void integral_value_bool(bool value) {
 	stack.push(Token(value));
-	return true;
 }
diff --git a/src/primitives/eval.d b/src/primitives/eval.d
index 8b080e2..08d8fb9 100644
--- a/src/primitives/eval.d
+++ b/src/primitives/eval.d
@@ -1,65 +1,53 @@
 module src.primitives.eval;
 
-import src.primitives.impl;
+import std.variant;
 
-bool evaluate(int value) {
-	return drop_mode;
-}
+import src.stack;
+import src.primitives.core;
+import conditional = src.primitives.conditional;
+
+bool evaluate_primitive(string word) {
+	switch ( word ) {
+		case     "§"     : definition_start;           break;
+		case     "$"     : binary_op_variable_bind;    break;
+		case     "@"     : unary_op_variable_resolve;  break;
+		case     "if"    : conditional.eval_if;        break;
+		case     "then"  : conditional.eval_then;      break;
+		case     "else"  : conditional.eval_else;      break;
+		case     "+"     : binary_op_add;              break;
+		case     "*"     : binary_op_multiply;         break;
+		case     "/"     : binary_op_divide;           break;
+		case     "%"     : binary_op_modulo;           break;
+		case     "."     : unary_op_io_print;          break;
+		case     "pop"   : unary_op_stack_pop;         break;
+		case     "dup"   : unary_op_stack_dup;         break;
+		case     "swp"   : binary_op_stack_swp;        break;
+		case     "true"  : integral_value_bool(true);  break;
+		case     "false" : integral_value_bool(false); break;
+		case     "<"     : binary_cond_lt;             break;
+		case     "="     : binary_cond_eq;             break;
+		default          : return false;
+	}
 
-bool evaluate(bool value) {
-	return drop_mode;
+	return true;
 }
 
-bool evaluate(string word) {
-	if ( drop_mode ) {
-		switch ( word ) {
-			case "then":
-				return n_ary_conditional_then;
-			case "else":
-				return n_ary_conditional_else;
-			default:
-				return true;
-		}
+bool evaluate(Token token) {
+	if ( conditional.drop(token) ) {
+		return true;
+	} else {
+		return token.visit!(
+			(int    value) => false,
+			(bool   value) => false,
+			(string word ) => evaluate_primitive(word)
+		);
 	}
+}
 
-	switch ( word ) {
-		case "§":
-			return definition_start;
-		case "$":
-			return binary_op_variable_bind;
-		case "@":
-			return unary_op_variable_resolve;
-		case "if":
-			return unary_conditional_if;
-		case "then":
-			return n_ary_conditional_then;
-		case "else":
-			return n_ary_conditional_else;
-		case "+":
-			return binary_op_add;
-		case "*":
-			return binary_op_multiply;
-		case "/":
-			return binary_op_divide;
-		case "%":
-			return binary_op_modulo;
-		case ".":
-			return unary_op_io_print;
-		case "pop":
-			return unary_op_stack_pop;
-		case "dup":
-			return unary_op_stack_dup;
-		case "swp":
-			return binary_op_stack_swp;
-		case "true":
-			return integral_value_bool(true);
-		case "false":
-			return integral_value_bool(false);
-		case "<":
-			return binary_cond_lt;
-		case "=":
-			return binary_cond_eq;
-		default:
-			return false;
+Stack!Token result() {
+	if ( conditional.dischargeable ) {
+		return conditional.discharge;
+	} else {
+		return Stack!Token();
 	}
 }
diff --git a/src/stack.d b/src/stack.d
index 2fb602b..678f3e8 100644
--- a/src/stack.d
+++ b/src/stack.d
@@ -1,7 +1,8 @@
 module src.stack;
 
-import std.variant;
+import std.conv;
 import std.string;
+import std.variant;
 import std.container : SList;
 
 static import src.definition;
@@ -11,6 +12,14 @@ alias Stack = SList;
 
 Stack!Token stack;
 
+Token toToken(string value) {
+	if ( value.isNumeric ) {
+		return Token(parse!int(value));
+	} else {
+		return Token(value);
+	}
+}
+
 Token top(ref Stack!Token stack) {
 	if ( stack.empty ) {
 		throw new Exception("stack is empty");