Lambdas in Tacit Code

While tacit programming is an excellent default, it is not suitable for all use cases. Attempting to use tacit programming everywhere results in pointlessly onerous data shuffling. A few local names, in the form of lambdas and let expressions and lexical closures, can simplify a useful subset of code, making it easier to read and write. Many tacit languages, including Factor and Kitten, provide an ‘escape’ from the tacit style. Factor uses a macro rewrite, while Kitten treats this as a primitive feature with support from the syntax and runtime.

I am developing a tacit concatenative language, Awelon. Unlike conventional programming languages, Awelon takes an approach of storing code with a simple, uniform syntax in a database, and minimizing the core language. Awelon has become considerably simpler since last time I discussed it on this blog. If you’re interested, I encourage you peruse the linked documentation. The core of Awelon is just four primitive combinators:

Awelon Primitive Combinators
[B][A]a == A[B]           (apply)
[B][A]b == [[B]A]         (bind)
   [A]c == [A][A]         (copy)
   [A]d ==                (drop) 

Awelon additionally has syntactic sugar for natural numbers and text literals, and parenthetical annotations like `(nat)`, `(memo)`, or `(par)` for performance and debugging. But all observable behavior and data is ultimately defined in terms of the four combinators. All data is logically Church or Scott encoded as functions, even if accelerated under the hood. Because Awelon’s syntax and semantics is very simple at the storage layer, I leverage editable views for presenting a more sophisticated view to the programmer. For example, a proposed view might expand decimal number `3.141` to `[[3141 0 integer] 3 decimal]`. And `-4/6` to `[[0 4 integer] 6 rational]`.

For Awelon, an escape from the tacit style should also be an editable view – a bit like Factor’s macro expansion, but reversible because I’ll be storing the tacit representation. How to accomplish this, exactly, didn’t really click for me until yesterday when I was reviewing the Wikipedia article on combinatory logic and specifically the translation from lambda calculus to SKI combinators. I can apply a similar translation to extract lambda variables from Awelon code:

Extract to Argument
   T(X,E) extracts X from E
   ∀X,E. [X] T(X,E) == E
   T(X,E) does not contain X

T(X, E) | E does not contain X => d E
T(X, X) => i  (where [A]i == A)
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)

We can implement i = [][]b a a d

This is a simple algorithm that generates efficient code. The translation is ‘reversible’ by partial evaluation of `[X] T(X,E)` to propagate the variable back into the rendered view. The rules can be simplified a bit (no need for `i`) if we assume X is a value and instead extract to `X T(X,E)`.

I find Factor’s syntax for named locals to be headache inducing. But Kitten’s `→ X;` assignment syntax is reasonably aesthetic and effectively supports both lambdas and let expressions. Consider an adaptation of Kitten’s syntax for named locals to Awelon:

View: → X; X
Source: (λ X) i

View: → X Y Z; X foo [Y] bar
Source: (λ X Y Z) d [i foo] a bar

View: 7 → X; X X * X -
Source: 7 (λ X) c a c a [*] a i -

Here the `(λ X)` is an annotation or comment that tells our editable view that we intend to present the code as a lambda expression with a specific variable name ‘X’. The details of its representation aren’t essential. What does matter is that we can use the comment to systematically recover the view from source:

Source: (λ X) i
View: → X; [X] i  
  => → X; X

Source: (λ X Y Z) d [i foo] a bar
View: → X Y Z; [X][Y][Z] d [i foo] a bar
  => → X Y Z; [X][Y][i foo] a bar      (dropped Z)
  => → X Y Z; [X]i foo [Y] bar         (apply a)
  => → X Y Z; X foo [Y] bar            (apply i)

Source: 7 (λ X) c a c a [*] a i -
View: 7 → X; [X] c a c a [*] a i -
  => 7 → X; [X] [X] a c a [*] a i -
  => 7 → X; X [X] c a [*] a i -
  => 7 → X; X X [X] [*] a i -
  => 7 → X; X X * [X] i -
  => 7 → X; X X * X -

It seems to work, though we may need to limit partial evaluations based on the patterns in ‘extract to argument’ to avoid evaluating parts of code irrelevant to the lambda.

Awelon programmers will have named locals where convenient without entangling names with syntax or semantics. This has me feeling more confident in my decision to favor concatenative combinators as a simpler base for computation than lambda calculus.

Addendum: To avoid unnecessary copying, we can introduce specialized rewrite rules for conditional behaviors of general form `T(X, [onT][onF]if) => [T(X, onT)][T(X, onF)]if`. I assume `if` will drop one branch and inline the other based on a boolean on the stack. Thus, I leave `X` on the stack rather than copy it into both branches.

Advertisements
This entry was posted in Language Design, User Interface. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s