提交: 245f670944ef60b609a95029f37db32924d75ba4 - cammy (git)

A categorical programming language

Commit MetaInfo

• 修订版: 245f670944ef60b609a95029f37db32924d75ba4 (tree)
• 时间: 2022-10-17 02:57:01
• 作者: Corbin <cds@corb...>
• Commiter: Corbin

Log Message

Rewrite the trampoline in Purescript.

Took a little bit of effort, but it seems worthwhile! The generated code
has the desired loop! I'm impressed.

更改概述

• modified: .envrc
• add: honey/cammy.purs
• modified: honey/honey.py
• modified: honey/static/honey.js
• modified: shell.nix

差异

--- a/.envrc
+++ b/.envrc
@@ -1,4 +1,4 @@
-# export NIX_PATH=nixpkgs=/home/simpson/nixpkgs
+export NIX_PATH=nixpkgs=/home/simpson/nixpkgs
 use nix
 eval $(keychain --eval --agents ssh)
 

--- /dev/null
+++ b/honey/cammy.purs
@@ -0,0 +1,41 @@
+module Cammy where
+
+data Unit = Unit
+type Lazy = (->) Unit
+data Free f t = Pure t | Free (f (Free f t))
+
+-- Cribbed Bilby trampoline, modified and extended to give a monad.
+-- Improved using https://stackoverflow.com/a/64854259/264985
+-- Further improved by ripping off Control.Monad.Trampoline
+type Tramp = Free Lazy
+
+done :: forall t. t -> Tramp t
+done = Pure
+
+cont :: forall t. (Unit -> Tramp t) -> Tramp t
+cont = Free
+
+fmap :: forall s t. (s -> t) -> Tramp s -> Tramp t
+fmap f (Pure x) = Pure (f x)
+fmap f (Free thunk) = Free (\u -> fmap f (thunk u))
+
+bind :: forall s t. (s -> Tramp t) -> Tramp s -> Tramp t
+bind f (Pure x) = f x
+bind f (Free thunk) = Free (\u -> bind f (thunk u))
+
+join :: forall t. Tramp (Tramp t) -> Tramp t
+join = bind id
+
+runTrampoline :: forall t. Tramp t -> t
+runTrampoline (Pure x) = x
+runTrampoline (Free thunk) = runTrampoline (thunk Unit)
+
+lift :: forall s t. (s -> t) -> s -> Tramp t
+lift f x = Pure (f x)
+
+id :: forall t. t -> t
+id x = x
+
+comp :: forall r s t. (r -> Tramp s) -> (s -> Tramp t) -> r -> Tramp t
+comp f g x = bind g (f x)
+

--- a/honey/honey.py
+++ b/honey/honey.py
@@ -9,6 +9,7 @@ from .constants import CORE_PRIMITIVES, CORE_TEMPLATES
 from .parser import parse
 
 MOVELIST = "/nix/store/dhlswr6d9057lvdq7394dgmlncviv7za-movelist/bin/"
+PURESCRIPT = "/nix/store/sf7hbhk4bbfq9px1y6442pvlmd6z2zn5-purescript-0.14.7/bin/"
 
 app = Flask(__name__)
 
@@ -78,7 +79,7 @@ def home():
         </div>
         <script
             src="{ url_for("static", filename="honey.js") }"
-            type="text/javascript"></script>
+            type="module"></script>
         <datalist id="dippers">
             {dippers}
         </datalist>

--- a/honey/static/honey.js
+++ b/honey/static/honey.js
@@ -1,3 +1,5 @@
+import * as Cammy from "./Cammy/index.js";
+
 function fetchJSON(url, options = {}) {
     return fetch(url, options).then(resp => resp.json());
 }
@@ -35,51 +37,9 @@ class Extractor {
     }
 }
 
-function rescueNaN(f) {
-    return x => {
-        let y = f(x);
-        return isNaN(y) ? [false, null] : [true, y];
-    };
-}
-
-// Cribbed Bilby trampoline, modified and extended to give a monad.
-// Improved using https://stackoverflow.com/a/64854259/264985
-// X -> Tramp X
-function done(result) { return ["pure", result]; }
-// [1,Tramp X] -> Tramp X
-function cont(thunk) { return ["cont", thunk]; }
-// Tramp X × [X,Tramp Y] -> Tramp Y
-function bind(action, f) { return ["bind", action, f]; }
-// function join(action) { return cont(() => bind(action, ma => ma)); }
-// function fmap(f) { return action => bind(action, x => done(f(x))); }
-// [X,Tramp Y] × [Y,Tramp Z] -> [X,Tramp Z]
-function andThen(f, g) { return x => bind(f(x), g); }
-// Tramp X -> X
-function trampoline(action) {
-    // Tramp X
-    let register = action;
-    // µS. [X,Tramp Y] × S + 1
-    let stack = null;
-    while (true) {
-        switch (register[0]) {
-            case "pure":
-                if (stack === null) { return register[1]; }
-                register = stack[0](register[1]);
-                stack = stack[1];
-                break;
-            case "bind":
-                stack = [register[2], stack];
-                register = register[1];
-                break;
-            case "cont":
-                register = register[1]();
-                break;
-            default:
-                console.log("stack", stack);
-                throw new Error("unknown trampoline action " + register[0]);
-        }
-    }
-}
+function fixNaN(x) { return isNaN(x) ? [false, null] : [true, x]; }
+function rescueNaN(f) { return x => fixNaN(f(x)); }
+function rescueNaN2(f) { return ([x, y]) => fixNaN(f(x, y)); }
 
 const prims = {
     "id": x => x,
@@ -87,6 +47,7 @@ const prims = {
     "fst": ([x, y]) => x,
     "snd": ([x, y]) => y,
     "dup": x => [x, x],
+    "app": ([f, x]) => f(x),
     // XXX not the best encoding for sums
     "left": x => [true, x],
     "right": x => [false, x],
@@ -105,11 +66,10 @@ const prims = {
     "f-zero": _ => 0.0,
     "f-one": _ => 1.0,
     "f-pi": _ => Math.PI,
-    // XXX need NaN checks!
-    "f-add": ([x, y]) => x + y,
-    "f-mul": ([x, y]) => x * y,
+    "f-add": rescueNaN2((x, y) => x + y),
+    "f-mul": rescueNaN2((x, y) => x * y),
     "f-negate": x => -x,
-    "f-recip": x => 1 / x,
+    "f-recip": rescueNaN(x => 1 / x),
     "f-sign": x => x <= -0.0,
     "f-floor": rescueNaN(Math.floor),
     "f-sqrt": rescueNaN(Math.sqrt),
@@ -124,11 +84,11 @@ function compile(expr) {
         switch (expr[0]) {
             case "comp": {
                 const [f, g] = l;
-                return andThen(f, g);
+                return x => Cammy.bind(f(x), g);
             }
             case "pair": {
                 const [f, g] = l;
-                return x => bind(f(x), y => bind(g(x), z => done([y, z])));
+                return x => Cammy.bind(f(x), y => Cammy.bind(g(x), z => Cammy.done([y, z])));
             }
             case "case": {
                 const [f, g] = l;
@@ -136,20 +96,18 @@ function compile(expr) {
             }
             case "curry": {
                 const [f] = l;
-                // XXX slightly wrong...
-                return x => done(y => f([x, y]));
+                return x => Cammy.done(y => f([x, y]));
             }
             case "uncurry": {
                 const [f] = l;
-                // XXX ...but also wrong here
-                return ([x, y]) => bind(f(x), g => g(y));
+                return ([x, y]) => Cammy.join(Cammy.bind(f(x), g => g(y)));
             }
             case "pr": {
                 const [z, s] = l;
                 return x => {
                     let rv = z(null);
                     for (let i = 0; i < x; i++) {
-                        rv = bind(rv, s);
+                        rv = Cammy.bind(rv, s);
                     }
                     return rv;
                 };
@@ -159,9 +117,9 @@ function compile(expr) {
                 return xs => {
                     let rv = n(null);
                     for (let i = 0; i < xs.length; i++) {
-                        rv = bind(rv, x => c([xs[i], x]));
+                        rv = Cammy.bind(rv, x => c([xs[i], x]));
                     }
-                    return done(rv);
+                    return Cammy.done(rv);
                 };
             }
             default:
@@ -171,7 +129,7 @@ function compile(expr) {
         if (prims[expr] === undefined) {
             throw new Error("unimplemented prim " + expr);
         }
-        return x => done(prims[expr](x));
+        return x => Cammy.done(prims[expr](x));
     }
 }
 
@@ -250,7 +208,7 @@ function tileForIndex(extractor, index, title, trail) {
                         const canvas = document.createElement("canvas");
                         canvas.width = 100; canvas.height = 100;
                         div.appendChild(canvas);
-                        drawFrame(canvas, ([x, y]) => trampoline(compiled([x, y])), getChannels);
+                        drawFrame(canvas, ([x, y]) => Cammy.runTrampoline(compiled([x, y])), getChannels);
                     } else {
                         div.innerHTML += "Not sure how to display this image yet.";
                     }
@@ -265,7 +223,7 @@ function tileForIndex(extractor, index, title, trail) {
                         function stepFrame(timestamp) {
                             if (start === undefined) { start = timestamp; }
                             const t = (timestamp - start) * 0.001;
-                            drawFrame(canvas, ([x, y]) => trampoline(compiled([[x, y], t])), getChannels);
+                            drawFrame(canvas, ([x, y]) => Cammy.runTrampoline(compiled([[x, y], t])), getChannels);
                             setTimeout(() => window.requestAnimationFrame(stepFrame), 1000);
                         }
                         window.requestAnimationFrame(stepFrame);
@@ -277,7 +235,7 @@ function tileForIndex(extractor, index, title, trail) {
                     {
                         div.setAttribute("class", "tile sequence");
                         const result = Array.from({length: 10},
-                            (_, i) => trampoline(compiled(i)));
+                            (_, i) => Cammy.runTrampoline(compiled(i)));
                         const guts = result.map(renderer).join("</td><td>");
                         div.innerHTML += `<table>
                             <tr>
@@ -288,7 +246,7 @@ function tileForIndex(extractor, index, title, trail) {
                     break;
                 case JSON.stringify("1"):
                     div.setAttribute("class", "tile element");
-                    div.innerHTML += renderer(trampoline(compiled(null)));
+                    div.innerHTML += renderer(Cammy.runTrampoline(compiled(null)));
                     break;
                 default:
                     div.innerHTML += "Not sure how to display this yet.";

--- a/shell.nix
+++ b/shell.nix
@@ -11,14 +11,14 @@ in pkgs.stdenv.mkDerivation {
     # debugging native code
     gdb checksec
     # profiling RPython JITs
-    python3Packages.vmprof
+    # python3Packages.vmprof
     # maintaining embed/
     ocamlformat
     # maintaining movelist/
     egg2nix
     # maintaining cammy-rpy/
     # python2Packages.pyflakes
-    python3Packages.pyflakes
+    python39Packages.pyflakes
     # using cammy-comb
     graphviz
     # using cammy-draw
@@ -30,7 +30,7 @@ in pkgs.stdenv.mkDerivation {
     # working with JSON
     jq
     # honey
-    python3Packages.flask
+    python39Packages.flask
     # benchmarking
     busybox feedgnuplot linuxPackages.perf
     # publishing
@@ -43,9 +43,8 @@ in pkgs.stdenv.mkDerivation {
     sloccount
     # experimenting with hive management
     ranger
-    # ???
-    openapi-generator-cli yaml2json python3Packages.virtualenv
-    # !?!?
-    wabt binaryen
+    # experimenting with Honey
+    # openapi-generator-cli yaml2json python3Packages.virtualenv
+    purescript
   ];
 }