Add an under macro for bidirectional transformation

[masak]

So, I was checking out the examples, and came to the implementation of Nim addition:

func infix:<⊕>(lhs, rhs) is equiv(infix:<+>) {
    my lb = binfmt(lhs);
    my rb = binfmt(rhs);
    lb = padLeft(lb, rb.chars(), "0");
    rb = padLeft(rb, lb.chars(), "0");
    my result = 0;
    my p = 1;
    for (^lb.chars()).reverse() -> i {
        if lb.substr(i, 1) != rb.substr(i, 1) {
            result = result + p;
        }
        p = p * 2;
    }
    return result;
}

It got me thinking about the ideal shape this code "wants" to have. And suddenly a feature jumped out at me that I guess I've been half-thinking of for years — doing some calculation "under a transform":

func infix:<⊕>(lhs, rhs) is equiv(infix:<+>) {
    my result;
    under BitVectorTransform {
        result = zipPadLeft(lhs, rhs, padWith: 0).map(
            func (leftBit, rightBit) { return leftBit == rightBit ?? 0 !! 1 }
        );
    }
    return result;
}

Briefly:

• BitVectorTransform is a class, with two static methods: forward and backward.
• It might help to think of it as a generic class BitVectorTransform<Outer, Inner>, and the two methods as having signatures forward(o: Outer): Inner and backward(i: Inner): Outer.
• An under block gets code-generated to a regular block statement containing the original code, except variables declared outside this block are wrapped with forward or backward calls — depending on whether they are reads or writes, respectively.
• Forget for a moment that I'm using various conjectural/unimplemented features: ternary operator, parameter destructuring, and a named argument. Please also ignore the fact that zipPadLeft is kind of a bad idea (but the problem is genuine, and I encountered something very similar in the samefringe musing).

The BitVectorTransform class looks like what you'd expect:

class BitVectorTransform {
    @static method forward(input) {
        # ...convert number to bit vector...
    }

    @static method backward(output) {
        # ...convert bit vector to number...
    }
}

Technically, we should be able to skip the intermediate result variable, and just lean on the fact that a returned value also counts as "something passing out of the under block":

func infix:<⊕>(lhs, rhs) is equiv(infix:<+>) {
    under BitVectorTransform {
        zipPadLeft(lhs, rhs, padWith: 0).map(
            func ([leftBit, rightBit]) { return leftBit == rightBit ?? 0 !! 1 }
        );
    }
}

I'm just saying. It's starting to look attractive.

The idea of an under block must have been stewing in me for a while. I remember first being impressed by the "doing X under a transform" when I learned that logarithms turn multiplication into addition, and exponentiation into multiplication. There are also things like Fourier and Laplace transforms.

Something about the shape of the solution also reminds me of Python's with statement. But with is concerned with establishing a dynamic context, trapping control flow going in and out; here we're concerned with establishing a transformation, um, bubble — trapping values going in and out.

[vendethiel]

APL can actually do "under"... ish. Its Star Diaeresis (⍣) operator repeats an operation N times, but the number of times can actually be ¯1.

It's gonna be really hard to show a legible example, because of how APL reads in general, but I'll still try:

(×∘2)⍣¯1⊢3 ⍝ The whole operation
(×∘2)           ⍝ A partially applied multiplication operator, in Raku this'd be *×2
        ⍣¯1      ⍝ Repeated -1 times, inverse of this function
             ⊢3  ⍝ Applied to 3

This results in 1.5.

The way you could have "dual" would be to first, apply the "forward" operation, then apply the whole block, then apply the inverse of the "forward" operation.
I'm gonna post a "dual" here. I can detail it, but it's gonna be hard to read no matter what.
⍺⍺ is "function to the left", ⍵⍵ is "function to the right", and ⍵ is "argument to the right".

      f←{⍺⍺⍣¯1⊢⍵⍵⍺⍺⍵}
      (×∘2)f(+∘2)⊢5
6

(×∘2) is the function to the left (⍺⍺), (+∘2) is the function to the right (⍵⍵), 5 is the argument to the right (⍵).
So what happens is this:

(×∘2)⍣¯1⊢2+2×5

Which calculates (2*5+2)/2, 6.

A bit long-winded for a narrow use case, but the sentiment is the same. Dyalog APL Extended, which is an extension to Dyalog APL, has this "under" function as the operator ⍢.

[masak]

@vendethiel Thank you for the explanation. It's good to know about prior art. I agree APL is somewhat opaque, but (thanks to your explanations), I think I actually got it.

It feels to me the under macro is doing something more, semantically. The APL version passes around values fairly to transform forwards-and-backwards fairly explicitly. The under macro implicitly injects/wraps forward and backward calls around values which cross in and out (respectively) of the lexical environment of the under block.

I don't recall seeing that technique before; the closest thing it reminds me of is our treatment of free variables in quasi blocks (which turn into "direct lookups" per #410). Maybe variable interpolations in Raku regexes could be considered a variant of this pattern, too. under is lexically changing the "meaning" of free variables — I'm a bit surprised myself at how OK I am with that. It feels slightly related to exists (#292) and delete (#290) in that it "changes how we evaluate something" (but via a syntax transformation).