lambda.d

module lambda;


import std.algorithm;
import std.container;
import std.conv;
import std.exception;
import std.functional;
import std.range;


abstract class Expression
{
	Expression dup()
	{
		assert(0);
	}
}

final class Variable : Expression
{
	string name;

	this(string n)
	{
		name = n;
	}

	override string toString() const
	{
		return name;
	}

	override bool opEquals(Object obj) const
	{
		if (auto var = cast(Variable)obj) return name == var.name;
		return false;
	}

	override Expression dup()
	{
		return variable(name);
	}
}

Variable variable(string x)
{
	return new Variable(x);
}

final class Lambda : Expression
{
	string var;

	Expression term;

	this(string v, Expression t)
	{
		var = v;
		term = t;
	}

	override bool opEquals(Object obj) const
	{
		if (auto lm = cast(Lambda)obj) return lm.var == var && lm.term == term;
		return false;
	}

	override string toString()
	{
		if (auto lm = cast(Lambda)term)
		{
			auto vars = appender!(string[]);
			vars ~= var;

			Lambda l = lm;
			do
			{
				lm = l;
				vars ~= lm.var;
				l = cast(Lambda)lm.term;
			} while (l);

			// strip parenthesis
			if (auto a = cast(Application) lm.term)
				return "(λ"~ vars.data.join(' ') ~ "." ~ lm.term.toString()[1 .. $-1] ~ ")";
			else
				return "(λ"~ vars.data.join(' ') ~ "." ~ lm.term.toString() ~ ")";
		}
		else
		{
			// strip parenthesis
			if (auto a = cast(Application) term)
				return "(λ"~ var ~ "." ~ term.toString()[1 .. $-1] ~ ")";
			else
				return "(λ"~ var ~ "." ~ term.toString() ~ ")";
		}
	}

	override Expression dup()
	{
		return lambda(var, term.dup);
	}
}

unittest
{
	Expression expr = lambda("x", lambda("y", application(variable("x"), variable("y"))));
	assert(expr.toString() == "(λx y.x y)", expr.toString());
}

Lambda lambda(string var, Expression term)
{
	assert(term);
	return new Lambda(var, term);
}

final class Application : Expression
{
	Expression func;

	Expression input;

	this(Expression f, Expression i)
	{
		func = f;
		input = i;
	}

	override bool opEquals(Object obj) const
	{
		if (auto app = cast(Application)obj) return app.func == func && app.input == input;
		return false;
	}

	override string toString()
	{
		auto apps = appender!(Application[]);

		auto a = this;
		while (a)
		{
			apps ~= cast(Application)a;
			a = cast(Application)a.func;
		}

		return "(" ~ apps.data[$-1].func.toString() ~ " " ~
			apps.data.retro.map!(a => a.input.toString()).join(' ') ~ ")";
	}

	override Expression dup()
	{
		return application(func.dup, input.dup);
	}
}

Application application(Expression l, Expression r)
{
	assert(l); assert(r);
	return new Application(l, r);
}

unittest
{
	Expression lm = lambda("x", variable("x"));
	assert(lm.toString() == "(λx.x)");
}


RedBlackTree!string freeVariables(Expression expr)
{
	return expr.castSwitch!(
		(Variable v)
		{
			string[1] ar = v.name;
			return redBlackTree(ar);
		},
		(Lambda lm)
		{
			auto vars = freeVariables(lm.term);
			vars.removeKey(lm.var);
			return vars;
		},
		(Application app)
		{
			auto vars = freeVariables(app.func);
			vars.insert(freeVariables(app.input)[]);
			return vars;
		});
}

unittest
{
	assert(lambda("x", application(variable("x"), variable("y"))).freeVariables[]
			.equal(only("y")));
	assert(lambda("x", application(variable("a"), variable("a"))).freeVariables[]
			.equal(only("a")));
	assert(lambda("x", application(variable("a"), variable("b"))).freeVariables[]
			.equal(only("a", "b")));
}


struct SubstituteVariableNames
{
	import std.ascii : lowercase;
	string alphas = lowercase;
	auto postfixes = chain(only(""), sequence!("n").map!(to!string));

	enum empty = false;

	string front()
	{
		assert(!alphas.empty);
		return chain(only(alphas.front), postfixes.front).text;
	}

	void popFront()
	{
		alphas.popFront();

		if (alphas.empty)
		{
			alphas = lowercase;
			postfixes.popFront();
		}
	}
}

unittest
{
	static assert(isInputRange!SubstituteVariableNames);
	import std.ascii : lowercase;
	assert(SubstituteVariableNames().drop(26).startsWith(only("a0", "b0")));
}


void replace(ref Expression lm, string from, Expression to, RedBlackTree!string freevars = null)
{
	lm.castSwitch!(
		(Variable var)
		{
			if (var.name == from) lm = to;
		},
		(Lambda ab)
		{
			if (ab.var == from) return;

			assert(!freevars || freevars[].equal(to.freeVariables[]));
			if (!freevars) freevars = to.freeVariables;
			if (ab.var in freevars)
			{
				auto vars = ab.term.freeVariables;
				string newv = SubstituteVariableNames().filter!(i => i !in vars && i !in freevars).front;
				ab.term.replace(ab.var, variable(newv));
				ab.var = newv;
			}

			ab.term.replace(from, to, freevars);
		},
		(Application app)
		{
			app.func.replace(from, to, freevars);
			app.input.replace(from, to.dup, freevars);
		});
}

unittest
{
	Expression lm =
		application(
				lambda("i",
					lambda("y", variable("x"))),
				variable("x"));
	lm.replace("x", variable("i"));
	assert(lm ==
		application(
			lambda("a",
				lambda("y", variable("i"))),
			variable("i")));

	lm = LambdaParser!string(`\y z.x`).parseExpression();
	lm.replace("x", application(variable("y"), variable("z")));
	assert(lm == lambda("a", lambda("a", application(variable("y"), variable("z")))), lm.toString());
}


bool reduction(ref Expression lm)
{
	return lm.castSwitch!(
		(Variable _) => false,
		(Lambda lm) => lm.term.reduction(),
		(Application app)
		{
			if (auto l = cast(Lambda)app.func)
			{
				l.term.replace(l.var, app.input);
				lm = l.term;
				return true;
			}

			return app.func.reduction() || app.input.reduction();
		});
}

unittest
{
	Expression lm = application(lambda("x", lambda("y", variable("x"))), variable("a"));
	lm.reduction();
	assert(lm == lambda("y", variable("a")));
}


struct LambdaParser(R) if (isInputRange!R)
{
	import std.ascii;
	R _r;

	Variable parseVariable()
	{
		auto app = appender!(ElementEncodingType!R[]);

		enforce(_r.front.isAlpha || _r.front == '_', "Expected alphabet or '_'");
		app ~= _r.front; _r.popFront();
		app ~= refRange(&_r).until!(not!(c => c.isAlphaNum || c == '_'));

		return variable(app.data);
	}

	Lambda parseLambda()
	{
		skipWhite();
		enforce(_r.skipOver("λ") || _r.skipOver('\\'), "Expected 'λ' or '\\'");

		auto vars = appender!(Variable[]);
		skipWhite();
		while (_r.front != '.')
		{
			vars ~= parseVariable();
			skipWhite();
			enforce(!_r.empty, "Unexpected EOF");
		}

		enforce(vars.data.length > 0, "Must have at least 1 argument");

		enforce(_r.skipOver('.'));
		skipWhite();

		auto term = parseExpression();

		Lambda l;
		l = lambda(vars.data[$-1].name, term);
		foreach (v; vars.data[0 .. $-1].retro) l = lambda(v.name, l);

		return l;
	}

	Expression parseExpression(bool noapp = false)
	{
		skipWhite();
		enforce(!_r.empty, "Expected expression");

		Expression expr;

		if (_r.front.isAlpha || _r.front == '_')
		{
			expr = parseVariable();
		}
		else if (_r.startsWith("λ") || _r.front == '\\')
		{
			 expr = parseLambda();
		}
		else if (_r.skipOver('('))
		{
			expr = parseExpression();
			enforce(!_r.empty && _r.skipOver(')'), "Expected ')'");
		}
		else
		{
			enforce(false, "Expected expression, not '" ~ to!string(_r.front) ~ "'");
		}

		skipWhite();
		if (_r.empty) return expr;

		if (!noapp && _r.front != ')')
		{
			Expression input;
			if (_r.front.isAlpha)
			{
				input = parseVariable();
			}
			else if (_r.startsWith("λ") || _r.front == '\\')
			{
				input = parseLambda();
			}
			else
			{
				input = parseExpression(true);
			}

			skipWhite();

			Application app = application(expr, input);
			while (!_r.empty && _r.front != ')')
				app = application(app, parseExpression(true));
			return app;
		}

		return expr;
	}

	void skipWhite()
	{
		while (!_r.empty && _r.front.isWhite) _r.popFront();
	}
}

unittest
{
	static void testParser(string input, Expression expected)
	{
		import std.stdio;

		auto parsed = LambdaParser!string(input).parseExpression();
		if (parsed != expected)
		{
			stderr.writefln("Expected\t%s\nbut got\t\t%s", expected, parsed);
			assert(0);
		}
	}

	testParser(`(λx.x) a (\x y.x) c`,
			application(
				application(
					application(
						lambda("x", variable("x")),
						variable("a")),
					lambda("x", lambda("y", variable("x")))),
				variable("c")));

	testParser(`((λx y.x) (λy.i)) \z.z`,
			application(
				application(
					lambda("x", lambda("y", variable("x"))),
					lambda("y", variable("i"))),
				lambda("z", variable("z"))));

	testParser(`\x.x y \z.z w`,
			lambda("x",
				application(
					application(
						variable("x"), variable("y")),
					lambda("z",
						application(variable("z"), variable("w"))))));

	testParser(`(\m n s z. n (m s) z)`,
			lambda("m",
				lambda("n",
					lambda("s",
						lambda("z",
							application(
								application(
									variable("n"),
									application(variable("m"), variable("s"))),
								variable("z")))))));

	testParser(`a0b0c0123`, variable("a0b0c0123"));

	testParser(`a0 b0 c0123`,
			application(
				application(variable("a0"), variable("b0")),
				variable("c0123")));
}


unittest
{
	auto expr = LambdaParser!string(`(λm n s z.n (m s) z) (λs z.s (s (s z))) (λs z.s (s z))`)
		.parseExpression();

	while (expr.reduction()) {}

	assert(expr == LambdaParser!string(`\s z.s (s (s (s (s (s z)))))`).parseExpression(),
			expr.toString());
}

struct LambdaInterpreter
{
	Expression[string] variables;

	void interpret(string line)
	{
		import std.stdio, std.string;

		if (line.empty) return;

		if (line.skipOver("let "))
		{
			import std.ascii;
			enforce(!line.front.isDigit);
			auto name = refRange(&line).until!(not!(c => c.isAlphaNum || c == '_')).array.to!string;
			enforce(!name.empty);

			refRange(&line).until!(not!isWhite).copy((dchar){});
			enforce(line.skipOver("="));
			refRange(&line).until!(not!isWhite).copy((dchar){});

			auto expr = LambdaParser!string(line).parseExpression();

			foreach (v; expr.freeVariables[])
			{
				if (auto e = v in variables)
				{
					expr.replace(v, e.dup);
				}
			}

			variables[name] = expr;
			variables.rehash();
			writeln(name, " = ", variables[name].toString());
		}
		else
		{
			auto expr = LambdaParser!string(line).parseExpression();

			writeln(expr.toString.stripParen);

			bool rep;
			foreach (v; expr.freeVariables[])
			{
				if (auto e = v in variables)
				{
					expr.replace(v, e.dup);
					rep = true;
				}
			}
			if (rep) writeln(expr.toString.stripParen);

			ulong ctr;
			while (expr.reduction())
			{
				writeln(expr.toString.stripParen);

				if (++ctr >= 100)
				{
					writeln("Inturrupted");
					break;
				}
			}
		}
	}
}

string stripParen(string s) @safe pure nothrow @nogc
{
	if (s[0] == '(' && s[$-1] == ')') return s[1 .. $-1];
	else return s;
}

void main()
{
	import std.stdio, std.string;

	LambdaInterpreter intp;

	while (true)
	{
		write("λ> ");
		auto line = readln().chomp;

		if (line.skipOver(":load "))
		{
			auto f = File(line);
			scope(exit) f.close();
			foreach (l; f.byLine) intp.interpret(l.idup);
		}
		else
		{
			intp.interpret(line);
		}
	}
}