* Don't use ATerms for the abstract syntax trees anymore. Not

  finished yet.

16 files changed, 684 insertions, 569 deletions

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index 99f742ffec..60b1815d96 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -8,15 +8,15 @@ libexpr_la_SOURCES = \
 pkginclude_HEADERS = \
  nixexpr.hh eval.hh parser.hh lexer-tab.hh parser-tab.hh \
  get-drvs.hh attr-path.hh value-to-xml.hh common-opts.hh \
- names.hh nixexpr-ast.hh
+ names.hh
 
 libexpr_la_LIBADD = ../libutil/libutil.la ../libstore/libstore.la \
  ../boost/format/libformat.la
 
-BUILT_SOURCES = nixexpr-ast.cc nixexpr-ast.hh \
+BUILT_SOURCES = \
  parser-tab.hh lexer-tab.hh parser-tab.cc lexer-tab.cc
 
-EXTRA_DIST = lexer.l parser.y nixexpr-ast.def nixexpr-ast.cc
+EXTRA_DIST = lexer.l parser.y
 
 AM_CXXFLAGS = \
  -I$(srcdir)/.. ${aterm_include} \
@@ -34,15 +34,6 @@ lexer-tab.cc lexer-tab.hh: lexer.l
 	$(flex) --outfile lexer-tab.cc --header-file=lexer-tab.hh $(srcdir)/lexer.l 
 
 
-# ATerm helper function generation.
-
-nixexpr-ast.cc nixexpr-ast.hh: ../aterm-helper.pl nixexpr-ast.def
-	$(perl) $(srcdir)/../aterm-helper.pl nixexpr-ast.hh nixexpr-ast.cc < $(srcdir)/nixexpr-ast.def
-
-
-CLEANFILES =
-
-
 # SDF stuff (not built by default).
 nix.tbl: nix.sdf
 	sdf2table -m Nix -s -i nix.sdf -o nix.tbl
diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index 5f1c0ad783..aa421ab431 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -1,5 +1,4 @@
 #include "attr-path.hh"
-#include "nixexpr-ast.hh"
 #include "util.hh"
 
 
@@ -7,7 +6,7 @@ namespace nix {
 
 
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr e, Value & v)
+    const Bindings & autoArgs, Expr * e, Value & v)
 {
     Strings tokens = tokenizeString(attrPath, ".");
 
@@ -46,7 +45,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath,
                     format("the expression selected by the selection path `%1%' should be an attribute set but is %2%")
                     % curPath % showType(v));
 
-            Bindings::iterator a = v.attrs->find(toATerm(attr));
+            Bindings::iterator a = v.attrs->find(attr);
             if (a == v.attrs->end())
                 throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
             v = a->second;
diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh
index 518a7a95da..33587e5ede 100644
--- a/src/libexpr/attr-path.hh
+++ b/src/libexpr/attr-path.hh
@@ -11,7 +11,7 @@ namespace nix {
 
     
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr e, Value & v);
+    const Bindings & autoArgs, Expr * e, Value & v);
 
     
 }
diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index d5d3df40a9..6171de0f0e 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -20,10 +20,10 @@ bool parseOptionArg(const string & arg, Strings::iterator & i,
     if (i == argsEnd) throw error;
     string value = *i++;
 
-    Value & v(autoArgs[toATerm(name)]);
+    Value & v(autoArgs[name]);
 
     if (arg == "--arg")
-        state.mkThunk_(v, parseExprFromString(state, value, absPath(".")));
+        state.mkThunk_(v, parseExprFromString(value, absPath(".")));
     else
         mkString(v, value);
     
diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc
index 77861dea95..32f4940df9 100644
--- a/src/libexpr/eval-test.cc
+++ b/src/libexpr/eval-test.cc
@@ -2,8 +2,8 @@
 #include "parser.hh"
 #include "hash.hh"
 #include "util.hh"
-#include "nixexpr-ast.hh"
 
+#include <iostream>
 #include <cstdlib>
 #include <cstring>
 
@@ -12,8 +12,8 @@ using namespace nix;
 
 void doTest(EvalState & state, string s)
 {
-    Expr e = parseExprFromString(state, s, absPath("."));
-    printMsg(lvlError, format(">>>>> %1%") % e);
+    Expr * e = parseExprFromString(s, absPath("."));
+    std::cerr << ">>>>> " << *e << std::endl;
     Value v;
     state.eval(e, v);
     state.strictForceValue(v);
@@ -24,8 +24,10 @@ void doTest(EvalState & state, string s)
 void run(Strings args)
 {
     EvalState state;
-    
+
     printMsg(lvlError, format("size of value: %1% bytes") % sizeof(Value));
+    printMsg(lvlError, format("size of int AST node: %1% bytes") % sizeof(ExprInt));
+    printMsg(lvlError, format("size of attrset AST node: %1% bytes") % sizeof(ExprAttrs));
     
     doTest(state, "123");
     doTest(state, "{ x = 1; y = 2; }");
@@ -53,7 +55,7 @@ void run(Strings args)
     doTest(state, "let id = x: x; in [1 2] == [(id 1) (id 2)]");
     doTest(state, "let id = x: x; in [1 2] == [(id 1) (id 3)]");
     doTest(state, "[1 2] == [3 (let x = x; in x)]");
-    doTest(state, "{ x = 1; y.z = 2; } == { y = { z = 2; }; x = 1; }");
+    //doTest(state, "{ x = 1; y.z = 2; } == { y = { z = 2; }; x = 1; }");
     doTest(state, "{ x = 1; y = 2; } == { x = 2; }");
     doTest(state, "{ x = [ 1 2 ]; } == { x = [ 1 ] ++ [ 2 ]; }");
     doTest(state, "1 != 1");
@@ -63,23 +65,23 @@ void run(Strings args)
     doTest(state, "__head [ 1 2 3 ]");
     doTest(state, "__add 1 2");
     doTest(state, "null");
-    doTest(state, "null");
-    doTest(state, "\"foo\"");
-    doTest(state, "let s = \"bar\"; in \"foo${s}\"");
+    //doTest(state, "\"foo\"");
+    //doTest(state, "let s = \"bar\"; in \"foo${s}\"");
     doTest(state, "if true then 1 else 2");
     doTest(state, "if false then 1 else 2");
     doTest(state, "if false || true then 1 else 2");
     doTest(state, "let x = x; in if true || x then 1 else 2");
+    doTest(state, "http://nixos.org/");
     doTest(state, "/etc/passwd");
     //doTest(state, "import ./foo.nix");
     doTest(state, "map (x: __add 1 x) [ 1 2 3 ]");
     doTest(state, "map (builtins.add 1) [ 1 2 3 ]");
-    doTest(state, "builtins.hasAttr \"x\" { x = 1; }");
+    //doTest(state, "builtins.hasAttr \"x\" { x = 1; }");
     doTest(state, "let x = 1; as = rec { inherit x; y = as.x; }; in as.y");
     doTest(state, "let as = { x = 1; }; bs = rec { inherit (as) x; y = x; }; in bs.y");
     doTest(state, "let as = rec { inherit (y) x; y = { x = 1; }; }; in as.x");
     doTest(state, "builtins.toXML 123");
-    doTest(state, "builtins.toXML { a.b = \"x\" + \"y\"; c = [ 1 2 ] ++ [ 3 4 ]; }");
+    //doTest(state, "builtins.toXML { a.b = \"x\" + \"y\"; c = [ 1 2 ] ++ [ 3 4 ]; }");
 
     state.printStats();
 }
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 7434aa8422..8ead986b81 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -4,7 +4,6 @@
 #include "util.hh"
 #include "store-api.hh"
 #include "derivations.hh"
-#include "nixexpr-ast.hh"
 #include "globals.hh"
 
 #include <cstring>
@@ -45,7 +44,7 @@ std::ostream & operator << (std::ostream & str, Value & v)
     case tAttrs:
         str << "{ ";
         foreach (Bindings::iterator, i, *v.attrs)
-            str << aterm2String(i->first) << " = " << i->second << "; ";
+            str << i->first << " = " << i->second << "; ";
         str << "}";
         break;
     case tList:
@@ -96,8 +95,6 @@ EvalState::EvalState() : baseEnv(allocEnv())
     nrValues = nrEnvs = nrEvaluated = recursionDepth = maxRecursionDepth = 0;
     deepestStack = (char *) -1;
 
-    initNixExprHelpers();
-
     createBaseEnv();
     
     allowUnsafeEquality = getEnv("NIX_NO_UNSAFE_EQ", "") == "";
@@ -112,9 +109,9 @@ EvalState::~EvalState()
 
 void EvalState::addConstant(const string & name, Value & v)
 {
-    baseEnv.bindings[toATerm(name)] = v;
+    baseEnv.bindings[name] = v;
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    (*baseEnv.bindings[toATerm("builtins")].attrs)[toATerm(name2)] = v;
+    (*baseEnv.bindings["builtins"].attrs)[name2] = v;
     nrValues += 2;
 }
 
@@ -126,9 +123,9 @@ void EvalState::addPrimOp(const string & name,
     v.type = tPrimOp;
     v.primOp.arity = arity;
     v.primOp.fun = primOp;
-    baseEnv.bindings[toATerm(name)] = v;
+    baseEnv.bindings[name] = v;
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    (*baseEnv.bindings[toATerm("builtins")].attrs)[toATerm(name2)] = v;
+    (*baseEnv.bindings["builtins"].attrs)[name2] = v;
     nrValues += 2;
 }
 
@@ -212,12 +209,12 @@ void mkPath(Value & v, const char * s)
 }
 
 
-static Value * lookupWith(Env * env, Sym name)
+static Value * lookupWith(Env * env, const Sym & name)
 {
     if (!env) return 0;
     Value * v = lookupWith(env->up, name);
     if (v) return v;
-    Bindings::iterator i = env->bindings.find(sWith);
+    Bindings::iterator i = env->bindings.find("<with>");
     if (i == env->bindings.end()) return 0;
     Bindings::iterator j = i->second.attrs->find(name);
     if (j != i->second.attrs->end()) return &j->second;
@@ -225,7 +222,7 @@ static Value * lookupWith(Env * env, Sym name)
 }
 
 
-static Value * lookupVar(Env * env, Sym name)
+static Value * lookupVar(Env * env, const Sym & name)
 {
     /* First look for a regular variable binding for `name'. */
     for (Env * env2 = env; env2; env2 = env2->up) {
@@ -251,7 +248,7 @@ static Value * lookupVar(Env * env, Sym name)
     }
 #endif
     
-    throwEvalError("undefined variable `%1%'", aterm2String(name));
+    throwEvalError("undefined variable `%1%'", name);
 }
 
 
@@ -284,7 +281,7 @@ void EvalState::mkAttrs(Value & v)
 }
 
 
-void EvalState::mkThunk_(Value & v, Expr expr)
+void EvalState::mkThunk_(Value & v, Expr * expr)
 {
     mkThunk(v, baseEnv, expr);
 }
@@ -302,11 +299,11 @@ void EvalState::evalFile(const Path & path, Value & v)
 {
     startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path);
 
-    Expr e = parseTrees.get(toATerm(path));
+    Expr * e = parseTrees[path];
 
     if (!e) {
-        e = parseExprFromFile(*this, path);
-        parseTrees.set(toATerm(path), e);
+        e = parseExprFromFile(path);
+        parseTrees[path] = e;
     }
     
     try {
@@ -334,7 +331,7 @@ struct RecursionCounter
 };
 
 
-void EvalState::eval(Env & env, Expr e, Value & v)
+void EvalState::eval(Env & env, Expr * e, Value & v)
 {
     /* When changing this function, make sure that you don't cause a
        (large) increase in stack consumption! */
@@ -350,6 +347,9 @@ void EvalState::eval(Env & env, Expr e, Value & v)
 
     nrEvaluated++;
 
+    e->eval(*this, env, v);
+
+#if 0
     Sym name;
     int n;
     ATerm s; ATermList context, es;
@@ -357,138 +357,6 @@ void EvalState::eval(Env & env, Expr e, Value & v)
     Expr e1, e2, e3, fun, arg, attrs;
     Pattern pat; Expr body; Pos pos;
     
-    if (matchVar(e, name)) {
-        Value * v2 = lookupVar(&env, name);
-        forceValue(*v2);
-        v = *v2;
-    }
-
-    else if (matchInt(e, n))
-        mkInt(v, n);
-
-    else if (matchStr(e, s, context)) {
-        assert(context == ATempty);
-        mkString(v, ATgetName(ATgetAFun(s)));
-    }
-
-    else if (matchPath(e, s))
-        mkPath(v, ATgetName(ATgetAFun(s)));
-
-    else if (matchAttrs(e, es)) {
-        mkAttrs(v);
-        ATerm e2, pos;
-        for (ATermIterator i(es); i; ++i) {
-            if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-            Value & v2 = (*v.attrs)[name];
-            nrValues++;
-            mkThunk(v2, env, e2);
-        }
-    }
-
-    else if (matchRec(e, rbnds, nrbnds)) {
-        /* Create a new environment that contains the attributes in
-           this `rec'. */
-        Env & env2(allocEnv());
-        env2.up = &env;
-        
-        v.type = tAttrs;
-        v.attrs = &env2.bindings;
-
-        /* The recursive attributes are evaluated in the new
-           environment. */
-        ATerm name, e2, pos;
-        for (ATermIterator i(rbnds); i; ++i) {
-            if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-            Value & v2 = env2.bindings[name];
-            nrValues++;
-            mkThunk(v2, env2, e2);
-        }
-
-        /* The non-recursive attributes, on the other hand, are
-           evaluated in the original environment. */
-        for (ATermIterator i(nrbnds); i; ++i) {
-            if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-            Value & v2 = env2.bindings[name];
-            nrValues++;
-            mkThunk(v2, env, e2);
-        }
-    }
-
-    else if (matchSelect(e, e2, name)) {
-        Value v2;
-        eval(env, e2, v2);
-        forceAttrs(v2); // !!! eval followed by force is slightly inefficient
-        Bindings::iterator i = v2.attrs->find(name);
-        if (i == v2.attrs->end())
-            throwEvalError("attribute `%1%' missing", aterm2String(name));
-        try {            
-            forceValue(i->second);
-        } catch (Error & e) {
-            addErrorPrefix(e, "while evaluating the attribute `%1%':\n", aterm2String(name));
-            throw;
-        }
-        v = i->second;
-    }
-
-    else if (matchFunction(e, pat, body, pos)) {
-        v.type = tLambda;
-        v.lambda.env = &env;
-        v.lambda.pat = pat;
-        v.lambda.body = body;
-    }
-
-    else if (matchCall(e, fun, arg)) {
-        Value vFun;
-        eval(env, fun, vFun);
-        Value vArg;
-        mkThunk(vArg, env, arg); // !!! should this be on the heap?
-        callFunction(vFun, vArg, v);
-    }
-
-    else if (matchWith(e, attrs, body, pos)) {
-        Env & env2(allocEnv());
-        env2.up = &env;
-
-        Value & vAttrs = env2.bindings[sWith];
-        nrValues++;
-        eval(env, attrs, vAttrs);
-        forceAttrs(vAttrs);
-        
-        eval(env2, body, v);
-    }
-
-    else if (matchList(e, es)) {
-        mkList(v, ATgetLength(es));
-        for (unsigned int n = 0; n < v.list.length; ++n, es = ATgetNext(es))
-            mkThunk(v.list.elems[n], env, ATgetFirst(es));
-    }
-
-    else if (matchOpEq(e, e1, e2)) {
-        Value v1; eval(env, e1, v1);
-        Value v2; eval(env, e2, v2);
-        mkBool(v, eqValues(v1, v2));
-    }
-
-    else if (matchOpNEq(e, e1, e2)) {
-        Value v1; eval(env, e1, v1);
-        Value v2; eval(env, e2, v2);
-        mkBool(v, !eqValues(v1, v2));
-    }
-
-    else if (matchOpConcat(e, e1, e2)) {
-        Value v1; eval(env, e1, v1);
-        forceList(v1);
-        Value v2; eval(env, e2, v2);
-        forceList(v2);
-        mkList(v, v1.list.length + v2.list.length);
-        /* !!! This loses sharing with the original lists.  We could
-           use a tCopy node, but that would use more memory. */
-        for (unsigned int n = 0; n < v1.list.length; ++n)
-            v.list.elems[n] = v1.list.elems[n];
-        for (unsigned int n = 0; n < v2.list.length; ++n)
-            v.list.elems[n + v1.list.length] = v2.list.elems[n];
-    }
-
     else if (matchConcatStrings(e, es)) {
         PathSet context;
         std::ostringstream s;
@@ -521,10 +389,6 @@ void EvalState::eval(Env & env, Expr e, Value & v)
             mkString(v, s.str(), context);
     }
 
-    /* Conditionals. */
-    else if (matchIf(e, e1, e2, e3))
-        eval(env, evalBool(env, e1) ? e2 : e3, v);
-
     /* Assertions. */
     else if (matchAssert(e, e1, e2, pos)) {
         if (!evalBool(env, e1))
@@ -536,30 +400,6 @@ void EvalState::eval(Env & env, Expr e, Value & v)
     else if (matchOpNot(e, e1))
         mkBool(v, !evalBool(env, e1));
 
-    /* Implication. */
-    else if (matchOpImpl(e, e1, e2))
-        return mkBool(v, !evalBool(env, e1) || evalBool(env, e2));
-    
-    /* Conjunction (logical AND). */
-    else if (matchOpAnd(e, e1, e2))
-        mkBool(v, evalBool(env, e1) && evalBool(env, e2));
-    
-    /* Disjunction (logical OR). */
-    else if (matchOpOr(e, e1, e2))
-        mkBool(v, evalBool(env, e1) || evalBool(env, e2));
-
-    /* Attribute set update (//). */
-    else if (matchOpUpdate(e, e1, e2)) {
-        Value v2;
-        eval(env, e1, v2);
-        
-        cloneAttrs(v2, v);
-        
-        eval(env, e2, v2);
-        foreach (Bindings::iterator, i, *v2.attrs)
-            (*v.attrs)[i->first] = i->second; // !!! sharing
-    }
-
     /* Attribute existence test (?). */
     else if (matchOpHasAttr(e, e1, name)) {
         Value vAttrs;
@@ -567,8 +407,130 @@ void EvalState::eval(Env & env, Expr e, Value & v)
         forceAttrs(vAttrs);
         mkBool(v, vAttrs.attrs->find(name) != vAttrs.attrs->end());
     }
+#endif
+}
+
+
+void EvalState::eval(Expr * e, Value & v)
+{
+    eval(baseEnv, e, v);
+}
 
-    else abort();
+
+bool EvalState::evalBool(Env & env, Expr * e)
+{
+    Value v;
+    eval(env, e, v);
+    if (v.type != tBool)
+        throwTypeError("value is %1% while a Boolean was expected", showType(v));
+    return v.boolean;
+}
+
+
+void ExprInt::eval(EvalState & state, Env & env, Value & v)
+{
+    mkInt(v, n);
+}
+
+
+void ExprString::eval(EvalState & state, Env & env, Value & v)
+{
+    mkString(v, s.c_str());
+}
+
+
+void ExprPath::eval(EvalState & state, Env & env, Value & v)
+{
+    mkPath(v, s.c_str());
+}
+
+
+void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
+{
+    if (recursive) {
+
+        /* Create a new environment that contains the attributes in
+           this `rec'. */
+        Env & env2(state.allocEnv());
+        env2.up = &env;
+        
+        v.type = tAttrs;
+        v.attrs = &env2.bindings;
+
+        /* The recursive attributes are evaluated in the new
+           environment. */
+        foreach (Attrs::iterator, i, attrs) {
+            Value & v2 = env2.bindings[i->first];
+            mkThunk(v2, env2, i->second);
+        }
+
+        /* The inherited attributes, on the other hand, are
+           evaluated in the original environment. */
+        foreach (list<string>::iterator, i, inherited) {
+            Value & v2 = env2.bindings[*i];
+            mkCopy(v2, *lookupVar(&env, *i));
+        }
+    }
+
+    else {
+        state.mkAttrs(v);
+        foreach (Attrs::iterator, i, attrs) {
+            Value & v2 = (*v.attrs)[i->first];
+            mkThunk(v2, env, i->second);
+        }
+    }
+}
+
+
+void ExprList::eval(EvalState & state, Env & env, Value & v)
+{
+    state.mkList(v, elems.size());
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        mkThunk(v.list.elems[n], env, elems[n]);
+}
+
+
+void ExprVar::eval(EvalState & state, Env & env, Value & v)
+{
+    Value * v2 = lookupVar(&env, name);
+    state.forceValue(*v2);
+    v = *v2;
+}
+
+
+void ExprSelect::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v2;
+    state.eval(env, e, v2);
+    state.forceAttrs(v2); // !!! eval followed by force is slightly inefficient
+    Bindings::iterator i = v2.attrs->find(name);
+    if (i == v2.attrs->end())
+        throwEvalError("attribute `%1%' missing", name);
+    try {            
+        state.forceValue(i->second);
+    } catch (Error & e) {
+        addErrorPrefix(e, "while evaluating the attribute `%1%':\n", name);
+        throw;
+    }
+    v = i->second;
+}
+
+
+void ExprLambda::eval(EvalState & state, Env & env, Value & v)
+{
+    v.type = tLambda;
+    v.lambda.env = &env;
+    v.lambda.fun = this;
+}
+
+
+void ExprApp::eval(EvalState & state, Env & env, Value & v)
+{
+    Value vFun;
+    state.eval(env, e1, vFun);
+    Value vArg;
+    mkThunk(vArg, env, e2); // !!! should this be on the heap?
+    state.callFunction(vFun, vArg, v);
 }
 
 
@@ -613,19 +575,17 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
     Env & env2(allocEnv());
     env2.up = fun.lambda.env;
 
-    ATermList formals; ATerm ellipsis, name;
-
-    if (matchVarPat(fun.lambda.pat, name)) {
-        Value & vArg = env2.bindings[name];
+    if (!fun.lambda.fun->matchAttrs) {
+        Value & vArg = env2.bindings[fun.lambda.fun->arg];
         nrValues++;
         vArg = arg;
     }
 
-    else if (matchAttrsPat(fun.lambda.pat, formals, ellipsis, name)) {
+    else {
         forceAttrs(arg);
         
-        if (name != sNoAlias) {
-            env2.bindings[name] = arg;
+        if (!fun.lambda.fun->arg.empty()) {
+            env2.bindings[fun.lambda.fun->arg] = arg;
             nrValues++;
         }                
 
@@ -633,21 +593,15 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
            there is no matching actual argument but the formal
            argument has a default, use the default. */
         unsigned int attrsUsed = 0;
-        for (ATermIterator i(formals); i; ++i) {
-            Expr def; Sym name;
-            DefaultValue def2;
-            if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
-
-            Bindings::iterator j = arg.attrs->find(name);
+        foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
+            Bindings::iterator j = arg.attrs->find(i->name);
                 
-            Value & v = env2.bindings[name];
+            Value & v = env2.bindings[i->name];
             nrValues++;
                 
             if (j == arg.attrs->end()) {
-                if (!matchDefaultValue(def2, def)) def = 0;
-                if (def == 0) throwTypeError("the argument named `%1%' required by the function is missing",
-                    aterm2String(name));
-                mkThunk(v, env2, def);
+                if (!i->def) throwTypeError("the argument named `%1%' required by the function is missing", i->name);
+                mkThunk(v, env2, i->def);
             } else {
                 attrsUsed++;
                 mkCopy(v, j->second);
@@ -658,13 +612,11 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
            argument (unless the attribute match specifies a `...').
            TODO: show the names of the expected/unexpected
            arguments. */
-        if (ellipsis == eFalse && attrsUsed != arg.attrs->size())
+        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size())
             throwTypeError("function called with unexpected argument");
     }
 
-    else abort();
-        
-    eval(env2, fun.lambda.body, v);
+    eval(env2, fun.lambda.fun->body, v);
 }
 
 
@@ -672,45 +624,114 @@ void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res
 {
     forceValue(fun);
 
-    ATerm name;
-    ATermList formals;
-    ATermBool ellipsis;
-    
-    if (fun.type != tLambda || !matchAttrsPat(fun.lambda.pat, formals, ellipsis, name)) {
+    if (fun.type != tLambda || !fun.lambda.fun->matchAttrs) {
         res = fun;
         return;
     }
 
     Value actualArgs;
     mkAttrs(actualArgs);
-    
-    for (ATermIterator i(formals); i; ++i) {
-        Expr name, def; ATerm def2;
-        if (!matchFormal(*i, name, def2)) abort();
-        Bindings::const_iterator j = args.find(name);
+
+    foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
+        Bindings::const_iterator j = args.find(i->name);
         if (j != args.end())
-            (*actualArgs.attrs)[name] = j->second;
-        else if (!matchDefaultValue(def2, def))
-            throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", aterm2String(name));
+            (*actualArgs.attrs)[i->name] = j->second;
+        else if (!i->def)
+            throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", i->name);
     }
 
     callFunction(fun, actualArgs, res);
 }
 
 
-void EvalState::eval(Expr e, Value & v)
+void ExprWith::eval(EvalState & state, Env & env, Value & v)
 {
-    eval(baseEnv, e, v);
+    Env & env2(state.allocEnv());
+    env2.up = &env;
+
+    Value & vAttrs = env2.bindings["<with>"];
+    state.eval(env, attrs, vAttrs);
+    state.forceAttrs(vAttrs);
+        
+    state.eval(env2, body, v);
 }
 
 
-bool EvalState::evalBool(Env & env, Expr e)
+void ExprIf::eval(EvalState & state, Env & env, Value & v)
 {
-    Value v;
-    eval(env, e, v);
-    if (v.type != tBool)
-        throwTypeError("value is %1% while a Boolean was expected", showType(v));
-    return v.boolean;
+    state.eval(env, state.evalBool(env, cond) ? then : else_, v);
+}
+
+    
+void ExprOpEq::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v1; state.eval(env, e1, v1);
+    Value v2; state.eval(env, e2, v2);
+    mkBool(v, state.eqValues(v1, v2));
+}
+
+
+void ExprOpNEq::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v1; state.eval(env, e1, v1);
+    Value v2; state.eval(env, e2, v2);
+    mkBool(v, !state.eqValues(v1, v2));
+}
+
+
+void ExprOpAnd::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, state.evalBool(env, e1) && state.evalBool(env, e2));
+}
+
+
+void ExprOpOr::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, state.evalBool(env, e1) || state.evalBool(env, e2));
+}
+
+
+void ExprOpImpl::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, !state.evalBool(env, e1) || state.evalBool(env, e2));
+}
+
+
+void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v2;
+    state.eval(env, e1, v2);
+    state.forceAttrs(v2);
+        
+    state.cloneAttrs(v2, v);
+        
+    state.eval(env, e2, v2);
+    state.forceAttrs(v2);
+    
+    foreach (Bindings::iterator, i, *v2.attrs)
+        (*v.attrs)[i->first] = i->second; // !!! sharing
+}
+
+
+void ExprOpConcatStrings::eval(EvalState & state, Env & env, Value & v)
+{
+    abort();
+}
+
+
+void ExprOpConcatLists::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v1; state.eval(env, e1, v1);
+    state.forceList(v1);
+    Value v2; state.eval(env, e2, v2);
+    state.forceList(v2);
+    state.mkList(v, v1.list.length + v2.list.length);
+    /* !!! This loses sharing with the original lists.  We could use a
+       tCopy node, but that would use more memory. */
+    for (unsigned int n = 0; n < v1.list.length; ++n)
+        v.list.elems[n] = v1.list.elems[n];
+    for (unsigned int n = 0; n < v2.list.length; ++n)
+        v.list.elems[n + v1.list.length] = v2.list.elems[n];
 }
 
 
@@ -827,7 +848,7 @@ string EvalState::forceStringNoCtx(Value & v)
 bool EvalState::isDerivation(Value & v)
 {
     if (v.type != tAttrs) return false;
-    Bindings::iterator i = v.attrs->find(toATerm("type"));
+    Bindings::iterator i = v.attrs->find("type");
     return i != v.attrs->end() && forceStringNoCtx(i->second) == "derivation";
 }
 
@@ -871,7 +892,7 @@ string EvalState::coerceToString(Value & v, PathSet & context,
     }
 
     if (v.type == tAttrs) {
-        Bindings::iterator i = v.attrs->find(toATerm("outPath"));
+        Bindings::iterator i = v.attrs->find("outPath");
         if (i == v.attrs->end())
             throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
         return coerceToString(i->second, context, coerceMore, copyToStore);
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index fb4dd802e0..cbdd09085d 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -3,7 +3,6 @@
 
 #include <map>
 
-#include "aterm.hh"
 #include "nixexpr.hh"
 
 
@@ -15,7 +14,7 @@ class EvalState;
 struct Env;
 struct Value;
 
-typedef ATerm Sym;
+typedef string Sym;
 
 typedef std::map<Sym, Value> Bindings;
 
@@ -55,10 +54,32 @@ struct Value
     {
         int integer;
         bool boolean;
+        
+        /* Strings in the evaluator carry a so-called `context' (the
+           ATermList) which is a list of strings representing store
+           paths.  This is to allow users to write things like
+
+             "--with-freetype2-library=" + freetype + "/lib"
+
+           where `freetype' is a derivation (or a source to be copied
+           to the store).  If we just concatenated the strings without
+           keeping track of the referenced store paths, then if the
+           string is used as a derivation attribute, the derivation
+           will not have the correct dependencies in its inputDrvs and
+           inputSrcs.
+
+           The semantics of the context is as follows: when a string
+           with context C is used as a derivation attribute, then the
+           derivations in C will be added to the inputDrvs of the
+           derivation, and the other store paths in C will be added to
+           the inputSrcs of the derivations.
+
+           For canonicity, the store paths should be in sorted order. */
         struct {
             const char * s;
             const char * * context;
         } string;
+        
         const char * path;
         Bindings * attrs;
         struct {
@@ -67,15 +88,14 @@ struct Value
         } list;
         struct {
             Env * env;
-            Expr expr;
+            Expr * expr;
         } thunk;
         struct {
             Value * left, * right;
         } app;
         struct {
             Env * env;
-            Pattern pat;
-            Expr body;
+            ExprLambda * fun;
         } lambda;
         Value * val;
         struct {
@@ -104,7 +124,7 @@ static inline void mkBool(Value & v, bool b)
 }
 
 
-static inline void mkThunk(Value & v, Env & env, Expr expr)
+static inline void mkThunk(Value & v, Env & env, Expr * expr)
 {
     v.type = tThunk;
     v.thunk.env = &env;
@@ -146,7 +166,7 @@ private:
 
     bool allowUnsafeEquality;
 
-    ATermMap parseTrees;
+    std::map<Path, Expr *> parseTrees;
 
 public:
     
@@ -159,12 +179,12 @@ public:
 
     /* Evaluate an expression to normal form, storing the result in
        value `v'. */
-    void eval(Expr e, Value & v);
-    void eval(Env & env, Expr e, Value & v);
+    void eval(Expr * e, Value & v);
+    void eval(Env & env, Expr * e, Value & v);
 
     /* Evaluation the expression, then verify that it has the expected
        type. */
-    bool evalBool(Env & env, Expr e);
+    bool evalBool(Env & env, Expr * e);
 
     /* If `v' is a thunk, enter it and overwrite `v' with the result
        of the evaluation of the thunk.  If `v' is a delayed function
@@ -215,12 +235,12 @@ private:
     void addPrimOp(const string & name,
         unsigned int arity, PrimOp primOp);
 
+public:
+    
     /* Do a deep equality test between two values.  That is, list
        elements and attributes are compared recursively. */
     bool eqValues(Value & v1, Value & v2);
 
-public:
-    
     void callFunction(Value & fun, Value & arg, Value & v);
 
     /* Automatically call a function for which each argument has a
@@ -233,7 +253,7 @@ public:
 
     void mkList(Value & v, unsigned int length);
     void mkAttrs(Value & v);
-    void mkThunk_(Value & v, Expr expr);
+    void mkThunk_(Value & v, Expr * expr);
     
     void cloneAttrs(Value & src, Value & dst);
 
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index f5e7242f9f..95938d5c1f 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -1,5 +1,4 @@
 #include "get-drvs.hh"
-#include "nixexpr-ast.hh"
 #include "util.hh"
 
 
@@ -9,7 +8,7 @@ namespace nix {
 string DrvInfo::queryDrvPath(EvalState & state) const
 {
     if (drvPath == "") {
-        Bindings::iterator i = attrs->find(toATerm("drvPath"));
+        Bindings::iterator i = attrs->find("drvPath");
         PathSet context;
         (string &) drvPath = i != attrs->end() ? state.coerceToPath(i->second, context) : "";
     }
@@ -20,7 +19,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const
 string DrvInfo::queryOutPath(EvalState & state) const
 {
     if (outPath == "") {
-        Bindings::iterator i = attrs->find(toATerm("outPath"));
+        Bindings::iterator i = attrs->find("outPath");
         PathSet context;
         (string &) outPath = i != attrs->end() ? state.coerceToPath(i->second, context) : "";
     }
@@ -32,7 +31,7 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
 {
     MetaInfo meta;
     
-    Bindings::iterator a = attrs->find(toATerm("meta"));
+    Bindings::iterator a = attrs->find("meta");
     if (a == attrs->end()) return meta; /* fine, empty meta information */
 
     state.forceAttrs(a->second);
@@ -51,7 +50,7 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
             for (unsigned int j = 0; j < i->second.list.length; ++j)
                 value.stringValues.push_back(state.forceStringNoCtx(i->second.list.elems[j]));
         } else continue;
-        meta[aterm2String(i->first)] = value;
+        meta[i->first] = value;
     }
 
     return meta;
@@ -114,12 +113,12 @@ static bool getDerivation(EvalState & state, Value & v,
 
         DrvInfo drv;
     
-        Bindings::iterator i = v.attrs->find(toATerm("name"));
+        Bindings::iterator i = v.attrs->find("name");
         /* !!! We really would like to have a decent back trace here. */
         if (i == v.attrs->end()) throw TypeError("derivation name missing");
         drv.name = state.forceStringNoCtx(i->second);
 
-        i = v.attrs->find(toATerm("system"));
+        i = v.attrs->find("system");
         if (i == v.attrs->end())
             drv.system = "unknown";
         else
@@ -171,7 +170,7 @@ static void getDerivations(EvalState & state, Value & vIn,
 
         /* !!! undocumented hackery to support combining channels in
            nix-env.cc. */
-        bool combineChannels = v.attrs->find(toATerm("_combineChannels")) != v.attrs->end();
+        bool combineChannels = v.attrs->find("_combineChannels") != v.attrs->end();
 
         /* Consider the attributes in sorted order to get more
            deterministic behaviour in nix-env operations (e.g. when
@@ -180,12 +179,12 @@ static void getDerivations(EvalState & state, Value & vIn,
            precedence). */
         StringSet attrs;
         foreach (Bindings::iterator, i, *v.attrs)
-            attrs.insert(aterm2String(i->first));
+            attrs.insert(i->first);
 
         foreach (StringSet::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % *i);
             string pathPrefix2 = addToPath(pathPrefix, *i);
-            Value & v2((*v.attrs)[toATerm(*i)]);
+            Value & v2((*v.attrs)[*i]);
             if (combineChannels)
                 getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
             else if (getDerivation(state, v2, pathPrefix2, drvs, done)) {
@@ -194,7 +193,7 @@ static void getDerivations(EvalState & state, Value & vIn,
                    if it has a `recurseForDerivations = true'
                    attribute. */
                 if (v2.type == tAttrs) {
-                    Bindings::iterator j = v2.attrs->find(toATerm("recurseForDerivations"));
+                    Bindings::iterator j = v2.attrs->find("recurseForDerivations");
                     if (j != v2.attrs->end() && state.forceBool(j->second))
                         getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
                 }
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
index 82c3500202..f750cfd02d 100644
--- a/src/libexpr/lexer.l
+++ b/src/libexpr/lexer.l
@@ -8,9 +8,7 @@
 
 
 %{
-#include "aterm.hh"
 #include "nixexpr.hh"
-#include "nixexpr-ast.hh"
 #define BISON_HEADER_HACK
 #include "parser-tab.hh"
 
@@ -45,8 +43,9 @@ static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
 }
 
 
-static Expr unescapeStr(const char * s)
+static Expr * unescapeStr(const char * s)
 {
+#if 0
     string t;
     char c;
     while ((c = *s++)) {
@@ -66,6 +65,7 @@ static Expr unescapeStr(const char * s)
         else t += c;
     }
     return makeStr(toATerm(t), ATempty);
+#endif
 }
 
  
@@ -105,7 +105,7 @@ inherit     { return INHERIT; }
 \/\/        { return UPDATE; }
 \+\+        { return CONCAT; }
 
-{ID}        { yylval->t = toATerm(yytext); return ID; /* !!! alloc */ }
+{ID}        { yylval->id = strdup(yytext); return ID; }
 {INT}       { int n = atoi(yytext); /* !!! overflow */
               yylval->n = n;
               return INT;
@@ -117,7 +117,7 @@ inherit     { return INHERIT; }
    shouldn't be followed by a "{".  Right now "$\"" will be consumed
    as part of a string, rather than a "$" followed by the string
    terminator.  Disallow "$\"" for now. */
-              yylval->t = unescapeStr(yytext); /* !!! alloc */ 
+              yylval->e = unescapeStr(yytext);
               return STR;
             }
 <STRING>\$\{  { BEGIN(INITIAL); return DOLLAR_CURLY; }
@@ -126,31 +126,31 @@ inherit     { return INHERIT; }
 
 \'\'(\ *\n)?     { BEGIN(IND_STRING); return IND_STRING_OPEN; }
 <IND_STRING>([^\$\']|\$[^\{\']|\'[^\'\$])+ {
-                   yylval->t = makeIndStr(toATerm(yytext));
+                   //yylval->t = makeIndStr(toATerm(yytext));
                    return IND_STR;
                  }
 <IND_STRING>\'\'\$ {
-                   yylval->t = makeIndStr(toATerm("$"));
+                   //yylval->t = makeIndStr(toATerm("$"));
                    return IND_STR;
                  }
 <IND_STRING>\'\'\' {
-                   yylval->t = makeIndStr(toATerm("''"));
+                   //yylval->t = makeIndStr(toATerm("''"));
                    return IND_STR;
                  }
 <IND_STRING>\'\'\\. {
-                   yylval->t = unescapeStr(yytext + 2);
+                   //yylval->t = unescapeStr(yytext + 2);
                    return IND_STR;
                  }
 <IND_STRING>\$\{ { BEGIN(INITIAL); return DOLLAR_CURLY; }
 <IND_STRING>\'\' { BEGIN(INITIAL); return IND_STRING_CLOSE; }
 <IND_STRING>\'   {
-                   yylval->t = makeIndStr(toATerm("'"));
+                   //yylval->t = makeIndStr(toATerm("'"));
                    return IND_STR;
                  }
 <IND_STRING>.    return yytext[0]; /* just in case: shouldn't be reached */
 
-{PATH}      { yylval->t = toATerm(yytext); return PATH; /* !!! alloc */ }
-{URI}       { yylval->t = toATerm(yytext); return URI; /* !!! alloc */ }
+{PATH}      { yylval->path = strdup(yytext); return PATH; }
+{URI}       { yylval->uri = strdup(yytext); return URI; }
 
 [ \t\r\n]+    /* eat up whitespace */
 \#[^\r\n]*    /* single-line comments */
diff --git a/src/libexpr/nixexpr-ast.def b/src/libexpr/nixexpr-ast.def
deleted file mode 100644
index 36c25dcfe7..0000000000
--- a/src/libexpr/nixexpr-ast.def
+++ /dev/null
@@ -1,97 +0,0 @@
-init initNixExprHelpers
-
-Pos | string int int | Pos |
-NoPos | | Pos |
-
-Function | Pattern Expr Pos | Expr |
-Assert | Expr Expr Pos | Expr |
-With | Expr Expr Pos | Expr |
-If | Expr Expr Expr | Expr |
-OpNot | Expr | Expr |
-OpEq | Expr Expr | Expr |
-OpNEq | Expr Expr | Expr |
-OpAnd | Expr Expr | Expr |
-OpOr | Expr Expr | Expr |
-OpImpl | Expr Expr | Expr |
-OpUpdate | Expr Expr | Expr |
-OpHasAttr | Expr string | Expr |
-OpPlus | Expr Expr | Expr |
-OpConcat | Expr Expr | Expr |
-ConcatStrings | ATermList | Expr |
-Call | Expr Expr | Expr |
-Select | Expr string | Expr |
-Var | string | Expr |
-Int | int | Expr |
-
-# Strings in the evaluator carry a so-called `context' (the ATermList)
-# which is a list of strings representing store paths.  This is to
-# allow users to write things like
-#
-#   "--with-freetype2-library=" + freetype + "/lib"
-#
-# where `freetype' is a derivation (or a source to be copied to the
-# store).  If we just concatenated the strings without keeping track
-# of the referenced store paths, then if the string is used as a
-# derivation attribute, the derivation will not have the correct
-# dependencies in its inputDrvs and inputSrcs.
-#
-# The semantics of the context is as follows: when a string with
-# context C is used as a derivation attribute, then the derivations in
-# C will be added to the inputDrvs of the derivation, and the other
-# store paths in C will be added to the inputSrcs of the derivations.
-#
-# For canonicity, the store paths should be in sorted order.
-Str | string ATermList | Expr |
-Str | string | Expr | ObsoleteStr
-
-# Internal to the parser, doesn't occur in ASTs.
-IndStr | string | Expr |
-
-# A path is a reference to a file system object that is to be copied
-# to the Nix store when used as a derivation attribute.  When it is
-# concatenated to a string (i.e., `str + path'), it is also copied and
-# the resulting store path is concatenated to the string (with the
-# store path in the context).  If a string or path is concatenated to
-# a path (i.e., `path + str' or `path + path'), the result is a new
-# path (if the right-hand side is a string, the context must be
-# empty).
-Path | string | Expr |
-
-List | ATermList | Expr |
-BlackHole | | Expr |
-Undefined | | Expr |
-Removed | | Expr |
-PrimOp | int ATermBlob ATermList | Expr |
-Attrs | ATermList | Expr |
-Closed | Expr | Expr |
-Rec | ATermList ATermList | Expr |
-Bool | ATermBool | Expr |
-Null | | Expr |
-
-Bind | string Expr Pos | ATerm |
-BindAttrPath | ATermList Expr Pos | ATerm | # desugared during parsing
-Bind | string Expr | ATerm | ObsoleteBind
-Inherit | Expr ATermList Pos | ATerm |
-
-Scope | | Expr |
-
-VarPat | string | Pattern |
-AttrsPat | ATermList ATermBool string | Pattern | # bool = `...'
-
-Formal | string DefaultValue | ATerm |
-
-DefaultValue | Expr | DefaultValue |
-NoDefaultValue | | DefaultValue |
-
-True | | ATermBool |
-False | | ATermBool |
-
-PrimOpDef | int ATermBlob | ATerm |
-
-AttrRHS | Expr Pos | ATerm |
-
-eTrue = makeBool(makeTrue())
-eFalse = makeBool(makeFalse())
-sOverrides = toATerm("__overrides")
-sNoAlias = toATerm("")
-sWith = toATerm("<with>")
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 3c5d02b34f..05dfbd3223 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -1,17 +1,94 @@
 #include "nixexpr.hh"
 #include "derivations.hh"
 #include "util.hh"
-#include "aterm.hh"
-
-#include "nixexpr-ast.hh"
-#include "nixexpr-ast.cc"
 
 #include <cstdlib>
 
 
 namespace nix {
-    
 
+
+std::ostream & operator << (std::ostream & str, Expr & e)
+{
+    e.show(str);
+    return str;
+}
+
+
+void ExprInt::show(std::ostream & str)
+{
+    str << n;
+}
+
+void ExprString::show(std::ostream & str)
+{
+    str << "\"" << s << "\""; // !!! escaping
+}
+
+void ExprPath::show(std::ostream & str)
+{
+    str << s;
+}
+
+void ExprVar::show(std::ostream & str)
+{
+    str << name;
+}
+
+void ExprSelect::show(std::ostream & str)
+{
+    str << "(" << *e << ")." << name;
+}
+
+void ExprAttrs::show(std::ostream & str)
+{
+    if (recursive) str << "rec ";
+    str << "{ ";
+    foreach (list<string>::iterator, i, inherited)
+        str << "inherited " << *i << "; ";
+    foreach (Attrs::iterator, i, attrs)
+        str << i->first << " = " << *i->second << "; ";
+    str << "}";
+}
+
+void ExprList::show(std::ostream & str)
+{
+    str << "[ ";
+    foreach (vector<Expr *>::iterator, i, elems)
+        str << "(" << **i << ") ";
+    str << "]";
+}
+
+void ExprLambda::show(std::ostream & str)
+{
+    str << "(";
+    if (matchAttrs) {
+        str << "{ ";
+        bool first = true;
+        foreach (Formals::Formals_::iterator, i, formals->formals) {
+            if (first) first = false; else str << ", ";
+            str << i->name;
+            if (i->def) str << " ? " << *i->def;
+        }
+        str << " }";
+        if (arg != "") str << " @ ";
+    }
+    if (arg != "") str << arg;
+    str << ": " << *body << ")";
+}
+
+void ExprWith::show(std::ostream & str)
+{
+    str << "with " << *attrs << "; " << *body;
+}
+
+void ExprIf::show(std::ostream & str)
+{
+    str << "if " << *cond << " then " << *then << " else " << *else_;
+}
+
+
+#if 0
 string showPos(ATerm pos)
 {
     ATerm path;
@@ -159,28 +236,7 @@ void checkVarDefs(const ATermMap & defs, Expr e)
     set<Expr> done;
     checkVarDefs2(done, defs, e);
 }
-
-
-bool matchStr(Expr e, string & s, PathSet & context)
-{
-    ATermList l;
-    ATerm s_;
-
-    if (!matchStr(e, s_, l)) return false;
-
-    s = aterm2String(s_);
-
-    for (ATermIterator i(l); i; ++i)
-        context.insert(aterm2String(*i));
-
-    return true;
-}
-
-
-Expr makeStr(const string & s, const PathSet & context)
-{
-    return makeStr(toATerm(s), toATermList(context));
-}
+#endif
 
 
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 9f1050d807..ebdfd0a152 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -3,7 +3,6 @@
 
 #include <map>
 
-#include "aterm-map.hh"
 #include "types.hh"
 
 
@@ -18,22 +17,152 @@ MakeError(Abort, EvalError)
 MakeError(TypeError, EvalError)
 
 
-/* Nix expressions are represented as ATerms.  The maximal sharing
-   property of the ATerm library allows us to implement caching of
-   normals forms efficiently. */
-typedef ATerm Expr;
-typedef ATerm DefaultValue;
-typedef ATerm Pos;
-typedef ATerm Pattern;
-typedef ATerm ATermBool;
+struct Pos
+{
+    string file;
+    unsigned int line, column;
+};
+
+
+/* Abstract syntax of Nix expressions. */
+
+struct Env;
+struct Value;
+struct EvalState;
+
+struct Expr
+{
+    virtual void show(std::ostream & str) = 0;
+    virtual void eval(EvalState & state, Env & env, Value & v)
+    {
+        throw Error("not implemented");
+    }
+};
+
+std::ostream & operator << (std::ostream & str, Expr & e);
+
+#define COMMON_METHODS \
+    void show(std::ostream & str); \
+    void eval(EvalState & state, Env & env, Value & v);
+
+struct ExprInt : Expr
+{
+    int n;
+    ExprInt(int n) : n(n) { };
+    COMMON_METHODS
+};
+
+struct ExprString : Expr
+{
+    string s;
+    ExprString(const string & s) : s(s) { };
+    COMMON_METHODS
+};
+
+struct ExprPath : Expr
+{
+    string s;
+    ExprPath(const string & s) : s(s) { };
+    COMMON_METHODS
+};
+
+struct ExprVar : Expr
+{
+    string name;
+    ExprVar(const string & name) : name(name) { };
+    COMMON_METHODS
+};
+
+struct ExprSelect : Expr
+{
+    Expr * e;
+    string name;
+    ExprSelect(Expr * e, const string & name) : e(e), name(name) { };
+    COMMON_METHODS
+};
+
+struct ExprAttrs : Expr
+{
+    bool recursive;
+    typedef std::map<string, Expr *> Attrs;
+    Attrs attrs;
+    list<string> inherited;
+    ExprAttrs() : recursive(false) { };
+    COMMON_METHODS
+};
 
+struct ExprList : Expr
+{
+    std::vector<Expr *> elems;
+    ExprList() { };
+    COMMON_METHODS
+};
 
-/* A STL vector of ATerms.  Should be used with great care since it's
-   stored on the heap, and the elements are therefore not roots to the
-   ATerm garbage collector. */
-typedef vector<ATerm> ATermVector;
+struct Formal
+{
+    string name;
+    Expr * def;
+    Formal(const string & name, Expr * def) : name(name), def(def) { };
+};
 
+struct Formals
+{
+    typedef std::list<Formal> Formals_;
+    Formals_ formals;
+    bool ellipsis;
+};
 
+struct ExprLambda : Expr
+{
+    Pos pos;
+    string arg;
+    bool matchAttrs;
+    Formals * formals;
+    Expr * body;
+    ExprLambda(const Pos & pos, const string & arg, bool matchAttrs, Formals * formals, Expr * body)
+        : pos(pos), arg(arg), matchAttrs(matchAttrs), formals(formals), body(body) { };
+    COMMON_METHODS
+};
+
+struct ExprWith : Expr
+{
+    Pos pos;
+    Expr * attrs, * body;
+    ExprWith(const Pos & pos, Expr * attrs, Expr * body) : pos(pos), attrs(attrs), body(body) { };
+    COMMON_METHODS
+};
+
+struct ExprIf : Expr
+{
+    Expr * cond, * then, * else_;
+    ExprIf(Expr * cond, Expr * then, Expr * else_) : cond(cond), then(then), else_(else_) { };
+    COMMON_METHODS
+};
+
+#define MakeBinOp(name, s) \
+    struct Expr##name : Expr \
+    { \
+        Expr * e1, * e2; \
+        Expr##name(Expr * e1, Expr * e2) : e1(e1), e2(e2) { }; \
+        void show(std::ostream & str) \
+        { \
+            str << *e1 << " " s " " << *e2; \
+        } \
+        void eval(EvalState & state, Env & env, Value & v); \
+    };
+
+MakeBinOp(App, "")
+MakeBinOp(OpEq, "==")
+MakeBinOp(OpNEq, "!=")
+MakeBinOp(OpAnd, "&&")
+MakeBinOp(OpOr, "||")
+MakeBinOp(OpImpl, "->")
+MakeBinOp(OpUpdate, "//")
+MakeBinOp(OpConcatStrings, "+")
+MakeBinOp(OpConcatLists, "++")
+
+
+#if 0
 /* Show a position. */
 string showPos(ATerm pos);
 
@@ -56,13 +185,7 @@ Expr makeAttrs(const ATermMap & attrs);
 /* Check whether all variables are defined in the given expression.
    Throw an exception if this isn't the case. */
 void checkVarDefs(const ATermMap & def, Expr e);
-
-
-/* Manipulation of Str() nodes.  Note: matchStr() does not clear
-   context!  */
-bool matchStr(Expr e, string & s, PathSet & context);
-
-Expr makeStr(const string & s, const PathSet & context = PathSet());
+#endif
 
 
 }
diff --git a/src/libexpr/parser.hh b/src/libexpr/parser.hh
index 3f430eb325..d1e531ca29 100644
--- a/src/libexpr/parser.hh
+++ b/src/libexpr/parser.hh
@@ -9,11 +9,10 @@ namespace nix {
 
 /* Parse a Nix expression from the specified file.  If `path' refers
    to a directory, then "/default.nix" is appended. */
-Expr parseExprFromFile(EvalState & state, Path path);
+Expr * parseExprFromFile(Path path);
 
 /* Parse a Nix expression from the specified string. */
-Expr parseExprFromString(EvalState & state, const string & s,
-    const Path & basePath);
+Expr * parseExprFromString(const string & s, const Path & basePath);
 
 
 }
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index a28d56d24f..96fbe2cb4b 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -23,13 +23,12 @@
 #include "aterm.hh"
 #include "util.hh"
     
+#include "nixexpr.hh"
+
 #include "parser-tab.hh"
 #include "lexer-tab.hh"
 #define YYSTYPE YYSTYPE // workaround a bug in Bison 2.4
 
-#include "nixexpr.hh"
-#include "nixexpr-ast.hh"
-
 
 using namespace nix;
 
@@ -39,13 +38,14 @@ namespace nix {
     
 struct ParseData 
 {
-    Expr result;
+    Expr * result;
     Path basePath;
     Path path;
     string error;
 };
- 
 
+
+#if 0
 static string showAttrPath(ATermList attrPath)
 {
     string s;
@@ -79,10 +79,12 @@ static ATermList buildAttrs(const Tree & t, ATermList & nonrec)
                 : makeBind(i->first, makeAttrs(buildAttrs(i->second, nonrec)), makeNoPos()));
     return res;
 }
+#endif
  
 
-static Expr fixAttrs(bool recursive, ATermList as)
+static void fixAttrs(ExprAttrs & attrs)
 {
+#if 0
     Tree attrs;
 
     /* This ATermMap is needed to ensure that the `leaf' fields in the
@@ -135,9 +137,11 @@ static Expr fixAttrs(bool recursive, ATermList as)
     ATermList rec = buildAttrs(attrs, nonrec);
         
     return recursive ? makeRec(rec, nonrec) : makeAttrs(rec);
+#endif
 }
 
 
+#if 0
 static void checkPatternVars(ATerm pos, ATermMap & map, Pattern pat)
 {
     ATerm name = sNoAlias;
@@ -261,6 +265,7 @@ static Expr stripIndentation(ATermList es)
 
     return makeConcatStrings(ATreverse(es2));
 }
+#endif
 
 
 void backToString(yyscan_t scanner);
@@ -269,8 +274,11 @@ void backToIndString(yyscan_t scanner);
 
 static Pos makeCurPos(YYLTYPE * loc, ParseData * data)
 {
-    return makePos(toATerm(data->path),
-        loc->first_line, loc->first_column);
+    Pos pos;
+    pos.file = data->path;
+    pos.line = loc->first_line;
+    pos.column = loc->first_column;
+    return pos;
 }
 
 #define CUR_POS makeCurPos(yylocp, data)
@@ -311,22 +319,31 @@ static void freeAndUnprotect(void * p)
 %}
 
 %union {
-  ATerm t;
-  ATermList ts;
-  struct {
-    ATermList formals;
-    bool ellipsis;
-  } formals;
+  nix::Expr * e;
+  nix::ExprList * list;
+  nix::ExprAttrs * attrs;
+  nix::Formals * formals;
+  nix::Formal * formal;
   int n;
+  char * id;
+  char * path;
+  char * uri;
+  std::list<std::string> * ids;
 }
 
-%type <t> start expr expr_function expr_if expr_op
-%type <t> expr_app expr_select expr_simple bind inheritsrc formal
-%type <t> pattern
-%type <ts> binds ids attrpath expr_list string_parts ind_string_parts
+%type <e> start expr expr_function expr_if expr_op
+%type <e> expr_app expr_select expr_simple
+%type <list> expr_list
+%type <attrs> binds
+%type <ts> attrpath string_parts ind_string_parts
 %type <formals> formals
-%token <t> ID STR IND_STR PATH URI
+%type <formal> formal
+%type <ids> ids
+%token <id> ID ATTRPATH
+%token <t> STR IND_STR
 %token <n> INT
+%token <path> PATH
+%token <uri> URI
 %token IF THEN ELSE ASSERT WITH LET IN REC INHERIT EQ NEQ AND OR IMPL
 %token DOLLAR_CURLY /* == ${ */
 %token IND_STRING_OPEN IND_STRING_CLOSE
@@ -350,54 +367,63 @@ start: expr { data->result = $1; };
 expr: expr_function;
 
 expr_function
-  : pattern ':' expr_function
-    { checkPatternVars(CUR_POS, $1); $$ = makeFunction($1, $3, CUR_POS); }
-  | ASSERT expr ';' expr_function
+  : ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, $1, false, 0, $3); /* checkPatternVars(CUR_POS, $1); $$ = makeFunction($1, $3, CUR_POS); */ }
+  | '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, "", true, $2, $5); }
+  | '{' formals '}' '@' ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, $5, true, $2, $7); }
+  | ID '@' '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, $1, true, $4, $7); }
+  /* | ASSERT expr ';' expr_function
     { $$ = makeAssert($2, $4, CUR_POS); }
+    */
   | WITH expr ';' expr_function
-    { $$ = makeWith($2, $4, CUR_POS); }
+    { $$ = new ExprWith(CUR_POS, $2, $4); }
   | LET binds IN expr_function
-    { $$ = makeSelect(fixAttrs(true, ATinsert($2, makeBindAttrPath(ATmakeList1(toATerm("<let-body>")), $4, CUR_POS))), toATerm("<let-body>")); }
+    { $2->attrs["<let-body>"] = $4; $2->recursive = true; fixAttrs(*$2); $$ = new ExprSelect($2, "<let-body>"); }
   | expr_if
   ;
 
 expr_if
-  : IF expr THEN expr ELSE expr
-    { $$ = makeIf($2, $4, $6); }
+  : IF expr THEN expr ELSE expr { $$ = new ExprIf($2, $4, $6); }
   | expr_op
   ;
 
 expr_op
-  : '!' expr_op %prec NEG { $$ = makeOpNot($2); }
-  | expr_op EQ expr_op { $$ = makeOpEq($1, $3); }
-  | expr_op NEQ expr_op { $$ = makeOpNEq($1, $3); }
-  | expr_op AND expr_op { $$ = makeOpAnd($1, $3); }
-  | expr_op OR expr_op { $$ = makeOpOr($1, $3); }
-  | expr_op IMPL expr_op { $$ = makeOpImpl($1, $3); }
-  | expr_op UPDATE expr_op { $$ = makeOpUpdate($1, $3); }
+  : /* '!' expr_op %prec NEG { $$ = makeOpNot($2); }
+       | */
+    expr_op EQ expr_op { $$ = new ExprOpEq($1, $3); }
+  | expr_op NEQ expr_op { $$ = new ExprOpNEq($1, $3); }
+  | expr_op AND expr_op { $$ = new ExprOpAnd($1, $3); }
+  | expr_op OR expr_op { $$ = new ExprOpOr($1, $3); }
+  | expr_op IMPL expr_op { $$ = new ExprOpImpl($1, $3); }
+  | expr_op UPDATE expr_op { $$ = new ExprOpUpdate($1, $3); }
+  /*
   | expr_op '?' ID { $$ = makeOpHasAttr($1, $3); }
-  | expr_op '+' expr_op { $$ = makeConcatStrings(ATmakeList2($1, $3)); }
-  | expr_op CONCAT expr_op { $$ = makeOpConcat($1, $3); }
+  */
+  | expr_op '+' expr_op { $$ = new ExprOpConcatStrings($1, $3); }
+  | expr_op CONCAT expr_op { $$ = new ExprOpConcatLists($1, $3); }
   | expr_app
   ;
 
 expr_app
   : expr_app expr_select
-    { $$ = makeCall($1, $2); }
+    { $$ = new ExprApp($1, $2); }
   | expr_select { $$ = $1; }
   ;
 
 expr_select
   : expr_select '.' ID
-    { $$ = makeSelect($1, $3); }
+    { $$ = new ExprSelect($1, $3); }
   | expr_simple { $$ = $1; }
   ;
 
 expr_simple
-  : ID { $$ = makeVar($1); }
-  | INT { $$ = makeInt($1); }
+  : ID { $$ = new ExprVar($1); }
+  | INT { $$ = new ExprInt($1); } /*
   | '"' string_parts '"' {
-      /* For efficiency, and to simplify parse trees a bit. */
+      /* For efficiency, and to simplify parse trees a bit. * /
       if ($2 == ATempty) $$ = makeStr(toATerm(""), ATempty);
       else if (ATgetNext($2) == ATempty) $$ = ATgetFirst($2);
       else $$ = makeConcatStrings(ATreverse($2));
@@ -405,18 +431,21 @@ expr_simple
   | IND_STRING_OPEN ind_string_parts IND_STRING_CLOSE {
       $$ = stripIndentation(ATreverse($2));
   }
-  | PATH { $$ = makePath(toATerm(absPath(aterm2String($1), data->basePath))); }
-  | URI { $$ = makeStr($1, ATempty); }
+                                  */
+  | PATH { $$ = new ExprPath(absPath($1, data->basePath)); }
+  | URI { $$ = new ExprString($1); }
   | '(' expr ')' { $$ = $2; }
+/*
   /* Let expressions `let {..., body = ...}' are just desugared
-     into `(rec {..., body = ...}).body'. */
+     into `(rec {..., body = ...}).body'. * /
   | LET '{' binds '}'
     { $$ = makeSelect(fixAttrs(true, $3), toATerm("body")); }
+  */
   | REC '{' binds '}'
-    { $$ = fixAttrs(true, $3); }
+    { fixAttrs(*$3); $3->recursive = true; $$ = $3; }
   | '{' binds '}'
-    { $$ = fixAttrs(false, $2); }
-  | '[' expr_list ']' { $$ = makeList(ATreverse($2)); }
+    { fixAttrs(*$2); $$ = $2; }
+  | '[' expr_list ']' { $$ = $2; }
   ;
 
 string_parts
@@ -431,63 +460,56 @@ ind_string_parts
   | { $$ = ATempty; }
   ;
 
-pattern
-  : ID { $$ = makeVarPat($1); }
-  | '{' formals '}' { $$ = makeAttrsPat($2.formals, $2.ellipsis ? eTrue : eFalse, sNoAlias); }
-  | '{' formals '}' '@' ID { $$ = makeAttrsPat($2.formals, $2.ellipsis ? eTrue : eFalse, $5); }
-  | ID '@' '{' formals '}' { $$ = makeAttrsPat($4.formals, $4.ellipsis ? eTrue : eFalse, $1); }
-  ;
-
 binds
-  : binds bind { $$ = ATinsert($1, $2); }
-  | { $$ = ATempty; }
-  ;
-
-bind
-  : attrpath '=' expr ';'
-    { $$ = makeBindAttrPath(ATreverse($1), $3, CUR_POS); }
-  | INHERIT inheritsrc ids ';'
-    { $$ = makeInherit($2, $3, CUR_POS); }
+  : binds ID '=' expr ';' { $$ = $1; $$->attrs[$2] = $4; }
+  | binds INHERIT ids ';'
+    { $$ = $1;
+      foreach (list<string>::iterator, i, *$3)
+        $$->inherited.push_back(*i);
+    }
+  | binds INHERIT '(' expr ')' ids ';'
+    { $$ = $1;
+      /* !!! Should ensure sharing of the expression in $4. */
+      foreach (list<string>::iterator, i, *$6)
+        $$->attrs[*i] = new ExprSelect($4, *i);
+    }
+  | { $$ = new ExprAttrs; }
   ;
 
-inheritsrc
-  : '(' expr ')' { $$ = $2; }
-  | { $$ = makeScope(); }
+ids
+  : ids ID { $$ = $1; $1->push_back($2); /* !!! dangerous */ }
+  | { $$ = new list<string>; }
   ;
 
-ids: ids ID { $$ = ATinsert($1, $2); } | { $$ = ATempty; };
-
 attrpath
   : attrpath '.' ID { $$ = ATinsert($1, $3); }
   | ID { $$ = ATmakeList1($1); }
   ;
 
 expr_list
-  : expr_list expr_select { $$ = ATinsert($1, $2); }
-  | { $$ = ATempty; }
+  : expr_list expr_select { $$ = $1; $1->elems.push_back($2); /* !!! dangerous */ }
+  | { $$ = new ExprList; }
   ;
 
 formals
-  : formal ',' formals /* !!! right recursive */
-    { $$.formals = ATinsert($3.formals, $1); $$.ellipsis = $3.ellipsis; }
+  : formal ',' formals
+    { $$ = $3; $$->formals.push_front(*$1); /* !!! dangerous */ }
   | formal
-    { $$.formals = ATinsert(ATempty, $1); $$.ellipsis = false; }
+    { $$ = new Formals; $$->formals.push_back(*$1); $$->ellipsis = false; }
   |
-    { $$.formals = ATempty; $$.ellipsis = false; }
+    { $$ = new Formals; $$->ellipsis = false; }
   | ELLIPSIS
-    { $$.formals = ATempty; $$.ellipsis = true; }
+    { $$ = new Formals; $$->ellipsis = true; }
   ;
 
 formal
-  : ID { $$ = makeFormal($1, makeNoDefaultValue()); }
-  | ID '?' expr { $$ = makeFormal($1, makeDefaultValue($3)); }
+  : ID { $$ = new Formal($1, 0); }
+  | ID '?' expr { $$ = new Formal($1, $3); }
   ;
   
 %%
 
 
-#include "eval.hh"  
-
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
@@ -497,9 +519,7 @@ formal
 namespace nix {
       
 
-static Expr parse(EvalState & state,
-    const char * text, const Path & path,
-    const Path & basePath)
+static Expr * parse(const char * text, const Path & path, const Path & basePath)
 {
     yyscan_t scanner;
     ParseData data;
@@ -523,7 +543,7 @@ static Expr parse(EvalState & state,
 }
 
 
-Expr parseExprFromFile(EvalState & state, Path path)
+Expr * parseExprFromFile(Path path)
 {
     assert(path[0] == '/');
 
@@ -544,14 +564,13 @@ Expr parseExprFromFile(EvalState & state, Path path)
         path = canonPath(path + "/default.nix");
 
     /* Read and parse the input file. */
-    return parse(state, readFile(path).c_str(), path, dirOf(path));
+    return parse(readFile(path).c_str(), path, dirOf(path));
 }
 
 
-Expr parseExprFromString(EvalState & state,
-    const string & s, const Path & basePath)
+Expr * parseExprFromString(const string & s, const Path & basePath)
 {
-    return parse(state, s.c_str(), "(string)", basePath);
+    return parse(s.c_str(), "(string)", basePath);
 }
 
  
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 74eb2b26d0..cd40ade008 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -5,7 +5,6 @@
 #include "util.hh"
 #include "archive.hh"
 #include "value-to-xml.hh"
-#include "nixexpr-ast.hh"
 #include "parser.hh"
 #include "names.hh"
 
@@ -281,7 +280,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
 
     /* Figure out the name first (for stack backtraces). */
-    Bindings::iterator attr = args[0]->attrs->find(toATerm("name"));
+    Bindings::iterator attr = args[0]->attrs->find("name");
     if (attr == args[0]->attrs->end())
         throw EvalError("required attribute `name' missing");
     string drvName;
@@ -302,7 +301,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     bool outputHashRecursive = false;
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
-        string key = aterm2String(i->first);
+        string key = i->first;
         startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
 
         try {
@@ -449,8 +448,8 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
 
     /* !!! assumes a single output */
     state.mkAttrs(v);
-    mkString((*v.attrs)[toATerm("outPath")], outPath, singleton<PathSet>(drvPath));
-    mkString((*v.attrs)[toATerm("drvPath")], drvPath, singleton<PathSet>("=" + drvPath));
+    mkString((*v.attrs)["outPath"], outPath, singleton<PathSet>(drvPath));
+    mkString((*v.attrs)["drvPath"], drvPath, singleton<PathSet>("=" + drvPath));
 }
 
 
@@ -655,7 +654,7 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v)
 
     StringSet names;
     foreach (Bindings::iterator, i, *args[0]->attrs)
-        names.insert(aterm2String(i->first));
+        names.insert(i->first);
 
     unsigned int n = 0;
     foreach (StringSet::iterator, i, names)
@@ -668,7 +667,7 @@ static void prim_getAttr(EvalState & state, Value * * args, Value & v)
 {
     string attr = state.forceStringNoCtx(*args[0]);
     state.forceAttrs(*args[1]);
-    Bindings::iterator i = args[1]->attrs->find(toATerm(attr));
+    Bindings::iterator i = args[1]->attrs->find(attr);
     if (i == args[1]->attrs->end())
         throw EvalError(format("attribute `%1%' missing") % attr);
     state.forceValue(i->second);
@@ -681,7 +680,7 @@ static void prim_hasAttr(EvalState & state, Value * * args, Value & v)
 {
     string attr = state.forceStringNoCtx(*args[0]);
     state.forceAttrs(*args[1]);
-    mkBool(v, args[1]->attrs->find(toATerm(attr)) != args[1]->attrs->end());
+    mkBool(v, args[1]->attrs->find(attr) != args[1]->attrs->end());
 }
 
 
@@ -702,7 +701,7 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
 
     for (unsigned int i = 0; i < args[1]->list.length; ++i) {
         state.forceStringNoCtx(args[1]->list.elems[i]);
-        v.attrs->erase(toATerm(args[1]->list.elems[i].string.s));
+        v.attrs->erase(args[1]->list.elems[i].string.s);
     }
 }
 
@@ -721,16 +720,16 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
         Value & v2(args[0]->list.elems[i]);
         state.forceAttrs(v2);
         
-        Bindings::iterator j = v2.attrs->find(toATerm("name"));
+        Bindings::iterator j = v2.attrs->find("name");
         if (j == v2.attrs->end())
             throw TypeError("`name' attribute missing in a call to `listToAttrs'");
         string name = state.forceStringNoCtx(j->second);
         
-        j = v2.attrs->find(toATerm("value"));
+        j = v2.attrs->find("value");
         if (j == v2.attrs->end())
             throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-        (*v.attrs)[toATerm(name)] = j->second; // !!! sharing?
+        (*v.attrs)[name] = j->second; // !!! sharing?
     }
 }
 
@@ -977,8 +976,8 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
     string name = state.forceStringNoCtx(*args[0]);
     DrvName parsed(name);
     state.mkAttrs(v);
-    mkString((*v.attrs)[toATerm("name")], parsed.name);
-    mkString((*v.attrs)[toATerm("version")], parsed.version);
+    mkString((*v.attrs)["name"], parsed.name);
+    mkString((*v.attrs)["version"], parsed.version);
 }
 
 
@@ -999,10 +998,9 @@ void EvalState::createBaseEnv()
 {
     baseEnv.up = 0;
 
-    {   Value & v = baseEnv.bindings[toATerm("builtins")];
-        v.type = tAttrs;
-        v.attrs = new Bindings;
-    }
+    Value & builtins = baseEnv.bindings["builtins"];
+    builtins.type = tAttrs;
+    builtins.attrs = new Bindings;
 
     /* Add global constants such as `true' to the base environment. */
     Value v;
@@ -1025,8 +1023,8 @@ void EvalState::createBaseEnv()
     /* Add a wrapper around the derivation primop that computes the
        `drvPath' and `outPath' attributes lazily. */
     string s = "attrs: let res = derivationStrict attrs; in attrs // { drvPath = res.drvPath; outPath = res.outPath; type = \"derivation\"; }";
-    mkThunk(v, baseEnv, parseExprFromString(*this, s, "/"));
-    addConstant("derivation", v);
+    //mkThunk(v, baseEnv, parseExprFromString(s, "/"));
+    //addConstant("derivation", v);
 
     // Miscellaneous
     addPrimOp("import", 1, prim_import);
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index eff414aba3..c8a067aacf 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -1,7 +1,5 @@
 #include "value-to-xml.hh"
 #include "xml-writer.hh"
-#include "nixexpr-ast.hh"
-#include "aterm.hh"
 #include "util.hh"
 
 #include <cstdlib>
@@ -27,31 +25,10 @@ static void showAttrs(EvalState & state, bool strict, Bindings & attrs,
 {
     StringSet names;
     foreach (Bindings::iterator, i, attrs)
-        names.insert(aterm2String(i->first));
+        names.insert(i->first);
     foreach (StringSet::iterator, i, names) {
         XMLOpenElement _(doc, "attr", singletonAttrs("name", *i));
-        printValueAsXML(state, strict, attrs[toATerm(*i)], doc, context, drvsSeen);
-    }
-}
-
-
-static void printPatternAsXML(Pattern pat, XMLWriter & doc)
-{
-    ATerm name;
-    ATermList formals;
-    ATermBool ellipsis;
-    if (matchVarPat(pat, name))
-        doc.writeEmptyElement("varpat", singletonAttrs("name", aterm2String(name)));
-    else if (matchAttrsPat(pat, formals, ellipsis, name)) {
-        XMLAttrs attrs;
-        if (name != sNoAlias) attrs["name"] = aterm2String(name);
-        if (ellipsis == eTrue) attrs["ellipsis"] = "1";
-        XMLOpenElement _(doc, "attrspat", attrs);
-        for (ATermIterator i(formals); i; ++i) {
-            Expr name; ATerm dummy;
-            if (!matchFormal(*i, name, dummy)) abort();
-            doc.writeEmptyElement("attr", singletonAttrs("name", aterm2String(name)));
-        }
+        printValueAsXML(state, strict, attrs[*i], doc, context, drvsSeen);
     }
 }
 
@@ -90,14 +67,14 @@ static void printValueAsXML(EvalState & state, bool strict, Value & v,
             if (state.isDerivation(v)) {
                 XMLAttrs xmlAttrs;
             
-                Bindings::iterator a = v.attrs->find(toATerm("derivation"));
+                Bindings::iterator a = v.attrs->find("derivation");
 
                 Path drvPath;
-                a = v.attrs->find(toATerm("drvPath"));
+                a = v.attrs->find("drvPath");
                 if (a != v.attrs->end() && a->second.type == tString)
                     xmlAttrs["drvPath"] = drvPath = a->second.string.s;
         
-                a = v.attrs->find(toATerm("outPath"));
+                a = v.attrs->find("outPath");
                 if (a != v.attrs->end() && a->second.type == tString)
                     xmlAttrs["outPath"] = a->second.string.s;
 
@@ -126,7 +103,15 @@ static void printValueAsXML(EvalState & state, bool strict, Value & v,
 
         case tLambda: {
             XMLOpenElement _(doc, "function");
-            printPatternAsXML(v.lambda.pat, doc);
+            if (v.lambda.fun->matchAttrs) {
+                XMLAttrs attrs;
+                if (!v.lambda.fun->arg.empty()) attrs["name"] = v.lambda.fun->arg;
+                if (v.lambda.fun->formals->ellipsis) attrs["ellipsis"] = "1";
+                XMLOpenElement _(doc, "attrspat", attrs);
+                foreach (Formals::Formals_::iterator, i, v.lambda.fun->formals->formals)
+                    doc.writeEmptyElement("attr", singletonAttrs("name", i->name));
+            } else
+                doc.writeEmptyElement("varpat", singletonAttrs("name", v.lambda.fun->arg));
             break;
         }