提交: 93e74726ee3198bf643e3348c10f3b064ef4f16e - cammy (git)

A categorical programming language

Commit MetaInfo

• 修订版: 93e74726ee3198bf643e3348c10f3b064ef4f16e (tree)
• 时间: 2022-04-07 13:47:18
• 作者: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

Improve the JIT merge points.

The generated JIT bridges are much nicer. There's still a lot of
typechecking, though.

更改概述

• modified: accept-jelly.py
• modified: cammy-rpy/builder.nix
• modified: cammy-rpy/cammylib/arrows.py
• modified: cammy-rpy/cammylib/djinn.py
• modified: cammy-rpy/cammylib/jelly.py
• modified: cammy-rpy/draw.py
• modified: cammy-rpy/repl.py
• modified: default.nix
• modified: hive/complex-graph.cammy
• add: hive/demo/burning-ship-color.cammy
• modified: hive/demo/burning-ship-fast.cammy
• modified: hive/demo/burning-ship.cammy
• add: hive/f/2pi.cammy
• add: hive/f/radians-to-turns.cammy
• modified: hive/fractal-maybe.cammy
• add: hive/fractal-membership-color.cammy
• modified: hive/fractal-membership-fast.cammy
• modified: hive/fractal-membership.cammy
• add: hive/int-fractal-maybe.cammy
• add: hive/int-step-iter.cammy
• modified: hive/iter-fractal.cammy
• add: hive/monads/maybe/guard.cammy
• add: hive/nat/16.cammy
• add: hive/nat/32.cammy
• add: hive/nat/4.cammy
• modified: hive/nat/lte.cammy
• modified: jelly/src/main.rs
• modified: test_canonical.json
• modified: todo.txt

差异

--- a/accept-jelly.py
+++ b/accept-jelly.py
@@ -5,7 +5,7 @@ import sys
 movelist = sys.argv[-2]
 jelly = sys.argv[-1]
 timeout = 5
-difficulty = 10
+difficulty = 15
 
 with open("test_canonical.json", "rb") as handle:
     testCases = json.load(handle)

--- a/cammy-rpy/builder.nix
+++ b/cammy-rpy/builder.nix
@@ -33,8 +33,8 @@ in
       pypyPackages.pytest libffi
     ];
 
-    JELLY_PATH = "${jelly}/bin/jelly";
-    MOVELIST_PATH = "${movelist}/bin/movelist";
+    # JELLY_PATH = "${jelly}/bin/jelly";
+    # MOVELIST_PATH = "${movelist}/bin/movelist";
 
     buildPhase = ''
       source $stdenv/setup

--- a/cammy-rpy/cammylib/arrows.py
+++ b/cammy-rpy/cammylib/arrows.py
@@ -1,7 +1,7 @@
 import math
 
-from rpython.rlib.jit import JitDriver, isconstant, we_are_jitted
-from rpython.rlib.rbigint import rbigint
+from rpython.rlib.jit import JitDriver, isconstant, promote, we_are_jitted
+# from rpython.rlib.rbigint import rbigint
 
 
 class TypeFail(Exception):
@@ -46,7 +46,7 @@ class N(Element):
     _immutable_ = True
     def __init__(self, bi): self._bi = bi
     def n(self): return self._bi
-    def asStr(self): return self._bi.str()
+    def asStr(self): return "%d" % self._bi
 
 class F(Element):
     _immutable_ = True
@@ -106,7 +106,10 @@ class H(Element):
         self._f = f
         self._x = x
     def apply(self, y):
-        return self._f.run(P(self._x, y))
+        # Defunctionalize by assuming that f can only take on finitely many
+        # values. This trick was suggested by cfbolz; they do a similar trick
+        # in Pycket for similar ends.
+        return promote(self._f).run(P(self._x, y))
     def asStr(self):
         return "%s @ %s" % (self._f, self._x.asStr())
 
@@ -265,12 +268,12 @@ class Disj(Arrow):
 
 class Zero(Arrow):
     _immutable_ = True
-    def run(self, x): return N(rbigint.fromint(0))
+    def run(self, x): return N(0)
     def types(self, cs): return cs.concrete("1"), cs.concrete("N")
 
 class Succ(Arrow):
     _immutable_ = True
-    def run(self, x): return N(x.n().int_add(1))
+    def run(self, x): return N(x.n() + 1)
     def types(self, cs): return cs.concrete("N"), cs.concrete("N")
 
 pr_driver = JitDriver(name="pr",
@@ -286,9 +289,9 @@ class PrimRec(Arrow):
     def run(self, x):
         n = x.n()
         rv = self._x.run(T())
-        while n.tobool():
+        while n > 0:
             pr_driver.jit_merge_point(pr=self, n=n, rv=rv)
-            n = n.int_sub(1)
+            n -= 1
             rv = self._f.run(rv)
         return rv
 
@@ -318,11 +321,10 @@ class Cons(Arrow):
         return cs.functor("pair", [x, xs]), xs
 
 fold_driver = JitDriver(name="fold",
-        greens=["fold"], reds=["element"],
+        greens=["arrow", "fold"], reds="auto",
         is_recursive=True)
 
 def driveFold(fold, element):
-    fold_driver.jit_merge_point(fold=fold, element=element)
     return fold.run(element)
 
 class Fold(Arrow):
@@ -333,7 +335,9 @@ class Fold(Arrow):
     def run(self, x):
         rv = self._n.run(T())
         for e in x.l():
-            rv = driveFold(self._c, P(e, rv))
+            fold_driver.jit_merge_point(arrow=self, fold=self._c)
+            elt = P(e, rv)
+            rv = self._c.run(elt)
         return rv
     def types(self, cs):
         ndom, ncod = self._n.types(cs)

--- a/cammy-rpy/cammylib/djinn.py
+++ b/cammy-rpy/cammylib/djinn.py
@@ -4,10 +4,10 @@ from rpython.rlib.rfile import create_popen_file
 
 from cammylib.parser import parse
 
-movelist_path = os.environ["MOVELIST_PATH"]
-
 def askDjinn(dom, cod):
     "Synthesize a Cammy expression with the given domain and codomain."
+
+    movelist_path = os.environ["MOVELIST_PATH"]
     command = "%s '%s' '%s' 1" % (movelist_path, dom.asStr(), cod.asStr())
     with create_popen_file(command, "r") as handle:
         s = handle.read()

--- a/cammy-rpy/cammylib/jelly.py
+++ b/cammy-rpy/cammylib/jelly.py
@@ -4,13 +4,13 @@ from rpython.rlib.rfile import create_fdopen_rfile
 
 from cammylib.parser import parse
 
-jelly_path = os.environ["JELLY_PATH"]
-
 def jellify(sexp):
     """
     Optimize a Cammy expression.
     """
 
+    jelly_path = os.environ["JELLY_PATH"]
+
     rin, win = os.pipe()
     rout, wout = os.pipe()
     # NB: We must close all four pipe FDs in both processes.

--- a/cammy-rpy/draw.py
+++ b/cammy-rpy/draw.py
@@ -53,27 +53,22 @@ class Window(object):
         return c1, c2
 
 sample_driver = JitDriver(name="sample",
-        greens=["program"], reds=["x", "y"],
+        greens=["program"], reds="auto",
         is_recursive=True)
 
-def sample(program, x, y):
-    sample_driver.jit_merge_point(program=program, x=x, y=y)
-    rgb = program.run(P(F(x), F(y)))
-    r = rgb.first().f()
-    g = rgb.second().first().f()
-    b = rgb.second().second().f()
-    return r, g, b
-
 offsets = [(0.0, 0.0), (1.0, 1.0), (1.0, -1.0), (-1.0, 1.0), (-1.0, -1.0)]
 
 @unroll_safe
 def multisample(program, radius, x, y):
     r = g = b = 0.0
     for ox, oy in offsets:
-        sr, sg, sb = sample(program, x + radius * ox, y + radius * oy)
-        r += sr
-        g += sg
-        b += sb
+        sx = x + radius * ox
+        sy = y + radius * oy
+        sample_driver.jit_merge_point(program=program)
+        rgb = program.run(P(F(sx), F(sy)))
+        r += rgb.first().f()
+        g += rgb.second().first().f()
+        b += rgb.second().second().f()
     l = len(offsets)
     return finishChannel(r / l), finishChannel(g / l), finishChannel(b / l)
 

--- a/cammy-rpy/repl.py
+++ b/cammy-rpy/repl.py
@@ -45,11 +45,19 @@ def command(hive, code, line):
         arrow = sexp.buildArrow()
         cs = ConstraintStore()
         domain, codomain = arrow.types(cs)
+        # If the arrow is polymorphic, monomorphize it.
+        cs.unify(domain, cs.concrete("1"))
         extractor = TypeExtractor(cs, PlaintextTypeFormatter())
         if extractor.extract(domain) != "1":
             print "Arrow is not an element"
         else:
             print arrow.run(T()).asStr()
+    elif code == "n":
+        # Normalize an arrow.
+        sexp, trail = parse(line)
+        sexp = sexp.canonicalize(hive)
+        sexp = jellify(sexp)
+        print sexp.asStr()
     elif code == "d":
         # Invoke djinn.
         dom, cod = parseTypes(line)

--- a/default.nix
+++ b/default.nix
@@ -3,12 +3,12 @@ let
   inherit (nixpkgs) pkgs;
   jelly = (import jelly/Cargo.nix { pkgs = nixpkgs; }).rootCrate.build;
   movelist = import ./movelist { inherit nixpkgs; };
-  cammy-comb = import ./cammy-rpy/comb.nix { inherit nixpkgs jelly movelist; };
-  cammy-draw = import ./cammy-rpy/draw.nix { inherit nixpkgs jelly movelist; };
-  cammy-frame = import ./cammy-rpy/frame.nix { inherit nixpkgs jelly movelist; };
-  cammy-repl = import ./cammy-rpy/repl.nix { inherit nixpkgs jelly movelist; };
-  cammy-rename = import ./cammy-rpy/rename.nix { inherit nixpkgs jelly movelist; };
-  cammy-weave = import ./cammy-rpy/weave.nix { inherit nixpkgs jelly movelist; };
+  cammy-comb = import ./cammy-rpy/comb.nix { inherit nixpkgs ; };
+  cammy-draw = import ./cammy-rpy/draw.nix { inherit nixpkgs ; };
+  cammy-frame = import ./cammy-rpy/frame.nix { inherit nixpkgs ; };
+  cammy-repl = import ./cammy-rpy/repl.nix { inherit nixpkgs ; };
+  cammy-rename = import ./cammy-rpy/rename.nix { inherit nixpkgs ; };
+  cammy-weave = import ./cammy-rpy/weave.nix { inherit nixpkgs ; };
 in pkgs.stdenv.mkDerivation {
   name = "cammy";
   version = "0.2";
@@ -32,11 +32,23 @@ in pkgs.stdenv.mkDerivation {
     makeWrapper ${jelly}/bin/jelly $out/bin/cammy-jelly
 
     # RPython tools
-    makeWrapper ${cammy-comb}/bin/cammy-comb $out/bin/cammy-comb
-    makeWrapper ${cammy-draw}/bin/cammy-draw $out/bin/cammy-draw
-    makeWrapper ${cammy-frame}/bin/cammy-frame $out/bin/cammy-frame
-    makeWrapper ${cammy-repl}/bin/cammy-repl $out/bin/cammy-repl
-    makeWrapper ${cammy-rename}/bin/cammy-rename $out/bin/cammy-rename
-    makeWrapper ${cammy-weave}/bin/cammy-weave $out/bin/cammy-weave
+    makeWrapper ${cammy-comb}/bin/cammy-comb $out/bin/cammy-comb \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
+    makeWrapper ${cammy-draw}/bin/cammy-draw $out/bin/cammy-draw \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
+    makeWrapper ${cammy-frame}/bin/cammy-frame $out/bin/cammy-frame \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
+    makeWrapper ${cammy-repl}/bin/cammy-repl $out/bin/cammy-repl \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
+    makeWrapper ${cammy-rename}/bin/cammy-rename $out/bin/cammy-rename \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
+    makeWrapper ${cammy-weave}/bin/cammy-weave $out/bin/cammy-weave \
+      --set JELLY_PATH "$out/bin/cammy-jelly" \
+      --set MOVELIST_PATH "$out/bin/cammy-djinn"
   '';
 }

--- a/hive/complex-graph.cammy
+++ b/hive/complex-graph.cammy
@@ -1,4 +1,8 @@
-(comp (pair (f/addpair (f/divpair (comp pair/swap f-atan2) (fun/const (f/mulpair f-pi f/2))) (fun/const (comp f/2 f-recip))) (f/mulpair v2/complex/norm (fun/const f/2))) hv2rgb)
+(comp
+  (pair
+    (f/addpair (comp (comp pair/swap f-atan2) f/radians-to-turns) (fun/const (comp f/2 f-recip)))
+    (f/mulpair v2/complex/norm (fun/const f/2)))
+  hv2rgb)
 
 Map a complex number to a color. The magnitude is mapped to luminance and the
 angle is mapped to hue.

--- /dev/null
+++ b/hive/demo/burning-ship-color.cammy
@@ -0,0 +1,11 @@
+(comp
+  (comp
+    (fractal-membership-color v2/burning-ship nat/9)
+    (monads/maybe/guard (pair/of nat/lte id (fun/const nat/8))))
+  (case
+    (comp (comp nat/to-f f/radians-to-turns) h2rgb)
+    (v3/broadcast f-zero)))
+
+Draw membership for the [Burning Ship
+fractal](https://en.wikipedia.org/wiki/Burning_Ship_fractal), a relative of
+the Mandelbrot set.

--- a/hive/demo/burning-ship-fast.cammy
+++ b/hive/demo/burning-ship-fast.cammy
@@ -1,4 +1,4 @@
-(comp (fractal-membership-fast v2/burning-ship nat/256) (v3/broadcast (f/subpair (fun/const f-one) id)))
+(fractal-membership-fast v2/burning-ship nat/8)
 
 Draw membership for the [Burning Ship
 fractal](https://en.wikipedia.org/wiki/Burning_Ship_fractal), a relative of

--- a/hive/demo/burning-ship.cammy
+++ b/hive/demo/burning-ship.cammy
@@ -1,4 +1,4 @@
-(comp (fractal-membership v2/burning-ship nat/256) (v3/broadcast (f/subpair (fun/const f-one) id)))
+(comp (fractal-membership v2/burning-ship nat/8) (v3/broadcast (f/subpair (fun/const f-one) id)))
 
 Draw membership for the [Burning Ship
 fractal](https://en.wikipedia.org/wiki/Burning_Ship_fractal), a relative of

--- /dev/null
+++ b/hive/f/2pi.cammy
@@ -0,0 +1,3 @@
+(f/mulpair f/2 f-pi)
+
+The constant $2\pi$, sometimes called $\tau$.

--- /dev/null
+++ b/hive/f/radians-to-turns.cammy
@@ -0,0 +1,3 @@
+(f/divpair id (fun/const f/2pi))
+
+Convert radians to turns.

--- a/hive/fractal-maybe.cammy
+++ b/hive/fractal-maybe.cammy
@@ -1,3 +1,7 @@
-(comp (comp @0 (pair v2/complex/mag-2 (pair left (comp ignore right)))) bool/pick)
+(comp
+  (comp
+    @0
+    (pair v2/complex/mag-2 (pair left (comp ignore right))))
+  bool/pick)
 
 Take a step in an IFS, failing if the step has magnitude 2 or greater.

--- /dev/null
+++ b/hive/fractal-membership-color.cammy
@@ -0,0 +1,6 @@
+(comp
+  (iter-fractal @0 @1)
+  (comp (list/filter v2/complex/mag-2) list/len))
+
+Like fractal-membership, but just returning the length so that we can
+false-color it.

--- a/hive/fractal-membership-fast.cammy
+++ b/hive/fractal-membership-fast.cammy
@@ -1,4 +1,8 @@
-(comp (iter-fractal-fast @0 @1) (case (fun/const f-one) (fun/const f-zero)))
+(comp
+  (iter-fractal-fast @0 @1)
+  (case
+    (v3/broadcast (fun/const f-one))
+    (comp (comp nat/to-f f/radians-to-turns) h2rgb)))
 
 Iterate a fractal for a maximum number of steps, and return a value in $[0,1]$
 indicating how many steps were taken, with 1 indicating that the fractal did

--- a/hive/fractal-membership.cammy
+++ b/hive/fractal-membership.cammy
@@ -1,4 +1,6 @@
-(comp (iter-fractal @0 @1) (comp (list/filter v2/complex/mag-2) (comp list/len (f/divpair nat/to-f (fun/const (comp @1 nat/to-f))))))
+(comp
+  (iter-fractal @0 @1)
+  (comp (list/filter v2/complex/mag-2) (comp list/len (f/divpair nat/to-f (fun/const (comp @1 nat/to-f))))))
 
 Measure the degree to which a fractal diverges. Given a maximum number of
 steps, we iterate the IFS for a fractal in the complex plane until its

--- /dev/null
+++ b/hive/int-fractal-maybe.cammy
@@ -0,0 +1,7 @@
+(comp
+  (comp
+    fun/app
+    (pair v2/complex/mag-2 (pair left (comp ignore right))))
+  bool/pick)
+
+Like fractal-maybe, but internal.

--- /dev/null
+++ b/hive/int-step-iter.cammy
@@ -0,0 +1 @@
+(monads/iter step-unit step-bind (maybe-step @0))

--- a/hive/iter-fractal.cammy
+++ b/hive/iter-fractal.cammy
@@ -1,4 +1,8 @@
-(comp (fun/apppair (fun/const (comp @1 nonempty/unfold)) (pair (comp (fun/const f-zero) pair/dup) @0)) snd)
+(comp
+  (fun/apppair
+    (fun/const (comp @1 nonempty/unfold))
+    (pair (comp (fun/const f-zero) pair/dup) @0))
+  snd)
 
 Iterate an [IFS](https://en.wikipedia.org/wiki/Iterated_function_system) for a
 given number of steps.

--- /dev/null
+++ b/hive/monads/maybe/guard.cammy
@@ -0,0 +1,5 @@
+(comp
+  (pair @0 (pair left (fun/const right)))
+  bool/pick)
+
+Do nothing if a value passes a filter, otherwise fail.

--- /dev/null
+++ b/hive/nat/16.cammy
@@ -0,0 +1 @@
+(comp nat/4 nat/sqr)

--- /dev/null
+++ b/hive/nat/32.cammy
@@ -0,0 +1 @@
+(comp (pair nat/5 nat/2) nat/exp)

--- /dev/null
+++ b/hive/nat/4.cammy
@@ -0,0 +1 @@
+(comp nat/2 nat/sqr)

--- a/hive/nat/lte.cammy
+++ b/hive/nat/lte.cammy
@@ -1 +1,7 @@
-(curry (comp (uncurry nat/monus) nat/is_zero))
+(uncurry (pr
+  (curry (fun/const t))
+  (curry (comp
+    (comp (pair/mapsnd nat/pred-maybe) fun/distribr)
+    (case fun/app (fun/const f))))))
+
+The less-than-or-equal relation on natural numbers.

--- a/jelly/src/main.rs
+++ b/jelly/src/main.rs
@@ -20,6 +20,9 @@ fn load_tree(handle :&mut Read) -> std::io::Result<RecExpr<SymbolLang>> {
 // "dual from X" means that justification X formally dualizes to justify the following rule. For
 // example, products and sums are dual.
 
+// "inverse of X" means that rule X is run in reverse in order to open up further optimization
+// opportunities.
+
 // Rules marked "associative!" can cause explosions.
 
 // Rules marked "improvement!" can improve IEEE 754 results in both precision and accuracy, so
@@ -51,6 +54,8 @@ fn main() -> std::io::Result<()> {
             => "(pair (comp ?f ?j) ?g)"),
         // Elliott 2013
         rw!("pair-precompose"; "(pair (comp ?r ?f) (comp ?r ?g))" => "(comp ?r (pair ?f ?g))"),
+        // inverse of pair-precompose
+        rw!("pair-precompose-inv"; "(comp ?r (pair ?f ?g))" => "(pair (comp ?r ?f) (comp ?r ?g))"),
         // pair-precompose when ?f is id
         rw!("pair-factor-fst"; "(pair ?r (comp ?r ?g))" => "(comp ?r (pair id ?g))"),
         // pair-precompose when ?g is id
@@ -88,6 +93,10 @@ fn main() -> std::io::Result<()> {
         rw!("list-unroll-fold-nil"; "(comp nil (fold ?x ?f))" => "?x"),
         rw!("list-unroll-fold-cons"; "(comp cons (fold ?x ?f))" => "(comp (pair fst (fold ?x ?f)) ?f)"),
 
+        // 2 = 1 + 1
+        rw!("bool-t-either"; "(comp t either)" => "left"),
+        rw!("bool-f-either"; "(comp f either)" => "right"),
+
         // Boolean negation
         rw!("bool-t-not"; "(comp t not)" => "f"),
         rw!("bool-f-not"; "(comp f not)" => "t"),
@@ -122,6 +131,9 @@ fn main() -> std::io::Result<()> {
         rw!("f-one-sign"; "(comp f-one f-sign)" => "t"),
         rw!("f-zero-sign"; "(comp f-zero f-sign)" => "t"),
         rw!("f-pi-sign"; "(comp f-pi f-sign)" => "t"),
+
+        // IEEE 754 function properties
+        rw!("f-recip-sign"; "(comp f-recip f-sign)" => "f-sign"),
     ];
 
     let tree = load_tree(&mut std::io::stdin())?;

--- a/test_canonical.json
+++ b/test_canonical.json
@@ -4,5 +4,6 @@
     ["X", "(pair X X)", ["(pair id id)"]],
     ["(pair X Y)", "(pair Y X)", ["(pair snd fst)"]],
     ["(pair (hom X Y) X)", "Y", ["(uncurry id)"]],
-    ["1", "2", ["t", "f"]]
+    ["1", "2", ["t", "f"]],
+    ["1", "(list X)", ["nil", "(comp ignore nil)"]]
 ]

--- a/todo.txt
+++ b/todo.txt
@@ -3,6 +3,7 @@
   * : commands
     * help, describe commands
     * edit an atom's trail
+    * save a recent REPL line as a new file
 * More list manipulations
   * list/eq : [X × X, 2] → [[X] × [X], 2]
   * list/zip : [X] × [Y] → [X × Y]
@@ -33,6 +34,7 @@
   * Interval type?
 * Cantor's type of bitstrings: N -> 2
   * We have subobjects now, X -> 2
+  * And finite bitstrings, [2]
 * Moore machines: For state type Q and input type S, Q × S -> Q
   * Moore transducers: [Q × S, Q] -> [Q × S, Q]
 * Mealy machines: For state type Q, input type S, and output type L, Q × S -> Q × L
@@ -49,5 +51,15 @@
   * We now can iter-maybe, short-circuiting evaluation
   * We need to iter-maybe but also keep track of how many steps were taken
     * Instead of X -> [N, Y + 1], we need X -> [N, N x (Y + 1)]
+  * It's all built and type-checked, but it doesn't work
+    * The fractal has type C -> [C, C] where C is complex numbers
+      * We are currently calling it with 0+0i, which is a family index
+        * Constant family, constant output
+      * We need to call it with the input number (easy) and then use internal
+        logic to call the endomorphism in a loop (hard)
 * ulimit jellification?
 * formal power series N -> Q
+* Dual numbers: like complex numbers, but different units, multiplication
+* CI: automatic generation of demo images
+  * Would be nice to know how long it takes, too
+  * Parameterize by number of iterations?