Commit: 322ce0897c89057b54726d1d10da3deaa281ee57 - regiux (git)

A fast implementation of the Nix expression language

Commit MetaInfo

• Revisión: 322ce0897c89057b54726d1d10da3deaa281ee57 (tree)
• Tiempo: 2024-06-13 13:01:55
• Autor: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

gmachine: Flesh out actual operations.

This is going to be a supercombinator machine, so I need to rethink the
current compilation scheme.

Cambiar Resumen

• modified: gmachine.py
• modified: heap.py
• modified: main.py
• modified: parser.py

Diferencia incremental

--- a/gmachine.py
+++ b/gmachine.py
@@ -2,9 +2,15 @@
 # We will implement graph reduction by compiling an expression into bytecode
 # which, when evaluated, builds the graph node representing that expression.
 
-CONST, OUTER, PICK = range(3)
+# Quirks:
+# 0) The instruction at PC 0 is always UNWIND, to ease EVAL.
+
+from heap import HeapApp
+
+OUTER, CONST, LOCAL, ARG, PRIM, MKAP, SLIDE, COND, EVAL, UNWIND = range(10)
 
 class StackUnderflow(Exception): pass
+class Overapplied(Exception): pass
 
 class G(object):
     _immutable_attrs_ = "code[*]", "consts[*]"
@@ -14,25 +20,52 @@ class G(object):
 
     def run(self, outers):
         stack = []
-        pc = 0
+        dump = []
+        # Quirk (0)
+        pc = 1
         while pc < len(self.code):
             inst = self.code[pc]
             pc += 1
-            if inst == CONST:
-                stack.append(self.consts[self.code[pc]])
-                pc += 1
-            elif inst == OUTER:
+            if inst == OUTER:
                 stack.append(outers[self.code[pc]])
                 pc += 1
-            elif inst == PICK:
-                depth = self.code[pc]
+            elif inst == CONST:
+                stack.append(self.consts[self.code[pc]])
+                pc += 1
+            elif inst == LOCAL:
+                i = len(stack) - self.code[pc]
                 pc += 1
-                i = len(stack) - depth
-                if i < 0: raise StackUnderflow()
                 stack.append(stack[i])
+            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)
+            elif inst == PRIM: assert False
+            elif inst == MKAP: stack.append(HeapApp(stack.pop(), stack.pop()))
+            elif inst == SLIDE:
+                top = stack.pop()
+                stop = len(stack) - self.code[pc]
+                pc += 1
+                if stop < 0: raise StackUnderflow()
+                del stack[:stop]
+                stack.append(top)
+            elif inst == COND: assert False
+            elif inst == EVAL:
+                top = stack.pop()
+                dump.append((stack, pc))
+                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()
             else:
                 print "Unknown bytecode:", inst
                 assert False
+        # XXX possible?
         try: return stack.pop()
         except IndexError: raise StackUnderflow()
 
@@ -44,7 +77,8 @@ class MissingVar(Exception):
 class Compiler(object):
     def __init__(self, scope):
         self.scope = scope
-        self.code = []
+        # Quirk (0)
+        self.code = [UNWIND]
         self.consts = []
         self.locals = []
 
@@ -62,9 +96,21 @@ class Compiler(object):
         self.code.append(CONST)
         self.code.append(i)
 
-    def pick(self, i):
+    def local(self, i):
+        assert i >= 0, "implementation error"
+        self.code.append(LOCAL)
+        self.code.append(i)
+
+    def arg(self, i):
+        assert i >= 0, "implementation error"
+        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(PICK)
+        self.code.append(SLIDE)
         self.code.append(i)
 
     def finish(self): return G(self.code[:], self.consts[:])

--- a/heap.py
+++ b/heap.py
@@ -36,25 +36,25 @@ class HeapObject(object):
                         self.__class__.__name__)
 
 class HeapTrue(HeapObject):
-    _immutable_ = True
+    # _immutable_ = True
     def asStr(self): return "true"
     def unwrapBool(self): return True
 true = HeapTrue()
 
 class HeapFalse(HeapObject):
-    _immutable_ = True
+    # _immutable_ = True
     def asStr(self): return "false"
     def unwrapBool(self): return False
 false = HeapFalse()
 
 class HeapInt(HeapObject):
-    _immutable_ = True
+    # _immutable_ = True
     def __init__(self, i): self.i = i
     def asStr(self): return str(self.i)
     def unwrapInt(self): return self.i
 
 class HeapStr(HeapObject):
-    _immutable_ = True
+    # _immutable_ = True
     def __init__(self, s): self.s = s
     def asStr(self): return self.s
     def unwrapStr(self): return self.s

--- a/main.py
+++ b/main.py
@@ -2,7 +2,7 @@ import sys
 
 from gmachine import Compiler
 from heap import defaultScope, InfiniteLoop
-from parser import parse, MissingVar, NotAnExpr, ParseError
+from parser import parse, NotAnExpr, ParseError
 
 def entryPoint(argv):
     if len(argv) < 2:
@@ -33,10 +33,6 @@ def entryPoint(argv):
         print "Error while compiling"
         print "Input syntax was not an expr, but:", e.cls
         return 1
-    except MissingVar as e:
-        print "Error while compiling"
-        print "Name was missing:", e.name
-        return 1
 
     obj = g.run(defaultScope.values())
     print "Heap object:", obj

--- a/parser.py
+++ b/parser.py
@@ -161,12 +161,12 @@ class SelectBox(EBox):
 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
-        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)
+    # def compile(self, compiler):
+    #     # XXX should probably be a compiler method
+    #     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):