Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
namespace sharplisp
{
public static class Ext
{
public static void Each<T>(this IEnumerable els, Action<T, int> a)
{
var i = 0;
foreach (T e in els)
{
a(e, i++);
}
}
}
class SharpLisp
{
class Env : Dictionary<string, object>
{
private readonly Env _outer;
public Env(IEnumerable<object> keys = null, IEnumerable<object> values = null, Env outer = null)
{
if (keys != null && values != null)
{
keys.Each<string>((s, i) => Add(s, values.ElementAt(i)));
}
_outer = outer;
}
public Env Find(object var)
{
if (Keys.Contains(var))
{
return this;
}
if (_outer != null)
{
return _outer.Find(var);
}
throw new Exception(string.Format("undefined variable: {0}", var));
}
}
static Stack<string> Tokenize(string input)
{
return new Stack<string>(input.Replace("(", " ( ").Replace(")", " ) ")
.Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Reverse());
}
static object Parse(Stack<string> tokens)
{
if (!tokens.Any())
{
throw new Exception("unexpected EOF");
}
var token = tokens.Pop();
if (token == "(")
{
var expression = new List<object>();
while (tokens.Peek() != ")")
{
expression.Add(Parse(tokens));
}
tokens.Pop();
return expression;
}
if (token == ")")
{
throw new Exception("unexpected )");
}
return token;
}
static bool IsString(object x)
{
var symbol = x as string;
return (symbol != null);
}
static bool IsAtom(object x)
{
if (x is int)
{
return true;
}
var symbol = x as string;
if (symbol != null)
{
int intValue;
if (int.TryParse(symbol, out intValue))
{
return true;
}
float floatValue;
if (float.TryParse(symbol, NumberStyles.Float, CultureInfo.InvariantCulture, out floatValue))
{
return true;
}
}
return false;
}
static float FloatValue(object x)
{
var symbol = Convert.ToString(x);
try
{
return float.Parse(symbol, NumberStyles.Float, CultureInfo.InvariantCulture);
}
catch (FormatException)
{
throw new Exception(string.Format("Invalid float value: {0}", symbol));
}
}
static List<object> ListRef(object x)
{
return (List<object>)x;
}
static object Eval(object x, Env environment)
{
if (IsString(x))
{
var symbol = (string)x;
return IsAtom(x) ? x : environment.Find(x)[symbol];
}
var list = x as List<object>;
if (list == null)
{
return x;
}
var expression = list[0] as string;
if (expression == "quote")
{
var cdr = list.Skip(1).ToList();
switch (cdr.Count)
{
case 1:
return cdr[0];
default:
throw new Exception("quote: invalid");
}
}
if (expression == "if")
{
var test = list[1];
var conseq = list[2];
var alt = list[3];
var branch = Eval(test, environment);
return Eval(branch != null ? conseq : alt, environment);
}
switch (expression)
{
case "set!":
{
var var = (string)list[1];
var exp = list[2];
environment.Find(list[1])[var] = Eval(exp, environment);
}
break;
case "define":
{
var var = (string)list[1];
var exp = list[2];
environment[var] = Eval(exp, environment);
}
break;
case "lambda":
{
var vars = list[1] as List<object>;
var exp = list[2];
Func<List<object>, object> lambda = args => Eval(exp, new Env(vars, args, environment));
return lambda;
}
case "begin":
{
object val = null;
foreach (var exp in list.Skip(1).ToList())
{
val = Eval(exp, environment);
}
return val;
}
default:
{
var exps = new Stack<object>();
list.Reverse();
foreach (var exp in list)
{
exps.Push(Eval(exp, environment));
}
var proc = exps.Pop() as Func<List<object>, object>;
return proc(exps.ToList());
}
}
return null;
}
static string Datum(object expression)
{
if (!(expression is List<object>))
{
if (expression is bool)
{
return (bool)expression ? "#t" : "#f";
}
return Convert.ToString(expression);
}
return "(" + string.Join(" ", (ListRef(expression).Select(a => IsAtom(a) ? a : Datum(a))).ToArray()) + ")";
}
static void Main(string[] args)
{
var env = new Env();
Func<List<object>, object> mul = list => list.Aggregate((a, x) => FloatValue(a) * FloatValue(x));
Func<List<object>, object> add = list => list.Aggregate((a, x) => FloatValue(a) + FloatValue(x));
Func<List<object>, object> sub = list => list.Aggregate((a, x) => FloatValue(a) - FloatValue(x));
Func<List<object>, object> div = list => list.Aggregate((a, x) => FloatValue(a) / FloatValue(x));
Func<List<object>, object> not = list => !((bool)list[0]);
Func<List<object>, object> gt = list => FloatValue(list[0]) > FloatValue(list[1]);
Func<List<object>, object> lt = list => FloatValue(list[0]) < FloatValue(list[1]);
Func<List<object>, object> ge = list => FloatValue(list[0]) >= FloatValue(list[1]);
Func<List<object>, object> le = list => FloatValue(list[0]) <= FloatValue(list[1]);
Func<List<object>, object> eq = list => FloatValue(list[0]).Equals(FloatValue(list[1]));
Func<List<object>, object> newlist = ListRef;
Func<List<object>, object> car = l =>
{
if (ListRef(l[0]).Count > 0)
{
return ListRef(l[0])[0];
}
throw new Exception("Empty list");
};
Func<List<object>, object> cdr = l =>
{
if (ListRef(l[0]).Count > 0)
{
return ListRef(l[0]).Skip(1).ToList();
}
throw new Exception("Empty list");
};
Func<List<object>, object> len = list => ListRef(list[0]).Count;
Func<List<object>, object> islist = list => list[0] is List<object>;
Func<List<object>, object> append = list =>
{
var dest = ListRef(list[0]);
var src = ListRef(list[1]);
dest.AddRange(src);
return dest;
};
Func<List<object>, object> cons = list =>
{
var res = new List<object>
{
ListRef(list[0]).Count == 1? ListRef(list[0])[0] : ListRef(list[0]),
ListRef(list[1]).Count == 1? ListRef(list[1])[0] : ListRef(list[1])
};
return res;
};
Func<List<object>, object> isnull = list => !IsAtom(list[0]) && ListRef(list[0]).Count == 0;
Func<List<object>, object> issymbol = list => !IsAtom(list[0]) && IsString(list[0]);
env.Add("*", mul);
env.Add("+", add);
env.Add("-", sub);
env.Add("/", div);
env.Add("not", not);
env.Add(">", gt);
env.Add("<", lt);
env.Add(">=", ge);
env.Add("<=", le);
env.Add("=", eq);
env.Add("equal?", eq);
env.Add("list", newlist);
env.Add("list?", islist);
env.Add("car", car);
env.Add("cdr", cdr);
env.Add("length", len);
env.Add("append", append);
env.Add("null?", isnull);
env.Add("symbol?", issymbol);
env.Add("cons", cons);
while (true)
{
Console.Write("> ");
try
{
var ret = Eval(Parse(Tokenize(Console.ReadLine())), env);
if (ret != null)
{
Console.WriteLine(Datum(ret));
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.