Re: [stack] a constructive-concatenative language

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