Alternative Locals Proposal

[dmbarbour]

At the moment, Kitten's support for locals require special support from the compiler, REPL, etc.. I recently developed a different approach to locals in context of my language, Awelon, in support of editable views. I think it might be a fine option for Kitten, too, assuming you're interested in simplicity.

Assume we have combinators:

[B][A] a == A[B]   (apply aka dip)
[B][A] b == [[B]A] (bind)
   [A] c == [A][A] (copy)
   [A] d ==        (drop)
   [A] i == A      (inline)

With these, we can easily rewrite a program to extract 'free variable' arguments:

T(X, E) - extract X from E such that:
      T(X,E) does not contain X
      [X] T(X,E) == E

T(X, E) | E does not contain X => d E
T(X, X) => i
T(X, [X]) =>
T(X, [E]) => [T(X,E)] b
T(X, F G)
    | only F contains X => T(X,F) G
    | only G contains X => [F] a T(X,G)
    | otherwise => c [T(X,F)] a T(X,G)

T(X,E) is is similar to the proof that SKI combinators can encode lambda calculus, tweaked for concatenative combinators. For -> X Y Z; CODE we assume [X][Y][Z] is on the stack and thus evaluating T(Z, T(Y, T(X, CODE))) will have the correct result.

A REPL could logically prepend each line with its environment:

[X] -> X; [Y] -> Y; [Z] -> Z; REPL LINE

Anyhow, this would give you locals without complicating your formal semantics, compiler, or runtime. I figured you might find this proposal interesting, even if you choose not to pursue it.

Besides support for named locals, I use the same algorithm for an optimization pass to support staged partial evaluations - i.e. evaluate [VN]...[V2][V1][V0]program as far as we can with undefined words, V0..VN, then extract those variables. This effectively gives me a similar behavior to lambda-calculus partial evaluations, and conveniently shifts any argument dropping to the front of the program.

Have fun.

Edits: minor perf enhancement, fix on order for processing X Y Z variables.

[evincarofautumn]

This is cool, thanks! Even if I don’t end up changing how locals work, I think this will turn out to be useful. The first thing that came to mind was to suggest avoiding locals when it makes the code simpler by some metric like size/nesting:

foo.ktn:99:2-8: suggestion: reduce '-> x; x x' to 'dup'
foo.ktn:42:2-24: suggestion: reduce '-> a, b, c; (a + b + c)' to '(+) (+)'

From a cursory look, it also seems more efficient than Kirby’s algorithm. I’d want to try it on real code, and probably have #153 at the ready to handle any intermediate closures that can’t be optimised out.

[dmbarbour]

I forgot that Kitten is using the lambda variables as value words, that is x is constrained to refer to a value. In that case, we can simplify a bit, and eliminate need for the i combinator:

T(X, E) - extract *value* X from E such that:
    T(X,E) does not contain X
    X T(X,E) == E

T(X,E) | E does not contain X => d E
T(X,X) =>
T(X,[E]) => [T(X,E)] b
T(X, F G)
    | only F contains X => T(X,F) G
    | only G contains X => [F] a T(X,G)
    | otherwise => c [T(X,F)] a T(X,G)

This changes the T(X,X) rule and eliminates the T(X,[X]) rule, but we've added a constraint that X is a single stack value. (In the original algorithm, X could be any complete subprogram.)

[dmbarbour]

I have discovered a potential issue with this translation: when we express conditional behaviors with multiple branches (like [onTrue][onFalse]if), we will copy our value into each branch, then select just one branch for evaluation which renders the copies useless.

I expect there are zero-copy solutions to this based on specializing for conditional decisions and staging the rewrite. That is, each conditional branch is rewritten internally, and we provide a unified stack to each of the branches. After I develop a suitable algorithm for Awelon, I'll be sure to let you know. :)

[evincarofautumn]

I figured out the value version from your original code. :)

I’m not too concerned about copying. It’s generally expected if you capture a variable in multiple closures. And if a conditional combinator is implemented in terms of Kitten’s if, it won’t construct closures when inlined anyway.

[dmbarbour]

So, I know you don't need it for Kitten, but I did find a simple solution for avoiding construction of unnecessary closures in Awelon where booleans are just Church-encoded functions and interpreted evaluation is not uncommon. It is sufficient to add a rule of form:

T(X, [onT][onF] if) => [T(X, onT)][T(X, onF)] if

Which is a simpler way to say:

T(X, [onT][onF] if) => T(X, X [-> X; onT] [-> X; onF] if)

Essentially we leave X on the stack and assume that if will apply only one of the two branches in a structured way. This generalizes easily to other conditional behaviors, too.