* Working evaluator.

* Mutually recursive attribute sets.
* Print evaluator efficiency statistics.

10 files changed, 540 insertions, 309 deletions

diff --git a/src/fix-ng/Makefile.am b/src/fix-ng/Makefile.am
index b0e90450e3..359e39c46c 100644
--- a/src/fix-ng/Makefile.am
+++ b/src/fix-ng/Makefile.am
@@ -1,6 +1,6 @@
 bin_PROGRAMS = fix-ng
 
-fix_ng_SOURCES = fix-expr.cc parser.cc eval.cc fix.cc
+fix_ng_SOURCES = fix-expr.cc parser.cc eval.cc primops.cc fix.cc
 fix_ng_LDADD = ../libmain/libmain.a ../libnix/libnix.a ../boost/format/libformat.a \
  -L../../externals/inst/lib -ldb_cxx -lsglr -lATB -lconversion -lasfix2 -lmept -lATerm
 
diff --git a/src/fix-ng/eval.cc b/src/fix-ng/eval.cc
index c0f4680a49..7854677416 100644
--- a/src/fix-ng/eval.cc
+++ b/src/fix-ng/eval.cc
@@ -1,18 +1,167 @@
 #include "eval.hh"
 #include "expr.hh"
 #include "parser.hh"
+#include "primops.hh"
 
 
 EvalState::EvalState()
 {
     blackHole = ATmake("BlackHole()");
     if (!blackHole) throw Error("cannot build black hole");
+    nrEvaluated = nrCached = 0;
+}
+
+
+Expr getAttr(EvalState & state, Expr e, const string & name)
+{
+}
+
+
+/* Substitute an argument set into the body of a function. */
+static Expr substArgs(Expr body, ATermList formals, Expr arg)
+{
+    Subs subs;
+    Expr undefined = ATmake("Undefined");
+
+    /* Get the formal arguments. */
+    while (!ATisEmpty(formals)) {
+        char * s;
+        if (!ATmatch(ATgetFirst(formals), "<str>", &s))
+            abort(); /* can't happen */
+        subs[s] = undefined;
+        formals = ATgetNext(formals);
+    }
+
+    /* Get the actual arguments, and check that they match with the
+       formals. */
+    Attrs args;
+    queryAllAttrs(arg, args);
+    for (Attrs::iterator i = args.begin(); i != args.end(); i++) {
+        if (subs.find(i->first) == subs.end())
+            throw badTerm(format("argument `%1%' not declared") % i->first, arg);
+        subs[i->first] = i->second;
+    }
+
+    /* Check that all arguments are defined. */
+    for (Subs::iterator i = subs.begin(); i != subs.end(); i++)
+        if (i->second == undefined)
+            throw badTerm(format("formal argument `%1%' missing") % i->first, arg);
+    
+    return substitute(subs, body);
+}
+
+
+/* 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}'. */
+ATerm expandRec(ATerm e, ATermList bnds)
+{
+    /* Create the substitution list. */
+    Subs subs;
+    ATermList bs = bnds;
+    while (!ATisEmpty(bs)) {
+        char * s;
+        Expr e2;
+        if (!ATmatch(ATgetFirst(bs), "Bind(<str>, <term>)", &s, &e2))
+            abort(); /* can't happen */
+        subs[s] = ATmake("Select(<term>, <str>)", e, s);
+        bs = ATgetNext(bs);
+    }
+
+    /* Create the non-recursive set. */
+    Attrs as;
+    bs = bnds;
+    while (!ATisEmpty(bs)) {
+        char * s;
+        Expr e2;
+        if (!ATmatch(ATgetFirst(bs), "Bind(<str>, <term>)", &s, &e2))
+            abort(); /* can't happen */
+        as[s] = substitute(subs, e2);
+        bs = ATgetNext(bs);
+    }
+
+    return makeAttrs(as);
+}
+
+
+string evalString(EvalState & state, Expr e)
+{
+    e = evalExpr(state, e);
+    char * s;
+    if (!ATmatch(e, "Str(<str>)", &s))
+        throw badTerm("string expected", e);
+    return s;
+}
+
+
+Path evalPath(EvalState & state, Expr e)
+{
+    e = evalExpr(state, e);
+    char * s;
+    if (!ATmatch(e, "Path(<str>)", &s))
+        throw badTerm("path expected", e);
+    return s;
 }
 
 
 Expr evalExpr2(EvalState & state, Expr e)
 {
-    return e;
+    Expr e1, e2, e3, e4;
+    char * s1;
+
+    /* Normal forms. */
+    if (ATmatch(e, "Str(<str>)", &s1) ||
+        ATmatch(e, "Path(<str>)", &s1) ||
+        ATmatch(e, "Uri(<str>)", &s1) ||
+        ATmatch(e, "Function([<list>], <term>)", &e1, &e2) ||
+        ATmatch(e, "Attrs([<list>])", &e1) ||
+        ATmatch(e, "List([<list>])", &e1))
+        return e;
+
+    /* Any encountered variables must be undeclared or primops. */
+    if (ATmatch(e, "Var(<str>)", &s1)) {
+        return e;
+    }
+
+    /* Function application. */
+    if (ATmatch(e, "Call(<term>, <term>)", &e1, &e2)) {
+        
+        /* Evaluate the left-hand side. */
+        e1 = evalExpr(state, e1);
+
+        /* Is it a primop or a function? */
+        if (ATmatch(e1, "Var(<str>)", &s1)) {
+            string primop(s1);
+            if (primop == "import") return primImport(state, e2);
+            if (primop == "derivation") return primDerivation(state, e2);
+            else throw badTerm("undefined variable/primop", e1);
+        }
+
+        else if (ATmatch(e1, "Function([<list>], <term>)", &e3, &e4)) {
+            return evalExpr(state, 
+                substArgs(e4, (ATermList) e3, evalExpr(state, e2)));
+        }
+        
+        else throw badTerm("expecting a function or primop", e1);
+    }
+
+    /* Attribute selection. */
+    if (ATmatch(e, "Select(<term>, <str>)", &e1, &s1)) {
+        string name(s1);
+        Expr a = queryAttr(evalExpr(state, e1), name);
+        if (!a) throw badTerm(format("missing attribute `%1%'") % name, e);
+        return evalExpr(state, a);
+    }
+
+    /* Mutually recursive sets. */
+    ATermList bnds;
+    if (ATmatch(e, "Rec([<list>])", &bnds))
+        return expandRec(e, (ATermList) bnds);
+
+    /* Barf. */
+    throw badTerm("invalid expression", e);
 }
 
 
@@ -20,12 +169,15 @@ Expr evalExpr(EvalState & state, Expr e)
 {
     Nest nest(lvlVomit, format("evaluating expression: %1%") % printTerm(e));
 
+    state.nrEvaluated++;
+
     /* Consult the memo table to quickly get the normal form of
        previously evaluated expressions. */
     NormalForms::iterator i = state.normalForms.find(e);
     if (i != state.normalForms.end()) {
         if (i->second == state.blackHole)
             throw badTerm("infinite recursion", e);
+        state.nrCached++;
         return i->second;
     }
 
@@ -43,3 +195,11 @@ Expr evalFile(EvalState & state, const Path & path)
     Expr e = parseExprFromFile(path);
     return evalExpr(state, e);
 }
+
+
+void printEvalStats(EvalState & state)
+{
+    debug(format("evaluated %1% expressions, %2% cache hits, %3%%% efficiency")
+        % state.nrEvaluated % state.nrCached
+        % ((float) state.nrCached / (float) state.nrEvaluated * 100));
+}
diff --git a/src/fix-ng/eval.hh b/src/fix-ng/eval.hh
index 5fcb648a74..364f28471b 100644
--- a/src/fix-ng/eval.hh
+++ b/src/fix-ng/eval.hh
@@ -4,19 +4,23 @@
 #include <map>
 
 #include "fix-expr.hh"
+#include "expr.hh"
 
 
 typedef map<Expr, Expr> NormalForms;
-//typedef map<Path, PathSet> PkgPaths;
-//typedef map<Path, Hash> PkgHashes;
+typedef map<Path, PathSet> DrvPaths;
+typedef map<Path, Hash> DrvHashes;
 
 struct EvalState 
 {
     NormalForms normalForms;
-    //    PkgPaths pkgPaths;
-    //    PkgHashes pkgHashes; /* normalised package hashes */
+    DrvPaths drvPaths;
+    DrvHashes drvHashes; /* normalised derivation hashes */
     Expr blackHole;
 
+    unsigned int nrEvaluated;
+    unsigned int nrCached;
+
     EvalState();
 };
 
@@ -27,5 +31,12 @@ Expr evalExpr(EvalState & state, Expr e);
 /* Evaluate an expression read from the given file to normal form. */
 Expr evalFile(EvalState & state, const Path & path);
 
+/* Specific results. */
+string evalString(EvalState & state, Expr e);
+Path evalPath(EvalState & state, Expr e);
+
+/* Print statistics. */
+void printEvalStats(EvalState & state);
+
 
 #endif /* !__EVAL_H */
diff --git a/src/fix-ng/fix-expr.cc b/src/fix-ng/fix-expr.cc
index 8d47817ff0..ff0b7d43d0 100644
--- a/src/fix-ng/fix-expr.cc
+++ b/src/fix-ng/fix-expr.cc
@@ -31,3 +31,96 @@ ATerm bottomupRewrite(TermFun & f, ATerm e)
 
     return e;
 }
+
+
+void queryAllAttrs(Expr e, Attrs & attrs)
+{
+    ATermList bnds;
+    if (!ATmatch(e, "Attrs([<list>])", &bnds))
+        throw badTerm("expected attribute set", e);
+
+    while (!ATisEmpty(bnds)) {
+        char * s;
+        Expr e;
+        if (!ATmatch(ATgetFirst(bnds), "Bind(<str>, <term>)", &s, &e))
+            abort(); /* can't happen */
+        attrs[s] = e;
+        bnds = ATgetNext(bnds);
+    }
+}
+
+
+Expr queryAttr(Expr e, const string & name)
+{
+    Attrs attrs;
+    queryAllAttrs(e, attrs);
+    Attrs::iterator i = attrs.find(name);
+    return i == attrs.end() ? 0 : i->second;
+}
+
+
+Expr makeAttrs(const Attrs & attrs)
+{
+    ATermList bnds = ATempty;
+    for (Attrs::const_iterator i = attrs.begin(); i != attrs.end(); i++)
+        bnds = ATinsert(bnds, 
+            ATmake("Bind(<str>, <term>)", i->first.c_str(), i->second));
+    return ATmake("Attrs(<term>)", ATreverse(bnds));
+}
+
+
+ATerm substitute(Subs & subs, ATerm e)
+{
+    char * s;
+
+    if (ATmatch(e, "Var(<str>)", &s)) {
+        Subs::iterator i = subs.find(s);
+        if (i == subs.end())
+            return e;
+        else
+            return i->second;
+    }
+
+    /* In case of a function, filter out all variables bound by this
+       function. */
+    ATermList formals;
+    ATerm body;
+    if (ATmatch(e, "Function([<list>], <term>)", &formals, &body)) {
+        Subs subs2(subs);
+        ATermList fs = formals;
+        while (!ATisEmpty(fs)) {
+            if (!ATmatch(ATgetFirst(fs), "<str>", &s)) abort();
+            subs2.erase(s);
+            fs = ATgetNext(fs);
+        }
+        return ATmake("Function(<term>, <term>)", formals,
+            substitute(subs2, body));
+    }
+
+    /* !!! Rec(...) */
+
+    if (ATgetType(e) == AT_APPL) {
+        AFun fun = ATgetAFun(e);
+        int arity = ATgetArity(fun);
+        ATermList args = ATempty;
+
+        for (int i = arity - 1; i >= 0; i--)
+            args = ATinsert(args, substitute(subs, ATgetArgument(e, i)));
+        
+        return (ATerm) ATmakeApplList(fun, args);
+    }
+
+    if (ATgetType(e) == AT_LIST) {
+        ATermList in = (ATermList) e;
+        ATermList out = ATempty;
+
+        while (!ATisEmpty(in)) {
+            out = ATinsert(out, substitute(subs, ATgetFirst(in)));
+            in = ATgetNext(in);
+        }
+
+        return (ATerm) ATreverse(out);
+    }
+
+    return e;
+}
diff --git a/src/fix-ng/fix-expr.hh b/src/fix-ng/fix-expr.hh
index 5c50e9170f..700f7beca9 100644
--- a/src/fix-ng/fix-expr.hh
+++ b/src/fix-ng/fix-expr.hh
@@ -1,6 +1,8 @@
 #ifndef __FIXEXPR_H
 #define __FIXEXPR_H
 
+#include <map>
+
 #include <aterm2.h>
 
 #include "util.hh"
@@ -15,13 +17,27 @@ typedef ATerm Expr;
 /* 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
 {
     virtual ATerm operator () (ATerm e) = 0;
 };
-
 ATerm bottomupRewrite(TermFun & f, ATerm e);
 
+/* Query all attributes in an attribute set expression.  The
+   expression must be in normal form. */
+typedef map<string, Expr> Attrs;
+void queryAllAttrs(Expr e, Attrs & attrs);
+
+/* Query a specific attribute from an attribute set expression.  The
+   expression must be in normal form. */
+Expr queryAttr(Expr e, const string & name);
+
+/* Create an attribute set expression from an Attrs value. */
+Expr makeAttrs(const Attrs & attrs);
+
+/* Perform a set of substitutions on an expression. */
+typedef map<string, Expr> Subs;
+ATerm substitute(Subs & subs, ATerm e);
+
 
 #endif /* !__FIXEXPR_H */
diff --git a/src/fix-ng/fix.cc b/src/fix-ng/fix.cc
index fb98dc6978..d791461bd5 100644
--- a/src/fix-ng/fix.cc
+++ b/src/fix-ng/fix.cc
@@ -9,7 +9,6 @@
 
 
 #if 0
-#if 0
 static Path searchPath(const Paths & searchDirs, const Path & relPath)
 {
     if (string(relPath, 0, 1) == "/") return relPath;
@@ -28,178 +27,9 @@ static Path searchPath(const Paths & searchDirs, const Path & relPath)
 #endif
 
 
-static Expr substExpr(string x, Expr rep, Expr e)
-{
-    char * s;
-    Expr e2;
-
-    if (ATmatch(e, "Var(<str>)", &s))
-        if (x == s)
-            return rep;
-        else
-            return e;
-
-    ATermList formals;
-    if (ATmatch(e, "Function([<list>], <term>)", &formals, &e2)) {
-        while (!ATisEmpty(formals)) {
-            if (!ATmatch(ATgetFirst(formals), "<str>", &s))
-                throw badTerm("not a list of formals", (ATerm) formals);
-            if (x == (string) s)
-                return e;
-            formals = ATgetNext(formals);
-        }
-    }
-
-    /* Generically substitute in subterms. */
-
-    if (ATgetType(e) == AT_APPL) {
-        AFun fun = ATgetAFun(e);
-        int arity = ATgetArity(fun);
-        ATermList args = ATempty;
-
-        for (int i = arity - 1; i >= 0; i--)
-            args = ATinsert(args, substExpr(x, rep, ATgetArgument(e, i)));
-        
-        return (ATerm) ATmakeApplList(fun, args);
-    }
-
-    if (ATgetType(e) == AT_LIST) {
-        ATermList in = (ATermList) e;
-        ATermList out = ATempty;
-
-        while (!ATisEmpty(in)) {
-            out = ATinsert(out, substExpr(x, rep, ATgetFirst(in)));
-            in = ATgetNext(in);
-        }
-
-        return (ATerm) ATreverse(out);
-    }
-
-    throw badTerm("do not know how to substitute", e);
-}
-
-
-static Expr substExprMany(ATermList formals, ATermList args, Expr body)
-{
-    char * s;
-    Expr e;
-
-    /* !!! check args against formals */
-
-    while (!ATisEmpty(args)) {
-        ATerm tup = ATgetFirst(args);
-        if (!ATmatch(tup, "(<str>, <term>)", &s, &e))
-            throw badTerm("expected an argument tuple", tup);
-
-        body = substExpr(s, e, body);
-
-        args = ATgetNext(args);
-    }
-    
-    return body;
-}
-
-
-static PathSet nixExprRootsCached(EvalState & state, const Path & nePath)
-{
-    PkgPaths::iterator i = state.pkgPaths.find(nePath);
-    if (i != state.pkgPaths.end())
-        return i->second;
-    else {
-        PathSet paths = nixExprRoots(nePath);
-        state.pkgPaths[nePath] = paths;
-        return paths;
-    }
-}
-
-
-static Hash hashPackage(EvalState & state, NixExpr ne)
-{
-    if (ne.type == NixExpr::neDerivation) {
-	PathSet inputs2;
-        for (PathSet::iterator i = ne.derivation.inputs.begin();
-             i != ne.derivation.inputs.end(); i++)
-        {
-            PkgHashes::iterator j = state.pkgHashes.find(*i);
-            if (j == state.pkgHashes.end())
-                throw Error(format("don't know expression `%1%'") % (string) *i);
-            inputs2.insert(j->second);
-        }
-	ne.derivation.inputs = inputs2;
-    }
-    return hashTerm(unparseNixExpr(ne));
-}
-
-
-static string processBinding(EvalState & state, Expr e, NixExpr & ne)
-{
-    char * s1;
-
-    if (ATmatch(e, "NixExpr(<str>)", &s1)) {
-        Path nePath(s1);
-        PathSet paths = nixExprRootsCached(state, nePath);
-        if (paths.size() != 1) abort();
-        Path path = *(paths.begin());
-        ne.derivation.inputs.insert(nePath);
-        return path;
-    }
-    
-    if (ATmatch(e, "<str>", &s1))
-        return s1;
-
-    if (ATmatch(e, "True")) return "1";
-    
-    if (ATmatch(e, "False")) return "";
-
-    ATermList l;
-    if (ATmatch(e, "[<list>]", &l)) {
-	string s;
-	bool first = true;
-        while (!ATisEmpty(l)) {
-	    if (!first) s = s + " "; else first = false;
-	    s += processBinding(state, evalExpr(state, ATgetFirst(l)), ne);
-            l = ATgetNext(l);
-        }
-	return s;
-    }
-    
-    throw badTerm("invalid package binding", e);
-}
-
-
+#if 0
 static Expr evalExpr2(EvalState & state, Expr e)
 {
-    char * s1;
-    Expr e1, e2, e3, e4;
-    ATermList bnds;
-
-    /* Normal forms. */
-    if (ATmatch(e, "<str>", &s1) ||
-        ATmatch(e, "[<list>]", &e1) ||
-        ATmatch(e, "True") ||
-        ATmatch(e, "False") ||
-        ATmatch(e, "Function([<list>], <term>)", &e1, &e2) ||
-        ATmatch(e, "NixExpr(<str>)", &s1))
-        return e;
-
-    try {
-        Hash pkgHash = hashPackage(state, parseNixExpr(e));
-        Path pkgPath = writeTerm(e, "");
-        state.pkgHashes[pkgPath] = pkgHash;
-        return ATmake("NixExpr(<str>)", pkgPath.c_str());
-    } catch (...) { /* !!! catch parse errors only */
-    }
-
-    /* Application. */
-    if (ATmatch(e, "Call(<term>, [<list>])", &e1, &e2) ||
-        ATmatch(e, "App(<term>, [<list>])", &e1, &e2)) {
-        e1 = evalExpr(state, e1);
-        if (!ATmatch(e1, "Function([<list>], <term>)", &e3, &e4))
-            throw badTerm("expecting a function", e1);
-        return evalExpr(state,
-            substExprMany((ATermList) e3, (ATermList) e2, e4));
-    }
-
     /* Conditional. */
     if (ATmatch(e, "If(<term>, <term>, <term>)", &e1, &e2, &e3)) {
         e1 = evalExpr(state, e1);
@@ -226,127 +56,6 @@ static Expr evalExpr2(EvalState & state, Expr e)
             ATmake("True") : ATmake("False");
     }
 
-    /* Platform constant. */
-    if (ATmatch(e, "Platform")) {
-        return ATmake("<str>", thisSystem.c_str());
-    }
-
-    /* Fix inclusion. */
-    if (ATmatch(e, "IncludeFix(<str>)", &s1)) {
-        Path fileName(s1);
-        return evalFile(state, s1);
-    }
-
-    /* Relative files. */
-    if (ATmatch(e, "Relative(<str>)", &s1)) {
-        Path srcPath = s1;
-        Path dstPath = addToStore(srcPath);
-
-        ClosureElem elem;
-        NixExpr ne;
-        ne.type = NixExpr::neClosure;
-        ne.closure.roots.insert(dstPath);
-        ne.closure.elems[dstPath] = elem;
-
-        Hash pkgHash = hashPackage(state, ne);
-        Path pkgPath = writeTerm(unparseNixExpr(ne), "");
-        state.pkgHashes[pkgPath] = pkgHash;
-
-        msg(lvlChatty, format("copied `%1%' -> closure `%2%'")
-            % srcPath % pkgPath);
-
-        return ATmake("NixExpr(<str>)", pkgPath.c_str());
-    }
-
-    /* Packages are transformed into Nix derivation expressions. */
-    if (ATmatch(e, "Package([<list>])", &bnds)) {
-
-        /* Evaluate the bindings and put them in a map. */
-        map<string, ATerm> bndMap;
-        bndMap["platform"] = ATmake("<str>", thisSystem.c_str());
-        while (!ATisEmpty(bnds)) {
-            ATerm bnd = ATgetFirst(bnds);
-            if (!ATmatch(bnd, "(<str>, <term>)", &s1, &e1))
-                throw badTerm("binding expected", bnd);
-            bndMap[s1] = evalExpr(state, e1);
-            bnds = ATgetNext(bnds);
-        }
-
-        /* Gather information for building the derivation
-           expression. */
-        NixExpr ne;
-        ne.type = NixExpr::neDerivation;
-        ne.derivation.platform = thisSystem;
-        string name;
-        Path outPath;
-        Hash outHash;
-        bool outHashGiven = false;
-        bnds = ATempty;
-
-        for (map<string, ATerm>::iterator it = bndMap.begin();
-             it != bndMap.end(); it++)
-        {
-            string key = it->first;
-            ATerm value = it->second;
-
-            if (key == "args") {
-                ATermList args;
-                if (!ATmatch(value, "[<list>]", &args))
-                    throw badTerm("list expected", value);
-                
-                while (!ATisEmpty(args)) {
-                    Expr arg = evalExpr(state, ATgetFirst(args));
-                    ne.derivation.args.push_back(processBinding(state, arg, ne));
-                    args = ATgetNext(args);
-                }
-            }
-
-            else {
-                string s = processBinding(state, value, ne);
-                ne.derivation.env[key] = s;
-
-                if (key == "build") ne.derivation.builder = s;
-                if (key == "name") name = s;
-                if (key == "outPath") outPath = s;
-                if (key == "id") { 
-                    outHash = parseHash(s);
-                    outHashGiven = true;
-                }
-            }
-
-            bnds = ATinsert(bnds, 
-                ATmake("(<str>, <term>)", key.c_str(), value));
-        }
-
-        if (ne.derivation.builder == "")
-            throw badTerm("no builder specified", e);
-        
-        if (name == "")
-            throw badTerm("no package name specified", e);
-        
-        /* Determine the output path. */
-        if (!outHashGiven) outHash = hashPackage(state, ne);
-        if (outPath == "")
-            /* Hash the Nix expression with no outputs to produce a
-               unique but deterministic path name for this package. */
-            outPath = 
-                canonPath(nixStore + "/" + ((string) outHash).c_str() + "-" + name);
-        ne.derivation.env["out"] = outPath;
-        ne.derivation.outputs.insert(outPath);
-
-        /* Write the resulting term into the Nix store directory. */
-        Hash pkgHash = outHashGiven
-            ? hashString((string) outHash + outPath)
-            : hashPackage(state, ne);
-        Path pkgPath = writeTerm(unparseNixExpr(ne), "-d-" + name);
-        state.pkgHashes[pkgPath] = pkgHash;
-
-        msg(lvlChatty, format("instantiated `%1%' -> `%2%'")
-            % name % pkgPath);
-
-        return ATmake("NixExpr(<str>)", pkgPath.c_str());
-    }
-
     /* BaseName primitive function. */
     if (ATmatch(e, "BaseName(<term>)", &e1)) {
         e1 = evalExpr(state, e1);
@@ -355,8 +64,6 @@ static Expr evalExpr2(EvalState & state, Expr e)
         return ATmake("<str>", baseNameOf(s1).c_str());
     }
 
-    /* Barf. */
-    throw badTerm("invalid expression", e);
 }
 #endif
 
@@ -374,17 +81,27 @@ static Expr evalStdin(EvalState & state)
 static void printNixExpr(EvalState & state, Expr e)
 {
     ATermList es;
-    char * s;
-    if (ATmatch(e, "NixExpr(<str>)", &s)) {
-        cout << format("%1%\n") % s;
-    } 
-    else if (ATmatch(e, "[<list>]", &es)) {
+
+    if (ATmatch(e, "Attrs([<list>])", &es)) {
+        Expr a = queryAttr(e, "type");
+        if (a && evalString(state, a) == "derivation") {
+            a = queryAttr(e, "drvPath");
+            if (a) {
+                cout << format("%1%\n") % evalPath(state, a);
+                return;
+            }
+        }
+    }
+
+    if (ATmatch(e, "[<list>]", &es)) {
         while (!ATisEmpty(es)) {
             printNixExpr(state, evalExpr(state, ATgetFirst(es)));
             es = ATgetNext(es);
         }
+        return;
     }
-    else throw badTerm("top level does not evaluate to a (list of) Nix expression(s)", e);
+
+    throw badTerm("top level does not evaluate to one or more Nix expressions", e);
 }
 
 
@@ -435,6 +152,8 @@ void run(Strings args)
         Expr e = evalFile(state, absPath(*it));
         printNixExpr(state, e);
     }
+
+    printEvalStats(state);
 }
 
 
diff --git a/src/fix-ng/fix.sdf b/src/fix-ng/fix.sdf
index 2074d98294..cae5d2748e 100644
--- a/src/fix-ng/fix.sdf
+++ b/src/fix-ng/fix.sdf
@@ -44,6 +44,9 @@ exports
     "{" {Id ","}* "}" ":" Expr
     -> Expr {cons("Function"), right}
 
+    "rec" "{" {Bind ","}* "}"
+    -> Expr {cons("Rec")}
+
     "{" {Bind ","}* "}"
     -> Expr {cons("Attrs")}
 
@@ -71,6 +74,7 @@ exports
   sorts Id Path
   lexical syntax
     [a-zA-Z\_][a-zA-Z0-9\_\']* -> Id
+    "rec" -> Id {reject}
     [0-9]+ -> Int
     "\"" ~[\n\"]* "\"" -> Str
     PathComp ("/" PathComp)+ -> Path
diff --git a/src/fix-ng/parser.cc b/src/fix-ng/parser.cc
index d146ad88cb..d310397c2d 100644
--- a/src/fix-ng/parser.cc
+++ b/src/fix-ng/parser.cc
@@ -40,7 +40,7 @@ struct Cleanup : TermFun
             string path(s);
             if (path[0] != '/')
                 path = basePath + "/" + path;
-            return ATmake("Str(<str>)", canonPath(path).c_str());
+            return ATmake("Path(<str>)", canonPath(path).c_str());
         }
 
         if (ATmatch(e, "Int(<str>)", &s)) {
diff --git a/src/fix-ng/primops.cc b/src/fix-ng/primops.cc
new file mode 100644
index 0000000000..f86f9eb38d
--- /dev/null
+++ b/src/fix-ng/primops.cc
@@ -0,0 +1,206 @@
+#include "primops.hh"
+#include "normalise.hh"
+#include "globals.hh"
+
+
+Expr primImport(EvalState & state, Expr arg)
+{
+    char * path;
+    if (!ATmatch(arg, "Path(<str>)", &path))
+        throw badTerm("path expected", arg);
+    return evalFile(state, path);
+}
+
+
+static PathSet nixExprRootsCached(EvalState & state, const Path & nePath)
+{
+    DrvPaths::iterator i = state.drvPaths.find(nePath);
+    if (i != state.drvPaths.end())
+        return i->second;
+    else {
+        PathSet paths = nixExprRoots(nePath);
+        state.drvPaths[nePath] = paths;
+        return paths;
+    }
+}
+
+
+static Hash hashDerivation(EvalState & state, NixExpr ne)
+{
+    if (ne.type == NixExpr::neDerivation) {
+	PathSet inputs2;
+        for (PathSet::iterator i = ne.derivation.inputs.begin();
+             i != ne.derivation.inputs.end(); i++)
+        {
+            DrvHashes::iterator j = state.drvHashes.find(*i);
+            if (j == state.drvHashes.end())
+                throw Error(format("don't know expression `%1%'") % (string) *i);
+            inputs2.insert(j->second);
+        }
+	ne.derivation.inputs = inputs2;
+    }
+    return hashTerm(unparseNixExpr(ne));
+}
+
+
+static Path copyAtom(EvalState & state, const Path & srcPath)
+{
+    /* !!! should be cached */
+    Path dstPath(addToStore(srcPath));
+
+    ClosureElem elem;
+    NixExpr ne;
+    ne.type = NixExpr::neClosure;
+    ne.closure.roots.insert(dstPath);
+    ne.closure.elems[dstPath] = elem;
+
+    Hash drvHash = hashDerivation(state, ne);
+    Path drvPath = writeTerm(unparseNixExpr(ne), "");
+    state.drvHashes[drvPath] = drvHash;
+
+    msg(lvlChatty, format("copied `%1%' -> closure `%2%'")
+        % srcPath % drvPath);
+    return drvPath;
+}
+
+
+static string addInput(EvalState & state, 
+    Path & nePath, NixExpr & ne)
+{
+    PathSet paths = nixExprRootsCached(state, nePath);
+    if (paths.size() != 1) abort();
+    Path path = *(paths.begin());
+    ne.derivation.inputs.insert(nePath);
+    return path;
+}
+
+
+static string processBinding(EvalState & state, Expr e, NixExpr & ne)
+{
+    e = evalExpr(state, e);
+
+    char * s;
+    ATermList es;
+
+    if (ATmatch(e, "Str(<str>)", &s)) return s;
+    if (ATmatch(e, "Uri(<str>)", &s)) return s;
+    if (ATmatch(e, "True")) return "1";
+    if (ATmatch(e, "False")) return "";
+
+    if (ATmatch(e, "Attrs([<list>])", &es)) {
+        Expr a = queryAttr(e, "type");
+        if (a && evalString(state, a) == "derivation") {
+            a = queryAttr(e, "drvPath");
+            if (a) {
+                Path drvPath = evalPath(state, a);
+                return addInput(state, drvPath, ne);
+            }
+        }
+    }
+
+    if (ATmatch(e, "Path(<str>)", &s)) {
+        Path drvPath = copyAtom(state, s);
+        return addInput(state, drvPath, ne);
+    }
+    
+    if (ATmatch(e, "List([<list>])", &es)) {
+	string s;
+	bool first = true;
+        while (!ATisEmpty(es)) {
+            Nest nest(lvlVomit, format("processing list element"));
+	    if (!first) s = s + " "; else first = false;
+	    s += processBinding(state, evalExpr(state, ATgetFirst(es)), ne);
+            es = ATgetNext(es);
+        }
+	return s;
+    }
+    
+    throw badTerm("invalid derivation binding", e);
+}
+
+
+Expr primDerivation(EvalState & state, Expr args)
+{
+    Nest nest(lvlVomit, "evaluating derivation");
+
+    Attrs attrs;
+    args = evalExpr(state, args);
+    queryAllAttrs(args, attrs);
+
+    /* Build the derivation expression by processing the attributes. */
+    NixExpr ne;
+    ne.type = NixExpr::neDerivation;
+
+    string drvName;
+    Path outPath;
+    Hash outHash;
+    bool outHashGiven = false;
+
+    for (Attrs::iterator i = attrs.begin(); i != attrs.end(); i++) {
+        string key = i->first;
+        Expr value = i->second;
+        Nest nest(lvlVomit, format("processing attribute `%1%'") % key);
+
+        /* The `args' attribute is special: it supplies the
+           command-line arguments to the builder. */
+        if (key == "args") {
+            ATermList args;
+            if (!ATmatch(value, "[<list>]", &args))
+                throw badTerm("list expected", value);
+            while (!ATisEmpty(args)) {
+                Expr arg = evalExpr(state, ATgetFirst(args));
+                ne.derivation.args.push_back(processBinding(state, arg, ne));
+                args = ATgetNext(args);
+            }
+        }
+
+        /* All other attributes are passed to the builder through the
+           environment. */
+        else {
+            string s = processBinding(state, value, ne);
+            ne.derivation.env[key] = s;
+            if (key == "builder") ne.derivation.builder = s;
+            else if (key == "system") ne.derivation.platform = s;
+            else if (key == "name") drvName = s;
+            else if (key == "outPath") outPath = s;
+            else if (key == "id") { 
+                outHash = parseHash(s);
+                outHashGiven = true;
+            }
+        }
+    }
+    
+    /* Do we have all required attributes? */
+    if (ne.derivation.builder == "")
+        throw badTerm("required attribute `builder' missing", args);
+    if (ne.derivation.platform == "")
+        throw badTerm("required attribute `system' missing", args);
+    if (drvName == "")
+        throw badTerm("required attribute `name' missing", args);
+        
+    /* Determine the output path. */
+    if (!outHashGiven) outHash = hashDerivation(state, ne);
+    if (outPath == "")
+        /* Hash the Nix expression with no outputs to produce a
+           unique but deterministic path name for this derivation. */
+        outPath = canonPath(nixStore + "/" + 
+            ((string) outHash).c_str() + "-" + drvName);
+    ne.derivation.env["out"] = outPath;
+    ne.derivation.outputs.insert(outPath);
+
+    /* Write the resulting term into the Nix store directory. */
+    Hash drvHash = outHashGiven
+        ? hashString((string) outHash + outPath)
+        : hashDerivation(state, ne);
+    Path drvPath = writeTerm(unparseNixExpr(ne), "-d-" + drvName);
+    state.drvHashes[drvPath] = drvHash;
+
+    msg(lvlChatty, format("instantiated `%1%' -> `%2%'")
+        % drvName % drvPath);
+
+    attrs["outPath"] = ATmake("Path(<str>)", outPath.c_str());
+    attrs["drvPath"] = ATmake("Path(<str>)", drvPath.c_str());
+    attrs["type"] = ATmake("Str(\"derivation\")");
+
+    return makeAttrs(attrs);
+}
diff --git a/src/fix-ng/primops.hh b/src/fix-ng/primops.hh
new file mode 100644
index 0000000000..41b572c688
--- /dev/null
+++ b/src/fix-ng/primops.hh
@@ -0,0 +1,22 @@
+#ifndef __PRIMOPS_H
+#define __PRIMOPS_H
+
+#include "eval.hh"
+
+
+/* Load and evaluate an expression from path specified by the
+   argument. */ 
+Expr primImport(EvalState & state, Expr arg);
+
+
+/* Construct (as a unobservable) side effect) a Nix derivation
+   expression that performs the derivation described by the argument
+   set.  Returns the original set extended with the following
+   attributes: `outPath' containing the primary output path of the
+   derivation; `drvPath' containing the path of the Nix expression;
+   and `type' set to `derivation' to indicate that this is a
+   derivation. */
+Expr primDerivation(EvalState & state, Expr args);
+
+
+#endif /* !__PRIMOPS_H */