Commit: 50462950c7e62a96aae777ca2ede6eb5dd1f3244 - regiux (git)

A fast implementation of the Nix expression language

Commit MetaInfo

• Revision: 50462950c7e62a96aae777ca2ede6eb5dd1f3244 (tree)
• Time: 2024-06-14 11:11:02
• Author: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

Get 2 + 2 working again.

The supercombinator preparation will be the hard part. Not tricky, just
a lot of work.

Change Summary

• modified: README.txt
• modified: gmachine.py
• modified: main.py
• modified: parser.py
• modified: todo.txt

Incremental Difference

--- a/README.txt
+++ b/README.txt
@@ -1 +1,11 @@
 This is a basic parser for the Nix language.
+
+## Bibliography
+
+### G-Machine
+
+These posts were helpful for disentangling some of the weirder parts:
+
+* https://amelia.how/posts/the-gmachine-in-detail.html
+* https://www.moonbitlang.com/docs/examples/gmachine-1
+* https://www.moonbitlang.com/docs/examples/gmachine-2

--- a/gmachine.py
+++ b/gmachine.py
@@ -5,18 +5,29 @@
 # Quirks:
 # 0) The instruction at PC 0 is always UNWIND, to ease EVAL.
 
-from heap import HeapApp
+from heap import HeapAction, HeapBinary, HeapApp, HeapAttrSet, WrongType
 
-OUTER, CONST, LOCAL, ARG, PRIM, MKAP, SLIDE, COND, EVAL, UNWIND = range(10)
+INSTRUCTIONS = [
+    # Core G-machine operations.
+    "outer", "const", "local", "arg", "prim", "mkApp", "slide", "cond", "eval", "unwind",
+    # Nix-specific operations.
+    "selectAttr",
+]
+globals().update({inst.upper(): i for i, inst in enumerate(INSTRUCTIONS)})
 
 class StackUnderflow(Exception): pass
 class Overapplied(Exception): pass
 
+def getArg(app):
+    if not isinstance(app, HeapApp): raise Overapplied()
+    return app.x
+
 class G(object):
-    _immutable_attrs_ = "code[*]", "consts[*]"
-    def __init__(self, code, consts):
+    _immutable_attrs_ = "code[*]", "consts[*]", "attrs[*]"
+    def __init__(self, code, consts, attrs):
         self.code = code
         self.consts = consts
+        self.attrs = attrs
 
     def run(self, outers):
         stack = []
@@ -25,6 +36,8 @@ class G(object):
         pc = 1
         while pc < len(self.code):
             inst = self.code[pc]
+            print "Stack:", stack
+            print "PC:", pc, "Inst:", INSTRUCTIONS[inst]
             pc += 1
             if inst == OUTER:
                 stack.append(outers[self.code[pc]])
@@ -39,11 +52,12 @@ class G(object):
             elif inst == ARG:
                 i = len(stack) - self.code[pc]
                 pc += 1
-                node = stack[i]
-                if not isinstance(node, HeapApp): raise Overapplied()
-                stack.append(node.f)
+                stack.append(getArg(stack[i]))
             elif inst == PRIM: assert False
-            elif inst == MKAP: stack.append(HeapApp(stack.pop(), stack.pop()))
+            elif inst == MKAPP:
+                x = stack.pop()
+                f = stack.pop()
+                stack.append(HeapApp(f, x))
             elif inst == SLIDE:
                 top = stack.pop()
                 stop = len(stack) - self.code[pc]
@@ -58,10 +72,37 @@ class G(object):
                 stack = [top]
                 pc = 0
             elif inst == UNWIND:
-                while isinstance(stack[-1], HeapApp): stack.append(stack[-1].f)
-                # XXX supercombinators
-                if dump: stack, pc = dump.pop()
-                else: return stack.pop()
+                top = stack.pop()
+                print "Unwinding:", top
+                while isinstance(top, HeapApp):
+                    print "App:", top, "->", top.f
+                    stack.append(top)
+                    top = top.f
+                print "Unwound stack:", stack
+                # XXX supercombinators too!
+                if isinstance(top, HeapAction):
+                    if len(stack) < 1: return top
+                    print "Unary op:", top, stack[-1]
+                    x = getArg(stack.pop())
+                    top = top.action(x)
+                    stack.append(top)
+                elif isinstance(top, HeapBinary):
+                    if len(stack) < 2: return top
+                    print "Binary op:", top, stack[-1], stack[-2]
+                    x = getArg(stack.pop())
+                    y = getArg(stack.pop())
+                    top = top.action(x, y)
+                    stack.append(top)
+                elif dump:
+                    print "Dump pop", pc, "->",
+                    stack, pc = dump.pop()
+                    print pc
+                    stack.append(top)
+                else: return top
+            elif inst == SELECTATTR:
+                top = stack.pop()
+                stack.append(top.getAttr(self.attrs[self.code[pc]]))
+                pc += 1
             else:
                 print "Unknown bytecode:", inst
                 assert False
@@ -81,10 +122,10 @@ class Compiler(object):
         self.code = [UNWIND]
         self.consts = []
         self.locals = []
+        self.attrs = []
 
     def outer(self, name):
-        try:
-            i = self.scope.index(name)
+        try: i = self.scope.index(name)
         except ValueError: raise MissingVar(name)
         else:
             self.code.append(OUTER)
@@ -106,11 +147,43 @@ class Compiler(object):
         self.code.append(ARG)
         self.code.append(i)
 
-    def mkAp(self): self.code.append(MKAP)
-
     def slide(self, i):
         assert i >= 0, "implementation error"
         self.code.append(SLIDE)
         self.code.append(i)
 
-    def finish(self): return G(self.code[:], self.consts[:])
+    def mkApp(self): self.code.append(MKAPP)
+    def unwind(self): self.code.append(UNWIND)
+
+    def selectAttr(self, s):
+        try: i = self.attrs.index(s)
+        except ValueError:
+            i = len(self.attrs)
+            self.attrs.append(s)
+        self.code.append(SELECTATTR)
+        self.code.append(i)
+
+    def finish(self):
+        # Epilogue.
+        # XXX slide?
+        self.unwind()
+        return G(self.code[:], self.consts[:], self.attrs[:])
+
+def disassemble(code):
+    rv = []
+    pc = 0
+    i = 0
+    while pc < len(code):
+        # We don't have "%-3d" or str.rjust().
+        istr = str(i)
+        istr = " " * (3 - len(istr)) + istr
+        inst = code[pc]
+        pc += 1
+        if inst in (OUTER, CONST, LOCAL, ARG, SLIDE, SELECTATTR):
+            arg = code[pc]
+            pc += 1
+            s = "%s:  %s %d" % (istr, INSTRUCTIONS[inst], arg)
+        else: s = "%s:  %s" % (istr, INSTRUCTIONS[inst])
+        rv.append(s)
+        i += 1
+    return rv

--- a/main.py
+++ b/main.py
@@ -1,6 +1,6 @@
 import sys
 
-from gmachine import Compiler
+from gmachine import Compiler, disassemble
 from heap import defaultScope, InfiniteLoop
 from parser import parse, NotAnExpr, ParseError
 
@@ -29,6 +29,8 @@ def entryPoint(argv):
         ast.compile(compiler)
         g = compiler.finish()
         print "Top-level machine:", g
+        print "Disassembly:"
+        for line in disassemble(g.code): print line
     except NotAnExpr as e:
         print "Error while compiling"
         print "Input syntax was not an expr, but:", e.cls

--- a/parser.py
+++ b/parser.py
@@ -153,28 +153,31 @@ class SelectBox(EBox):
             return "%s.%s" % (self.expr.pretty(), self.path.pretty())
         else:
             return "%s.%s or %s" % (self.expr.pretty(), self.path.pretty(), self.alt.pretty())
-    # def compile(self, compiler):
-    #     assert self.alt is None, "can't compile yet"
-    #     return heap.HeapSelect(self.expr.compile(scope),
-    #                            [attr2str(attr) for attr in self.path.getattrs()])
+    def compile(self, compiler):
+        assert self.alt is None, "can't compile yet"
+        self.expr.compile(compiler)
+        for attr in self.path.getattrs(): compiler.selectAttr(attr2str(attr))
 
 class VarBox(EBox):
     def __init__(self, name): self.name = name
     def pretty(self): return self.name
-    # def compile(self, compiler):
-    #     # XXX should probably be a compiler method
+    def compile(self, compiler):
+        # XXX should probably be a compiler method
+        if self.name in compiler.scope: return compiler.outer(self.name)
+        else: raise MissingVar(self.name)
+    # XXX locals
     #     if self.name in compiler.locals:
     #         compiler.pick(len(compiler.locals) - compiler.locals.index(self.name))
-    #     elif self.name in compiler.scope: return compiler.outer(self.name)
-    #     else: raise MissingVar(self.name)
 
 class AppBox(EBox):
     def __init__(self, func, arg):
         self.func = func
         self.arg = arg
     def pretty(self): return "(%s) (%s)" % (self.func.pretty(), self.arg.pretty())
-    # def compile(self, compiler):
-    #     return heap.HeapApp(self.func.compile(scope), self.arg.compile(scope))
+    def compile(self, compiler):
+        self.func.compile(compiler)
+        self.arg.compile(compiler)
+        compiler.mkApp()
 
 class StrQLBox(EBox):
     def __init__(self, init, pairs):
@@ -205,11 +208,13 @@ class ExprBinaryBox(EBox):
         self.verb = verb
     def pretty(self):
         return "(%s %s %s)" % (self.verb, self.left.pretty(), self.right.pretty())
-    # def compile(self, compiler):
-    #     return heap.HeapApp(
-    #             heap.HeapApp(heap.HeapSelect(scope["builtins"], [self.verb]),
-    #                          self.left.compile(scope)),
-    #             self.right.compile(scope))
+    def compile(self, compiler):
+        compiler.outer("builtins")
+        compiler.selectAttr(self.verb)
+        self.left.compile(compiler)
+        compiler.mkApp()
+        self.right.compile(compiler)
+        compiler.mkApp()
 
 class BindBox(RegiuxBox):
     "A box for attrset attributes."

--- a/todo.txt
+++ b/todo.txt
@@ -31,6 +31,9 @@
   * Gonna use the recipe developed in cammy-sampler, bf
     * AST nodes are instances of subclasses of BaseBox
     * Any katamorphisms on ASTs are given as methods
+  * Considering implementing an IR AST
+    * Includes most expansions
+    * Goal: Ease supercombinator recognition and compilation
   * Optimizations? Consider Frances' list:
     * CSE
       * Basically shouldn't ever happen
@@ -57,13 +60,10 @@
 * Evaluation
   * Will need to transform parser AST to something lower-level
     * The ancient question: AST or bytecode?
+      * Bytecode! Maybe an AST first
   * How to be lazy?
-    * Graph reduction?
-      * Bytecode might be a good fit here! Push-enter, etc.
-  * How to builtins?
-    * Either set up a special instruction for them or add `builtins` to scope
-      * Probably the latter, given that `builtins.derivation` is actually Nix code
-        * This is the case in both Nix and Tvix
+    * G-machine!
+      * Needs effort to properly share work
 * Store operations
   * Might not be our problem at first
     * Because if we can emit derivations, then the system daemon can take over?