* Merged the `fast-eval' branch.

21 files changed, 2522 insertions, 2313 deletions

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index e16600fbf..e7228e183 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -2,27 +2,25 @@ pkglib_LTLIBRARIES = libexpr.la
 
 libexpr_la_SOURCES = \
  nixexpr.cc eval.cc primops.cc lexer-tab.cc parser-tab.cc \
- get-drvs.cc attr-path.cc expr-to-xml.cc common-opts.cc \
+ get-drvs.cc attr-path.cc value-to-xml.cc common-opts.cc \
  names.cc
 
 pkginclude_HEADERS = \
  nixexpr.hh eval.hh parser.hh lexer-tab.hh parser-tab.hh \
- get-drvs.hh attr-path.hh expr-to-xml.hh common-opts.hh \
- names.hh nixexpr-ast.hh
+ get-drvs.hh attr-path.hh value-to-xml.hh common-opts.hh \
+ names.hh symbol-table.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} \
+ -I$(srcdir)/.. \
  -I$(srcdir)/../libutil -I$(srcdir)/../libstore
-AM_CFLAGS = \
- ${aterm_include}
 
 
 # Parser generation.
@@ -34,15 +32,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 e8e4c050c..0660ba1c1 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -1,23 +1,12 @@
 #include "attr-path.hh"
-#include "nixexpr-ast.hh"
 #include "util.hh"
 
 
 namespace nix {
 
 
-bool isAttrs(EvalState & state, Expr e, ATermMap & attrs)
-{
-    e = evalExpr(state, e);
-    ATermList dummy;
-    if (!matchAttrs(e, dummy)) return false;
-    queryAllAttrs(e, attrs, false);
-    return true;
-}
-
-
-Expr findAlongAttrPath(EvalState & state, const string & attrPath,
-    const ATermMap & autoArgs, Expr e)
+void findAlongAttrPath(EvalState & state, const string & attrPath,
+    const Bindings & autoArgs, Expr * e, Value & v)
 {
     Strings tokens = tokenizeString(attrPath, ".");
 
@@ -25,8 +14,10 @@ Expr findAlongAttrPath(EvalState & state, const string & attrPath,
         Error(format("attribute selection path `%1%' does not match expression") % attrPath);
 
     string curPath;
+
+    state.mkThunk_(v, e);
     
-    for (Strings::iterator i = tokens.begin(); i != tokens.end(); ++i) {
+    foreach (Strings::iterator, i, tokens) {
 
         if (!curPath.empty()) curPath += ".";
         curPath += *i;
@@ -38,7 +29,10 @@ Expr findAlongAttrPath(EvalState & state, const string & attrPath,
         if (string2Int(attr, attrIndex)) apType = apIndex;
 
         /* Evaluate the expression. */
-        e = evalExpr(state, autoCallFunction(evalExpr(state, e), autoArgs));
+        Value vTmp;
+        state.autoCallFunction(autoArgs, v, vTmp);
+        v = vTmp;
+        state.forceValue(v);
 
         /* It should evaluate to either an attribute set or an
            expression, according to what is specified in the
@@ -46,36 +40,31 @@ Expr findAlongAttrPath(EvalState & state, const string & attrPath,
 
         if (apType == apAttr) {
 
-            ATermMap attrs;
-
-            if (!isAttrs(state, e, attrs))
+            if (v.type != tAttrs)
                 throw TypeError(
                     format("the expression selected by the selection path `%1%' should be an attribute set but is %2%")
-                    % curPath % showType(e));
-                
-            e = attrs.get(toATerm(attr));
-            if (!e)
-                throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
+                    % curPath % showType(v));
 
+            Bindings::iterator a = v.attrs->find(state.symbols.create(attr));
+            if (a == v.attrs->end())
+                throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
+            v = a->second.value;
         }
 
         else if (apType == apIndex) {
 
-            ATermList es;
-            if (!matchList(e, es))
+            if (v.type != tList)
                 throw TypeError(
                     format("the expression selected by the selection path `%1%' should be a list but is %2%")
-                    % curPath % showType(e));
+                    % curPath % showType(v));
 
-            e = ATelementAt(es, attrIndex);
-            if (!e)
-                throw Error(format("list index %1% in selection path `%2%' not found") % attrIndex % curPath);
-            
+            if (attrIndex >= v.list.length)
+                throw Error(format("list index %1% in selection path `%2%' is out of range") % attrIndex % curPath);
+
+            v = *v.list.elems[attrIndex];
         }
         
     }
-    
-    return e;
 }
 
  
diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh
index 7abaa83a0..33587e5ed 100644
--- a/src/libexpr/attr-path.hh
+++ b/src/libexpr/attr-path.hh
@@ -10,8 +10,8 @@
 namespace nix {
 
     
-Expr findAlongAttrPath(EvalState & state, const string & attrPath,
-    const ATermMap & autoArgs, Expr e);
+void findAlongAttrPath(EvalState & state, const string & attrPath,
+    const Bindings & autoArgs, Expr * e, Value & v);
 
     
 }
diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 9e3f8f961..5a4856568 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -9,7 +9,7 @@ namespace nix {
 
 bool parseOptionArg(const string & arg, Strings::iterator & i,
     const Strings::iterator & argsEnd, EvalState & state,
-    ATermMap & autoArgs)
+    Bindings & autoArgs)
 {
     if (arg != "--arg" && arg != "--argstr") return false;
 
@@ -19,11 +19,13 @@ bool parseOptionArg(const string & arg, Strings::iterator & i,
     string name = *i++;
     if (i == argsEnd) throw error;
     string value = *i++;
-    
-    Expr e = arg == "--arg"
-        ? parseExprFromString(state, value, absPath("."))
-        : makeStr(value);
-    autoArgs.set(toATerm(name), e);
+
+    Value & v(autoArgs[state.symbols.create(name)].value);
+
+    if (arg == "--arg")
+        state.mkThunk_( v, parseExprFromString(state, value, absPath(".")));
+    else
+        mkString(v, value);
     
     return true;
 }
diff --git a/src/libexpr/common-opts.hh b/src/libexpr/common-opts.hh
index fb9659cdc..80298ce55 100644
--- a/src/libexpr/common-opts.hh
+++ b/src/libexpr/common-opts.hh
@@ -9,7 +9,7 @@ namespace nix {
 /* Some common option parsing between nix-env and nix-instantiate. */
 bool parseOptionArg(const string & arg, Strings::iterator & i,
     const Strings::iterator & argsEnd, EvalState & state,
-    ATermMap & autoArgs);
+    Bindings & autoArgs);
     
 }
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index cd9c64594..26739faf6 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -4,9 +4,10 @@
 #include "util.hh"
 #include "store-api.hh"
 #include "derivations.hh"
-#include "nixexpr-ast.hh"
 #include "globals.hh"
 
+#include <cstring>
+
 
 #define LocalNoInline(f) static f __attribute__((noinline)); f
 #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f
@@ -15,23 +16,139 @@
 namespace nix {
     
 
-EvalState::EvalState()
-    : normalForms(32768), primOps(128)
+std::ostream & operator << (std::ostream & str, Value & v)
 {
-    nrEvaluated = nrCached = 0;
+    switch (v.type) {
+    case tInt:
+        str << v.integer;
+        break;
+    case tBool:
+        str << (v.boolean ? "true" : "false");
+        break;
+    case tString:
+        str << "\"";
+        for (const char * i = v.string.s; *i; i++)
+            if (*i == '\"' || *i == '\\') str << "\\" << *i;
+            else if (*i == '\n') str << "\\n";
+            else if (*i == '\r') str << "\\r";
+            else if (*i == '\t') str << "\\t";
+            else str << *i;
+        str << "\"";
+        break;
+    case tPath:
+        str << v.path; // !!! escaping?
+        break;
+    case tNull:
+        str << "true";
+        break;
+    case tAttrs: {
+        str << "{ ";
+        typedef std::map<string, Value *> Sorted;
+        Sorted sorted;
+        foreach (Bindings::iterator, i, *v.attrs)
+            sorted[i->first] = &i->second.value;
+        foreach (Sorted::iterator, i, sorted)
+            str << i->first << " = " << *i->second << "; ";
+        str << "}";
+        break;
+    }
+    case tList:
+        str << "[ ";
+        for (unsigned int n = 0; n < v.list.length; ++n)
+            str << *v.list.elems[n] << " ";
+        str << "]";
+        break;
+    case tThunk:
+    case tCopy:
+        str << "<CODE>";
+        break;
+    case tLambda:
+        str << "<LAMBDA>";
+        break;
+    case tPrimOp:
+        str << "<PRIMOP>";
+        break;
+    case tPrimOpApp:
+        str << "<PRIMOP-APP>";
+        break;
+    default:
+        throw Error("invalid value");
+    }
+    return str;
+}
 
-    initNixExprHelpers();
 
-    addPrimOps();
+string showType(const Value & v)
+{
+    switch (v.type) {
+        case tInt: return "an integer";
+        case tBool: return "a boolean";
+        case tString: return "a string";
+        case tPath: return "a path";
+        case tNull: return "null";
+        case tAttrs: return "an attribute set";
+        case tList: return "a list";
+        case tThunk: return "a thunk";
+        case tApp: return "a function application";
+        case tLambda: return "a function";
+        case tCopy: return "a copy";
+        case tBlackhole: return "a black hole";
+        case tPrimOp: return "a built-in function";
+        case tPrimOpApp: return "a partially applied built-in function";
+    }
+    abort();
+}
 
+
+EvalState::EvalState()
+    : sWith(symbols.create("<with>"))
+    , sOutPath(symbols.create("outPath"))
+    , sDrvPath(symbols.create("drvPath"))
+    , sType(symbols.create("type"))
+    , sMeta(symbols.create("meta"))
+    , sName(symbols.create("name"))
+    , sSystem(symbols.create("system"))
+    , baseEnv(allocEnv(128))
+    , baseEnvDispl(0)
+    , staticBaseEnv(false, 0)
+{
+    nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
+    nrEvaluated = recursionDepth = maxRecursionDepth = 0;
+    deepestStack = (char *) -1;
+
+    createBaseEnv();
+    
     allowUnsafeEquality = getEnv("NIX_NO_UNSAFE_EQ", "") == "";
 }
 
 
+EvalState::~EvalState()
+{
+    assert(recursionDepth == 0);
+}
+
+
+void EvalState::addConstant(const string & name, Value & v)
+{
+    staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
+    baseEnv.values[baseEnvDispl++] = v;
+    string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
+}
+
+
 void EvalState::addPrimOp(const string & name,
     unsigned int arity, PrimOp primOp)
 {
-    primOps.set(toATerm(name), makePrimOpDef(arity, ATmakeBlob(0, (void *) primOp)));
+    Value v;
+    string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+    v.type = tPrimOp;
+    v.primOp.arity = arity;
+    v.primOp.fun = primOp;
+    v.primOp.name = strdup(name2.c_str());
+    staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
+    baseEnv.values[baseEnvDispl++] = v;
+    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
 }
 
 
@@ -50,6 +167,11 @@ LocalNoInlineNoReturn(void throwEvalError(const char * s, const string & s2))
     throw EvalError(format(s) % s2);
 }
 
+LocalNoInlineNoReturn(void throwEvalError(const char * s, const string & s2, const string & s3))
+{
+    throw EvalError(format(s) % s2 % s3);
+}
+
 LocalNoInlineNoReturn(void throwTypeError(const char * s))
 {
     throw TypeError(s);
@@ -60,9 +182,19 @@ LocalNoInlineNoReturn(void throwTypeError(const char * s, const string & s2))
     throw TypeError(format(s) % s2);
 }
 
-LocalNoInline(void addErrorPrefix(Error & e, const char * s))
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const Pos & pos, const string & s2))
+{
+    throw TypeError(format(s) % pos % s2);
+}
+
+LocalNoInlineNoReturn(void throwTypeError(const char * s, const Pos & pos))
+{
+    throw TypeError(format(s) % pos);
+}
+
+LocalNoInlineNoReturn(void throwAssertionError(const char * s, const Pos & pos))
 {
-    e.addPrefix(s);
+    throw AssertionError(format(s) % pos);
 }
 
 LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2))
@@ -70,845 +202,884 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2))
     e.addPrefix(format(s) % s2);
 }
 
-LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2, const string & s3))
+LocalNoInline(void addErrorPrefix(Error & e, const char * s, const Pos & pos))
 {
-    e.addPrefix(format(s) % s2 % s3);
+    e.addPrefix(format(s) % pos);
+}
+
+LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2, const Pos & pos))
+{
+    e.addPrefix(format(s) % s2 % pos);
 }
 
 
-/* Pattern-match `pat' against `arg'.  The result is a set of
-   substitutions (`subs') and a set of recursive substitutions
-   (`subsRecursive').  The latter can refer to the variables bound by
-   both `subs' and `subsRecursive'. */
-static void patternMatch(EvalState & state,
-    Pattern pat, Expr arg, ATermMap & subs, ATermMap & subsRecursive)
+void mkString(Value & v, const char * s)
 {
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    ATermBool ellipsis;
-    
-    if (matchVarPat(pat, name)) 
-        subs.set(name, arg);
+    v.type = tString;
+    v.string.s = strdup(s);
+    v.string.context = 0;
+}
 
-    else if (matchAttrsPat(pat, formals, ellipsis)) {
 
-        arg = evalExpr(state, arg);
+void mkString(Value & v, const string & s, const PathSet & context)
+{
+    mkString(v, s.c_str());
+    if (!context.empty()) {
+        unsigned int n = 0;
+        v.string.context = new const char *[context.size() + 1];
+        foreach (PathSet::const_iterator, i, context) 
+            v.string.context[n++] = strdup(i->c_str());
+        v.string.context[n] = 0;
+    }
+}
 
-        /* Get the actual arguments. */
-        ATermMap attrs;
-        queryAllAttrs(arg, attrs);
-        unsigned int nrAttrs = attrs.size();
 
-        /* For each formal argument, get the actual argument.  If
-           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 name, def;
-            DefaultValue def2;
-            if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
-
-            Expr value = attrs[name];
-
-            if (value == 0) {
-                if (!matchDefaultValue(def2, def)) def = 0;
-                if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing")
-                    % aterm2String(name));
-                subsRecursive.set(name, def);
-            } else {
-                attrsUsed++;
-                attrs.remove(name);
-                subs.set(name, value);
-            }
+void mkPath(Value & v, const char * s)
+{
+    v.type = tPath;
+    v.path = strdup(s);
+}
+
 
+Value * EvalState::lookupVar(Env * env, const VarRef & var)
+{
+    for (unsigned int l = var.level; l; --l, env = env->up) ;
+    
+    if (var.fromWith) {
+        while (1) {
+            Bindings::iterator j = env->values[0].attrs->find(var.name);
+            if (j != env->values[0].attrs->end())
+                return &j->second.value;
+            if (env->prevWith == 0)
+                throwEvalError("undefined variable `%1%'", var.name);
+            for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
         }
+    } else
+        return &env->values[var.displ];
+}
 
-        /* Check that each actual argument is listed as a formal
-           argument (unless the attribute match specifies a `...'). */
-        if (ellipsis == eFalse && attrsUsed != nrAttrs)
-            throw TypeError(format("the function does not expect an argument named `%1%'")
-                % aterm2String(attrs.begin()->key));
-    }
 
-    else if (matchAtPat(pat, pat1, pat2)) {
-        patternMatch(state, pat1, arg, subs, subsRecursive);
-        patternMatch(state, pat2, arg, subs, subsRecursive);
-    }
+Value * EvalState::allocValues(unsigned int count)
+{
+    nrValues += count;
+    return new Value[count]; // !!! check destructor
+}
+
 
-    else abort();
+Env & EvalState::allocEnv(unsigned int size)
+{
+    nrEnvs++;
+    nrValuesInEnvs += size;
+    Env * env = (Env *) malloc(sizeof(Env) + size * sizeof(Value));
+    return *env;
 }
 
 
-/* Substitute an argument set into the body of a function. */
-static Expr substArgs(EvalState & state,
-    Expr body, Pattern pat, Expr arg)
+void EvalState::mkList(Value & v, unsigned int length)
 {
-    ATermMap subs(16), subsRecursive(16);
-    
-    patternMatch(state, pat, arg, subs, subsRecursive);
-
-    /* If we used any default values, make a recursive attribute set
-       out of the (argument-name, value) tuples.  This is so that we
-       can support default values that refer to each other, e.g.  ({x,
-       y ? x + x}: y) {x = "foo";} evaluates to "foofoo". */
-    if (subsRecursive.size() != 0) {
-        ATermList recAttrs = ATempty;
-        foreach (ATermMap::const_iterator, i, subs)
-            recAttrs = ATinsert(recAttrs, makeBind(i->key, i->value, makeNoPos()));
-        foreach (ATermMap::const_iterator, i, subsRecursive)
-            recAttrs = ATinsert(recAttrs, makeBind(i->key, i->value, makeNoPos()));
-        Expr rec = makeRec(recAttrs, ATempty);
-        foreach (ATermMap::const_iterator, i, subsRecursive)
-            subs.set(i->key, makeSelect(rec, i->key));
-    }
+    v.type = tList;
+    v.list.length = length;
+    v.list.elems = new Value *[length];
+    nrListElems += length;
+}
+
 
-    return substitute(Substitution(0, &subs), body);
+void EvalState::mkAttrs(Value & v)
+{
+    v.type = tAttrs;
+    v.attrs = new Bindings;
 }
 
 
-/* Transform a mutually recursive set into a non-recursive set.  Each
-   attribute is transformed into an expression that has all references
-   to attributes substituted with selection expressions on the
-   original set.  E.g., e = `rec {x = f x y; y = x;}' becomes `{x = f
-   (e.x) (e.y); y = e.x;}'. */
-LocalNoInline(ATerm expandRec(EvalState & state, ATerm e, ATermList rbnds, ATermList nrbnds))
+void EvalState::mkThunk_(Value & v, Expr * expr)
 {
-    ATerm name;
-    Expr e2;
-    Pos pos;
-    Expr eOverrides = 0;
+    mkThunk(v, baseEnv, expr);
+}
 
-    /* Create the substitution list. */
-    ATermMap subs(ATgetLength(rbnds) + ATgetLength(nrbnds));
-    for (ATermIterator i(rbnds); i; ++i) {
-        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-        subs.set(name, makeSelect(e, name));
-    }
-    for (ATermIterator i(nrbnds); i; ++i) {
-        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-        if (name == sOverrides) eOverrides = e2;
-        subs.set(name, e2);
-    }
 
-    /* If the rec contains an attribute called `__overrides', then
-       evaluate it, and add the attributes in that set to the rec.
-       This allows overriding of recursive attributes, which is
-       otherwise not possible.  (You can use the // operator to
-       replace an attribute, but other attributes in the rec will
-       still reference the original value, because that value has been
-       substituted into the bodies of the other attributes.  Hence we
-       need __overrides.) */
-    ATermMap overrides;
-    if (eOverrides) {
-        eOverrides = evalExpr(state, eOverrides);
-        queryAllAttrs(eOverrides, overrides, false);
-        foreach (ATermMap::const_iterator, i, overrides)
-            subs.set(i->key, i->value);
+void EvalState::cloneAttrs(Value & src, Value & dst)
+{
+    mkAttrs(dst);
+    foreach (Bindings::iterator, i, *src.attrs) {
+        Attr & a = (*dst.attrs)[i->first];
+        mkCopy(a.value, i->second.value);
+        a.pos = i->second.pos;
     }
+}
 
-    Substitution subs_(0, &subs);
 
-    /* Create the non-recursive set. */
-    ATermMap as(ATgetLength(rbnds) + ATgetLength(nrbnds));
-    for (ATermIterator i(rbnds); i; ++i) {
-        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-        as.set(name, makeAttrRHS(substitute(subs_, e2), pos));
-    }
+void EvalState::evalFile(const Path & path, Value & v)
+{
+    startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path);
 
-    if (eOverrides)
-        foreach (ATermMap::const_iterator, i, overrides)
-            as.set(i->key, makeAttrRHS(i->value, makeNoPos()));
+    Expr * e = parseTrees[path];
 
-    /* Copy the non-recursive bindings.  !!! inefficient */
-    for (ATermIterator i(nrbnds); i; ++i) {
-        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
-        as.set(name, makeAttrRHS(e2, pos));
+    if (!e) {
+        e = parseExprFromFile(*this, path);
+        parseTrees[path] = e;
+    }
+    
+    try {
+        eval(e, v);
+    } catch (Error & e) {
+        addErrorPrefix(e, "while evaluating the file `%1%':\n", path);
+        throw;
     }
-
-    return makeAttrs(as);
 }
 
 
-LocalNoInline(Expr updateAttrs(Expr e1, Expr e2))
+struct RecursionCounter
 {
-    /* Note: e1 and e2 should be in normal form. */
+    EvalState & state;
+    RecursionCounter(EvalState & state) : state(state)
+    {
+        state.recursionDepth++;
+        if (state.recursionDepth > state.maxRecursionDepth)
+            state.maxRecursionDepth = state.recursionDepth;
+    }
+    ~RecursionCounter()
+    {   
+        state.recursionDepth--;
+    }
+};
 
-    ATermMap attrs;
-    queryAllAttrs(e1, attrs, true);
-    queryAllAttrs(e2, attrs, true);
 
-    return makeAttrs(attrs);
-}
+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! */
 
+    /* !!! Disable this eventually. */
+    RecursionCounter r(*this);
+    char x;
+    if (&x < deepestStack) deepestStack = &x;
+    
+    //debug(format("eval: %1%") % *e);
 
-string evalString(EvalState & state, Expr e, PathSet & context)
-{
-    e = evalExpr(state, e);
-    string s;
-    if (!matchStr(e, s, context))
-        throwTypeError("value is %1% while a string was expected", showType(e));
-    return s;
+    checkInterrupt();
+
+    nrEvaluated++;
+
+    e->eval(*this, env, v);
 }
 
 
-string evalStringNoCtx(EvalState & state, Expr e)
+void EvalState::eval(Expr * e, Value & v)
 {
-    PathSet context;
-    string s = evalString(state, e, context);
-    if (!context.empty())
-        throw EvalError(format("the string `%1%' is not allowed to refer to a store path (such as `%2%')")
-            % s % *(context.begin()));
-    return s;
+    eval(baseEnv, e, v);
 }
 
 
-int evalInt(EvalState & state, Expr e)
+bool EvalState::evalBool(Env & env, Expr * e)
 {
-    e = evalExpr(state, e);
-    int i;
-    if (!matchInt(e, i))
-        throwTypeError("value is %1% while an integer was expected", showType(e));
-    return i;
+    Value v;
+    eval(env, e, v);
+    if (v.type != tBool)
+        throwTypeError("value is %1% while a Boolean was expected", showType(v));
+    return v.boolean;
 }
 
 
-bool evalBool(EvalState & state, Expr e)
+void EvalState::evalAttrs(Env & env, Expr * e, Value & v)
 {
-    e = evalExpr(state, e);
-    if (e == eTrue) return true;
-    else if (e == eFalse) return false;
-    else throwTypeError("value is %1% while a boolean was expected", showType(e));
+    eval(env, e, v);
+    if (v.type != tAttrs)
+        throwTypeError("value is %1% while an attribute set was expected", showType(v));
 }
 
 
-ATermList evalList(EvalState & state, Expr e)
+void Expr::eval(EvalState & state, Env & env, Value & v)
 {
-    e = evalExpr(state, e);
-    ATermList list;
-    if (!matchList(e, list))
-        throwTypeError("value is %1% while a list was expected", showType(e));
-    return list;
+    abort();
 }
 
 
-static void flattenList(EvalState & state, Expr e, ATermList & result)
+void ExprInt::eval(EvalState & state, Env & env, Value & v)
 {
-    ATermList es;
-    e = evalExpr(state, e);
-    if (matchList(e, es))
-        for (ATermIterator i(es); i; ++i)
-            flattenList(state, *i, result);
-    else
-        result = ATinsert(result, e);
+    mkInt(v, n);
 }
 
 
-ATermList flattenList(EvalState & state, Expr e)
+void ExprString::eval(EvalState & state, Env & env, Value & v)
 {
-    ATermList result = ATempty;
-    flattenList(state, e, result);
-    return ATreverse(result);
+    mkString(v, s.c_str());
 }
 
 
-string coerceToString(EvalState & state, Expr e, PathSet & context,
-    bool coerceMore, bool copyToStore)
+void ExprPath::eval(EvalState & state, Env & env, Value & v)
 {
-    e = evalExpr(state, e);
+    mkPath(v, s.c_str());
+}
 
-    string s;
 
-    if (matchStr(e, s, context)) return s;
+void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
+{
+    state.mkAttrs(v);
 
-    ATerm s2;
-    if (matchPath(e, s2)) {
-        Path path(canonPath(aterm2String(s2)));
+    if (recursive) {
+        /* Create a new environment that contains the attributes in
+           this `rec'. */
+        Env & env2(state.allocEnv(attrs.size() + inherited.size()));
+        env2.up = &env;
 
-        if (!copyToStore) return path;
+        unsigned int displ = 0;
         
-        if (isDerivation(path))
-            throw EvalError(format("file names are not allowed to end in `%1%'")
-                % drvExtension);
+        /* The recursive attributes are evaluated in the new
+           environment. */
+        foreach (Attrs::iterator, i, attrs) {
+            nix::Attr & a = (*v.attrs)[i->first];
+            mkCopy(a.value, env2.values[displ]);
+            mkThunk(env2.values[displ++], env2, i->second.first);
+            a.pos = &i->second.second;
+        }
 
-        Path dstPath;
-        if (state.srcToStore[path] != "")
-            dstPath = state.srcToStore[path];
-        else {
-            dstPath = readOnlyMode
-                ? computeStorePathForPath(path).first
-                : store->addToStore(path);
-            state.srcToStore[path] = dstPath;
-            printMsg(lvlChatty, format("copied source `%1%' -> `%2%'")
-                % path % dstPath);
+        /* The inherited attributes, on the other hand, are
+           evaluated in the original environment. */
+        foreach (list<Inherited>::iterator, i, inherited) {
+            nix::Attr & a = (*v.attrs)[i->first.name];
+            Value * v2 = state.lookupVar(&env, i->first);
+            mkCopy(a.value, *v2);
+            mkCopy(env2.values[displ++], *v2);
+            a.pos = &i->second;
         }
 
-        context.insert(dstPath);
-        return dstPath;
-    }
-        
-    ATermList es;
-    if (matchAttrs(e, es)) {
-        Expr e2 = queryAttr(e, "outPath");
-        if (!e2) throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
-        return coerceToString(state, e2, context, coerceMore, copyToStore);
     }
 
-    if (coerceMore) {
-
-        /* Note that `false' is represented as an empty string for
-           shell scripting convenience, just like `null'. */
-        if (e == eTrue) return "1";
-        if (e == eFalse) return "";
-        int n;
-        if (matchInt(e, n)) return int2String(n);
-        if (matchNull(e)) return "";
+    else {
+        foreach (Attrs::iterator, i, attrs) {
+            nix::Attr & a = (*v.attrs)[i->first];
+            mkThunk(a.value, env, i->second.first);
+            a.pos = &i->second.second;
+        }
 
-        if (matchList(e, es)) {
-            string result;
-            es = flattenList(state, e);
-            bool first = true;
-            for (ATermIterator i(es); i; ++i) {
-                if (!first) result += " "; else first = false;
-                result += coerceToString(state, *i,
-                    context, coerceMore, copyToStore);
-            }
-            return result;
+        foreach (list<Inherited>::iterator, i, inherited) {
+            nix::Attr & a = (*v.attrs)[i->first.name];
+            mkCopy(a.value, *state.lookupVar(&env, i->first));
+            a.pos = &i->second;
         }
     }
-    
-    throwTypeError("cannot coerce %1% to a string", showType(e));
 }
 
 
-/* Common implementation of `+', ConcatStrings and `~'. */
-static ATerm concatStrings(EvalState & state, ATermVector & args,
-    string separator = "")
+void ExprLet::eval(EvalState & state, Env & env, Value & v)
 {
-    if (args.empty()) return makeStr("", PathSet());
-    
-    PathSet context;
-    std::ostringstream s;
+    /* Create a new environment that contains the attributes in this
+       `let'. */
+    Env & env2(state.allocEnv(attrs->attrs.size() + attrs->inherited.size()));
+    env2.up = &env;
 
-    /* If the first element is a path, then the result will also be a
-       path, we don't copy anything (yet - that's done later, since
-       paths are copied when they are used in a derivation), and none
-       of the strings are allowed to have contexts. */
-    ATerm dummy;
-    args.front() = evalExpr(state, args.front());
-    bool isPath = matchPath(args.front(), dummy);
-
-    for (ATermVector::const_iterator i = args.begin(); i != args.end(); ++i) {
-        if (i != args.begin()) s << separator;
-        s << coerceToString(state, *i, context, false, !isPath);
-    }
+    unsigned int displ = 0;
 
-    if (isPath && !context.empty())
-        throw EvalError(format("a string that refers to a store path cannot be appended to a path, in `%1%'")
-            % s.str());
-    
-    return isPath
-        ? makePath(toATerm(s.str()))
-        : makeStr(s.str(), context);
+    /* The recursive attributes are evaluated in the new
+       environment. */
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        mkThunk(env2.values[displ++], env2, i->second.first);
+
+    /* The inherited attributes, on the other hand, are evaluated in
+       the original environment. */
+    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
+        mkCopy(env2.values[displ++], *state.lookupVar(&env, i->first));
+
+    state.eval(env2, body, v);
 }
 
 
-Path coerceToPath(EvalState & state, Expr e, PathSet & context)
+void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
-    string path = coerceToString(state, e, context, false, false);
-    if (path == "" || path[0] != '/')
-        throw EvalError(format("string `%1%' doesn't represent an absolute path") % path);
-    return path;
+    state.mkList(v, elems.size());
+    Value * vs = state.allocValues(v.list.length);
+    for (unsigned int n = 0; n < v.list.length; ++n) {
+        v.list.elems[n] = &vs[n];
+        mkThunk(vs[n], env, elems[n]);
+    }
 }
 
 
-Expr autoCallFunction(Expr e, const ATermMap & args)
+void ExprVar::eval(EvalState & state, Env & env, Value & v)
 {
-    Pattern pat;
-    ATerm body, pos;
-    ATermList formals;
-    ATermBool ellipsis;
-    
-    /* !!! this should be more general */
-    if (matchFunction(e, pat, body, pos) && matchAttrsPat(pat, formals, ellipsis)) {
-        ATermMap actualArgs(ATgetLength(formals));
-        
-        for (ATermIterator i(formals); i; ++i) {
-            Expr name, def, value; ATerm def2;
-            if (!matchFormal(*i, name, def2)) abort();
-            if ((value = args.get(name)))
-                actualArgs.set(name, makeAttrRHS(value, makeNoPos()));
-            else if (!matchDefaultValue(def2, def))
-                throw TypeError(format("cannot auto-call a function that has an argument without a default value (`%1%')")
-                    % aterm2String(name));
-        }
-        
-        e = makeCall(e, makeAttrs(actualArgs));
+    Value * v2 = state.lookupVar(&env, info);
+    state.forceValue(*v2);
+    v = *v2;
+}
+
+
+void ExprSelect::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v2;
+    state.evalAttrs(env, e, v2);
+    Bindings::iterator i = v2.attrs->find(name);
+    if (i == v2.attrs->end())
+        throwEvalError("attribute `%1%' missing", name);
+    try {            
+        state.forceValue(i->second.value);
+    } catch (Error & e) {
+        addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
+            name, *i->second.pos);
+        throw;
     }
-    
-    return e;
+    v = i->second.value;
 }
 
 
-/* Evaluation of various language constructs.  These have been taken
-   out of evalExpr2 to reduce stack space usage.  (GCC is really dumb
-   about stack space: it just adds up all the local variables and
-   temporaries of every scope into one huge stack frame.  This is
-   really bad for deeply recursive functions.) */
+void ExprOpHasAttr::eval(EvalState & state, Env & env, Value & v)
+{
+    Value vAttrs;
+    state.evalAttrs(env, e, vAttrs);
+    mkBool(v, vAttrs.attrs->find(name) != vAttrs.attrs->end());
+}
 
 
-LocalNoInline(Expr evalVar(EvalState & state, ATerm name))
+void ExprLambda::eval(EvalState & state, Env & env, Value & v)
 {
-    ATerm primOp = state.primOps.get(name);
-    if (!primOp)
-        throw EvalError(format("impossible: undefined variable `%1%'") % aterm2String(name));
-    int arity;
-    ATermBlob fun;
-    if (!matchPrimOpDef(primOp, arity, fun)) abort();
-    if (arity == 0)
-        /* !!! backtrace for primop call */
-        return ((PrimOp) ATgetBlobData(fun)) (state, ATermVector());
-    else
-        return makePrimOp(arity, fun, ATempty);
+    v.type = tLambda;
+    v.lambda.env = &env;
+    v.lambda.fun = this;
 }
 
 
-LocalNoInline(Expr evalCall(EvalState & state, Expr fun, Expr arg))
+void ExprApp::eval(EvalState & state, Env & env, Value & v)
 {
-    Pattern pat;
-    ATerm pos;
-    Expr body;
-        
-    /* Evaluate the left-hand side. */
-    fun = evalExpr(state, fun);
-
-    /* Is it a primop or a function? */
-    int arity;
-    ATermBlob funBlob;
-    ATermList args;
-    if (matchPrimOp(fun, arity, funBlob, args)) {
-        args = ATinsert(args, arg);
-        if (ATgetLength(args) == arity) {
-            /* Put the arguments in a vector in reverse (i.e.,
-               actual) order. */
-            ATermVector args2(arity);
-            for (ATermIterator i(args); i; ++i)
-                args2[--arity] = *i;
-            /* !!! backtrace for primop call */
-            return ((PrimOp) ATgetBlobData(funBlob))
-                (state, args2);
-        } else
-            /* Need more arguments, so propagate the primop. */
-            return makePrimOp(arity, funBlob, args);
-    }
+    Value vFun;
+    state.eval(env, e1, vFun);
+    Value vArg;
+    mkThunk(vArg, env, e2); // !!! should this be on the heap?
+    state.callFunction(vFun, vArg, v);
+}
 
-    else if (matchFunction(fun, pat, body, pos)) {
-        try {
-            return evalExpr(state, substArgs(state, body, pat, arg));
-        } catch (Error & e) {
-            addErrorPrefix(e, "while evaluating the function at %1%:\n",
-                showPos(pos));
-            throw;
+
+void EvalState::callFunction(Value & fun, Value & arg, Value & v)
+{
+    if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
+        unsigned int argsLeft =
+            fun.type == tPrimOp ? fun.primOp.arity : fun.primOpApp.argsLeft;
+        if (argsLeft == 1) {
+            /* We have all the arguments, so call the primop.  First
+               find the primop. */
+            Value * primOp = &fun;
+            while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left;
+            assert(primOp->type == tPrimOp);
+            unsigned int arity = primOp->primOp.arity;
+                
+            /* Put all the arguments in an array. */
+            Value * vArgs[arity];
+            unsigned int n = arity - 1;
+            vArgs[n--] = &arg;
+            for (Value * arg = &fun; arg->type == tPrimOpApp; arg = arg->primOpApp.left)
+                vArgs[n--] = arg->primOpApp.right;
+
+            /* And call the primop. */
+            try {
+                primOp->primOp.fun(*this, vArgs, v);
+            } catch (Error & e) {
+                addErrorPrefix(e, "while evaluating the builtin function `%1%':\n", primOp->primOp.name);
+                throw;
+            }
+        } else {
+            Value * v2 = allocValues(2);
+            v2[0] = fun;
+            v2[1] = arg;
+            v.type = tPrimOpApp;
+            v.primOpApp.left = &v2[0];
+            v.primOpApp.right = &v2[1];
+            v.primOpApp.argsLeft = argsLeft - 1;
         }
+        return;
     }
+    
+    if (fun.type != tLambda)
+        throwTypeError("attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
+            showType(fun));
+
+    unsigned int size =
+        (fun.lambda.fun->arg.empty() ? 0 : 1) +
+        (fun.lambda.fun->matchAttrs ? fun.lambda.fun->formals->formals.size() : 0);
+    Env & env2(allocEnv(size));
+    env2.up = fun.lambda.env;
+
+    unsigned int displ = 0;
+
+    if (!fun.lambda.fun->matchAttrs)
+        env2.values[displ++] = arg;
+
+    else {
+        forceAttrs(arg);
         
-    else throwTypeError(
-        "attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
-        showType(fun));
-}
+        if (!fun.lambda.fun->arg.empty())
+            env2.values[displ++] = arg;
 
+        /* For each formal argument, get the actual argument.  If
+           there is no matching actual argument but the formal
+           argument has a default, use the default. */
+        unsigned int attrsUsed = 0;
+        foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
+            Bindings::iterator j = arg.attrs->find(i->name);
+            if (j == arg.attrs->end()) {
+                if (!i->def) throwTypeError("function at %1% called without required argument `%2%'",
+                    fun.lambda.fun->pos, i->name);   
+                mkThunk(env2.values[displ++], env2, i->def);
+            } else {
+                attrsUsed++;
+                mkCopy(env2.values[displ++], j->second.value);
+            }
+        }
+
+        /* Check that each actual argument is listed as a formal
+           argument (unless the attribute match specifies a `...').
+           TODO: show the names of the expected/unexpected
+           arguments. */
+        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size())
+            throwTypeError("function at %1% called with unexpected argument", fun.lambda.fun->pos);
+    }
 
-LocalNoInline(Expr evalSelect(EvalState & state, Expr e, ATerm name))
-{
-    ATerm pos;
-    string s = aterm2String(name);
-    Expr a = queryAttr(evalExpr(state, e), s, pos);
-    if (!a) throwEvalError("attribute `%1%' missing", s);
     try {
-        return evalExpr(state, a);
+        eval(env2, fun.lambda.fun->body, v);
     } catch (Error & e) {
-        addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
-            s, showPos(pos));
+        addErrorPrefix(e, "while evaluating the function at %1%:\n", fun.lambda.fun->pos);
         throw;
     }
 }
 
 
-LocalNoInline(Expr evalAssert(EvalState & state, Expr cond, Expr body, ATerm pos))
+void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res)
 {
-    if (!evalBool(state, cond))
-        throw AssertionError(format("assertion failed at %1%") % showPos(pos));
-    return evalExpr(state, body);
-}
+    forceValue(fun);
 
+    if (fun.type != tLambda || !fun.lambda.fun->matchAttrs) {
+        res = fun;
+        return;
+    }
 
-LocalNoInline(Expr evalWith(EvalState & state, Expr defs, Expr body, ATerm pos))
-{
-    ATermMap attrs;
-    try {
-        defs = evalExpr(state, defs);
-        queryAllAttrs(defs, attrs);
-    } catch (Error & e) {
-        addErrorPrefix(e, "while evaluating the `with' definitions at %1%:\n",
-            showPos(pos));
-        throw;
+    Value actualArgs;
+    mkAttrs(actualArgs);
+
+    foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
+        Bindings::const_iterator j = args.find(i->name);
+        if (j != args.end())
+            (*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);
     }
-    try {
-        body = substitute(Substitution(0, &attrs), body);
-        checkVarDefs(state.primOps, body);
-        return evalExpr(state, body);
-    } catch (Error & e) {
-        addErrorPrefix(e, "while evaluating the `with' body at %1%:\n",
-            showPos(pos));
-        throw;
-    } 
+
+    callFunction(fun, actualArgs, res);
 }
 
 
-LocalNoInline(Expr evalHasAttr(EvalState & state, Expr e, ATerm name))
+void ExprWith::eval(EvalState & state, Env & env, Value & v)
 {
-    ATermMap attrs;
-    queryAllAttrs(evalExpr(state, e), attrs);
-    return makeBool(attrs.get(name) != 0);
+    Env & env2(state.allocEnv(1));
+    env2.up = &env;
+    env2.prevWith = prevWith;
+
+    state.evalAttrs(env, attrs, env2.values[0]);
+
+    state.eval(env2, body, v);
 }
 
 
-LocalNoInline(Expr evalPlusConcat(EvalState & state, Expr e))
+void ExprIf::eval(EvalState & state, Env & env, Value & v)
 {
-    Expr e1, e2;
-    ATermList es;
+    state.eval(env, state.evalBool(env, cond) ? then : else_, v);
+}
+
     
-    ATermVector args;
+void ExprAssert::eval(EvalState & state, Env & env, Value & v)
+{
+    if (!state.evalBool(env, cond))
+        throwAssertionError("assertion failed at %1%", pos);
+    state.eval(env, body, v);
+}
+
     
-    if (matchOpPlus(e, e1, e2)) {
-
-        /* !!! Awful compatibility hack for `drv + /path'.
-           According to regular concatenation, /path should be
-           copied to the store and its store path should be
-           appended to the string.  However, in Nix <= 0.10, /path
-           was concatenated.  So handle that case separately, but
-           do print out a warning.  This code can go in Nix 0.12,
-           maybe. */
-        e1 = evalExpr(state, e1);
-        e2 = evalExpr(state, e2);
-
-        ATermList as;
-        ATerm p;
-        if (matchAttrs(e1, as) && matchPath(e2, p)) {
-            static bool haveWarned = false;
-            warnOnce(haveWarned, format(
-                    "concatenation of a derivation and a path is deprecated; "
-                    "you should write `drv + \"%1%\"' instead of `drv + %1%'")
-                % aterm2String(p));
-            PathSet context;
-            return makeStr(
-                coerceToString(state, makeSelect(e1, toATerm("outPath")), context)
-                + aterm2String(p), context);
-        }
+void ExprOpNot::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, !state.evalBool(env, e));
+}
 
-        args.push_back(e1);
-        args.push_back(e2);
-    }
 
-    else if (matchConcatStrings(e, es))
-        for (ATermIterator i(es); i; ++i) args.push_back(*i);
-        
-    try {
-        return concatStrings(state, args);
-    } catch (Error & e) {
-        addErrorPrefix(e, "in a string concatenation:\n");
-        throw;
-    }
+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));
 }
 
 
-LocalNoInline(Expr evalSubPath(EvalState & state, Expr e1, Expr e2))
+void ExprOpNEq::eval(EvalState & state, Env & env, Value & v)
 {
-    static bool haveWarned = false;
-    warnOnce(haveWarned, "the subpath operator (~) is deprecated, use string concatenation (+) instead");
-    ATermVector args;
-    args.push_back(e1);
-    args.push_back(e2);
-    return concatStrings(state, args, "/");
+    Value v1; state.eval(env, e1, v1);
+    Value v2; state.eval(env, e2, v2);
+    mkBool(v, !state.eqValues(v1, v2));
 }
 
 
-LocalNoInline(Expr evalOpConcat(EvalState & state, Expr e1, Expr e2))
+void ExprOpAnd::eval(EvalState & state, Env & env, Value & v)
 {
-    try {
-        ATermList l1 = evalList(state, e1);
-        ATermList l2 = evalList(state, e2);
-        return makeList(ATconcat(l1, l2));
-    } catch (Error & e) {
-        addErrorPrefix(e, "in a list concatenation:\n");
-        throw;
-    }
+    mkBool(v, state.evalBool(env, e1) && state.evalBool(env, e2));
 }
 
 
-/* Implementation of the `==' and `!=' operators. */
-LocalNoInline(bool areEqual(EvalState & state, Expr e1, Expr e2))
+void ExprOpOr::eval(EvalState & state, Env & env, Value & v)
 {
-    e1 = evalExpr(state, e1);
-    e2 = evalExpr(state, e2);
-
-    /* We cannot test functions/primops for equality, and we currently
-       don't support testing equality between attribute sets or lists
-       - that would have to be a deep equality test to be sound. */
-    AFun sym1 = ATgetAFun(e1);
-    AFun sym2 = ATgetAFun(e2);
+    mkBool(v, state.evalBool(env, e1) || state.evalBool(env, e2));
+}
 
-    if (sym1 != sym2) return false;
 
-    /* Functions are incomparable. */
-    if (sym1 == symFunction || sym1 == symPrimOp) return false;
+void ExprOpImpl::eval(EvalState & state, Env & env, Value & v)
+{
+    mkBool(v, !state.evalBool(env, e1) || state.evalBool(env, e2));
+}
 
-    if (!state.allowUnsafeEquality && sym1 == symAttrs)
-        throw EvalError("comparison of attribute sets is not implemented");
 
-    /* !!! This allows comparisons of infinite data structures to
-       succeed, such as `let x = [x]; in x == x'.  This is
-       undesirable, since equivalent (?) terms such as `let x = [x]; y
-       = [y]; in x == y' don't terminate. */
-    if (e1 == e2) return true;
+void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
+{
+    Value v2;
+    state.evalAttrs(env, e1, v2);
+        
+    state.cloneAttrs(v2, v);
+        
+    state.evalAttrs(env, e2, v2);
     
-    if (sym1 == symList) {
-        ATermList es1; matchList(e1, es1);
-        ATermList es2; matchList(e2, es2);
-        if (ATgetLength(es1) != ATgetLength(es2)) return false;
-        ATermIterator i(es1), j(es2);
-        while (*i) {
-            if (!areEqual(state, *i, *j)) return false;
-            ++i; ++j;
+    foreach (Bindings::iterator, i, *v2.attrs) {
+        Attr & a = (*v.attrs)[i->first];
+        mkCopy(a.value, i->second.value);
+        a.pos = i->second.pos;
+    }
+}
+
+
+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);
+    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];
+}
+
+
+void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
+{
+    PathSet context;
+    std::ostringstream s;
+        
+    bool first = true, isPath = false;
+    Value vStr;
+
+    foreach (vector<Expr *>::iterator, i, *es) {
+        state.eval(env, *i, vStr);
+
+        /* If the first element is a path, then the result will also
+           be a path, we don't copy anything (yet - that's done later,
+           since paths are copied when they are used in a derivation),
+           and none of the strings are allowed to have contexts. */
+        if (first) {
+            isPath = vStr.type == tPath;
+            first = false;
         }
-        return true;
+            
+        s << state.coerceToString(vStr, context, false, !isPath);
     }
-    
-    return false;
+        
+    if (isPath && !context.empty())
+        throwEvalError("a string that refers to a store path cannot be appended to a path, in `%1%'", s.str());
+
+    if (isPath)
+        mkPath(v, s.str().c_str());
+    else
+        mkString(v, s.str(), context);
 }
 
 
-static char * deepestStack = (char *) -1; /* for measuring stack usage */
+void EvalState::forceValue(Value & v)
+{
+    if (v.type == tThunk) {
+        ValueType saved = v.type;
+        try {
+            v.type = tBlackhole;
+            eval(*v.thunk.env, v.thunk.expr, v);
+        } catch (Error & e) {
+            v.type = saved;
+            throw;
+        }
+    }
+    else if (v.type == tCopy) {
+        forceValue(*v.val);
+        v = *v.val;
+    }
+    else if (v.type == tApp)
+        callFunction(*v.app.left, *v.app.right, v);
+    else if (v.type == tBlackhole)
+        throwEvalError("infinite recursion encountered");
+}
 
 
-Expr evalExpr2(EvalState & state, Expr e)
+void EvalState::strictForceValue(Value & v)
 {
-    /* When changing this function, make sure that you don't cause a
-       (large) increase in stack consumption! */
-    
-    char x;
-    if (&x < deepestStack) deepestStack = &x;
+    forceValue(v);
     
-    Expr e1, e2, e3;
-    ATerm name, pos;
-    AFun sym = ATgetAFun(e);
-
-    /* Normal forms. */
-    if (sym == symStr ||
-        sym == symPath ||
-        sym == symNull ||
-        sym == symInt ||
-        sym == symBool ||
-        sym == symFunction ||
-        sym == symAttrs ||
-        sym == symList ||
-        sym == symPrimOp)
-        return e;
+    if (v.type == tAttrs) {
+        foreach (Bindings::iterator, i, *v.attrs)
+            strictForceValue(i->second.value);
+    }
     
-    /* The `Closed' constructor is just a way to prevent substitutions
-       into expressions not containing free variables. */
-    if (matchClosed(e, e1))
-        return evalExpr(state, e1);
-
-    /* Any encountered variables must be primops (since undefined
-       variables are detected after parsing). */
-    if (matchVar(e, name)) return evalVar(state, name);
-
-    /* Function application. */
-    if (matchCall(e, e1, e2)) return evalCall(state, e1, e2);
-
-    /* Attribute selection. */
-    if (matchSelect(e, e1, name)) return evalSelect(state, e1, name);
-
-    /* Mutually recursive sets. */
-    ATermList rbnds, nrbnds;
-    if (matchRec(e, rbnds, nrbnds))
-        return expandRec(state, e, rbnds, nrbnds);
-
-    /* Conditionals. */
-    if (matchIf(e, e1, e2, e3))
-        return evalExpr(state, evalBool(state, e1) ? e2 : e3);
-
-    /* Assertions. */
-    if (matchAssert(e, e1, e2, pos)) return evalAssert(state, e1, e2, pos);
-
-    /* Withs. */
-    if (matchWith(e, e1, e2, pos)) return evalWith(state, e1, e2, pos);
-
-    /* Generic equality/inequality.  Note that the behaviour on
-       composite data (lists, attribute sets) and functions is
-       undefined, since the subterms of those terms are not evaluated.
-       However, we don't want to make (==) strict, because that would
-       make operations like `big_derivation == null' very slow (unless
-       we were to evaluate them side-by-side). */
-    if (matchOpEq(e, e1, e2)) return makeBool(areEqual(state, e1, e2));
-        
-    if (matchOpNEq(e, e1, e2)) return makeBool(!areEqual(state, e1, e2));
-        
-    /* Negation. */
-    if (matchOpNot(e, e1))
-        return makeBool(!evalBool(state, e1));
+    else if (v.type == tList) {
+        for (unsigned int n = 0; n < v.list.length; ++n)
+            strictForceValue(*v.list.elems[n]);
+    }
+}
 
-    /* Implication. */
-    if (matchOpImpl(e, e1, e2))
-        return makeBool(!evalBool(state, e1) || evalBool(state, e2));
 
-    /* Conjunction (logical AND). */
-    if (matchOpAnd(e, e1, e2))
-        return makeBool(evalBool(state, e1) && evalBool(state, e2));
+int EvalState::forceInt(Value & v)
+{
+    forceValue(v);
+    if (v.type != tInt)
+        throwTypeError("value is %1% while an integer was expected", showType(v));
+    return v.integer;
+}
 
-    /* Disjunction (logical OR). */
-    if (matchOpOr(e, e1, e2))
-        return makeBool(evalBool(state, e1) || evalBool(state, e2));
 
-    /* Attribute set update (//). */
-    if (matchOpUpdate(e, e1, e2))
-        return updateAttrs(evalExpr(state, e1), evalExpr(state, e2));
+bool EvalState::forceBool(Value & v)
+{
+    forceValue(v);
+    if (v.type != tBool)
+        throwTypeError("value is %1% while a Boolean was expected", showType(v));
+    return v.boolean;
+}
+
 
-    /* Attribute existence test (?). */
-    if (matchOpHasAttr(e, e1, name)) return evalHasAttr(state, e1, name);
+void EvalState::forceAttrs(Value & v)
+{
+    forceValue(v);
+    if (v.type != tAttrs)
+        throwTypeError("value is %1% while an attribute set was expected", showType(v));
+}
 
-    /* String or path concatenation. */
-    if (sym == symOpPlus || sym == symConcatStrings)
-        return evalPlusConcat(state, e);
 
-    /* Backwards compatability: subpath operator (~). */
-    if (matchSubPath(e, e1, e2)) return evalSubPath(state, e1, e2);
+void EvalState::forceList(Value & v)
+{
+    forceValue(v);
+    if (v.type != tList)
+        throwTypeError("value is %1% while a list was expected", showType(v));
+}
 
-    /* List concatenation. */
-    if (matchOpConcat(e, e1, e2)) return evalOpConcat(state, e1, e2);
 
-    /* Barf. */
-    abort();
+void EvalState::forceFunction(Value & v)
+{
+    forceValue(v);
+    if (v.type != tLambda && v.type != tPrimOp && v.type != tPrimOpApp)
+        throwTypeError("value is %1% while a function was expected", showType(v));
 }
 
 
-Expr evalExpr(EvalState & state, Expr e)
+string EvalState::forceString(Value & v)
 {
-    checkInterrupt();
+    forceValue(v);
+    if (v.type != tString)
+        throwTypeError("value is %1% while a string was expected", showType(v));
+    return string(v.string.s);
+}
 
-#if 0
-    startNest(nest, lvlVomit,
-        format("evaluating expression: %1%") % e);
-#endif
-
-    state.nrEvaluated++;
-
-    /* Consult the memo table to quickly get the normal form of
-       previously evaluated expressions. */
-    Expr nf = state.normalForms.get(e);
-    if (nf) {
-        if (nf == makeBlackHole())
-            throwEvalError("infinite recursion encountered");
-        state.nrCached++;
-        return nf;
-    }
 
-    /* Otherwise, evaluate and memoize. */
-    state.normalForms.set(e, makeBlackHole());
-    try {
-        nf = evalExpr2(state, e);
-    } catch (Error & err) {
-        state.normalForms.remove(e);
-        throw;
-    }
-    state.normalForms.set(e, nf);
-    return nf;
+string EvalState::forceString(Value & v, PathSet & context)
+{
+    string s = forceString(v);
+    if (v.string.context)
+        for (const char * * p = v.string.context; *p; ++p) 
+            context.insert(*p);
+    return s;
 }
 
 
-Expr evalFile(EvalState & state, const Path & path)
+string EvalState::forceStringNoCtx(Value & v)
 {
-    startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path);
-    Expr e = parseExprFromFile(state, path);
-    try {
-        return evalExpr(state, e);
-    } catch (Error & e) {
-        e.addPrefix(format("while evaluating the file `%1%':\n")
-            % path);
-        throw;
-    }
+    string s = forceString(v);
+    if (v.string.context)
+        throwEvalError("the string `%1%' is not allowed to refer to a store path (such as `%2%')",
+            v.string.s, v.string.context[0]);
+    return s;
 }
 
 
-static Expr strictEvalExpr(EvalState & state, Expr e, ATermMap & nfs);
+bool EvalState::isDerivation(Value & v)
+{
+    if (v.type != tAttrs) return false;
+    Bindings::iterator i = v.attrs->find(sType);
+    return i != v.attrs->end() && forceStringNoCtx(i->second.value) == "derivation";
+}
 
 
-static Expr strictEvalExpr_(EvalState & state, Expr e, ATermMap & nfs)
+string EvalState::coerceToString(Value & v, PathSet & context,
+    bool coerceMore, bool copyToStore)
 {
-    e = evalExpr(state, e);
+    forceValue(v);
 
-    ATermList as;
-    if (matchAttrs(e, as)) {
-        ATermList as2 = ATempty;
-        for (ATermIterator i(as); i; ++i) {
-            ATerm name; Expr e; ATerm pos;
-            if (!matchBind(*i, name, e, pos)) abort(); /* can't happen */
-            as2 = ATinsert(as2, makeBind(name, strictEvalExpr(state, e, nfs), pos));
-        }
-        return makeAttrs(ATreverse(as2));
+    string s;
+
+    if (v.type == tString) {
+        if (v.string.context) 
+            for (const char * * p = v.string.context; *p; ++p) 
+                context.insert(*p);
+        return v.string.s;
     }
-    
-    ATermList es;
-    if (matchList(e, es)) {
-        ATermList es2 = ATempty;
-        for (ATermIterator i(es); i; ++i)
-            es2 = ATinsert(es2, strictEvalExpr(state, *i, nfs));
-        return makeList(ATreverse(es2));
+
+    if (v.type == tPath) {
+        Path path(canonPath(v.path));
+
+        if (!copyToStore) return path;
+        
+        if (nix::isDerivation(path))
+            throwEvalError("file names are not allowed to end in `%1%'", drvExtension);
+
+        Path dstPath;
+        if (srcToStore[path] != "")
+            dstPath = srcToStore[path];
+        else {
+            dstPath = readOnlyMode
+                ? computeStorePathForPath(path).first
+                : store->addToStore(path);
+            srcToStore[path] = dstPath;
+            printMsg(lvlChatty, format("copied source `%1%' -> `%2%'")
+                % path % dstPath);
+        }
+
+        context.insert(dstPath);
+        return dstPath;
     }
-    
-    return e;
-}
 
+    if (v.type == tAttrs) {
+        Bindings::iterator i = v.attrs->find(sOutPath);
+        if (i == v.attrs->end())
+            throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
+        return coerceToString(i->second.value, context, coerceMore, copyToStore);
+    }
 
-static Expr strictEvalExpr(EvalState & state, Expr e, ATermMap & nfs)
-{
-    Expr nf = nfs.get(e);
-    if (nf) return nf;
+    if (coerceMore) {
 
-    nf = strictEvalExpr_(state, e, nfs);
+        /* Note that `false' is represented as an empty string for
+           shell scripting convenience, just like `null'. */
+        if (v.type == tBool && v.boolean) return "1";
+        if (v.type == tBool && !v.boolean) return "";
+        if (v.type == tInt) return int2String(v.integer);
+        if (v.type == tNull) return "";
 
-    nfs.set(e, nf);
+        if (v.type == tList) {
+            string result;
+            for (unsigned int n = 0; n < v.list.length; ++n) {
+                result += coerceToString(*v.list.elems[n],
+                    context, coerceMore, copyToStore);
+                if (n < v.list.length - 1
+                    /* !!! not quite correct */
+                    && (v.list.elems[n]->type != tList || v.list.elems[n]->list.length != 0))
+                    result += " ";
+            }
+            return result;
+        }
+    }
     
-    return nf;
+    throwTypeError("cannot coerce %1% to a string", showType(v));
 }
 
 
-Expr strictEvalExpr(EvalState & state, Expr e)
+Path EvalState::coerceToPath(Value & v, PathSet & context)
 {
-    ATermMap strictNormalForms;
-    return strictEvalExpr(state, e, strictNormalForms);
+    string path = coerceToString(v, context, false, false);
+    if (path == "" || path[0] != '/')
+        throwEvalError("string `%1%' doesn't represent an absolute path", path);
+    return path;
 }
 
 
-/* Yes, this is a really bad idea... */
-extern "C" {
-    unsigned long AT_calcAllocatedSize();
+bool EvalState::eqValues(Value & v1, Value & v2)
+{
+    forceValue(v1);
+    forceValue(v2);
+
+    /* !!! Hack to support some old broken code that relies on pointer
+       equality tests between attribute sets.  (Specifically,
+       builderDefs calls uniqList on a list of attribute sets.)  Will
+       remove this eventually. */
+    if (&v1 == &v2) return true;
+
+    if (v1.type != v2.type) return false;
+
+    switch (v1.type) {
+
+        case tInt:
+            return v1.integer == v2.integer;
+
+        case tBool:
+            return v1.boolean == v2.boolean;
+
+        case tString: {
+            /* Compare both the string and its context. */
+            if (strcmp(v1.string.s, v2.string.s) != 0) return false;
+            const char * * p = v1.string.context, * * q = v2.string.context;
+            if (!p && !q) return true;
+            if (!p || !q) return false;
+            for ( ; *p && *q; ++p, ++q)
+                if (strcmp(*p, *q) != 0) return false;
+            if (*p || *q) return false;
+            return true;
+        }
+
+        case tPath:
+            return strcmp(v1.path, v2.path) == 0;
+
+        case tNull:
+            return true;
+
+        case tList:
+            if (v1.list.length != v2.list.length) return false;
+            for (unsigned int n = 0; n < v1.list.length; ++n)
+                if (!eqValues(*v1.list.elems[n], *v2.list.elems[n])) return false;
+            return true;
+
+        case tAttrs: {
+            if (v1.attrs->size() != v2.attrs->size()) return false;
+            Bindings::iterator i, j;
+            for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j)
+                if (i->first != j->first || !eqValues(i->second.value, j->second.value))
+                    return false;
+            return true;
+        }
+
+        /* Functions are incomparable. */
+        case tLambda:
+        case tPrimOp:
+        case tPrimOpApp:
+            return false;
+
+        default:
+            throwEvalError("cannot compare %1% with %2%", showType(v1), showType(v2));
+    }
 }
 
-void printEvalStats(EvalState & state)
+
+void EvalState::printStats()
 {
     char x;
     bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0";
-    printMsg(showStats ? lvlInfo : lvlDebug,
-        format("evaluated %1% expressions, %2% cache hits, %3%%% efficiency, used %4% ATerm bytes, used %5% bytes of stack space")
-        % state.nrEvaluated % state.nrCached
-        % ((float) state.nrCached / (float) state.nrEvaluated * 100)
-        % AT_calcAllocatedSize()
-        % (&x - deepestStack));
-    if (showStats)
-        printATermMapStats();
+    Verbosity v = showStats ? lvlInfo : lvlDebug;
+    printMsg(v, "evaluation statistics:");
+    printMsg(v, format("  expressions evaluated: %1%") % nrEvaluated);
+    printMsg(v, format("  stack space used: %1% bytes") % (&x - deepestStack));
+    printMsg(v, format("  max eval() nesting depth: %1%") % maxRecursionDepth);
+    printMsg(v, format("  stack space per eval() level: %1% bytes")
+        % ((&x - deepestStack) / (float) maxRecursionDepth));
+    printMsg(v, format("  environments allocated: %1% (%2% bytes)")
+        % nrEnvs % (nrEnvs * sizeof(Env)));
+    printMsg(v, format("  values allocated in environments: %1% (%2% bytes)")
+        % nrValuesInEnvs % (nrValuesInEnvs * sizeof(Value)));
+    printMsg(v, format("  list elements: %1% (%2% bytes)")
+        % nrListElems % (nrListElems * sizeof(Value *)));
+    printMsg(v, format("  misc. values allocated: %1% (%2% bytes)")
+        % nrValues % (nrValues * sizeof(Value)));
+    printMsg(v, format("  symbols in symbol table: %1%") % symbols.size());
 }
 
- 
+
 }
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index fed6d3472..1a9862c29 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -3,17 +3,165 @@
 
 #include <map>
 
-#include "aterm.hh"
 #include "nixexpr.hh"
+#include "symbol-table.hh"
 
 
 namespace nix {
 
 
 class Hash;
-    
+class EvalState;
+struct Env;
+struct Value;
+struct Attr;
+
+typedef std::map<Symbol, Attr> Bindings;
+
+
+typedef enum {
+    tInt = 1,
+    tBool,
+    tString,
+    tPath,
+    tNull,
+    tAttrs,
+    tList,
+    tThunk,
+    tApp,
+    tLambda,
+    tCopy,
+    tBlackhole,
+    tPrimOp,
+    tPrimOpApp,
+} ValueType;
+
+
+typedef void (* PrimOp) (EvalState & state, Value * * args, Value & v);
+
+
+struct Value
+{
+    ValueType type;
+    union 
+    {
+        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; // must be in sorted order
+        } string;
+        
+        const char * path;
+        Bindings * attrs;
+        struct {
+            unsigned int length;
+            Value * * elems;
+        } list;
+        struct {
+            Env * env;
+            Expr * expr;
+        } thunk;
+        struct {
+            Value * left, * right;
+        } app;
+        struct {
+            Env * env;
+            ExprLambda * fun;
+        } lambda;
+        Value * val;
+        struct {
+            PrimOp fun;
+            char * name;
+            unsigned int arity;
+        } primOp;
+        struct {
+            Value * left, * right;
+            unsigned int argsLeft;
+        } primOpApp;
+    };
+};
+
+
+struct Env
+{
+    Env * up;
+    unsigned int prevWith; // nr of levels up to next `with' environment
+    Value values[0];
+};
+
+
+struct Attr
+{
+    Value value;
+    Pos * pos;
+    Attr() : pos(&noPos) { };
+};
+
+
+static inline void mkInt(Value & v, int n)
+{
+    v.type = tInt;
+    v.integer = n;
+}
+
+
+static inline void mkBool(Value & v, bool b)
+{
+    v.type = tBool;
+    v.boolean = b;
+}
+
+
+static inline void mkThunk(Value & v, Env & env, Expr * expr)
+{
+    v.type = tThunk;
+    v.thunk.env = &env;
+    v.thunk.expr = expr;
+}
+
+
+static inline void mkCopy(Value & v, Value & src)
+{
+    v.type = tCopy;
+    v.val = &src;
+}
+
+
+static inline void mkApp(Value & v, Value & left, Value & right)
+{
+    v.type = tApp;
+    v.app.left = &left;
+    v.app.right = &right;
+}
+
+
+void mkString(Value & v, const char * s);
+void mkString(Value & v, const string & s, const PathSet & context = PathSet());
+void mkPath(Value & v, const char * s);
+
 
-typedef std::map<Path, PathSet> DrvRoots;
 typedef std::map<Path, Hash> DrvHashes;
 
 /* Cache for calls to addToStore(); maps source paths to the store
@@ -22,75 +170,153 @@ typedef std::map<Path, Path> SrcToStore;
 
 struct EvalState;
 
-/* Note: using a ATermVector is safe here, since when we call a primop
-   we also have an ATermList on the stack. */
-typedef Expr (* PrimOp) (EvalState &, const ATermVector & args);
+
+std::ostream & operator << (std::ostream & str, Value & v);
 
 
-struct EvalState 
+class EvalState 
 {
-    ATermMap normalForms;
-    ATermMap primOps;
-    DrvRoots drvRoots;
+public:
     DrvHashes drvHashes; /* normalised derivation hashes */
-    SrcToStore srcToStore; 
 
-    unsigned int nrEvaluated;
-    unsigned int nrCached;
+    SymbolTable symbols;
+
+    const Symbol sWith, sOutPath, sDrvPath, sType, sMeta, sName, sSystem;
+
+private:
+    SrcToStore srcToStore; 
 
     bool allowUnsafeEquality;
 
+    std::map<Path, Expr *> parseTrees;
+
+public:
+    
     EvalState();
+    ~EvalState();
+
+    /* Evaluate an expression read from the given file to normal
+       form. */
+    void evalFile(const Path & path, Value & v);
+
+    /* 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);
+
+    /* Evaluation the expression, then verify that it has the expected
+       type. */
+    bool evalBool(Env & env, Expr * e);
+    void evalAttrs(Env & env, Expr * e, Value & v);
+
+    /* 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
+       application, call the function and overwrite `v' with the
+       result.  Otherwise, this is a no-op. */
+    void forceValue(Value & v);
+
+    /* Force a value, then recursively force list elements and
+       attributes. */
+    void strictForceValue(Value & v);
+
+    /* Force `v', and then verify that it has the expected type. */
+    int forceInt(Value & v);
+    bool forceBool(Value & v);
+    void forceAttrs(Value & v);
+    void forceList(Value & v);
+    void forceFunction(Value & v); // either lambda or primop
+    string forceString(Value & v);
+    string forceString(Value & v, PathSet & context);
+    string forceStringNoCtx(Value & v);
+
+    /* Return true iff the value `v' denotes a derivation (i.e. a
+       set with attribute `type = "derivation"'). */
+    bool isDerivation(Value & v);
+
+    /* String coercion.  Converts strings, paths and derivations to a
+       string.  If `coerceMore' is set, also converts nulls, integers,
+       booleans and lists to a string.  If `copyToStore' is set,
+       referenced paths are copied to the Nix store as a side effect.q */
+    string coerceToString(Value & v, PathSet & context,
+        bool coerceMore = false, bool copyToStore = true);
+
+    /* Path coercion.  Converts strings, paths and derivations to a
+       path.  The result is guaranteed to be a canonicalised, absolute
+       path.  Nothing is copied to the store. */
+    Path coerceToPath(Value & v, PathSet & context);
+
+private:
+
+    /* The base environment, containing the builtin functions and
+       values. */
+    Env & baseEnv;
+
+    unsigned int baseEnvDispl;
+
+public:
+    
+    /* The same, but used during parsing to resolve variables. */
+    StaticEnv staticBaseEnv; // !!! should be private
+
+private:
+    
+    void createBaseEnv();
+    
+    void addConstant(const string & name, Value & v);
 
-    void addPrimOps();
     void addPrimOp(const string & name,
         unsigned int arity, PrimOp primOp);
-};
 
+    Value * lookupVar(Env * env, const VarRef & var);
+    
+    friend class ExprVar;
+    friend class ExprAttrs;
+    friend class ExprLet;
 
-/* Evaluate an expression to normal form. */
-Expr evalExpr(EvalState & state, Expr e);
+public:
+    
+    /* Do a deep equality test between two values.  That is, list
+       elements and attributes are compared recursively. */
+    bool eqValues(Value & v1, Value & v2);
 
-/* Evaluate an expression read from the given file to normal form. */
-Expr evalFile(EvalState & state, const Path & path);
+    void callFunction(Value & fun, Value & arg, Value & v);
 
-/* Evaluate an expression, and recursively evaluate list elements and
-   attributes.  If `canonicalise' is true, we remove things like
-   position information and make sure that attribute sets are in
-   sorded order. */
-Expr strictEvalExpr(EvalState & state, Expr e);
+    /* Automatically call a function for which each argument has a
+       default value or has a binding in the `args' map. */
+    void autoCallFunction(const Bindings & args, Value & fun, Value & res);
+    
+    /* Allocation primitives. */
+    Value * allocValues(unsigned int count);
+    Env & allocEnv(unsigned int size);
 
-/* Specific results. */
-string evalString(EvalState & state, Expr e, PathSet & context);
-string evalStringNoCtx(EvalState & state, Expr e);
-int evalInt(EvalState & state, Expr e);
-bool evalBool(EvalState & state, Expr e);
-ATermList evalList(EvalState & state, Expr e);
+    void mkList(Value & v, unsigned int length);
+    void mkAttrs(Value & v);
+    void mkThunk_(Value & v, Expr * expr);
+    
+    void cloneAttrs(Value & src, Value & dst);
 
-/* Flatten nested lists into a single list (or expand a singleton into
-   a list). */
-ATermList flattenList(EvalState & state, Expr e);
+    /* Print statistics. */
+    void printStats();
 
-/* String coercion.  Converts strings, paths and derivations to a
-   string.  If `coerceMore' is set, also converts nulls, integers,
-   booleans and lists to a string. */
-string coerceToString(EvalState & state, Expr e, PathSet & context,
-    bool coerceMore = false, bool copyToStore = true);
+private:
+    
+    unsigned long nrEnvs;
+    unsigned long nrValuesInEnvs;
+    unsigned long nrValues;
+    unsigned long nrListElems;
+    unsigned long nrEvaluated;
+    unsigned int recursionDepth;
+    unsigned int maxRecursionDepth;
+    char * deepestStack; /* for measuring stack usage */
+    
+    friend class RecursionCounter;
+};
 
-/* Path coercion.  Converts strings, paths and derivations to a path.
-   The result is guaranteed to be an canonicalised, absolute path.
-   Nothing is copied to the store. */
-Path coerceToPath(EvalState & state, Expr e, PathSet & context);
 
-/* Automatically call a function for which each argument has a default
-   value or has a binding in the `args' map.  Note: result is a call,
-   not a normal form; it should be evaluated by calling evalExpr(). */
-Expr autoCallFunction(Expr e, const ATermMap & args);
+/* Return a string representing the type of the value `v'. */
+string showType(const Value & v);
 
-/* Print statistics. */
-void printEvalStats(EvalState & state);
 
- 
 }
 
 
diff --git a/src/libexpr/expr-to-xml.cc b/src/libexpr/expr-to-xml.cc
deleted file mode 100644
index 1e59eebfc..000000000
--- a/src/libexpr/expr-to-xml.cc
+++ /dev/null
@@ -1,186 +0,0 @@
-#include "expr-to-xml.hh"
-#include "xml-writer.hh"
-#include "nixexpr-ast.hh"
-#include "aterm.hh"
-#include "util.hh"
-
-#include <cstdlib>
-
-
-namespace nix {
-
-    
-static XMLAttrs singletonAttrs(const string & name, const string & value)
-{
-    XMLAttrs attrs;
-    attrs[name] = value;
-    return attrs;
-}
-
-
-/* set<Expr> is safe because all the expressions are also reachable
-   from the stack, therefore can't be garbage-collected. */
-typedef set<Expr> ExprSet;
-
-
-static void printTermAsXML(Expr e, XMLWriter & doc, PathSet & context,
-    ExprSet & drvsSeen, bool location);
-
-
-static void showAttrs(const ATermMap & attrs, XMLWriter & doc,
-    PathSet & context, ExprSet & drvsSeen, bool location)
-{
-    StringSet names;
-    for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i)
-        names.insert(aterm2String(i->key));
-    for (StringSet::iterator i = names.begin(); i != names.end(); ++i) {
-        ATerm attrRHS = attrs.get(toATerm(*i));
-	ATerm attr;
-	Pos pos;
-	XMLAttrs xmlAttrs;
-
-	xmlAttrs["name"] = *i;
-	if(matchAttrRHS(attrRHS, attr, pos)) {
-	    ATerm path;
-	    int line, column;
-            if (location && matchPos(pos, path, line, column)) {
-		xmlAttrs["path"] = aterm2String(path);
-		xmlAttrs["line"] = (format("%1%") % line).str();
-		xmlAttrs["column"] = (format("%1%") % column).str();
-	    }
-	} else
-	    abort(); // Should not happen.
-
-        XMLOpenElement _(doc, "attr", xmlAttrs);
-        printTermAsXML(attr, doc, context, drvsSeen, location);
-    }
-}
-
-
-static void printPatternAsXML(Pattern pat, XMLWriter & doc)
-{
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    ATermBool ellipsis;
-    if (matchVarPat(pat, name))
-        doc.writeEmptyElement("varpat", singletonAttrs("name", aterm2String(name)));
-    else if (matchAttrsPat(pat, formals, ellipsis)) {
-        XMLOpenElement _(doc, "attrspat");
-        for (ATermIterator i(formals); i; ++i) {
-            Expr name; ATerm dummy;
-            if (!matchFormal(*i, name, dummy)) abort();
-            doc.writeEmptyElement("attr", singletonAttrs("name", aterm2String(name)));
-        }
-        if (ellipsis == eTrue) doc.writeEmptyElement("ellipsis");
-    }
-    else if (matchAtPat(pat, pat1, pat2)) {
-        XMLOpenElement _(doc, "at");
-        printPatternAsXML(pat1, doc);
-        printPatternAsXML(pat2, doc);
-    }
-}
-
-
-static void printTermAsXML(Expr e, XMLWriter & doc, PathSet & context,
-    ExprSet & drvsSeen, bool location)
-{
-    XMLAttrs attrs;
-    string s;
-    ATerm s2;
-    int i;
-    ATermList as, es;
-    ATerm pat, body, pos;
-
-    checkInterrupt();
-
-    if (matchStr(e, s, context)) /* !!! show the context? */
-        doc.writeEmptyElement("string", singletonAttrs("value", s));
-
-    else if (matchPath(e, s2))
-        doc.writeEmptyElement("path", singletonAttrs("value", aterm2String(s2)));
-
-    else if (matchNull(e))
-        doc.writeEmptyElement("null");
-
-    else if (matchInt(e, i))
-        doc.writeEmptyElement("int", singletonAttrs("value", (format("%1%") % i).str()));
-
-    else if (e == eTrue)
-        doc.writeEmptyElement("bool", singletonAttrs("value", "true"));
-
-    else if (e == eFalse)
-        doc.writeEmptyElement("bool", singletonAttrs("value", "false"));
-
-    else if (matchAttrs(e, as)) {
-        ATermMap attrs;
-        queryAllAttrs(e, attrs, true);
-
-        Expr aRHS = attrs.get(toATerm("type"));
-	Expr a = NULL;
-	if (aRHS)
-	    matchAttrRHS(aRHS, a, pos);
-        if (a && matchStr(a, s, context) && s == "derivation") {
-
-            XMLAttrs xmlAttrs;
-            Path outPath, drvPath;
-
-            aRHS = attrs.get(toATerm("drvPath"));
-            matchAttrRHS(aRHS, a, pos);
-            if (matchStr(a, drvPath, context))
-                xmlAttrs["drvPath"] = drvPath;
-
-            aRHS = attrs.get(toATerm("outPath"));
-            matchAttrRHS(aRHS, a, pos);
-            if (matchStr(a, outPath, context))
-                xmlAttrs["outPath"] = outPath;
-
-            XMLOpenElement _(doc, "derivation", xmlAttrs);
-
-            if (drvsSeen.find(e) == drvsSeen.end()) {
-                drvsSeen.insert(e);
-                showAttrs(attrs, doc, context, drvsSeen, location);
-            } else
-                doc.writeEmptyElement("repeated");
-        }
-
-        else {
-            XMLOpenElement _(doc, "attrs");
-            showAttrs(attrs, doc, context, drvsSeen, location);
-        }
-    }
-
-    else if (matchList(e, es)) {
-        XMLOpenElement _(doc, "list");
-        for (ATermIterator i(es); i; ++i)
-            printTermAsXML(*i, doc, context, drvsSeen, location);
-    }
-
-    else if (matchFunction(e, pat, body, pos)) {
-        ATerm path;
-	int line, column;
-	XMLAttrs xmlAttrs;
-	if (location && matchPos(pos, path, line, column)) {
-	    xmlAttrs["path"] = aterm2String(path);
-	    xmlAttrs["line"] = (format("%1%") % line).str();
-	    xmlAttrs["column"] = (format("%1%") % column).str();
-	}
-	XMLOpenElement _(doc, "function", xmlAttrs);
-        printPatternAsXML(pat, doc);
-    }
-
-    else
-        doc.writeEmptyElement("unevaluated");
-}
-
-
-void printTermAsXML(Expr e, std::ostream & out, PathSet & context, bool location)
-{
-    XMLWriter doc(true, out);
-    XMLOpenElement root(doc, "expr");
-    ExprSet drvsSeen;    
-    printTermAsXML(e, doc, context, drvsSeen, location);
-}
-
- 
-}
diff --git a/src/libexpr/expr-to-xml.hh b/src/libexpr/expr-to-xml.hh
deleted file mode 100644
index de9d55f32..000000000
--- a/src/libexpr/expr-to-xml.hh
+++ /dev/null
@@ -1,16 +0,0 @@
-#ifndef __EXPR_TO_XML_H
-#define __EXPR_TO_XML_H
-
-#include <string>
-#include <map>
-
-#include "nixexpr.hh"
-#include "aterm.hh"
-
-namespace nix {
-
-void printTermAsXML(Expr e, std::ostream & out, PathSet & context, bool location = false);
-    
-}
-
-#endif /* !__EXPR_TO_XML_H */
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 1442d7988..82a92416b 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"
 
 
@@ -8,17 +7,10 @@ namespace nix {
 
 string DrvInfo::queryDrvPath(EvalState & state) const
 {
-    if (drvPath == "") {
-        Expr a = attrs->get(toATerm("drvPath"));
-
-        /* Backwards compatibility hack with user environments made by
-           Nix <= 0.10: these contain illegal Path("") expressions. */
-        ATerm t;
-        if (a && matchPath(evalExpr(state, a), t))
-            return aterm2String(t);
-        
+    if (drvPath == "" && attrs) {
+        Bindings::iterator i = attrs->find(state.sDrvPath);
         PathSet context;
-        (string &) drvPath = a ? coerceToPath(state, a, context) : "";
+        (string &) drvPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
     }
     return drvPath;
 }
@@ -26,11 +18,10 @@ string DrvInfo::queryDrvPath(EvalState & state) const
 
 string DrvInfo::queryOutPath(EvalState & state) const
 {
-    if (outPath == "") {
-        Expr a = attrs->get(toATerm("outPath"));
-        if (!a) throw TypeError("output path missing");
+    if (outPath == "" && attrs) {
+        Bindings::iterator i = attrs->find(state.sOutPath);
         PathSet context;
-        (string &) outPath = coerceToPath(state, a, context);
+        (string &) outPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
     }
     return outPath;
 }
@@ -38,35 +29,30 @@ string DrvInfo::queryOutPath(EvalState & state) const
 
 MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
 {
-    MetaInfo meta;
+    if (metaInfoRead) return meta;
     
-    Expr a = attrs->get(toATerm("meta"));
-    if (!a) return meta; /* fine, empty meta information */
+    (bool &) metaInfoRead = true;
+    
+    Bindings::iterator a = attrs->find(state.sMeta);
+    if (a == attrs->end()) return meta; /* fine, empty meta information */
 
-    ATermMap attrs2;
-    queryAllAttrs(evalExpr(state, a), attrs2);
+    state.forceAttrs(a->second.value);
 
-    for (ATermMap::const_iterator i = attrs2.begin(); i != attrs2.end(); ++i) {
-        Expr e = evalExpr(state, i->value);
-        string s;
-        PathSet context;
+    foreach (Bindings::iterator, i, *a->second.value.attrs) {
         MetaValue value;
-        int n;
-        ATermList es;
-        if (matchStr(e, s, context)) {
+        state.forceValue(i->second.value);
+        if (i->second.value.type == tString) {
             value.type = MetaValue::tpString;
-            value.stringValue = s;
-            meta[aterm2String(i->key)] = value;
-        } else if (matchInt(e, n)) {
+            value.stringValue = i->second.value.string.s;
+        } else if (i->second.value.type == tInt) {
             value.type = MetaValue::tpInt;
-            value.intValue = n;
-            meta[aterm2String(i->key)] = value;
-        } else if (matchList(e, es)) {
+            value.intValue = i->second.value.integer;
+        } else if (i->second.value.type == tList) {
             value.type = MetaValue::tpStrings;
-            for (ATermIterator j(es); j; ++j)
-                value.stringValues.push_back(evalStringNoCtx(state, *j));
-            meta[aterm2String(i->key)] = value;
-        }
+            for (unsigned int j = 0; j < i->second.value.list.length; ++j)
+                value.stringValues.push_back(state.forceStringNoCtx(*i->second.value.list.elems[j]));
+        } else continue;
+        ((MetaInfo &) meta)[i->first] = value;
     }
 
     return meta;
@@ -82,73 +68,46 @@ MetaValue DrvInfo::queryMetaInfo(EvalState & state, const string & name) const
 
 void DrvInfo::setMetaInfo(const MetaInfo & meta)
 {
-    ATermMap metaAttrs;
-    foreach (MetaInfo::const_iterator, i, meta) {
-        Expr e;
-        switch (i->second.type) {
-            case MetaValue::tpInt: e = makeInt(i->second.intValue); break;
-            case MetaValue::tpString: e = makeStr(i->second.stringValue); break;
-            case MetaValue::tpStrings: {
-                ATermList es = ATempty;
-                foreach (Strings::const_iterator, j, i->second.stringValues)
-                    es = ATinsert(es, makeStr(*j));
-                e = makeList(ATreverse(es));
-                break;
-            }
-            default: abort();
-        }
-        metaAttrs.set(toATerm(i->first), makeAttrRHS(e, makeNoPos()));
-    }
-    attrs->set(toATerm("meta"), makeAttrs(metaAttrs));
+    metaInfoRead = true;
+    this->meta = meta;
 }
 
 
-/* Cache for already evaluated derivations.  Usually putting ATerms in
-   a STL container is unsafe (they're not scanning for GC roots), but
-   here it doesn't matter; everything in this set is reachable from
-   the stack as well. */
-typedef set<Expr> Exprs;
+/* Cache for already considered attrsets. */
+typedef set<Bindings *> Done;
 
 
-/* Evaluate expression `e'.  If it evaluates to an attribute set of
-   type `derivation', then put information about it in `drvs' (unless
-   it's already in `doneExprs').  The result boolean indicates whether
-   it makes sense for the caller to recursively search for derivations
-   in `e'. */
-static bool getDerivation(EvalState & state, Expr e,
-    const string & attrPath, DrvInfos & drvs, Exprs & doneExprs)
+/* Evaluate value `v'.  If it evaluates to an attribute set of type
+   `derivation', then put information about it in `drvs' (unless it's
+   already in `doneExprs').  The result boolean indicates whether it
+   makes sense for the caller to recursively search for derivations in
+   `v'. */
+static bool getDerivation(EvalState & state, Value & v,
+    const string & attrPath, DrvInfos & drvs, Done & done)
 {
     try {
-        
-        ATermList es;
-        e = evalExpr(state, e);
-        if (!matchAttrs(e, es)) return true;
-
-        boost::shared_ptr<ATermMap> attrs(new ATermMap());
-        queryAllAttrs(e, *attrs, false);
-        
-        Expr a = attrs->get(toATerm("type"));
-        if (!a || evalStringNoCtx(state, a) != "derivation") return true;
+        state.forceValue(v);
+        if (!state.isDerivation(v)) return true;
 
         /* Remove spurious duplicates (e.g., an attribute set like
            `rec { x = derivation {...}; y = x;}'. */
-        if (doneExprs.find(e) != doneExprs.end()) return false;
-        doneExprs.insert(e);
+        if (done.find(v.attrs) != done.end()) return false;
+        done.insert(v.attrs);
 
         DrvInfo drv;
     
-        a = attrs->get(toATerm("name"));
+        Bindings::iterator i = v.attrs->find(state.sName);
         /* !!! We really would like to have a decent back trace here. */
-        if (!a) throw TypeError("derivation name missing");
-        drv.name = evalStringNoCtx(state, a);
+        if (i == v.attrs->end()) throw TypeError("derivation name missing");
+        drv.name = state.forceStringNoCtx(i->second.value);
 
-        a = attrs->get(toATerm("system"));
-        if (!a)
+        i = v.attrs->find(state.sSystem);
+        if (i == v.attrs->end())
             drv.system = "unknown";
         else
-            drv.system = evalStringNoCtx(state, a);
+            drv.system = state.forceStringNoCtx(i->second.value);
 
-        drv.attrs = attrs;
+        drv.attrs = v.attrs;
 
         drv.attrPath = attrPath;
 
@@ -161,11 +120,11 @@ static bool getDerivation(EvalState & state, Expr e,
 }
 
 
-bool getDerivation(EvalState & state, Expr e, DrvInfo & drv)
+bool getDerivation(EvalState & state, Value & v, DrvInfo & drv)
 {
-    Exprs doneExprs;
+    Done done;
     DrvInfos drvs;
-    getDerivation(state, e, "", drvs, doneExprs);
+    getDerivation(state, v, "", drvs, done);
     if (drvs.size() != 1) return false;
     drv = drvs.front();
     return true;
@@ -178,83 +137,73 @@ static string addToPath(const string & s1, const string & s2)
 }
 
 
-static void getDerivations(EvalState & state, Expr e,
-    const string & pathPrefix, const ATermMap & autoArgs,
-    DrvInfos & drvs, Exprs & doneExprs)
+static void getDerivations(EvalState & state, Value & vIn,
+    const string & pathPrefix, const Bindings & autoArgs,
+    DrvInfos & drvs, Done & done)
 {
-    e = evalExpr(state, autoCallFunction(evalExpr(state, e), autoArgs));
-
+    Value v;
+    state.autoCallFunction(autoArgs, vIn, v);
+    
     /* Process the expression. */
-    ATermList es;
     DrvInfo drv;
 
-    if (!getDerivation(state, e, pathPrefix, drvs, doneExprs))
-        return;
+    if (!getDerivation(state, v, pathPrefix, drvs, done)) ;
 
-    if (matchAttrs(e, es)) {
-        ATermMap drvMap(ATgetLength(es));
-        queryAllAttrs(e, drvMap);
+    else if (v.type == tAttrs) {
 
         /* !!! undocumented hackery to support combining channels in
            nix-env.cc. */
-        bool combineChannels = drvMap.get(toATerm("_combineChannels"));
+        bool combineChannels = v.attrs->find(state.symbols.create("_combineChannels")) != v.attrs->end();
 
         /* Consider the attributes in sorted order to get more
            deterministic behaviour in nix-env operations (e.g. when
            there are names clashes between derivations, the derivation
            bound to the attribute with the "lower" name should take
            precedence). */
-        typedef std::map<string, Expr> AttrsSorted;
-        AttrsSorted attrsSorted;
-        foreach (ATermMap::const_iterator, i, drvMap)
-            attrsSorted[aterm2String(i->key)] = i->value;
+        typedef std::map<string, Symbol> SortedSymbols;
+        SortedSymbols attrs;
+        foreach (Bindings::iterator, i, *v.attrs)
+            attrs.insert(std::pair<string, Symbol>(i->first, i->first));
 
-        foreach (AttrsSorted::iterator, i, attrsSorted) {
+        foreach (SortedSymbols::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
             string pathPrefix2 = addToPath(pathPrefix, i->first);
+            Value & v2((*v.attrs)[i->second].value);
             if (combineChannels)
-                getDerivations(state, i->second, pathPrefix2, autoArgs, drvs, doneExprs);
-            else if (getDerivation(state, i->second, pathPrefix2, drvs, doneExprs)) {
+                getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
+            else if (getDerivation(state, v2, pathPrefix2, drvs, done)) {
                 /* If the value of this attribute is itself an
                    attribute set, should we recurse into it?  => Only
                    if it has a `recurseForDerivations = true'
                    attribute. */
-                ATermList es;
-                Expr e = evalExpr(state, i->second), e2;
-                if (matchAttrs(e, es)) {
-                    ATermMap attrs(ATgetLength(es));
-                    queryAllAttrs(e, attrs, false);
-                    if (((e2 = attrs.get(toATerm("recurseForDerivations")))
-                            && evalBool(state, e2)))
-                        getDerivations(state, e, pathPrefix2, autoArgs, drvs, doneExprs);
+                if (v2.type == tAttrs) {
+                    Bindings::iterator j = v2.attrs->find(state.symbols.create("recurseForDerivations"));
+                    if (j != v2.attrs->end() && state.forceBool(j->second.value))
+                        getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
                 }
             }
         }
-        
-        return;
     }
 
-    if (matchList(e, es)) {
-        int n = 0;
-        for (ATermIterator i(es); i; ++i, ++n) {
+    else if (v.type == tList) {
+        for (unsigned int n = 0; n < v.list.length; ++n) {
             startNest(nest, lvlDebug,
                 format("evaluating list element"));
             string pathPrefix2 = addToPath(pathPrefix, (format("%1%") % n).str());
-            if (getDerivation(state, *i, pathPrefix2, drvs, doneExprs))
-                getDerivations(state, *i, pathPrefix2, autoArgs, drvs, doneExprs);
+            if (getDerivation(state, *v.list.elems[n], pathPrefix2, drvs, done))
+                getDerivations(state, *v.list.elems[n], pathPrefix2, autoArgs, drvs, done);
         }
-        return;
     }
 
-    throw TypeError("expression does not evaluate to a derivation (or a set or list of those)");
+    else throw TypeError("expression does not evaluate to a derivation (or a set or list of those)");
 }
 
 
-void getDerivations(EvalState & state, Expr e, const string & pathPrefix,
-    const ATermMap & autoArgs, DrvInfos & drvs)
+void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
+    const Bindings & autoArgs, DrvInfos & drvs)
 {
-    Exprs doneExprs;
-    getDerivations(state, e, pathPrefix, autoArgs, drvs, doneExprs);
+    Done done;
+    getDerivations(state, v, pathPrefix, autoArgs, drvs, done);
 }
 
  
diff --git a/src/libexpr/get-drvs.hh b/src/libexpr/get-drvs.hh
index b56f54711..ca7d98002 100644
--- a/src/libexpr/get-drvs.hh
+++ b/src/libexpr/get-drvs.hh
@@ -29,16 +29,19 @@ struct DrvInfo
 private:
     string drvPath;
     string outPath;
+
+    bool metaInfoRead;
+    MetaInfo meta;
     
 public:
     string name;
     string attrPath; /* path towards the derivation */
     string system;
 
-    /* !!! these should really be hidden, and setMetaInfo() should
-       make a copy since the ATermMap can be shared between multiple
-       DrvInfos. */
-    boost::shared_ptr<ATermMap> attrs;
+    /* !!! make this private */
+    Bindings * attrs;
+
+    DrvInfo() : metaInfoRead(false), attrs(0) { };
 
     string queryDrvPath(EvalState & state) const;
     string queryOutPath(EvalState & state) const;
@@ -62,13 +65,12 @@ public:
 typedef list<DrvInfo> DrvInfos;
 
 
-/* Evaluate expression `e'.  If it evaluates to a derivation, store
-   information about the derivation in `drv' and return true.
-   Otherwise, return false. */
-bool getDerivation(EvalState & state, Expr e, DrvInfo & drv);
+/* If value `v' denotes a derivation, store information about the
+   derivation in `drv' and return true.  Otherwise, return false. */
+bool getDerivation(EvalState & state, Value & v, DrvInfo & drv);
 
-void getDerivations(EvalState & state, Expr e, const string & pathPrefix,
-    const ATermMap & autoArgs, DrvInfos & drvs);
+void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
+    const Bindings & autoArgs, DrvInfos & drvs);
 
  
 }
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
index 81aec99e1..f29f9b684 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"
 
@@ -21,13 +19,16 @@ namespace nix {
     
 static void initLoc(YYLTYPE * loc)
 {
-    loc->first_line = 1;
-    loc->first_column = 1;
+    loc->first_line = loc->last_line = 1;
+    loc->first_column = loc->last_column = 1;
 }
 
     
 static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
 {
+    loc->first_line = loc->last_line;
+    loc->first_column = loc->last_column;
+
     while (len--) {
        switch (*s++) {
        case '\r':
@@ -35,17 +36,17 @@ static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
                s++;
            /* fall through */
        case '\n': 
-           ++loc->first_line;
-           loc->first_column = 1;
+           ++loc->last_line;
+           loc->last_column = 1;
            break;
        default:
-           ++loc->first_column;
+           ++loc->last_column;
        }
     }
 }
 
 
-static Expr unescapeStr(const char * s)
+static Expr * unescapeStr(const char * s)
 {
     string t;
     char c;
@@ -65,7 +66,7 @@ static Expr unescapeStr(const char * s)
         }
         else t += c;
     }
-    return makeStr(toATerm(t), ATempty);
+    return new ExprString(t);
 }
 
  
@@ -105,19 +106,20 @@ 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->t = ATmake("<int>", n);
+              yylval->n = n;
               return INT;
             }
 
 \"          { BEGIN(STRING); return '"'; }
 <STRING>([^\$\"\\]|\$[^\{\"]|\\.)+ {
-/* !!! Not quite right: we want a follow restriction on "$", it
-   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 */ 
+              /* !!! Not quite right: we want a follow restriction on
+                 "$", it 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->e = unescapeStr(yytext);
               return STR;
             }
 <STRING>\$\{  { BEGIN(INITIAL); return DOLLAR_CURLY; }
@@ -126,31 +128,31 @@ inherit     { return INHERIT; }
 
 \'\'(\ *\n)?     { BEGIN(IND_STRING); return IND_STRING_OPEN; }
 <IND_STRING>([^\$\']|\$[^\{\']|\'[^\'\$])+ {
-                   yylval->t = makeIndStr(toATerm(yytext));
+                   yylval->e = new ExprIndStr(yytext);
                    return IND_STR;
                  }
 <IND_STRING>\'\'\$ {
-                   yylval->t = makeIndStr(toATerm("$"));
+                   yylval->e = new ExprIndStr("$");
                    return IND_STR;
                  }
 <IND_STRING>\'\'\' {
-                   yylval->t = makeIndStr(toATerm("''"));
+                   yylval->e = new ExprIndStr("''");
                    return IND_STR;
                  }
 <IND_STRING>\'\'\\. {
-                   yylval->t = unescapeStr(yytext + 2);
+                   yylval->e = 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->e = new ExprIndStr("'");
                    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 00b5f5a13..000000000
--- 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 |
-SubPath | 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 | Pattern | # bool = `...'
-AtPat | Pattern Pattern | Pattern |
-
-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")
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 3675dccea..898fdb609 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -1,407 +1,325 @@
 #include "nixexpr.hh"
 #include "derivations.hh"
 #include "util.hh"
-#include "aterm.hh"
-
-#include "nixexpr-ast.hh"
-#include "nixexpr-ast.cc"
 
 #include <cstdlib>
 
 
 namespace nix {
-    
 
-string showPos(ATerm pos)
+
+/* Displaying abstract syntax trees. */
+
+std::ostream & operator << (std::ostream & str, Expr & e)
 {
-    ATerm path;
-    int line, column;
-    if (matchNoPos(pos)) return "undefined position";
-    if (!matchPos(pos, path, line, column))
-        throw badTerm("position expected", pos);
-    return (format("`%1%:%2%:%3%'") % aterm2String(path) % line % column).str();
+    e.show(str);
+    return str;
 }
-    
 
-ATerm bottomupRewrite(TermFun & f, ATerm e)
+void Expr::show(std::ostream & str)
 {
-    checkInterrupt();
-
-    if (ATgetType(e) == AT_APPL) {
-        AFun fun = ATgetAFun(e);
-        int arity = ATgetArity(fun);
-        ATerm args[arity];
-
-        for (int i = 0; i < arity; ++i)
-            args[i] = bottomupRewrite(f, ATgetArgument(e, i));
-        
-        e = (ATerm) ATmakeApplArray(fun, args);
-    }
-
-    else if (ATgetType(e) == AT_LIST) {
-        ATermList in = (ATermList) e;
-        ATermList out = ATempty;
-
-        for (ATermIterator i(in); i; ++i)
-            out = ATinsert(out, bottomupRewrite(f, *i));
-
-        e = (ATerm) ATreverse(out);
-    }
+    abort();
+}
 
-    return f(e);
+void ExprInt::show(std::ostream & str)
+{
+    str << n;
 }
 
+void ExprString::show(std::ostream & str)
+{
+    str << "\"" << s << "\""; // !!! escaping
+}
 
-void queryAllAttrs(Expr e, ATermMap & attrs, bool withPos)
+void ExprPath::show(std::ostream & str)
 {
-    ATermList bnds;
-    if (!matchAttrs(e, bnds))
-        throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
+    str << s;
+}
 
-    for (ATermIterator i(bnds); i; ++i) {
-        ATerm name;
-        Expr e;
-        ATerm pos;
-        if (!matchBind(*i, name, e, pos)) abort(); /* can't happen */
-        attrs.set(name, withPos ? makeAttrRHS(e, pos) : e);
-    }
+void ExprVar::show(std::ostream & str)
+{
+    str << info.name;
 }
 
+void ExprSelect::show(std::ostream & str)
+{
+    str << "(" << *e << ")." << name;
+}
 
-Expr queryAttr(Expr e, const string & name)
+void ExprOpHasAttr::show(std::ostream & str)
 {
-    ATerm dummy;
-    return queryAttr(e, name, dummy);
+    str << "(" << *e << ") ? " << name;
 }
 
+void ExprAttrs::show(std::ostream & str)
+{
+    if (recursive) str << "rec ";
+    str << "{ ";
+    foreach (list<Inherited>::iterator, i, inherited)
+        str << "inherit " << i->first.name << "; ";
+    foreach (Attrs::iterator, i, attrs)
+        str << i->first << " = " << *i->second.first << "; ";
+    str << "}";
+}
 
-Expr queryAttr(Expr e, const string & name, ATerm & pos)
+void ExprList::show(std::ostream & str)
 {
-    ATermList bnds;
-    if (!matchAttrs(e, bnds))
-        throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
+    str << "[ ";
+    foreach (vector<Expr *>::iterator, i, elems)
+        str << "(" << **i << ") ";
+    str << "]";
+}
 
-    for (ATermIterator i(bnds); i; ++i) {
-        ATerm name2, pos2;
-        Expr e;
-        if (!matchBind(*i, name2, e, pos2))
-            abort(); /* can't happen */
-        if (aterm2String(name2) == name) {
-            pos = pos2;
-            return e;
+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.empty()) str << " @ ";
     }
-
-    return 0;
+    if (!arg.empty()) str << arg;
+    str << ": " << *body << ")";
 }
 
-
-Expr makeAttrs(const ATermMap & attrs)
+void ExprLet::show(std::ostream & str)
 {
-    ATermList bnds = ATempty;
-    for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) {
-        Expr e;
-        ATerm pos;
-        if (!matchAttrRHS(i->value, e, pos))
-            abort(); /* can't happen */
-        bnds = ATinsert(bnds, makeBind(i->key, e, pos));
-    }
-    return makeAttrs(bnds);
+    str << "let ";
+    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
+        str << "inherit " << i->first.name << "; ";
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        str << i->first << " = " << *i->second.first << "; ";
+    str << "in " << *body;
 }
 
-
-static void varsBoundByPattern(ATermMap & map, Pattern pat)
+void ExprWith::show(std::ostream & str)
 {
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    ATermBool ellipsis;
-    /* Use makeRemoved() so that it can be used directly in
-       substitute(). */
-    if (matchVarPat(pat, name))
-        map.set(name, makeRemoved());
-    else if (matchAttrsPat(pat, formals, ellipsis)) { 
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            map.set(name, makeRemoved());
-        }
-    }
-    else if (matchAtPat(pat, pat1, pat2)) {
-        varsBoundByPattern(map, pat1);
-        varsBoundByPattern(map, pat2);
-    }
-    else abort();
+    str << "with " << *attrs << "; " << *body;
 }
 
+void ExprIf::show(std::ostream & str)
+{
+    str << "if " << *cond << " then " << *then << " else " << *else_;
+}
 
-Expr substitute(const Substitution & subs, Expr e)
+void ExprAssert::show(std::ostream & str)
 {
-    checkInterrupt();
+    str << "assert " << *cond << "; " << *body;
+}
 
-    //if (subs.size() == 0) return e;
+void ExprOpNot::show(std::ostream & str)
+{
+    str << "! " << *e;
+}
 
-    ATerm name, pos, e2;
+void ExprConcatStrings::show(std::ostream & str)
+{
+    bool first = true;
+    foreach (vector<Expr *>::iterator, i, *es) {
+        if (first) first = false; else str << " + ";
+        str << **i;
+    }
+}
 
-    /* As an optimisation, don't substitute in subterms known to be
-       closed. */
-    if (matchClosed(e, e2)) return e;
 
-    if (matchVar(e, name)) {
-        Expr sub = subs.lookup(name);
-        if (sub == makeRemoved()) sub = 0;
-        Expr wrapped;
-        /* Add a "closed" wrapper around terms that aren't already
-           closed.  The check is necessary to prevent repeated
-           wrapping, e.g., closed(closed(closed(...))), which kills
-           caching. */
-        return sub ? (matchClosed(sub, wrapped) ? sub : makeClosed(sub)) : e;
-    }
+std::ostream & operator << (std::ostream & str, const Pos & pos)
+{
+    if (!pos.line)
+        str << "undefined position";
+    else
+        str << (format("`%1%:%2%:%3%'") % pos.file % pos.line % pos.column).str();
+    return str;
+}
 
-    /* In case of a function, filter out all variables bound by this
-       function. */
-    Pattern pat;
-    ATerm body;
-    if (matchFunction(e, pat, body, pos)) {
-        ATermMap map(16);
-        varsBoundByPattern(map, pat);
-        Substitution subs2(&subs, &map);
-        return makeFunction(
-            (Pattern) substitute(subs2, (Expr) pat),
-            substitute(subs2, body), pos);
-    }
 
-    /* Idem for a mutually recursive attribute set. */
-    ATermList rbnds, nrbnds;
-    if (matchRec(e, rbnds, nrbnds)) {
-        ATermMap map(ATgetLength(rbnds) + ATgetLength(nrbnds));
-        for (ATermIterator i(rbnds); i; ++i)
-            if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
-            else abort(); /* can't happen */
-        for (ATermIterator i(nrbnds); i; ++i)
-            if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
-            else abort(); /* can't happen */
-        return makeRec(
-            (ATermList) substitute(Substitution(&subs, &map), (ATerm) rbnds),
-            (ATermList) substitute(subs, (ATerm) nrbnds));
-    }
+Pos noPos;
 
-    if (ATgetType(e) == AT_APPL) {
-        AFun fun = ATgetAFun(e);
-        int arity = ATgetArity(fun);
-        ATerm args[arity];
-        bool changed = false;
 
-        for (int i = 0; i < arity; ++i) {
-            ATerm arg = ATgetArgument(e, i);
-            args[i] = substitute(subs, arg);
-            if (args[i] != arg) changed = true;
-        }
-        
-        return changed ? (ATerm) ATmakeApplArray(fun, args) : e;
-    }
+/* Computing levels/displacements for variables. */
 
-    if (ATgetType(e) == AT_LIST) {
-        unsigned int len = ATgetLength((ATermList) e);
-        ATerm es[len];
-        ATermIterator i((ATermList) e);
-        for (unsigned int j = 0; i; ++i, ++j)
-            es[j] = substitute(subs, *i);
-        ATermList out = ATempty;
-        for (unsigned int j = len; j; --j)
-            out = ATinsert(out, es[j - 1]);
-        return (ATerm) out;
-    }
+void Expr::bindVars(const StaticEnv & env)
+{
+    abort();
+}
 
-    return e;
+void ExprInt::bindVars(const StaticEnv & env)
+{
 }
 
+void ExprString::bindVars(const StaticEnv & env)
+{
+}
 
-/* We use memoisation to prevent exponential complexity on heavily
-   shared ATerms (remember, an ATerm is a graph, not a tree!).  Note
-   that using an STL set is fine here wrt to ATerm garbage collection
-   since all the ATerms in the set are already reachable from
-   somewhere else. */
-static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
+void ExprPath::bindVars(const StaticEnv & env)
 {
-    if (done.find(e) != done.end()) return;
-    done.insert(e);
-    
-    ATerm name, pos, value;
-    ATerm with, body;
-    ATermList rbnds, nrbnds;
-    Pattern pat;
-
-    /* Closed terms don't have free variables, so we don't have to
-       check by definition. */
-    if (matchClosed(e, value)) return;
-    
-    else if (matchVar(e, name)) {
-        if (!defs.get(name))
-            throw EvalError(format("undefined variable `%1%'")
-                % aterm2String(name));
-    }
+}
 
-    else if (matchFunction(e, pat, body, pos)) {
-        ATermMap defs2(defs);
-        varsBoundByPattern(defs2, pat);
-        set<Expr> done2;
-        checkVarDefs2(done2, defs2, pat);
-        checkVarDefs2(done2, defs2, body);
-    }
-        
-    else if (matchRec(e, rbnds, nrbnds)) {
-        checkVarDefs2(done, defs, (ATerm) nrbnds);
-        ATermMap defs2(defs);
-        for (ATermIterator i(rbnds); i; ++i) {
-            if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
-            defs2.set(name, (ATerm) ATempty);
-        }
-        for (ATermIterator i(nrbnds); i; ++i) {
-            if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
-            defs2.set(name, (ATerm) ATempty);
+void VarRef::bind(const StaticEnv & env)
+{
+    /* Check whether the variable appears in the environment.  If so,
+       set its level and displacement. */
+    const StaticEnv * curEnv;
+    unsigned int level;
+    int withLevel = -1;
+    for (curEnv = &env, level = 0; curEnv; curEnv = curEnv->up, level++) {
+        if (curEnv->isWith) {
+            if (withLevel == -1) withLevel = level;
+        } else {
+            StaticEnv::Vars::const_iterator i = curEnv->vars.find(name);
+            if (i != curEnv->vars.end()) {
+                fromWith = false;
+                this->level = level;
+                displ = i->second;
+                return;
+            }
         }
-        set<Expr> done2;
-        checkVarDefs2(done2, defs2, (ATerm) rbnds);
     }
 
-    else if (matchWith(e, with, body, pos)) {
-        /* We can't check the body without evaluating the definitions
-           (which is an arbitrary expression), so we don't do that
-           here but only when actually evaluating the `with'. */
-        checkVarDefs2(done, defs, with);
-    }
-    
-    else if (ATgetType(e) == AT_APPL) {
-        int arity = ATgetArity(ATgetAFun(e));
-        for (int i = 0; i < arity; ++i)
-            checkVarDefs2(done, defs, ATgetArgument(e, i));
-    }
+    /* Otherwise, the variable must be obtained from the nearest
+       enclosing `with'.  If there is no `with', then we can issue an
+       "undefined variable" error now. */
+    if (withLevel == -1) throw EvalError(format("undefined variable `%1%'") % name);
 
-    else if (ATgetType(e) == AT_LIST)
-        for (ATermIterator i((ATermList) e); i; ++i)
-            checkVarDefs2(done, defs, *i);
+    fromWith = true;
+    this->level = withLevel;
 }
 
-
-void checkVarDefs(const ATermMap & defs, Expr e)
+void ExprVar::bindVars(const StaticEnv & env)
 {
-    set<Expr> done;
-    checkVarDefs2(done, defs, e);
+    info.bind(env);
 }
 
+void ExprSelect::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+}
 
-struct Canonicalise : TermFun
+void ExprOpHasAttr::bindVars(const StaticEnv & env)
 {
-    ATerm operator () (ATerm e)
-    {
-        /* Remove position info. */
-        ATerm path;
-        int line, column;
-        if (matchPos(e, path, line, column))
-            return makeNoPos();
+    e->bindVars(env);
+}
 
-        /* Sort attribute sets. */
-        ATermList _;
-        if (matchAttrs(e, _)) {
-            ATermMap attrs;
-            queryAllAttrs(e, attrs);
-            StringSet names;
-            for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i)
-                names.insert(aterm2String(i->key));
+void ExprAttrs::bindVars(const StaticEnv & env)
+{
+    if (recursive) {
+        StaticEnv newEnv(false, &env);
+    
+        unsigned int displ = 0;
 
-            ATermList attrs2 = ATempty;
-            for (StringSet::reverse_iterator i = names.rbegin(); i != names.rend(); ++i)
-                attrs2 = ATinsert(attrs2,
-                    makeBind(toATerm(*i), attrs.get(toATerm(*i)), makeNoPos()));
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            newEnv.vars[i->first] = displ++;
 
-            return makeAttrs(attrs2);
+        foreach (list<Inherited>::iterator, i, inherited) {
+            newEnv.vars[i->first.name] = displ++;
+            i->first.bind(env);
         }
-        
-        return e;
+
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            i->second.first->bindVars(newEnv);
     }
-};
 
+    else {
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            i->second.first->bindVars(env);
 
-Expr canonicaliseExpr(Expr e)
-{
-    Canonicalise canonicalise;
-    return bottomupRewrite(canonicalise, e);
+        foreach (list<Inherited>::iterator, i, inherited)
+            i->first.bind(env);
+    }
 }
 
-
-Expr makeBool(bool b)
+void ExprList::bindVars(const StaticEnv & env)
 {
-    return b ? eTrue : eFalse;
+    foreach (vector<Expr *>::iterator, i, elems)
+        (*i)->bindVars(env);
 }
 
-
-bool matchStr(Expr e, string & s, PathSet & context)
+void ExprLambda::bindVars(const StaticEnv & env)
 {
-    ATermList l;
-    ATerm s_;
-
-    if (!matchStr(e, s_, l)) return false;
+    StaticEnv newEnv(false, &env);
+    
+    unsigned int displ = 0;
+    
+    if (!arg.empty()) newEnv.vars[arg] = displ++;
 
-    s = aterm2String(s_);
+    if (matchAttrs) {
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            newEnv.vars[i->name] = displ++;
 
-    for (ATermIterator i(l); i; ++i)
-        context.insert(aterm2String(*i));
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            if (i->def) i->def->bindVars(newEnv);
+    }
 
-    return true;
+    body->bindVars(newEnv);
 }
 
+void ExprLet::bindVars(const StaticEnv & env)
+{
+    StaticEnv newEnv(false, &env);
+    
+    unsigned int displ = 0;
+
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        newEnv.vars[i->first] = displ++;
+
+    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited) {
+        newEnv.vars[i->first.name] = displ++;
+        i->first.bind(env);
+    }
 
-Expr makeStr(const string & s, const PathSet & context)
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        i->second.first->bindVars(newEnv);
+    
+    body->bindVars(newEnv);
+}
+
+void ExprWith::bindVars(const StaticEnv & env)
 {
-    return makeStr(toATerm(s), toATermList(context));
+    /* Does this `with' have an enclosing `with'?  If so, record its
+       level so that `lookupVar' can look up variables in the previous
+       `with' if this one doesn't contain the desired attribute. */
+    const StaticEnv * curEnv;
+    unsigned int level;
+    prevWith = 0;
+    for (curEnv = &env, level = 1; curEnv; curEnv = curEnv->up, level++)
+        if (curEnv->isWith) {
+            prevWith = level;
+            break;
+        }
+    
+    attrs->bindVars(env);    
+    StaticEnv newEnv(true, &env);
+    body->bindVars(newEnv);
 }
 
+void ExprIf::bindVars(const StaticEnv & env)
+{
+    cond->bindVars(env);
+    then->bindVars(env);
+    else_->bindVars(env);
+}
 
-string showType(Expr e)
+void ExprAssert::bindVars(const StaticEnv & env)
 {
-    ATerm t1, t2;
-    ATermList l1;
-    ATermBlob b1;
-    int i1;
-    Pattern p1;
-    if (matchStr(e, t1, l1)) return "a string";
-    if (matchPath(e, t1)) return "a path";
-    if (matchNull(e)) return "null";
-    if (matchInt(e, i1)) return "an integer";
-    if (matchBool(e, t1)) return "a boolean";
-    if (matchFunction(e, p1, t1, t2)) return "a function";
-    if (matchAttrs(e, l1)) return "an attribute set";
-    if (matchList(e, l1)) return "a list";
-    if (matchPrimOp(e, i1, b1, l1)) return "a partially applied built-in function";
-    return "an unknown type";
+    cond->bindVars(env);
+    body->bindVars(env);
 }
 
+void ExprOpNot::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+}
 
-string showValue(Expr e)
+void ExprConcatStrings::bindVars(const StaticEnv & env)
 {
-    PathSet context;
-    string s;
-    ATerm s2;
-    int i;
-    if (matchStr(e, s, context)) {
-        string u;
-        for (string::iterator i = s.begin(); i != s.end(); ++i)
-            if (*i == '\"' || *i == '\\') u += "\\" + *i;
-            else if (*i == '\n') u += "\\n";
-            else if (*i == '\r') u += "\\r";
-            else if (*i == '\t') u += "\\t";
-            else u += *i;
-        return "\"" + u + "\"";
-    }
-    if (matchPath(e, s2)) return aterm2String(s2);
-    if (matchNull(e)) return "null";
-    if (matchInt(e, i)) return (format("%1%") % i).str();
-    if (e == eTrue) return "true";
-    if (e == eFalse) return "false";
-    /* !!! incomplete */
-    return "<unknown>";
+    foreach (vector<Expr *>::iterator, i, *es)
+        (*i)->bindVars(env);
 }
 
- 
+
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index c7cdf46df..1c72441b2 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -3,8 +3,7 @@
 
 #include <map>
 
-#include "aterm-map.hh"
-#include "types.hh"
+#include "symbol-table.hh"
 
 
 namespace nix {
@@ -18,105 +17,254 @@ 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;
+/* Position objects. */
 
+struct Pos
+{
+    string file;
+    unsigned int line, column;
+    Pos() : line(0), column(0) { };
+    Pos(const string & file, unsigned int line, unsigned int column)
+        : file(file), line(line), column(column) { };
+};
+
+extern Pos noPos;
+
+std::ostream & operator << (std::ostream & str, const Pos & pos);
 
-/* 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 Env;
+struct Value;
+struct EvalState;
+struct StaticEnv;
 
-/* A substitution is a linked list of ATermMaps that map names to
-   identifiers.  We use a list of ATermMaps rather than a single to
-   make it easy to grow or shrink a substitution when entering a
-   scope. */
-struct Substitution
+
+/* Abstract syntax of Nix expressions. */
+
+struct Expr
 {
-    ATermMap * map;
-    const Substitution * prev;
+    virtual void show(std::ostream & str);
+    virtual void bindVars(const StaticEnv & env);
+    virtual void eval(EvalState & state, Env & env, Value & v);
+};
 
-    Substitution(const Substitution * prev, ATermMap * map)
-    {
-        this->prev = prev;
-        this->map = map;
-    }
-    
-    Expr lookup(Expr name) const
-    {
-        Expr x;
-        for (const Substitution * s(this); s; s = s->prev)
-            if ((x = s->map->get(name))) return x;
-        return 0;
-    }
+std::ostream & operator << (std::ostream & str, Expr & e);
+
+#define COMMON_METHODS \
+    void show(std::ostream & str); \
+    void eval(EvalState & state, Env & env, Value & v); \
+    void bindVars(const StaticEnv & env);
+
+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
+};
 
-/* Show a position. */
-string showPos(ATerm pos);
+/* Temporary class used during parsing of indented strings. */
+struct ExprIndStr : Expr
+{
+    string s;
+    ExprIndStr(const string & s) : s(s) { };
+};
 
-/* Generic bottomup traversal over ATerms.  The traversal first
-   recursively descends into subterms, and then applies the given term
-   function to the resulting term. */
-struct TermFun
+struct ExprPath : Expr
 {
-    virtual ~TermFun() { }
-    virtual ATerm operator () (ATerm e) = 0;
+    string s;
+    ExprPath(const string & s) : s(s) { };
+    COMMON_METHODS
 };
-ATerm bottomupRewrite(TermFun & f, ATerm e);
 
+struct VarRef
+{
+    Symbol name;
 
-/* Query all attributes in an attribute set expression.  The
-   expression must be in normal form. */
-void queryAllAttrs(Expr e, ATermMap & attrs, bool withPos = false);
+    /* Whether the variable comes from an environment (e.g. a rec, let
+       or function argument) or from a "with". */
+    bool fromWith;
+    
+    /* In the former case, the value is obtained by going `level'
+       levels up from the current environment and getting the
+       `displ'th value in that environment.  In the latter case, the
+       value is obtained by getting the attribute named `name' from
+       the attribute set stored in the environment that is `level'
+       levels up from the current one.*/
+    unsigned int level;
+    unsigned int displ;
+
+    VarRef(const Symbol & name) : name(name) { };
+    void bind(const StaticEnv & env);
+};
 
-/* Query a specific attribute from an attribute set expression.  The
-   expression must be in normal form. */
-Expr queryAttr(Expr e, const string & name);
-Expr queryAttr(Expr e, const string & name, ATerm & pos);
+struct ExprVar : Expr
+{
+    VarRef info;
+    ExprVar(const Symbol & name) : info(name) { };
+    COMMON_METHODS
+};
 
-/* Create an attribute set expression from an Attrs value. */
-Expr makeAttrs(const ATermMap & attrs);
+struct ExprSelect : Expr
+{
+    Expr * e;
+    Symbol name;
+    ExprSelect(Expr * e, const Symbol & name) : e(e), name(name) { };
+    COMMON_METHODS
+};
 
+struct ExprOpHasAttr : Expr
+{
+    Expr * e;
+    Symbol name;
+    ExprOpHasAttr(Expr * e, const Symbol & name) : e(e), name(name) { };
+    COMMON_METHODS
+};
 
-/* Perform a set of substitutions on an expression. */
-Expr substitute(const Substitution & subs, Expr e);
+struct ExprAttrs : Expr
+{
+    bool recursive;
+    typedef std::pair<Expr *, Pos> Attr;
+    typedef std::pair<VarRef, Pos> Inherited;
+    typedef std::map<Symbol, Attr> Attrs;
+    Attrs attrs;
+    list<Inherited> inherited;
+    std::map<Symbol, Pos> attrNames; // used during parsing
+    ExprAttrs() : recursive(false) { };
+    COMMON_METHODS
+};
 
+struct ExprList : Expr
+{
+    std::vector<Expr *> elems;
+    ExprList() { };
+    COMMON_METHODS
+};
 
-/* 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);
+struct Formal
+{
+    Symbol name;
+    Expr * def;
+    Formal(const Symbol & name, Expr * def) : name(name), def(def) { };
+};
 
+struct Formals
+{
+    typedef std::list<Formal> Formals_;
+    Formals_ formals;
+    std::set<Symbol> argNames; // used during parsing
+    bool ellipsis;
+};
+
+struct ExprLambda : Expr
+{
+    Pos pos;
+    Symbol arg;
+    bool matchAttrs;
+    Formals * formals;
+    Expr * body;
+    ExprLambda(const Pos & pos, const Symbol & arg, bool matchAttrs, Formals * formals, Expr * body)
+        : pos(pos), arg(arg), matchAttrs(matchAttrs), formals(formals), body(body)
+    {
+        if (!arg.empty() && formals && formals->argNames.find(arg) != formals->argNames.end())
+            throw ParseError(format("duplicate formal function argument `%1%' at %2%")
+                % arg % pos);
+    };
+    COMMON_METHODS
+};
+
+struct ExprLet : Expr
+{
+    ExprAttrs * attrs;
+    Expr * body;
+    ExprLet(ExprAttrs * attrs, Expr * body) : attrs(attrs), body(body) { };
+    COMMON_METHODS
+};
 
-/* Canonicalise a Nix expression by sorting attributes and removing
-   location information. */
-Expr canonicaliseExpr(Expr e);
+struct ExprWith : Expr
+{
+    Pos pos;
+    Expr * attrs, * body;
+    unsigned int prevWith;
+    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
+};
 
-/* Create an expression representing a boolean. */
-Expr makeBool(bool b);
+struct ExprAssert : Expr
+{
+    Pos pos;
+    Expr * cond, * body;
+    ExprAssert(const Pos & pos, Expr * cond, Expr * body) : pos(pos), cond(cond), body(body) { };
+    COMMON_METHODS
+};
 
+struct ExprOpNot : Expr
+{
+    Expr * e;
+    ExprOpNot(Expr * e) : e(e) { };
+    COMMON_METHODS
+};
 
-/* Manipulation of Str() nodes.  Note: matchStr() does not clear
-   context!  */
-bool matchStr(Expr e, string & s, PathSet & context);
+#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 bindVars(const StaticEnv & env) \
+        { \
+            e1->bindVars(env); e2->bindVars(env); \
+        } \
+        void eval(EvalState & state, Env & env, Value & v); \
+    };
+
+MakeBinOp(App, "")
+MakeBinOp(OpEq, "==")
+MakeBinOp(OpNEq, "!=")
+MakeBinOp(OpAnd, "&&")
+MakeBinOp(OpOr, "||")
+MakeBinOp(OpImpl, "->")
+MakeBinOp(OpUpdate, "//")
+MakeBinOp(OpConcatLists, "++")
+
+struct ExprConcatStrings : Expr
+{
+    vector<Expr *> * es;
+    ExprConcatStrings(vector<Expr *> * es) : es(es) { };
+    COMMON_METHODS
+};
 
-Expr makeStr(const string & s, const PathSet & context = PathSet());
 
+/* Static environments are used to map variable names onto (level,
+   displacement) pairs used to obtain the value of the variable at
+   runtime. */
+struct StaticEnv
+{
+    bool isWith;
+    const StaticEnv * up;
+    typedef std::map<Symbol, unsigned int> Vars;
+    Vars vars;
+    StaticEnv(bool isWith, const StaticEnv * up) : isWith(isWith), up(up) { };
+};
 
-/* Showing types, values. */
-string showType(Expr e);
 
-string showValue(Expr e);
 
- 
 }
 
 
diff --git a/src/libexpr/parser.hh b/src/libexpr/parser.hh
index 334822b5e..c8c8ad809 100644
--- a/src/libexpr/parser.hh
+++ b/src/libexpr/parser.hh
@@ -8,12 +8,11 @@ namespace nix {
 
 
 /* Parse a Nix expression from the specified file.  If `path' refers
-   to a directory, the "/default.nix" is appended. */
-Expr parseExprFromFile(EvalState & state, Path path);
+   to a directory, then "/default.nix" is appended. */
+Expr * parseExprFromFile(EvalState & state, Path path);
 
 /* Parse a Nix expression from the specified string. */
-Expr parseExprFromString(EvalState & state, const string & s,
-    const Path & basePath);
+Expr * parseExprFromString(EvalState & state, const string & s, const Path & basePath);
 
 
 }
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 8706ce025..7236bab19 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -20,16 +20,14 @@
 #include <stdlib.h>
 #include <string.h>
 
-#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,145 +37,85 @@ namespace nix {
     
 struct ParseData 
 {
-    Expr result;
+    SymbolTable & symbols;
+    Expr * result;
     Path basePath;
     Path path;
     string error;
+    Symbol sLetBody;
+    ParseData(SymbolTable & symbols)
+        : symbols(symbols)
+        , sLetBody(symbols.create("<let-body>"))
+    { };
 };
- 
 
-static string showAttrPath(ATermList attrPath)
+
+static string showAttrPath(const vector<Symbol> & attrPath)
 {
     string s;
-    for (ATermIterator i(attrPath); i; ++i) {
+    foreach (vector<Symbol>::const_iterator, i, attrPath) {
         if (!s.empty()) s += '.';
-        s += aterm2String(*i);
+        s += *i;
     }
     return s;
 }
- 
-
-struct Tree
-{
-    Expr leaf; ATerm pos; bool recursive;
-    typedef std::map<ATerm, Tree> Children;
-    Children children;
-    Tree() { leaf = 0; recursive = true; }
-};
 
 
-static ATermList buildAttrs(const Tree & t, ATermList & nonrec)
+static void dupAttr(const vector<Symbol> & attrPath, const Pos & pos, const Pos & prevPos)
 {
-    ATermList res = ATempty;
-    for (Tree::Children::const_reverse_iterator i = t.children.rbegin();
-         i != t.children.rend(); ++i)
-        if (!i->second.recursive)
-            nonrec = ATinsert(nonrec, makeBind(i->first, i->second.leaf, i->second.pos));
-        else
-            res = ATinsert(res, i->second.leaf
-                ? makeBind(i->first, i->second.leaf, i->second.pos)
-                : makeBind(i->first, makeAttrs(buildAttrs(i->second, nonrec)), makeNoPos()));
-    return res;
+    throw ParseError(format("attribute `%1%' at %2% already defined at %3%")
+        % showAttrPath(attrPath) % pos % prevPos);
 }
  
 
-static Expr fixAttrs(bool recursive, ATermList as)
+static void dupAttr(Symbol attr, const Pos & pos, const Pos & prevPos)
 {
-    Tree attrs;
-
-    /* This ATermMap is needed to ensure that the `leaf' fields in the
-       Tree nodes are not garbage collected. */
-    ATermMap gcRoots;
-
-    for (ATermIterator i(as); i; ++i) {
-        ATermList names, attrPath; Expr src, e; ATerm name, pos;
-
-        if (matchInherit(*i, src, names, pos)) {
-            bool fromScope = matchScope(src);
-            for (ATermIterator j(names); j; ++j) {
-                if (attrs.children.find(*j) != attrs.children.end()) 
-                    throw ParseError(format("duplicate definition of attribute `%1%' at %2%")
-                        % showAttrPath(ATmakeList1(*j)) % showPos(pos));
-                Tree & t(attrs.children[*j]);
-                Expr leaf = fromScope ? makeVar(*j) : makeSelect(src, *j);
-                gcRoots.set(leaf, leaf);
-                t.leaf = leaf;
-                t.pos = pos;
-                if (recursive && fromScope) t.recursive = false;
-            }
-        }
-
-        else if (matchBindAttrPath(*i, attrPath, e, pos)) {
-
-            Tree * t(&attrs);
-            
-            for (ATermIterator j(attrPath); j; ) {
-                name = *j; ++j;
-                if (t->leaf) throw ParseError(format("attribute set containing `%1%' at %2% already defined at %3%")
-                    % showAttrPath(attrPath) % showPos(pos) % showPos (t->pos));
-                t = &(t->children[name]);
-            }
-
-            if (t->leaf)
-                throw ParseError(format("duplicate definition of attribute `%1%' at %2% and %3%")
-                    % showAttrPath(attrPath) % showPos(pos) % showPos (t->pos));
-            if (!t->children.empty())
-                throw ParseError(format("duplicate definition of attribute `%1%' at %2%")
-                    % showAttrPath(attrPath) % showPos(pos));
-
-            t->leaf = e; t->pos = pos;
-        }
-
-        else abort(); /* can't happen */
-    }
-
-    ATermList nonrec = ATempty;
-    ATermList rec = buildAttrs(attrs, nonrec);
-        
-    return recursive ? makeRec(rec, nonrec) : makeAttrs(rec);
+    vector<Symbol> attrPath; attrPath.push_back(attr);
+    throw ParseError(format("attribute `%1%' at %2% already defined at %3%")
+        % showAttrPath(attrPath) % pos % prevPos);
 }
+ 
 
-
-static void checkPatternVars(ATerm pos, ATermMap & map, Pattern pat)
+static void addAttr(ExprAttrs * attrs, const vector<Symbol> & attrPath,
+    Expr * e, const Pos & pos)
 {
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    ATermBool ellipsis;
-    if (matchVarPat(pat, name)) {
-        if (map.get(name))
-            throw ParseError(format("duplicate formal function argument `%1%' at %2%")
-                % aterm2String(name) % showPos(pos));
-        map.set(name, name);
-    }
-    else if (matchAttrsPat(pat, formals, ellipsis)) { 
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            if (map.get(name))
-                throw ParseError(format("duplicate formal function argument `%1%' at %2%")
-                    % aterm2String(name) % showPos(pos));
-            map.set(name, name);
+    unsigned int n = 0;
+    foreach (vector<Symbol>::const_iterator, i, attrPath) {
+        n++;
+        ExprAttrs::Attrs::iterator j = attrs->attrs.find(*i);
+        if (j != attrs->attrs.end()) {
+            ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.first);
+            if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.second);
+            attrs = attrs2;
+        } else {
+            if (attrs->attrNames.find(*i) != attrs->attrNames.end())
+                dupAttr(attrPath, pos, attrs->attrNames[*i]);
+            attrs->attrNames[*i] = pos;
+            if (n == attrPath.size())
+                attrs->attrs[*i] = ExprAttrs::Attr(e, pos);
+            else {
+                ExprAttrs * nested = new ExprAttrs;
+                attrs->attrs[*i] = ExprAttrs::Attr(nested, pos);
+                attrs = nested;
+            }
         }
     }
-    else if (matchAtPat(pat, pat1, pat2)) {
-        checkPatternVars(pos, map, pat1);
-        checkPatternVars(pos, map, pat2);
-    }
-    else abort();
 }
 
 
-static void checkPatternVars(ATerm pos, Pattern pat)
+static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
 {
-    ATermMap map;
-    checkPatternVars(pos, map, pat);
+    if (formals->argNames.find(formal.name) != formals->argNames.end())
+        throw ParseError(format("duplicate formal function argument `%1%' at %2%")
+            % formal.name % pos);
+    formals->formals.push_front(formal);
+    formals->argNames.insert(formal.name);
 }
 
 
-static Expr stripIndentation(ATermList es)
+static Expr * stripIndentation(vector<Expr *> & es)
 {
-    if (es == ATempty) return makeStr("");
+    if (es.empty()) return new ExprString("");
     
     /* Figure out the minimum indentation.  Note that by design
        whitespace-only final lines are not taken into account.  (So
@@ -185,9 +123,9 @@ static Expr stripIndentation(ATermList es)
     bool atStartOfLine = true; /* = seen only whitespace in the current line */
     unsigned int minIndent = 1000000;
     unsigned int curIndent = 0;
-    ATerm e;
-    for (ATermIterator i(es); i; ++i) {
-        if (!matchIndStr(*i, e)) {
+    foreach (vector<Expr *>::iterator, i, es) {
+        ExprIndStr * e = dynamic_cast<ExprIndStr *>(*i);
+        if (!e) {
             /* Anti-quotations end the current start-of-line whitespace. */
             if (atStartOfLine) {
                 atStartOfLine = false;
@@ -195,12 +133,11 @@ static Expr stripIndentation(ATermList es)
             }
             continue;
         }
-        string s = aterm2String(e);
-        for (unsigned int j = 0; j < s.size(); ++j) {
+        for (unsigned int j = 0; j < e->s.size(); ++j) {
             if (atStartOfLine) {
-                if (s[j] == ' ')
+                if (e->s[j] == ' ')
                     curIndent++;
-                else if (s[j] == '\n') {
+                else if (e->s[j] == '\n') {
                     /* Empty line, doesn't influence minimum
                        indentation. */
                     curIndent = 0;
@@ -208,7 +145,7 @@ static Expr stripIndentation(ATermList es)
                     atStartOfLine = false;
                     if (curIndent < minIndent) minIndent = curIndent;
                 }
-            } else if (s[j] == '\n') {
+            } else if (e->s[j] == '\n') {
                 atStartOfLine = true;
                 curIndent = 0;
             }
@@ -216,37 +153,37 @@ static Expr stripIndentation(ATermList es)
     }
 
     /* Strip spaces from each line. */
-    ATermList es2 = ATempty;
+    vector<Expr *> * es2 = new vector<Expr *>;
     atStartOfLine = true;
     unsigned int curDropped = 0;
-    unsigned int n = ATgetLength(es);
-    for (ATermIterator i(es); i; ++i, --n) {
-        if (!matchIndStr(*i, e)) {
+    unsigned int n = es.size();
+    for (vector<Expr *>::iterator i = es.begin(); i != es.end(); ++i, --n) {
+        ExprIndStr * e = dynamic_cast<ExprIndStr *>(*i);
+        if (!e) {
             atStartOfLine = false;
             curDropped = 0;
-            es2 = ATinsert(es2, *i);
+            es2->push_back(*i);
             continue;
         }
         
-        string s = aterm2String(e);
         string s2;
-        for (unsigned int j = 0; j < s.size(); ++j) {
+        for (unsigned int j = 0; j < e->s.size(); ++j) {
             if (atStartOfLine) {
-                if (s[j] == ' ') {
+                if (e->s[j] == ' ') {
                     if (curDropped++ >= minIndent)
-                        s2 += s[j];
+                        s2 += e->s[j];
                 }
-                else if (s[j] == '\n') {
+                else if (e->s[j] == '\n') {
                     curDropped = 0;
-                    s2 += s[j];
+                    s2 += e->s[j];
                 } else {
                     atStartOfLine = false;
                     curDropped = 0;
-                    s2 += s[j];
+                    s2 += e->s[j];
                 }
             } else {
-                s2 += s[j];
-                if (s[j] == '\n') atStartOfLine = true;
+                s2 += e->s[j];
+                if (e->s[j] == '\n') atStartOfLine = true;
             }
         }
 
@@ -257,11 +194,11 @@ static Expr stripIndentation(ATermList es)
             if (p != string::npos && s2.find_first_not_of(' ', p + 1) == string::npos)
                 s2 = string(s2, 0, p + 1);
         }
-            
-        es2 = ATinsert(es2, makeStr(s2));
+
+        es2->push_back(new ExprString(s2));
     }
 
-    return makeConcatStrings(ATreverse(es2));
+    return new ExprConcatStrings(es2);
 }
 
 
@@ -269,13 +206,12 @@ void backToString(yyscan_t scanner);
 void backToIndString(yyscan_t scanner);
 
 
-static Pos makeCurPos(YYLTYPE * loc, ParseData * data)
+static Pos makeCurPos(const YYLTYPE & loc, ParseData * data)
 {
-    return makePos(toATerm(data->path),
-        loc->first_line, loc->first_column);
+    return Pos(data->path, loc.first_line, loc.first_column);
 }
 
-#define CUR_POS makeCurPos(yylocp, data)
+#define CUR_POS makeCurPos(*yylocp, data)
 
 
 }
@@ -283,29 +219,10 @@ static Pos makeCurPos(YYLTYPE * loc, ParseData * data)
 
 void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * error)
 {
-    data->error = (format("%1%, at `%2%':%3%:%4%")
-        % error % data->path % loc->first_line % loc->first_column).str();
-}
-
-
-/* Make sure that the parse stack is scanned by the ATerm garbage
-   collector. */
-static void * mallocAndProtect(size_t size)
-{
-    void * p = malloc(size);
-    if (p) ATprotectMemory(p, size);
-    return p;
-}
-
-static void freeAndUnprotect(void * p)
-{
-    ATunprotectMemory(p);
-    free(p);
+    data->error = (format("%1%, at %2%")
+        % error % makeCurPos(*loc, data)).str();
 }
 
-#define YYMALLOC mallocAndProtect
-#define YYFREE freeAndUnprotect
-
 
 #endif
 
@@ -313,20 +230,32 @@ 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; // !!! -> Symbol
+  char * path;
+  char * uri;
+  std::vector<nix::Symbol> * ids;
+  std::vector<nix::Expr *> * string_parts;
 }
 
-%type <t> start expr expr_function expr_if expr_op
-%type <t> expr_app expr_select expr_simple bind inheritsrc formal
-%type <t> pattern pattern2
-%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 <formals> formals
-%token <t> ID INT STR IND_STR PATH URI
+%type <formal> formal
+%type <ids> ids attrpath
+%type <string_parts> string_parts ind_string_parts
+%token <id> ID ATTRPATH
+%token <e> 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,163 +279,172 @@ start: expr { data->result = $1; };
 expr: expr_function;
 
 expr_function
-  : pattern ':' expr_function
-    { checkPatternVars(CUR_POS, $1); $$ = makeFunction($1, $3, CUR_POS); }
+  : ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), false, 0, $3); }
+  | '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create(""), true, $2, $5); }
+  | '{' formals '}' '@' ID ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($5), true, $2, $7); }
+  | ID '@' '{' formals '}' ':' expr_function
+    { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), true, $4, $7); }
   | ASSERT expr ';' expr_function
-    { $$ = makeAssert($2, $4, CUR_POS); }
+    { $$ = new ExprAssert(CUR_POS, $2, $4); }
   | 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>")); }
+    { $$ = new ExprLet($2, $4); }
   | 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 '~' expr_op { $$ = makeSubPath($1, $3); }
-  | expr_op '?' ID { $$ = makeOpHasAttr($1, $3); }
-  | expr_op '+' expr_op { $$ = makeOpPlus($1, $3); }
-  | expr_op CONCAT expr_op { $$ = makeOpConcat($1, $3); }
+  : '!' expr_op %prec NEG { $$ = new ExprOpNot($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 { $$ = new ExprOpHasAttr($1, data->symbols.create($3)); }
+  | expr_op '+' expr_op
+    { vector<Expr *> * l = new vector<Expr *>;
+      l->push_back($1);
+      l->push_back($3);
+      $$ = new ExprConcatStrings(l);
+    }
+  | 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, data->symbols.create($3)); }
   | expr_simple { $$ = $1; }
   ;
 
 expr_simple
-  : ID { $$ = makeVar($1); }
-  | INT { $$ = makeInt(ATgetInt((ATermInt) $1)); }
+  : ID { $$ = new ExprVar(data->symbols.create($1)); }
+  | INT { $$ = new ExprInt($1); }
   | '"' string_parts '"' {
       /* 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));
+      if ($2->empty()) $$ = new ExprString("");
+      else if ($2->size() == 1) $$ = $2->front();
+      else $$ = new ExprConcatStrings($2);
   }
   | IND_STRING_OPEN ind_string_parts IND_STRING_CLOSE {
-      $$ = stripIndentation(ATreverse($2));
+      $$ = stripIndentation(*$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'. */
   | LET '{' binds '}'
-    { $$ = makeSelect(fixAttrs(true, $3), toATerm("body")); }
+    { $3->recursive = true; $$ = new ExprSelect($3, data->symbols.create("body")); }
   | REC '{' binds '}'
-    { $$ = fixAttrs(true, $3); }
+    { $3->recursive = true; $$ = $3; }
   | '{' binds '}'
-    { $$ = fixAttrs(false, $2); }
-  | '[' expr_list ']' { $$ = makeList(ATreverse($2)); }
+    { $$ = $2; }
+  | '[' expr_list ']' { $$ = $2; }
   ;
 
 string_parts
-  : string_parts STR { $$ = ATinsert($1, $2); }
-  | string_parts DOLLAR_CURLY expr '}' { backToString(scanner); $$ = ATinsert($1, $3); }
-  | { $$ = ATempty; }
+  : string_parts STR { $$ = $1; $1->push_back($2); }
+  | string_parts DOLLAR_CURLY expr '}' { backToString(scanner); $$ = $1; $1->push_back($3); }
+  | { $$ = new vector<Expr *>; }
   ;
 
 ind_string_parts
-  : ind_string_parts IND_STR { $$ = ATinsert($1, $2); }
-  | ind_string_parts DOLLAR_CURLY expr '}' { backToIndString(scanner); $$ = ATinsert($1, $3); }
-  | { $$ = ATempty; }
-  ;
-
-pattern
-  : pattern2 '@' pattern { $$ = makeAtPat($1, $3); }
-  | pattern2
-  ;
-
-pattern2
-  : ID { $$ = makeVarPat($1); }
-  | '{' formals '}' { $$ = makeAttrsPat($2.formals, $2.ellipsis ? eTrue : eFalse); }
+  : ind_string_parts IND_STR { $$ = $1; $1->push_back($2); }
+  | ind_string_parts DOLLAR_CURLY expr '}' { backToIndString(scanner); $$ = $1; $1->push_back($3); }
+  | { $$ = new vector<Expr *>; }
   ;
 
 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 attrpath '=' expr ';' { $$ = $1; addAttr($$, *$2, $4, makeCurPos(@2, data)); }
+  | binds INHERIT ids ';'
+    { $$ = $1;
+      foreach (vector<Symbol>::iterator, i, *$3) {
+          if ($$->attrNames.find(*i) != $$->attrNames.end())
+              dupAttr(*i, makeCurPos(@3, data), $$->attrNames[*i]);
+          Pos pos = makeCurPos(@3, data);
+          $$->inherited.push_back(ExprAttrs::Inherited(*i, pos));
+          $$->attrNames[*i] = pos;
+      }
+    }
+  | binds INHERIT '(' expr ')' ids ';'
+    { $$ = $1;
+      /* !!! Should ensure sharing of the expression in $4. */
+      foreach (vector<Symbol>::iterator, i, *$6) {
+          if ($$->attrNames.find(*i) != $$->attrNames.end())
+              dupAttr(*i, makeCurPos(@6, data), $$->attrNames[*i]);
+          $$->attrs[*i] = ExprAttrs::Attr(new ExprSelect($4, *i), makeCurPos(@6, data));
+          $$->attrNames[*i] = makeCurPos(@6, data);
+      }}
+
+  | { $$ = new ExprAttrs; }
   ;
 
-inheritsrc
-  : '(' expr ')' { $$ = $2; }
-  | { $$ = makeScope(); }
+ids
+  : ids ID { $$ = $1; $1->push_back(data->symbols.create($2)); /* !!! dangerous */ }
+  | { $$ = new vector<Symbol>; }
   ;
 
-ids: ids ID { $$ = ATinsert($1, $2); } | { $$ = ATempty; };
-
 attrpath
-  : attrpath '.' ID { $$ = ATinsert($1, $3); }
-  | ID { $$ = ATmakeList1($1); }
+  : attrpath '.' ID { $$ = $1; $1->push_back(data->symbols.create($3)); }
+  | ID { $$ = new vector<Symbol>; $$->push_back(data->symbols.create($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; addFormal(CUR_POS, $$, *$1); }
   | formal
-    { $$.formals = ATinsert(ATempty, $1); $$.ellipsis = false; }
+    { $$ = new Formals; addFormal(CUR_POS, $$, *$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(data->symbols.create($1), 0); }
+  | ID '?' expr { $$ = new Formal(data->symbols.create($1), $3); }
   ;
   
 %%
 
 
-#include "eval.hh"  
-
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <unistd.h>
 
+#include <eval.hh>
+
 
 namespace nix {
       
 
-static Expr parse(EvalState & state,
-    const char * text, const Path & path,
-    const Path & basePath)
+static Expr * parse(EvalState & state, const char * text,
+    const Path & path, const Path & basePath)
 {
     yyscan_t scanner;
-    ParseData data;
+    ParseData data(state.symbols);
     data.basePath = basePath;
     data.path = path;
 
@@ -518,7 +456,7 @@ static Expr parse(EvalState & state,
     if (res) throw ParseError(data.error);
 
     try {
-        checkVarDefs(state.primOps, data.result);
+        data.result->bindVars(state.staticBaseEnv);
     } catch (Error & e) {
         throw ParseError(format("%1%, in `%2%'") % e.msg() % path);
     }
@@ -527,16 +465,10 @@ static Expr parse(EvalState & state,
 }
 
 
-Expr parseExprFromFile(EvalState & state, Path path)
+Expr * parseExprFromFile(EvalState & state, Path path)
 {
     assert(path[0] == '/');
 
-#if 0
-    /* Perhaps this is already an imploded parse tree? */
-    Expr e = ATreadFromNamedFile(path.c_str());
-    if (e) return e;
-#endif
-
     /* If `path' is a symlink, follow it.  This is so that relative
        path references work. */
     struct stat st;
@@ -558,7 +490,7 @@ Expr parseExprFromFile(EvalState & state, Path path)
 }
 
 
-Expr parseExprFromString(EvalState & state,
+Expr * parseExprFromString(EvalState & state,
     const string & s, const Path & basePath)
 {
     return parse(state, s.c_str(), "(string)", basePath);
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 7dddc91a8..9d36fb6a0 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -4,8 +4,7 @@
 #include "store-api.hh"
 #include "util.hh"
 #include "archive.hh"
-#include "expr-to-xml.hh"
-#include "nixexpr-ast.hh"
+#include "value-to-xml.hh"
 #include "parser.hh"
 #include "names.hh"
 
@@ -14,87 +13,23 @@
 #include <unistd.h>
 
 #include <algorithm>
+#include <cstring>
 
 
 namespace nix {
 
 
 /*************************************************************
- * Constants
- *************************************************************/
-
-
-static Expr prim_builtins(EvalState & state, const ATermVector & args)
-{
-    /* Return an attribute set containing all primops.  This allows
-       Nix expressions to test for new primops and take appropriate
-       action if they're not available.  For instance, rather than
-       calling a primop `foo' directly, they could say `if builtins ?
-       foo then builtins.foo ... else ...'. */
-
-    ATermMap builtins(state.primOps.size());
-
-    for (ATermMap::const_iterator i = state.primOps.begin();
-         i != state.primOps.end(); ++i)
-    {
-        string name = aterm2String(i->key);
-        if (string(name, 0, 2) == "__")
-            name = string(name, 2);
-        /* !!! should use makePrimOp here, I guess. */
-        builtins.set(toATerm(name), makeAttrRHS(makeVar(i->key), makeNoPos()));
-    }
-
-    return makeAttrs(builtins);
-}
-
-
-/* Boolean constructors. */
-static Expr prim_true(EvalState & state, const ATermVector & args)
-{
-    return eTrue;
-}
-
-
-static Expr prim_false(EvalState & state, const ATermVector & args)
-{
-    return eFalse;
-}
-
-
-/* Return the null value. */
-static Expr prim_null(EvalState & state, const ATermVector & args)
-{
-    return makeNull();
-}
-
-
-/* Return a string constant representing the current platform.  Note!
-   that differs between platforms, so Nix expressions using
-   `__currentSystem' can evaluate to different values on different
-   platforms. */
-static Expr prim_currentSystem(EvalState & state, const ATermVector & args)
-{
-    return makeStr(thisSystem);
-}
-
-
-static Expr prim_currentTime(EvalState & state, const ATermVector & args)
-{
-    return ATmake("Int(<int>)", time(0));
-}
-
-
-/*************************************************************
  * Miscellaneous
  *************************************************************/
 
 
 /* Load and evaluate an expression from path specified by the
    argument. */ 
-static Expr prim_import(EvalState & state, const ATermVector & args)
+static void prim_import(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Path path = coerceToPath(state, args[0], context);
+    Path path = state.coerceToPath(*args[0], context);
 
     for (PathSet::iterator i = context.begin(); i != context.end(); ++i) {
         assert(isStorePath(*i));
@@ -105,164 +40,203 @@ static Expr prim_import(EvalState & state, const ATermVector & args)
             store->buildDerivations(singleton<PathSet>(*i));
     }
 
-    return evalFile(state, path);
+    state.evalFile(path, v);
 }
 
 
 /* Determine whether the argument is the null value. */
-static Expr prim_isNull(EvalState & state, const ATermVector & args)
+static void prim_isNull(EvalState & state, Value * * args, Value & v)
 {
-    return makeBool(matchNull(evalExpr(state, args[0])));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tNull);
 }
 
 
 /* Determine whether the argument is a function. */
-static Expr prim_isFunction(EvalState & state, const ATermVector & args)
+static void prim_isFunction(EvalState & state, Value * * args, Value & v)
 {
-    Expr e = evalExpr(state, args[0]);
-    Pattern pat;
-    ATerm body, pos;
-    return makeBool(matchFunction(e, pat, body, pos));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tLambda);
 }
 
+
 /* Determine whether the argument is an Int. */
-static Expr prim_isInt(EvalState & state, const ATermVector & args)
+static void prim_isInt(EvalState & state, Value * * args, Value & v)
 {
-    int i;
-    return makeBool(matchInt(evalExpr(state, args[0]), i));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tInt);
 }
 
+
 /* Determine whether the argument is an String. */
-static Expr prim_isString(EvalState & state, const ATermVector & args)
+static void prim_isString(EvalState & state, Value * * args, Value & v)
 {
-    string s;
-    PathSet l;
-    return makeBool(matchStr(evalExpr(state, args[0]), s, l));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tString);
 }
 
+
 /* Determine whether the argument is an Bool. */
-static Expr prim_isBool(EvalState & state, const ATermVector & args)
+static void prim_isBool(EvalState & state, Value * * args, Value & v)
 {
-    ATermBool b;
-    return makeBool(matchBool(evalExpr(state, args[0]), b));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tBool);
 }
 
-static Expr prim_genericClosure(EvalState & state, const ATermVector & args)
+
+struct CompareValues
+{
+    bool operator () (const Value & v1, const Value & v2) const
+    {
+        if (v1.type != v2.type)
+            throw EvalError("cannot compare values of different types");
+        switch (v1.type) {
+            case tInt:
+                return v1.integer < v2.integer;
+            case tString:
+                return strcmp(v1.string.s, v2.string.s) < 0;
+            case tPath:
+                return strcmp(v1.path, v2.path) < 0;
+            default:
+                throw EvalError(format("cannot compare %1% with %2%") % showType(v1) % showType(v2));
+        }
+    }
+};
+
+
+static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
 {
     startNest(nest, lvlDebug, "finding dependencies");
 
-    Expr attrs = evalExpr(state, args[0]);
+    state.forceAttrs(*args[0]);
 
     /* Get the start set. */
-    Expr startSet = queryAttr(attrs, "startSet");
-    if (!startSet) throw EvalError("attribute `startSet' required");
-    ATermList startSet2 = evalList(state, startSet);
+    Bindings::iterator startSet =
+        args[0]->attrs->find(state.symbols.create("startSet"));
+    if (startSet == args[0]->attrs->end())
+        throw EvalError("attribute `startSet' required");
+    state.forceList(startSet->second.value);
 
-    set<Expr> workSet; // !!! gc roots
-    for (ATermIterator i(startSet2); i; ++i) workSet.insert(*i);
+    list<Value *> workSet;
+    for (unsigned int n = 0; n < startSet->second.value.list.length; ++n)
+        workSet.push_back(startSet->second.value.list.elems[n]);
 
     /* Get the operator. */
-    Expr op = queryAttr(attrs, "operator");
-    if (!op) throw EvalError("attribute `operator' required");
-    
+    Bindings::iterator op =
+        args[0]->attrs->find(state.symbols.create("operator"));
+    if (op == args[0]->attrs->end())
+        throw EvalError("attribute `operator' required");
+    state.forceValue(op->second.value);
+
     /* Construct the closure by applying the operator to element of
        `workSet', adding the result to `workSet', continuing until
        no new elements are found. */
-    ATermList res = ATempty;
-    set<Expr> doneKeys; // !!! gc roots
+    list<Value> res;
+    set<Value, CompareValues> doneKeys;
     while (!workSet.empty()) {
-	Expr e = *(workSet.begin());
-	workSet.erase(e);
+	Value * e = *(workSet.begin());
+	workSet.pop_front();
 
-        e = strictEvalExpr(state, e);
+        state.forceAttrs(*e);
 
-        Expr key = queryAttr(e, "key");
-        if (!key) throw EvalError("attribute `key' required");
+        Bindings::iterator key =
+            e->attrs->find(state.symbols.create("key"));
+        if (key == e->attrs->end())
+            throw EvalError("attribute `key' required");
+        state.forceValue(key->second.value);
 
-	if (doneKeys.find(key) != doneKeys.end()) continue;
-        doneKeys.insert(key);
-        res = ATinsert(res, e);
+        if (doneKeys.find(key->second.value) != doneKeys.end()) continue;
+        doneKeys.insert(key->second.value);
+        res.push_back(*e);
         
         /* Call the `operator' function with `e' as argument. */
-        ATermList res = evalList(state, makeCall(op, e));
-
-        /* Try to find the dependencies relative to the `path'. */
-        for (ATermIterator i(res); i; ++i)
-            workSet.insert(evalExpr(state, *i));
+        Value call;
+        mkApp(call, op->second.value, *e);
+        state.forceList(call);
+
+        /* Add the values returned by the operator to the work set. */
+        for (unsigned int n = 0; n < call.list.length; ++n) {
+            state.forceValue(*call.list.elems[n]);
+            workSet.push_back(call.list.elems[n]);
+        }
     }
 
-    return makeList(res);
+    /* Create the result list. */
+    state.mkList(v, res.size());
+    Value * vs = state.allocValues(res.size());
+
+    unsigned int n = 0;
+    foreach (list<Value>::iterator, i, res) {
+        v.list.elems[n] = &vs[n];
+        vs[n++] = *i;
+    }
 }
 
 
-static Expr prim_abort(EvalState & state, const ATermVector & args)
+static void prim_abort(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
     throw Abort(format("evaluation aborted with the following error message: `%1%'") %
-        evalString(state, args[0], context));
+        state.coerceToString(*args[0], context));
 }
 
 
-static Expr prim_throw(EvalState & state, const ATermVector & args)
+static void prim_throw(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
     throw ThrownError(format("user-thrown exception: %1%") %
-        evalString(state, args[0], context));
+        state.coerceToString(*args[0], context));
 }
 
 
-static Expr prim_addErrorContext(EvalState & state, const ATermVector & args)
+static void prim_addErrorContext(EvalState & state, Value * * args, Value & v)
 {
-    PathSet context;
     try {
-        return evalExpr(state, args[1]);
+        state.forceValue(*args[1]);
+        v = *args[1];
     } catch (Error & e) {
-        e.addPrefix(format("%1%\n") %
-            evalString(state, args[0], context));
+        PathSet context;
+        e.addPrefix(format("%1%\n") % state.coerceToString(*args[0], context));
         throw;
     }
 }
 
+
 /* Try evaluating the argument. Success => {success=true; value=something;}, 
  * else => {success=false; value=false;} */
-static Expr prim_tryEval(EvalState & state, const ATermVector & args)
+static void prim_tryEval(EvalState & state, Value * * args, Value & v)
 {
-    ATermMap res = ATermMap();
+    state.mkAttrs(v);
     try {
-        Expr val = evalExpr(state, args[0]);
-        res.set(toATerm("value"), makeAttrRHS(val, makeNoPos()));
-        res.set(toATerm("success"), makeAttrRHS(eTrue, makeNoPos()));
+        state.forceValue(*args[0]);
+        (*v.attrs)[state.symbols.create("value")].value = *args[0];
+        mkBool((*v.attrs)[state.symbols.create("success")].value, true);
     } catch (AssertionError & e) {
-        printMsg(lvlDebug, format("tryEval caught an error: %1%: %2%") % e.prefix() % e.msg());
-        res.set(toATerm("value"), makeAttrRHS(eFalse, makeNoPos()));
-        res.set(toATerm("success"), makeAttrRHS(eFalse, makeNoPos()));
+        mkBool((*v.attrs)[state.symbols.create("value")].value, false);
+        mkBool((*v.attrs)[state.symbols.create("success")].value, false);
     }
-    return makeAttrs(res);
 }
 
 
 /* Return an environment variable.  Use with care. */
-static Expr prim_getEnv(EvalState & state, const ATermVector & args)
+static void prim_getEnv(EvalState & state, Value * * args, Value & v)
 {
-    string name = evalStringNoCtx(state, args[0]);
-    return makeStr(getEnv(name));
+    string name = state.forceStringNoCtx(*args[0]);
+    mkString(v, getEnv(name));
 }
 
 
-/* Evaluate the first expression, and print its abstract syntax tree
-   on standard error.  Then return the second expression.  Useful for
-   debugging.
- */
-static Expr prim_trace(EvalState & state, const ATermVector & args)
+/* Evaluate the first expression and print it on standard error.  Then
+   return the second expression.  Useful for debugging. */
+static void prim_trace(EvalState & state, Value * * args, Value & v)
 {
-    Expr e = evalExpr(state, args[0]);
-    string s;
-    PathSet context;
-    if (matchStr(e, s, context))
-        printMsg(lvlError, format("trace: %1%") % s);
+    state.forceValue(*args[0]);
+    if (args[0]->type == tString)
+        printMsg(lvlError, format("trace: %1%") % args[0]->string.s);
     else
-        printMsg(lvlError, format("trace: %1%") % e);
-    return evalExpr(state, args[1]);
+        printMsg(lvlError, format("trace: %1%") % *args[0]);
+    state.forceValue(*args[1]);
+    v = *args[1];
 }
 
 
@@ -324,7 +298,7 @@ static Hash hashDerivationModulo(EvalState & state, Derivation drv)
     }
     drv.inputDrvs = inputs2;
     
-    return hashTerm(unparseDerivation(drv));
+    return hashString(htSHA256, unparseDerivation(drv));
 }
 
 
@@ -335,28 +309,25 @@ static Hash hashDerivationModulo(EvalState & state, Derivation drv)
    derivation; `drvPath' containing the path of the Nix expression;
    and `type' set to `derivation' to indicate that this is a
    derivation. */
-static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
+static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
 {
     startNest(nest, lvlVomit, "evaluating derivation");
 
-    ATermMap attrs;
-    queryAllAttrs(evalExpr(state, args[0]), attrs, true);
+    state.forceAttrs(*args[0]);
 
-    /* Figure out the name already (for stack backtraces). */
-    ATerm posDrvName;
-    Expr eDrvName = attrs.get(toATerm("name"));
-    if (!eDrvName)
+    /* Figure out the name first (for stack backtraces). */
+    Bindings::iterator attr = args[0]->attrs->find(state.sName);
+    if (attr == args[0]->attrs->end())
         throw EvalError("required attribute `name' missing");
-    if (!matchAttrRHS(eDrvName, eDrvName, posDrvName)) abort();
     string drvName;
+    Pos & posDrvName(*attr->second.pos);
     try {        
-        drvName = evalStringNoCtx(state, eDrvName);
+        drvName = state.forceStringNoCtx(attr->second.value);
     } catch (Error & e) {
-        e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n")
-            % showPos(posDrvName));
+        e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n") % posDrvName);
         throw;
     }
-
+    
     /* Build the derivation expression by processing the attributes. */
     Derivation drv;
     
@@ -365,12 +336,8 @@ static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
     string outputHash, outputHashAlgo;
     bool outputHashRecursive = false;
 
-    for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) {
-        string key = aterm2String(i->key);
-        ATerm value;
-        Expr pos;
-        ATerm rhs = i->value;
-        if (!matchAttrRHS(rhs, value, pos)) abort();
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        string key = i->first;
         startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
 
         try {
@@ -378,15 +345,9 @@ static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
             if (key == "args") {
-                ATermList es;
-                value = evalExpr(state, value);
-                if (!matchList(value, es)) {
-                    static bool haveWarned = false;
-                    warnOnce(haveWarned, "the `args' attribute should evaluate to a list");
-                    es = flattenList(state, value);
-                }
-                for (ATermIterator i(es); i; ++i) {
-                    string s = coerceToString(state, *i, context, true);
+                state.forceList(i->second.value);
+                for (unsigned int n = 0; n < i->second.value.list.length; ++n) {
+                    string s = state.coerceToString(*i->second.value.list.elems[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -394,11 +355,11 @@ static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
             /* All other attributes are passed to the builder through
                the environment. */
             else {
-                string s = coerceToString(state, value, context, true);
+                string s = state.coerceToString(i->second.value, context, true);
                 drv.env[key] = s;
                 if (key == "builder") drv.builder = s;
-                else if (key == "system") drv.platform = s;
-                else if (key == "name") drvName = s;
+                else if (i->first == state.sSystem) drv.platform = s;
+                else if (i->first == state.sName) drvName = s;
                 else if (key == "outputHash") outputHash = s;
                 else if (key == "outputHashAlgo") outputHashAlgo = s;
                 else if (key == "outputHashMode") {
@@ -410,12 +371,11 @@ static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
 
         } catch (Error & e) {
             e.addPrefix(format("while evaluating the derivation attribute `%1%' at %2%:\n")
-                % key % showPos(pos));
+                % key % *i->second.pos);
             e.addPrefix(format("while instantiating the derivation named `%1%' at %2%:\n")
-                % drvName % showPos(posDrvName));
+                % drvName % posDrvName);
             throw;
         }
-
     }
     
     /* Everything in the context of the strings in the derivation
@@ -523,33 +483,9 @@ static Expr prim_derivationStrict(EvalState & state, const ATermVector & args)
     state.drvHashes[drvPath] = hashDerivationModulo(state, drv);
 
     /* !!! assumes a single output */
-    ATermMap outAttrs(2);
-    outAttrs.set(toATerm("outPath"),
-        makeAttrRHS(makeStr(outPath, singleton<PathSet>(drvPath)), makeNoPos()));
-    outAttrs.set(toATerm("drvPath"),
-        makeAttrRHS(makeStr(drvPath, singleton<PathSet>("=" + drvPath)), makeNoPos()));
-
-    return makeAttrs(outAttrs);
-}
-
-
-static Expr prim_derivationLazy(EvalState & state, const ATermVector & args)
-{
-    Expr eAttrs = evalExpr(state, args[0]);
-    ATermMap attrs;    
-    queryAllAttrs(eAttrs, attrs, true);
-
-    attrs.set(toATerm("type"),
-        makeAttrRHS(makeStr("derivation"), makeNoPos()));
-
-    Expr drvStrict = makeCall(makeVar(toATerm("derivation!")), eAttrs);
-
-    attrs.set(toATerm("outPath"),
-        makeAttrRHS(makeSelect(drvStrict, toATerm("outPath")), makeNoPos()));
-    attrs.set(toATerm("drvPath"),
-        makeAttrRHS(makeSelect(drvStrict, toATerm("drvPath")), makeNoPos()));
-    
-    return makeAttrs(attrs);
+    state.mkAttrs(v);
+    mkString((*v.attrs)[state.sOutPath].value, outPath, singleton<PathSet>(drvPath));
+    mkString((*v.attrs)[state.sDrvPath].value, drvPath, singleton<PathSet>("=" + drvPath));
 }
 
 
@@ -559,11 +495,11 @@ static Expr prim_derivationLazy(EvalState & state, const ATermVector & args)
 
 
 /* Convert the argument to a path.  !!! obsolete? */
-static Expr prim_toPath(EvalState & state, const ATermVector & args)
+static void prim_toPath(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string path = coerceToPath(state, args[0], context);
-    return makeStr(canonPath(path), context);
+    Path path = state.coerceToPath(*args[0], context);
+    mkString(v, canonPath(path), context);
 }
 
 
@@ -575,60 +511,58 @@ static Expr prim_toPath(EvalState & state, const ATermVector & args)
    /nix/store/newhash-oldhash-oldname.  In the past, `toPath' had
    special case behaviour for store paths, but that created weird
    corner cases. */
-static Expr prim_storePath(EvalState & state, const ATermVector & args)
+static void prim_storePath(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Path path = canonPath(coerceToPath(state, args[0], context));
+    Path path = canonPath(state.coerceToPath(*args[0], context));
     if (!isInStore(path))
         throw EvalError(format("path `%1%' is not in the Nix store") % path);
     Path path2 = toStorePath(path);
     if (!store->isValidPath(path2))
         throw EvalError(format("store path `%1%' is not valid") % path2);
     context.insert(path2);
-    return makeStr(path, context);
+    mkString(v, path, context);
 }
 
 
-static Expr prim_pathExists(EvalState & state, const ATermVector & args)
+static void prim_pathExists(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Path path = coerceToPath(state, args[0], context);
+    Path path = state.coerceToPath(*args[0], context);
     if (!context.empty())
         throw EvalError(format("string `%1%' cannot refer to other paths") % path);
-    return makeBool(pathExists(path));
+    mkBool(v, pathExists(path));
 }
 
 
 /* Return the base name of the given string, i.e., everything
    following the last slash. */
-static Expr prim_baseNameOf(EvalState & state, const ATermVector & args)
+static void prim_baseNameOf(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    return makeStr(baseNameOf(coerceToString(state, args[0], context)), context);
+    mkString(v, baseNameOf(state.coerceToString(*args[0], context)), context);
 }
 
 
 /* Return the directory of the given path, i.e., everything before the
    last slash.  Return either a path or a string depending on the type
    of the argument. */
-static Expr prim_dirOf(EvalState & state, const ATermVector & args)
+static void prim_dirOf(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Expr e = evalExpr(state, args[0]); ATerm dummy;
-    bool isPath = matchPath(e, dummy);
-    Path dir = dirOf(coerceToPath(state, e, context));
-    return isPath ? makePath(toATerm(dir)) : makeStr(dir, context);
+    Path dir = dirOf(state.coerceToPath(*args[0], context));
+    if (args[0]->type == tPath) mkPath(v, dir.c_str()); else mkString(v, dir, context);
 }
 
 
 /* Return the contents of a file as a string. */
-static Expr prim_readFile(EvalState & state, const ATermVector & args)
+static void prim_readFile(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Path path = coerceToPath(state, args[0], context);
+    Path path = state.coerceToPath(*args[0], context);
     if (!context.empty())
         throw EvalError(format("string `%1%' cannot refer to other paths") % path);
-    return makeStr(readFile(path));
+    mkString(v, readFile(path).c_str());
 }
 
 
@@ -640,26 +574,26 @@ static Expr prim_readFile(EvalState & state, const ATermVector & args)
 /* Convert the argument (which can be any Nix expression) to an XML
    representation returned in a string.  Not all Nix expressions can
    be sensibly or completely represented (e.g., functions). */
-static Expr prim_toXML(EvalState & state, const ATermVector & args)
+static void prim_toXML(EvalState & state, Value * * args, Value & v)
 {
     std::ostringstream out;
     PathSet context;
-    printTermAsXML(strictEvalExpr(state, args[0]), out, context);
-    return makeStr(out.str(), context);
+    printValueAsXML(state, true, false, *args[0], out, context);
+    mkString(v, out.str(), context);
 }
 
 
 /* Store a string in the Nix store as a source file that can be used
    as an input by derivations. */
-static Expr prim_toFile(EvalState & state, const ATermVector & args)
+static void prim_toFile(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string name = evalStringNoCtx(state, args[0]);
-    string contents = evalString(state, args[1], context);
+    string name = state.forceStringNoCtx(*args[0]);
+    string contents = state.forceString(*args[1], context);
 
     PathSet refs;
 
-    for (PathSet::iterator i = context.begin(); i != context.end(); ++i) {
+    foreach (PathSet::iterator, i, context) {
         Path path = *i;
         if (path.at(0) == '=') path = string(path, 1);
         if (isDerivation(path))
@@ -674,17 +608,17 @@ static Expr prim_toFile(EvalState & state, const ATermVector & args)
     /* Note: we don't need to add `context' to the context of the
        result, since `storePath' itself has references to the paths
        used in args[1]. */
-    
-    return makeStr(storePath, singleton<PathSet>(storePath));
+
+    mkString(v, storePath, singleton<PathSet>(storePath));
 }
 
 
 struct FilterFromExpr : PathFilter
 {
     EvalState & state;
-    Expr filter;
+    Value & filter;
     
-    FilterFromExpr(EvalState & state, Expr filter)
+    FilterFromExpr(EvalState & state, Value & filter)
         : state(state), filter(filter)
     {
     }
@@ -695,35 +629,47 @@ struct FilterFromExpr : PathFilter
         if (lstat(path.c_str(), &st))
             throw SysError(format("getting attributes of path `%1%'") % path);
 
-        Expr call =
-            makeCall(
-                makeCall(filter, makeStr(path)),
-                makeStr(
-                    S_ISREG(st.st_mode) ? "regular" :
-                    S_ISDIR(st.st_mode) ? "directory" :
-                    S_ISLNK(st.st_mode) ? "symlink" :
-                    "unknown" /* not supported, will fail! */
-                    ));
-                
-        return evalBool(state, call);
+        /* Call the filter function.  The first argument is the path,
+           the second is a string indicating the type of the file. */
+        Value arg1;
+        mkString(arg1, path);
+
+        Value fun2;
+        state.callFunction(filter, arg1, fun2);
+
+        Value arg2;
+        mkString(arg2, 
+            S_ISREG(st.st_mode) ? "regular" :
+            S_ISDIR(st.st_mode) ? "directory" :
+            S_ISLNK(st.st_mode) ? "symlink" :
+            "unknown" /* not supported, will fail! */);
+        
+        Value res;
+        state.callFunction(fun2, arg2, res);
+
+        return state.forceBool(res);
     }
 };
 
 
-static Expr prim_filterSource(EvalState & state, const ATermVector & args)
+static void prim_filterSource(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    Path path = coerceToPath(state, args[1], context);
+    Path path = state.coerceToPath(*args[1], context);
     if (!context.empty())
         throw EvalError(format("string `%1%' cannot refer to other paths") % path);
 
-    FilterFromExpr filter(state, args[0]);
+    state.forceValue(*args[0]);
+    if (args[0]->type != tLambda)
+        throw TypeError(format("first argument in call to `filterSource' is not a function but %1%") % showType(*args[0]));
+
+    FilterFromExpr filter(state, *args[0]);
 
     Path dstPath = readOnlyMode
         ? computeStorePathForPath(path, true, htSHA256, filter).first
         : store->addToStore(path, true, htSHA256, filter);
 
-    return makeStr(dstPath, singleton<PathSet>(dstPath));
+    mkString(v, dstPath, singleton<PathSet>(dstPath));
 }
 
 
@@ -734,131 +680,119 @@ static Expr prim_filterSource(EvalState & state, const ATermVector & args)
 
 /* Return the names of the attributes in an attribute set as a sorted
    list of strings. */
-static Expr prim_attrNames(EvalState & state, const ATermVector & args)
+static void prim_attrNames(EvalState & state, Value * * args, Value & v)
 {
-    ATermMap attrs;
-    queryAllAttrs(evalExpr(state, args[0]), attrs);
+    state.forceAttrs(*args[0]);
 
-    StringSet names;
-    for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i)
-        names.insert(aterm2String(i->key));
+    state.mkList(v, args[0]->attrs->size());
+    Value * vs = state.allocValues(v.list.length);
 
-    ATermList list = ATempty;
-    for (StringSet::const_reverse_iterator i = names.rbegin();
-         i != names.rend(); ++i)
-        list = ATinsert(list, makeStr(*i, PathSet()));
+    StringSet names;
+    foreach (Bindings::iterator, i, *args[0]->attrs)
+        names.insert(i->first);
 
-    return makeList(list);
+    unsigned int n = 0;
+    foreach (StringSet::iterator, i, names) {
+        v.list.elems[n] = &vs[n];
+        mkString(vs[n++], *i);
+    }
 }
 
 
 /* Dynamic version of the `.' operator. */
-static Expr prim_getAttr(EvalState & state, const ATermVector & args)
+static void prim_getAttr(EvalState & state, Value * * args, Value & v)
 {
-    string attr = evalStringNoCtx(state, args[0]);
-    return evalExpr(state, makeSelect(args[1], toATerm(attr)));
+    string attr = state.forceStringNoCtx(*args[0]);
+    state.forceAttrs(*args[1]);
+    // !!! Should we create a symbol here or just do a lookup?
+    Bindings::iterator i = args[1]->attrs->find(state.symbols.create(attr));
+    if (i == args[1]->attrs->end())
+        throw EvalError(format("attribute `%1%' missing") % attr);
+    // !!! add to stack trace?
+    state.forceValue(i->second.value);
+    v = i->second.value;
 }
 
 
 /* Dynamic version of the `?' operator. */
-static Expr prim_hasAttr(EvalState & state, const ATermVector & args)
+static void prim_hasAttr(EvalState & state, Value * * args, Value & v)
 {
-    string attr = evalStringNoCtx(state, args[0]);
-    return evalExpr(state, makeOpHasAttr(args[1], toATerm(attr)));
+    string attr = state.forceStringNoCtx(*args[0]);
+    state.forceAttrs(*args[1]);
+    mkBool(v, args[1]->attrs->find(state.symbols.create(attr)) != args[1]->attrs->end());
 }
 
 
-/* Builds an attribute set from a list specifying (name, value)
-   pairs.  To be precise, a list [{name = "name1"; value = value1;}
-   ... {name = "nameN"; value = valueN;}] is transformed to {name1 =
-   value1; ... nameN = valueN;}. */
-static Expr prim_listToAttrs(EvalState & state, const ATermVector & args)
+/* Determine whether the argument is an attribute set. */
+static void prim_isAttrs(EvalState & state, Value * * args, Value & v)
 {
-    try {
-        ATermMap res = ATermMap();
-        ATermList list;
-        list = evalList(state, args[0]);
-        for (ATermIterator i(list); i; ++i){
-            // *i should now contain a pointer to the list item expression
-            ATermList attrs;
-            Expr evaledExpr = evalExpr(state, *i);
-            if (matchAttrs(evaledExpr, attrs)){
-                Expr e = evalExpr(state, makeSelect(evaledExpr, toATerm("name")));
-                string attr = evalStringNoCtx(state,e);
-                Expr r = makeSelect(evaledExpr, toATerm("value"));
-                res.set(toATerm(attr), makeAttrRHS(r, makeNoPos()));
-            }
-            else
-                throw TypeError(format("list element in `listToAttrs' is %s, expected a set { name = \"<name>\"; value = <value>; }")
-                    % showType(evaledExpr));
-        }
-    
-        return makeAttrs(res);
-    
-    } catch (Error & e) {
-        e.addPrefix(format("in `listToAttrs':\n"));
-        throw;
-    }
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tAttrs);
 }
 
 
-static Expr prim_removeAttrs(EvalState & state, const ATermVector & args)
+static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
 {
-    ATermMap attrs;
-    queryAllAttrs(evalExpr(state, args[0]), attrs, true);
-    
-    ATermList list = evalList(state, args[1]);
+    state.forceAttrs(*args[0]);
+    state.forceList(*args[1]);
 
-    for (ATermIterator i(list); i; ++i)
-        /* It's not an error for *i not to exist. */
-        attrs.remove(toATerm(evalStringNoCtx(state, *i)));
+    state.cloneAttrs(*args[0], v);
 
-    return makeAttrs(attrs);
+    for (unsigned int i = 0; i < args[1]->list.length; ++i) {
+        state.forceStringNoCtx(*args[1]->list.elems[i]);
+        v.attrs->erase(state.symbols.create(args[1]->list.elems[i]->string.s));
+    }
 }
 
 
-/* Determine whether the argument is an attribute set. */
-static Expr prim_isAttrs(EvalState & state, const ATermVector & args)
+/* Builds an attribute set from a list specifying (name, value)
+   pairs.  To be precise, a list [{name = "name1"; value = value1;}
+   ... {name = "nameN"; value = valueN;}] is transformed to {name1 =
+   value1; ... nameN = valueN;}. */
+static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
 {
-    ATermList list;
-    return makeBool(matchAttrs(evalExpr(state, args[0]), list));
-}
+    state.forceList(*args[0]);
 
+    state.mkAttrs(v);
 
-/* Return the right-biased intersection of two attribute sets as1 and
-   as2, i.e. a set that contains every attribute from as2 that is also
-   a member of as1. */
-static Expr prim_intersectAttrs(EvalState & state, const ATermVector & args)
-{
-    ATermMap as1, as2;
-    queryAllAttrs(evalExpr(state, args[0]), as1, true);
-    queryAllAttrs(evalExpr(state, args[1]), as2, true);
-
-    ATermMap res;
-    foreach (ATermMap::const_iterator, i, as2)
-        if (as1[i->key]) res.set(i->key, i->value);
+    for (unsigned int i = 0; i < args[0]->list.length; ++i) {
+        Value & v2(*args[0]->list.elems[i]);
+        state.forceAttrs(v2);
+        
+        Bindings::iterator j = v2.attrs->find(state.sName);
+        if (j == v2.attrs->end())
+            throw TypeError("`name' attribute missing in a call to `listToAttrs'");
+        string name = state.forceStringNoCtx(j->second.value);
+        
+        j = v2.attrs->find(state.symbols.create("value"));
+        if (j == v2.attrs->end())
+            throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-    return makeAttrs(res);
+        Attr & a = (*v.attrs)[state.symbols.create(name)];
+        mkCopy(a.value, j->second.value);
+        a.pos = j->second.pos;
+    }
 }
 
 
-static void attrsInPattern(ATermMap & map, Pattern pat)
+/* Return the right-biased intersection of two attribute sets as1 and
+   as2, i.e. a set that contains every attribute from as2 that is also
+   a member of as1. */
+static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
 {
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    ATermBool ellipsis;
-    if (matchAttrsPat(pat, formals, ellipsis)) { 
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm def;
-            if (!matchFormal(*i, name, def)) abort();
-            map.set(name, makeAttrRHS(makeBool(def != constNoDefaultValue), makeNoPos()));
+    state.forceAttrs(*args[0]);
+    state.forceAttrs(*args[1]);
+        
+    state.mkAttrs(v);
+    
+    foreach (Bindings::iterator, i, *args[1]->attrs) {
+        Bindings::iterator j = args[0]->attrs->find(i->first);
+        if (j != args[0]->attrs->end()) {
+            Attr & a = (*v.attrs)[i->first];
+            mkCopy(a.value, i->second.value);
+            a.pos = i->second.pos;
         }
     }
-    else if (matchAtPat(pat, pat1, pat2)) {
-        attrsInPattern(map, pat1);
-        attrsInPattern(map, pat2);
-    }
 }
 
 
@@ -875,17 +809,18 @@ static void attrsInPattern(ATermMap & map, Pattern pat)
       functionArgs (x: ...)
    => { }
 */
-static Expr prim_functionArgs(EvalState & state, const ATermVector & args)
+static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
 {
-    Expr f = evalExpr(state, args[0]);
-    ATerm pat, body, pos;
-    if (!matchFunction(f, pat, body, pos))
-        throw TypeError("`functionArgs' required a function");
-    
-    ATermMap as;
-    attrsInPattern(as, pat);
+    state.forceValue(*args[0]);
+    if (args[0]->type != tLambda)
+        throw TypeError("`functionArgs' requires a function");
 
-    return makeAttrs(as);
+    state.mkAttrs(v);
+
+    if (!args[0]->lambda.fun->matchAttrs) return;
+
+    foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
+        mkBool((*v.attrs)[i->name].value, i->def);
 }
 
 
@@ -895,53 +830,58 @@ static Expr prim_functionArgs(EvalState & state, const ATermVector & args)
 
 
 /* Determine whether the argument is a list. */
-static Expr prim_isList(EvalState & state, const ATermVector & args)
+static void prim_isList(EvalState & state, Value * * args, Value & v)
 {
-    ATermList list;
-    return makeBool(matchList(evalExpr(state, args[0]), list));
+    state.forceValue(*args[0]);
+    mkBool(v, args[0]->type == tList);
 }
 
 
 /* Return the first element of a list. */
-static Expr prim_head(EvalState & state, const ATermVector & args)
+static void prim_head(EvalState & state, Value * * args, Value & v)
 {
-    ATermList list = evalList(state, args[0]);
-    if (ATisEmpty(list))
+    state.forceList(*args[0]);
+    if (args[0]->list.length == 0)
         throw Error("`head' called on an empty list");
-    return evalExpr(state, ATgetFirst(list));
+    state.forceValue(*args[0]->list.elems[0]);
+    v = *args[0]->list.elems[0];
 }
 
 
 /* Return a list consisting of everything but the the first element of
    a list. */
-static Expr prim_tail(EvalState & state, const ATermVector & args)
+static void prim_tail(EvalState & state, Value * * args, Value & v)
 {
-    ATermList list = evalList(state, args[0]);
-    if (ATisEmpty(list))
+    state.forceList(*args[0]);
+    if (args[0]->list.length == 0)
         throw Error("`tail' called on an empty list");
-    return makeList(ATgetNext(list));
+    state.mkList(v, args[0]->list.length - 1);
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        v.list.elems[n] = args[0]->list.elems[n + 1];
 }
 
 
 /* Apply a function to every element of a list. */
-static Expr prim_map(EvalState & state, const ATermVector & args)
+static void prim_map(EvalState & state, Value * * args, Value & v)
 {
-    Expr fun = evalExpr(state, args[0]);
-    ATermList list = evalList(state, args[1]);
+    state.forceFunction(*args[0]);
+    state.forceList(*args[1]);
 
-    ATermList res = ATempty;
-    for (ATermIterator i(list); i; ++i)
-        res = ATinsert(res, makeCall(fun, *i));
+    state.mkList(v, args[1]->list.length);
+    Value * vs = state.allocValues(v.list.length);
 
-    return makeList(ATreverse(res));
+    for (unsigned int n = 0; n < v.list.length; ++n) {
+        v.list.elems[n] = &vs[n];
+        mkApp(vs[n], *args[0], *args[1]->list.elems[n]);
+    }
 }
 
 
 /* Return the length of a list.  This is an O(1) time operation. */
-static Expr prim_length(EvalState & state, const ATermVector & args)
+static void prim_length(EvalState & state, Value * * args, Value & v)
 {
-    ATermList list = evalList(state, args[0]);
-    return makeInt(ATgetLength(list));
+    state.forceList(*args[0]);
+    mkInt(v, args[0]->list.length);
 }
 
 
@@ -950,44 +890,35 @@ static Expr prim_length(EvalState & state, const ATermVector & args)
  *************************************************************/
 
 
-static Expr prim_add(EvalState & state, const ATermVector & args)
+static void prim_add(EvalState & state, Value * * args, Value & v)
 {
-    int i1 = evalInt(state, args[0]);
-    int i2 = evalInt(state, args[1]);
-    return makeInt(i1 + i2);
+    mkInt(v, state.forceInt(*args[0]) + state.forceInt(*args[1]));
 }
 
 
-static Expr prim_sub(EvalState & state, const ATermVector & args)
+static void prim_sub(EvalState & state, Value * * args, Value & v)
 {
-    int i1 = evalInt(state, args[0]);
-    int i2 = evalInt(state, args[1]);
-    return makeInt(i1 - i2);
+    mkInt(v, state.forceInt(*args[0]) - state.forceInt(*args[1]));
 }
 
 
-static Expr prim_mul(EvalState & state, const ATermVector & args)
+static void prim_mul(EvalState & state, Value * * args, Value & v)
 {
-    int i1 = evalInt(state, args[0]);
-    int i2 = evalInt(state, args[1]);
-    return makeInt(i1 * i2);
+    mkInt(v, state.forceInt(*args[0]) * state.forceInt(*args[1]));
 }
 
 
-static Expr prim_div(EvalState & state, const ATermVector & args)
+static void prim_div(EvalState & state, Value * * args, Value & v)
 {
-    int i1 = evalInt(state, args[0]);
-    int i2 = evalInt(state, args[1]);
+    int i2 = state.forceInt(*args[1]);
     if (i2 == 0) throw EvalError("division by zero");
-    return makeInt(i1 / i2);
+    mkInt(v, state.forceInt(*args[0]) / i2);
 }
 
 
-static Expr prim_lessThan(EvalState & state, const ATermVector & args)
+static void prim_lessThan(EvalState & state, Value * * args, Value & v)
 {
-    int i1 = evalInt(state, args[0]);
-    int i2 = evalInt(state, args[1]);
-    return makeBool(i1 < i2);
+    mkBool(v, state.forceInt(*args[0]) < state.forceInt(*args[1]));
 }
 
 
@@ -999,11 +930,11 @@ static Expr prim_lessThan(EvalState & state, const ATermVector & args)
 /* Convert the argument to a string.  Paths are *not* copied to the
    store, so `toString /foo/bar' yields `"/foo/bar"', not
    `"/nix/store/whatever..."'. */
-static Expr prim_toString(EvalState & state, const ATermVector & args)
+static void prim_toString(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string s = coerceToString(state, args[0], context, true, false);
-    return makeStr(s, context);
+    string s = state.coerceToString(*args[0], context, true, false);
+    mkString(v, s, context);
 }
 
 
@@ -1011,32 +942,32 @@ static Expr prim_toString(EvalState & state, const ATermVector & args)
    at character position `min(start, stringLength str)' inclusive and
    ending at `min(start + len, stringLength str)'.  `start' must be
    non-negative. */
-static Expr prim_substring(EvalState & state, const ATermVector & args)
+static void prim_substring(EvalState & state, Value * * args, Value & v)
 {
-    int start = evalInt(state, args[0]);
-    int len = evalInt(state, args[1]);
+    int start = state.forceInt(*args[0]);
+    int len = state.forceInt(*args[1]);
     PathSet context;
-    string s = coerceToString(state, args[2], context);
+    string s = state.coerceToString(*args[2], context);
 
     if (start < 0) throw EvalError("negative start position in `substring'");
 
-    return makeStr(string(s, start, len), context);
+    mkString(v, string(s, start, len), context);
 }
 
 
-static Expr prim_stringLength(EvalState & state, const ATermVector & args)
+static void prim_stringLength(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string s = coerceToString(state, args[0], context);
-    return makeInt(s.size());
+    string s = state.coerceToString(*args[0], context);
+    mkInt(v, s.size());
 }
 
 
-static Expr prim_unsafeDiscardStringContext(EvalState & state, const ATermVector & args)
+static void prim_unsafeDiscardStringContext(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string s = coerceToString(state, args[0], context);
-    return makeStr(s, PathSet());
+    string s = state.coerceToString(*args[0], context);
+    mkString(v, s, PathSet());
 }
 
 
@@ -1046,10 +977,10 @@ static Expr prim_unsafeDiscardStringContext(EvalState & state, const ATermVector
    source-only deployment).  This primop marks the string context so
    that builtins.derivation adds the path to drv.inputSrcs rather than
    drv.inputDrvs. */
-static Expr prim_unsafeDiscardOutputDependency(EvalState & state, const ATermVector & args)
+static void prim_unsafeDiscardOutputDependency(EvalState & state, Value * * args, Value & v)
 {
     PathSet context;
-    string s = coerceToString(state, args[0], context);
+    string s = state.coerceToString(*args[0], context);
 
     PathSet context2;
     foreach (PathSet::iterator, i, context) {
@@ -1058,29 +989,7 @@ static Expr prim_unsafeDiscardOutputDependency(EvalState & state, const ATermVec
         context2.insert(p);
     }
     
-    return makeStr(s, context2);
-}
-
-
-/* Expression serialization/deserialization */
-
-
-static Expr prim_exprToString(EvalState & state, const ATermVector & args)
-{
-    /* !!! this disregards context */
-    return makeStr(atPrint(evalExpr(state, args[0])));
-}
-
-
-static Expr prim_stringToExpr(EvalState & state, const ATermVector & args)
-{
-    /* !!! this can introduce arbitrary garbage terms in the
-       evaluator! */;
-    string s;
-    PathSet l;
-    if (!matchStr(evalExpr(state, args[0]), s, l))
-        throw EvalError("stringToExpr needs string argument!");
-    return ATreadFromString(s.c_str());
+    mkString(v, s, context2);
 }
 
 
@@ -1089,23 +998,21 @@ static Expr prim_stringToExpr(EvalState & state, const ATermVector & args)
  *************************************************************/
 
 
-static Expr prim_parseDrvName(EvalState & state, const ATermVector & args)
+static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
 {
-    string name = evalStringNoCtx(state, args[0]);
+    string name = state.forceStringNoCtx(*args[0]);
     DrvName parsed(name);
-    ATermMap attrs(2);
-    attrs.set(toATerm("name"), makeAttrRHS(makeStr(parsed.name), makeNoPos()));
-    attrs.set(toATerm("version"), makeAttrRHS(makeStr(parsed.version), makeNoPos()));
-    return makeAttrs(attrs);
+    state.mkAttrs(v);
+    mkString((*v.attrs)[state.sName].value, parsed.name);
+    mkString((*v.attrs)[state.symbols.create("version")].value, parsed.version);
 }
 
 
-static Expr prim_compareVersions(EvalState & state, const ATermVector & args)
+static void prim_compareVersions(EvalState & state, Value * * args, Value & v)
 {
-    string version1 = evalStringNoCtx(state, args[0]);
-    string version2 = evalStringNoCtx(state, args[1]);
-    int d = compareVersions(version1, version2);
-    return makeInt(d);
+    string version1 = state.forceStringNoCtx(*args[0]);
+    string version2 = state.forceStringNoCtx(*args[1]);
+    mkInt(v, compareVersions(version1, version2));
 }
 
 
@@ -1114,16 +1021,31 @@ static Expr prim_compareVersions(EvalState & state, const ATermVector & args)
  *************************************************************/
 
 
-void EvalState::addPrimOps()
+void EvalState::createBaseEnv()
 {
-    addPrimOp("builtins", 0, prim_builtins);
-        
-    // Constants
-    addPrimOp("true", 0, prim_true);
-    addPrimOp("false", 0, prim_false);
-    addPrimOp("null", 0, prim_null);
-    addPrimOp("__currentSystem", 0, prim_currentSystem);
-    addPrimOp("__currentTime", 0, prim_currentTime);
+    baseEnv.up = 0;
+
+    /* Add global constants such as `true' to the base environment. */
+    Value v;
+
+    /* `builtins' must be first! */
+    mkAttrs(v);
+    addConstant("builtins", v);
+
+    mkBool(v, true);
+    addConstant("true", v);
+    
+    mkBool(v, false);
+    addConstant("false", v);
+    
+    v.type = tNull;
+    addConstant("null", v);
+
+    mkInt(v, time(0));
+    addConstant("__currentTime", v);
+
+    mkString(v, thisSystem.c_str());
+    addConstant("__currentSystem", v);
 
     // Miscellaneous
     addPrimOp("import", 1, prim_import);
@@ -1140,14 +1062,14 @@ void EvalState::addPrimOps()
     addPrimOp("__getEnv", 1, prim_getEnv);
     addPrimOp("__trace", 2, prim_trace);
 
-    
-    // Expr <-> String
-    addPrimOp("__exprToString", 1, prim_exprToString);
-    addPrimOp("__stringToExpr", 1, prim_stringToExpr);
-
     // Derivations
-    addPrimOp("derivation!", 1, prim_derivationStrict);
-    addPrimOp("derivation", 1, prim_derivationLazy);
+    addPrimOp("derivationStrict", 1, prim_derivationStrict);
+
+    /* 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);
 
     // Paths
     addPrimOp("__toPath", 1, prim_toPath);
@@ -1178,7 +1100,7 @@ void EvalState::addPrimOps()
     addPrimOp("__tail", 1, prim_tail);
     addPrimOp("map", 2, prim_map);
     addPrimOp("__length", 1, prim_length);
-
+    
     // Integer arithmetic
     addPrimOp("__add", 2, prim_add);
     addPrimOp("__sub", 2, prim_sub);
@@ -1195,7 +1117,7 @@ void EvalState::addPrimOps()
 
     // Versions
     addPrimOp("__parseDrvName", 1, prim_parseDrvName);
-    addPrimOp("__compareVersions", 2, prim_compareVersions);
+    addPrimOp("__compareVersions", 2, prim_compareVersions);    
 }
 
 
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
new file mode 100644
index 000000000..424c23538
--- /dev/null
+++ b/src/libexpr/symbol-table.hh
@@ -0,0 +1,81 @@
+#ifndef __SYMBOL_TABLE_H
+#define __SYMBOL_TABLE_H
+
+#include <map>
+#include <tr1/unordered_set>
+
+#include "types.hh"
+
+namespace nix {
+
+/* Symbol table used by the parser and evaluator to represent and look
+   up identifiers and attribute sets efficiently.
+   SymbolTable::create() converts a string into a symbol.  Symbols
+   have the property that they can be compared efficiently (using a
+   pointer equality test), because the symbol table stores only one
+   copy of each string. */
+
+class Symbol
+{
+private:
+    const string * s; // pointer into SymbolTable
+    Symbol(const string * s) : s(s) { };
+    friend class SymbolTable;
+
+public:
+    bool operator == (const Symbol & s2) const
+    {
+        return s == s2.s;
+    }
+    
+    bool operator != (const Symbol & s2) const
+    {
+        return s != s2.s;
+    }
+    
+    bool operator < (const Symbol & s2) const
+    {
+        return s < s2.s;
+    }
+
+    operator const string & () const
+    {
+        return *s;
+    }
+
+    bool empty() const
+    {
+        return s->empty();
+    }
+
+    friend std::ostream & operator << (std::ostream & str, const Symbol & sym);
+};
+
+inline std::ostream & operator << (std::ostream & str, const Symbol & sym)
+{
+    str << *sym.s;
+    return str;
+}
+
+class SymbolTable
+{
+private:
+    typedef std::tr1::unordered_set<string> Symbols;
+    Symbols symbols;
+
+public:
+    Symbol create(const string & s)
+    {
+        std::pair<Symbols::iterator, bool> res = symbols.insert(s);
+        return Symbol(&*res.first);
+    }
+
+    unsigned int size() const
+    {
+        return symbols.size();
+    }
+};
+
+}
+
+#endif /* !__SYMBOL_TABLE_H */
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
new file mode 100644
index 000000000..e751fd300
--- /dev/null
+++ b/src/libexpr/value-to-xml.cc
@@ -0,0 +1,161 @@
+#include "value-to-xml.hh"
+#include "xml-writer.hh"
+#include "util.hh"
+
+#include <cstdlib>
+
+
+namespace nix {
+
+    
+static XMLAttrs singletonAttrs(const string & name, const string & value)
+{
+    XMLAttrs attrs;
+    attrs[name] = value;
+    return attrs;
+}
+
+
+static void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, XMLWriter & doc, PathSet & context, PathSet & drvsSeen);
+
+
+static void posToXML(XMLAttrs & xmlAttrs, const Pos & pos)
+{
+    xmlAttrs["path"] = pos.file;
+    xmlAttrs["line"] = (format("%1%") % pos.line).str();
+    xmlAttrs["column"] = (format("%1%") % pos.column).str();
+}
+
+
+static void showAttrs(EvalState & state, bool strict, bool location,
+    Bindings & attrs, XMLWriter & doc, PathSet & context, PathSet & drvsSeen)
+{
+    StringSet names;
+    
+    foreach (Bindings::iterator, i, attrs)
+        names.insert(i->first);
+    
+    foreach (StringSet::iterator, i, names) {
+        Attr & a(attrs[state.symbols.create(*i)]);
+        
+        XMLAttrs xmlAttrs;
+        xmlAttrs["name"] = *i;
+        if (location && a.pos != &noPos) posToXML(xmlAttrs, *a.pos);
+        
+        XMLOpenElement _(doc, "attr", xmlAttrs);
+        printValueAsXML(state, strict, location,
+            a.value, doc, context, drvsSeen);
+    }
+}
+
+
+static void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, XMLWriter & doc, PathSet & context, PathSet & drvsSeen)
+{
+    checkInterrupt();
+
+    if (strict) state.forceValue(v);
+        
+    switch (v.type) {
+
+        case tInt:
+            doc.writeEmptyElement("int", singletonAttrs("value", (format("%1%") % v.integer).str()));
+            break;
+
+        case tBool:
+            doc.writeEmptyElement("bool", singletonAttrs("value", v.boolean ? "true" : "false"));
+            break;
+
+        case tString:
+            /* !!! show the context? */
+            doc.writeEmptyElement("string", singletonAttrs("value", v.string.s));
+            break;
+
+        case tPath:
+            doc.writeEmptyElement("path", singletonAttrs("value", v.path));
+            break;
+
+        case tNull:
+            doc.writeEmptyElement("null");
+            break;
+
+        case tAttrs:
+            if (state.isDerivation(v)) {
+                XMLAttrs xmlAttrs;
+            
+                Bindings::iterator a = v.attrs->find(state.symbols.create("derivation"));
+
+                Path drvPath;
+                a = v.attrs->find(state.sDrvPath);
+                if (a != v.attrs->end()) {
+                    if (strict) state.forceValue(a->second.value);
+                    if (a->second.value.type == tString)
+                        xmlAttrs["drvPath"] = drvPath = a->second.value.string.s;
+                }
+        
+                a = v.attrs->find(state.sOutPath);
+                if (a != v.attrs->end()) {
+                    if (strict) state.forceValue(a->second.value);
+                    if (a->second.value.type == tString)
+                        xmlAttrs["outPath"] = a->second.value.string.s;
+                }
+
+                XMLOpenElement _(doc, "derivation", xmlAttrs);
+
+                if (drvPath != "" && drvsSeen.find(drvPath) == drvsSeen.end()) {
+                    drvsSeen.insert(drvPath);
+                    showAttrs(state, strict, location, *v.attrs, doc, context, drvsSeen);
+                } else
+                    doc.writeEmptyElement("repeated");
+            }
+
+            else {
+                XMLOpenElement _(doc, "attrs");
+                showAttrs(state, strict, location, *v.attrs, doc, context, drvsSeen);
+            }
+            
+            break;
+
+        case tList: {
+            XMLOpenElement _(doc, "list");
+            for (unsigned int n = 0; n < v.list.length; ++n)
+                printValueAsXML(state, strict, location, *v.list.elems[n], doc, context, drvsSeen);
+            break;
+        }
+
+        case tLambda: {
+            XMLAttrs xmlAttrs;
+            if (location) posToXML(xmlAttrs, v.lambda.fun->pos);
+            XMLOpenElement _(doc, "function", xmlAttrs);
+            
+            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;
+        }
+
+        default:
+            doc.writeEmptyElement("unevaluated");
+    }
+}
+
+
+void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, std::ostream & out, PathSet & context)
+{
+    XMLWriter doc(true, out);
+    XMLOpenElement root(doc, "expr");
+    PathSet drvsSeen;    
+    printValueAsXML(state, strict, location, v, doc, context, drvsSeen);
+}
+
+ 
+}
diff --git a/src/libexpr/value-to-xml.hh b/src/libexpr/value-to-xml.hh
new file mode 100644
index 000000000..0c6de3a8b
--- /dev/null
+++ b/src/libexpr/value-to-xml.hh
@@ -0,0 +1,17 @@
+#ifndef __VALUE_TO_XML_H
+#define __VALUE_TO_XML_H
+
+#include <string>
+#include <map>
+
+#include "nixexpr.hh"
+#include "eval.hh"
+
+namespace nix {
+
+void printValueAsXML(EvalState & state, bool strict, bool location,
+    Value & v, std::ostream & out, PathSet & context);
+    
+}
+
+#endif /* !__VALUE_TO_XML_H */