• R/O
  • HTTP
  • SSH
  • HTTPS

提交

标签
No Tags

Frequently used words (click to add to your profile)

javaandroidc++linuxc#windowsobjective-ccocoaqt誰得pythonphprubygameguibathyscaphec計画中(planning stage)翻訳omegatframeworktwitterdomtestvb.netdirectxゲームエンジンbtronarduinopreviewer

A categorical programming language


Commit MetaInfo

修订版213493bb130b7e9ce07d6803c1aac027f1819c5f (tree)
时间2021-08-14 10:29:57
作者Corbin <cds@corb...>
CommiterCorbin

Log Message

Implement list fusion.

We are fusing both intermediate lists and partially-consumed lists.

更改概述

差异

--- a/cammy.txt
+++ b/cammy.txt
@@ -49,9 +49,9 @@ succ : N → N
4949 Given x : 1 → X and f : X → X, pr(x, f) : N → X
5050
5151 nil : 1 → [X]
52-cons : X × [X] → X
53-Given f : X → Y, map(f) : [X] → [Y]
52+cons : X × [X] → [X]
5453 Given x : 1 → Y and f : X × Y → Y, fold(x, f) : [X] → Y
54+Given f : X → Y, map(f) = fold(nil, comp(pair(comp(fst, f), snd), cons)) : [X] → [Y]
5555
5656 Combinators with (*) are provided by OCaml by default; the others are in a
5757 stub module. Type-checking is achieved by copying the combinators into
--- /dev/null
+++ b/hive/list/gauss.cammy
@@ -0,0 +1 @@
1+(comp list/range nat/sum)
--- a/jelly/src/main.rs
+++ b/jelly/src/main.rs
@@ -8,8 +8,14 @@ fn load_tree(handle :&mut Read) -> std::io::Result<RecExpr<SymbolLang>> {
88 input.parse().map_err(|e| std::io::Error::new(std::io::ErrorKind::InvalidData, e))
99 }
1010
11+// Wadler 1989: https://www2.cs.sfu.ca/CourseCentral/831/burton/Notes/July14/free.pdf
1112 // Conal 2013: http://conal.net/blog/posts/optimizing-cccs
1213
14+// Rules with names ending in "-desugar" are directly transcribed from the underlying equality.
15+
16+// "free for X" means that the polymorphic type of X implies the underlying equality justifying
17+// the annotated rule, as in Wadler 1989.
18+
1319 fn main() -> std::io::Result<()> {
1420 let rules :&[Rewrite<SymbolLang, ()>] = &[
1521 rw!("comp-id-left"; "(comp id ?x)" => "?x"),
@@ -18,23 +24,29 @@ fn main() -> std::io::Result<()> {
1824
1925 rw!("ignore-absorb-left"; "(comp ?x ignore)" => "ignore"),
2026
27+ // free for fst
2128 rw!("fst-elim-pair"; "(comp (pair ?f ?g) fst)" => "?f"),
29+ // free for snd
2230 rw!("snd-elim-pair"; "(comp (pair ?f ?g) snd)" => "?g"),
2331 rw!("pair-fst-snd"; "(pair fst snd)" => "id"),
2432 // Conal 2013
2533 rw!("pair-precompose"; "(pair (comp ?r ?f) (comp ?r ?g))" => "(comp ?r (pair ?f ?g))"),
2634
35+ // free for left
2736 rw!("left-elim-case"; "(comp left (case ?f ?g))" => "?f"),
37+ // free for right
2838 rw!("right-elim-case"; "(comp right (case ?f ?g))" => "?g"),
2939 rw!("case-left-right"; "(case left right)" => "id"),
3040
3141 rw!("assl-assr-cancel"; "(comp assl assr)" => "id"),
3242 rw!("assr-assl-cancel"; "(comp assr assl)" => "id"),
3343
44+ // free for swap
3445 rw!("swap-pair"; "(comp (pair ?f ?g) swap)" => "(pair ?g ?f)"),
3546 rw!("pair-snd-fst"; "(pair snd fst)" => "swap"),
3647 rw!("swap-twice-cancel"; "(comp swap swap)" => "id"),
3748
49+ // free for dup
3850 rw!("dup-factor"; "(pair ?f ?f)" => "(comp ?f dup)"),
3951 rw!("dup-desugar"; "dup" => "(pair id id)"),
4052
@@ -52,6 +64,9 @@ fn main() -> std::io::Result<()> {
5264 rw!("nat-elim-pr"; "(pr zero succ)" => "id"),
5365
5466 rw!("list-elim-fold"; "(fold nil cons)" => "id"),
67+
68+ rw!("map-desugar"; "(map ?f)" => "(fold nil (comp (pair (comp fst ?f) snd) cons))"),
69+ rw!("map-fusion"; "(comp (map ?f) (map ?g))" => "(map (comp ?f ?g))"),
5570 ];
5671
5772 let tree = load_tree(&mut std::io::stdin())?;
--- a/todo.txt
+++ b/todo.txt
@@ -1,4 +1,5 @@
11 * list/eq : [X × X, 2] → [[X] × [X], 2]
22 * list/zip : [X] × [Y] → [X × Y]
33 * list/tail : [X] → [X]
4+* list/unfold : [Y, X × Y + 1] → [Y, [X]]
45 * rat