A categorical programming language
| 修订版 | ff384e39f1a4342afc72e1e7b1abe6650caf934a (tree) |
|---|---|
| 时间 | 2022-04-12 12:25:31 |
| 作者 | Corbin <cds@corb...> |
| Commiter | Corbin |
Fix an incorrect optimization.
cammy-rpy/draw.py (diff)
hive/demo/burning-ship-color.cammy (diff) jelly/src/main.rs (diff)
todo.txt (diff)| @@ -2,7 +2,7 @@ | ||
| 2 | 2 | |
| 3 | 3 | import math, sys |
| 4 | 4 | |
| 5 | -from rpython.rlib.jit import JitDriver, unroll_safe #, set_param | |
| 5 | +from rpython.rlib.jit import JitDriver, unroll_safe, set_param | |
| 6 | 6 | from rpython.rlib.rfile import create_stdio |
| 7 | 7 | from rpython.rlib.rfloat import string_to_float |
| 8 | 8 | from rpython.rlib.rstring import StringBuilder, split |
| @@ -98,7 +98,7 @@ def drawPNG(program, filename, corners, width, height): | ||
| 98 | 98 | |
| 99 | 99 | |
| 100 | 100 | def main(argv): |
| 101 | - # set_param(None, "trace_limit", 50001) | |
| 101 | + set_param(None, "trace_limit", 50001) | |
| 102 | 102 | |
| 103 | 103 | prog = argv[1] |
| 104 | 104 | window = [string_to_float(s) for s in split(argv[2])] |
| @@ -1,7 +1,7 @@ | ||
| 1 | 1 | (comp |
| 2 | 2 | (comp |
| 3 | - (fractal-membership-color v2/burning-ship (comp nat/8 succ)) | |
| 4 | - (monads/maybe/guard (pair/of nat/lte id (fun/const nat/8)))) | |
| 3 | + (fractal-membership-color v2/burning-ship (comp nat/16 succ)) | |
| 4 | + (monads/maybe/guard (pair/of nat/lte id (fun/const nat/16)))) | |
| 5 | 5 | (case |
| 6 | 6 | (comp (comp nat/to-f f/radians-to-turns) h2rgb) |
| 7 | 7 | (v3/broadcast f-zero))) |
| @@ -26,7 +26,7 @@ fn load_tree(handle :&mut Read) -> std::io::Result<RecExpr<SymbolLang>> { | ||
| 26 | 26 | |
| 27 | 27 | // Rules marked "associative!" can cause explosions. |
| 28 | 28 | |
| 29 | -// Rules marked "improvement!" can improve IEEE 754 results in both precision and accuracy, so | |
| 29 | +// Rules marked "improvement!" can improve IEEE 754 results in both precision and/or accuracy, so | |
| 30 | 30 | // cannot be run backwards. |
| 31 | 31 | |
| 32 | 32 | fn main() -> std::io::Result<()> { |
| @@ -95,7 +95,7 @@ fn main() -> std::io::Result<()> { | ||
| 95 | 95 | |
| 96 | 96 | rw!("list-elim-fold"; "(fold nil cons)" => "id"), |
| 97 | 97 | rw!("list-unroll-fold-nil"; "(comp nil (fold ?x ?f))" => "?x"), |
| 98 | - rw!("list-unroll-fold-cons"; "(comp cons (fold ?x ?f))" => "(comp (pair fst (fold ?x ?f)) ?f)"), | |
| 98 | + rw!("list-unroll-fold-cons"; "(comp cons (fold ?x ?f))" => "(comp (pair fst (comp snd (fold ?x ?f))) ?f)"), | |
| 99 | 99 | |
| 100 | 100 | // 2 = 1 + 1 |
| 101 | 101 | rw!("bool-t-either"; "(comp t either)" => "left"), |
| @@ -141,7 +141,7 @@ fn main() -> std::io::Result<()> { | ||
| 141 | 141 | ]; |
| 142 | 142 | |
| 143 | 143 | let tree = load_tree(&mut std::io::stdin())?; |
| 144 | - eprintln!("Input expression has cost {}", AstSize.cost_rec(&tree)); | |
| 144 | + eprintln!("Input expression has size {}", AstSize.cost_rec(&tree)); | |
| 145 | 145 | |
| 146 | 146 | let runner = Runner::default().with_expr(&tree).run(rules); |
| 147 | 147 | eprintln!("E-graph finished running: {:?} after {} iterations", runner.stop_reason.unwrap(), |
| @@ -149,7 +149,8 @@ fn main() -> std::io::Result<()> { | ||
| 149 | 149 | |
| 150 | 150 | let mut extractor = Extractor::new(&runner.egraph, AstSize); |
| 151 | 151 | let (best_cost, best_expr) = extractor.find_best(runner.roots[0]); |
| 152 | - eprintln!("Best expression has cost {}", best_cost); | |
| 152 | + // eprintln!("Best expression has size {} and cost {}", best_cost); | |
| 153 | + eprintln!("Input expression has size {}", AstSize.cost_rec(&best_expr)); | |
| 153 | 154 | |
| 154 | 155 | std::io::stdout().write_all(best_expr.pretty(78).as_bytes()); |
| 155 | 156 | std::io::stdout().write_all(b"\n") |
| @@ -89,12 +89,22 @@ | ||
| 89 | 89 | * Homs: pointer to heap-allocated array of two cells |
| 90 | 90 | * The first cell is a code pointer |
| 91 | 91 | * The second cell is the curried data |
| 92 | -* Finish CAM | |
| 93 | - * curry/uncurry: write code to new code area, jump to code, call stack | |
| 94 | - * pr/fold: test and jump | |
| 95 | - * pr: pred? | |
| 96 | - * fold: testing for nil, pushing cells in correct order, pairing | |
| 97 | - * lists should use cons cells | |
| 98 | - * current lists are more like arrays... | |
| 92 | +* Optimize CAM | |
| 93 | + * Peepholes: Several standard improvements are possible | |
| 94 | + * Atomic instruction emitters would be augmented with ability to look | |
| 95 | + backwards and cancel out or amend previous instructions | |
| 96 | + * Taking a label would create a code barrier, to avoid having to | |
| 97 | + recompute jumps | |
| 98 | + * TCO, or really any call optimizations | |
| 99 | + * snoc and other backwards versions of ops | |
| 99 | 100 | * fun/precomp is an ingredient of CPS transformation |
| 100 | 101 | * https://okmij.org/ftp/continuations/undelimited.html |
| 102 | +* A serious cost model | |
| 103 | + * Current jelly cost model is AstSize | |
| 104 | + * O(1) is incorrect for some operations | |
| 105 | + * Even constant ops have differing costs | |
| 106 | + * New cost model based on CAM | |
| 107 | + * id, comp, cons are all free now! | |
| 108 | + * fst, snd are "term ops", don't touch stack | |
| 109 | + * so is nearly all of ALU, but fst, snd are also removable by JIT | |
| 110 | + * in general, ALU ops are more expensive than stack ops! |
Fork