Approaches to for/fold notation

[rocketnia]

In today's Rhombus meeting, for/fold came up as a particular place where Shrubbery notation might be lacking. I mentioned that it was like a form of primitive recursion.

Primitive recursion is a limited kind of recursion where the recursion must proceed on a smaller structure than the input. It's used in total functional languages to guarantee that recursive operations over inductive data types terminate. Nowadays, languages like Agda can figure out the termination guarantees a lot more kinds of recursion, and users don't have to specify what "input" they're recursing over like they do when they use primitive recursion directly.

Primitive recursion over a cons list is foldr. Its inputs, in some order, are:

• A handler for nil: A function of no arguments that returns a state.
• A handler for cons: A function that takes an element (the car) and a state (the result of recursion over the list in the cdr) and returns a state.

And the result is:

• A handler for any list: A function of one argument that takes a list and returns a state.

This isn't exactly the signature of Racket's foldr, but it's easy to implement something like this in terms of Racket's foldr and vice versa.

Anyhow, if we want to make a syntax that has a handler for nil and a handler for cons, I think it could look similar to a match form.

Here's an example of for/foldr in the docs:

> (for/foldr ([acc '()] #:delay)
            ([v (in-range 1 4)])
    (printf "--> ~v\n" v)
    (begin0
      (cons v (force acc))
      (printf "<-- ~v\n" v)))
--> 1
--> 2
--> 3
<-- 3
<-- 2
<-- 1
'(1 2 3)

Apologies for how unfamliiar I am with the Rhombus prototype, but I imagine something shaped roughly like this pseudocode could work:

for_foldr in_range(1, 4) ~delay
| StreamNil(): []
| StreamCons(v, acc):
    printf("--> ~v\n", v)
    val result: Cons(v, force(acc))
    printf("<-- ~v\n", v)
    result

And for for/fold rather than for/foldr, we would be doing primitive recursion over a snoc list rather than a cons list:

> (for/fold ([sum 0]
             [rev-roots null])
           ([i '(1 2 3 4)])
    (values (+ sum i) (cons (sqrt i) rev-roots)))
10
'(2 1.7320508075688772 1.4142135623730951 1)

for_fold [1, 2, 3, 4]
| StreamLin(): values(0, [])
| StreamSnoc(values(sum, rev_roots), i):
    values(sum + i, Cons(sqrt(i), rev_roots))

(Putting values(...) in the argument of another pattern might be suspect. That's one of many things that makes this pseudocode.... 😅 )

Another option here could be to make these folding styles more integrated into match by having a special recur pattern...

match in_range(1, 4)
| StreamNil(): []
| StreamCons(v, recur(acc, ~delay)): Cons(v, force(acc))

match [1, 2, 3, 4]
| StreamLin(): values(0, [])
| StreamSnoc(recur(values(sum, rev_roots)), i):
    values(sum + i, Cons(sqrt(i), rev_roots))

I realize none of these are very for-like, since the variables aren't close to the expressions that produce them (v and in_range(1, 4); acc and the branch results; i and [1, 2, 3, 4]; and values(sum, rev_roots) and the branch results). A for form probably doesn't need to have the verbosity of StreamNil, StreamCons, StreamLin, and StreamSnoc either, since for forms are specialized to streams.

So, another option could be something more like this, where the variables v and i are brought closer to the streams producing them and the variables acc and values(sum, rev_roots) are brought into the header so they can apply to both branch results:

for_foldr ~delay acc ~over v ~in in_range(1, 4)
| ~begin: []
| ~entry: Cons(v, force(acc))

for_fold values(sum, rev_roots) ~over i ~in [1, 2, 3, 4]
| ~end: values(0, [])
| ~item: values(sum + i, Cons(sqrt(i), rev_roots))

These examples only have one stream each. To accommodate multiple streams, it might help to adjust the syntax so the streams are declared as part of a block. So here's yet another possible take on things:

for:
  entry v: in_range(1, 4)
  foldr ~delay acc
  | []
  | Cons(v, force(acc))

for:
  entry i: [1, 2, 3, 4]
  fold values(sum, rev_roots)
  | values(0, [])
  | values(sum + i, Cons(sqrt(i), rev_roots))

These are just some possible ideas on my mind. Feel free to take this thread wherever you like.

I searched around for some existing discussion on this but didn't quite find any. I'm aware of https://github.com/samdphillips/rhombus-examples but not really aware of where everyone else is keeping their Rhombus prototype experiments, so I might have overlooked some obvious for/fold tinkering that's already been going on somewhere.

[AlexKnauth]

A form like this in S-Expression notation:

(for/foldr ([acc '()] #:delay)
           ([v (in-range 1 4)])
  (printf "--> ~v\n" v)
  (begin0
    (cons v (force acc))
    (printf "<-- ~v\n" v)))

Would be written like this in the current version of Wraith:

for/foldr [acc '() & #:delay]
          [v (in-range 1 4)]
  printf "--> ~v\n" v
  begin0
    cons v (force acc)
    printf "<-- ~v\n" v

And this Wraith version works as-is without having to define a new for/foldr macro: just reusing the existing Racket macro works just fine.

By contrast Shrubbery-Rhombus macros need to be written specifically for Shrubbery... If I were to define a macro in Shrubbery to do this it might look something like this:

for_foldr ((acc: [], ~delay),
           (v: in_range(1, 4))):
  printf("--> ~v\n", v)
  begin0:
    cons(v, force(acc))
    printf("<-- ~v\n", v)

Which needs an extra grouping of parens that Racket's for/foldr doesn't need, to let the "init" bindings and the "iter" bindings be put on the same indentation level.

If I changed the lexer for identifiers and relaxed the indentation and : block syntax of Shrubbery to be just a little bit more like Wraith, I could get this to:

for/foldr (acc: [], ~delay)
          (v: in-range(1, 4)):
  printf("--> ~v\n", v)
  begin0:
    cons(v, force(acc))
    printf("<-- ~v\n", v)

Which would be consistent with a possible bridge to S-Expression notation that parsed to the same tree as the original Racket and Wraith examples.

[AlexKnauth]

@spdegabrielle

You mentioned a hybrid approach briefly in the meeting on Thursday. I'd be interested in seeing what that could look like?

One example of something in the space between Shrubbery and Wraith is what I wrote in the comment above:

for/foldr (acc: [], ~delay)
          (v: in-range(1, 4)):
  printf("--> ~v\n", v)
  begin0:
    cons(v, force(acc))
    printf("<-- ~v\n", v)

But I would currently lean more toward this below which is a just little bit closer to Wraith than that:

for/foldr [acc: [], ~delay]
          [v: in-range 1 4]:
  printf "--> ~v\n" v
  begin0
    cons v (force acc)
    printf "<-- ~v\n" v

With an S-Expression bridge that would parse it as:

(for/foldr [(acc []) #:delay]
           [(v (in-range 1 4))]
  (printf "--> ~v\n" v)
  (begin0
    (cons v (force acc))
    (printf "<-- ~v\n" v)))

I'm curious about people's opinions between these: the main difference is whether function calls can look like f(a, b, c) or f a b c. The main advantage of the former is that it looks like familiar "algebra notation", and it also has an advantage of distinguishing zero-argument function calls f(). The main advantage of the latter from my perspective is that it works more consistently with my ideas for an S-Expression bridge.

[mflatt]

Here's something I've been experimenting with in https://github.com/mflatt/rhombus-prototype/tree/for (just a partial implementation, no documentation). It's related to @rocketnia's "streams are declared as part of a block".

In the example below,~each is similar to @rocketnia's entry, using a keyword to clarify that it's not a macro-extensible position (more on that below), and ~and is like ~each but to continue a parallel group:

fun enumerate(l :: List):
  for:
    ~each v: l
    ~and  i: 0..
    displayln(i & ". " & v)

enumerate(["a", "b", "c"])

// prints
//  0. a
//  1. b
//  2. c

In this example, l has the static information List, and List is bound so that thefor expansion uses in-list. The .. operator is in-range or in-naturals, depending on whether it has a second argument, so in-naturals above.

A "folder" can appear after for, where List is bound as a folder that creates a list:

fun grid(m, n):
  for List:
    ~each i: 0..m
    ~each j: 0..n
    [i, j]

grid(2, 3) // => [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]]

Similarly, values is bound as a folder form:

fun sum(l :: List):
  for values(sum = 0):
    ~each i: l
    sum+i

sum([2, 3, 4]) // => 9

You could imagine a ~right modifier for values that makes it foldr, and so on.

These for examples are probably easy to read for someone familiar with Racket's for forms, but I'm not sure they'd make sense to someone accustomed to for in other languages. Maybe a different word would help?

Meanwhile, an advantage of putting element bindings in the body is that no special syntax like #:do is needed to put things between ~each clauses:

fun grid2(m, n):
  for List:
    ~each i: 0..m
    val k: i + 1
    ~each j: 0..n
    [k, j]

grid2(2, 3) // => [[1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

The current experiment doesn't yet have ~when and ~unless, but they'd work within the body, too. Note that a ~when could be inserted into an existing body after a local binding; there's no need to rearrange definitions to fit some in a special iteration section (analogous to in-value or #:do).

The current experiment also doesn't quite parse in the right way, because it's too eager about expanding the right-hand side of ~each or ~and to propagate static information. The new #:do form in for/fold from racket/base helps, but a further change would be need to allow delayed generation of binding clauses — if something like this approach to for for Rhombus works out otherwise. Edit: a for2 branch uses a new #:splice clause form in for from racket/base to get the expansion order right.

I'm not sure about using a keyword for ~each (as well as ~and, ~when, ~unless, ~break, etc.). A plain identifier could work, and using identifiers would further suggests macros that expand to element-binding clauses; I don't think there's a technical obstacle to that approach. But using keywords (and not allowing macros don't expand to them) makes the loop-structuring clauses more apparent; in that way, it's is closer to the constrained for shape of racket/base.

[mflatt]

I've pushed a more complete implementation with documentation to the main branch. Of course, it's as tentative and subject to further discussion as everything else.

[jackfirth]

So here's some design questions:

1. Racket's for* is unique in that it allows implicit nesting. Most languages would just have you express nested iteration with nested for loops. There are some advantages to that approach: it makes nesting a lot more apparent and it simplifies the grammar of for statements. Do we think implicit nesting à la for* is worth dedicated syntax in Rhombus?

2. Is the .. syntax specific to for loops, or is it intended to be an operator that can be used in any expression? I think a..b constructing a collection or sequence of some kind would be useful.

3. for/fold seems to inhabit a space between using for forms with mutation and stream pipelines with transducers and reducers. How much use do we expect this space to get? What if it turns out that most for/fold loops would be better written as either stream pipelines or plain old for loops with some mutable state?

[plane]

I think ideally there would be a nice syntax for an append-map type operation with for, ideally allowing you to build your output data structures without generating lots of intermediate forms.

[mflatt]

To record some answers from today's meeting:

1. Yes. Slightly longer answer: see notes for January 20 meeting.
2. An operator that can be used in any expression, analogous to (and currently implemented exactly as) in-range or in-naturals
3. We agree that for[/fold] is on a curve stretching from old recursive functions to transducers.