[stack] sweetening concatenative syntax
John Nowak <[email protected]>
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <[email protected]> |
I've had some thoughts recently on syntactic additions to
concatenative languages that seem potentially quite useful. At the
very least, they would put an end to silly discussions over largely
imagined deficiencies of postfix syntax and pointfree programming.
This is perhaps crucial if we expect any significant uptake of
concatenative languages.
Below are the four extensions that I'm proposing. I'm strongly
considering one or more in the language I'm currently working on
(named "Fifth" for what are likely obvious reasons). The first two
should be fairly uncontroversial. The latter two are simple
translations I've not seen discussed before that seem potentially very
useful in practice.
I. Lambda Expressions
Assuming functions have the syntax '[<body>]', it seems useful to
introduce the syntax '[<bindings> -> <body>], where bindings are
ordered with the top of the stack towards the right as is familiar.
For example, the following two functions are equivalent:
foo :: -> [a b -> b a a]
foo = [swap dup]
foo = [a b -> b a a]
Note that the type syntax mimics the lambda expression syntax (or vice
versa if you prefer). The type notation is similar to Cat's with minor
alterations for the purposes of brevity. In particular, scalar
variables are all lowercase, row variables are all uppercase, and
concrete types are title-case and of at least two characters (to avoid
confusion with row variables).
Variables should, of course, be lexically scoped. A translation of
expressions with lambdas to efficient pointfree stack-based code is
not especially difficult. This is the case regardless of if the
language is linear (which introduces only small complications), typed,
or "lacking" a retain stack. Of course, I elide the translation here
for the sake of... space.
II. Local Function Variables
If you permit lambdas, it makes sense to offer a simple syntax for
declaring functions with named variables. This is similar to how
Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo
(lambda (<bindings>) <body>))'. The declaration syntax proposed here
mimics use. In particular, the name of the function being defined
occurs *after* the arguments.
The following two statements are equivalent (where 'i' is the identity
combinator with the type 'A (A -> B) -> B'):
a b foo = b a a
foo = [a b -> b a a] i
Here's another example in which 'unlist' is a deconstructor for a
list; the first function provided handled the null case and the second
handles the cons case:
unlist :: A [b] (A -> C) (A b [b] -> C) -> C
map :: [a] (a -> b) -> [b]
list f map = list [] [x xs -> x f i xs f map cons] unlist
It should be noted that both lambda expressions and functions declared
with the local variable syntax may use more items on the stack than
they explicitly bind. For example, the following definition of map is
equivalent to the above and likely preferable in practice:
f map = [] [x xs -> x f i xs f map cons] unlist
III. Prefix Notation
It occurred to me recently that there exists a simple syntactic
translation from prefix code (a la Scheme), where '(foo a b c)' is the
application of 'foo' to three arguments, to postfix code. This
translation can be done without any type information. The translation
consists of simply removing the parenthesis and placing the first
element at the end. If that first element is a local binding or a
lambda expression, an 'i' is prepended to cause it to be evaluated.
Here are some simple translation examples:
(cons 1 null) => 1 null cons
(+ (- 1 2) 3) => 1 2 - 3 +
[f -> (f 10)] => [f -> 10 f i]
f foo = (f 5) => f foo = 5 f i
Interestingly, you get partial application for free:
double = (* 2)
One thing that may seem like a problem is that '(1 2 3)' will be
translated to '(2 3 1)' when really an error should occur as '1' is
not a function. However, that's not the case: '1' *is* a function.
More precisely, it is a row polymorphic function that consumes a stack
and yields a new stack (1 :: A -> A int). As such, the above syntactic
translation is completely valid and it would be wrong to reject it.
Prefix notation may seem like a curiosity at first, perhaps existing
only to lure over those familiar with prefix notation. However, I'd
argue that prefix notation makes certain code objectively easier to
read. This is especially the case when dealing with deconstructors
like 'if' or 'unlist' as the higher order function of primary interest
is "announced" earlier in the definition. In the following example,
both functions are equivalent:
f map = [] [x xs -> x f i xs f map cons] unlist
f map =
(unlist []
[x xs -> x f i xs f map cons])
(Perhaps this is not the best example. Substitute a better one with
nested ifs.)
Prefix notation also has the benefit that you can express "nested"
code (as above) in a way that allows editors to automatically intent
properly. This is not at all the case with purely postfix code where
type information and perhaps some heuristics would need to be involved
to produce acceptable indentation.
Here's a rewriting of map using *only* prefix notation in a way that
most any Scheme or Haskell programmer would find comfortable:
f map =
(unlist []
[x xs -> (cons (f x) (map xs f))])
IV. Indentation
Prefix notation is often criticized for being overly verbose or noisy.
The Python solution is to use indentation instead of paired
delimiters, but this introduces a number of problems: It's harder for
machines to generate valid code, pasting between sources can be messy,
editors can't really automatically re-indent code, plenty of people
(myself included) hate it, etc.
The correct way to address this problem (if you are to address it at
all) is to do what Haskell does and offer *optional* indentation-
sensitive syntax that gets translated to the more explicit form. This
can be implemented as a relatively trivial pre-parser pass and does
not require modification of the parser itself.
Indentation-sensitive syntax is introduced with a colon. Here are some
simple examples showing how indentation-sensitive code is translated
to prefix code which is then translated to "normal" code:
a b c: d e f => a b (c d e f) => a b d e f c
a b c:
d e f: => a b (c d e (f g h)) => a b d e g h f c
g h
Finally, here again is our map example, this time even spiffier:
f map = unlist:
[]
[x xs -> cons: (f x) (map xs f)]
This looks quite close to the Haskell version, except that our
programs are, after translation, still expressed only in terms of the
functional forms of composition and quotation! (I was wrong in an
earlier email when I started that composition is the only functional
form in Joy. Quotation is also a functional form.) This definition is
arguably easier to read than the postfix, pointfree alternative, as it
clearly announces at the start that 'map' is a function that
destructures a list, details the result of the destructization at the
start of the relevant line, and indicates directly after that the
result of the function will be a list via the prefixing of 'cons'.
- John