* Refactoring: put the Nix expression evaluator in its own library so

  that it can be used by multiple programs.

13 files changed, 1689 insertions, 0 deletions

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
new file mode 100644
index 000000000..6fe798501
--- /dev/null
+++ b/src/libexpr/Makefile.am
@@ -0,0 +1,22 @@
+bin_PROGRAMS = nix-instantiate
+
+nix_instantiate_SOURCES = nixexpr.cc parser.cc eval.cc primops.cc main.cc
+nix_instantiate_LDADD = ../libmain/libmain.a ../libstore/libstore.a ../libutil/libutil.a \
+ ../boost/format/libformat.a -L../../externals/inst/lib -ldb_cxx \
+ -lsglr -lATB -lconversion -lasfix2 -lmept -lATerm
+
+AM_CXXFLAGS = \
+ -I.. -I../../externals/inst/include -I../libutil -I../libstore -I../libmain
+
+
+# Parse table generation.
+
+parser.o: parse-table.h
+
+parse-table.h: nix.tbl
+	../bin2c/bin2c nixParseTable < $< > $@ || (rm $@ && exit 1)
+
+%.tbl: %.sdf
+	../../externals/inst/bin/sdf2table -s -i $< -o $@
+
+CLEANFILES = parse-table.h nix.tbl
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
new file mode 100644
index 000000000..b110c3a4a
--- /dev/null
+++ b/src/libexpr/eval.cc
@@ -0,0 +1,265 @@
+#include "eval.hh"
+#include "parser.hh"
+#include "primops.hh"
+
+
+EvalState::EvalState()
+    : normalForms(32768, 75)
+{
+    blackHole = ATmake("BlackHole()");
+    if (!blackHole) throw Error("cannot build black hole");
+    nrEvaluated = nrCached = 0;
+}
+
+
+/* Substitute an argument set into the body of a function. */
+static Expr substArgs(Expr body, ATermList formals, Expr arg)
+{
+    ATMatcher m;
+    ATermMap subs;
+    Expr undefined = ATmake("Undefined");
+
+    /* Get the formal arguments. */
+    for (ATermIterator i(formals); i; ++i) {
+        Expr name, def;
+        if (atMatch(m, *i) >> "NoDefFormal" >> name)
+            subs.set(name, undefined);
+        else if (atMatch(m, *i) >> "DefFormal" >> name >> def)
+            subs.set(name, def);
+        else abort(); /* can't happen */
+    }
+
+    /* Get the actual arguments, and check that they match with the
+       formals. */
+    ATermMap args;
+    queryAllAttrs(arg, args);
+    for (ATermIterator i(args.keys()); i; ++i) {
+        Expr key = *i;
+        Expr cur = subs.get(key);
+        if (!cur)
+            throw badTerm(format("function has no formal argument `%1%'")
+                % aterm2String(key), arg);
+        subs.set(key, args.get(key));
+    }
+
+    /* Check that all arguments are defined. */
+    for (ATermIterator i(subs.keys()); i; ++i)
+        if (subs.get(*i) == undefined)
+            throw badTerm(format("formal argument `%1%' missing")
+                % aterm2String(*i), 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)
+{
+    ATMatcher m;
+
+    /* Create the substitution list. */
+    ATermMap subs;
+    for (ATermIterator i(bnds); i; ++i) {
+        string s;
+        Expr e2;
+        if (!(atMatch(m, *i) >> "Bind" >> s >> e2))
+            abort(); /* can't happen */
+        subs.set(s, ATmake("Select(<term>, <str>)", e, s.c_str()));
+    }
+
+    /* Create the non-recursive set. */
+    ATermMap as;
+    for (ATermIterator i(bnds); i; ++i) {
+        string s;
+        Expr e2;
+        if (!(atMatch(m, *i) >> "Bind" >> s >> e2))
+            abort(); /* can't happen */
+        as.set(s, substitute(subs, e2));
+    }
+
+    return makeAttrs(as);
+}
+
+
+string evalString(EvalState & state, Expr e)
+{
+    e = evalExpr(state, e);
+    ATMatcher m;
+    string s;
+    if (!(atMatch(m, e) >> "Str" >> s))
+        throw badTerm("string expected", e);
+    return s;
+}
+
+
+Path evalPath(EvalState & state, Expr e)
+{
+    e = evalExpr(state, e);
+    ATMatcher m;
+    string s;
+    if (!(atMatch(m, e) >> "Path" >> s))
+        throw badTerm("path expected", e);
+    return s;
+}
+
+
+bool evalBool(EvalState & state, Expr e)
+{
+    e = evalExpr(state, e);
+    ATMatcher m;
+    if (atMatch(m, e) >> "Bool" >> "True") return true;
+    else if (atMatch(m, e) >> "Bool" >> "False") return false;
+    else throw badTerm("expecting a boolean", e);
+}
+
+
+Expr evalExpr2(EvalState & state, Expr e)
+{
+    ATMatcher m;
+    Expr e1, e2, e3, e4;
+    string s1;
+
+    /* Normal forms. */
+    if (atMatch(m, e) >> "Str" ||
+        atMatch(m, e) >> "Path" ||
+        atMatch(m, e) >> "Uri" ||
+        atMatch(m, e) >> "Bool" ||
+        atMatch(m, e) >> "Function" ||
+        atMatch(m, e) >> "Attrs" ||
+        atMatch(m, e) >> "List")
+        return e;
+
+    /* Any encountered variables must be undeclared or primops. */
+    if (atMatch(m, e) >> "Var" >> s1) {
+        if (s1 == "null") return primNull(state);
+        return e;
+    }
+
+    /* Function application. */
+    if (atMatch(m, e) >> "Call" >> e1 >> e2) {
+
+        ATermList formals;
+        
+        /* Evaluate the left-hand side. */
+        e1 = evalExpr(state, e1);
+
+        /* Is it a primop or a function? */
+        if (atMatch(m, e1) >> "Var" >> s1) {
+            if (s1 == "import") return primImport(state, e2);
+            if (s1 == "derivation") return primDerivation(state, e2);
+            if (s1 == "toString") return primToString(state, e2);
+            if (s1 == "baseNameOf") return primBaseNameOf(state, e2);
+            if (s1 == "isNull") return primIsNull(state, e2);
+            else throw badTerm("undefined variable/primop", e1);
+        }
+
+        else if (atMatch(m, e1) >> "Function" >> formals >> e4)
+            return evalExpr(state, 
+                substArgs(e4, formals, evalExpr(state, e2)));
+        
+        else throw badTerm("expecting a function or primop", e1);
+    }
+
+    /* Attribute selection. */
+    if (atMatch(m, e) >> "Select" >> e1 >> s1) {
+        Expr a = queryAttr(evalExpr(state, e1), s1);
+        if (!a) throw badTerm(format("missing attribute `%1%'") % s1, e);
+        return evalExpr(state, a);
+    }
+
+    /* Mutually recursive sets. */
+    ATermList bnds;
+    if (atMatch(m, e) >> "Rec" >> bnds)
+        return expandRec(e, bnds);
+
+    /* Let expressions `let {..., body = ...}' are just desugared
+       into `(rec {..., body = ...}).body'. */
+    if (atMatch(m, e) >> "LetRec" >> bnds)
+        return evalExpr(state, ATmake("Select(Rec(<term>), \"body\")", bnds));
+
+    /* Conditionals. */
+    if (atMatch(m, e) >> "If" >> e1 >> e2 >> e3) {
+        if (evalBool(state, e1))
+            return evalExpr(state, e2);
+        else
+            return evalExpr(state, e3);
+    }
+
+    /* Assertions. */
+    if (atMatch(m, e) >> "Assert" >> e1 >> e2) {
+        if (!evalBool(state, e1)) throw badTerm("guard failed", e);
+        return evalExpr(state, e2);
+    }
+
+    /* Generic equality. */
+    if (atMatch(m, e) >> "OpEq" >> e1 >> e2)
+        return makeBool(evalExpr(state, e1) == evalExpr(state, e2));
+
+    /* Generic inequality. */
+    if (atMatch(m, e) >> "OpNEq" >> e1 >> e2)
+        return makeBool(evalExpr(state, e1) != evalExpr(state, e2));
+
+    /* Negation. */
+    if (atMatch(m, e) >> "OpNot" >> e1)
+        return makeBool(!evalBool(state, e1));
+
+    /* Implication. */
+    if (atMatch(m, e) >> "OpImpl" >> e1 >> e2)
+        return makeBool(!evalBool(state, e1) || evalBool(state, e2));
+
+    /* Conjunction (logical AND). */
+    if (atMatch(m, e) >> "OpAnd" >> e1 >> e2)
+        return makeBool(evalBool(state, e1) && evalBool(state, e2));
+
+    /* Disjunction (logical OR). */
+    if (atMatch(m, e) >> "OpOr" >> e1 >> e2)
+        return makeBool(evalBool(state, e1) || evalBool(state, e2));
+
+    /* Barf. */
+    throw badTerm("invalid expression", e);
+}
+
+
+Expr evalExpr(EvalState & state, Expr e)
+{
+    startNest(nest, lvlVomit,
+        format("evaluating expression: %1%") % e);
+
+    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 == state.blackHole)
+            throw badTerm("infinite recursion", e);
+        state.nrCached++;
+        return nf;
+    }
+
+    /* Otherwise, evaluate and memoize. */
+    state.normalForms.set(e, state.blackHole);
+    nf = evalExpr2(state, e);
+    state.normalForms.set(e, nf);
+    return nf;
+}
+
+
+Expr evalFile(EvalState & state, const Path & path)
+{
+    startNest(nest, lvlTalkative, format("evaluating file `%1%'") % 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/libexpr/eval.hh b/src/libexpr/eval.hh
new file mode 100644
index 000000000..0bc052676
--- /dev/null
+++ b/src/libexpr/eval.hh
@@ -0,0 +1,42 @@
+#ifndef __EVAL_H
+#define __EVAL_H
+
+#include <map>
+
+#include "aterm.hh"
+#include "hash.hh"
+#include "nixexpr.hh"
+
+
+typedef map<Path, PathSet> DrvPaths;
+typedef map<Path, Hash> DrvHashes;
+
+struct EvalState 
+{
+    ATermMap normalForms;
+    DrvPaths drvPaths;
+    DrvHashes drvHashes; /* normalised derivation hashes */
+    Expr blackHole;
+
+    unsigned int nrEvaluated;
+    unsigned int nrCached;
+
+    EvalState();
+};
+
+
+/* Evaluate an expression to normal form. */
+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/libexpr/fix-expr.cc b/src/libexpr/fix-expr.cc
new file mode 100644
index 000000000..e9c5a3ba6
--- /dev/null
+++ b/src/libexpr/fix-expr.cc
@@ -0,0 +1,215 @@
+#include "fix-expr.hh"
+#include "expr.hh"
+
+
+ATermMap::ATermMap(unsigned int initialSize, unsigned int maxLoadPct)
+{
+    table = ATtableCreate(initialSize, maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+}
+
+
+ATermMap::ATermMap(const ATermMap & map)
+    : table(0)
+{
+    ATermList keys = map.keys();
+
+    /* !!! adjust allocation for load pct */
+    table = ATtableCreate(ATgetLength(keys), map.maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+
+    for (ATermIterator i(keys); i; ++i)
+        set(*i, map.get(*i));
+}
+
+
+ATermMap::~ATermMap()
+{
+    if (table) ATtableDestroy(table);
+}
+
+
+void ATermMap::set(ATerm key, ATerm value)
+{
+    return ATtablePut(table, key, value);
+}
+
+
+void ATermMap::set(const string & key, ATerm value)
+{
+    set(string2ATerm(key), value);
+}
+
+
+ATerm ATermMap::get(ATerm key) const
+{
+    return ATtableGet(table, key);
+}
+
+
+ATerm ATermMap::get(const string & key) const
+{
+    return get(string2ATerm(key));
+}
+
+
+void ATermMap::remove(ATerm key)
+{
+    ATtableRemove(table, key);
+}
+
+
+void ATermMap::remove(const string & key)
+{
+    remove(string2ATerm(key));
+}
+
+
+ATermList ATermMap::keys() const
+{
+    ATermList keys = ATtableKeys(table);
+    if (!keys) throw Error("cannot query aterm map keys");
+    return keys;
+}
+
+
+ATerm string2ATerm(const string & s)
+{
+    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s.c_str(), 0, ATtrue));
+}
+
+
+string aterm2String(ATerm t)
+{
+    return ATgetName(ATgetAFun(t));
+}
+    
+
+ATerm bottomupRewrite(TermFun & f, ATerm e)
+{
+    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, bottomupRewrite(f, ATgetArgument(e, i)));
+        
+        e = (ATerm) ATmakeApplList(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);
+    }
+
+    return f(e);
+}
+
+
+void queryAllAttrs(Expr e, ATermMap & attrs)
+{
+    ATMatcher m;
+    ATermList bnds;
+    if (!(atMatch(m, e) >> "Attrs" >> bnds))
+        throw badTerm("expected attribute set", e);
+
+    for (ATermIterator i(bnds); i; ++i) {
+        string s;
+        Expr e;
+        if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+            abort(); /* can't happen */
+        attrs.set(s, e);
+    }
+}
+
+
+Expr queryAttr(Expr e, const string & name)
+{
+    ATermMap attrs;
+    queryAllAttrs(e, attrs);
+    return attrs.get(name);
+}
+
+
+Expr makeAttrs(const ATermMap & attrs)
+{
+    ATermList bnds = ATempty;
+    for (ATermIterator i(attrs.keys()); i; ++i)
+        bnds = ATinsert(bnds, 
+            ATmake("Bind(<term>, <term>)", *i, attrs.get(*i)));
+    return ATmake("Attrs(<term>)", ATreverse(bnds));
+}
+
+
+Expr substitute(const ATermMap & subs, Expr e)
+{
+    ATMatcher m;
+    string s;
+
+    if (atMatch(m, e) >> "Var" >> s) {
+        Expr sub = subs.get(s);
+        return sub ? sub : e;
+    }
+
+    /* In case of a function, filter out all variables bound by this
+       function. */
+    ATermList formals;
+    ATerm body;
+    if (atMatch(m, e) >> "Function" >> formals >> body) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(formals); i; ++i) {
+            Expr def;
+            if (!(atMatch(m, *i) >> "NoDefFormal" >> s) &&
+                !(atMatch(m, *i) >> "DefFormal" >> s >> def))
+                abort();
+            subs2.remove(s);
+        }
+        return ATmake("Function(<term>, <term>)", formals,
+            substitute(subs2, body));
+    }
+
+    /* Idem for a mutually recursive attribute set. */
+    ATermList bindings;
+    if (atMatch(m, e) >> "Rec" >> bindings) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(bindings); i; ++i) {
+            Expr e;
+            if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+                abort(); /* can't happen */
+            subs2.remove(s);
+        }
+        return ATmake("Rec(<term>)", substitute(subs2, (ATerm) bindings));
+    }
+
+    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 out = ATempty;
+        for (ATermIterator i((ATermList) e); i; ++i)
+            out = ATinsert(out, substitute(subs, *i));
+        return (ATerm) ATreverse(out);
+    }
+
+    return e;
+}
+
+
+Expr makeBool(bool b)
+{
+    return b ? ATmake("Bool(True)") : ATmake("Bool(False)");
+}
diff --git a/src/libexpr/fix-expr.hh b/src/libexpr/fix-expr.hh
new file mode 100644
index 000000000..6c1e51d9c
--- /dev/null
+++ b/src/libexpr/fix-expr.hh
@@ -0,0 +1,75 @@
+#ifndef __FIXEXPR_H
+#define __FIXEXPR_H
+
+#include <map>
+
+#include <aterm2.h>
+
+#include "util.hh"
+
+
+/* Fix 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;
+
+
+/* Mappings from ATerms to ATerms.  This is just a wrapper around
+   ATerm tables. */
+class ATermMap
+{
+private:
+    unsigned int maxLoadPct;
+    ATermTable table;
+    
+public:
+    ATermMap(unsigned int initialSize = 16, unsigned int maxLoadPct = 75);
+    ATermMap(const ATermMap & map);
+    ~ATermMap();
+
+    void set(ATerm key, ATerm value);
+    void set(const string & key, ATerm value);
+
+    ATerm get(ATerm key) const;
+    ATerm get(const string & key) const;
+
+    void remove(ATerm key);
+    void remove(const string & key);
+
+    ATermList keys() const;
+};
+
+
+/* Convert a string to an ATerm (i.e., a quoted nullary function
+   applicaton). */
+ATerm string2ATerm(const string & s);
+string aterm2String(ATerm t);
+
+/* 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. */
+void queryAllAttrs(Expr e, ATermMap & 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 ATermMap & attrs);
+
+/* Perform a set of substitutions on an expression. */
+Expr substitute(const ATermMap & subs, Expr e);
+
+/* Create an expression representing a boolean. */
+Expr makeBool(bool b);
+
+
+#endif /* !__FIXEXPR_H */
diff --git a/src/libexpr/main.cc b/src/libexpr/main.cc
new file mode 100644
index 000000000..aa6883ff8
--- /dev/null
+++ b/src/libexpr/main.cc
@@ -0,0 +1,117 @@
+#include <map>
+#include <iostream>
+
+#include "globals.hh"
+#include "normalise.hh"
+#include "shared.hh"
+#include "eval.hh"
+
+
+#if 0
+static Path searchPath(const Paths & searchDirs, const Path & relPath)
+{
+    if (string(relPath, 0, 1) == "/") return relPath;
+
+    for (Paths::const_iterator i = searchDirs.begin();
+         i != searchDirs.end(); i++)
+    {
+        Path path = *i + "/" + relPath;
+        if (pathExists(path)) return path;
+    }
+
+    throw Error(
+        format("path `%1%' not found in any of the search directories")
+        % relPath);
+}
+#endif
+
+
+static Expr evalStdin(EvalState & state)
+{
+    startNest(nest, lvlTalkative, format("evaluating standard input"));
+    Expr e = ATreadFromFile(stdin);
+    if (!e) 
+        throw Error(format("unable to read a term from stdin"));
+    return evalExpr(state, e);
+}
+
+
+static void printNixExpr(EvalState & state, Expr e)
+{
+    ATMatcher m;
+    ATermList es;
+
+    if (atMatch(m, e) >> "Attrs" >> 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 (ATgetType(e) == AT_LIST) {
+        for (ATermIterator i((ATermList) e); i; ++i)
+            printNixExpr(state, evalExpr(state, *i));
+        return;
+    }
+
+    throw badTerm("top level does not evaluate to one or more Nix expressions", e);
+}
+
+
+void run(Strings args)
+{
+    EvalState state;
+    Strings files;
+    bool readStdin = false;
+
+#if 0
+    state.searchDirs.push_back(".");
+    state.searchDirs.push_back(nixDataDir + "/nix");
+#endif
+    
+    for (Strings::iterator it = args.begin();
+         it != args.end(); )
+    {
+        string arg = *it++;
+
+#if 0
+        if (arg == "--includedir" || arg == "-I") {
+            if (it == args.end())
+                throw UsageError(format("argument required in `%1%'") % arg);
+            state.searchDirs.push_back(*it++);
+        }
+        else
+#endif
+        if (arg == "--verbose" || arg == "-v")
+            verbosity = (Verbosity) ((int) verbosity + 1);
+        else if (arg == "-")
+            readStdin = true;
+        else if (arg[0] == '-')
+            throw UsageError(format("unknown flag `%1%`") % arg);
+        else
+            files.push_back(arg);
+    }
+
+    openDB();
+
+    if (readStdin) {
+        Expr e = evalStdin(state);
+        printNixExpr(state, e);
+    }
+
+    for (Strings::iterator it = files.begin();
+         it != files.end(); it++)
+    {
+        Expr e = evalFile(state, absPath(*it));
+        printNixExpr(state, e);
+    }
+
+    printEvalStats(state);
+}
+
+
+string programId = "nix-instantiate";
diff --git a/src/libexpr/nix.sdf b/src/libexpr/nix.sdf
new file mode 100644
index 000000000..615bdb974
--- /dev/null
+++ b/src/libexpr/nix.sdf
@@ -0,0 +1,209 @@
+definition
+
+module Main
+imports Fix
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Top level syntax.
+
+module Fix
+imports Fix-Exprs Fix-Layout
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Expressions.
+
+module Fix-Exprs
+imports Fix-Lexicals URI
+exports
+  sorts Expr Formal Bind Binds BindSemi ExprList
+  context-free syntax
+
+    Id -> Expr {cons("Var")}
+
+    Int -> Expr {cons("Int")}
+
+    Str -> Expr {cons("Str")}
+
+    Uri -> Expr {cons("Uri")}
+
+    Path -> Expr {cons("Path")}
+
+    "(" Expr ")" -> Expr {bracket}
+
+    Expr Expr -> Expr {cons("Call"), left}
+
+    "{" {Formal ","}* "}" ":" Expr -> Expr {cons("Function")}
+    Id -> Formal {cons("NoDefFormal")}
+    Id "?" Expr -> Formal {cons("DefFormal")}
+
+    "assert" Expr ";" Expr -> Expr {cons("Assert")}
+
+    "rec" "{" Binds "}" -> Expr {cons("Rec")}
+    "let" "{" Binds "}" -> Expr {cons("LetRec")}
+    "{" Binds "}" -> Expr {cons("Attrs")}
+
+    Id "=" Expr -> Bind {cons("Bind")}
+    {Bind ";"}* -> Binds
+    Bind ";" -> BindSemi 
+    BindSemi* -> Binds
+
+    "[" ExprList "]" -> Expr {cons("List")}
+    "" -> ExprList {cons("ExprNil")}
+    Expr ExprList -> ExprList {cons("ExprCons")}
+
+    Expr "." Id -> Expr {cons("Select")}
+
+    "if" Expr "then" Expr "else" Expr -> Expr {cons("If")}
+
+    Expr "==" Expr -> Expr {cons("OpEq"), non-assoc}
+    Expr "!=" Expr -> Expr {cons("OpNEq"), non-assoc}
+
+    "!" Expr -> Expr {cons("OpNot")}
+    Expr "&&" Expr -> Expr {cons("OpAnd"), right}
+    Expr "||" Expr -> Expr {cons("OpOr"), right}
+    Expr "->" Expr -> Expr {cons("OpImpl"), right}
+
+    Bool -> Expr {cons("Bool")}
+
+  context-free priorities
+
+    Expr "." Id -> Expr
+  > Expr ExprList -> ExprList
+  > Expr Expr -> Expr
+  > "!" Expr -> Expr
+  > Expr "==" Expr -> Expr
+  > Expr "!=" Expr -> Expr
+  > Expr "&&" Expr -> Expr
+  > Expr "||" Expr -> Expr
+  > Expr "->" Expr -> Expr
+  > "assert" Expr ";" Expr -> Expr
+  > "{" {Formal ","}* "}" ":" Expr -> Expr
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Lexical syntax.
+
+module Fix-Lexicals
+exports
+  sorts Id Int Str Path PathComp Bool
+  lexical syntax
+    [a-zA-Z\_][a-zA-Z0-9\_\']* -> Id
+    "rec" -> Id {reject}
+    "let" -> Id {reject}
+    "if" -> Id {reject}
+    "then" -> Id {reject}
+    "else" -> Id {reject}
+    "true" -> Id {reject}
+    "false" -> Id {reject}
+    "assert" -> Id {reject}
+
+    [0-9]+ -> Int
+
+    "\"" ~[\n\"]* "\"" -> Str
+
+    PathComp ("/" PathComp)+ -> Path
+    [a-zA-Z0-9\.\_\-\+]+ -> PathComp
+
+    "true" -> Bool
+    "false" -> Bool
+
+  lexical restrictions
+    Id -/- [a-zA-Z0-9\_\']
+    Int -/- [0-9]
+    Path -/- [a-zA-Z0-9\.\_\-\+\/]
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% URIs (RFC 2396, appendix A).
+
+module URI
+exports
+  sorts Uri Uhierpart Uopaquepart Uuricnoslash Unetpath Uabspath
+        Urelpath Urelsegment Uscheme Uauthority Uregname Userver
+        Uuserinfo Uhostport Uhost Uhostname Udomainlabel Utoplabel
+        UIPv4address Uport Upath Upathsegments Usegment Uparam
+        Upchar Uquery Ufragment Uuric Ureserved Uunreserved Umark
+        Uescaped Uhex Ualphanum Ualpha Ulowalpha Uupalpha Udigit
+  lexical syntax
+    Uscheme ":" (Uhierpart | Uopaquepart) -> Uri
+
+    (Unetpath | Uabspath) ("?" Uquery)? -> Uhierpart
+    Uuricnoslash Uuric* -> Uopaquepart
+
+    Uunreserved | Uescaped | [\;\?\:\@\&\=\+\$\,] -> Uuricnoslash
+
+    "//" Uauthority Uabspath? -> Unetpath
+    "/" Upathsegments -> Uabspath
+    "//" Uuric* -> Uabspath {reject}
+    Urelsegment Uabspath? -> Urelpath
+
+    (Uunreserved | Uescaped | [\;\@\&\=\+\$\,])+ -> Urelsegment
+
+    Ualpha (Ualpha | Udigit | [\+\-\.])* -> Uscheme
+
+    Userver | Uregname -> Uauthority
+
+    (Uunreserved | Uescaped | [\$\,\;\:\@\&\=\+])+ -> Uregname
+
+    ((Uuserinfo "@") Uhostport) -> Userver
+    (Uunreserved | Uescaped | [\;\:\&\=\+\$\,])* -> Uuserinfo
+
+    Uhost (":" Uport)? -> Uhostport
+    Uhostname | UIPv4address -> Uhost
+    (Udomainlabel ".")+ Utoplabel "."? -> Uhostname
+    Ualphanum | Ualphanum (Ualphanum | "-")* Ualphanum -> Udomainlabel
+    Ualpha | Ualpha (Ualphanum | "-")* Ualphanum -> Utoplabel
+    Udigit+ "." Udigit+ "." Udigit+ "." Udigit+ -> UIPv4address
+    Udigit* -> Uport
+
+    Uabspath | Uopaquepart -> Upath
+    Usegment ("/" Usegment)* -> Upathsegments
+    Upchar* (";" Uparam)* -> Usegment
+    Upchar* -> Uparam
+    Uunreserved | Uescaped | [\:\@\&\=\+\$\,] -> Upchar
+
+    Uuric* -> Uquery
+
+    Uuric* -> Ufragment
+
+    Ureserved | Uunreserved | Uescaped -> Uuric
+    [\;\/\?\:\@\&\=\+\$\,] -> Ureserved
+    Ualphanum | Umark -> Uunreserved
+    [\-\_\.\!\~\*\'\(\)] -> Umark
+
+    "%" Uhex Uhex -> Uescaped
+    Udigit | [A-Fa-f] -> Uhex
+
+    Ualpha | Udigit -> Ualphanum
+    Ulowalpha | Uupalpha -> Ualpha
+
+    [a-z] -> Ulowalpha
+    [A-Z] -> Uupalpha
+    [0-9] -> Udigit
+
+  lexical restrictions
+    Uri -/- [a-zA-Z0-9\-\_\.\!\~\*\'\(\)]
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Layout.
+
+module Fix-Layout
+exports
+  sorts HashComment Asterisk Comment EOF
+  lexical syntax
+    [\ \t\n] -> LAYOUT
+    HashComment -> LAYOUT
+    Comment -> LAYOUT
+    "#" ~[\n]* ([\n] | EOF) -> HashComment
+    "//" ~[\n]* ([\n] | EOF) -> HashComment
+    "/*" ( ~[\*] | Asterisk )* "*/" -> Comment
+    [\*] -> Asterisk
+    "" -> EOF
+  lexical restrictions
+    Asterisk -/- [\/]
+    EOF -/- ~[]
+  context-free restrictions
+    LAYOUT? -/- [\ \t\n] | [\#]
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
new file mode 100644
index 000000000..816b39dc1
--- /dev/null
+++ b/src/libexpr/nixexpr.cc
@@ -0,0 +1,215 @@
+#include "nixexpr.hh"
+#include "storeexpr.hh"
+
+
+ATermMap::ATermMap(unsigned int initialSize, unsigned int maxLoadPct)
+{
+    table = ATtableCreate(initialSize, maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+}
+
+
+ATermMap::ATermMap(const ATermMap & map)
+    : table(0)
+{
+    ATermList keys = map.keys();
+
+    /* !!! adjust allocation for load pct */
+    table = ATtableCreate(ATgetLength(keys), map.maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+
+    for (ATermIterator i(keys); i; ++i)
+        set(*i, map.get(*i));
+}
+
+
+ATermMap::~ATermMap()
+{
+    if (table) ATtableDestroy(table);
+}
+
+
+void ATermMap::set(ATerm key, ATerm value)
+{
+    return ATtablePut(table, key, value);
+}
+
+
+void ATermMap::set(const string & key, ATerm value)
+{
+    set(string2ATerm(key), value);
+}
+
+
+ATerm ATermMap::get(ATerm key) const
+{
+    return ATtableGet(table, key);
+}
+
+
+ATerm ATermMap::get(const string & key) const
+{
+    return get(string2ATerm(key));
+}
+
+
+void ATermMap::remove(ATerm key)
+{
+    ATtableRemove(table, key);
+}
+
+
+void ATermMap::remove(const string & key)
+{
+    remove(string2ATerm(key));
+}
+
+
+ATermList ATermMap::keys() const
+{
+    ATermList keys = ATtableKeys(table);
+    if (!keys) throw Error("cannot query aterm map keys");
+    return keys;
+}
+
+
+ATerm string2ATerm(const string & s)
+{
+    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s.c_str(), 0, ATtrue));
+}
+
+
+string aterm2String(ATerm t)
+{
+    return ATgetName(ATgetAFun(t));
+}
+    
+
+ATerm bottomupRewrite(TermFun & f, ATerm e)
+{
+    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, bottomupRewrite(f, ATgetArgument(e, i)));
+        
+        e = (ATerm) ATmakeApplList(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);
+    }
+
+    return f(e);
+}
+
+
+void queryAllAttrs(Expr e, ATermMap & attrs)
+{
+    ATMatcher m;
+    ATermList bnds;
+    if (!(atMatch(m, e) >> "Attrs" >> bnds))
+        throw badTerm("expected attribute set", e);
+
+    for (ATermIterator i(bnds); i; ++i) {
+        string s;
+        Expr e;
+        if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+            abort(); /* can't happen */
+        attrs.set(s, e);
+    }
+}
+
+
+Expr queryAttr(Expr e, const string & name)
+{
+    ATermMap attrs;
+    queryAllAttrs(e, attrs);
+    return attrs.get(name);
+}
+
+
+Expr makeAttrs(const ATermMap & attrs)
+{
+    ATermList bnds = ATempty;
+    for (ATermIterator i(attrs.keys()); i; ++i)
+        bnds = ATinsert(bnds, 
+            ATmake("Bind(<term>, <term>)", *i, attrs.get(*i)));
+    return ATmake("Attrs(<term>)", ATreverse(bnds));
+}
+
+
+Expr substitute(const ATermMap & subs, Expr e)
+{
+    ATMatcher m;
+    string s;
+
+    if (atMatch(m, e) >> "Var" >> s) {
+        Expr sub = subs.get(s);
+        return sub ? sub : e;
+    }
+
+    /* In case of a function, filter out all variables bound by this
+       function. */
+    ATermList formals;
+    ATerm body;
+    if (atMatch(m, e) >> "Function" >> formals >> body) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(formals); i; ++i) {
+            Expr def;
+            if (!(atMatch(m, *i) >> "NoDefFormal" >> s) &&
+                !(atMatch(m, *i) >> "DefFormal" >> s >> def))
+                abort();
+            subs2.remove(s);
+        }
+        return ATmake("Function(<term>, <term>)", formals,
+            substitute(subs2, body));
+    }
+
+    /* Idem for a mutually recursive attribute set. */
+    ATermList bindings;
+    if (atMatch(m, e) >> "Rec" >> bindings) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(bindings); i; ++i) {
+            Expr e;
+            if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+                abort(); /* can't happen */
+            subs2.remove(s);
+        }
+        return ATmake("Rec(<term>)", substitute(subs2, (ATerm) bindings));
+    }
+
+    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 out = ATempty;
+        for (ATermIterator i((ATermList) e); i; ++i)
+            out = ATinsert(out, substitute(subs, *i));
+        return (ATerm) ATreverse(out);
+    }
+
+    return e;
+}
+
+
+Expr makeBool(bool b)
+{
+    return b ? ATmake("Bool(True)") : ATmake("Bool(False)");
+}
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
new file mode 100644
index 000000000..011c2900e
--- /dev/null
+++ b/src/libexpr/nixexpr.hh
@@ -0,0 +1,75 @@
+#ifndef __NIXEXPR_H
+#define __NIXEXPR_H
+
+#include <map>
+
+#include <aterm2.h>
+
+#include "util.hh"
+
+
+/* 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;
+
+
+/* Mappings from ATerms to ATerms.  This is just a wrapper around
+   ATerm tables. */
+class ATermMap
+{
+private:
+    unsigned int maxLoadPct;
+    ATermTable table;
+    
+public:
+    ATermMap(unsigned int initialSize = 16, unsigned int maxLoadPct = 75);
+    ATermMap(const ATermMap & map);
+    ~ATermMap();
+
+    void set(ATerm key, ATerm value);
+    void set(const string & key, ATerm value);
+
+    ATerm get(ATerm key) const;
+    ATerm get(const string & key) const;
+
+    void remove(ATerm key);
+    void remove(const string & key);
+
+    ATermList keys() const;
+};
+
+
+/* Convert a string to an ATerm (i.e., a quoted nullary function
+   applicaton). */
+ATerm string2ATerm(const string & s);
+string aterm2String(ATerm t);
+
+/* 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. */
+void queryAllAttrs(Expr e, ATermMap & 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 ATermMap & attrs);
+
+/* Perform a set of substitutions on an expression. */
+Expr substitute(const ATermMap & subs, Expr e);
+
+/* Create an expression representing a boolean. */
+Expr makeBool(bool b);
+
+
+#endif /* !__NIXEXPR_H */
diff --git a/src/libexpr/parser.cc b/src/libexpr/parser.cc
new file mode 100644
index 000000000..b2c74af33
--- /dev/null
+++ b/src/libexpr/parser.cc
@@ -0,0 +1,164 @@
+#include <sstream>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+extern "C" {
+#include <sglr.h>
+#include <asfix2.h>
+}
+
+#include "aterm.hh"
+#include "parser.hh"
+#include "shared.hh"
+#include "parse-table.h"
+
+
+/* Cleanup cleans up an imploded parse tree into an actual abstract
+   syntax tree that we can evaluate.  It removes quotes around
+   strings, converts integer literals into actual integers, and
+   absolutises paths relative to the directory containing the input
+   file. */
+struct Cleanup : TermFun
+{
+    string basePath;
+
+    virtual ATerm operator () (ATerm e)
+    {
+        ATMatcher m;
+        string s;
+
+        if (atMatch(m, e) >> "Str" >> s) {
+            return ATmake("Str(<str>)",
+                string(s, 1, s.size() - 2).c_str());
+        }
+
+        if (atMatch(m, e) >> "Path" >> s) {
+            if (s[0] != '/')
+                s = basePath + "/" + s;
+            return ATmake("Path(<str>)", canonPath(s).c_str());
+        }
+
+        if (atMatch(m, e) >> "Int" >> s) {
+            istringstream s2(s);
+            int n;
+            s2 >> n;
+            return ATmake("Int(<int>)", n);
+        }
+
+        if (atMatch(m, e) >> "Bool" >> "true")
+            return ATmake("Bool(True)");
+        
+        if (atMatch(m, e) >> "Bool" >> "false")
+            return ATmake("Bool(False)");
+
+        if (atMatch(m, e) >> "ExprNil")
+            return (ATerm) ATempty;
+
+        ATerm e1;
+        ATermList e2;
+        if (atMatch(m, e) >> "ExprCons" >> e1 >> e2)
+            return (ATerm) ATinsert(e2, e1);
+
+        return e;
+    }
+};
+
+
+Expr parseExprFromFile(Path path)
+{
+#if 0
+    /* Perhaps this is already an imploded parse tree? */
+    Expr e = ATreadFromNamedFile(path.c_str());
+    if (e) return e;
+#endif
+
+    /* If `path' refers to a directory, append `/default.nix'. */
+    struct stat st;
+    if (stat(path.c_str(), &st))
+        throw SysError(format("getting status of `%1%'") % path);
+    if (S_ISDIR(st.st_mode))
+        path = canonPath(path + "/default.nix");
+
+    /* Initialise the SDF libraries. */
+    static bool initialised = false;
+    static ATerm parseTable = 0;
+    static language lang = 0;
+
+    if (!initialised) {
+        PT_initMEPTApi();
+        PT_initAsFix2Api();
+        SGinitParser(ATfalse);
+
+        ATprotect(&parseTable);
+        parseTable = ATreadFromBinaryString(
+            (char *) nixParseTable, sizeof nixParseTable);
+        if (!parseTable)
+            throw Error(format("cannot construct parse table term"));
+
+        ATprotect(&lang);
+        lang = ATmake("Nix");
+        if (!SGopenLanguageFromTerm(
+                (char *) programId.c_str(), lang, parseTable))
+            throw Error(format("cannot open language"));
+
+        SG_STARTSYMBOL_ON();
+        SG_OUTPUT_ON();
+        SG_ASFIX2ME_ON();
+        SG_AMBIGUITY_ERROR_ON();
+        SG_FILTER_OFF();
+
+        initialised = true;
+    }
+
+    /* Read the input file.  We can't use SGparseFile() because it's
+       broken, so we read the input ourselves and call
+       SGparseString(). */
+    AutoCloseFD fd = open(path.c_str(), O_RDONLY);
+    if (fd == -1) throw SysError(format("opening `%1%'") % path);
+
+    if (fstat(fd, &st) == -1)
+        throw SysError(format("statting `%1%'") % path);
+
+    char text[st.st_size + 1];
+    readFull(fd, (unsigned char *) text, st.st_size);
+    text[st.st_size] = 0;
+
+    /* Parse it. */
+    ATerm result = SGparseString(lang, "Expr", text);
+    if (!result)
+        throw SysError(format("parse failed in `%1%'") % path);
+    if (SGisParseError(result))
+        throw Error(format("parse error in `%1%': %2%")
+            % path % result);
+
+    /* Implode it. */
+    PT_ParseTree tree = PT_makeParseTreeFromTerm(result);
+    if (!tree)
+        throw Error(format("cannot create parse tree"));
+    
+    ATerm imploded = PT_implodeParseTree(tree,
+        ATtrue,
+        ATtrue,
+        ATtrue,
+        ATtrue,
+        ATtrue,
+        ATtrue,
+        ATfalse,
+        ATtrue,
+        ATtrue,
+        ATtrue,
+        ATfalse);
+    if (!imploded)
+        throw Error(format("cannot implode parse tree"));
+
+    printMsg(lvlVomit, format("imploded parse tree of `%1%': %2%")
+        % path % imploded);
+
+    /* Finally, clean it up. */
+    Cleanup cleanup;
+    cleanup.basePath = dirOf(path);
+    return bottomupRewrite(cleanup, imploded);
+}
diff --git a/src/libexpr/parser.hh b/src/libexpr/parser.hh
new file mode 100644
index 000000000..5983ec562
--- /dev/null
+++ b/src/libexpr/parser.hh
@@ -0,0 +1,10 @@
+#ifndef __PARSER_H
+#define __PARSER_H
+
+#include "nixexpr.hh"
+
+
+Expr parseExprFromFile(Path path);
+
+
+#endif /* !__PARSER_H */
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
new file mode 100644
index 000000000..097933115
--- /dev/null
+++ b/src/libexpr/primops.cc
@@ -0,0 +1,246 @@
+#include "primops.hh"
+#include "normalise.hh"
+#include "globals.hh"
+
+
+Expr primImport(EvalState & state, Expr arg)
+{
+    ATMatcher m;
+    string path;
+    if (!(atMatch(m, arg) >> "Path" >> path))
+        throw badTerm("path expected", arg);
+    return evalFile(state, path);
+}
+
+
+static PathSet storeExprRootsCached(EvalState & state, const Path & nePath)
+{
+    DrvPaths::iterator i = state.drvPaths.find(nePath);
+    if (i != state.drvPaths.end())
+        return i->second;
+    else {
+        PathSet paths = storeExprRoots(nePath);
+        state.drvPaths[nePath] = paths;
+        return paths;
+    }
+}
+
+
+static Hash hashDerivation(EvalState & state, StoreExpr ne)
+{
+    if (ne.type == StoreExpr::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(unparseStoreExpr(ne));
+}
+
+
+static Path copyAtom(EvalState & state, const Path & srcPath)
+{
+    /* !!! should be cached */
+    Path dstPath(addToStore(srcPath));
+
+    ClosureElem elem;
+    StoreExpr ne;
+    ne.type = StoreExpr::neClosure;
+    ne.closure.roots.insert(dstPath);
+    ne.closure.elems[dstPath] = elem;
+
+    Hash drvHash = hashDerivation(state, ne);
+    Path drvPath = writeTerm(unparseStoreExpr(ne), "");
+    state.drvHashes[drvPath] = drvHash;
+
+    printMsg(lvlChatty, format("copied `%1%' -> closure `%2%'")
+        % srcPath % drvPath);
+    return drvPath;
+}
+
+
+static string addInput(EvalState & state, 
+    Path & nePath, StoreExpr & ne)
+{
+    PathSet paths = storeExprRootsCached(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, StoreExpr & ne)
+{
+    e = evalExpr(state, e);
+
+    ATMatcher m;
+    string s;
+    ATermList es;
+
+    if (atMatch(m, e) >> "Str" >> s) return s;
+    if (atMatch(m, e) >> "Uri" >> s) return s;
+    if (atMatch(m, e) >> "Bool" >> "True") return "1";
+    if (atMatch(m, e) >> "Bool" >> "False") return "";
+
+    if (atMatch(m, e) >> "Attrs" >> 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(m, e) >> "Path" >> s) {
+        Path drvPath = copyAtom(state, s);
+        return addInput(state, drvPath, ne);
+    }
+    
+    if (atMatch(m, e) >> "List" >> es) {
+	string s;
+	bool first = true;
+        for (ATermIterator i(es); i; ++i) {
+            startNest(nest, lvlVomit, format("processing list element"));
+	    if (!first) s = s + " "; else first = false;
+	    s += processBinding(state, evalExpr(state, *i), ne);
+        }
+	return s;
+    }
+
+    if (atMatch(m, e) >> "Null") return "";
+    
+    throw badTerm("invalid derivation binding", e);
+}
+
+
+Expr primDerivation(EvalState & state, Expr args)
+{
+    startNest(nest, lvlVomit, "evaluating derivation");
+
+    ATermMap attrs;
+    args = evalExpr(state, args);
+    queryAllAttrs(args, attrs);
+
+    /* Build the derivation expression by processing the attributes. */
+    StoreExpr ne;
+    ne.type = StoreExpr::neDerivation;
+
+    string drvName;
+    Path outPath;
+    Hash outHash;
+    bool outHashGiven = false;
+
+    for (ATermIterator i(attrs.keys()); i; ++i) {
+        string key = aterm2String(*i);
+        Expr value = attrs.get(key);
+        startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
+
+        /* The `args' attribute is special: it supplies the
+           command-line arguments to the builder. */
+        if (key == "args") {
+            throw Error("args not implemented");
+#if 0
+            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);
+            }
+#endif
+        }
+
+        /* 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(unparseStoreExpr(ne), "-d-" + drvName);
+    state.drvHashes[drvPath] = drvHash;
+
+    printMsg(lvlChatty, format("instantiated `%1%' -> `%2%'")
+        % drvName % drvPath);
+
+    attrs.set("outPath", ATmake("Path(<str>)", outPath.c_str()));
+    attrs.set("drvPath", ATmake("Path(<str>)", drvPath.c_str()));
+    attrs.set("type", ATmake("Str(\"derivation\")"));
+
+    return makeAttrs(attrs);
+}
+
+
+Expr primBaseNameOf(EvalState & state, Expr arg)
+{
+    string s = evalString(state, arg);
+    return ATmake("Str(<str>)", baseNameOf(s).c_str());
+}
+
+
+Expr primToString(EvalState & state, Expr arg)
+{
+    arg = evalExpr(state, arg);
+    ATMatcher m;
+    string s;
+    if (atMatch(m, arg) >> "Str" >> s ||
+        atMatch(m, arg) >> "Path" >> s ||
+        atMatch(m, arg) >> "Uri" >> s)
+        return ATmake("Str(<str>)", s.c_str());
+    else throw badTerm("cannot coerce to string", arg);
+}
+
+
+Expr primNull(EvalState & state)
+{
+    return ATmake("Null");
+}
+
+
+Expr primIsNull(EvalState & state, Expr arg)
+{
+    arg = evalExpr(state, arg);
+    ATMatcher m;
+    return makeBool(atMatch(m, arg) >> "Null");
+}
diff --git a/src/libexpr/primops.hh b/src/libexpr/primops.hh
new file mode 100644
index 000000000..76d587afd
--- /dev/null
+++ b/src/libexpr/primops.hh
@@ -0,0 +1,34 @@
+#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);
+
+/* Return the base name of the given string, i.e., everything
+   following the last slash. */
+Expr primBaseNameOf(EvalState & state, Expr arg);
+
+/* Convert the argument (which can be a path or a uri) to a string. */
+Expr primToString(EvalState & state, Expr arg);
+
+/* Return the null value. */
+Expr primNull(EvalState & state);
+
+/* Determine whether the argument is the null value. */
+Expr primIsNull(EvalState & state, Expr arg);
+
+
+#endif /* !__PRIMOPS_H */