/*
 * Copyright (c) 2009  Henry Strickland.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of Henry Strickland
 *    may not be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY HENRY STRICKLAND ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL HENRY STRICKLAND BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <assert.h>
#include <stdio.h>

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;
typedef unsigned long word;  // big enough to hold a pointer
const word LOBIT = 1;

typedef struct SNode {
  struct SNode *left, *right;
  SNode(SNode* l, SNode* r) : left(l), right(r) {}
} *sn;

typedef sn (*PrimFunc)(sn env, sn args);

typedef struct Symbol {
  const string name;
  sn global;
  PrimFunc prim;
  Symbol(const string& n) : name(n), global(NULL), prim(NULL) {}
} *sym;

typedef map<string, sym> SymTable;
SymTable Syms;

sym Intern(const string& s) {
  SymTable::iterator it = Syms.find(s);
  if (it == Syms.end()) {
    sym p = new Symbol(s);
    Syms[s] = p;
    return p;
  } else {
    return it->second;
  }
}

sn NIL, T, LAMBDA, QUOTE, BIND, UNBIND, APPLY, EVAL, PRIM, IF;
sn CAR, CDR, CONS, NULL_, EQ, ATOMP, LIST;

bool atomp(sn x) { return (1 == (1&word(x))); }
bool consp(sn x) { return (0 == (1&word(x))); }
bool listp(sn x) { return (x == NIL || consp(x)); }
void CheckAtom(sn x) { assert(atomp(x)); }
void CheckCons(sn x) { assert(consp(x)); }
void CheckList(sn x) { assert(listp(x)); }
sn Atom(const string& s) { return sn(LOBIT|word(Intern(s))); }
sym AtomSym(sn x) { CheckAtom(x); return sym(~LOBIT&word(x)); }
string AtomName(sn x) { return AtomSym(x)->name; }

sn car(sn x) { CheckCons(x); return x->left; }
sn cdr(sn x) { CheckCons(x); return x->right; }
sn cons(sn l, sn r) { return new SNode(l, r); }
bool null(sn x) { CheckList(x); return x == NIL; }
bool not_(sn x) { return x == NIL; }

sn cadr(sn x) { return car(cdr(x)); }
sn cddr(sn x) { return cdr(cdr(x)); }
sn caddr(sn x) { return car(cdr(cdr(x))); }
sn cadddr(sn x) { return car(cdr(cdr(cdr(x)))); }
sn list1(sn x) { return cons(x, NIL); }
sn list2(sn x, sn y) { return cons(x, cons(y, NIL)); }
sn list3(sn x, sn y, sn z) { return cons(x, cons(y, cons(z, NIL))); }
sn list4(sn x, sn y, sn z, sn a) { return cons(x, cons(y, cons(z, cons(a, NIL)))); }
sn list5(sn x, sn y, sn z, sn a, sn b) { return cons(x, cons(y, cons(z, cons(a, cons(b, NIL))))); }
sn list6(sn x, sn y, sn z, sn a, sn b, sn c) { return cons(x, cons(y, cons(z, cons(a, cons(b, cons(c, NIL)))))); }

string Str(sn x) {
  if (atomp(x)) return AtomName(x); // Todo: escape
  string z = "( ";
  while (x != NIL) {
    z += Str(car(x)) + " ";
    x = cdr(x);
  }
  return z + ")";
}

sn Lookup(sn env, sn x) {
  CheckList(env);
  CheckAtom(x);
  while (env != NIL) {
    if (car(env) == x) return cadr(env);
    env = cddr(env);
  }
  sym s = AtomSym(x);
  if (s->global) return s->global;

  cerr << "LOOKUP NOT FOUND: " << AtomName(x) << "\n";
  assert(0);
}

sn PrimCar(sn env, sn args) {
  cerr << "PrimCar: " << Str(args) << "\n";
  CheckCons(args);
  assert(cdr(args) == NIL);
  sn a1 = car(args);
  return car(a1);
}
sn PrimCdr(sn env, sn args) {
  cerr << "PrimCdr: " << Str(args) << "\n";
  CheckCons(args);
  assert(cdr(args) == NIL);
  sn a1 = car(args);
  return cdr(a1);
}
sn PrimCons(sn env, sn args) {
  cerr << "PrimCons: " << Str(args) << "\n";
  CheckCons(args);
  assert(cddr(args) == NIL);
  sn a1 = car(args);
  sn a2 = cadr(args);
  return cons(a1, a2);
}
sn PrimNull(sn env, sn args) {
  cerr << "PrimNull: " << Str(args) << "\n";
  CheckCons(args);
  assert(cdr(args) == NIL);
  sn a1 = car(args);
  return null(a1) ? T : NIL;
}
sn PrimAtomp(sn env, sn args) {
  cerr << "PrimAtomp: " << Str(args) << "\n";
  CheckCons(args);
  assert(cdr(args) == NIL);
  sn a1 = car(args);
  return atomp(a1) ? T : NIL;
}
sn PrimEq(sn env, sn args) {
  cerr << "PrimEq: " << Str(args) << "\n";
  CheckCons(args);
  assert(cddr(args) == NIL);
  sn a1 = car(args);
  sn a2 = cadr(args);
  return a1 == a2 ? T : NIL;
}
sn PrimList(sn env, sn args) {
  cerr << "PrimList: " << Str(args) << "\n";
  CheckList(args);
  return args;
}

void InitAtoms() {
  NIL = Atom("nil");
  T = Atom("t");
  LAMBDA = Atom("lambda");
  QUOTE = Atom("quote");
  BIND = Atom("bind");
  UNBIND = Atom("unbind");
  APPLY = Atom("apply");
  EVAL = Atom("eval");
  PRIM = Atom("prim");
  IF = Atom("if");

  AtomSym(T)->global = T; // global t has value t

  CAR = Atom("car");
  AtomSym(CAR)->global = list2(PRIM, CAR);
  AtomSym(CAR)->prim = PrimCar;

  CDR = Atom("cdr");
  AtomSym(CDR)->global = list2(PRIM, CDR);
  AtomSym(CDR)->prim = PrimCdr;

  CONS = Atom("cons");
  AtomSym(CONS)->global = list2(PRIM, CONS);
  AtomSym(CONS)->prim = PrimCons;

  NULL_ = Atom("null");
  AtomSym(NULL_)->global = list2(PRIM, NULL_);
  AtomSym(NULL_)->prim = PrimNull;

  ATOMP = Atom("atomp");
  AtomSym(ATOMP)->global = list2(PRIM, ATOMP);
  AtomSym(ATOMP)->prim = PrimAtomp;

  EQ = Atom("eq");
  AtomSym(EQ)->global = list2(PRIM, EQ);
  AtomSym(EQ)->prim = PrimEq;

  LIST = Atom("list");
  AtomSym(LIST)->global = list2(PRIM, LIST);
  AtomSym(LIST)->prim = PrimList;
}

struct LTerp {
  sn env, work, stk;
  LTerp(sn e, sn w, sn s) : env(e), work(w), stk(s) {}
};
string Str(LTerp t) { return Str(list6(Atom("ENV:"), t.env, Atom("WORK:"), t.work, Atom("STK:"), t.stk)); }

sn Pop(sn &X) { sn z = car(X); X = cdr(X); return z; }
void Push(sn &X, sn a) { X = cons(a, X); }

LTerp Step(LTerp t) {
  sn env = t.env;
  sn work = t.work;
  sn stk = t.stk;
  CheckList(env);
  CheckCons(work);  // not NIL
  CheckList(stk);
  sn w = Pop(work);
  sn a = Pop(work);

  if (w == BIND) {
    sn value = Pop(stk);
    Push(env, value);
    Push(env, a);
    cerr << "Bind: " << Str(a) << " <- " << Str(value) << "\n";
  } else if (w == UNBIND) {
    sn var = Pop(env);
    assert (var == a);
    sn value = Pop(env);
    cerr << "UnBind: " << Str(a) << " // " << Str(value) << "\n";
  } else if (w == APPLY) {
    cerr << "Apply:: [" << Str(a) << "]   stk: " << Str(stk) << "\n";
    // a has length of num of args.
    sn fn = Pop(stk);
    CheckCons(fn);
    Pop(a); // pop & ignore, for the counter
    
    if (PRIM == car(fn)) {

      sn r_args = NIL;
      while (!null(a)) {
        sn x = Pop(stk);
        cerr << "Apply: pushing Pop(stk) to r_args: " << Str(x) << "\n";
        Push(r_args, x);
        Pop(a); // pop & ignore, for the counter
      }

      sn args = NIL;
      while (!null(r_args)) {
        Push(args, Pop(r_args));
      }

      CheckAtom(cadr(fn));
      sym sy = AtomSym(cadr(fn));
      assert(sy);
      cerr << "Apply: Prim: " << sy->name << "  args: " << Str(args) << "\n";
      assert(sy->prim);
      sn z = sy->prim(env, args);
      cerr << "Apply: Prim Returns: " << Str(z) << "\n";
      Push(stk, z);
    } else if (LAMBDA == car(fn)) {

        // Apply the lambda function
        CheckCons(cdr(fn));  // must have 2nd part: params
        CheckCons(cddr(fn)); // must have 3rd part: expr
        sn params = cadr(fn);
        sn expr = caddr(fn);

        sn rev_params = NIL;
        sn pp = params;
        while (pp != NIL) {
          sn p = Pop(pp);
          CheckAtom(p);
          Push(rev_params, p);
	}
	pp = params;
        while (pp != NIL) {
          Push(work, Pop(pp));
          Push(work, UNBIND);
        }
	Push(work, expr);
	Push(work, EVAL);

        pp = rev_params;
        while (pp != NIL) {
          sn param = Pop(pp);
          Push(work, param);
          Push(work, BIND);
cerr << "Apply bind:  " << Str(param) << "\n";
          //CheckCons(args); // must have real arg for formal param car(params) 
          //sn arg = Pop(args);
          //Push(stk, arg);
	}

    } else {
      cerr << "Apply Error:  Not a function: " << Str(fn) << "\n";
      assert(0);
    }
  } else if (w == IF) {
    sn pred = Pop(stk);
    if (not_(pred)) {
      // Use the else clause.
      Push(work, cadr(a));
    } else {
      // Use the then clause.
      Push(work, car(a));
    }
    Push(work, EVAL);  // eval 1 of them.
  } else if (w == EVAL) {
    cerr << "Eval: " << Str(a) << " env: " << Str(env) << "\n";
    if (atomp(a)) {
      sn z = Lookup(env, a);
      assert(z);
      cerr << "Eval Lookup Result: " << Str(z) << "\n";
      Push(stk, z);
    } else {
      CheckCons(a); // cant be empty
      sn cmd = car(a);
      if (cmd == QUOTE) {
        Push(stk, cadr(a));
      } else if (cmd == LAMBDA) {
        Push(stk, a);  // LAMBDA is self-evaluating
      } else if (cmd == IF) {
        Push(work, list2(caddr(a), cadddr(a)));  // then & else clauses
	Push(work, IF);
        Push(work, cadr(a));  // Predicate to evaluate
	Push(work, EVAL);
      } else {
        sn args = a;
	Push(work, args);   // used for its length == arg count
	Push(work, APPLY);
	while (args != NIL) {
	  sn arg = Pop(args);
	  Push(work, arg);
	  Push(work, EVAL);
        }
      }
    }
  } else {
    cerr << "BAD WORK: " << Str(w) << ", " << Str(a) << ", " << Str(work) << "\n";
    assert(0);
  }
  return LTerp(env, work, stk); 
}
  
sn Eval(sn x) {
  LTerp t(NIL, list2(EVAL, x), NIL);
  while (t.work != NIL) {
    cerr << "..." << Str(t) << "\n";
    t = Step(t);
  }
  cerr << "...RETURNING CAR " << Str(t.stk) << "\n";
  return car(t.stk);
}


void Tests() {
  sym abc = Intern("abc");

  assert(abc == Intern("abc"));
  assert("abc" == Intern("abc")->name);
  assert(abc != Intern("def"));
  assert("abc" != Intern("def")->name);

  sn def = Atom("def");
  sn xyz = Atom("xyz");
  assert("def" == AtomName(def));
  assert("xyz" == AtomName(xyz));
  assert("nil" == AtomName(NIL));
  assert("t" == AtomName(T));

  assert(atomp(Atom("def")));
  assert(!consp(Atom("def")));
  assert(!listp(Atom("def")));
  assert(listp(Atom("nil")));

  assert(def == car(cons(Atom("def"), Atom("xyz"))));
  assert(xyz == cdr(cons(Atom("def"), Atom("xyz"))));

  sn three = list3(Atom("one"), Atom("two"), Atom("three"));
  assert(Atom("one") == car(three));
  assert(Atom("two") == cadr(three));
  assert(Atom("three") == car(cddr(three)));
  assert(Atom("three") == cadr(cdr(three)));
  assert(NIL == cddr(cdr(three)));

  assert(def == car(list2(def, xyz)));
  assert(xyz == cadr(list2(def, xyz)));
  assert(NIL == cddr(list2(def, xyz)));

  assert(three == car(list1(three)));
  assert(NIL == cdr(list1(three)));

  assert(T == Lookup(NIL, T));
  assert(T == Lookup(list2(def, xyz), T));
  assert(xyz == Lookup(list2(def, xyz), def));

  assert("def" == Str(def));
  assert("( def )" == Str(list1(def)));
  assert("( def ( one two three ) )" == Str(list2(def, three)));

  LTerp t1 = Step(LTerp(NIL, list2(BIND, def), list1(xyz)));
  assert("( def xyz )" == Str(t1.env));
  assert("( ENV: ( def xyz ) WORK: nil STK: nil )" == Str(t1));

  LTerp t2 = Step(LTerp(t1.env, list2(UNBIND, def), NIL));
  assert("( ENV: nil WORK: nil STK: nil )" == Str(t2));

  cerr << "t3:\n";
  LTerp t3 = Step(LTerp(NIL,
                        list2(APPLY, list2(NIL, NIL)),
                        list2(list2(PRIM, CAR), three)));
  assert("( ENV: nil WORK: nil STK: ( one ) )" == Str(t3));

  cerr << "t4:\n";
  LTerp t4 = Step(LTerp(NIL,
                        list2(APPLY, list3(NIL, NIL, NIL)),
                        list3(list2(PRIM, CONS), def, three)));
  assert("( ENV: nil WORK: nil STK: ( ( def one two three ) ) )" == Str(t4));

  cerr << "t5:\n";
  LTerp t5 = Step(LTerp(NIL,
                        list2(EVAL, CAR),
                        NIL));
  assert("( ENV: nil WORK: nil STK: ( ( prim car ) ) )" == Str(t5));

  cerr << "t6:\n";
  LTerp t6 = Step(LTerp(NIL,
                        list2(EVAL, list2(QUOTE, three)),
                        NIL));
  assert("( ENV: nil WORK: nil STK: ( ( one two three ) ) )" == Str(t6));

  cerr << "t7:\n";
  LTerp t7 = Step(LTerp(NIL,
                        list2(EVAL, list3(LAMBDA, list2(def, xyz), NIL)),
                        NIL));
  assert("( ENV: nil WORK: nil STK: ( ( lambda ( def xyz ) nil ) ) )" == Str(t7));

  cerr << "t8:\n";
  LTerp t8 = Step(LTerp(NIL,
                        list2(EVAL, list2(CAR, list2(QUOTE, three))),
                        NIL));
  cerr << Str(t8) << "\n";
  t8 = Step(t8);  // eval quote...
  cerr << Str(t8) << "\n";
  t8 = Step(t8);  // eval lambda...
  cerr << Str(t8) << "\n";
  t8 = Step(t8);  // Apply 
  assert("( ENV: nil WORK: nil STK: ( one ) )" == Str(t8));

  cerr << "t9:\n";
  LTerp t9 = Step(LTerp(list2(def, three),
                        list2(EVAL, list2(CAR, list2(CAR, list3(CONS, def, def)))),
                        NIL));
  while (consp(t9.work)) {
    cerr << Str(t9) << "\n";
    t9 = Step(t9);  // eval quote...
  }
  cerr << "t9 => " << Str(t9) << "\n";
  assert("( one )" == Str(t9.stk));

  cerr << "t10:\n";
  sn x = Atom("x");
  sn y = Atom("y");
  sn lambda10 = list3(LAMBDA, list2(x, y), list3(CONS, x, y));
  LTerp t10 = Step(LTerp(list2(def, three),
                        list2(EVAL, list3(lambda10, def, list2(CDR, def))),
                        NIL));
  while (consp(t10.work)) {
    cerr << "  .. env: " << Str(t10.env) << "\n";
    cerr << "  .... work: " << Str(t10.work) << "\n";
    cerr << "  ...... stk: " << Str(t10.stk) << "\n";
    t10 = Step(t10);  // eval quote...
  }
  cerr << "t10 => " << Str(t10) << "\n";
  assert("( ( ( one two three ) two three ) )" == Str(t10.stk));

  cerr << "t11:\n";
  sn append = Atom("append");
  AtomSym(append)->global = list3(
      LAMBDA,
      list2(x, y),
      list4(IF,
            list2(NULL_, x),
	    y,
	    list3(CONS,
	          list2(CAR, x),
		  list3(append, list2(CDR, x), y))));
  sn z11 = Eval(list3(append, list2(QUOTE, three), list2(QUOTE, three)));
  cerr << "t11 => " << Str(z11) << "\n";
  assert("( one two three one two three )" == Str(z11));

  cerr << "t12:\n";
  sn reverse = Atom("reverse");
  AtomSym(reverse)->global = list3(
      LAMBDA,
      list1(x),
      list4(IF,
            list2(NULL_, x),
	    list2(QUOTE, NIL),
	    list3(append,
	          list2(reverse, list2(CDR, x)),
		  list2(LIST, list2(CAR, x)))));
  sn z12 = Eval(list2(reverse, list2(QUOTE, three)));
  cerr << "t12 => " << Str(z12) << "\n";
  assert("( three two one )" == Str(z12));

  // OKAY
  cerr << "TESTS OKAY." << "\n";
}

int main() {
  InitAtoms();
  Tests();
  return 0;
}
