Lisp-like languages

/*
    Lisp-like languages ( https://en.wikipedia.org/wiki/Lisp_%28programming_language%29 )

    (Take #9)

    Cyril Jandia (07/2016)

    Public Domain.

    NO WARRANTY EXPRESSED OR IMPLIED. USE AT YOUR OWN RISK.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Text.RegularExpressions;

namespace LispLike
{
    public delegate object Parser(string input);

    public class Token
    {
        public Token(string pattern, Parser parser) : this(pattern, parser, false) { }
        public Token(string pattern, Parser parser, bool priority) { Regex = new Regex(String.Format("^({0})", !String.IsNullOrEmpty(Pattern = pattern) ? Pattern : ".*"), RegexOptions.Compiled); ValueOf = parser; Priority = priority; }
        public string Pattern { get; private set; }
        public Regex Regex { get; private set; }
        public Parser ValueOf { get; private set; }
        public bool Priority { get; private set; }
    }

    public class Syntax
    {
        private const string Spaced = "s+";
        private const string Opened = "(";
        private const string Closed = ")";

        private static readonly Token Spacing = Token(Spaced, Identity, 1);
        private static readonly Token Opening = Token(Opened, Identity);
        private static readonly Token Closing = Token(Closed, Identity);

        private Tuple<Token, string, object> Next(string input, ref string remaining)
        {
            if (!String.IsNullOrEmpty(input))
            {
                var found = null as Match;
                var tuple = Lexicon.FirstOrDefault(current => (found = current.Item2.Regex.Match(input)).Success && (found.Length > 0));
                var token = tuple != null ? tuple.Item2 : null;
                var match = token != null ? found.Value : null;
                remaining = match != null ? input.Substring(match.Length) : input;
                return token != null ? Tuple.Create(token, match, token.ValueOf(match)) : null;
            }
            else
            {
                return null;
            }
        }

        private IEnumerable<Tuple<Token, string, object>> From(string input)
        {
            Tuple<Token, string, object> item;
            while ((item = Next(input, ref input)) != null)
            {
                yield return item;
            }
        }

        private IEnumerator<Tuple<Token, string, object>> Source(string input)
        {
            var source = From(input).Where(tuple => tuple.Item1 != Spacing).GetEnumerator();
            if (source.MoveNext())
            {
                return source;
            }
            throw Language.Error("unexpected EOF");
        }

        private object Parse(IEnumerator<Tuple<Token, string, object>> source, bool root)
        {
            var token = source.Current.Item1;
            var value = source.Current.Item3;
            if (token == Opening)
            {
                var list = new List<object>();
                while (token != Closing)
                {
                    if (source.MoveNext())
                    {
                        if ((token = source.Current.Item1) != Closing)
                        {
                            list.Add(Parse(source, false));
                        }
                    }
                    else
                    {
                        throw Language.Error("unexpected EOF");
                    }
                }
                value = list.ToArray();
            }
            if (root && source.MoveNext())
            {
                throw Language.Error("unexpected \"{0}\"", ToString(source.Current.Item2));
            }
            return value;
        }

        protected IList<Tuple<string, Token>> Lexicon { get; private set; }

        public static string Escape(string pattern)
        {
            return Escape(pattern, -1);
        }

        public static string Escape(string pattern, int count)
        {
            count = count < 0 ? pattern.Length : count;
            return pattern.Aggregate(new StringBuilder(), (escaped, character) => escaped.AppendFormat("{0}{1}", count-- > 0 ? "\\" : String.Empty, character)).ToString();
        }

        public static object Identity(string input)
        {
            return input;
        }

        public static object Symbol(string input)
        {
            return new Symbol(input);
        }

        public static Token Token(string pattern, Parser parser)
        {
            return Token(pattern, parser, -1);
        }

        public static Token Token(string pattern, Parser parser, int escapeCount)
        {
            return Token(pattern, parser, escapeCount, false);
        }

        public static Token Token(string pattern, Parser parser, bool priority)
        {
            return Token(pattern, parser, -1, priority);
        }

        public static Token Token(string pattern, Parser parser, int escapeCount, bool priority)
        {
            return new Token(Escape(pattern, escapeCount), parser, priority);
        }

        public static Tuple<string, Parser> Lexical(string pattern, Parser parser)
        {
            return Tuple.Create(pattern, parser);
        }

        public static Tuple<string, Parser, bool> Lexical(string pattern, Parser parser, bool priority)
        {
            return Tuple.Create(pattern, parser, priority);
        }

        public static string ToString(object expression)
        {
            return
                expression is object[] ?
                (
                    ((object[])expression).Length > 0 ?
                    ((object[])expression).Aggregate(new StringBuilder("("), (result, obj) => result.AppendFormat(" {0}", ToString(obj))).Append(" )").ToString()
                    :
                    "( )"
                )
                :
                ((expression != null ? expression.ToString() : null) ?? "(null)").Replace("\r\n", "\n").Replace("\\\n", "\n").Replace("\\t", "\t").Replace("\\n", "\n").Replace("\\r", "\r").Replace("\\\"", "\"");
        }

        public Syntax()
        {
            Lexicon = new List<Tuple<string, Token>>();
            Include(Spacing, Opening, Closing);
        }

        public Syntax Include(Token token)
        {
            if (Lexicon.FirstOrDefault(tuple => tuple.Item1 == token.Pattern) == null)
            {
                if (token.Priority)
                {
                    Lexicon.Insert(0, Tuple.Create(token.Pattern, token));
                }
                else
                {
                    Lexicon.Add(Tuple.Create(token.Pattern, token));
                }
            }
            return this;
        }

        public Syntax Include(params Token[] tokens)
        {
            return tokens.Aggregate(this, (syntax, token) => syntax.Include(token));
        }

        public Syntax Include(params Tuple<string, Parser>[] entries)
        {
            return Include(entries.Select(entry => new Token(entry.Item1, entry.Item2)).ToArray());
        }

        public Syntax Include(params Tuple<string, Parser, bool>[] entries)
        {
            return Include(entries.Select(entry => new Token(entry.Item1, entry.Item2, entry.Item3)).ToArray());
        }

        public object Parse(string input)
        {
            return Parse(Source(input), true);
        }
    }

    public class Symbol
    {
        public Symbol(object id) { Id = Language.Const(id); }
        public override string ToString() { return Id.ToString(); }
        public object Id { get; private set; }
    }

    public delegate object Semantic(object[] arguments, Environment environment);

    public class Keyword : Symbol
    {
        public Keyword(string id, Semantic semantic) : base(id) { Semantic = semantic; }
        public Semantic Semantic { get; private set; }
    }

    [AttributeUsage(AttributeTargets.Method | AttributeTargets.Field, AllowMultiple = false, Inherited = false)]
    public class BuiltinAttribute : Attribute
    {
        public BuiltinAttribute(string id) { Id = id; }
        public string Id { get; private set; }
    }

    public abstract class Callable : Symbol
    {
        protected Callable(int length) : this(null, length) { }
        protected Callable(string id, int length) : base(id) { Length = length; }
        public abstract object Invoke(params object[] arguments);
        public Delegate Delegate { get; protected set; }
        public int Length { get; protected set; }
        public bool Variadic { get; protected set; }
    }

    public class Lambda : Callable
    {
        public Lambda(Symbol[] formals, Func<object[], object> closure) : base(formals.Length) { Formals = formals; Delegate = (Closure = closure); }
        public override int GetHashCode() { return Closure.GetHashCode(); }
        public override string ToString() { return String.Format("{0} => ...", Syntax.ToString(Formals)); }
        public override object Invoke(params object[] arguments) { return Closure(arguments); }
        public Symbol[] Formals { get; private set; }
        public Func<object[], object> Closure { get; private set; }
    }

    public abstract class Builtin : Callable
    {
        protected Builtin(string id, int length) : base(id, length) { }
        protected int Count(object[] arguments) { return arguments != null ? arguments.Length : 0; }
    }

    public class Builtin<TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, TResult> function) : base(id, 0) { Delegate = (Function = function); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null); }
        public Func<Environment, TResult> Function { get; private set; }
    }

    public class Builtin<T1, TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, T1, TResult> function) : base(id, 1) { Delegate = (Function = function); var arg1 = Function.Method.GetParameters()[1]; Variadic = (arg1.Name == "params") && (typeof(T1) == typeof(object[])); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null, count > 1 ? (T1)arguments[1] : default(T1)); }
        public Func<Environment, T1, TResult> Function { get; private set; }
    }

    public class Builtin<T1, T2, TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, T1, T2, TResult> function) : base(id, 2) { Delegate = (Function = function); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null, count > 1 ? (T1)arguments[1] : default(T1), count > 2 ? (T2)arguments[2] : default(T2)); }
        public Func<Environment, T1, T2, TResult> Function { get; private set; }
    }

    public class Builtin<T1, T2, T3, TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, T1, T2, T3, TResult> function) : base(id, 3) { Delegate = (Function = function); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null, count > 1 ? (T1)arguments[1] : default(T1), count > 2 ? (T2)arguments[2] : default(T2), count > 3 ? (T3)arguments[3] : default(T3)); }
        public Func<Environment, T1, T2, T3, TResult> Function { get; private set; }
    }

    public class Builtin<T1, T2, T3, T4, TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, T1, T2, T3, T4, TResult> function) : base(id, 4) { Delegate = (Function = function); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null, count > 1 ? (T1)arguments[1] : default(T1), count > 2 ? (T2)arguments[2] : default(T2), count > 3 ? (T3)arguments[3] : default(T3), count > 4 ? (T4)arguments[4] : default(T4)); }
        public Func<Environment, T1, T2, T3, T4, TResult> Function { get; private set; }
    }

    public class Builtin<T1, T2, T3, T4, T5, TResult> : Builtin
    {
        public Builtin(string id, Func<Environment, T1, T2, T3, T4, T5, TResult> function) : base(id, 5) { Delegate = (Function = function); }
        public override object Invoke(params object[] arguments) { var count = Count(arguments); return Function(count > 0 ? (Environment)arguments[0] : null, count > 1 ? (T1)arguments[1] : default(T1), count > 2 ? (T2)arguments[2] : default(T2), count > 3 ? (T3)arguments[3] : default(T3), count > 4 ? (T4)arguments[4] : default(T4), count > 5 ? (T5)arguments[5] : default(T5)); }
        public Func<Environment, T1, T2, T3, T4, T5, TResult> Function { get; private set; }
    }

    public class Environment : Dictionary<object, object>
    {
        private object[] GetBindings() { var bindings = this.Where(pair => !Equals(pair.Key, String.Empty)).Select(pair => new[] { pair.Key, pair.Value }); var keyed = new HashSet<object>(bindings.Select(pair => ((object[])pair)[0])); var bound = (Outer != null ? Outer.Bindings.Where(pair => !keyed.Contains(((object[])pair)[0])).Concat(bindings) : bindings).ToArray(); return bound; }
        private bool TryGet(object id, ref object value) { var key = id != null ? id.ToString() : null; if (key != null) { if (!ContainsKey(key)) { return Outer != null ? Outer.TryGet(key, ref value) : false; } else { value = key.Length > 0 ? this[key] : Bindings; return true; } } else return false; }
        public static readonly Builtin<object[], object> Bound = new Builtin<object[], object>(String.Empty, (@in, @params) => (@params != null) && (@params.Length > 0) ? @in.Get(@params[0]) : @in.Bindings);
        public Environment(Language language, Environment outer) : this(language, null as IDictionary<object, object>) { Outer = outer; }
        public Environment(Language language, IDictionary<object, object> builtins) { this[String.Empty] = Bound; Language = language; if (builtins != null) { builtins.Aggregate(this, (scope, pair) => { scope.Add(pair.Key, pair.Value); return scope; }); } }
        public object Invoke(object id, params object[] arguments) { var callable = Get(id) as Callable; if (callable == null) { throw Language.Error("not callable \"{0}\"", Syntax.ToString(id)); } var argv = new object[arguments != null ? arguments.Length + 1 : 1]; var argc = argv.Length; if (argc > 1) { Array.Copy(arguments, 0, argv, 1, argc - 1); } argv[0] = this; return callable.Invoke(argv); }
        public object Get(object id) { object value = null; if (!TryGet(id, ref value)) { throw Language.Error("undefined \"{0}\"", Syntax.ToString(id)); } return value; }
        public bool Has(object id) { object value = null; return TryGet(id, ref value); }
        public Language Language { get; private set; }
        public Environment Outer { get; private set; }
        public object[] Bindings { get { return GetBindings(); } }
    }

    public class Language
    {
        private Keyword test;

        private Type[] GetSignature(MethodInfo method)
        {
            var parameters = method.GetParameters();
            var length = parameters.Length;
            return parameters.Select(parameter => parameter.ParameterType).Concat(new[] { method.ReturnType }).ToArray();
        }

        private Type GetDelegateType(Type[] signature)
        {
            var delegateTypes = new[] { null, typeof(Func<,>), typeof(Func<,,>), typeof(Func<,,,>), typeof(Func<,,,,>), typeof(Func<,,,,,>), typeof(Func<,,,,,,>) };
            return delegateTypes[signature.Length - 1].MakeGenericType(signature);
        }

        private Type GetBuiltinType(Type[] signature)
        {
            var builtinTypes = new[] { null, typeof(Builtin<>), typeof(Builtin<,>), typeof(Builtin<,,>), typeof(Builtin<,,,>), typeof(Builtin<,,,,>), typeof(Builtin<,,,,,>) };
            return builtinTypes[signature.Length - 1].MakeGenericType(signature.Skip(1).ToArray());
        }

        private void AddBuiltin(IDictionary<object, object> builtins, object id, object value)
        {
            builtins.Add(id, value);
        }

        private IDictionary<object, object> GetReflectedBuiltins()
        {
            return
                GetType().
                GetMembers().
                Aggregate
                (
                    new Dictionary<object, object>(),
                    (reflected, member) =>
                    {
                        var attribute = member.GetCustomAttribute<BuiltinAttribute>(false);
                        string id;
                        if ((attribute != null) && !String.IsNullOrEmpty(id = attribute.Id))
                        {
                            var method = member as MethodInfo;
                            var field = member as FieldInfo;
                            object builtin;
                            if (method != null)
                            {
                                var signature = GetSignature(method);
                                var delegateType = GetDelegateType(signature);
                                var builtinType = GetBuiltinType(signature);
                                var @delegate = Delegate.CreateDelegate(delegateType, this, method);
                                builtin = Activator.CreateInstance(builtinType, id, @delegate);
                            }
                            else
                            {
                                if (field.IsInitOnly)
                                {
                                    builtin = field.GetValue(this);
                                }
                                else
                                {
                                    throw Error("field \"{0}\" must be read-only", field.Name);
                                }
                            }
                            AddBuiltin(reflected, id, builtin);
                        }
                        return reflected;
                    }
                );
        }

        private object Evaluate(string input, Environment environment)
        {
            return Evaluate(Syntax.Parse(input), environment);
        }

        private object Evaluate(object expression, Environment environment)
        {
            var list = expression as object[];
            var symbol = Symbol(expression);
            if (environment == null)
            {
                return Evaluate(expression, new Environment(this, Builtins));
            }
            else if (list != null)
            {
                object id;
                if ((list.Length > 0) && ((symbol = Symbol(list[0])) != null) && Keywords.ContainsKey(id = symbol.Id))
                {
                    return Keywords[id].Semantic(list, environment);
                }
                else
                {
                    int length;
                    list = list.Select(expr => Evaluate(expr, environment)).ToArray();
                    if (((length = list.Length) > 0) && ((symbol = Symbol(list[0])) != null) && (symbol is Callable))
                    {
                        var callable = (Callable)symbol;
                        var variadic = callable.Variadic;
                        var arguments = new object[variadic ? length - 1 : length];
                        if (length > 1)
                        {
                            Array.Copy(list, 1, arguments, variadic ? 0 : 1, length - 1);
                        }
                        if (variadic)
                        {
                            return callable.Invoke(environment, arguments);
                        }
                        else
                        {
                            arguments[0] = environment;
                            return callable.Invoke(arguments);
                        }
                    }
                    else
                    {
                        return list;
                    }
                }
            }
            else if (symbol != null)
            {
                return environment.Get(symbol);
            }
            else
            {
                return expression;
            }
        }

        protected Symbol Symbol(object value)
        {
            return value as Symbol;
        }

        public static object Const()
        {
            return Const(null);
        }

        public static object Const(object id)
        {
            return id ?? Guid.NewGuid().ToString("P");
        }

        public static Symbol New(object id)
        {
            return new Symbol(id);
        }

        public static KeyValuePair<object, Keyword> Keyword(string id, Semantic semantic)
        {
            return new KeyValuePair<object, Keyword>(id, new Keyword(id, semantic));
        }

        public static KeyValuePair<object, object> Builtin(string id, object value)
        {
            return new KeyValuePair<object, object>(id, value);
        }

        public static KeyValuePair<object, object> Builtin<TResult>(string id, Func<Environment, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<TResult>(id, function));
        }

        public static KeyValuePair<object, object> Builtin<T1, TResult>(string id, Func<Environment, T1, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<T1, TResult>(id, function));
        }

        public static KeyValuePair<object, object> Builtin<T1, T2, TResult>(string id, Func<Environment, T1, T2, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<T1, T2, TResult>(id, function));
        }

        public static KeyValuePair<object, object> Builtin<T1, T2, T3, TResult>(string id, Func<Environment, T1, T2, T3, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<T1, T2, T3, TResult>(id, function));
        }

        public static KeyValuePair<object, object> Builtin<T1, T2, T3, T4, TResult>(string id, Func<Environment, T1, T2, T3, T4, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<T1, T2, T3, T4, TResult>(id, function));
        }

        public static KeyValuePair<object, object> Builtin<T1, T2, T3, T4, T5, TResult>(string id, Func<Environment, T1, T2, T3, T4, T5, TResult> function)
        {
            return new KeyValuePair<object, object>(id, new Builtin<T1, T2, T3, T4, T5, TResult>(id, function));
        }

        public static Exception Error(string message, params object[] arguments)
        {
            return new Exception(String.Format(message, arguments));
        }

        public Language()
            : this(null)
        {
        }

        public Language(Syntax syntax)
        {
            Syntax = syntax ?? new Syntax();
            Keywords = new Dictionary<object, Keyword>();
            Builtins = new Dictionary<object, object>(GetReflectedBuiltins());
        }

        public object Const(object[] list, Environment outer)
        {
            return Const();
        }

        public object New(object[] list, Environment outer)
        {
            return New(Evaluate(list[1], outer));
        }

        public object Quote(object[] list, Environment outer)
        {
            return list[1];
        }

        public object List(object[] list, Environment outer)
        {
            return list.Skip(1).Select(item => Evaluate(item, outer)).ToArray();
        }

        public object Apply(object[] list, Environment outer)
        {
            var arguments = Evaluate(list[2], outer);
            arguments = !(arguments is object[]) ? new[] { arguments } : (object[])arguments;
            return Evaluate(new[] { list[1] }.Concat((object[])arguments).ToArray(), outer);
        }

        public object Lambda(object[] list, Environment outer)
        {
            var display = (object[])list[1];
            var formals = new Symbol[display.Length];
            for (var i = 0; i < formals.Length; i++)
            {
                formals[i] = Symbol(display[i]);
            }
            var @this = null as Lambda;
            @this =
                new Lambda
                (
                    formals,
                    delegate (object[] @params)
                    {
                        var environment = new Environment(this, outer);
                        var actual = @params.Length;
                        var length = formals.Length;
                        var i = 0;
                        while (i < length)
                        {
                            var formal = formals[i++];
                            if (i < actual)
                            {
                                environment[formal.Id] = @params[i];
                            }
                        }
                        environment["this"] = environment[@this.Id] = @this;
                        environment["params"] = @params.Skip(1).ToArray();
                        return Evaluate(list[2], environment);
                    }
                );
            return @this;
        }

        public object Let(object[] list, Environment outer)
        {
            var environment = new Environment(this, outer);
            var assignments = (object[])list[1];
            for (var i = 0; i < assignments.Length; i++)
            {
                var pair = (object[])assignments[i];
                environment[Symbol(pair[0]).Id] = Evaluate(pair[1], outer);
            }
            return Evaluate(list[2], environment);
        }

        public object Coalesce(object[] list, Environment outer)
        {
            test = test ?? Keywords.Values.First(keyword => keyword.Semantic == Test);
            return Test(new[] { test, new[] { test, list[1] }, list[1], list[2] }, outer);
        }

        public object Test(object[] list, Environment outer)
        {
            return
                list.Length > 2 ?
                (
                    (bool)Evaluate(list[1], outer) ? Evaluate(list[2], outer) : Evaluate(list[3], outer)
                )
                :
                outer.Has(list[1]);
        }

        public Language Include(KeyValuePair<object, Keyword> keywordDefinition)
        {
            Keywords.Add(keywordDefinition.Key, keywordDefinition.Value);
            return this;
        }

        public Language Include(params KeyValuePair<object, Keyword>[] keywordDefinitions)
        {
            foreach (var keywordDefinition in keywordDefinitions)
            {
                Include(keywordDefinition);
            }
            return this;
        }

        public Language Include(KeyValuePair<object, object> builtinDefinition)
        {
            AddBuiltin(Builtins, builtinDefinition.Key, builtinDefinition.Value);
            return this;
        }

        public Language Include(params KeyValuePair<object, object>[] builtinDefinitions)
        {
            foreach (var builtinDefinition in builtinDefinitions)
            {
                Include(builtinDefinition);
            }
            return this;
        }

        public object Evaluate(string input)
        {
            return Evaluate(input, null as object[]);
        }

        public object Evaluate(string input, params object[] arguments)
        {
            return Evaluate((arguments != null) && (arguments.Length > 0) ? String.Format(input, arguments) : input, null as Environment);
        }

        public object Evaluate(object expression)
        {
            return Evaluate(expression, null);
        }

        public Syntax Syntax { get; private set; }

        public IDictionary<object, Keyword> Keywords { get; private set; }

        public IDictionary<object, object> Builtins { get; private set; }
    }

    public class MyLanguage : Language
    {
        private class EqualityComparer : IEqualityComparer<object>
        {
            internal bool Equal(object x, object y)
            {
                return
                    Equals(x, y) ||
                    (
                        (x != null) &&
                        (y != null) &&
                        (
                            (x is object[]) &&
                            (y is object[]) &&
                            ((object[])x).SequenceEqual((object[])y, this)
                        )
                    );
            }

            bool IEqualityComparer<object>.Equals(object x, object y)
            {
                return Equal(x, y);
            }

            int IEqualityComparer<object>.GetHashCode(object obj)
            {
                return obj != null ? obj.GetHashCode() : 0;
            }
        }

        private static readonly EqualityComparer Equality = new EqualityComparer();

        [Builtin("void")]
        public readonly Type @void = typeof(void);

        [Builtin("null")]
        public readonly object @null = null;

        [Builtin("false")]
        public readonly bool @false = false;

        [Builtin("true")]
        public readonly bool @true = true;

        [Builtin("typeof")]
        public Type @typeof(Environment environment, object value) => value != null ? value.GetType() : @void;

        [Builtin("string")]
        public string @string(Environment environment, object value) => Syntax.ToString(value);

        [Builtin("format")]
        public string format(Environment environment, string template, object[] arguments) => String.Format(template, arguments);

        [Builtin("!=")]
        public bool notEqual(Environment environment, object left, object right) => !equal(null, left, right);

        [Builtin("==")]
        public bool equal(Environment environment, object left, object right) => Equality.Equal(left, right);

        [Builtin("&&")]
        public bool and(Environment environment, bool left, bool right) => left && right;

        [Builtin("||")]
        public bool or(Environment environment, bool left, bool right) => left || right;

        [Builtin("!")]
        public bool not(Environment environment, bool value) => !value;

        [Builtin("+")]
        public object add(Environment environment, object[] @params) =>
            @params[0] is string ?
            (object)String.Concat(@params)
            :
            (int)@params[0] + (int)@params[1];

        [Builtin("-")]
        public int subtract(Environment environment, int left, int right) => left - right;

        [Builtin("*")]
        public int multiply(Environment environment, int left, int right) => left * right;

        [Builtin("/")]
        public int divide(Environment environment, int left, int right) => left / right;

        [Builtin("%")]
        public int modulo(Environment environment, int left, int right) => left % right;
    }

    class Program
    {
        static void Main(string[] args)
        {
            var language = new MyLanguage();

            language.
                Syntax.
                Include
                (
                    Syntax.Token("const", Syntax.Symbol, 0),
                    Syntax.Token("new", Syntax.Symbol, 0),
                    Syntax.Token("'", Syntax.Symbol),
                    Syntax.Token(":", Syntax.Symbol),
                    Syntax.Token(".", Syntax.Symbol),
                    Syntax.Token("=>", Syntax.Symbol),
                    Syntax.Token("=", Syntax.Symbol),
                    Syntax.Token("??", Syntax.Symbol),
                    Syntax.Token("?", Syntax.Symbol),

                    Syntax.Token("==", Syntax.Symbol, true),
                    Syntax.Token("!=", Syntax.Symbol)
                ).
                Include
                (
                    Syntax.Lexical("false", Syntax.Symbol),
                    Syntax.Lexical("true", Syntax.Symbol),
                    Syntax.Lexical("null", Syntax.Symbol),

                    Syntax.Lexical("[0-9]+", s => int.Parse(s)),
                    Syntax.Lexical("\\\"(\\\\\\n|\\\\t|\\\\n|\\\\r|\\\\\\\"|[^\\\"])*\\\"", s => s.Substring(1, s.Length - 2)),

                    Syntax.Lexical("[\\$_A-Za-z][\\.\\$_0-9A-Za-z\\-\\!]*", Syntax.Symbol),

                    Syntax.Lexical("\\&\\&", Syntax.Symbol),
                    Syntax.Lexical("\\|\\|", Syntax.Symbol),
                    Syntax.Lexical("\\!", Syntax.Symbol),

                    Syntax.Lexical("[\\+\\-\\*\\/\\%]", Syntax.Symbol)
                );

            language.
                Include
                (
                    Language.Keyword("const", language.Const),
                    Language.Keyword("new", language.New),
                    Language.Keyword("'", language.Quote),
                    Language.Keyword(":", language.List),
                    Language.Keyword(".", language.Apply),
                    Language.Keyword("=>", language.Lambda),
                    Language.Keyword("=", language.Let),
                    Language.Keyword("??", language.Coalesce),
                    Language.Keyword("?", language.Test)
                ).
                Include
                (
                    Language.Builtin("write", (Environment environment, object value) => { Console.Write(value = [email protected](environment, value)); return value; }),
                    Language.Builtin("writeln", (Environment environment, object value) => { Console.WriteLine(value = [email protected](environment, value)); return value; }),

                    Language.Builtin("sum", (Environment environment, object[] @params) =>
                        @params[0] is object[] ?
                        ((object[])@params[0]).Cast<int>().Sum()
                        :
                        @params.Cast<int>().Sum()
                    ),
                    Language.Builtin("length", (Environment environment, object value) =>
                        !(value is object[]) ?
                        (
                            value is string ?
                            (object)((string)value).Length
                            :
                            null
                        )
                        :
                        ((object[])value).Length
                    ),
                    Language.Builtin("add", (Environment environment, object[] list, object value) => list != null ? list.Concat(new[] { value }).ToArray() : null),
                    Language.Builtin("any", (Environment environment, object[] list, Callable filter) => (list != null) && (filter != null) ? (object)list.Any(item => (bool)filter.Invoke(environment, item)) : null),
                    Language.Builtin("concat", (Environment environment, object[] left, object[] right) => (left != null) && (right != null) ? left.Concat(right).ToArray() : null),
                    Language.Builtin("first", (Environment environment, object[] list) => (list != null) && (list.Length > 0) ? list[0] : null),
                    Language.Builtin("head", (Environment environment, object[] list) => environment.Invoke("first", new[] { list })),
                    Language.Builtin("last", (Environment environment, object[] list) => list != null ? environment.Invoke("first", new[] { list.Reverse().ToArray() }) : null),
                    Language.Builtin("skip", (Environment environment, object[] list, int count) => (list != null) && (list.Length > 0) ? list.Skip(count).ToArray() : null),
                    Language.Builtin("remaining", (Environment environment, object[] list) => environment.Invoke("skip", list, 1)),
                    Language.Builtin("tail", (Environment environment, object[] list) => environment.Invoke("remaining", new[] { list })),
                    Language.Builtin("select", (Environment environment, object[] list, Callable mapper) =>
                        mapper != null ?
                        (list != null ? list.Select(item => mapper.Invoke(environment, item)).ToArray() : null)
                        :
                        null
                    ),
                    Language.Builtin("where", (Environment environment, object[] list, Callable filter) =>
                        filter != null ?
                        (
                            filter.Length > 1 ?
                            (list != null ? list.Where((item, index) => (bool)filter.Invoke(environment, item, index)).ToArray() : null)
                            :
                            (list != null ? list.Where(item => (bool)filter.Invoke(environment, item)).ToArray() : null)
                        )
                        :
                        null
                    )
                );

            language.Evaluate(@"( writeln ( == ( typeof null ) void ) )");
            Console.WriteLine();

            language.
                Evaluate
                (@"
                    (
                        ( writeln ( sum ( ) ) )
                        ( writeln ( sum 1 ) )
                        ( writeln ( sum ( 1 2 ) ) )
                        ( writeln ( sum 1 2 3 ) )
                    )
                ");
            Console.WriteLine();

            /*
this       is
a               multi
line                       text
constant                               demo
"with"some"quotes
            */
            language.
                Evaluate
                (@"
                    ( writeln
                        ""this\tis\r\na\t\tmulti\nline\t\t\ttext\
constant\t\t\t\tdemo\n\""with\""some\""quotes""
                    )
                ");
            Console.WriteLine();

            language.
                Evaluate
                (@"
                    ( =
                        (
                            (
                                until
                                ( =>
                                    ( n f ) (
                                        ? ( != n 0 )
                                        ( concat ( this ( - n 1 ) f ) ( : ( : n ( f n ) ) ) )
                                        ( : ( : 0 ( f 0 ) ) )
                                    )
                                )
                            )
                            (
                                n!
                                ( =>
                                    ( n ) (
                                        ? ( != n 0 )
                                        ( * n ( this ( - n 1 ) ) )
                                        1
                                    )
                                )
                            )
                        )
                        (
                            writeln
                            ( . + (
                                    select
                                    ( until 12 n! )
                                    ( =>
                                        ( p ) ( =
                                            (
                                                ( n ( first p ) )
                                                ( v ( last p ) )
                                            )
                                            ( format ""\r\n{0}! = {1}"" ( n v ) )
                                        )
                                    )
                                )
                            )
                        )
                    )
                ");
            Console.WriteLine();
            Console.WriteLine("...");
            Console.WriteLine();

            var factorial = (Lambda)language.
                Evaluate
                (@"
                    ( => ( n ) (
                            ? ( != n 0 )
                            ( * n ( this ( - n 1 ) ) )
                            1
                        )
                    )
                ");

            var sw = new System.Diagnostics.Stopwatch();
            var n = 12;
            var r = 0;
            int k;
            sw.Start();
            for (k = 0; k < 10000; k++)
            {
                r = (int)factorial.Invoke(null, n);
            }
            sw.Stop();
            Console.WriteLine("{0}! = {1}", n, r);
            Console.WriteLine();
            Console.WriteLine("in {0} ms (for {1} times)", sw.ElapsedMilliseconds, k.ToString("0,0"));
            Console.WriteLine();

            //Console.ReadKey();
        }
    }
}