#include <string>
#include <iostream>
#include <vector>
#include <stdio.h>

const int nil=0, pointer=1, number=2, symbol=3, punctuation=4;

struct value
{ int tag;
  int what;
  value() { tag=nil, what=0; }
  value(int t, int w) { tag=t; what=w; } };

struct cell
{ value head, tail; };

cell * heap = NULL;

struct entry
{ string name;
  value v;
  entry(): v(nil, 0) { } };

vector<entry> symboltable;
value construct(value a, value b);

vector<FILE *> inputs;

int findsymbol(string s)
{ for (int i=0; i<symboltable.size(); i+=1)
  { if (symboltable[i].name == s)
      return  i; }
  entry e;
  e.name = s;
  int index = symboltable.size();
  e.v = value(nil, 0);
  symboltable.push_back(e);
  return index; }

void set_in_symbol_table(int index, value newv)
{ if (symboltable[index].v.tag == nil)
    symboltable[index].v = construct(newv, symboltable[index].v);
  else
    heap[symboltable[index].v.what].head = newv; }

void push_in_symbol_table(int index, value newv)
{ symboltable[index].v = construct(newv, symboltable[index].v); }

value tailof(value v);

void pop_from_symbol_table(int index)
{ symboltable[index].v = tailof(symboltable[index].v); }

value get_from_symbol_table(int index)
{ if (symboltable[index].v.tag == nil)
    return value(symbol, index);
  else
    return heap[symboltable[index].v.what].head; }

int s_add, s_mul, s_div, s_sub, s_cons, s_head, s_tail, s_if, s_set,
    s_true, s_false, s_eq, s_less, s_while, s_seq, s_print, s_read, s_,
    s_quote, s_eval, s_char, s_isnil, s_iscell, s_isnum, s_more, s_noteq,
    s_lesseq, s_moreeq, s_and, s_or, s_not, s_mod, s_local, s_function,
    s_list, s_load, s_free;

void primesymbols()
{ s_add = findsymbol("add");
  s_sub = findsymbol("sub");
  s_mul = findsymbol("mul");
  s_div = findsymbol("div");
  s_mod = findsymbol("mod");
  s_cons = findsymbol("cons");
  s_head = findsymbol("head");
  s_tail = findsymbol("tail");
  s_set = findsymbol("set");
  s_true = findsymbol("true");
  s_false = findsymbol("false");
  s_eq = findsymbol("eq");
  s_less = findsymbol("less");
  s_more = findsymbol("more");
  s_moreeq = findsymbol("moreeq");
  s_lesseq = findsymbol("lesseq");
  s_noteq = findsymbol("noteq");
  s_or = findsymbol("or");
  s_and = findsymbol("and");
  s_not = findsymbol("not");
  s_local = findsymbol("local");
  s_function = findsymbol("function");
  s_ = findsymbol("");
  s_free = findsymbol("free");
  s_load = findsymbol("load");
  s_list = findsymbol("list");
  s_char = findsymbol("char");
  s_isnil = findsymbol("isnil");
  s_iscell = findsymbol("iscell");
  s_isnum = findsymbol("isnum");
  s_quote = findsymbol("quote");
  s_eval = findsymbol("eval");
  s_while = findsymbol("while");
  s_seq = findsymbol("seq");
  s_print = findsymbol("print");
  s_read = findsymbol("read");
  s_if = findsymbol("if"); }

bool issymbol(value a, int s)
{ if (a.tag!=symbol)
    return false;
  return a.what == s; }

bool iscell(value a)
{ return a.tag==pointer; }

value freelist;

value construct(value a, value b)
{ value n = freelist;
  if (freelist.tag == nil)
  { cerr << "out of memory\n";
    exit(1); }
  freelist = heap[freelist.what].tail;
  heap[n.what].head = a;
  heap[n.what].tail = b;
  return n; }

value read();

value restoflist()
{ value a = read();
  if (a.tag==punctuation && a.what==')')
    return value(nil, 0);
  value b = restoflist();
  return construct(a, b); }

value read()
{ int c=' ';
  while (true)
  { while (c==' ' || c=='\n')
      c=getchar();
    if (c==';')
    { while (c!=EOF && c!='\n')
        c=getchar();
      continue; }
    if (c!=EOF)
      break;
    if (inputs.size()==0)
      exit(0);
    fclose(stdin);
    stdin = inputs.back();
    inputs.pop_back();
    c=' '; }
  string s="";
  if (c>='0' && c<='9')
  { while (c>='0' && c<='9')
    { s+=(char)c;
      c=getchar(); }
    ungetc(c, stdin);
    return value(number, atol(s.c_str())); }
  else if (c>='a' && c<='z')
  { while (c>='a' && c<='z')
    { s+=(char)c;
      c=getchar(); }
    ungetc(c, stdin);
    if (s=="nil")
      return value(nil, 0);
    return value(symbol, findsymbol(s)); }
  if (c=='(')
    return restoflist();
  else
    return value(punctuation, c);
  return value(nil, 0); }

void print(ostream & out, value v)
{ if (v.tag==nil)
    out << "nil";
  else if (v.tag==number)
    out << v.what;
  else if (v.tag==symbol)
    out << symboltable[v.what].name;
  else if (v.tag==punctuation)
    out << (char)v.what;
  else if (v.tag==pointer)
  { out << "( ";
    while (v.tag == pointer)
    { print(out, heap[v.what].head);
      out << " ";
      v = heap[v.what].tail; }
    if (v.tag != nil)
    { out << "| ";
      print(out, v);
      out << " "; }
    out << ")"; }
  else
    out << "???"; }

ostream & operator<<(ostream & out, const value & v)
{ print(out, v);
  return out; }

value headof(value v)
{ if (v.tag!=pointer)
    return value(nil, 0);
  return heap[v.what].head; }

void setheadof(value c, value v)
{ if (c.tag!=pointer)
    printf("not a cell in setheadof\n");
  else
    heap[c.what].head = v; }

value tailof(value v)
{ if (v.tag!=pointer)
    return value(nil, 0);
  return heap[v.what].tail; }

void settailof(value c, value v)
{ if (c.tag!=pointer)
    printf("not a cell in settailof\n");
  else
    heap[c.what].tail = v; }

value secondof(value v)
{ return headof(tailof(v)); }

value thirdof(value v)
{ return headof(tailof(tailof(v))); }

value fourthof(value v)
{ return headof(tailof(tailof(tailof(v)))); }

value evaluate(value x)
{ if (x.tag == symbol)
    return get_from_symbol_table(x.what);
  else if (x.tag != pointer)
    return x;
  value op = evaluate(headof(x));

  if (iscell(op) && issymbol(headof(op), s_function))
  { value paramnames = secondof(op);
    value body = thirdof(op);
    value paramexprs = tailof(x);
    value paramvals = value(nil, 0);
    value lastval = value(nil, 0);

    while (paramexprs.tag!=nil)
    { value thisval = evaluate(headof(paramexprs));
      value newlink = construct(thisval, value(nil, 0));
      if (lastval.tag==nil)
        paramvals = newlink;
      else
        settailof(lastval, newlink);
      lastval = newlink;
      paramexprs = tailof(paramexprs); }

    while (paramnames.tag!=nil)
    { value thisparam = headof(paramnames);
      value thisval = headof(paramvals);
      push_in_symbol_table(thisparam.what, thisval);
      paramvals = tailof(paramvals);
      paramnames = tailof(paramnames); }

    value answer = evaluate(body);

    paramnames = secondof(op);
    while (paramnames.tag!=nil)
    { value thisvar = headof(paramnames);
      pop_from_symbol_table(thisvar.what);
      paramnames = tailof(paramnames); } 

    return answer; }

  else if (issymbol(op, s_add))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in add\n";
      return value(number, 0); }
    return value(number, a.what+b.what); }

  else if (issymbol(op, s_sub))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in sub\n";
      return value(number, 0); }
    return value(number, a.what-b.what); }

  else if (issymbol(op, s_mul))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in mul\n";
      return value(number, 0); }
    return value(number, a.what*b.what); }

  else if (issymbol(op, s_div))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in div\n";
      return value(number, 0); }
    if (b.what==0)
    { cout << "division by zero\n";
      return value(nil, 0); }
    return value(number, a.what/b.what); }

  else if (issymbol(op, s_mod))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in mod\n";
      return value(number, 0); }
    if (b.what==0)
    { cout << "division (mod) by zero\n";
      return value(nil, 0); }
    return value(number, a.what%b.what); }

  else if (issymbol(op, s_cons))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    return construct(a, b); }

  else if (issymbol(op, s_head))
  { value a = evaluate(secondof(x));
    if (a.tag!=pointer)
    { cout << "not cell in head, but ** " << secondof(x) << " -> " << a << " **\n";
      return value(nil, 0); }
    return headof(a); }

  else if (issymbol(op, s_tail))
  { value a = evaluate(secondof(x));
    if (a.tag!=pointer)
    { cout << "not cell in tail\n";
      return value(nil, 0); }
    return tailof(a); }

  else if (issymbol(op, s_set))
  { value a = secondof(x);
    value b = evaluate(thirdof(x));
    if (a.tag!=symbol)
    { cout << "not symbol in set\n";
      return value(nil, 0); }
    set_in_symbol_table(a.what, b);
    return a; }

  else if (issymbol(op, s_eq))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag==b.tag && a.what==b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_noteq))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=b.tag && a.what!=b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_less))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in less\n";
      return value(number, 0); }
    if (a.what<b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_more))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in more\n";
      return value(number, 0); }
    if (a.what>b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_lesseq))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in lesseq\n";
      return value(number, 0); }
    if (a.what<=b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_moreeq))
  { value a = evaluate(secondof(x));
    value b = evaluate(thirdof(x));
    if (a.tag!=number || b.tag!=number)
    { cout << "not numbers in moreeq\n";
      return value(number, 0); }
    if (a.what>=b.what)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_if))
  { value a = evaluate(secondof(x));
    value b = thirdof(x);
    value c = fourthof(x);
    if (issymbol(a, s_true))
      return evaluate(b);
    if (issymbol(a, s_false))
      return evaluate(c);
    cout << "not true or false in if\n";
    return value(number, 0); }

  else if (issymbol(op, s_not))
  { value a = evaluate(secondof(x));
    if (issymbol(a, s_true))
      return value(symbol, s_false);
    if (issymbol(a, s_false))
      return value(symbol, s_true);
    cout << "not true or false in not\n";
    return value(number, 0); }

  else if (issymbol(op, s_and))
  { value a = evaluate(secondof(x));
    value b = thirdof(x);
    if (issymbol(a, s_true))
      return evaluate(b);
    if (issymbol(a, s_false))
      return value(symbol, s_false);
    cout << "not true or false in and\n";
    return value(number, 0); }

  else if (issymbol(op, s_or))
  { value a = evaluate(secondof(x));
    value b = thirdof(x);
    if (issymbol(a, s_false))
      return evaluate(b);
    if (issymbol(a, s_true))
      return value(symbol, s_true);
    cout << "not true or false in or\n";
    return value(number, 0); }

  else if (issymbol(op, s_read))
  { return read(); }

  else if (issymbol(op, s_print))
  { value a = evaluate(secondof(x));
    cout << a;
    return a; }

  else if (issymbol(op, s_seq))
  { value curr = tailof(x), last=value(nil, 0);
    while (curr.tag!=nil)
    { last=evaluate(headof(curr));
      curr=tailof(curr); }
    return last; }

  else if (issymbol(op, s_while))
  { value cond = secondof(x), body = thirdof(x), last = value(nil, 0);
    while (true)
    { value b = evaluate(cond);
      if (issymbol(b, s_false))
        break;
      else if (! issymbol(b, s_true))
      { cout << "not true or false in while\n";
        break; }
      last = evaluate(body); }
    return last; }

  else if (issymbol(op, s_quote))
  { return secondof(x); }

  else if (issymbol(op, s_function))
  { return x; }

  else if (issymbol(op, s_eval))
  { return evaluate(evaluate(secondof(x))); }

  else if (issymbol(op, s_char))
  { value a = evaluate(secondof(x));
    if (a.tag!=number)
    { cout << "not number in char\n";
      return value(nil, 0); }
    return value(punctuation, a.what); }

  else if (issymbol(op, s_isnil))
  { value a = evaluate(secondof(x));
    if (a.tag==nil)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_iscell))
  { value a = evaluate(secondof(x));
    if (a.tag==pointer)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_isnum))
  { value a = evaluate(secondof(x));
    if (a.tag==number)
      return value(symbol, s_true);
    else
      return value(symbol, s_false); }

  else if (issymbol(op, s_load))
  { value name = secondof(x);
    if (name.tag!=symbol)
    { printf("not a name in load\n");
      return value(nil, 0); }
    FILE * f = fopen(symboltable[name.what].name.c_str(), "r");
    if (f==NULL)
    { printf("can't read file\n");
      return value(nil, 0); }
    inputs.push_back(stdin);
    stdin = f;
    return value(symbol, s_true); }

  else if (issymbol(op, s_list))
  { x = tailof(x);
    if (x.tag==nil)
      return value(nil, 0);
    value first = construct(value(nil, 0), value(nil, 0));
    value last = first;
    while (true)
    { setheadof(last, evaluate(headof(x)));
      x = tailof(x);
      if (x.tag==nil)
        break;
      settailof(last, construct(value(nil, 0), value(nil, 0)));
      last = tailof(last); }
    return first; }

  else if (issymbol(op, s_local))
  { value vars = secondof(x);
    while (vars.tag!=nil)
    { value thisvar = headof(vars);
      push_in_symbol_table(thisvar.what, value(nil, 0));
      vars = tailof(vars); }
    value answer = evaluate(thirdof(x));
    vars = secondof(x);
    while (vars.tag!=nil)
    { value thisvar = headof(vars);
      pop_from_symbol_table(thisvar.what);
      vars = tailof(vars); }
    return answer; }

  else
  { cout << "Not a function: " << x << "\n";
    return value(nil, 0); } }

void main()
{ int heapsize = 10000;
  heap = new cell[heapsize];
  for (int i=0; i<heapsize; i+=1)
  { heap[i].head = value(symbol, s_free);
    heap[i].tail = value(pointer, i+1); }
  heap[heapsize-1].head = value(symbol, s_free);
  heap[heapsize-1].tail = value(nil, 0);
  freelist = value(pointer, 0);
  primesymbols();
  while (1)
  { cout << "> ";
    value v = read();
    v = evaluate(v);
    cout << v << "\n"; } }