Racket list deforestation

[dzoep]

Summary of Changes

• introduce new bindings for deforested racket/base and racket/list procedures
• use literal matching on the new bindings in deforestation pass
• provide the new bindings from qi/list in place of the originals bindings
• add scribblings for the new bindings with links to original Racket documentation
• deforested take from racket/list using "state consing"
• added new tests and fixed some existing to work with the new changes

Public Domain Dedication

• [x] In contributing, I relinquish any copyright claims on my contribution and freely release it into the public domain in the simple hope that it will provide value.

(Why: The freely released, copyright-free work in this repository represents an investment in a better way of doing things called attribution-based economics. Attribution-based economics is based on the simple idea that we gain more by giving more, not by holding on to things that, truly, we could only create because we, in our turn, received from others. As it turns out, an economic system based on attribution -- where those who give more are more empowered -- is significantly more efficient than capitalism while also being stable and fair (unlike capitalism, on both counts), giving it transformative power to elevate the human condition and address the problems that face us today along with a host of others that have been intractable since the beginning. You can help make this a reality by releasing your work in the same way -- freely into the public domain in the simple hope of providing value. Learn more about attribution-based economics at drym.org, tell your friends, do your part.)

[countvajhula]

The more I think about it, I do not like providing bindings from Qi that have Racket syntax (which we discussed in today's meeting, in a separate qi/deforest). I understand that it provides an easy transition from Racket-syntaxed list operations to Qi-syntaxed list operations over the course of development of deforestation, so it could be an acceptable compromise. I'd love to get more thoughts on it in the form of code review.

My preference would be to work out the proper interface together as part of merging this PR, and in addition, provide only Qi-syntaxed bindings from Qi libraries like qi/list. It's OK if it doesn't include all the bindings in racket/list out of the gate, since users could require them and use them as partial application forms, without deforestation, which is anyway already the case. I feel the majority of interfaces in racket/list are not widely used so I'm not sure it is a top priority to be comprehensive on day one.

In any case, having a clean interface now would unblock the deforestation efforts in earnest and I wouldn't be paranoid and watching over your shoulder @dzoep . Until then, I hesitate 😅

[benknoble]

I won't have time ahead of today's meeting, but I do intend to resolve any of my comments that are no longer needed. (If anyone else happens to go through them, that's fine too.)

[benknoble]

I've marked many comments resolved, but left open the ones that aren't addressed and that I think should still be (or at least should be considered).

I also still get an error in qi-sdk when trying to build locally.

[benknoble]

Also, it looks like there are some whitespace oddities. For example, try using the git-jump script from Git's contrib directory with this branch checked out:

git jump ws main..

Here's the resulting fix list:

qi-doc/scribblings/list-operations.scrbl:4: space before tab in indent.
+           racket/base)]
qi-doc/scribblings/list-operations.scrbl:94: space before tab in indent.
+      ((list-ref (lst pair?) (pos exact-nonnegative-integer?)) any/c))]{
qi-doc/scribblings/list-operations.scrbl:117: new blank line at EOF.
qi-lib/flow/core/compiler/1000-qi0.rkt:16: trailing whitespace.
+  
qi-lib/flow/core/compiler/2000-bindings.rkt:73: new blank line at EOF.
qi-lib/flow/core/compiler/deforest/bindings.rkt:20: trailing whitespace.
+  

[benknoble]

For the conflicts, I started the merge and then ran git log --oneline --left-right --merge -p to get the following, which shows that resolving the conflicts is probably straightforward:

< 06644b9 Fix tests of qi/list - use the new bindings.
diff --git a/qi-test/tests/compiler/rules/full-cycle.rkt b/qi-test/tests/compiler/rules/full-cycle.rkt
index 3b4535b..5aaca6b 100644
--- a/qi-test/tests/compiler/rules/full-cycle.rkt
+++ b/qi-test/tests/compiler/rules/full-cycle.rkt
@@ -11,6 +11,7 @@
          rackunit/text-ui
          syntax/macro-testing
          qi/flow/core/compiler/0100-deforest
+         qi/list
          "private/deforest-util.rkt"
          (submod qi/flow/extended/expander invoke))

< ed36927 Improve directory and module naming
diff --git a/qi-test/tests/compiler/rules/full-cycle.rkt b/qi-test/tests/compiler/rules/full-cycle.rkt
index 5b16f09..3b4535b 100644
--- a/qi-test/tests/compiler/rules/full-cycle.rkt
+++ b/qi-test/tests/compiler/rules/full-cycle.rkt
@@ -10,7 +10,7 @@
          rackunit
          rackunit/text-ui
          syntax/macro-testing
-         qi/flow/core/passes/pass-0100-deforest
+         qi/flow/core/compiler/0100-deforest
          "private/deforest-util.rkt"
          (submod qi/flow/extended/expander invoke))

< 8383bcf Split compiler passes into separate modules.
diff --git a/qi-test/tests/compiler/rules/full-cycle.rkt b/qi-test/tests/compiler/rules/full-cycle.rkt
index 52d21a9..5b16f09 100644
--- a/qi-test/tests/compiler/rules/full-cycle.rkt
+++ b/qi-test/tests/compiler/rules/full-cycle.rkt
@@ -10,7 +10,7 @@
          rackunit
          rackunit/text-ui
          syntax/macro-testing
-         qi/flow/core/deforest
+         qi/flow/core/passes/pass-0100-deforest
          "private/deforest-util.rkt"
          (submod qi/flow/extended/expander invoke))

> 515122f More direct "full cycle" compiler test macro
diff --git a/qi-test/tests/compiler/rules/full-cycle.rkt b/qi-test/tests/compiler/rules/full-cycle.rkt
index 52d21a9..e7e1749 100644
--- a/qi-test/tests/compiler/rules/full-cycle.rkt
+++ b/qi-test/tests/compiler/rules/full-cycle.rkt
@@ -11,22 +11,15 @@
          rackunit/text-ui
          syntax/macro-testing
          qi/flow/core/deforest
+         qi/flow/core/compiler
          "private/deforest-util.rkt"
          (submod qi/flow/extended/expander invoke))

 (begin-for-syntax
-  (require syntax/parse/define
-           (for-template qi/flow/core/compiler)
-           (for-syntax racket/base))
-
-  ;; A macro that accepts surface syntax, expands it, and then applies the
-  ;; indicated optimization passes.
-  (define-syntax-parser test-compile~>
-    [(_ stx)
-     #'(expand-flow stx)]
-    [(_ stx pass ... passN)
-     #'(passN
-        (test-compile~> stx pass ...))]))
+  ;; A function that expands and compiles surface syntax
+  (define (qi-compile stx)
+    (compile-flow
+     (expand-flow stx))))

 (define tests
@@ -39,9 +32,8 @@ (define tests
     (test-true "normalize → deforest"
                (deforested?
                  (phase1-eval
-                  (test-compile~> #'(~>> (filter odd?) values (map sqr))
-                                  normalize-pass
-                                  deforest-pass)))))))
+                  (qi-compile
+                   #'(~>> (filter odd?) values (map sqr)))))))))

 (module+ main
   (void

In fact, it's probably a good idea to try rebasing on top of the latest main (and dropping ade291f (doc: link to ways to enter the ☯ symbol, 2024-05-06) that snuck in there from 070ffc5 (doc: link to ways to enter the ☯ symbol, 2024-05-06)) at some point.