* Don't use ATmake / ATmatch anymore, nor the ATMatcher class.

  Instead we generate data bindings (build and match functions) for
  the constructors specified in `constructors.def'.  In particular
  this removes the conversions between AFuns and strings, and Nix
  expression evaluation now seems 3 to 4 times faster.

11 files changed, 410 insertions, 304 deletions

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index 45145a6bdb..99ed1a5ed3 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -2,9 +2,10 @@ noinst_LIBRARIES = libexpr.a
 
 libexpr_a_SOURCES = nixexpr.cc nixexpr.hh parser.cc parser.hh \
  eval.cc eval.hh primops.cc \
- lexer-tab.c lexer-tab.h parser-tab.c parser-tab.h
+ lexer-tab.c lexer-tab.h parser-tab.c parser-tab.h \
+ constructors.hh
 
-EXTRA_DIST = lexer.l parser.y
+EXTRA_DIST = lexer.l parser.y constructors.cc
 
 AM_CXXFLAGS = \
  -I.. ${bdb_include} ${aterm_include} -I../libutil -I../libstore
@@ -23,4 +24,12 @@ lexer-tab.c lexer-tab.h: lexer.l
 	$(flex) --outfile lexer-tab.c --header-file=lexer-tab.h lexer.l 
 
 
+# ATerm helper function generation.
+
+constructors.cc constructors.hh: aterm-helper.pl constructors.def
+	$(perl) aterm-helper.pl constructors.hh constructors.cc < constructors.def
+
+nixexpr.hh: constructors.hh
+
+
 CLEANFILES =
diff --git a/src/libexpr/aterm-helper.pl b/src/libexpr/aterm-helper.pl
new file mode 100755
index 0000000000..568141cb4a
--- /dev/null
+++ b/src/libexpr/aterm-helper.pl
@@ -0,0 +1,108 @@
+#! /usr/bin/perl -w
+
+die if scalar @ARGV != 2;
+
+my $syms = "";
+my $init = "";
+
+open HEADER, ">$ARGV[0]";
+open IMPL, ">$ARGV[1]";
+
+while (<STDIN>) {
+    next if (/^\s*$/);
+    
+    if (/^\s*(\w+)\s*\|([^\|]*)\|\s*(\w+)\s*\|\s*(\w+)?/) {
+        my $const = $1;
+        my @types = split ' ', $2;
+        my $result = $3;
+        my $funname = $4;
+        $funname = $const unless defined $funname;
+
+        my $formals = "";
+        my $formals2 = "";
+        my $args = "";
+        my $unpack = "";
+        my $n = 1;
+        foreach my $type (@types) {
+            $args .= ", ";
+            if ($type eq "string") {
+#                $args .= "(ATerm) ATmakeAppl0(ATmakeAFun((char *) e$n, 0, ATtrue))";
+#                $type = "const char *";
+                $type = "ATerm";
+                $args .= "e$n";
+            } elsif ($type eq "int") {
+                $args .= "(ATerm) ATmakeInt(e$n)";
+            } elsif ($type eq "ATermList" || $type eq "ATermBlob") {
+                $args .= "(ATerm) e$n";
+            } else {
+                $args .= "e$n";
+            }
+            $formals .= ", " if $formals ne "";
+            $formals .= "$type e$n";
+            $formals2 .= ", ";
+            $formals2 .= "$type & e$n";
+            my $m = $n - 1;
+            if ($type eq "int") {
+                $unpack .= "    e$n = ATgetInt((ATermInt) ATgetArgument(e, $m));\n";
+            } elsif ($type eq "ATermList") {
+                $unpack .= "    e$n = (ATermList) ATgetArgument(e, $m);\n";
+            } elsif ($type eq "ATermBlob") {
+                $unpack .= "    e$n = (ATermBlob) ATgetArgument(e, $m);\n";
+            } else {
+                $unpack .= "    e$n = ATgetArgument(e, $m);\n";
+            }
+            $n++;
+        }
+
+        my $arity = scalar @types;
+
+        print HEADER "extern AFun sym$funname;\n\n";
+        
+        print IMPL "AFun sym$funname = 0;\n";
+        
+        print HEADER "static inline $result make$funname($formals) {\n";
+        print HEADER "    return (ATerm) ATmakeAppl$arity(sym$funname$args);\n";
+        print HEADER "}\n\n";
+
+        print HEADER "#ifdef __cplusplus\n";
+        print HEADER "static inline bool match$funname(ATerm e$formals2) {\n";
+        print HEADER "    if (ATgetAFun(e) != sym$funname) return false;\n";
+        print HEADER "$unpack";
+        print HEADER "    return true;\n";
+        print HEADER "}\n";
+        print HEADER "#endif\n\n\n";
+
+        $init .= "    sym$funname = ATmakeAFun(\"$const\", $arity, ATfalse);\n";
+        $init .= "    ATprotectAFun(sym$funname);\n";
+    }
+
+    elsif (/^\s*(\w+)\s*=\s*(.*)$/) {
+        my $name = $1;
+        my $value = $2;
+        print HEADER "extern ATerm $name;\n";
+        print IMPL "ATerm $name = 0;\n";
+        $init .= "    $name = $value;\n";
+    }
+
+    else {
+        die "bad line: `$_'";
+    }
+}
+
+print HEADER "void initSyms();\n\n";
+
+print HEADER "static inline ATerm string2ATerm(const char * s) {\n";
+print HEADER "    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s, 0, ATtrue));\n";
+print HEADER "}\n\n";
+
+print HEADER "static inline const char * aterm2String(ATerm t) {\n";
+print HEADER "    return (const char *) ATgetName(ATgetAFun(t));\n";
+print HEADER "}\n\n";
+
+print IMPL "\n";
+print IMPL "void initSyms() {\n";
+print IMPL "$init";
+print IMPL "}\n";
+
+close HEADER;
+close IMPL;
diff --git a/src/libexpr/constructors.def b/src/libexpr/constructors.def
new file mode 100644
index 0000000000..497cd33c33
--- /dev/null
+++ b/src/libexpr/constructors.def
@@ -0,0 +1,53 @@
+Pos | string int int | Pos |
+NoPos | | Pos |
+
+Function | ATermList Expr Pos | Expr |
+Function1 | string 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 |
+Call | Expr Expr | Expr |
+Select | Expr string | Expr |
+Var | string | Expr |
+Int | int | Expr |
+Str | string | Expr |
+Path | string | Expr |
+Uri | string | Expr |
+List | ATermList | Expr |
+BlackHole | | Expr |
+Undefined | | Expr |
+PrimOp | int ATermBlob ATermList | Expr |
+Attrs | ATermList | Expr |
+Closed | Expr | Expr |
+Rec | ATermList ATermList | Expr |
+Bool | ATerm | Expr |
+Null | | Expr |
+
+Bind | string Expr Pos | ATerm |
+Bind | string Expr | ATerm | Bind2
+Inherit | Expr ATermList Pos | ATerm |
+
+Scope | | Expr |
+
+NoDefFormal | string | ATerm |
+DefFormal | string Expr | ATerm |
+
+True | | ATerm |
+False | | ATerm |
+
+PrimOpDef | int ATermBlob | ATerm |
+
+AttrRHS | Expr Pos | ATerm |
+
+eTrue = makeBool(makeTrue())
+eFalse = makeBool(makeFalse())
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 35b9cae00b..88362333c2 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -1,15 +1,17 @@
 #include "eval.hh"
 #include "parser.hh"
+#include "constructors.hh"
 
 
 EvalState::EvalState()
     : normalForms(32768, 50)
 {
-    blackHole = ATmake("BlackHole()");
-    if (!blackHole) throw Error("cannot build black hole");
+    blackHole = makeBlackHole();
     
     nrEvaluated = nrCached = 0;
 
+    initSyms();
+
     addPrimOps();
 }
 
@@ -17,24 +19,22 @@ EvalState::EvalState()
 void EvalState::addPrimOp(const string & name,
     unsigned int arity, PrimOp primOp)
 {
-    primOps.set(name, ATmake("(<int>, <term>)",
-        arity, ATmakeBlob(0, (void *) primOp)));
+    primOps.set(name, makePrimOpDef(arity, ATmakeBlob(0, (void *) primOp)));
 }
 
 
 /* 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");
+    Expr undefined = makeUndefined();
 
     /* Get the formal arguments. */
     for (ATermIterator i(formals); i; ++i) {
         Expr name, def;
-        if (atMatch(m, *i) >> "NoDefFormal" >> name)
+        if (matchNoDefFormal(*i, name))
             subs.set(name, undefined);
-        else if (atMatch(m, *i) >> "DefFormal" >> name >> def)
+        else if (matchDefFormal(*i, name, def))
             subs.set(name, def);
         else abort(); /* can't happen */
     }
@@ -69,38 +69,32 @@ static Expr substArgs(Expr body, ATermList formals, Expr arg)
    (e.x) (e.y); y = e.x;}'. */
 ATerm expandRec(ATerm e, ATermList rbnds, ATermList nrbnds)
 {
-    ATMatcher m;
     ATerm name;
     Expr e2;
+    Pos pos;
 
     /* Create the substitution list. */
     ATermMap subs;
     for (ATermIterator i(rbnds); i; ++i) {
-        if (!(atMatch(m, *i) >> "Bind" >> name >> e2))
-            abort(); /* can't happen */
-        subs.set(name, ATmake("Select(<term>, <term>)", e, name));
+        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
+        subs.set(name, makeSelect(e, name));
     }
     for (ATermIterator i(nrbnds); i; ++i) {
-        if (!(atMatch(m, *i) >> "Bind" >> name >> e2))
-            abort(); /* can't happen */
+        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
         subs.set(name, e2);
     }
 
     /* Create the non-recursive set. */
     ATermMap as;
     for (ATermIterator i(rbnds); i; ++i) {
-        ATerm pos;
-        if (!(atMatch(m, *i) >> "Bind" >> name >> e2 >> pos))
-            abort(); /* can't happen */
-        as.set(name, ATmake("(<term>, <term>)", substitute(subs, e2), pos));
+        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
+        as.set(name, makeAttrRHS(substitute(subs, e2), pos));
     }
 
     /* Copy the non-recursive bindings.  !!! inefficient */
     for (ATermIterator i(nrbnds); i; ++i) {
-        ATerm pos;
-        if (!(atMatch(m, *i) >> "Bind" >> name >> e2 >> pos))
-            abort(); /* can't happen */
-        as.set(name, ATmake("(<term>, <term>)", e2, pos));
+        if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */
+        as.set(name, makeAttrRHS(e2, pos));
     }
 
     return makeAttrs(as);
@@ -122,82 +116,73 @@ static Expr updateAttrs(Expr e1, Expr e2)
 string evalString(EvalState & state, Expr e)
 {
     e = evalExpr(state, e);
-    ATMatcher m;
-    string s;
-    if (!(atMatch(m, e) >> "Str" >> s))
-        throw Error("string expected");
-    return s;
+    ATerm s;
+    if (!matchStr(e, s)) throw Error("string expected");
+    return aterm2String(s);
 }
 
 
 Path evalPath(EvalState & state, Expr e)
 {
     e = evalExpr(state, e);
-    ATMatcher m;
-    string s;
-    if (!(atMatch(m, e) >> "Path" >> s))
-        throw Error("path expected");
-    return s;
+    ATerm s;
+    if (!matchPath(e, s)) throw Error("path expected");
+    return aterm2String(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;
+    if (e == eTrue) return true;
+    else if (e == eFalse) return false;
     else throw Error("boolean expected");
 }
 
 
 Expr evalExpr2(EvalState & state, Expr e)
 {
-    ATMatcher m;
     Expr e1, e2, e3, e4;
     ATerm name, pos;
+    AFun sym = ATgetAFun(e);
 
     /* Normal forms. */
-    string cons;
-    if (atMatch(m, e) >> cons &&
-        (cons == "Str" ||
-         cons == "Path" ||
-         cons == "SubPath" ||
-         cons == "Uri" ||
-         cons == "Null" ||
-         cons == "Int" ||
-         cons == "Bool" ||
-         cons == "Function" ||
-         cons == "Function1" ||
-         cons == "Attrs" ||
-         cons == "List" ||
-         cons == "PrimOp"))
+    if (sym == symStr ||
+        sym == symPath ||
+        sym == symSubPath ||
+        sym == symUri ||
+        sym == symNull ||
+        sym == symInt ||
+        sym == symBool ||
+        sym == symFunction ||
+        sym == symFunction1 ||
+        sym == symAttrs ||
+        sym == symList ||
+        sym == symPrimOp)
         return e;
-
+    
     /* The `Closed' constructor is just a way to prevent substitutions
        into expressions not containing free variables. */
-    if (atMatch(m, e) >> "Closed" >> e1)
+    if (matchClosed(e, e1))
         return evalExpr(state, e1);
 
     /* Any encountered variables must be primops (since undefined
        variables are detected after parsing). */
-    if (atMatch(m, e) >> "Var" >> name) {
+    if (matchVar(e, name)) {
         ATerm primOp = state.primOps.get(name);
         if (!primOp)
             throw Error(format("impossible: undefined variable `%1%'") % name);
         int arity;
-        ATerm fun;
-        if (!(atMatch(m, primOp) >> "" >> arity >> fun)) abort();
+        ATermBlob fun;
+        if (!matchPrimOpDef(primOp, arity, fun)) abort();
         if (arity == 0)
-            return ((PrimOp) ATgetBlobData((ATermBlob) fun))
-                (state, ATermVector());
+            return ((PrimOp) ATgetBlobData(fun)) (state, ATermVector());
         else
-            return ATmake("PrimOp(<int>, <term>, <term>)",
-                arity, fun, ATempty);
+            return makePrimOp(arity, fun, ATempty);
     }
 
     /* Function application. */
-    if (atMatch(m, e) >> "Call" >> e1 >> e2) {
+    if (matchCall(e, e1, e2)) {
 
         ATermList formals;
         ATerm pos;
@@ -207,9 +192,9 @@ Expr evalExpr2(EvalState & state, Expr e)
 
         /* Is it a primop or a function? */
         int arity;
-        ATerm fun;
+        ATermBlob fun;
         ATermList args;
-        if (atMatch(m, e1) >> "PrimOp" >> arity >> fun >> args) {
+        if (matchPrimOp(e1, arity, fun, args)) {
             args = ATinsert(args, e2);
             if (ATgetLength(args) == arity) {
                 /* Put the arguments in a vector in reverse (i.e.,
@@ -221,11 +206,10 @@ Expr evalExpr2(EvalState & state, Expr e)
                     (state, args2);
             } else
                 /* Need more arguments, so propagate the primop. */
-                return ATmake("PrimOp(<int>, <term>, <term>)",
-                    arity, fun, args);
+                return makePrimOp(arity, fun, args);
         }
 
-        else if (atMatch(m, e1) >> "Function" >> formals >> e4 >> pos) {
+        else if (matchFunction(e1, formals, e4, pos)) {
             e2 = evalExpr(state, e2);
             try {
                 return evalExpr(state, substArgs(e4, formals, e2));
@@ -235,7 +219,7 @@ Expr evalExpr2(EvalState & state, Expr e)
             }
         }
         
-        else if (atMatch(m, e1) >> "Function1" >> name >> e4 >> pos) {
+        else if (matchFunction1(e1, name, e4, pos)) {
             try {
                 ATermMap subs;
                 subs.set(name, e2);
@@ -250,9 +234,9 @@ Expr evalExpr2(EvalState & state, Expr e)
     }
 
     /* Attribute selection. */
-    string s1;
-    if (atMatch(m, e) >> "Select" >> e1 >> s1) {
+    if (matchSelect(e, e1, name)) {
         ATerm pos;
+        string s1 = aterm2String(name);
         Expr a = queryAttr(evalExpr(state, e1), s1, pos);
         if (!a) throw Error(format("attribute `%1%' missing") % s1);
         try {
@@ -265,11 +249,11 @@ Expr evalExpr2(EvalState & state, Expr e)
 
     /* Mutually recursive sets. */
     ATermList rbnds, nrbnds;
-    if (atMatch(m, e) >> "Rec" >> rbnds >> nrbnds)
+    if (matchRec(e, rbnds, nrbnds))
         return expandRec(e, rbnds, nrbnds);
 
     /* Conditionals. */
-    if (atMatch(m, e) >> "If" >> e1 >> e2 >> e3) {
+    if (matchIf(e, e1, e2, e3)) {
         if (evalBool(state, e1))
             return evalExpr(state, e2);
         else
@@ -277,14 +261,14 @@ Expr evalExpr2(EvalState & state, Expr e)
     }
 
     /* Assertions. */
-    if (atMatch(m, e) >> "Assert" >> e1 >> e2 >> pos) {
+    if (matchAssert(e, e1, e2, pos)) {
         if (!evalBool(state, e1))
             throw Error(format("assertion failed at %1%") % showPos(pos));
         return evalExpr(state, e2);
     }
 
     /* Withs. */
-    if (atMatch(m, e) >> "With" >> e1 >> e2 >> pos) {
+    if (matchWith(e, e1, e2, pos)) {
         ATermMap attrs;
         try {
             e1 = evalExpr(state, e1);
@@ -304,51 +288,51 @@ Expr evalExpr2(EvalState & state, Expr e)
     }
 
     /* Generic equality. */
-    if (atMatch(m, e) >> "OpEq" >> e1 >> e2)
+    if (matchOpEq(e, e1, e2))
         return makeBool(evalExpr(state, e1) == evalExpr(state, e2));
 
     /* Generic inequality. */
-    if (atMatch(m, e) >> "OpNEq" >> e1 >> e2)
+    if (matchOpNEq(e, e1, e2))
         return makeBool(evalExpr(state, e1) != evalExpr(state, e2));
 
     /* Negation. */
-    if (atMatch(m, e) >> "OpNot" >> e1)
+    if (matchOpNot(e, e1))
         return makeBool(!evalBool(state, e1));
 
     /* Implication. */
-    if (atMatch(m, e) >> "OpImpl" >> e1 >> e2)
+    if (matchOpImpl(e, e1, e2))
         return makeBool(!evalBool(state, e1) || evalBool(state, e2));
 
     /* Conjunction (logical AND). */
-    if (atMatch(m, e) >> "OpAnd" >> e1 >> e2)
+    if (matchOpAnd(e, e1, e2))
         return makeBool(evalBool(state, e1) && evalBool(state, e2));
 
     /* Disjunction (logical OR). */
-    if (atMatch(m, e) >> "OpOr" >> e1 >> e2)
+    if (matchOpOr(e, e1, e2))
         return makeBool(evalBool(state, e1) || evalBool(state, e2));
 
     /* Attribute set update (//). */
-    if (atMatch(m, e) >> "OpUpdate" >> e1 >> e2)
+    if (matchOpUpdate(e, e1, e2))
         return updateAttrs(evalExpr(state, e1), evalExpr(state, e2));
 
     /* Attribute existence test (?). */
-    if (atMatch(m, e) >> "OpHasAttr" >> e1 >> name) {
+    if (matchOpHasAttr(e, e1, name)) {
         ATermMap attrs;
         queryAllAttrs(evalExpr(state, e1), attrs);
         return makeBool(attrs.get(name) != 0);
     }
 
     /* String or path concatenation. */
-    if (atMatch(m, e) >> "OpPlus" >> e1 >> e2) {
+    if (matchOpPlus(e, e1, e2)) {
         e1 = evalExpr(state, e1);
         e2 = evalExpr(state, e2);
-        string s1, s2;
-        if (atMatch(m, e1) >> "Str" >> s1 &&
-            atMatch(m, e2) >> "Str" >> s2)
-            return makeString(s1 + s2);
-        else if (atMatch(m, e1) >> "Path" >> s1 &&
-            atMatch(m, e2) >> "Path" >> s2)
-            return makePath(canonPath(s1 + "/" + s2));
+        ATerm s1, s2;
+        if (matchStr(e1, s1) && matchStr(e2, s2))
+            return makeStr(string2ATerm((
+                (string) aterm2String(s1) + (string) aterm2String(s2)).c_str()));
+        else if (matchPath(e1, s1) && matchPath(e2, s2))
+            return makePath(string2ATerm(canonPath(
+                (string) aterm2String(s1) + "/" + (string) aterm2String(s2)).c_str()));
         else throw Error("wrong argument types in `+' operator");
     }
 
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 37288804d0..cbfb5576bf 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -2,6 +2,10 @@
 #include "storeexpr.hh"
 
 
+#include "constructors.hh"
+#include "constructors.cc"
+
+
 ATermMap::ATermMap(unsigned int initialSize, unsigned int maxLoadPct)
 {
     this->maxLoadPct = maxLoadPct;
@@ -38,7 +42,7 @@ void ATermMap::set(ATerm key, ATerm value)
 
 void ATermMap::set(const string & key, ATerm value)
 {
-    set(string2ATerm(key), value);
+    set(string2ATerm(key.c_str()), value);
 }
 
 
@@ -50,7 +54,7 @@ ATerm ATermMap::get(ATerm key) const
 
 ATerm ATermMap::get(const string & key) const
 {
-    return get(string2ATerm(key));
+    return get(string2ATerm(key.c_str()));
 }
 
 
@@ -62,7 +66,7 @@ void ATermMap::remove(ATerm key)
 
 void ATermMap::remove(const string & key)
 {
-    remove(string2ATerm(key));
+    remove(string2ATerm(key.c_str()));
 }
 
 
@@ -94,28 +98,14 @@ void ATermMap::reset()
 }
 
 
-ATerm string2ATerm(const string & s)
-{
-    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s.c_str(), 0, ATtrue));
-}
-
-
-string aterm2String(ATerm t)
-{
-    return ATgetName(ATgetAFun(t));
-}
-
-
 string showPos(ATerm pos)
 {
-    ATMatcher m;
-    Path path;
+    ATerm path;
     int line, column;
-    if (atMatch(m, pos) >> "NoPos")
-        return "undefined position";
-    if (!(atMatch(m, pos) >> "Pos" >> path >> line >> column))
+    if (matchNoPos(pos)) return "undefined position";
+    if (!matchPos(pos, path, line, column))
         throw badTerm("position expected", pos);
-    return (format("`%1%', line %2%") % path % line).str();
+    return (format("`%1%', line %2%") % aterm2String(path) % line).str();
 }
     
 
@@ -150,18 +140,16 @@ ATerm bottomupRewrite(TermFun & f, ATerm e)
 
 void queryAllAttrs(Expr e, ATermMap & attrs, bool withPos)
 {
-    ATMatcher m;
     ATermList bnds;
-    if (!(atMatch(m, e) >> "Attrs" >> bnds))
+    if (!matchAttrs(e, bnds))
         throw Error("attribute set expected");
 
     for (ATermIterator i(bnds); i; ++i) {
-        string s;
+        ATerm name;
         Expr e;
         ATerm pos;
-        if (!(atMatch(m, *i) >> "Bind" >> s >> e >> pos))
-            abort(); /* can't happen */
-        attrs.set(s, withPos ? ATmake("(<term>, <term>)", e, pos) : e);
+        if (!matchBind(*i, name, e, pos)) abort(); /* can't happen */
+        attrs.set(name, withPos ? makeAttrRHS(e, pos) : e);
     }
 }
 
@@ -175,18 +163,16 @@ Expr queryAttr(Expr e, const string & name)
 
 Expr queryAttr(Expr e, const string & name, ATerm & pos)
 {
-    ATMatcher m;
     ATermList bnds;
-    if (!(atMatch(m, e) >> "Attrs" >> bnds))
+    if (!matchAttrs(e, bnds))
         throw Error("attribute set expected");
 
     for (ATermIterator i(bnds); i; ++i) {
-        string s;
+        ATerm name2, pos2;
         Expr e;
-        ATerm pos2;
-        if (!(atMatch(m, *i) >> "Bind" >> s >> e >> pos2))
+        if (!matchBind(*i, name2, e, pos2))
             abort(); /* can't happen */
-        if (s == name) {
+        if (aterm2String(name2) == name) {
             pos = pos2;
             return e;
         }
@@ -198,17 +184,15 @@ Expr queryAttr(Expr e, const string & name, ATerm & pos)
 
 Expr makeAttrs(const ATermMap & attrs)
 {
-    ATMatcher m;
     ATermList bnds = ATempty;
     for (ATermIterator i(attrs.keys()); i; ++i) {
         Expr e;
         ATerm pos;
-        if (!(atMatch(m, attrs.get(*i)) >> "" >> e >> pos))
+        if (!matchAttrRHS(attrs.get(*i), e, pos))
             abort(); /* can't happen */
-        bnds = ATinsert(bnds, 
-            ATmake("Bind(<term>, <term>, <term>)", *i, e, pos));
+        bnds = ATinsert(bnds, makeBind(*i, e, pos));
     }
-    return ATmake("Attrs(<term>)", ATreverse(bnds));
+    return makeAttrs(ATreverse(bnds));
 }
 
 
@@ -216,57 +200,53 @@ Expr substitute(const ATermMap & subs, Expr e)
 {
     checkInterrupt();
 
-    ATMatcher m;
-    ATerm name, pos;
+    ATerm name, pos, e2;
 
     /* As an optimisation, don't substitute in subterms known to be
        closed. */
-    if (atMatch(m, e) >> "Closed") return e;
+    if (matchClosed(e, e2)) return e;
 
-    if (atMatch(m, e) >> "Var" >> name) {
+    if (matchVar(e, name)) {
         Expr sub = subs.get(name);
-        return sub ? ATmake("Closed(<term>)", sub) : e;
+        return sub ? makeClosed(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 >> pos) {
+    ATerm body, def;
+    if (matchFunction(e, formals, body, pos)) {
         ATermMap subs2(subs);
         for (ATermIterator i(formals); i; ++i) {
-            if (!(atMatch(m, *i) >> "NoDefFormal" >> name) &&
-                !(atMatch(m, *i) >> "DefFormal" >> name))
+            if (!matchNoDefFormal(*i, name) &&
+                !matchDefFormal(*i, name, def))
                 abort();
             subs2.remove(name);
         }
-        return ATmake("Function(<term>, <term>, <term>)",
-            substitute(subs, (ATerm) formals),
+        return makeFunction(
+            (ATermList) substitute(subs, (ATerm) formals),
             substitute(subs2, body), pos);
     }
 
-    if (atMatch(m, e) >> "Function1" >> name >> body >> pos) {
+    if (matchFunction1(e, name, body, pos)) {
         ATermMap subs2(subs);
         subs2.remove(name);
-        return ATmake("Function1(<term>, <term>, <term>)", name,
-            substitute(subs2, body), pos);
+        return makeFunction1(name, substitute(subs2, body), pos);
     }
         
     /* Idem for a mutually recursive attribute set. */
     ATermList rbnds, nrbnds;
-    if (atMatch(m, e) >> "Rec" >> rbnds >> nrbnds) {
+    if (matchRec(e, rbnds, nrbnds)) {
         ATermMap subs2(subs);
         for (ATermIterator i(rbnds); i; ++i)
-            if (atMatch(m, *i) >> "Bind" >> name)
-                subs2.remove(name);
+            if (matchBind(*i, name, e2, pos)) subs2.remove(name);
             else abort(); /* can't happen */
         for (ATermIterator i(nrbnds); i; ++i)
-            if (atMatch(m, *i) >> "Bind" >> name)
-                subs2.remove(name);
+            if (matchBind(*i, name, e2, pos)) subs2.remove(name);
             else abort(); /* can't happen */
-        return ATmake("Rec(<term>, <term>)",
-            substitute(subs2, (ATerm) rbnds),
-            substitute(subs, (ATerm) nrbnds));
+        return makeRec(
+            (ATermList) substitute(subs2, (ATerm) rbnds),
+            (ATermList) substitute(subs, (ATerm) nrbnds));
     }
 
     if (ATgetType(e) == AT_APPL) {
@@ -293,24 +273,23 @@ Expr substitute(const ATermMap & subs, Expr e)
 
 void checkVarDefs(const ATermMap & defs, Expr e)
 {
-    ATMatcher m;
-    ATerm name;
+    ATerm name, pos, value;
     ATermList formals;
     ATerm with, body;
     ATermList rbnds, nrbnds;
 
-    if (atMatch(m, e) >> "Var" >> name) {
+    if (matchVar(e, name)) {
         if (!defs.get(name))
             throw Error(format("undefined variable `%1%'")
                 % aterm2String(name));
     }
 
-    else if (atMatch(m, e) >> "Function" >> formals >> body) {
+    else if (matchFunction(e, formals, body, pos)) {
         ATermMap defs2(defs);
         for (ATermIterator i(formals); i; ++i) {
             Expr deflt;
-            if (!(atMatch(m, *i) >> "NoDefFormal" >> name))
-                if (atMatch(m, *i) >> "DefFormal" >> name >> deflt)
+            if (!matchNoDefFormal(*i, name))
+                if (matchDefFormal(*i, name, deflt))
                     checkVarDefs(defs, deflt);
                 else
                     abort();
@@ -319,29 +298,27 @@ void checkVarDefs(const ATermMap & defs, Expr e)
         checkVarDefs(defs2, body);
     }
         
-    else if (atMatch(m, e) >> "Function1" >> name >> body) {
+    else if (matchFunction1(e, name, body, pos)) {
         ATermMap defs2(defs);
         defs2.set(name, (ATerm) ATempty);
         checkVarDefs(defs2, body);
     }
         
-    else if (atMatch(m, e) >> "Rec" >> rbnds >> nrbnds) {
+    else if (matchRec(e, rbnds, nrbnds)) {
         checkVarDefs(defs, (ATerm) nrbnds);
         ATermMap defs2(defs);
         for (ATermIterator i(rbnds); i; ++i) {
-            if (!(atMatch(m, *i) >> "Bind" >> name))
-                abort(); /* can't happen */
+            if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
             defs2.set(name, (ATerm) ATempty);
         }
         for (ATermIterator i(nrbnds); i; ++i) {
-            if (!(atMatch(m, *i) >> "Bind" >> name))
-                abort(); /* can't happen */
+            if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
             defs2.set(name, (ATerm) ATempty);
         }
         checkVarDefs(defs2, (ATerm) rbnds);
     }
 
-    else if (atMatch(m, e) >> "With" >> with >> body) {
+    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'. */
@@ -362,17 +339,5 @@ void checkVarDefs(const ATermMap & defs, Expr e)
 
 Expr makeBool(bool b)
 {
-    return b ? ATmake("Bool(True)") : ATmake("Bool(False)");
-}
-
-
-Expr makeString(const string & s)
-{
-    return ATmake("Str(<str>)", s.c_str());
-}
-
-
-Expr makePath(const Path & path)
-{
-    return ATmake("Path(<str>)", path.c_str());
+    return b ? eTrue : eFalse;
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 657e6055c4..9c49751c7d 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -13,6 +13,8 @@
    normals forms efficiently. */
 typedef ATerm Expr;
 
+typedef ATerm Pos;
+
 
 /* Mappings from ATerms to ATerms.  This is just a wrapper around
    ATerm tables. */
@@ -53,11 +55,6 @@ private:
 typedef vector<ATerm> ATermVector;
 
 
-/* Convert a string to an ATerm (i.e., a quoted nullary function
-   applicaton). */
-ATerm string2ATerm(const string & s);
-string aterm2String(ATerm t);
-
 /* Show a position. */
 string showPos(ATerm pos);
 
diff --git a/src/libexpr/parser.cc b/src/libexpr/parser.cc
index 763faacf7b..a0a6c01df7 100644
--- a/src/libexpr/parser.cc
+++ b/src/libexpr/parser.cc
@@ -7,6 +7,7 @@
 
 #include "aterm.hh"
 #include "parser.hh"
+#include "constructors.hh"
 
 
 struct ParseData 
@@ -45,28 +46,24 @@ void parseError(ParseData * data, char * error, int line, int column)
         
 ATerm fixAttrs(int recursive, ATermList as)
 {
-    ATMatcher m;
     ATermList bs = ATempty, cs = ATempty;
     ATermList * is = recursive ? &cs : &bs;
     for (ATermIterator i(as); i; ++i) {
         ATermList names;
         Expr src;
         ATerm pos;
-        if (atMatch(m, *i) >> "Inherit" >> src >> names >> pos) {
-            bool fromScope = atMatch(m, src) >> "Scope";
+        if (matchInherit(*i, src, names, pos)) {
+            bool fromScope = matchScope(src);
             for (ATermIterator j(names); j; ++j) {
-                Expr rhs = fromScope
-                    ? ATmake("Var(<term>)", *j)
-                    : ATmake("Select(<term>, <term>)", src, *j);
-                *is = ATinsert(*is, ATmake("Bind(<term>, <term>, <term>)",
-                                   *j, rhs, pos));
+                Expr rhs = fromScope ? makeVar(*j) : makeSelect(src, *j);
+                *is = ATinsert(*is, makeBind(*j, rhs, pos));
             }
         } else bs = ATinsert(bs, *i);
     }
     if (recursive)
-        return ATmake("Rec(<term>, <term>)", bs, cs);
+        return makeRec(bs, cs);
     else
-        return ATmake("Attrs(<term>)", bs);
+        return makeAttrs(bs);
 }
 
 const char * getPath(ParseData * data)
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index c56d89809f..2864b1600e 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -15,6 +15,11 @@
 #include "parser-tab.h"
 #include "lexer-tab.h"
 
+typedef ATerm Expr;
+typedef ATerm Pos;
+    
+#include "constructors.hh"
+
 void setParseResult(void * data, ATerm t);
 void parseError(void * data, char * error, int line, int column);
 ATerm absParsedPath(void * data, ATerm t);
@@ -26,13 +31,13 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, void * data, char * s)
     parseError(data, s, loc->first_line, loc->first_column);
 }
 
-ATerm makePos(YYLTYPE * loc, void * data)
+static Pos makeCurPos(YYLTYPE * loc, void * data)
 {
-    return ATmake("Pos(<str>, <int>, <int>)",
-        getPath(data), loc->first_line, loc->first_column);
+    return makePos(string2ATerm(getPath(data)),
+        loc->first_line, loc->first_column);
 }
 
-#define CUR_POS makePos(yylocp, data)
+#define CUR_POS makeCurPos(yylocp, data)
  
 %}
 
@@ -65,64 +70,64 @@ expr: expr_function;
 
 expr_function
   : '{' formals '}' ':' expr_function
-    { $$ = ATmake("Function(<term>, <term>, <term>)", $2, $5, CUR_POS); }
+    { $$ = makeFunction($2, $5, CUR_POS); }
   | ID ':' expr_function
-    { $$ = ATmake("Function1(<term>, <term>, <term>)", $1, $3, CUR_POS); }
+    { $$ = makeFunction1($1, $3, CUR_POS); }
   | ASSERT expr ';' expr_function
-    { $$ = ATmake("Assert(<term>, <term>, <term>)", $2, $4, CUR_POS); }
+    { $$ = makeAssert($2, $4, CUR_POS); }
   | WITH expr ';' expr_function
-    { $$ = ATmake("With(<term>, <term>, <term>)", $2, $4, CUR_POS); }
+    { $$ = makeWith($2, $4, CUR_POS); }
   | expr_if
   ;
 
 expr_if
   : IF expr THEN expr ELSE expr
-    { $$ = ATmake("If(<term>, <term>, <term>)", $2, $4, $6); }
+    { $$ = makeIf($2, $4, $6); }
   | expr_op
   ;
 
 expr_op
-  : '!' expr_op %prec NEG { $$ = ATmake("OpNot(<term>)", $2); }
-  | expr_op EQ expr_op { $$ = ATmake("OpEq(<term>, <term>)", $1, $3); }
-  | expr_op NEQ expr_op { $$ = ATmake("OpNEq(<term>, <term>)", $1, $3); }
-  | expr_op AND expr_op { $$ = ATmake("OpAnd(<term>, <term>)", $1, $3); }
-  | expr_op OR expr_op { $$ = ATmake("OpOr(<term>, <term>)", $1, $3); }
-  | expr_op IMPL expr_op { $$ = ATmake("OpImpl(<term>, <term>)", $1, $3); }
-  | expr_op UPDATE expr_op { $$ = ATmake("OpUpdate(<term>, <term>)", $1, $3); }
-  | expr_op '~' expr_op { $$ = ATmake("SubPath(<term>, <term>)", $1, $3); }
-  | expr_op '?' ID { $$ = ATmake("OpHasAttr(<term>, <term>)", $1, $3); }
-  | expr_op '+' expr_op { $$ = ATmake("OpPlus(<term>, <term>)", $1, $3); }
+  : '!' 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_app
   ;
 
 expr_app
   : expr_app expr_select
-    { $$ = ATmake("Call(<term>, <term>)", $1, $2); }
+    { $$ = makeCall($1, $2); }
   | expr_select { $$ = $1; }
   ;
 
 expr_select
   : expr_select '.' ID
-    { $$ = ATmake("Select(<term>, <term>)", $1, $3); }
+    { $$ = makeSelect($1, $3); }
   | expr_simple { $$ = $1; }
   ;
 
 expr_simple
-  : ID { $$ = ATmake("Var(<term>)", $1); }
-  | INT { $$ = ATmake("Int(<term>)", $1); }
-  | STR { $$ = ATmake("Str(<term>)", $1); }
-  | PATH { $$ = ATmake("Path(<term>)", absParsedPath(data, $1)); }
-  | URI { $$ = ATmake("Uri(<term>)", $1); }
+  : ID { $$ = makeVar($1); }
+  | INT { $$ = makeInt(ATgetInt((ATermInt) $1)); }
+  | STR { $$ = makeStr($1); }
+  | PATH { $$ = makePath(absParsedPath(data, $1)); }
+  | URI { $$ = makeUri($1); }
   | '(' expr ')' { $$ = $2; }
   /* Let expressions `let {..., body = ...}' are just desugared
      into `(rec {..., body = ...}).body'. */
   | LET '{' binds '}'
-    { $$ = ATmake("Select(<term>, \"body\")", fixAttrs(1, $3)); }
+    { $$ = makeSelect(fixAttrs(1, $3), string2ATerm("body")); }
   | REC '{' binds '}'
     { $$ = fixAttrs(1, $3); }
   | '{' binds '}'
     { $$ = fixAttrs(0, $2); }
-  | '[' expr_list ']' { $$ = ATmake("List(<term>)", $2); }
+  | '[' expr_list ']' { $$ = makeList($2); }
   ;
 
 binds
@@ -132,14 +137,14 @@ binds
 
 bind
   : ID '=' expr ';'
-    { $$ = ATmake("Bind(<term>, <term>, <term>)", $1, $3, CUR_POS); }
+    { $$ = makeBind($1, $3, CUR_POS); }
   | INHERIT inheritsrc ids ';'
-    { $$ = ATmake("Inherit(<term>, <term>, <term>)", $2, $3, CUR_POS); }
+    { $$ = makeInherit($2, $3, CUR_POS); }
   ;
 
 inheritsrc
   : '(' expr ')' { $$ = $2; }
-  | { $$ = ATmake("Scope"); }
+  | { $$ = makeScope(); }
   ;
 
 ids: ids ID { $$ = ATinsert($1, $2); } | { $$ = ATempty; };
@@ -158,8 +163,8 @@ formals
   ;
 
 formal
-  : ID { $$ = ATmake("NoDefFormal(<term>)", $1); }
-  | ID '?' expr { $$ = ATmake("DefFormal(<term>, <term>)", $1, $3); }
+  : ID { $$ = makeNoDefFormal($1); }
+  | ID '?' expr { $$ = makeDefFormal($1, $3); }
   ;
   
 %%
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index a51a5119af..e230d35ce6 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1,18 +1,18 @@
 #include "normalise.hh"
 #include "eval.hh"
 #include "globals.hh"
+#include "constructors.hh"
 
 
 /* Load and evaluate an expression from path specified by the
    argument. */ 
 static Expr primImport(EvalState & state, const ATermVector & args)
 {
-    ATMatcher m;
-    string path;
+    ATerm path;
     Expr fn = evalExpr(state, args[0]);
-    if (!(atMatch(m, fn) >> "Path" >> path))
+    if (!matchPath(fn, path))
         throw Error("path expected");
-    return evalFile(state, path);
+    return evalFile(state, aterm2String(path));
 }
 
 
@@ -86,24 +86,23 @@ static void processBinding(EvalState & state, Expr e, StoreExpr & ne,
 {
     e = evalExpr(state, e);
 
-    ATMatcher m;
-    string s;
+    ATerm s;
     ATermList es;
     int n;
     Expr e1, e2;
 
-    if (atMatch(m, e) >> "Str" >> s) ss.push_back(s);
-    else if (atMatch(m, e) >> "Uri" >> s) ss.push_back(s);
-    else if (atMatch(m, e) >> "Bool" >> "True") ss.push_back("1");
-    else if (atMatch(m, e) >> "Bool" >> "False") ss.push_back("");
+    if (matchStr(e, s)) ss.push_back(aterm2String(s));
+    else if (matchUri(e, s)) ss.push_back(aterm2String(s));
+    else if (e == eTrue) ss.push_back("1");
+    else if (e == eFalse) ss.push_back("");
 
-    else if (atMatch(m, e) >> "Int" >> n) {
+    else if (matchInt(e, n)) {
         ostringstream st;
         st << n;
         ss.push_back(st.str());
     }
 
-    else if (atMatch(m, e) >> "Attrs") {
+    else if (matchAttrs(e, es)) {
         Expr a = queryAttr(e, "type");
         if (a && evalString(state, a) == "derivation") {
             a = queryAttr(e, "drvPath");
@@ -127,30 +126,29 @@ static void processBinding(EvalState & state, Expr e, StoreExpr & ne,
             throw Error("invalid derivation attribute");
     }
 
-    else if (atMatch(m, e) >> "Path" >> s) {
-        Path drvPath = copyAtom(state, s);
+    else if (matchPath(e, s)) {
+        Path drvPath = copyAtom(state, aterm2String(s));
         ss.push_back(addInput(state, drvPath, ne));
     }
     
-    else if (atMatch(m, e) >> "List" >> es) {
+    else if (matchList(e, es)) {
         for (ATermIterator i(es); i; ++i) {
             startNest(nest, lvlVomit, format("processing list element"));
 	    processBinding(state, evalExpr(state, *i), ne, ss);
         }
     }
 
-    else if (atMatch(m, e) >> "Null") ss.push_back("");
+    else if (matchNull(e)) ss.push_back("");
 
-    else if (atMatch(m, e) >> "SubPath" >> e1 >> e2) {
+    else if (matchSubPath(e, e1, e2)) {
         Strings ss2;
         processBinding(state, evalExpr(state, e1), ne, ss2);
         if (ss2.size() != 1)
             throw Error("left-hand side of `~' operator cannot be a list");
         e2 = evalExpr(state, e2);
-        if (!(atMatch(m, e2) >> "Str" >> s ||
-             (atMatch(m, e2) >> "Path" >> s)))
+        if (!(matchStr(e2, s) || matchPath(e2, s)))
             throw Error("right-hand side of `~' operator must be a path or string");
-        ss.push_back(canonPath(ss2.front() + "/" + s));
+        ss.push_back(canonPath(ss2.front() + "/" + aterm2String(s)));
     }
     
     else throw Error("invalid derivation attribute");
@@ -198,8 +196,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
         ATerm value;
         Expr pos;
         ATerm rhs = attrs.get(key);
-        ATMatcher m;
-        if (!(atMatch(m, rhs) >> "" >> value >> pos)) abort();
+        if (!matchAttrRHS(rhs, value, pos)) abort();
         startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
 
         Strings ss;
@@ -272,10 +269,11 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
     printMsg(lvlChatty, format("instantiated `%1%' -> `%2%'")
         % drvName % drvPath);
 
-    attrs.set("outPath", ATmake("(Path(<str>), NoPos)", outPath.c_str()));
-    attrs.set("drvPath", ATmake("(Path(<str>), NoPos)", drvPath.c_str()));
-    attrs.set("drvHash", ATmake("(<term>, NoPos)", makeString(drvHash)));
-    attrs.set("type", ATmake("(<term>, NoPos)", makeString("derivation")));
+    attrs.set("outPath", makeAttrRHS(makePath(string2ATerm(outPath.c_str())), makeNoPos()));
+    attrs.set("drvPath", makeAttrRHS(makePath(string2ATerm(drvPath.c_str())), makeNoPos()));
+    attrs.set("drvHash",
+        makeAttrRHS(makeStr(string2ATerm(((string) drvHash).c_str())), makeNoPos()));
+    attrs.set("type", makeAttrRHS(makeStr(string2ATerm("derivation")), makeNoPos()));
 
     return makeAttrs(attrs);
 }
@@ -285,7 +283,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
    following the last slash. */
 static Expr primBaseNameOf(EvalState & state, const ATermVector & args)
 {
-    return makeString(baseNameOf(evalString(state, args[0])));
+    return makeStr(string2ATerm(baseNameOf(evalString(state, args[0])).c_str()));
 }
 
 
@@ -293,12 +291,9 @@ static Expr primBaseNameOf(EvalState & state, const ATermVector & args)
 static Expr primToString(EvalState & state, const ATermVector & args)
 {
     Expr arg = evalExpr(state, args[0]);
-    ATMatcher m;
-    string s;
-    if (atMatch(m, arg) >> "Str" >> s ||
-        atMatch(m, arg) >> "Path" >> s ||
-        atMatch(m, arg) >> "Uri" >> s)
-        return makeString(s);
+    ATerm s;
+    if (matchStr(arg, s) || matchPath(arg, s) || matchUri(arg, s))
+        return makeStr(s);
     else throw Error("cannot coerce value to string");
 }
 
@@ -306,29 +301,27 @@ static Expr primToString(EvalState & state, const ATermVector & args)
 /* Boolean constructors. */
 static Expr primTrue(EvalState & state, const ATermVector & args)
 {
-    return ATmake("Bool(True)");
+    return eTrue;
 }
 
 
 static Expr primFalse(EvalState & state, const ATermVector & args)
 {
-    return ATmake("Bool(False)");
+    return eFalse;
 }
 
 
 /* Return the null value. */
 Expr primNull(EvalState & state, const ATermVector & args)
 {
-    return ATmake("Null");
+    return makeNull();
 }
 
 
 /* Determine whether the argument is the null value. */
 Expr primIsNull(EvalState & state, const ATermVector & args)
 {
-    Expr arg = evalExpr(state, args[0]);
-    ATMatcher m;
-    return makeBool(atMatch(m, arg) >> "Null");
+    return makeBool(matchNull(evalExpr(state, args[0])));
 }
 
 
@@ -338,18 +331,15 @@ Expr primMap(EvalState & state, const ATermVector & args)
     Expr fun = evalExpr(state, args[0]);
     Expr list = evalExpr(state, args[1]);
 
-    ATMatcher m;
-
     ATermList list2;
-    if (!(atMatch(m, list) >> "List" >> list2))
+    if (!matchList(list, list2))
         throw Error("`map' expects a list as its second argument");
 
     ATermList list3 = ATempty;
     for (ATermIterator i(list2); i; ++i)
-        list3 = ATinsert(list3,
-            ATmake("Call(<term>, <term>)", fun, *i));
+        list3 = ATinsert(list3, makeCall(fun, *i));
 
-    return ATmake("List(<term>)", ATreverse(list3));
+    return makeList(ATreverse(list3));
 }
 
 
diff --git a/src/nix-env/main.cc b/src/nix-env/main.cc
index 213082bdc7..f87c413126 100644
--- a/src/nix-env/main.cc
+++ b/src/nix-env/main.cc
@@ -6,6 +6,7 @@
 #include "parser.hh"
 #include "eval.hh"
 #include "help.txt.hh"
+#include "constructors.hh"
 
 #include <cerrno>
 #include <ctime>
@@ -47,10 +48,9 @@ void printHelp()
 
 bool parseDerivation(EvalState & state, Expr e, DrvInfo & drv)
 {
-    ATMatcher m;
-    
+    ATermList es;
     e = evalExpr(state, e);
-    if (!(atMatch(m, e) >> "Attrs")) return false;
+    if (!matchAttrs(e, es)) return false;
     Expr a = queryAttr(e, "type");
     if (!a || evalString(state, a) != "derivation") return false;
 
@@ -82,7 +82,6 @@ bool parseDerivation(EvalState & state, Expr e, DrvInfo & drv)
 
 bool parseDerivations(EvalState & state, Expr e, DrvInfos & drvs)
 {
-    ATMatcher m;
     ATermList es;
     DrvInfo drv;
 
@@ -91,7 +90,7 @@ bool parseDerivations(EvalState & state, Expr e, DrvInfos & drvs)
     if (parseDerivation(state, e, drv)) 
         drvs[drv.drvPath] = drv;
 
-    else if (atMatch(m, e) >> "Attrs") {
+    else if (matchAttrs(e, es)) {
         ATermMap drvMap;
         queryAllAttrs(e, drvMap);
         for (ATermIterator i(drvMap.keys()); i; ++i) {
@@ -103,7 +102,7 @@ bool parseDerivations(EvalState & state, Expr e, DrvInfos & drvs)
         }
     }
 
-    else if (atMatch(m, e) >> "List" >> es) {
+    else if (matchList(e, es)) {
         for (ATermIterator i(es); i; ++i) {
             debug(format("evaluating list element"));
             if (parseDerivation(state, *i, drv))
@@ -152,12 +151,10 @@ struct AddPos : TermFun
 {
     ATerm operator () (ATerm e)
     {
-        ATMatcher m;
         ATerm x, y, z;
-        if (atMatch(m, e) >> "Bind" >> x >> y >> z)
-            return e;
-        if (atMatch(m, e) >> "Bind" >> x >> y)
-            return ATmake("Bind(<term>, <term>, NoPos)", x, y);
+        if (matchBind(e, x, y, z)) return e;
+        if (matchBind2(e, x, y))
+            return makeBind(x, y, makeNoPos());
         return e;
     }
 };
@@ -194,36 +191,36 @@ void createUserEnv(EvalState & state, const DrvInfos & drvs,
     for (DrvInfos::const_iterator i = drvs.begin(); 
          i != drvs.end(); ++i)
     {
-        ATerm t = ATmake(
-            "Attrs(["
-            "Bind(\"type\", Str(\"derivation\"), NoPos), "
-            "Bind(\"name\", Str(<str>), NoPos), "
-            "Bind(\"system\", Str(<str>), NoPos), "
-            "Bind(\"drvPath\", Path(<str>), NoPos), "
-            "Bind(\"drvHash\", Str(<str>), NoPos), "
-            "Bind(\"outPath\", Path(<str>), NoPos)"
-            "])",
-            i->second.name.c_str(),
-            i->second.system.c_str(),
-            i->second.drvPath.c_str(),
-            ((string) i->second.drvHash).c_str(),
-            i->second.outPath.c_str());
+        ATerm t = makeAttrs(ATmakeList6(
+            makeBind(string2ATerm("type"),
+                makeStr(string2ATerm("derivation")), makeNoPos()),
+            makeBind(string2ATerm("name"),
+                makeStr(string2ATerm(i->second.name.c_str())), makeNoPos()),
+            makeBind(string2ATerm("system"),
+                makeStr(string2ATerm(i->second.system.c_str())), makeNoPos()),
+            makeBind(string2ATerm("drvPath"),
+                makePath(string2ATerm(i->second.drvPath.c_str())), makeNoPos()),
+            makeBind(string2ATerm("drvHash"),
+                makeStr(string2ATerm(((string) i->second.drvHash).c_str())), makeNoPos()),
+            makeBind(string2ATerm("outPath"),
+                makePath(string2ATerm(i->second.outPath.c_str())), makeNoPos())
+            ));
         inputs = ATinsert(inputs, t);
     }
 
-    ATerm inputs2 = ATmake("List(<term>)", ATreverse(inputs));
+    ATerm inputs2 = makeList(ATreverse(inputs));
 
     /* Also write a copy of the list of inputs to the store; we need
        it for future modifications of the environment. */
     Path inputsFile = writeTerm(inputs2, "-env-inputs");
 
-    Expr topLevel = ATmake(
-        "Call(<term>, Attrs(["
-        "Bind(\"system\", Str(<str>), NoPos), "
-        "Bind(\"derivations\", <term>, NoPos), " // !!! redundant
-        "Bind(\"manifest\", Path(<str>), NoPos)"
-        "]))",
-        envBuilder, thisSystem.c_str(), inputs2, inputsFile.c_str());
+    Expr topLevel = makeCall(envBuilder, makeAttrs(ATmakeList3(
+        makeBind(string2ATerm("system"),
+            makeStr(string2ATerm(thisSystem.c_str())), makeNoPos()),
+        makeBind(string2ATerm("derivations"), inputs2, makeNoPos()),
+        makeBind(string2ATerm("manifest"),
+            makePath(string2ATerm(inputsFile.c_str())), makeNoPos())
+        )));
 
     /* Instantiate it. */
     debug(format("evaluating builder expression `%1%'") % topLevel);
diff --git a/src/nix-instantiate/main.cc b/src/nix-instantiate/main.cc
index e396be5ff2..907f7257a4 100644
--- a/src/nix-instantiate/main.cc
+++ b/src/nix-instantiate/main.cc
@@ -6,6 +6,7 @@
 #include "shared.hh"
 #include "eval.hh"
 #include "parser.hh"
+#include "constructors.hh"
 #include "help.txt.hh"
 
 
@@ -32,7 +33,7 @@ static void printDrvPaths(EvalState & state, Expr e)
 
     /* !!! duplication w.r.t. parseDerivations in nix-env */
 
-    if (atMatch(m, e) >> "Attrs" >> es) {
+    if (matchAttrs(e, es)) {
         Expr a = queryAttr(e, "type");
         if (a && evalString(state, a) == "derivation") {
             a = queryAttr(e, "drvPath");
@@ -50,7 +51,7 @@ static void printDrvPaths(EvalState & state, Expr e)
         }
     }
 
-    if (atMatch(m, e) >> "List" >> es) {
+    if (matchList(e, es)) {
         for (ATermIterator i(es); i; ++i)
             printDrvPaths(state, evalExpr(state, *i));
         return;