A categorical programming language
修订版 | b8a799e5bd63d1760337d688ab95dc417edfc0b0 (tree) |
---|---|
时间 | 2023-01-04 15:36:05 |
作者 | Corbin <cds@corb...> |
Commiter | Corbin |
Try a new approach to compiling to WASM.
This is based on a graph-and-ports architecture, as used in Elliott's
"Compiling to Categories" and almost certainly elsewhere.
@@ -4,6 +4,53 @@ | ||
4 | 4 | |
5 | 5 | (import (cammyo)) |
6 | 6 | |
7 | +; A port is one of: | |
8 | +; - a typed WASM local | |
9 | +; - nothing: '() | |
10 | +; - a pair of ports: '(pair p1 p2) | |
11 | +; See Chapter 7 of | |
12 | +; http://conal.net/papers/compiling-to-categories/compiling-to-categories.pdf | |
13 | + | |
14 | +; A port context is a pair (p, ls) containing a port and a list of WASM locals. | |
15 | + | |
16 | +; Port <-> WAT Ty × WAT Insts × WAT Insts | |
17 | +(define (port-alloc° p ty before after) | |
18 | + (fresh (len) (lengtho before len) (conso len ty p) (conso ty before after))) | |
19 | + | |
20 | +; Ignore inputs and generate outputs of the given type. | |
21 | +; WAT Ty <-> Context × Context | |
22 | +(define (context-elt° t input output) | |
23 | + (fresh (po ins outs) | |
24 | + (cdro input ins) | |
25 | + (conso po outs output) | |
26 | + (port-alloc° po t ins outs))) | |
27 | + | |
28 | +; Consume inputs and generate outputs of the given type. | |
29 | +; WAT Ty × WAT Ty <-> Context × Context | |
30 | +(define (context-prim° s t input output) | |
31 | + (fresh (pi po ins outs) | |
32 | + (conso pi ins input) (cdro pi s) | |
33 | + (conso po outs output) | |
34 | + (port-alloc° po t ins outs))) | |
35 | + | |
36 | +; Relate expressions to operations and input+output port contexts. | |
37 | +; Cammy <-> WAT Insts × Port × Port | |
38 | +(define (ops-ports° expr insts input output) | |
39 | + (conde | |
40 | + ((== expr 'id) (nullo insts) (== input output)) | |
41 | + ((== expr 'ignore) (nullo insts) (fresh (ps) (cdro input ps) (conso '() ps output))) | |
42 | + ((== expr 'fst) (nullo insts) | |
43 | + (fresh (ps s t _p) (conso s ps input) (conso t ps output) | |
44 | + (== s `(pair ,t ,_p)))) | |
45 | + ((== expr 'zero) (== insts '((i32.const 0))) | |
46 | + (context-elt° 'i32 input output)) | |
47 | + ((== expr 'succ) (== insts '((i32.const 1) (i32.add))) | |
48 | + (context-prim° 'i32 'i32 input output)) | |
49 | + ((fresh (f g finsts ginsts ctx) | |
50 | + (== expr `(comp ,f ,g)) (appendo finsts ginsts insts) | |
51 | + (ops-ports° f finsts input ctx) (ops-ports° g ginsts ctx output))) | |
52 | + )) | |
53 | + | |
7 | 54 | ; Create a fresh symbol ala (gensym s) and bind it to a logic variable. |
8 | 55 | ; Meant for creating fresh locals for WASM. |
9 | 56 | ; string -> WAT Symbol |
@@ -22,7 +69,7 @@ | ||
22 | 69 | ; Cammy <-> WAT Insts |
23 | 70 | (define (stack-ops° expr ops) |
24 | 71 | (conde |
25 | - ((== expr 'id) (== ops '())) | |
72 | + ((== expr 'id) (nullo ops)) | |
26 | 73 | ((fresh (f g x y) (== expr `(comp ,f ,g)) (stack-ops° f x) (stack-ops° g y) (appendo x y ops))) |
27 | 74 | ; 1 |
28 | 75 | ((== expr 'ignore) (== ops '((drop)))) |
@@ -110,6 +157,7 @@ | ||
110 | 157 | (appendo decls body func) |
111 | 158 | )) |
112 | 159 | |
160 | +; The relational boundary for compiling a single function. | |
113 | 161 | (define (wasm-func expr name) |
114 | 162 | (car (run 1 (func) (wasm-func° expr name func)))) |
115 | 163 |
@@ -128,9 +176,19 @@ | ||
128 | 176 | (global.set $bump))) |
129 | 177 | funcs)) |
130 | 178 | |
131 | -(let* | |
132 | - ((expr (read)) | |
133 | - (func (wasm-func expr '$main))) | |
134 | - (begin | |
135 | - (pp (wasm-module (list func))) | |
136 | - (newline))) | |
179 | +; (let* | |
180 | +; ((expr (read)) | |
181 | +; (func (wasm-func expr '$main))) | |
182 | +; (begin | |
183 | +; (pp (wasm-module (list func))) | |
184 | +; (newline))) | |
185 | + | |
186 | +(define results | |
187 | + (run 1 (q) | |
188 | + (fresh (insts input output inp outp) | |
189 | + (ops-ports° (read) insts input output) | |
190 | + (caro input inp) (caro output outp) | |
191 | + (== q `(wip (insts ,insts) (input ,inp) (output ,outp)))))) | |
192 | + | |
193 | +(pp (car results)) | |
194 | +(newline) |