13 Feb 2012 20:05

## Re: [stack] Jon Purdy: Why Concatenative Programming Matters

On 02/13/2012 12:08 PM, William Tanksley, Jr wrote:

> description, but doesn't communicate very well. I don't know
> what else to say.

Apologies: This email is a bit of a brain dump and ill-proofread.

I think maybe the most interesting thing about concatenative
languages isn't stressed enough in the article: Unlike most every
other type of programming language on the planet, there is no
syntax for function application. All you get is composition and,
if higher-order, quotation.

I think the second most interesting thing is that all functions
operate on possibly empty sequences containing arbitrary amounts
of program state. It's this "all the state" element that gives
concatenative languages their character. For example, Backus's FL
does not do this; functions that need one number take just that
number and functions that need two take a pair; never do
functions take the entire state of a program as they usually do
in Forth or Factor.

For example, a tail-recursive 'length' function in a
concatenative language might be:

length = [0] dip loop where
loop = [null?] [drop] [[1 +] dip tail loop] if
end

And in FL:

def length ≡ f ∘ [id, ~0] where {
def f ≡ isnull ∘ xs → n; loop ∘ [tl ∘ xs, + ∘ [~1, n]]
def xs ≡ s1
def n ≡ s2
}

A quick guide to the FL program:

- '∘' is composition
- '~' is constant (i.e. \x y -> x)
- the square brackets denote "construction"; construction returns
a function that, when applied to an argument, returns a list of
length N where N is the number of functions provided by the
programmer; each element in the result corresponds to one
function after it was applied to the same input as all other
functions (e.g. '[f, g]:x == <f:x, g:x>', where ':' is FL's
syntax for application and angle brackets denote lists)
- conditionals are written 'a → b; c', where 'b' and 'c' are the
functions conditionally applied to the input to get the result
- 's1' and 's2' select the first and second elements from a list
- 'tl' is the tail operation

These two programs are, to me, radically different. The
concatenative program is decidedly "flat" and feels very
imperative. The FL program, on the other hand, is "nested" like
applicative programs usually are and feels, at least to me,
rather declarative; the fact that you can consider each function
within the two constructions to be completely independent is
probably the main reason for this. The independence of functions
also allows you to write aliases for selectors as I did above. In
fact, FL offers a form of pattern matching for conveniently
locally-defining such selector functions via double-square
brackets:

def length ≡ f ∘ [id, ~0] where {
def f ≡〚xs, n〛→
isnull ∘ xs → n; loop ∘ [tl ∘ xs, + ∘ [~1, n]]
}

This is very different from concatenative languages where
combinators like 'bi <at> ' allow the functions provided to step on
each other as the second function runs on top of the stack
returned from the first. This is the reason I gave up on
concatenative languages; the equational reasoning possible when
all functions operate on "the stack" just isn't great. I think
the fact that faking variables in FL is trivial while faking
variables in something like Factor requires a rather complex
transformation is evidence of this. I also think the lack of
useful equational reasoning is why things feel so imperative once
you get past the pretty examples in the Joy literature. Maybe I
just need more combinators.

To be fair, I should point out that having all functions work on
"the stack" does have its advantages. In particular, higher-order
programming in FL is pretty gnarly. In fact, doing it requires
pervasive use of "lifting" which is, essentially, a way of
modifying functions so that they take an additional argument full
of all the other stuff you want to use (and hence reminds me a

http://theory.stanford.edu/~aiken/publications/trs/FLProject.pdf

I guess what I'm trying to say is that "every function takes the
entire program state as input", or at least a good chunk of it
(as with Joy's 'infra'), is *really important*. While this fact
is arguably implicit in the definition on Wikipedia, it's not
spelled out at all. Maybe I can add some insight to it in the
next few days.

- jn

__._,_.___
Recent Activity:
.

__,_._,___

Gmane