There are many nice things about concatenative languages: Good
abstraction potential, easy handling of multiple value returns, simple
left-to-right syntax, suitability for linear types[1], etc. There are,
however, some things that I personally find problematic:
- Because functions are of the type stack -> stack, and because the
same stack is generally threaded throughout the entire program,
reasoning (both formal and informal) becomes complicated. I see no
reason at this point to think that concatenative languages are any
easier to reason about than applicative languages, especially as
"practical" concatenative languages end up adding variables and
substitution anyway. (The fact that you can translate code that
uses variables to a concatenative version full of quotation
splicing and dips isn't that useful.)
- It is difficult to compile concatenative languages efficiently,
especially in the presence of separate compilation. The current
technique I have requires extensive monomorphizing in order to be
able to generate efficient C.
- Interoperability with other languages is not as straightforward as
it is when two languages share the same basic (applicative) model.
- Typing concatenative languages requires row variables (or the
rough
equivalent of viewing the stack as unit-terminated list of pairs).
Even languages with curried functions like Haskell typically have
simpler types for "equivalent" functions. For example, here's
'map'
in Haskell: '(a -> b) -> List a -> List b'. Now here's the
type of a Factor-like 'map' that does accumulation on the stack:
'R (List x) [R x -> R y] -> R (List y)'.
- The dataflow of a program is easily obscured. For example, the
function '[+] dip' requires three values on the stack, but it only
actually cares about two of them. Analysis is required to recover
basic information that is explicit in applicative languages. This
is an especially big problem for me as I'm interested in rendering
concatenative code as a visual diagram for pedagogical purposes.
- After working with concatenative languages for some time, I still
occasionally myself having to write the code first in another
language so I can translate it to a concatenative version. This is
unacceptable. Maybe it's just me, but I sometimes find it easier
to
think without a stack getting in the way. I don't think it's just
me though: *Many* people agree.
I think these problems are the result of one fundamental issue: The
stack -> stack model, which requires that functions like '+' take the
entire state of the program as an argument, is not ideal. From a type
system perspective, you might say that functions that are row
polymorphic are not ideal when it comes to reasoning ability,
compilability, and interoperability. The stack is not such an issue in a
first-order language like Forth, but once you add powerful combinators,
things get much more difficult.
The solution to this problem (if you agree it's a problem) is to drop
the stack -> stack model. We can do this while still maintaining a
predominately left-to-right syntax, multiple value returns, and the
denotation of composition by concatenation. In other words, we can
remain "concatenative" while ditching the stack.
In place of the stack -> stack model, I substitute a model in which
functions remain unary but can produce and consume any type of value. A
good example of this is the 'square' function which squares a number. In
a concatenative language, 'square' takes some stack R with a number on
top and yields the same stack R with a new number on top. In the
language I'm proposing (called a "constructive" languages for reasons to
be explained later), 'square' simply takes a number and returns a
number.
An important question is how functions which produce or consume multiple
values can be handled. I propose that this be done via tuples (as in
Lisp) as opposed to currying (as in Haskell) or nested pairs (as in
concatenative languages). For example, here are the types and semantics
of the '+' function in a concatenative language (C), in a language with
curried functions (λ), and in the language I'm proposing (?):
C + : R num num -> R num
+ = \(x, (y, r)) -> (x + y, r) -- 'r' for "rest" or "row"
λ + : num -> num -> num
+ = \x -> \y -> x + y
? + : (num, num) -> num
+ = \(a, b) -> a + b
As another example, here's the 'dup' function in both a concatenative
language and the language I'm proposing. Note that in the second case,
'dup' takes *any* value:
C dup : R x -> R x x
dup = \(x, r) -> (x, (x, r))
? dup : x -> (x, x)
dup = x -> (x, x)
In order to make such a language work, it is necessary to change the
combining forms. I discard quotation, keep composition, and add the
forms of application, construction, combination, and selection:
- Composition is denoted via concatenation where 'f g' has the
semantics '\x -> g (f x)'. This is the same as in a concatenative
language.
- Application of a function 'f' to an object 'x' is denoted 'f:x'.
- Construction takes zero or more functions separated by commas
within square brackets and has the following semantics (similar to
'cleave' in Factor):
[] = \x -> ()
[f] = \x -> f x
[f, g] = \x -> (f x, g x)
[f, g, h] = \x -> (f x, g x, h x)
...
- Combination takes zero or more functions separated by commas
within
curly braces and has the following semantics (similar to 'spread'
in Factor):
{} = \x -> ()
{f} = \x -> f x
{f, g} = \(x, y) -> (f x, g y)
{f, g, h} = \(x, y, z) -> (f x, g y, h z)
...
- Selection has a syntax of the form 'M@N' yielding a function that
selects the Nth element of a tuple of size M. For example,
'4@2' has the semantics '\(x, y, z, w) -> y'. The reason for
indicating M is that we're dealing with tuples, not nested pairs,
and as such we can't operate on an arbitrary number of values.
This
is why we can get by without row polymorphism. I hope to come up
with a better syntax for this shortly, although as I'll show
later,
you never really have to use this form directly.
Here are a few simple examples that may help this make some sense. All
of these are really roughly equivalent. For example, 'fold' does not get
access to any sort of stack in a constructive language. Instead, the
function resulting from an application of fold takes a tuple where the
first element is a list and the second is the initial element.
C sq = dup *
? sq = dup *
C hypot = [sq] bi@ + sqrt
? hypot = {sq, sq} + sqrt
C +/- = [+] [-] 2bi
? +/- = [+, -]
C avg = [sum, len] bi /
? avg = [sum, len] / -- or just 'sum / len' if we have infix ops
C swap = [] papply dip
? swap = [2@2, 1@2]
C sum = 0 [+] fold
? sum = [id, 0] (fold +) -- HOFs are curried
C add3 = + +
? add3 = [[3@1, 3@2] +, 3@3] +
I should make a small note here with regard to literals. As in
concatenative languages, they are really functions, but they have
different semantics:
C 42 = \r -> (42, r)
λ 42 = 42
? 42 = \r -> 42
In order to make the language more familiar and to avoid the need to use
the form of selection, I allow the use of named variables. It is not
legal to use variables in any other places than those which allow a
trivial substitution for selection forms. For example:
add3:<x, y, z> = [[x, y] +, z] + -- x = 3@1, y = 3@2, z = 3@3
Much of this syntactic noise is eased by adding infix operators which
I'll use for the remainder of this document:
add3:<x, y, z> = x + y + z -- x + y = [x, y] +
One more example; the quadratic formula in all its numerically unstable
glory. We do this easily without defining any additional combinators:
discrim:<a, b, c> = b sq - 4 * a * c
<a, b> // c = [a / c, b / c]
find-roots:<a, b, c> = [b neg, discrim sqrt] [+, -] // 2 * a
Again, this is completely pointfree via a trivial translation:
discrim = 3@2 sq - 4 * 3@1 * 3@3
// = [2@1 2@1 / 2@2, 2@1 2@2 / 2@2]
find-roots = [3@2 neg, discrim sqrt] [+, -] // 2 * 3@1
And again as if we didn't have infix operators:
discrim = [3@2 sq, [[4, 3@1] *, 3@3] *] -
// = [[2@1 2@1, 2@2] /, [2@1 2@2, 2@2] /]
find-roots = [[3@2 neg, discrim sqrt] [+, -], 2 * 3@1] //
It seems perhaps that concatenative languages do not need a stack after
all. That said, there are still some things that I have to consider:
- Is it worth having composition read right-to-left instead? Doing
so
would let us write 'f[f[a, b], c]' instead of '[[a, b] f, c] f'.
If
you then change the square brackets to parentheses, you have a
very
familiar algol-like syntax.
- Is the current selection form too painful? Can I really get away
without allowing things like 'drop' and 'dip'? The answer is
probably yes if we assume judicious use of named variables.
- Will this approach scale up to real programs?
- Does this language translate well to a visual programming context?
Thanks for making it through. Any thoughts would be appreciated.
P.S. I somehow forgot to mention this earlier: The language I'm
proposing is *very* similar to Backus's FP, although FP used a nested
pair model like concatenative languages do (e.g. the 'tail' function in
FP is the same as 'drop' in Factor). As such, it suffers from some of
the same problems I'm trying very hard to avoid.
[1] http://home.pipeline.com/~hbaker1/ForthStack.html
Ow. Sorry for the line wrapping issues. Here's another copy. (Not sure
if sending this again is more annoying than the line wrapping, but
here we are.)
- - -
There are many nice things about concatenative languages: Good
abstraction potential, easy handling of multiple value returns, simple
left-to-right syntax, suitability for linear types[1], etc. There are,
however, some things that I personally find problematic:
- Because functions are of the type stack -> stack, and because the
same stack is generally threaded throughout the entire program,
reasoning (both formal and informal) becomes complicated. I see no
reason at this point to think that concatenative languages are any
easier to reason about than applicative languages, especially as
"practical" concatenative languages end up adding variables and
substitution anyway. (The fact that you can translate code that
uses variables to a concatenative version full of quotation
splicing and dips isn't that useful.)
- It is difficult to compile concatenative languages efficiently,
especially in the presence of separate compilation. The current
technique I have requires extensive monomorphizing in order to be
able to generate efficient C.
- Interoperability with other languages is not as straightforward as
it is when two languages share the same basic (applicative) model.
- Typing concatenative languages requires row variables (or the
rough equivalent of viewing the stack as unit-terminated list of
pairs). Even languages with curried functions like Haskell
typically have simpler types for "equivalent" functions. For
example, here's 'map' in Haskell: '(a -> b) -> List a -> List b'.
Now here's the type of a Factor-like 'map' that does accumulation
on the stack: 'R (List x) [R x -> R y] -> R (List y)'.
- The dataflow of a program is easily obscured. For example, the
function '[+] dip' requires three values on the stack, but it only
actually cares about two of them. Analysis is required to recover
basic information that is explicit in applicative languages. This
is an especially big problem for me as I'm interested in rendering
concatenative code as a visual diagram for pedagogical purposes.
- After working with concatenative languages for some time, I still
occasionally myself having to write the code first in another
language so I can translate it to a concatenative version. This is
unacceptable. Maybe it's just me, but I sometimes find it easier
to think without a stack getting in the way. I don't think it's
just me though: *Many* people agree.
I think these problems are the result of one fundamental issue: The
stack -> stack model, which requires that functions like '+' take the
entire state of the program as an argument, is not ideal. From a type
system perspective, you might say that functions that are row
polymorphic are not ideal when it comes to reasoning ability,
compilability, and interoperability. The stack is not such an issue in
a first-order language like Forth, but once you add powerful
combinators, things get much more difficult.
The solution to this problem (if you agree it's a problem) is to drop
the stack -> stack model. We can do this while still maintaining a
predominately left-to-right syntax, multiple value returns, and the
denotation of composition by concatenation. In other words, we can
remain "concatenative" while ditching the stack.
In place of the stack -> stack model, I substitute a model in which
functions remain unary but can produce and consume any type of value. A
good example of this is the 'square' function which squares a number.
In a concatenative language, 'square' takes some stack R with a number
on top and yields the same stack R with a new number on top. In the
language I'm proposing (called a "constructive" languages for reasons
to be explained later), 'square' simply takes a number and returns a
number.
An important question is how functions which produce or consume
multiple values can be handled. I propose that this be done via tuples
(as in Lisp) as opposed to currying (as in Haskell) or nested pairs (as
in concatenative languages). For example, here are the types and
semantics of the '+' function in a concatenative language (C), in a
language with curried functions (λ), and in the language I'm proposing
(?):
C + : R num num -> R num
+ = \(x, (y, r)) -> (x + y, r) -- 'r' for "rest" or "row"
λ + : num -> num -> num
+ = \x -> \y -> x + y
? + : (num, num) -> num
+ = \(a, b) -> a + b
As another example, here's the 'dup' function in both a concatenative
language and the language I'm proposing. Note that in the second case,
'dup' takes *any* value:
C dup : R x -> R x x
dup = \(x, r) -> (x, (x, r))
? dup : x -> (x, x)
dup = x -> (x, x)
In order to make such a language work, it is necessary to change the
combining forms. I discard quotation, keep composition, and add the
forms of application, construction, combination, and selection:
- Composition is denoted via concatenation where 'f g' has the
semantics '\x -> g (f x)'. This is the same as in a concatenative
language.
- Application of a function 'f' to an object 'x' is denoted 'f:x'.
- Construction takes zero or more functions separated by commas
within square brackets and has the following semantics (similar to
'cleave' in Factor):
[] = \x -> ()
[f] = \x -> f x
[f, g] = \x -> (f x, g x)
[f, g, h] = \x -> (f x, g x, h x)
...
- Combination takes zero or more functions separated by commas
within curly braces and has the following semantics (similar to
'spread' in Factor):
{} = \x -> ()
{f} = \x -> f x
{f, g} = \(x, y) -> (f x, g y)
{f, g, h} = \(x, y, z) -> (f x, g y, h z)
...
- Selection has a syntax of the form 'M@N' yielding a function that
selects the Nth element of a tuple of size M. For example,
'4@2' has the semantics '\(x, y, z, w) -> y'. The reason for
indicating M is that we're dealing with tuples, not nested pairs,
and as such we can't operate on an arbitrary number of values.
This is why we can get by without row polymorphism. I hope to come
up with a better syntax for this shortly, although as I'll show
later, you never really have to use this form directly.
Here are a few simple examples that may help this make some sense. All
of these are really roughly equivalent. For example, 'fold' does not
get access to any sort of stack in a constructive language. Instead,
the function resulting from an application of fold takes a tuple where
the first element is a list and the second is the initial element.
C sq = dup *
? sq = dup *
C hypot = [sq] bi@ + sqrt
? hypot = {sq, sq} + sqrt
C +/- = [+] [-] 2bi
? +/- = [+, -]
C avg = [sum, len] bi /
? avg = [sum, len] / -- or just 'sum / len' if we have infix ops
C swap = [] papply dip
? swap = [2@2, 1@2]
C sum = 0 [+] fold
? sum = [id, 0] (fold +) -- HOFs are curried
C add3 = + +
? add3 = [[3@1, 3@2] +, 3@3] +
I should make a small note here with regard to literals. As in
concatenative languages, they are really functions, but they have
different semantics:
C 42 = \r -> (42, r)
λ 42 = 42
? 42 = \r -> 42
In order to make the language more familiar and to avoid the need to
use the form of selection, I allow the use of named variables. It is
not legal to use variables in any other places than those which allow a
trivial substitution for selection forms. For example:
add3:<x, y, z> = [[x, y] +, z] + -- x = 3@1, y = 3@2, z = 3@3
Much of this syntactic noise is eased by adding infix operators which
I'll use for the remainder of this document:
add3:<x, y, z> = x + y + z -- x + y = [x, y] +
One more example; the quadratic formula in all its numerically unstable
glory. We do this easily without defining any additional combinators:
discrim:<a, b, c> = b sq - 4 * a * c
<a, b> // c = [a / c, b / c]
find-roots:<a, b, c> = [b neg, discrim sqrt] [+, -] // 2 * a
Again, this is completely pointfree via a trivial translation:
discrim = 3@2 sq - 4 * 3@1 * 3@3
// = [2@1 2@1 / 2@2, 2@1 2@2 / 2@2]
find-roots = [3@2 neg, discrim sqrt] [+, -] // 2 * 3@1
And again as if we didn't have infix operators:
discrim = [3@2 sq, [[4, 3@1] *, 3@3] *] -
// = [[2@1 2@1, 2@2] /, [2@1 2@2, 2@2] /]
find-roots = [[3@2 neg, discrim sqrt] [+, -], 2 * 3@1] //
It seems perhaps that concatenative languages do not need a stack after
all. That said, there are still some things that I have to consider:
- Is it worth having composition read right-to-left instead? Doing
so would let us write 'f[f[a, b], c]' instead of
'[[a, b] f, c] f'. If you then change the square brackets to
parentheses, you have a very familiar algol-like syntax.
- Is the current selection form too painful? Can I really get away
without allowing things like 'drop' and 'dip'? The answer is
probably yes if we assume judicious use of named variables.
- Will this approach scale up to real programs?
- Does this language translate well to a visual programming context?
Thanks for making it through. Any thoughts would be appreciated.
P.S. I somehow forgot to mention this earlier: The language I'm
proposing is *very* similar to Backus's FP, although FP used a nested
pair model like concatenative languages do (e.g. the 'tail' function in
FP is the same as 'drop' in Factor). As such, it suffers from some of
the same problems I'm trying very hard to avoid.
[1] http://home.pipeline.com/~hbaker1/ForthStack.html
On Dec 7, 2008, at 7:59 AM, John Nowak wrote:
> ? sum = [id, 0] (fold +) -- HOFs are curriedSigh. That should read as follows:
sum = [id, 0] fold:+
I swear I proofread this thing before I sent it.
- John
I've been too busy to do any more than scan your message, but I did
notice with interest your claim that you preserve concatenativity
without using a stack. I might get some time to check that claim after
the holidays.
In the meantime, I fwd'ed this to a friend who's got more time, and
this is what he said:
> This is a near-complete re-invention of Backus' FL language, including[...]
> syntax. The only things I can spot which are readily different are
> the selection syntax and that you no longer need to use 'o' to
> indicate composition.
>
> Not that this is anything wrong, of course -- FL has always been one
> of those languages which has piqued my curiosity. I've often pondered
> how hard it'd be to write an interpreter for my own dialect of FL too.
> * In FP/FL, all functions consume one datum. Passing multiple
> arguments to a function occurs via tuples, expressed in <a,b,c>
> syntax.
>
> * In FP/FL, integer literals are functions which return the nth item
> of a tuple. Thus, 3:<a,b,c> yields the value c (this is read "third
> of <a,b,c>". To actually specify a numeric literal, you prefix it
> with some character (I cannot remember which: I think ~).
>
> * ID is used for the identity function -- it returns its argument.
>
> * [f,g,h] is the construction operator in FP/FL; hence:
> [f,g,h]:<1,2,3> == <f:<1,2,3>, g:<1,2,3>, h:<1,2,3>>. Hence,
> computing the average of its parameter, a function can be written: avg
> = /:[+,length]. Using substitution, avg:<1,2,3> =
> /:[+,length]:<1,2,3> = /:[+:<1,2,3>, length:<1,2,3>] = /:<6, 3> = 2.
>
> I'm sure there are other attributes of FP/FL that I am missing or have
> forgotten.
>
> The point is, however, that Nowak's language and FP/FL are extremely
> similar. I'm not sure to what extent that FP/FL have influenced his
> thinking, but if it's an independent design, that speaks volumes for
> Backus' ideas. Perhaps traditional functional languages have it all
> wrong -- perhaps functions of tuples of arguments solves the dataflow
> problem when compiling to a stack architecture better than curried
> functions.
>
> However, Nowak's language has a few innovations of its own, which must
> not be ignored. I do not recall seeing anything like {a,b,c} syntax
> in FP/FL, for example. The elimination of 'o' for function
> composition perhaps forms the single biggest contribution. That
> _forces_ anything you program in it to be concatenative, by
> definition.
>
> I'm not a fan of him using infix mathematics in his language, only
> because it's nearly impossible to statically disambiguate postfix and
> infix forms of operators.
>
> I do have to admit, however, that I've been considering a language
> which is structured similarly to APL/J. The idea that you read from
> left to right, but evaluate from right to left is very appealing to
> me, particularly from an applicative point of view. So far as I can
> tell, the only core primitives in the language would be function
> definition (=), and the McCarthy conditional construct (a->b;c), and
> function application (a(b)). Everything else pretty much is
> effectively "standard library" material.
>
> However, I'll need to re-evaluate my "toy" language idea to see how
> making all functions operate on tuples of arguments changes it.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
>> I do have to admit, however, that I've been considering a language
>> which is structured similarly to APL/J. The idea that you read from
>> left to right, but evaluate from right to left is very appealing to
>> me, particularly from an applicative point of view. So far as I can
>> tell, the only core primitives in the language would be function
>> definition (=), and the McCarthy conditional construct (a->b;c), and
>> function application (a(b)).
what you've described is just iverson's "direct definition" restriction
of APL. a direct definition is an expression
f = expression
or
f = condition:expression-if-true:expression-if-false
"alpha" and "omega" are arguments to f. using x and y for these:
diff = x>y:x-y:y-x
some large APL systems have been written using only direct definition.
On Dec 11, 2008, at 1:48 PM, William Tanksley, Jr wrote:
> In the meantime, I fwd'ed this to a friend who's got more time, andVery good. Thanks for passing it on.
> this is what he said:
>> This is a near-complete re-invention of Backus' FL language,This is essentially true. One more important thing that is different
>> including
>> syntax. The only things I can spot which are readily different are
>> the selection syntax and that you no longer need to use 'o' to
>> indicate composition.
(that I think your friend realized but didn't mention here) is that
you cannot write the equivalent of FP's 'hd' or 'tl' functions because
they both operate on lists of arbitrary length. Here, selection only
works on tuples of a specific length. The idea was that this would
prevent some subtle errors and make reading easier, but it seems to be
something of a burden in my early experiments.
>> The point is, however, that Nowak's language and FP/FL are extremelyIt is not entirely independent. I was familiar with FP, although only
>> similar. I'm not sure to what extent that FP/FL have influenced his
>> thinking, but if it's an independent design, that speaks volumes for
>> Backus' ideas.
in a cursory way. What really happened was that I enjoyed the clarity
in which functions could written using the cleave and spread
combinators in Factor. I ended up working backwards and arriving at
something very much like FP. After realizing this, I lifted most of
FP's syntax.
>> I'm not a fan of him using infix mathematics in his language, onlyI'm not a big fan of this either. The problem is that the verbosity is
>> because it's nearly impossible to statically disambiguate postfix and
>> infix forms of operators.
a little irritating if something like it isn't offered. FL offered a
general infix syntax (the same as J's "fork", roughly '(f g h):x ==
g:<f:x, h:x>') and 15 level of precedence, perhaps for this reason.
I'm sure there are other syntactic approaches worth considering
though. Switching to a right-to-left evaluation order seems to help.
>> However, I'll need to re-evaluate my "toy" language idea to see howI'd be curious to hear the results of this experiment.
>> making all functions operate on tuples of arguments changes it.
One problem I've already run into with the language I proposed is that
first class functions are hopelessly painful to work with. The simple
example I had wanted to do was transform a binary operator (like '+')
to one that works on 3 values and yields 2:
foo(F) = [[3@1, 3@2] F, 3@3] F
However, if I try to write a version of 'foo' that takes some function
'F' as part of a tuple rather than as a constant, it becomes very
painful. Looking at Backus's FL, it appears the problem is partially
solved using "prime notation", but it's hardly elegant. Backus's
Formal FP seems to take an approach similar to what I wrote above,
although I'm not sure about that. In contrast, the concatenative code
is trivial: '[dip] keep i'. It's not clear to what extent the problems
I've run into are merely syntactic, but I suspect the syntax is not
the fundamental issue.
The other problem I quickly ran into is that rearranging values in
nested tuples is very awkward. Some kind of shuffling form would be
necessary to make this work. The addition of such a form may also do
much to solve the issue with first class functions being too awkward
to manipulate into a place where they can be properly applied.
- John