提交: a493d594f55f546bed94bbed9f5a08547ff4ba02 - cammy (git)

A categorical programming language

Commit MetaInfo

• 修订版: a493d594f55f546bed94bbed9f5a08547ff4ba02 (tree)
• 时间: 2023-01-03 09:20:01
• 作者: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

Really get hacking with graph reduction in RPython.

更改概述

• modified: cammy-rpy/builder.nix
• add: cammy-rpy/cammylib/graph.py
• modified: cammy-rpy/cammylib/parser.py
• modified: cammy-rpy/main.py
• modified: movelist/cammy-graph.scm

差异

--- a/cammy-rpy/builder.nix
+++ b/cammy-rpy/builder.nix
@@ -2,17 +2,15 @@ entrypoint: exe: enableJIT:
 { nixpkgs ? import <nixpkgs> {}, jelly ? null, movelist ? null }:
 let
   inherit (nixpkgs.pkgs)
-  fetchFromGitLab stdenv
+  fetchhg stdenv
   pkg-config libffi stb libcaca
   python2 python2Packages;
   # https://foss.heptapod.net/pypy/pypy/
-  pypySrc = fetchFromGitLab {
-    domain = "foss.heptapod.net";
-    owner = "pypy";
-    repo = "pypy";
-    # release candidate from branch release-pypy3.8-v7.x
-    rev = "90fd9ed34d52181de59cbfff863719472b05418e";
-    sha256 = "03cshgvh8qcsyac4q4vf0sbvcm1m2ikgwycwip4cc7sw9pzpw6a3";
+  pypySrc = fetchhg {
+    url = "https://foss.heptapod.net/pypy/pypy";
+    # tag release-pypy3.8-v7.3.11
+    rev = "release-pypy3.8-v7.3.11";
+    sha256 = "sha256-yHIY4cuCpfB0Nl1Odutc9w2QUPhWK+rxaSGfbBV+ZUg=";
   };
 in
   let

--- /dev/null
+++ b/cammy-rpy/cammylib/graph.py
@@ -0,0 +1,111 @@
+# Basic graph reduction.
+# Heavily inspired by https://theory.stanford.edu/~blynn/lambda/cl.html
+# and https://www.youtube.com/watch?v=GawiQQCn3bk
+
+from cammylib.parser import makeParser
+
+class InvalidGraph(Exception): pass
+
+class Node(object):
+    _immutable_ = True
+    def asStr(self): return self.symbol
+
+class Unit(Node):
+    _immutable_ = True
+    def asStr(self): return "*"
+unit = Unit()
+
+class App(Node):
+    _immutable_ = True
+
+    def __init__(self, f, x):
+        self.f = f
+        self.x = x
+
+    def asStr(self): return "(@ %s %s)" % (self.f.asStr(), self.x.asStr())
+
+class WordBox(Node):
+    _immutable_ = True
+    def __init__(self, w): self.w = w
+    def asStr(self): return "(w# %d)" % self.w
+
+lits = {
+    "Z": WordBox(0),
+    "U": unit,
+}
+prims = {name: type(name, (Node,), {"_immutable_": True, "symbol": name})() for name in (
+    "I", "B", "C", "K", "S", "N", "1+", "FZ", "FO",
+)}
+
+def buildAtom(symbol):
+    if symbol in lits: return lits[symbol]
+    elif symbol in prims: return prims[symbol]
+    else: raise InvalidGraph("can only build lits and prims")
+def buildApp(head, args):
+    if head != "@": raise InvalidGraph("can only build apps")
+    if len(args) != 2: raise InvalidGraph("can only do binary app")
+    return App(args[0], args[1])
+GraphParser = makeParser("GraphParser", buildAtom, buildApp)
+
+def app(f, x):
+    if f is prims["I"]: return x
+    elif isinstance(f, WordBox): return f
+    else: return App(f, x)
+def comp(g, f):
+    if f is prims["I"]: return g
+    elif g is prims["I"]: return f
+    return app(app(prims["B"], g), f)
+
+def reduce(g):
+    # Heap pointer, value stack
+    hp = g
+    s = []
+
+    while isinstance(hp, App):
+        print "---"
+        print "Current hp:", hp.asStr()
+        print "Current stack:"
+        for v in s: print v.asStr()
+        if hp.f is prims["I"] and s: hp = hp.x
+        elif hp.f is prims["B"] and len(s) >= 2:
+            g = hp.x
+            f = s.pop()
+            x = s.pop()
+            hp = app(g, app(f, x))
+        elif hp.f is prims["1+"]:
+            n = reduce(hp.x)
+            if isinstance(n, WordBox): hp = WordBox(n.w + 1)
+            else: hp = app(hp.f, n)
+        elif hp.f is prims["N"] and len(s) >= 2:
+            x = hp.x
+            f = s.pop()
+            n = reduce(s.pop())
+            if isinstance(n, WordBox):
+                # Exponentiate by squaring
+                i = n.w
+                v = prims["I"]
+                while i:
+                    if i & 1: v = comp(v, f)
+                    f = comp(f, f)
+                    i >>= 1
+                hp = app(v, x)
+            else:
+                # not fully evaluated
+                s.append(n)
+                s.append(f)
+        else: s.append(hp.x); hp = hp.f
+
+    # Rebuild spine if not fully applied
+    while s: hp = app(hp, s.pop())
+    return hp
+
+def doGraph(path):
+    print "Reading graph from", path
+    with open(path, "rb") as handle: parser = GraphParser(handle.read())
+    g = parser.takeExpression()
+    print "Got graph", g.asStr()
+    applied = app(g, unit)
+    print "Applying graph to unit to get", applied.asStr()
+    reduced = reduce(applied)
+    print "Reduced to", reduced.asStr()
+    return 0

--- a/cammy-rpy/cammylib/parser.py
+++ b/cammy-rpy/cammylib/parser.py
@@ -5,59 +5,70 @@ class ParseError(Exception):
     def __init__(self, message):
         self.message = message
 
-class CammyParser(object):
-    def __init__(self, s):
-        self._i = 0
-        self._s = s
-
-    def position(self):
-        return self._i
-
-    def hasMore(self):
-        return self._i < len(self._s)
-
-    def eatWhitespace(self):
-        while self.hasMore() and self._s[self._i] in (" ", "\n"):
-            self._i += 1
-
-    def canAndDoesEat(self, c):
-        if self._s[self._i] == c:
-            self._i += 1
-            return True
-        else:
-            return False
-
-    def takeName(self):
-        start = self._i
-        while self.hasMore() and self._s[self._i] not in (")", "(", " ", "\n"):
-            self._i += 1
-        stop = self._i
-        return self._s[start:stop]
-
-    def takeExpression(self):
-        self.eatWhitespace()
-        if self.canAndDoesEat('('):
-            return self.startFunctor()
-        else:
-            symbol = self.takeName()
-            if symbol.startswith("@"):
-                try:
-                    return sexp.Hole(int(symbol[1:]))
-                except ValueError:
-                    return sexp.Atom(symbol)
-            return sexp.Atom(symbol)
+def makeParser(parserName, buildAtom, buildList):
+    class Parser(object):
+        def __init__(self, s):
+            self._i = 0
+            self._s = s
+
+        def position(self):
+            return self._i
+
+        def hasMore(self):
+            return self._i < len(self._s)
+
+        def eatWhitespace(self):
+            while self.hasMore() and self._s[self._i] in (" ", "\n"):
+                self._i += 1
 
-    def startFunctor(self):
-        start = self._i
-        head = self.takeName()
-        self.eatWhitespace()
-        args = []
-        while not self.canAndDoesEat(')'):
-            args.append(self.takeExpression())
+        def canAndDoesEat(self, c):
+            if self._s[self._i] == c:
+                self._i += 1
+                return True
+            else:
+                return False
+
+        def takeName(self):
+            start = self._i
+            while self.hasMore() and self._s[self._i] not in (")", "(", " ", "\n"):
+                self._i += 1
+            stop = self._i
+            return self._s[start:stop]
+
+        def takeExpression(self):
             self.eatWhitespace()
-            if not self.hasMore():
-                raise ParseError("Unterminated functor starting at %d" % start)
-        return sexp.Functor(head, args)
+            if self.canAndDoesEat('('):
+                return self.startFunctor()
+            else:
+                symbol = self.takeName()
+                return buildAtom(symbol)
+
+        def startFunctor(self):
+            start = self._i
+            head = self.takeName()
+            self.eatWhitespace()
+            args = []
+            while not self.canAndDoesEat(')'):
+                args.append(self.takeExpression())
+                self.eatWhitespace()
+                if not self.hasMore():
+                    raise ParseError("Unterminated functor starting at %d" % start)
+            return buildList(head, args)
+
+    Parser.__name__ = parserName
+    return Parser
+
+def buildCammyAtom(symbol):
+    if symbol.startswith("@"):
+        try:
+            return sexp.Hole(int(symbol[1:]))
+        except ValueError:
+            return sexp.Atom(symbol)
+    return sexp.Atom(symbol)
+
+def buildCammyTemplate(head, args): return sexp.Functor(head, args)
+
+CammyParser = makeParser("CammyParser", buildCammyAtom, buildCammyTemplate)
 
 
 def parse(s):

--- a/cammy-rpy/main.py
+++ b/cammy-rpy/main.py
@@ -5,6 +5,7 @@ from cammylib.hax import patch_ctypes_for_ffi
 
 from animate import doAnimate
 from draw import doDraw
+from cammylib.graph import doGraph
 from repl import doREPL
 
 def help(exe, problem):
@@ -13,6 +14,7 @@ def help(exe, problem):
     print "Usage:"
     print "    animate PROG WIDTH HEIGHT Animate in the terminal"
     print "    draw PROG WIDTH HEIGHT OUT    Draw a picture"
+    print "    graph PROG      Uuuuhhhh"
     print "    repl     Start an interactive session"
     print "Set the hive path by exporting CAMMY_HIVE"
 
@@ -21,19 +23,26 @@ def main(argv):
     if len(argv) < 2:
         help(exe, "no command specified")
         return 1
-    hivepath = os.environ["CAMMY_HIVE"]
     command = argv[1]
     # XXX unrolling_iterable
     if command == "animate":
         if len(argv) != 5:
             help(exe, "animate takes three arguments")
             return 1
+        hivepath = os.environ["CAMMY_HIVE"]
         return doAnimate(hivepath, argv[2], int(argv[3]), int(argv[4]))
     elif command == "draw":
         if len(argv) != 6:
             help(exe, "draw takes four arguments")
+            return 1
         return doDraw(argv[2], argv[3], argv[4], argv[5])
+    elif command == "graph":
+        if len(argv) != 3:
+            help(exe, "graph takes one argument")
+            return 1
+        return doGraph(argv[2])
     elif command == "repl":
+        hivepath = os.environ["CAMMY_HIVE"]
         return doREPL(hivepath)
     else:
         help(exe, "unknown command: " + command)

--- a/movelist/cammy-graph.scm
+++ b/movelist/cammy-graph.scm
@@ -20,6 +20,7 @@
     ((== expr 'id) (== tree 'I))
     ((== expr `(comp ,f ,g)) (== tree `(@ (@ B ,tg) ,tf))
          (combinators° f tf) (combinators° g tg))
+    ((== expr 'ignore) (== tree 'U))
     ; \x l -> l (f x) (g x)
     ((== expr `(pair ,f ,g)) (== tree `(@ (@ S (@ (@ B C) (@ (@ B (@ C I)) ,tf))) ,tg))
          (combinators° f tf) (combinators° g tg))