# disallowing recursive definitions

## John Nowak — 2008-02-28 20:39:47

    Recently, I mentioned that if you disallow recursive definitions, then

    definitions can be thought of as macros or rewrite rules. In other

    words, you can replace every occurrence of foo in a program with foo's

    definition and then remove the definition without changing the meaning

    of the program. It is therefore trivial to remove all definitions in a

    program and be left with only a single function that only uses

    primitives built in to the system.

    This dual view of definitions as functions and definitions as rewrite

    rules is, at least, aesthetically appealing. I began to think of what

    some other benefits of disallowing recursive definitions might be:

    1. It isn't necessary to do tail call optimization; an appropriate

    combinator is used instead.

    2. The type system and formalization of the language in general are

    simplified. A restriction on recursive definitions may actually be a

    requirement for a truly compositional type system.

    3. WIth a small addition to the type system, it becomes possible to

    prove that the stack will not overflow given the correct set of

    recursive combinators. (Combinators like linrec would need to be

    disallowed or specially handled.)

    4. Similarly, it becomes possible compute the maximum number of items

    that will ever be on the stack, and pre-allocate a stack of exactly

    the right size upon program initialization.

    5. It allows additional ways of presenting code, such as an editor

    that can expand a definition inline to show what it does while still

    displaying a program with the same meaning.

    6. It becomes possible to prove termination when using recursive

    combinators that always terminate given that their arguments always

    terminate (such as primrec).

    There are likely other benefits that I'm missing.

    The question therefore is how critical recursive definitions actually

    are. They're not necessary in an absolute sense; any recursive

    function can be expressed using while. Essentially, it seems like

    disallowing recursive definitions has the same sort of tradeoff as

    disallowing multiple references to the same value (and therefore

    enforcing linearity): Many nice properties emerge and things are

    simplified, but it may simply be too much of a pain. I think it may be

    worth a shot.

    Thoughts?

    - John

## John Nowak — 2008-02-28 20:43:28

    On Feb 28, 2008, at 3:39 PM, John Nowak wrote:

     > 6. It becomes possible to prove termination when using recursive

    > combinators that always terminate given that their arguments always

    > terminate (such as primrec).

     To clarify, this is possible with recursive definitions as well.

    Without them however, it's a trivial addition to the type system that

    works exactly the same way that tracking of side effects works.

    - John

## John Cowan — 2008-02-28 20:44:53

    John Nowak scripsit:

     > Recently, I mentioned that if you disallow recursive definitions, then

    > definitions can be thought of as macros or rewrite rules.

     Sure, but then you can only compute primitive-recursive functions

    (roughly speaking, ones in which all loops are bounded at compile time).

    --

    Do what you will,                       John Cowan

       this Life's a Fiction                cowan@...

    And is made up of                       http://www.ccil.org/~cowan

       Contradiction.  --William Blake

## Daniel Ehrenberg — 2008-02-28 21:00:32

    > Recently, I mentioned that if you disallow recursive definitions, then

    >  definitions can be thought of as macros or rewrite rules. In other

    >  words, you can replace every occurrence of foo in a program with foo's

    >  definition and then remove the definition without changing the meaning

    >  of the program. It is therefore trivial to remove all definitions in a

    >  program and be left with only a single function that only uses

    >  primitives built in to the system.

    >

    >  This dual view of definitions as functions and definitions as rewrite

    >  rules is, at least, aesthetically appealing. I began to think of what

    >  some other benefits of disallowing recursive definitions might be:

    >

    >  1. It isn't necessary to do tail call optimization; an appropriate

    >  combinator is used instead.

    >  2. The type system and formalization of the language in general are

    >  simplified. A restriction on recursive definitions may actually be a

    >  requirement for a truly compositional type system.

    >  3. WIth a small addition to the type system, it becomes possible to

    >  prove that the stack will not overflow given the correct set of

    >  recursive combinators. (Combinators like linrec would need to be

    >  disallowed or specially handled.)

    >  4. Similarly, it becomes possible compute the maximum number of items

    >  that will ever be on the stack, and pre-allocate a stack of exactly

    >  the right size upon program initialization.

    >  5. It allows additional ways of presenting code, such as an editor

    >  that can expand a definition inline to show what it does while still

    >  displaying a program with the same meaning.

    >  6. It becomes possible to prove termination when using recursive

    >  combinators that always terminate given that their arguments always

    >  terminate (such as primrec).

    >

    >  There are likely other benefits that I'm missing.

    >

    >  The question therefore is how critical recursive definitions actually

    >  are. They're not necessary in an absolute sense; any recursive

    >  function can be expressed using while. Essentially, it seems like

    >  disallowing recursive definitions has the same sort of tradeoff as

    >  disallowing multiple references to the same value (and therefore

    >  enforcing linearity): Many nice properties emerge and things are

    >  simplified, but it may simply be too much of a pain. I think it may be

    >  worth a shot.

    >

    >  Thoughts?

    >

    >  - John

     Strictly speaking, recursive functions aren't necessary. However, they

    make code a lot more readable than directly using combinators which

    take 4 or 5 quotations. Try expressing the Magic Five algorithm (see

    http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22)

    to get the median of an array in linear time (for guaranteed O(n log

    n) Quicksort) in terms of a recursive combinator. It'd be really hard,

    and I'm not sure which combinator would be appropriate. So, maybe you

    don't want recursive functions strictly in the minimal formalized

    subset of your language, but, like lexically scoped variables, it

    might be nice if the compiler did the appropriate transformations to

    allow them in user code.

    Also, about restricting the set of combinators so the stack doesn't

    overflow: I'm not sure if that's worth it. If there's no explicit

    recursion, you'd want the set of combinators included to be as general

    as possible. (There is a combinator, condnestrec, which encodes

    general recursion, and this would obviously not be included if you

    want to prevent stack overflow.) Things like depth-first search are

    much easier to express on the system stack (which could overflow from

    certain graphs) than on an explicit stack, though strictly speaking

    it's possible either way (and I guess in some cases you would actually

    want to use an explicit stack).

    Dan

## Daniel Ehrenberg — 2008-02-28 21:04:09

    >  Sure, but then you can only compute primitive-recursive functions

    >  (roughly speaking, ones in which all loops are bounded at compile time).

     With linrec and cons, I think you could build yourself an ad-hoc

    variable-depth stack anyway, where loops aren't necessarily bounded.

    It'd just be awkward and not any more efficient.

## John Cowan — 2008-02-28 21:58:56

    Daniel Ehrenberg scripsit:

     > >  Sure, but then you can only compute primitive-recursive functions

    > >  (roughly speaking, ones in which all loops are bounded at compile time).

    >

    > With linrec and cons, I think you could build yourself an ad-hoc

    > variable-depth stack anyway, where loops aren't necessarily bounded.

    > It'd just be awkward and not any more efficient.

     True.  It would be interesting to see a concatenative language

    with support for data/codata, where you recurse downward on data

    and upward on codata, a la "total functional programming".

    --

    John Cowan  <cowan@...>  http://www.ccil.org/~cowan

            Raffiniert ist der Herrgott, aber boshaft ist er nicht.

                    --Albert Einstein

## Christopher Diggins — 2008-02-28 22:23:03

    On Thu, Feb 28, 2008 at 3:44 PM, John Cowan <cowan@...> wrote:

     > John Nowak scripsit:

    > > Recently, I mentioned that if you disallow recursive definitions, then

    > > definitions can be thought of as macros or rewrite rules.

    >

    > Sure, but then you can only compute primitive-recursive functions

    > (roughly speaking, ones in which all loops are bounded at compile time).

     I don't believe this is true. The approach I take is to pass the

    function definition as a named parameter to the function, and perform

    the point-free conversion.

    In Cat I can write the fibonnacci function (a tree recursive

    procedure) to take its body as an argument:

     >> define fibrec { \f.\n.[n 1 <= [1] [f n 1 - f apply f n 2 - f apply +] if] }

     Which my horrible horrible abstraction algorithm translates to:

    [dup dup [[[dup dup dup] dip [[[[id 1 <= [1]] papply dip] papply dip]

    papply dip] papply dip] dip] dip [[[[[[id] dip id 1 -] papply dip id

    apply] papply dip id] dip id 2 -] papply papply dip id apply +] papply

    papply papply papply papply papply if]

     >> define fib { fibrec swap fibrec apply }

    >> 5 fib

     8

    Incidentally this managed to completely corrupt my type checker, thanks a lot!

    :-)

    - Christopher

## Joe Bowbeer — 2008-02-28 23:47:51

    On Thu, Feb 28, 2008 at 12:39 PM, John Nowak wrote:

     > Recently, I mentioned that if you disallow recursive definitions, then

    > definitions can be thought of as macros or rewrite rules. In other

    > words, you can replace every occurrence of foo in a program with foo's

    > definition and then remove the definition without changing the meaning

    > of the program. It is therefore trivial to remove all definitions in a

    > program and be left with only a single function that only uses

    > primitives built in to the system.

    >

    > This dual view of definitions as functions and definitions as rewrite

    > rules is, at least, aesthetically appealing. I began to think of what

    > some other benefits of disallowing recursive definitions might be:

    >

    > 1. It isn't necessary to do tail call optimization; an appropriate

    > combinator is used instead.

    > 2. The type system and formalization of the language in general are

    > simplified. A restriction on recursive definitions may actually be a

    > requirement for a truly compositional type system.

    > 3. WIth a small addition to the type system, it becomes possible to

    > prove that the stack will not overflow given the correct set of

    > recursive combinators. (Combinators like linrec would need to be

    > disallowed or specially handled.)

    > 4. Similarly, it becomes possible compute the maximum number of items

    > that will ever be on the stack, and pre-allocate a stack of exactly

    > the right size upon program initialization.

    > 5. It allows additional ways of presenting code, such as an editor

    > that can expand a definition inline to show what it does while still

    > displaying a program with the same meaning.

    > 6. It becomes possible to prove termination when using recursive

    > combinators that always terminate given that their arguments always

    > terminate (such as primrec).

    >

    > There are likely other benefits that I'm missing.

    >

    > The question therefore is how critical recursive definitions actually

    > are. They're not necessary in an absolute sense; any recursive

    > function can be expressed using while. Essentially, it seems like

    > disallowing recursive definitions has the same sort of tradeoff as

    > disallowing multiple references to the same value (and therefore

    > enforcing linearity): Many nice properties emerge and things are

    > simplified, but it may simply be too much of a pain. I think it may be

    > worth a shot.

    >

    > Thoughts?

    >

    > - John

    >

    >

     As a former Schemer and fan of continuations, I'm conditioned to view (tail)

    recursion as the simpler, more powerful concept.  Not looping.

    Functional programming languages rely on recursion and still boast of

    referential transparency: the ability to substitute function applications by

    their definitions.  But they don't take the substitution as far as you'd

    like to...

    Functional languages favor recursion over looping because looping

    traditionally requires a loop variable whose value changes: a side effect.

    Recursion also allows tree-like control structures that are not easily

    replaced by while loops.

    --Joe

    [Non-text portions of this message have been removed]

## John Nowak — 2008-02-29 02:19:49

    On Feb 28, 2008, at 5:23 PM, Christopher Diggins wrote:

     > Incidentally this managed to completely corrupt my type checker,

    > thanks a lot!

     I'd be surprised if Cat were able to handle such a translation in the

    general case. Take something like the ackermann function in Haskell:

        ack 0 n = n + 1

        ack m 0 = ack (m - 1) 1

        ack m n = ack (m - 1) (ack m (n - 1))

    By passing the function itself as an additional argument, we can

    remove the recursive call:

        ackcore f 0 n = n + 1

        ackcore f m 0 = f f (m - 1) 1

        ackcore f m n = f f (m - 1) (f f m (n - 1))

        ack m n = ackcore ackcore m n

    Unfortunately, this will fail the occurs check. The only way that Cat

    could not run into this problem is if it discards the recursive

    constraint, which very well could be by your type checker is returning

    nonsense. (Of course, it's hard to tell for sure from here.)

    - John

## John Nowak — 2008-02-29 02:43:36

    On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:

     > As a former Schemer and fan of continuations, I'm conditioned to

    > view (tail)

    > recursion as the simpler, more powerful concept.  Not looping.

     I have a Scheme background as well.

     > Functional programming languages rely on recursion and still boast of

    > referential transparency: the ability to substitute function

    > applications by

    > their definitions.  But they don't take the substitution as far as

    > you'd

    > like to...

     Indeed.

     > Functional languages favor recursion over looping because looping

    > traditionally requires a loop variable whose value changes: a side

    > effect.

     What's surprising is how easily the stack lets you write code in an

    imperative style while remaining purely functional. Here's a small

    example where, given a natural number, we construct a list from 1 to

    that number:

        ; Scheme, via recursion

        (define (foo n)

          (let f ((n n) (xs '()))

            (if (zero? n)

                xs

                (f (- n 1) (cons n xs)))))

        ; Joy-like, via recursive combinator

        foo = null swap ((cons) keep pred) (zero?) until pop

        ; Another Joy-like version

        ; (prec :: A int int (A int -> A) -> A)

        foo = null swap 1 (cons) prec

    - John

## Joe Bowbeer — 2008-02-29 03:04:09

    Thanks for the examples.

    I think there's a relation between stack languages and Lisp's anaphoric

    macros:

     http://www.bookshelf.jp/texi/onlisp/onlisp_15.html#SEC99 -and-

     http://common-lisp.net/project/anaphora/anaphora.html

    In a stack language, the top of the stack is the anaphoric "it".

     On Thu, Feb 28, 2008 at 6:43 PM, John Nowak wrote:

    >

    > On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:

    >

    > > As a former Schemer and fan of continuations, I'm conditioned to

    > > view (tail)

    > > recursion as the simpler, more powerful concept.  Not looping.

    >

    > I have a Scheme background as well.

    >

    > > Functional programming languages rely on recursion and still boast of

    > > referential transparency: the ability to substitute function

    > > applications by

    > > their definitions.  But they don't take the substitution as far as

    > > you'd

    > > like to...

    >

    > Indeed.

    >

    > > Functional languages favor recursion over looping because looping

    > > traditionally requires a loop variable whose value changes: a side

    > > effect.

    >

    > What's surprising is how easily the stack lets you write code in an

    > imperative style while remaining purely functional. Here's a small

    > example where, given a natural number, we construct a list from 1 to

    > that number:

    >

    >    ; Scheme, via recursion

    >

    >    (define (foo n)

    >      (let f ((n n) (xs '()))

    >        (if (zero? n)

    >            xs

    >            (f (- n 1) (cons n xs)))))

    >

    >    ; Joy-like, via recursive combinator

    >

    >    foo = null swap ((cons) keep pred) (zero?) until pop

    >

    >    ; Another Joy-like version

    >    ; (prec :: A int int (A int -> A) -> A)

    >

    >    foo = null swap 1 (cons) prec

    >

    > - John

    >

    >

    [Non-text portions of this message have been removed]

## Christopher Diggins — 2008-02-29 03:26:22

    On Thu, Feb 28, 2008 at 9:19 PM, John Nowak <john@...> wrote:

     >

    >

    > On Feb 28, 2008, at 5:23 PM, Christopher Diggins wrote:

    >

    > > Incidentally this managed to completely corrupt my type checker,

    > > thanks a lot!

    >

    > I'd be surprised if Cat were able to handle such a translation in the

    > general case. Take something like the ackermann function in Haskell:

    >

    > ack 0 n = n + 1

    > ack m 0 = ack (m - 1) 1

    > ack m n = ack (m - 1) (ack m (n - 1))

    >

    > By passing the function itself as an additional argument, we can

    > remove the recursive call:

    >

    > ackcore f 0 n = n + 1

    > ackcore f m 0 = f f (m - 1) 1

    > ackcore f m n = f f (m - 1) (f f m (n - 1))

    >

    > ack m n = ackcore ackcore m n

    >

    > Unfortunately, this will fail the occurs check. The only way that Cat

    > could not run into this problem is if it discards the recursive

    > constraint,

     Cat does.

     > which very well could be by your type checker is returning

    > nonsense. (Of course, it's hard to tell for sure from here.)

     I suspect this is the problem. Here is the fibonacci function again

    (forcing it to use ints):

     >> define fib { \f.\n.[n 1 lteq_int [1] [f n 1 sub_int f apply f n 2

     sub_int f apply add_int] if] }

    Here is the type:

    fib : ( -> (A int int int int (A int int int int (A int int int int (A int int i

    nt int ((B -> C) -> A int int int int) int -> A int int int int) int -> A int in

    t int int) int -> A int int int int) int -> A int int int))

    Looks like I am going to have reintroduce recursive types.

    - Christopher

## John Nowak — 2008-02-29 04:34:50

    On Feb 28, 2008, at 10:26 PM, Christopher Diggins wrote:

     > Looks like I am going to have reintroduce recursive types.

     I've come to the same conclusion. They're almost certainly needed if

    you disallow recursive  definitions. ("Disallow" is really the wrong

    way to put it of course; "choose not to introduce" is more accurate.)

    - John

## John Cowan — 2008-02-29 04:35:06

    Joe Bowbeer scripsit:

     > As a former Schemer and fan of continuations, I'm conditioned to view (tail)

    > recursion as the simpler, more powerful concept.  Not looping.

     Sure it's simpler and more powerful.  That's because it's a general goto

    (with transfer of values).  And as Dijkstra said, "the go to statement

    as it stands is just too primitive; it is too much an invitation to make

    a mess of one's program."

    If you haven't actually read Dijkstra's squib, it's very much worth reading at

    http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html

    and numerous other places around the Net.

    --

    John Cowan   http://ccil.org/~cowan    cowan@...

    We want more school houses and less jails; more books and less arsenals;

    more learning and less vice; more constant work and less crime; more

    leisure and less greed; more justice and less revenge; in fact, more of

    the opportunities to cultivate our better natures.  --Samuel Gompers

## William Tanksley, Jr — 2008-02-29 06:19:58

    John Cowan <cowan@...> wrote:

     > Joe Bowbeer scripsit:

    >  > As a former Schemer and fan of continuations, I'm conditioned to view (tail)

    >  > recursion as the simpler, more powerful concept.  Not looping.

    >  Sure it's simpler and more powerful.  That's because it's a general goto

    >  (with transfer of values).  And as Dijkstra said, "the go to statement

    >  as it stands is just too primitive; it is too much an invitation to make

    >  a mess of one's program."

     I'm generally on Knuth's side on this one.

    But I don't see how tail recursion is a general goto statement. It

    seems structured -- in particular, a tail recursion has only one entry

    point.

     >  John Cowan   http://ccil.org/~cowan    cowan@...

     -Wm

## John Cowan — 2008-02-29 13:36:38

    William Tanksley, Jr scripsit:

     > I'm generally on Knuth's side on this one.

     Remember that Knuth thought Dijkstra was *mostly* right, and takes care to

    disclaim the notion that he is in favor of random gotos.  AFAIK, gotos are

    only used in TeX to compensate for Pascal's lack of a return statement.

     > But I don't see how tail recursion is a general goto statement. It

    > seems structured -- in particular, a tail recursion has only one entry

    > point.

     If you take an arbitrary tagbody (a list of statements and labels with

    gotos embedded in the statements), you can restructure it into a sequence

    of functions, one per label, where each function ends by tail calling the

    next function in sequence (corresponding to flowing through the label)

    and each goto is changed into a tail call.  This can be done entirely as

    a local transformation.

    So while it's true that tail calls have only one entry point, entry

    points and labels are basically the same thing from a Scheme perspective,

    something that neither Knuth nor Dijkstra deals with.  "Lambda: the

    ultimate GOTO."

    --

    Well, I have news for our current leaders       John Cowan

    and the leaders of tomorrow: the Bill of        cowan@...

    Rights is not a frivolous luxury, in force      http://www.ccil.org/~cowan

    only during times of peace and prosperity.

    We don't just push it to the side when the going gets tough.  --Molly Ivins

## Joe Bowbeer — 2008-02-29 21:49:58

    On Fri, Feb 29, 2008 at 5:36 AM, John Cowan wrote:

     > William Tanksley, Jr scripsit:

    >

    > > I'm generally on Knuth's side on this one.

    >

    > Remember that Knuth thought Dijkstra was *mostly* right, and takes care to

    > disclaim the notion that he is in favor of random gotos.  AFAIK, gotos are

    > only used in TeX to compensate for Pascal's lack of a return statement.

    >

    > > But I don't see how tail recursion is a general goto statement. It

    > > seems structured -- in particular, a tail recursion has only one entry

    > > point.

    >

    > If you take an arbitrary tagbody (a list of statements and labels with

    > gotos embedded in the statements), you can restructure it into a sequence

    > of functions, one per label, where each function ends by tail calling the

    > next function in sequence (corresponding to flowing through the label)

    > and each goto is changed into a tail call.  This can be done entirely as

    > a local transformation.

    >

    > So while it's true that tail calls have only one entry point, entry

    > points and labels are basically the same thing from a Scheme perspective,

    > something that neither Knuth nor Dijkstra deals with.  "Lambda: the

    > ultimate GOTO."

    >

    >

     I would say, rather: "continuations: the ultimate goto".  And I would mean

    that in a good way:)

    What you're describing is an equivalence between gotos and a sequence of

    function calls, something which is not 100% possible without support for

    recursion, and something which is not 100% efficient without tail-call

    optimization, but I can't see how you can twist this around to indict

    recursion.

    I do sort of see, now, how the anaphoric (from hell?) quality of stack

    programming languages does provide a lot of expressive power without the

    need to resort to recursion.

    --Joe

    [Non-text portions of this message have been removed]

## John Cowan — 2008-02-29 22:20:50

    Joe Bowbeer scripsit:

     > I do sort of see, now, how the anaphoric (from hell?) quality of stack

    > programming languages does provide a lot of expressive power without the

    > need to resort to recursion.

     Remember the original context.  I was agreeing with the statement that

    tail-calling is a confusing way to write down loops.  If you have loop

    syntax, you can easily see where the loop begins and ends and exits.

    If you just have tail calls, it's very easy to make a balls of it.

    I'm not the only Schemer to think this: the standard has named-let and do

    for this very reason, and there are lots of more general looping macros.

    They all use tail-calling to *implement* loops, but that's not what's

    at stake.

    --

    John Cowan  cowan@...  http://ccil.org/~cowan

    Any sufficiently-complicated C or Fortran program contains an ad-hoc,

    informally-specified bug-ridden slow implementation of half of Common Lisp.

            --Greenspun's Tenth Rule of Programming (rules 1-9 are unknown)

## Stevan Apter — 2008-03-01 13:51:59

    my interest in joy was triggered by examples contained in manfred's original

    papers.  those examples suggested that a way of simplifying the expression of

    algorithms which had been overlooked by the mainstream programming languages.

    as a long-time APLer, i was already convinced that one source of complexity

    was explicit looping, but it wasn't until i found myself drowning in a welter

    of explicit recursions on one particular project that i began to suspect that

    it might be possible to do for recursion what APL had done for looping.  joy's

    small set of recursive combinators suggested how this might be done.

    i'm still puzzled why authors of concatenative languages like cat and factor

    have resisted the incorporation of array primitives into their languages. in

    the admittedly trivial examples below, why not write

        1+til / applied to n generates 0..n-1, then add 1

    or

        1 drop til 1+  / add 1 to n, generate 0..n, then drop the first

    instead of either looping or recursion?

    my sense is that programmers (and language designers) *still* do not appreciate

    the power of array programming.  here's an example i posted the other day on

    comp.lang.functional, a general sudoku solver written in q by arthur whitney.

    for readability, i've replaced the case statement of q ($[x;y;z]) with if-then-

    else pseudocode.

    f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

    note the explicit tail-recursion on 'f' in the else clause.  also note that this is

    the standard algorithm used in sudoku solvers written in java, python, ruby, ocaml,

    &c.  compression is achieved through the use of a handlful of array primitives

    (til, find, raze, where, all), one iterator (each), a primitive for updating

    positions of an array (amend), and a single primitive extended from scalars to

    arrays (=).

     ----- Original Message -----

    From: "John Nowak" <john@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, February 28, 2008 9:43 PM

    Subject: Re: [stack] disallowing recursive definitions

    >

    > On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:

    >

    >> As a former Schemer and fan of continuations, I'm conditioned to

    >> view (tail)

    >> recursion as the simpler, more powerful concept.  Not looping.

    >

    > I have a Scheme background as well.

    >

    >> Functional programming languages rely on recursion and still boast of

    >> referential transparency: the ability to substitute function

    >> applications by

    >> their definitions.  But they don't take the substitution as far as

    >> you'd

    >> like to...

    >

    > Indeed.

    >

    >> Functional languages favor recursion over looping because looping

    >> traditionally requires a loop variable whose value changes: a side

    >> effect.

    >

    > What's surprising is how easily the stack lets you write code in an

    > imperative style while remaining purely functional. Here's a small

    > example where, given a natural number, we construct a list from 1 to

    > that number:

    >

    >    ; Scheme, via recursion

    >

    >    (define (foo n)

    >      (let f ((n n) (xs '()))

    >        (if (zero? n)

    >            xs

    >            (f (- n 1) (cons n xs)))))

    >

    >    ; Joy-like, via recursive combinator

    >

    >    foo = null swap ((cons) keep pred) (zero?) until pop

    >

    >    ; Another Joy-like version

    >    ; (prec :: A int int (A int -> A) -> A)

    >

    >    foo = null swap 1 (cons) prec

    >

    > - John

    >

## Stevan Apter — 2008-03-01 13:55:10

    > i'm still puzzled why authors of concatenative languages like cat and factor

    > have resisted the incorporation of array primitives into their languages. in

    > the admittedly trivial examples below, why not write

    >

    >    1+til / applied to n generates 0..n-1, then add 1

    >

    > or

    >

    >    1 drop til 1+  / add 1 to n, generate 0..n, then drop the first

    >

    > instead of either looping or recursion?

    >

     or in postfix notation:

        til 1 +

        1 + til 1 drop

     ----- Original Message -----

    From: "Stevan Apter" <sa@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 8:51 AM

    Subject: Re: [stack] disallowing recursive definitions

    > my interest in joy was triggered by examples contained in manfred's original

    > papers.  those examples suggested that a way of simplifying the expression of

    > algorithms which had been overlooked by the mainstream programming languages.

    > as a long-time APLer, i was already convinced that one source of complexity

    > was explicit looping, but it wasn't until i found myself drowning in a welter

    > of explicit recursions on one particular project that i began to suspect that

    > it might be possible to do for recursion what APL had done for looping.  joy's

    > small set of recursive combinators suggested how this might be done.

    >

    > i'm still puzzled why authors of concatenative languages like cat and factor

    > have resisted the incorporation of array primitives into their languages. in

    > the admittedly trivial examples below, why not write

    >

    >    1+til / applied to n generates 0..n-1, then add 1

    >

    > or

    >

    >    1 drop til 1+  / add 1 to n, generate 0..n, then drop the first

    >

    > instead of either looping or recursion?

    >

    > my sense is that programmers (and language designers) *still* do not appreciate

    > the power of array programming.  here's an example i posted the other day on

    > comp.lang.functional, a general sudoku solver written in q by arthur whitney.

    > for readability, i've replaced the case statement of q ($[x;y;z]) with if-then-

    > else pseudocode.

    >

    > f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

    >

    > note the explicit tail-recursion on 'f' in the else clause.  also note that this is

    > the standard algorithm used in sudoku solvers written in java, python, ruby, ocaml,

    > &c.  compression is achieved through the use of a handlful of array primitives

    > (til, find, raze, where, all), one iterator (each), a primitive for updating

    > positions of an array (amend), and a single primitive extended from scalars to

    > arrays (=).

    >

    >

    > ----- Original Message -----

    > From: "John Nowak" <john@...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Thursday, February 28, 2008 9:43 PM

    > Subject: Re: [stack] disallowing recursive definitions

    >

    >

    >>

    >> On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:

    >>

    >>> As a former Schemer and fan of continuations, I'm conditioned to

    >>> view (tail)

    >>> recursion as the simpler, more powerful concept.  Not looping.

    >>

    >> I have a Scheme background as well.

    >>

    >>> Functional programming languages rely on recursion and still boast of

    >>> referential transparency: the ability to substitute function

    >>> applications by

    >>> their definitions.  But they don't take the substitution as far as

    >>> you'd

    >>> like to...

    >>

    >> Indeed.

    >>

    >>> Functional languages favor recursion over looping because looping

    >>> traditionally requires a loop variable whose value changes: a side

    >>> effect.

    >>

    >> What's surprising is how easily the stack lets you write code in an

    >> imperative style while remaining purely functional. Here's a small

    >> example where, given a natural number, we construct a list from 1 to

    >> that number:

    >>

    >>    ; Scheme, via recursion

    >>

    >>    (define (foo n)

    >>      (let f ((n n) (xs '()))

    >>        (if (zero? n)

    >>            xs

    >>            (f (- n 1) (cons n xs)))))

    >>

    >>    ; Joy-like, via recursive combinator

    >>

    >>    foo = null swap ((cons) keep pred) (zero?) until pop

    >>

    >>    ; Another Joy-like version

    >>    ; (prec :: A int int (A int -> A) -> A)

    >>

    >>    foo = null swap 1 (cons) prec

    >>

    >> - John

    >>

    >

## Daniel Ehrenberg — 2008-03-01 14:17:23

    >  my sense is that programmers (and language designers) *still* do not

    > appreciate

    >  the power of array programming. here's an example i posted the other day on

    >  comp.lang.functional, a general sudoku solver written in q by arthur

    > whitney.

    >  for readability, i've replaced the case statement of q ($[x;y;z]) with

    > if-then-

    >  else pseudocode.

    >

    >  f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p

    > i:x find 0]find til 10]}

    >

    >  note the explicit tail-recursion on 'f' in the else clause. also note that

    > this is

    >  the standard algorithm used in sudoku solvers written in java, python,

    > ruby, ocaml,

    >  &c. compression is achieved through the use of a handlful of array

    > primitives

    >  (til, find, raze, where, all), one iterator (each), a primitive for

    > updating

    >  positions of an array (amend), and a single primitive extended from scalars

    > to

    >  arrays (=).

     I'm having a little trouble parsing this example. Do you think you

    could translate this example to XY, or at least insert parens so it's

    clear where the grouping is, and explain what 27=x... means? The

    resistance of Factor to add array primitives comes from the idea

    within the community that explicit, strongly typed array operations

    are sufficient. (There are words like v* to multiply two sequences of

    numbers.) Replacing v* with * is something that looks prettier but

    doesn't directly add more functionality. Maybe there's someplace in

    the middle, where functions like raze can be added without going to

    full-blown array primitives. Another problem with array primitives is

    that, generalized, they make arrays a little less first-class, but

    this may be a misunderstanding on my part.

    Thanks,

    Dan

## Stevan Apter — 2008-03-01 14:46:18

    ----- Original Message -----

    From: "Daniel Ehrenberg" <microdan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 9:17 AM

    Subject: Re: [stack] disallowing recursive definitions

    >>  my sense is that programmers (and language designers) *still* do not

    >> appreciate

    >>  the power of array programming. here's an example i posted the other day on

    >>  comp.lang.functional, a general sudoku solver written in q by arthur

    >> whitney.

    >>  for readability, i've replaced the case statement of q ($[x;y;z]) with

    >> if-then-

    >>  else pseudocode.

    >>

    >>  f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p

    >> i:x find 0]find til 10]}

    >>

    >>  note the explicit tail-recursion on 'f' in the else clause. also note that

    >> this is

    >>  the standard algorithm used in sudoku solvers written in java, python,

    >> ruby, ocaml,

    >>  &c. compression is achieved through the use of a handlful of array

    >> primitives

    >>  (til, find, raze, where, all), one iterator (each), a primitive for

    >> updating

    >>  positions of an array (amend), and a single primitive extended from scalars

    >> to

    >>  arrays (=).

    >

    > I'm having a little trouble parsing this example. Do you think you

    > could translate this example to XY, or at least insert parens so it's

    > clear where the grouping is, and explain what 27=x... means?

    hi dan.

    f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

    here's the grouping:

    f:{if all x

       then enlist x

       else raze

        f each

         amend[x;i]each

          where

           27=

            x[raze p i:x find 0]find

             til 10]}

    i.e. in the else clause, execute right-to-left (so read left-to-right).

    The

    > resistance of Factor to add array primitives comes from the idea

    > within the community that explicit, strongly typed array operations

    > are sufficient. (There are words like v* to multiply two sequences of

    > numbers.) Replacing v* with * is something that looks prettier but

    > doesn't directly add more functionality. Maybe there's someplace in

    > the middle, where functions like raze can be added without going to

    > full-blown array primitives. Another problem with array primitives is

    > that, generalized, they make arrays a little less first-class, but

    > this may be a misunderstanding on my part.

    note that in f, there is only one "array primitive":  in x=y, x and y

    are either scalars or, if both are arrays, they must be arrays of the

    same "shape" (a scalar is considered to be the same shape as any array.)

    perhaps this a misunderstanding about the term "array primitive".  in APL,

    +, <, =, &c. are extended to arrays, but they are all scalar primitives,

    i.e. they are defined on scalars.  primitives like 'find' and 'where' are

    array (or list) primitives:  they take arrays as arguments and return arrays

    or scalars as results.

    perhaps this is a special case of a wider problem, viz. imprecision about

    the terms "array", "list", &c.  i use these terms interchangeably, whereas

    others may not.  for me, a list or array is an ordered collection parts of

    which (sublists or subarrays or scalars) can be indexed/amended by position.

    note that in some array languages, e.g. k/q, other "bulk datatypes" exist,

    e.g. maps (or dictionaries), which are unordered collections parts of which

    can be indexed by symbols in the domain.  but i always mean objects of

    all bulk-types to be "first-class":  they can be assigned, passed as

    arguments, returned as results.  in every way, they are semantically

    identical to the atomic values out of which they are constructed.  moreover,

    all primitives (e.g. +) are defined (at least in principle) on all bulk-types.

    e.g. a vector can be added to a map (yielding a map), a table can be added to

    a vector (yielding a table), &c.  this "orthogonality property" is partly why

    complex algorithms like the sudoku solver can be expressed so simply.

    >

    > Thanks,

    >

    > Dan

    >

## Christopher Diggins — 2008-03-01 19:35:18

    On Sat, Mar 1, 2008 at 8:51 AM, Stevan Apter <sa@...> wrote:

     > i'm still puzzled why authors of concatenative languages like cat and factor

    > have resisted the incorporation of array primitives into their languages.

     Map, filter, fold, etc. are all part of the core Cat language. I

    consider all of these array primitives. The Cat concept of list is

    more or less analgous to an array, but is agnostic about

    implementation details. An implementation is left to its own devices

    as to what the performance characteristics of lists are. Sorry its not

    more clear in the current documentation.

     >in

    > the admittedly trivial examples below, why not write

    >

    > 1+til / applied to n generates 0..n-1, then add 1

     In Cat

    n [1 +] map

     > or

    >

    > 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first

     n [1] drop

     > instead of either looping or recursion?

     Sure completely valid. Of course sometimes loops are fun to have

    outside of the context of a list.

     > my sense is that programmers (and language designers) *still* do not

    > appreciate

    > the power of array programming.

     Well I know that Slava (the author of Factor) does, and I'd like to

    feel that I do. Its not really fair to single us out in this.

     > here's an example i posted the other day on

    > comp.lang.functional, a general sudoku solver written in q by arthur

    > whitney.

    > for readability, i've replaced the case statement of q ($[x;y;z]) with

    > if-then-

    > else pseudocode.

    >

    > f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p

    > i:x find 0]find til 10]}

    >

    > note the explicit tail-recursion on 'f' in the else clause. also note that

    > this is

    > the standard algorithm used in sudoku solvers written in java, python, ruby,

    > ocaml,

    > &c. compression is achieved through the use of a handlful of array

    > primitives

    > (til, find, raze, where, all), one iterator (each), a primitive for updating

    > positions of an array (amend), and a single primitive extended from scalars

    > to

    > arrays (=).

     I'll have to look more closely at this (I don't know what "til",

    "find", "raze", "where", "all", "each", and "amend" do). But it should

    be easy to implement something similar.

    Nonetheless, your original point is still valid that some more array

    processing primitives would be valuable in Cat. I'll add some to the

    specification.

    - Christopher

## Stevan Apter — 2008-03-01 20:24:41

    ----- Original Message -----

    From: "Christopher Diggins" <cdiggins@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 2:35 PM

    Subject: Re: [stack] disallowing recursive definitions

    > On Sat, Mar 1, 2008 at 8:51 AM, Stevan Apter <sa@...> wrote:

    >> i'm still puzzled why authors of concatenative languages like cat and factor

    >> have resisted the incorporation of array primitives into their languages.

    >

    > Map, filter, fold, etc. are all part of the core Cat language. I

    > consider all of these array primitives.

    i haven't looked at cat's implementation of these combinators.  how

    would you use map to add a matrix to a vector?  for example, suppose

    you have

        1 2 3 4

        5 6 7 8

    and

        10 20 30 40

    you want to add the vector to each row of the matrix.  now suppose

    you have a second vector

        11 12

    and you want to add each of those to each row of the matrix.

    in general, how do you map/filter/fold/zip functions which take more

    than one argument?

    > The Cat concept of list is

    > more or less analgous to an array, but is agnostic about

    > implementation details. An implementation is left to its own devices

    > as to what the performance characteristics of lists are. Sorry its not

    > more clear in the current documentation.

    >

    >>in

    >> the admittedly trivial examples below, why not write

    >>

    >> 1+til / applied to n generates 0..n-1, then add 1

    >

    > In Cat

    >

    > n [1 +] map

    >

    >> or

    >>

    >> 1 drop til 1+ / add 1 to n, generate 0..n, then drop the first

    >

    > n [1] drop

    >

    >> instead of either looping or recursion?

    >

    > Sure completely valid. Of course sometimes loops are fun to have

    > outside of the context of a list.

    sometimes they're necessary, but i can't say i have any fun writing

    them.  :-)

    >

    >> my sense is that programmers (and language designers) *still* do not

    >> appreciate

    >> the power of array programming.

    >

    > Well I know that Slava (the author of Factor) does, and I'd like to

    > feel that I do. Its not really fair to single us out in this.

    that's true in some sense.  i should have said something like this:

    given the role that simplicity and expressiveness play in the cognitive

    economy of concatenative language designers, i'd expect them to be

    close students of the gains in these areas made by iverson and his

    students over the last 45 years.  (yes, it really has been that long

    since iverson published "a programming language.")

    >

    >> here's an example i posted the other day on

    >> comp.lang.functional, a general sudoku solver written in q by arthur

    >> whitney.

    >> for readability, i've replaced the case statement of q ($[x;y;z]) with

    >> if-then-

    >> else pseudocode.

    >>

    >> f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p

    >> i:x find 0]find til 10]}

    >>

    >> note the explicit tail-recursion on 'f' in the else clause. also note that

    >> this is

    >> the standard algorithm used in sudoku solvers written in java, python, ruby,

    >> ocaml,

    >> &c. compression is achieved through the use of a handlful of array

    >> primitives

    >> (til, find, raze, where, all), one iterator (each), a primitive for updating

    >> positions of an array (amend), and a single primitive extended from scalars

    >> to

    >> arrays (=).

    >

    > I'll have to look more closely at this (I don't know what "til",

    > "find", "raze", "where", "all", "each", and "amend" do). But it should

    > be easy to implement something similar.

    >

    > Nonetheless, your original point is still valid that some more array

    > processing primitives would be valuable in Cat. I'll add some to the

    > specification.

    i'm not sure i had much of a point, beyond wanting to make a gesture of

    mental irritability.  concatenative languages are lovely, but, judged on

    the basis of how much code one has to write, not expressive enough to

    convince me i should use one.

    >

    > - Christopher

    >

## William Tanksley, Jr — 2008-03-01 22:08:04

    Christopher Diggins <cdiggins@...> wrote:

     > Stevan Apter <sa@...> wrote:

    >  > i'm still puzzled why authors of concatenative languages like cat and factor

    >  > have resisted the incorporation of array primitives into their languages.

     It shouldn't be a puzzle... They don't understand. It's hard to get

    started learning about it.

    The existing array languages are, with only two exceptions, closed

    source. (The early J interpreter was available, although I don't know

    how to get it now, and I couldn't ever figure out how to read it.) A+

    is unreservedly open source, of course, as is QNIAL. I found A+ to be

    very hard to figure out, QNIAL fairly easy.

     >  Map, filter, fold, etc. are all part of the core Cat language. I

    >  consider all of these array primitives.

     I suppose they technically are. They're just a beginning, though.

     > The Cat concept of list is

    >  more or less analgous to an array, but is agnostic about

    >  implementation details. An implementation is left to its own devices

    >  as to what the performance characteristics of lists are. Sorry its not

    >  more clear in the current documentation.

     That's a pretty important point, really. It makes the difference

    between an O(n) implementation and an O(n^2) one. I'd really rather it

    be specified.

     >  > my sense is that programmers (and language designers) *still* do not

    >  > appreciate the power of array programming.

     We don't. I don't. I wish I did, but it's a steep hill to climb.

     >  Nonetheless, your original point is still valid that some more array

    >  processing primitives would be valuable in Cat. I'll add some to the

    >  specification.

     I like the implicit iteration.

     >  - Christopher

     -Wm

## Christopher Diggins — 2008-03-01 22:11:33

    On Sat, Mar 1, 2008 at 5:08 PM, William Tanksley, Jr

    <wtanksleyjr@...> wrote:

     >

    > Christopher Diggins <cdiggins@...> wrote:

    > > Stevan Apter <sa@...> wrote:

    > > > i'm still puzzled why authors of concatenative languages like cat and

    > factor

    > > > have resisted the incorporation of array primitives into their

    > languages.

    >

    > It shouldn't be a puzzle... They don't understand.

     That is awfully presumptious of you.

    - Christopher

## Stevan Apter — 2008-03-01 22:43:04

    ----- Original Message -----

    From: "William Tanksley, Jr" <wtanksleyjr@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 5:08 PM

    Subject: Re: [stack] disallowing recursive definitions

    > Christopher Diggins <cdiggins@...> wrote:

    >> Stevan Apter <sa@...> wrote:

    >>  > i'm still puzzled why authors of concatenative languages like cat and factor

    >>  > have resisted the incorporation of array primitives into their languages.

    >

    > It shouldn't be a puzzle... They don't understand. It's hard to get

    > started learning about it.

    >

    > The existing array languages are, with only two exceptions, closed

    > source. (The early J interpreter was available, although I don't know

    > how to get it now, and I couldn't ever figure out how to read it.) A+

    > is unreservedly open source, of course, as is QNIAL. I found A+ to be

    > very hard to figure out, QNIAL fairly easy.

    there are several free APL interpreters available:

    http://www.vector.org.uk/?area=dnld&page=content/interpreters

    vector is probably the best general site for information about array

    languages.  J and Q (K) are ascii.  J is free, but i agree that is

    somewhat forbidding.  a freeware version of K5 has been planned, but

    isn't available yet.

    >

    >>  Map, filter, fold, etc. are all part of the core Cat language. I

    >>  consider all of these array primitives.

    >

    > I suppose they technically are. They're just a beginning, though.

    yes.

    >

    >> The Cat concept of list is

    >>  more or less analgous to an array, but is agnostic about

    >>  implementation details. An implementation is left to its own devices

    >>  as to what the performance characteristics of lists are. Sorry its not

    >>  more clear in the current documentation.

    >

    > That's a pretty important point, really. It makes the difference

    > between an O(n) implementation and an O(n^2) one. I'd really rather it

    > be specified.

    yes.  if you intend to let these datastructures bear the full weight of

    "array programming" (by which i mean crafting your algorithms in such

    a way that the language performs the iteration) then the implementation

    had better be sharp -- at least as efficient as what the programmer can

    do by explicitly iterating (and, one would hope, better.)

    >

    >>  > my sense is that programmers (and language designers) *still* do not

    >>  > appreciate the power of array programming.

    >

    > We don't. I don't. I wish I did, but it's a steep hill to climb.

    it goes in both directions.  when i'm forced to write the simplest loop,

    i usually get it wrong the first time, the second time, ...  it's

    embarrassing!  the trick is to internalize the idioms, which means

    learning them in the first place.  a good resource is eugene macdonell's

    k "finger exercises:

    http://www.kx.com/technical/contribs/eugene/kidioms.html

    so-called because having them at your fingertips as idioms is where

    the productivity comes from.

    and a good exercise:  solve them in your favorite language.

    >

    >>  Nonetheless, your original point is still valid that some more array

    >>  processing primitives would be valuable in Cat. I'll add some to the

    >>  specification.

    >

    > I like the implicit iteration.

    me too, but getting the design right isn't easy, and if it's an after-

    thought, it won't simplify things at all.

    >

    >>  - Christopher

    >

    > -Wm

    >

## William Tanksley, Jr — 2008-03-02 00:26:29

    Christopher Diggins <cdiggins@...> wrote:

     > William Tanksley, Jr <wtanksleyjr@...> wrote:

    >  > > > i'm still puzzled why authors of concatenative languages like cat and

    >  > factor

    >  > > > have resisted the incorporation of array primitives into their

    >  > languages.

    >  > It shouldn't be a puzzle... They don't understand.

    >  That is awfully presumptious of you.

     I didn't expect or intend to offend, but no, it's not presumptuous.

    You yourself said, 'I don't know what "til", "find", "raze", "where",

    "all", "each", and "amend" do'. The "array primitives" that you do

    understand, you only know about because you're extremely conversant

    with functional list-processing languages (not array languages). This

    shouldn't be insulting to you; you're a highly productive and

    intelligent person who thoroughly understands CS. I want to challenge

    the array language community to come out and educate us if they're

    dissatisfied with our work.

     >  - Christopher

     -Wm

## Stevan Apter — 2008-03-02 01:19:19

    ----- Original Message -----

    From: "William Tanksley, Jr" <wtanksleyjr@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 7:26 PM

    Subject: Re: [stack] disallowing recursive definitions

    > Christopher Diggins <cdiggins@...> wrote:

    >> William Tanksley, Jr <wtanksleyjr@...> wrote:

    >>  > > > i'm still puzzled why authors of concatenative languages like cat and

    >>  > factor

    >>  > > > have resisted the incorporation of array primitives into their

    >>  > languages.

    >

    >>  > It shouldn't be a puzzle... They don't understand.

    >

    >>  That is awfully presumptious of you.

    >

    > I didn't expect or intend to offend, but no, it's not presumptuous.

    > You yourself said, 'I don't know what "til", "find", "raze", "where",

    > "all", "each", and "amend" do'. The "array primitives" that you do

    > understand, you only know about because you're extremely conversant

    > with functional list-processing languages (not array languages). This

    > shouldn't be insulting to you; you're a highly productive and

    > intelligent person who thoroughly understands CS. I want to challenge

    > the array language community to come out and educate us if they're

    > dissatisfied with our work.

    that would be me i guess.  with only a few exceptions, most of the

    arrayheads i know don't have much interest in programming language

    theory.  hell, they hardly even think of APL as a language.  it's

    just a tool for doing math, mostly of the financial kind.  one

    exception that comes to mind is john scholes, CTO and principal

    language designer for dyalog, the APL company in the UK.  john has

    done some very cool work in meshing combinators, type theory, and

    array programming.

    as far as doing missionary work for arrays to the concatenative

    community (jeez i've come to despise that word), isn't that exactly what

    i've been doing for five years?  :-)  three toy languages, innumerable

    examples, &c.  (ok, now i'm starting to whine like mrs clinton.)  seriously

    though, i really am puzzled why none of the *serious* language designers

    around here (christopher and slava comes to mind) agree that

    array primitives and composition-based functional languages form

    a natural fit.  i've had this conversation with slava over on his

    factor chat-room, and i've never been able to persuade him on this

    point.  i think (and this is just pure speculation on my part) that

    you have tohave to have a bad feeling about writing a loop (or an

    explicit recursion) before you see the value of the alternative.

    you have to resent the fact that the language is making you write

    the same damned loop or recursion over and over again.  i mean,

    these are computers, right?  you should be able to tell it just

    once:  when i add an n-dimensional array and a m-dimensional

    array, and the structures cohere, then *you* figure out how to

    write the loop.

    remember that a lot of APLers learned APL as their first programming

    language (in business-school or at one of the investment banks back

    in the 80s, or in high-school in the 70s, when APL had a significant

    presence in education) and have never been able to bring themselves to

    learn java or c.  so for them (and for me too) looping and recursion

    are what you do when you can't find an array solution to your problem.

    maybe you can't find one because there isn't one to be found, or maybe

    you're just not looking at the problem correctly.  either way, you

    have to want to find it.  fortunately, problems like that don't crop

    up all that often in real life.  you have to go out and look for them.

## Daniel Ehrenberg — 2008-03-02 01:34:12

    >  note that in f, there is only one "array primitive": in x=y, x and y

    >  are either scalars or, if both are arrays, they must be arrays of the

    >  same "shape" (a scalar is considered to be the same shape as any array.)

    >

    >  perhaps this a misunderstanding about the term "array primitive". in APL,

    >  +, <, =, &c. are extended to arrays, but they are all scalar primitives,

    >  i.e. they are defined on scalars. primitives like 'find' and 'where' are

    >  array (or list) primitives: they take arrays as arguments and return arrays

    >  or scalars as results.

     You're right, there is some misunderstanding. What I was talking

    about, and what Factor's missing, is the property of things like "+"

    to denote both scalar and vector addition; how, in APL-based

    languages, certain operators like +, =, <, etc are defined to map

    their operation to atoms within vectors (assuming that shapes match).

    Everything else can be fairly easily defined in the library with no

    modifications to existing code, if it doesn't already exist. I might

    be misunderstanding the nature of array languages, but here's my

    problem with this: it creates a primitive, difficult-to-extend concept

    of an array which isn't quite first-class as far as I can tell.

    Anyway, I'm in the process of decoding the example given (since I

    don't know Q) and translating it directly to Factor to see if adding

    any idioms would be appropriate. Stevan, could you tell me what the

    function f is supposed to take as an argument? Either way, when I find

    myself writing explicit tail recursion (which is fairly but not

    extremely rare in Factor) I often try to abstract it into a

    combinator. When I make these abstractions, it's only because the

    existing ones (the higher order functions like each, map and reduce

    that Factor and APL basically share) can't express it. I can't imagine

    a situation where the fact that + operates on vectors as well as

    scalars would change whether I would have to write explicit tail

    recursion.

    I use tail recursion when I'm either (a) interfacing with non-arrays

    that still have to be iterated over in some way, for example an I/O

    stream (b) doing something weird that'd be awkward to express in terms

    of the abstractions I know. So (a) would be hard to eliminate, and (b)

    is more of a cause for concern. I encountered a lot of (b) cases in

    implementing things like Unicode normalization and case conversion,

    and in those cases I built some semi-general abstractions using tail

    recursion. I wonder if some of these should be moved to a more

    general-purpose library, but even if they should, that's not a case

    for array primitives in the sense of + to be integrated deeply into

    the language.

    (Just for the record, it's very annoying that there are two languages

    named Q, and the one relevant here has a very small online footprint,

    and that in that small website, the maintainers can't be bothered to

    type out "docs", instead calling the directory "d". Also, I just had a

    sort of "whoa" moment when I realized that the same guy who came up

    with the first good polynomial-time tree diffing algorithm is the same

    guy who's doing all this K/Q stuff...)

    Dan

## Stevan Apter — 2008-03-02 02:21:23

    hi dan

     ----- Original Message -----

    From: "Daniel Ehrenberg" <microdan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 8:34 PM

    Subject: Re: [stack] disallowing recursive definitions

    >>  note that in f, there is only one "array primitive": in x=y, x and y

    >>  are either scalars or, if both are arrays, they must be arrays of the

    >>  same "shape" (a scalar is considered to be the same shape as any array.)

    >>

    >>  perhaps this a misunderstanding about the term "array primitive". in APL,

    >>  +, <, =, &c. are extended to arrays, but they are all scalar primitives,

    >>  i.e. they are defined on scalars. primitives like 'find' and 'where' are

    >>  array (or list) primitives: they take arrays as arguments and return arrays

    >>  or scalars as results.

    >

    > You're right, there is some misunderstanding. What I was talking

    > about, and what Factor's missing, is the property of things like "+"

    > to denote both scalar and vector addition; how, in APL-based

    > languages, certain operators like +, =, <, etc are defined to map

    > their operation to atoms within vectors (assuming that shapes match).

    > Everything else can be fairly easily defined in the library with no

    > modifications to existing code, if it doesn't already exist. I might

    > be misunderstanding the nature of array languages, but here's my

    > problem with this: it creates a primitive, difficult-to-extend concept

    > of an array which isn't quite first-class as far as I can tell.

    in k, two arrays can be added if either or both are atoms, or their

    shapes are conformable.  so e.g. a 2x3x4 can be added to an array of

    shape 2 (a vector), or 2x3, or 2x3x4, or 2x3x4x...  or using various

    combinations of each, each-left, and each-right, a 2x3x4 can be added

    to a 7x2x3x4 or ...   the combinators allow you to control the way

    the dimensions line up for the operations.

    the k bulk datatypes are:  list, map, table (transposed map of lists),

    and keytable (map of a table with unique rows to a table.)  all

    primitives are defined on all types and combinations of types.  the

    combinations have different comformability and extension rules.

    an interesting question is what machinery, and in what strength,

    could be added to support user-defined datatypes.  at minimum, it

    would require (i) defining what the primitives do on each combination

    of the new datatype and existing datatypes, and (ii) what the

    conformability rules are (since for any datatype x, you would have

    to support at the very least lists and maps of x's.  an open question.

    but k, at least, has been grudging about the addition of new datatypes.

    in practice, the policy has always been:  simulate the new datatype,

    see how useful it is, think about how it could be integrated, &c.

    the process seems to take about five years.  a small number of ideas

    make it into the interpreter core, but when they do, their behavior

    is fully defined for each primitive and each bulk datatype.  at some

    point, i may describe the evolution of the concept of tables in k, from

    APL\360 to q.  it's an interesting story.

    so rather than proliferate datatypes (indefinitely if you leave it

    up to the programmer) and give up orthogonality, we try to represent

    pieces of the world with a very small set of bulk datatypes and an

    orthogonal, generalized set of primitives.  (atomic datatypes are

    easier to deal with, and there are lots of these.)

    >

    > Anyway, I'm in the process of decoding the example given (since I

    > don't know Q) and translating it directly to Factor to see if adding

    > any idioms would be appropriate. Stevan, could you tell me what the

    > function f is supposed to take as an argument?

    http://www.wagerlabs.com/blog/2008/02/shortest-sudoku.html

    Either way, when I find

    > myself writing explicit tail recursion (which is fairly but not

    > extremely rare in Factor) I often try to abstract it into a

    > combinator. When I make these abstractions, it's only because the

    > existing ones (the higher order functions like each, map and reduce

    > that Factor and APL basically share

    no, i think that's a misconception.  the k higher-order functions

    take functions of any valence.  e.g.

        f:{x+y*z}

        f'[a;b;c] / each applies f to corresponding elements of a,b,c

    ? ) can't express it. I can't imagine

    > a situation where the fact that + operates on vectors as well as

    > scalars would change whether I would have to write explicit tail

    > recursion.

    the sudoku solver contains a single scalar function =.  you'd have

    to write either a loop or a recursion to handle that.  other examples

    abound.  see eugene macdonell's paper, linked to in an earlier post.

    this is what i was unable to get slava to see:  extending + to arrays

    (or in factor's case, vectors via v+) by itself doesn't seem to get

    you anything terribly useful.  so big deal, how often do i want to

    add vectors?

    >

    > I use tail recursion when I'm either (a) interfacing with non-arrays

    > that still have to be iterated over in some way, for example an I/O

    > stream (b) doing something weird that'd be awkward to express in terms

    > of the abstractions I know. So (a) would be hard to eliminate,

    why isn't a stream a list?

    and (b)

    > is more of a cause for concern. I encountered a lot of (b) cases in

    > implementing things like Unicode normalization and case conversion,

    > and in those cases I built some semi-general abstractions using tail

    > recursion. I wonder if some of these should be moved to a more

    > general-purpose library, but even if they should, that's not a case

    > for array primitives in the sense of + to be integrated deeply into

    > the language.

    lower-to-upper case in k:

        u:_ci@[!256;97+!26;-;32]

        i:_ic"a99*bc"

        u i

      "A99*BC"

    no loops, no recursion.  depends on - being defined on arrays.

    look, this is what i meant when i said that the power of the array

    approach is not obvious -- it can't be "read off" the definitions of

    the primitives.  or if i didn't say that, that's what i meant.  as

    i *have* been trying to say for several years now is that with the

    right set of primitives and datatypes, all sorts of non-obvious

    solutions arise.  that's why the k sudoku is so short (i think it's

    down to 54 characters now.)

    >

    > (Just for the record, it's very annoying that there are two languages

    > named Q, and the one relevant here has a very small online footprint,

    > and that in that small website, the maintainers can't be bothered to

    > type out "docs", instead calling the directory "d". Also, I just had a

    > sort of "whoa" moment when I realized that the same guy who came up

    > with the first good polynomial-time tree diffing algorithm is the same

    > guy who's doing all this K/Q stuff...)

    you mean dennis shasha?  he's also the math games editor for scientific

    american.  he's the man!

    >

    > Dan

    >

## Daniel Ehrenberg — 2008-03-02 03:34:10

    >  > I use tail recursion when I'm either (a) interfacing with non-arrays

    >  > that still have to be iterated over in some way, for example an I/O

    >  > stream (b) doing something weird that'd be awkward to express in terms

    >  > of the abstractions I know. So (a) would be hard to eliminate,

    >

    >  why isn't a stream a list?

     Well, if by "list" you mean "lazy linked list", Factor doesn't work

    like that for input because it'd require memoizing past input values,

    and it wouldn't flush output well. If you mean something else I don't

    understand. As far as making input something you can iterate over with

    "each", that's something I'm working on (though it won't extend to

    map).

     >

    >  lower-to-upper case in k:

    >

    >  u:_ci@[!256;97+!26;-;32]

    >  i:_ic"a99*bc"

    >  u i

    >  "A99*BC"

    >

    >  no loops, no recursion. depends on - being defined on arrays.

    >

    >  look, this is what i meant when i said that the power of the array

    >  approach is not obvious -- it can't be "read off" the definitions of

    >  the primitives. or if i didn't say that, that's what i meant. as

    >  i *have* been trying to say for several years now is that with the

    >  right set of primitives and datatypes, all sorts of non-obvious

    >  solutions arise. that's why the k sudoku is so short (i think it's

    >  down to 54 characters now.)

     Umm, well, in the general Unicode case, there's some more complicated

    table lookup involved, and a bunch of corner cases. My Factor

    implementation is somewhat inelegant, and it'd be interesting to see

    something in K like that. Your implementation could be written in

    Factor as

    : >upper ( string -- newstring )

        [ dup CHAR: a CHAR: z between? [ CHAR: A CHAR: a - + ] when ] map ;

    These definitions have basically the same token count, so this example

    doesn't present an advantage or disadvantage of K.

    Dan

## Stevan Apter — 2008-03-02 06:14:34

    ----- Original Message -----

    From: "Daniel Ehrenberg" <microdan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, March 01, 2008 10:34 PM

    Subject: Re: [stack] disallowing recursive definitions

    >>  > I use tail recursion when I'm either (a) interfacing with non-arrays

    >>  > that still have to be iterated over in some way, for example an I/O

    >>  > stream (b) doing something weird that'd be awkward to express in terms

    >>  > of the abstractions I know. So (a) would be hard to eliminate,

    >>

    >>  why isn't a stream a list?

    >

    > Well, if by "list" you mean "lazy linked list", Factor doesn't work

    > like that for input because it'd require memoizing past input values,

    > and it wouldn't flush output well. If you mean something else I don't

    > understand. As far as making input something you can iterate over with

    > "each", that's something I'm working on (though it won't extend to

    > map).

    >>

    >>  lower-to-upper case in k:

    >>

    >>  u:_ci@[!256;97+!26;-;32]

    >>  i:_ic"a99*bc"

    >>  u i

    >>  "A99*BC"

    >>

    >>  no loops, no recursion. depends on - being defined on arrays.

    >>

    >>  look, this is what i meant when i said that the power of the array

    >>  approach is not obvious -- it can't be "read off" the definitions of

    >>  the primitives. or if i didn't say that, that's what i meant. as

    >>  i *have* been trying to say for several years now is that with the

    >>  right set of primitives and datatypes, all sorts of non-obvious

    >>  solutions arise. that's why the k sudoku is so short (i think it's

    >>  down to 54 characters now.)

    >

    > Umm, well, in the general Unicode case, there's some more complicated

    > table lookup involved, and a bunch of corner cases. My Factor

    > implementation is somewhat inelegant, and it'd be interesting to see

    > something in K like that.  Your implementation could be written in

    > Factor as

    >

    > : >upper ( string -- newstring )

    >    [ dup CHAR: a CHAR: z between? [ CHAR: A CHAR: a - + ] when ] map ;

    >

    > These definitions have basically the same token count, so this example

    > doesn't present an advantage or disadvantage of K.

    apologies for misleading you with how i presented my example.  here's

    a better explanation:

        _ic takes a string and returns a vector of ascii values

        _ci takes a vector of ascii values and returns a string

    e.g.

        _ic "a9."

    97 57 46

    so we create a constant u by replacing in 0-255 the ascii values for

    the lower-case letters with the ascii values for upper-case letters,

    and convert that vector to a string:

        u:_ci@[!256;97+!26;-;32]

    @ takes four arguments:  something to amend (in this case 0 to 255),

    indices into that thing (97+0 to 25), a function of two arguments (-),

    and a value (32).  so this reads:  int-to-char of subtract 32 from

    positions 97+!26 in !256.  this is an example of an array idiom --

    you use phrases like this so often, you see them as building blocks

    in larger structures.  what gives this approach its power is that

    the same functional schemes are used repeatedly to solve different

    problems.

    we don't u compute that again.  (the language could easily supply

    this to us as a predefined "feature", but why bother?)

    then for each string we want to upper-case, we convert it:

        _ic "ab3Xc"

    97 98 51 88 99

    and use those values to index out the values in u:

        u _ic "ab3Xc"

    "AB3XC"

    upper-casing is just indexing, so the upper-case function is just

        {u _ic x}

    >

    > Dan

    >

## Joe Bowbeer — 2008-02-29 05:06:40

    On Thu, Feb 28, 2008 at 8:35 PM, John Cowan wrote:

     > Joe Bowbeer scripsit:

    >

    > > As a former Schemer and fan of continuations, I'm conditioned to view

    > (tail)

    > > recursion as the simpler, more powerful concept.  Not looping.

    >

    > Sure it's simpler and more powerful.  That's because it's a general goto

    > (with transfer of values).  And as Dijkstra said, "the go to statement

    > as it stands is just too primitive; it is too much an invitation to make

    > a mess of one's program."

    >

    > If you haven't actually read Dijkstra's squib, it's very much worth

    > reading at

    >

    > http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html<http://www.u.arizona.edu/%7Erubinson/copyright_violations/Go_To_Considered_Harmful.html>

    > and numerous other places around the Net.

    >

    >

     As far as I know, Dijkstra didn't have a beef with recursion.

    The author of the following retrospective writes that Dijkstra probably

    considered recursion to be intellectually easier to grasp than iterative

    looping:

     http://david.tribble.com/text/goto.html

    In any event, it's clear from Dijkstra's letter than he didn't consider

    recursion to be harmful!

    To avoid confusion, I should have used the word "elegant".

    Recursion is the simple, elegant solution.

    --

    Joe Bowbeer

      http://mitpress.mit.edu/sicp/front/node3.html

        [ Sobre los gustos no hay disputa. ]

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2008-03-03 17:58:23

    John Cowan <cowan@...> wrote:

     > William Tanksley, Jr scripsit:

    >  > I'm generally on Knuth's side on this one.

    >  Remember that Knuth thought Dijkstra was *mostly* right, and takes care to

    >  disclaim the notion that he is in favor of random gotos.  AFAIK, gotos are

    >  only used in TeX to compensate for Pascal's lack of a return statement.

     Knuth seemed to see more use for it than that. But I grant your point,

    and I wouldn't want to be _against_ Dijkstra on any point, anyhow.

     >  > But I don't see how tail recursion is a general goto statement. It

    >  > seems structured -- in particular, a tail recursion has only one entry

    >  > point.

    >  If you take an arbitrary tagbody (a list of statements and labels with

    >  gotos embedded in the statements), you can restructure it into a sequence

    >  of functions, one per label, where each function ends by tail calling the

    >  next function in sequence (corresponding to flowing through the label)

    >  and each goto is changed into a tail call.  This can be done entirely as

    >  a local transformation.

     That feels questionable to me. GOTOs can be conditional, and tags can

    be inside conditions as well. In short and to be formal, it seems to

    me that tagbodies don't form properly nested trees, as functions

    must... I think they form digraphs.

    I hesitate to pronounce strongly on this, because I haven't studied

    it, and you clearly have. But perhaps if I make my mistake out loud

    you can correct me. :-)

     >  "Lambda: the ultimate GOTO."

     An interesting point. A recursive tail call in an applicative language

    can do one thing that a simple GOTO cannot: it can, at one stroke,

    change the value of all the parameters of the function to something

    else. This would certainly be sufficient to make an applicative

    theorist blanch...

     >  Well, I have news for our current leaders       John Cowan

     -Wm

## John Cowan — 2008-03-03 18:12:18

    Joe Bowbeer scripsit:

     > As far as I know, Dijkstra didn't have a beef with recursion.

     It seems to me from _A Discipline of Programming_ that he thought

    recursion a special case, relatively unimportant: the programming language

    he introduces there does not admit it.  And he is very much on record as

    condemning the reduction of iteration to (tail) recursion as a false

    reduction, _ignotum per ignotius_.

     > Recursion is the simple, elegant solution.

     Recursion can be employed elegantly, when it mirrors induction, or

    inelegantly, when it is an invitation to make a mess of your program.

    Not all syntactic sugar is oncogenetic: there are good reasons to use

    both let and lambda instead of just lambda.

    --

    As you read this, I don't want you to feel      John Cowan

    sorry for me, because, I believe everyone       cowan@...

    will die someday.                               http://www.ccil.org/~cowan

            --From a Nigerian-type scam spam

## John Cowan — 2008-03-03 18:36:52

    William Tanksley, Jr scripsit:

     > That feels questionable to me. GOTOs can be conditional,

     True, but that doesn't matter: you translate the conditional GO into a

    conditional invocation of the function corresponding to the labeled code.

     > and tags can be inside conditions as well.

     In a Lisp tagbody, tags are only recognized at the top level, so a label

    within a conditional becomes a label at the top level of a nested tagbody

    within the conditional.  GOs are allowed to go to a tag in any tagbody

    they are lexically nested in.  In order to implement this using functions,

    you have to lambda-lift the functions generated from any nested tagbody,

    but that again is well-understood, local, and easily performed.

    This actually allows rather more of a mess than even "normal" structured

    programming languages with GO TO allow.  Most languages don't permit you

    to GO TO into a construct from outside, though older versions allowed jumps

    out-then-back-in (Fortran 66) and/or in-and-then-back-out (simple Basics

    and others).  However, if you lambda-lift everything, you can actually

    jump around however you please.

     > In short and to be formal, it seems to me that tagbodies don't form

    > properly nested trees, as functions must... I think they form digraphs.

     A plausible way to think about tail recursion is to assume an infinite

    return stack, and then postpone all the returns until the end of the

    program (when they do not actually have to be performed).  So although the

    call graph is a tree, the actually extant part of it is a random directed

    graph, and all the retracing is simply banished from consideration.

    This is essentially how Chicken implements Scheme, except that because

    the control stack (the C stack) is not infinite, it is necessary to reset

    it periodically, banishing any embedded data structures that are still

    live to the C heap.  In effect, the C stack becomes the first generation

    of the Scheme heap.

     > An interesting point. A recursive tail call in an applicative language

    > can do one thing that a simple GOTO cannot: it can, at one stroke,

    > change the value of all the parameters of the function to something

    > else. This would certainly be sufficient to make an applicative

    > theorist blanch...

     Absolutely.  LAMBDA = GOTO + argument passing; that's what makes it

    "ultimate".

    --

    Cash registers don't really add and subtract;           John Cowan

            they only grind their gears.                    cowan@...

    But then they don't really grind their gears, either;

            they only obey the laws of physics.  --Unknown

## Joe Bowbeer — 2008-03-03 18:40:52

    On Mon, Mar 3, 2008 at 10:12 AM, John Cowan wrote:

     > Joe Bowbeer scripsit:

    >

    > > As far as I know, Dijkstra didn't have a beef with recursion.

    >

    > It seems to me from _A Discipline of Programming_ that he thought

    > recursion a special case, relatively unimportant: the programming language

    > he introduces there does not admit it.  And he is very much on record as

    > condemning the reduction of iteration to (tail) recursion as a false

    > reduction, _ignotum per ignotius_.

    >

     But he mentions recursion favorably in the letter you were using to indict

    it.  I'm confused.

     > > Recursion is the simple, elegant solution.

    >

    > Recursion can be employed elegantly, when it mirrors induction, or

    > inelegantly, when it is an invitation to make a mess of your program.

    > Not all syntactic sugar is oncogenetic: there are good reasons to use

    > both let and lambda instead of just lambda.

    >

     By "mess" you mean obfuscated and unintelligible?  I agree.  Recursion is an

    elegant concept that can lead to terse, confusing code.  But so, in my

    opinion, can concatenative programming, so I have trouble understanding your

    complaint.  If you are saying that adding recursion to concatenative

    programming is beyond the pale, I think I could agree with that.

    --Joe

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2008-03-03 19:48:27

    John Cowan <cowan@...> wrote:

     > William Tanksley, Jr scripsit:

    >  > and tags can be inside conditions as well.

    >  In a Lisp tagbody, tags are only recognized at the top level, so a label

    >  within a conditional becomes a label at the top level of a nested tagbody

    >  within the conditional.  GOs are allowed to go to a tag in any tagbody

    >  they are lexically nested in.  In order to implement this using functions,

    >  you have to lambda-lift the functions generated from any nested tagbody,

    >  but that again is well-understood, local, and easily performed.

     I don't know the term "lambda-lift", and Google knows of it mainly as

    a bunch of source files (I did find a 1985 paper on the topic, but

    it's a little dense to answer my questions easily). My question: does

    that include code copying -- in other words, is it possible for a

    single stretch of code-text in the original GOTO program to be present

    in two places in the lambda-lifted code text?

     >  This actually allows rather more of a mess than even "normal" structured

    >  programming languages with GO TO allow.  Most languages don't permit you

    >  to GO TO into a construct from outside, though older versions allowed jumps

    >  out-then-back-in (Fortran 66) and/or in-and-then-back-out (simple Basics

    >  and others).  However, if you lambda-lift everything, you can actually

    >  jump around however you please.

     Well, if you're really using GOTOs optimally (or pessimally) you don't

    have ANY structures, so the language can't stop you.

    http://catb.org/jargon/html/story-of-mel.html

     >  > In short and to be formal, it seems to me that tagbodies don't form

    >  > properly nested trees, as functions must... I think they form digraphs.

    >  A plausible way to think about tail recursion is to assume an infinite

    >  return stack, and then postpone all the returns until the end of the

    >  program (when they do not actually have to be performed).  So although the

    >  call graph is a tree, the actually extant part of it is a random directed

    >  graph, and all the retracing is simply banished from consideration.

     Interesting. I have a very hard time picturing this.

    I suppose that's why GOTOs are considered harmful.

     >  > An interesting point. A recursive tail call in an applicative language

    >  > can do one thing that a simple GOTO cannot: it can, at one stroke,

    >  > change the value of all the parameters of the function to something

    >  > else. This would certainly be sufficient to make an applicative

    >  > theorist blanch...

    >  Absolutely.  LAMBDA = GOTO + argument passing; that's what makes it

    >  "ultimate".

     Now, interestingly, a concatenative tail-call cannot do this. Does

    this imply some superiority for concatenative optimizers? :-)

    -Wm

## John Nowak — 2008-03-03 20:15:26

    On Mar 3, 2008, at 2:48 PM, William Tanksley, Jr wrote:

     >> An interesting point. A recursive tail call in an applicative

    >> language

    >> can do one thing that a simple GOTO cannot: it can, at one stroke,

    >> change the value of all the parameters of the function to something

    >> else. This would certainly be sufficient to make an applicative

    >> theorist blanch...

    >>

    >> Absolutely.  LAMBDA = GOTO + argument passing; that's what makes it

    >> "ultimate".

    >

    > Now, interestingly, a concatenative tail-call cannot do this. Does

    > this imply some superiority for concatenative optimizers? :-)

     With a concatenative tail-call you're passing the stack as an

    argument. In other words, you pass the entire state of the program!

    - John

## John Cowan — 2008-03-03 20:21:39

    William Tanksley, Jr scripsit:

     > Now, interestingly, a concatenative tail-call cannot do this. Does

    > this imply some superiority for concatenative optimizers? :-)

     No.  All you do is do an arbitrary stack shuffle before the tail call.

    --

    John Cowan        http://www.ccil.org/~cowan          cowan@...

    Please leave your values                Check your assumptions.  In fact,

       at the front desk.                      check your assumptions at the door.

         --sign in Paris hotel                   --Cordelia Vorkosigan

## William Tanksley, Jr — 2008-03-03 20:50:38

    John Cowan <cowan@...> wrote:

     > William Tanksley, Jr scripsit:

    >  > Now, interestingly, a concatenative tail-call cannot do this. Does

    >  > this imply some superiority for concatenative optimizers? :-)

     I'll reply to both of your messages in one.

     >  No.  All you do is do an arbitrary stack shuffle before the tail call.

     Then the analysis difficulty (if there is any) is obviously in the

    shuffle, not in the tail-call. The analytical problem with an

    applicative tail-call is that the 'shuffle' happens at the same time

    as the call.

     > With a concatenative tail-call you're passing the stack as an

    > argument. In other words, you pass the entire state of the program!

     Yes, this is how concatenative languages are modeled. That's how

    *every* step in their execution is modeled, not just tail-calls or

    calls. If this were a problem, concatenative languages would be

    universally problematic, not merely problematic in the presence of

    tail-calls.

     >  John Cowan        http://www.ccil.org/~cowan          cowan@...

     -Wm

## John Cowan — 2008-03-03 23:15:28

    Joe Bowbeer scripsit:

     > But he mentions recursion favorably in the letter you were using to indict

    > it.  I'm confused.

     He says that humans are good at (mathematical) induction, which is one

    way of understanding recursion.  You can't expect him to express his

    whole philosophy of programming in a squib; look into _A Discipline of

    Programming_ for the details.

     > But so, in my opinion, can concatenative programming, so I have trouble

    > understanding your complaint.  If you are saying that adding recursion

    > to concatenative programming is beyond the pale, I think I could agree

    > with that.

     I was speaking without particular reference to concatenative programming

    (off-topic, I know).

    --

    John Cowan  <cowan@...>  http://ccil.org/~cowan

    Micropayment advocates mistakenly believe that efficient allocation of

    resources is the purpose of markets.  Efficiency is a byproduct of market

    systems, not their goal.  The reasons markets work are not because users

    have embraced efficiency but because markets are the best place to allow

    users to maximize their preferences, and very often their preferences are

    not for conservation of cheap resources.  --Clay Shirkey

## John Nowak — 2008-03-04 00:16:34

    On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:

     >> With a concatenative tail-call you're passing the stack as an

    >> argument. In other words, you pass the entire state of the program!

    >

    > Yes, this is how concatenative languages are modeled. That's how

    > *every* step in their execution is modeled, not just tail-calls or

    > calls. If this were a problem, concatenative languages would be

    > universally problematic, not merely problematic in the presence of

    > tail-calls.

     Indeed, and I'd argue that this is exactly why many people find stack-

    based languages universally problematic. They're taking issue with all

    of this state passing, although they phrase it like "I can't keep the

    stack in my head". Of course this isn't a problem in practice,

    particularly when you have type inference involved and can get a quick

    summary of what a function cares about, but it does seem to be the

    source of many negative first impressions.

    - John

## Don Groves — 2008-03-04 01:38:52

    On Mar 3, 2008, at 19:50 , William Tanksley, Jr wrote:

     > John Cowan <cowan@...> wrote:

    >> William Tanksley, Jr scripsit:

    >>> Now, interestingly, a concatenative tail-call cannot do this. Does

    >>> this imply some superiority for concatenative optimizers? :-)

    >

    > I'll reply to both of your messages in one.

    >

    >>  No.  All you do is do an arbitrary stack shuffle before the tail

    >> call.

    >

    > Then the analysis difficulty (if there is any) is obviously in the

    > shuffle, not in the tail-call. The analytical problem with an

    > applicative tail-call is that the 'shuffle' happens at the same time

    > as the call.

    >

    >> With a concatenative tail-call you're passing the stack as an

    >> argument. In other words, you pass the entire state of the program!

    >

    > Yes, this is how concatenative languages are modeled. That's how

    > *every* step in their execution is modeled, not just tail-calls or

    > calls. If this were a problem, concatenative languages would be

    > universally problematic, not merely problematic in the presence of

    > tail-calls.

     A few months back, I finally caught on to this: by their nature,

    concatenative languages enforce computation by continuation

    passing. Would it be true to say there is no other way?

    --

    don

     >

    >>  John Cowan        http://www.ccil.org/~cowan          cowan@...

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Don Groves — 2008-03-04 01:42:46

    On Mar 3, 2008, at 19:16 , John Nowak wrote:

     >

    > On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:

    >

    >>> With a concatenative tail-call you're passing the stack as an

    >>> argument. In other words, you pass the entire state of the program!

    >>

    >> Yes, this is how concatenative languages are modeled. That's how

    >> *every* step in their execution is modeled, not just tail-calls or

    >> calls. If this were a problem, concatenative languages would be

    >> universally problematic, not merely problematic in the presence of

    >> tail-calls.

    >

    > Indeed, and I'd argue that this is exactly why many people find stack-

    > based languages universally problematic. They're taking issue with all

    > of this state passing, although they phrase it like "I can't keep the

    > stack in my head". Of course this isn't a problem in practice,

    > particularly when you have type inference involved and can get a quick

    > summary of what a function cares about, but it does seem to be the

    > source of many negative first impressions.

     Also, there has never been a requirement to "keep it all in one's head,"

    that's what comments are for. Commenting with stack diagrams is very

    useful!

    I know "real programmers" don't comment but in these languages, they

    should.

    --

    don

     > - John

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## zallambo — 2008-03-04 05:42:48

    --- In concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:

     >

    >

    > On Mar 3, 2008, at 19:16 , John Nowak wrote:

    >

    > >

    > > On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:

    > >

    > >>> With a concatenative tail-call you're passing the stack as an

    > >>> argument. In other words, you pass the entire state of the program!

    > >>

    > >> Yes, this is how concatenative languages are modeled. That's how

    > >> *every* step in their execution is modeled, not just tail-calls or

    > >> calls. If this were a problem, concatenative languages would be

    > >> universally problematic, not merely problematic in the presence of

    > >> tail-calls.

    > >

    > > Indeed, and I'd argue that this is exactly why many people find stack-

    > > based languages universally problematic. They're taking issue with all

    > > of this state passing, although they phrase it like "I can't keep the

    > > stack in my head". Of course this isn't a problem in practice,

    > > particularly when you have type inference involved and can get a quick

    > > summary of what a function cares about, but it does seem to be the

    > > source of many negative first impressions.

    >

    > Also, there has never been a requirement to "keep it all in one's head,"

    > that's what comments are for. Commenting with stack diagrams is very

    > useful!

    >

    > I know "real programmers" don't comment but in these languages, they

    > should.

    > --

    > don

     If code isn't readable without stack diagrams, comments seem like a

    poor fix. Rather, there should be a way to make the code itself more

    transparent. I think lambda expressions are a good replacement for

    stack diagrams. They make the stack explicit and are often easier to

    read. Compare:

    #x y u v -- (x*u - y*v) (x*v + y*u)

    dup4 [swap] dip * bury * swap - bury * bury * +

    [x y u v] [x u * y v * - x v * y u * +] lambda

    A mistake would be much easier to notice in the latter than the

    former. Not being able to keep track of the stack in one's head can be

    a serious problem.

    Fortunately lambda expressions can be implemented as macros and

    rewritten out of existence. So the language itself doesn't actually

    need to be extended.

    -Justin

## Christopher Diggins — 2008-03-04 06:06:57

    On Tue, Mar 4, 2008 at 12:42 AM, zallambo <zallambo@...> wrote:

     > --- In concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:

    > >

    > >

    > > On Mar 3, 2008, at 19:16 , John Nowak wrote:

    > >

    > > >

    > > > On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:

    > > >

    > > >>> With a concatenative tail-call you're passing the stack as an

    > > >>> argument. In other words, you pass the entire state of the program!

    > > >>

    > > >> Yes, this is how concatenative languages are modeled. That's how

    > > >> *every* step in their execution is modeled, not just tail-calls or

    > > >> calls. If this were a problem, concatenative languages would be

    > > >> universally problematic, not merely problematic in the presence of

    > > >> tail-calls.

    > > >

    > > > Indeed, and I'd argue that this is exactly why many people find stack-

    > > > based languages universally problematic. They're taking issue with all

    > > > of this state passing, although they phrase it like "I can't keep the

    > > > stack in my head". Of course this isn't a problem in practice,

    > > > particularly when you have type inference involved and can get a quick

    > > > summary of what a function cares about, but it does seem to be the

    > > > source of many negative first impressions.

    > >

    > > Also, there has never been a requirement to "keep it all in one's head,"

    > > that's what comments are for. Commenting with stack diagrams is very

    > > useful!

    > >

    > > I know "real programmers" don't comment but in these languages, they

    > > should.

    > > --

    > > don

    >

    > If code isn't readable without stack diagrams, comments seem like a

    > poor fix. Rather, there should be a way to make the code itself more

    > transparent. I think lambda expressions are a good replacement for

    > stack diagrams. They make the stack explicit and are often easier to

    > read. Compare:

    >

    > #x y u v -- (x*u - y*v) (x*v + y*u)

    > dup4 [swap] dip * bury * swap - bury * bury * +

    >

    > [x y u v] [x u * y v * - x v * y u * +] lambda

     <shamelessplug>

    Cat supports this notation as: \x.\y.\u.\v.[x u * y v * - x v * y u * +]

    </shamelessplug>

## Don Groves — 2008-03-05 04:16:39

    On Mar 3, 2008, at 19:06 , Christopher Diggins wrote:

     > On Tue, Mar 4, 2008 at 12:42 AM, zallambo <zallambo@...> wrote:

    >> --- In concatenative@yahoogroups.com, Don Groves <dgroves@...> wrote:

    >>>

    >>>

    >>> On Mar 3, 2008, at 19:16 , John Nowak wrote:

    >>>

    >>>>

    >>>> On Mar 3, 2008, at 3:50 PM, William Tanksley, Jr wrote:

    >>>>

    >>>>>> With a concatenative tail-call you're passing the stack as an

    >>>>>> argument. In other words, you pass the entire state of the

    >>>>>> program!

    >>>>>

    >>>>> Yes, this is how concatenative languages are modeled. That's how

    >>>>> *every* step in their execution is modeled, not just tail-calls or

    >>>>> calls. If this were a problem, concatenative languages would be

    >>>>> universally problematic, not merely problematic in the presence of

    >>>>> tail-calls.

    >>>>

    >>>> Indeed, and I'd argue that this is exactly why many people find

    >>>> stack-

    >>>> based languages universally problematic. They're taking issue

    >>>> with all

    >>>> of this state passing, although they phrase it like "I can't

    >>>> keep the

    >>>> stack in my head". Of course this isn't a problem in practice,

    >>>> particularly when you have type inference involved and can get a

    >>>> quick

    >>>> summary of what a function cares about, but it does seem to be the

    >>>> source of many negative first impressions.

    >>>

    >>> Also, there has never been a requirement to "keep it all in one's

    >>> head,"

    >>> that's what comments are for. Commenting with stack diagrams is very

    >>> useful!

    >>>

    >>> I know "real programmers" don't comment but in these languages, they

    >>> should.

    >>> --

    >>> don

    >>

    >> If code isn't readable without stack diagrams, comments seem like a

    >> poor fix. Rather, there should be a way to make the code itself more

    >> transparent. I think lambda expressions are a good replacement for

    >> stack diagrams. They make the stack explicit and are often easier to

    >> read. Compare:

    >>

    >> #x y u v -- (x*u - y*v) (x*v + y*u)

    >> dup4 [swap] dip * bury * swap - bury * bury * +

    >>

    >> [x y u v] [x u * y v * - x v * y u * +] lambda

    >

    > <shamelessplug>

    >

    > Cat supports this notation as: \x.\y.\u.\v.[x u * y v * - x v * y u

    > * +]

    >

    > </shamelessplug>

     Naming stack locations is a nice way to reduce the cognitive load

    and it looks like it works particularly well for mathematical

    algorithms.

    How well does it work for non-mathematical things?

    --

    don

     > Yahoo! Groups Links

    >

    >

    >

    >

## John Cowan — 2008-03-05 04:25:13

    William Tanksley scripsit:

     > I don't know the term "lambda-lift", and Google knows of it mainly as

    > a bunch of source files (I did find a 1985 paper on the topic, but

    > it's a little dense to answer my questions easily). My question: does

    > that include code copying -- in other words, is it possible for a

    > single stretch of code-text in the original GOTO program to be present

    > in two places in the lambda-lifted code text?

     No, it doesn't.  Lambda-lifting is a transformation of an inner (nested)

    procedure into a top-level procedure by adding one argument for each

    variable that is free in the inner procedure but bound in some enclosing

    procedure.  All calls are transformed likewise.

    For example:

    	(lambda (x y) ... (lambda (z w) ... x ...) ...)

    lambda-lifts to:

    	(lambda (z-of-x w x) ... x ...)

    	(lambda (x y) ... (z-of-x w x) ...)

    so z is renamed to z-of-x (or in some other way) and goes from one

    argument to two.

    This will not work, or at least requires extra machinery, when z is

    passed out of x to be called from somewhere else.  But that is not the

    case for lambdas made out of tagbody labels.

    --

    John Cowan    cowan@...    http://ccil.org/~cowan

            Sound change operates regularly to produce irregularities;

            analogy operates irregularly to produce regularities.

                    --E.H. Sturtevant, ca. 1945, probably at Yale

## Daniel Ehrenberg — 2008-03-05 04:33:12

    >  Naming stack locations is a nice way to reduce the cognitive load

    >  and it looks like it works particularly well for mathematical

    >  algorithms.

    >  How well does it work for non-mathematical things?

    >  --

    >  don

     I've used it for a dynamic programming problem, which made things much

    easier. But generally, I find that things come out cleaner when you

    don't use named variables. The dataflow is more direct. When you write

    things by dividing them into small words, the need for named variables

    is diminished; the ability to omit variable names also makes it easier

    to divide things into smaller chunks.

    Dan

## John Nowak — 2008-03-05 09:25:58

    On Mar 3, 2008, at 8:38 PM, Don Groves wrote:

     > A few months back, I finally caught on to this: by their nature,

    > concatenative languages enforce computation by continuation

    > passing.

     Indeed. This in *incredibly* useful as it means your language is

    essentially purely functional by default. After all, it's trivial to

    thread a world state through the entire program on the top of the

    stack. All you need then is a simple effect system to allow enforcing

    of purity (purity = does not read/write the world value) via the type

    system when desirable/necessary. The monoidal nature of Joy-like

    languages also enables linearity without linear/uniquneness types. Cat

    takes advantage of this, although perhaps not originally knowingly.

    Fifth does as well.

    - John

## William Tanksley, Jr — 2008-03-06 15:23:25

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  >> With a concatenative tail-call you're passing the stack as an

    >  >> argument. In other words, you pass the entire state of the program!

    >  > Yes, this is how concatenative languages are modeled. That's how

    >  > *every* step in their execution is modeled, not just tail-calls or

    >  > calls. If this were a problem, concatenative languages would be

    >  > universally problematic, not merely problematic in the presence of

    >  > tail-calls.

    >  Indeed, and I'd argue that this is exactly why many people find stack-

    >  based languages universally problematic. They're taking issue with all

    >  of this state passing, although they phrase it like "I can't keep the

    >  stack in my head". Of course this isn't a problem in practice,

    >  particularly when you have type inference involved and can get a quick

    >  summary of what a function cares about, but it does seem to be the

    >  source of many negative first impressions.

     Now we're treading on the marshy ground of subjective judgments... I

    don't think we're going to resolve this in this manner. I disagree

    that this is why some people find concatenative languages difficult,

    but I suspect neither one of us can build a model strong enough to

    refute the other's suspicions.

    But I wasn't talking about subjective impressions; I'm talking about

    mathematical analysis. We don't need to go into opinions.

    Mathematically, every operation in a concatenative language is modeled

    by passing the entire stack to each successive function, and yet the

    mathematical analysis is exceedingly simple.

    Therefore, if tail-calls are hard to analyze in a concatenative

    language, the problem is NOT that "the entire stack is being passed".

    The problem lies elsewhere.

    Let me quote you: "No.  All you do is do an arbitrary stack shuffle

    before the tail call."

    Again, the problem is the stack shuffle, not the tail call. Analysing

    the shuffle will untangle the entire problem, without having to

    involve any analysis of the tail-call. This contrasts with a tail-call

    in an applicative language, in which the tail-call is inseparable from

    the changing of the values of the parameters.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-06 16:53:43

    zallambo <zallambo@...> wrote:

     >  If code isn't readable without stack diagrams, comments seem like a

    >  poor fix.

     Indeed. But this isn't relevant to the discussion. Code is unreadable

    for many reasons. We were originally talking about a specific cause of

    unreadability which appears to apply exclusively to applicative

    languages -- now people have started complaining that concatenative

    languages are universally unreadable, which is not backed up by the

    arguments being presented.

     > Rather, there should be a way to make the code itself more

    >  transparent. I think lambda expressions are a good replacement for

    >  stack diagrams. They make the stack explicit and are often easier to

    >  read. Compare:

     Lambda expressions are an excellent tool, but they do not replace or

    augment stack diagrams; the purposes are simply different.

     >  #x y u v -- (x*u - y*v) (x*v + y*u)

    >  dup4 [swap] dip * bury * swap - bury * bury * +

    >  [x y u v] [x u * y v * - x v * y u * +] lambda

    >  A mistake would be much easier to notice in the latter than the

    >  former.

     A mistake in either one is a programming error, which can be

    arbitrarily hard to find. In this particular case, lambda is

    objectively better than raw stack notation, and a mathematical

    domain-specific-language would be even better (one should use the

    simplest thing that will work, of course); but in general, errors in

    lambdas are as hard to find as errors in stack notation; they can be

    worse in some situations because in a stack language, lambda

    expressions mix up and permit confusion between the two ways of

    getting parameters to the functions.

    Again, lambdas are useful, but in my experience they're mainly used

    where a math-like expression is desired -- in other words, it would be

    even more useful for the language to provide a math DSL.

     > Not being able to keep track of the stack in one's head can be

    > a serious problem.

     Indeed. Guess what my answer is to that problem?

    1. Learn better to keep track of the stack in your head;

    2. Write code that's easier to track.

    Both will only come with practice.

     >  -Justin

     -Wm

## John Nowak — 2008-03-06 20:11:44

    On Mar 6, 2008, at 10:23 AM, William Tanksley, Jr wrote:

     > John Nowak <john@...> wrote:

    >

    >> Indeed, and I'd argue that this is exactly why many people find

    >> stack-

    >> based languages universally problematic. They're taking issue with

    >> all

    >> of this state passing, although they phrase it like "I can't keep the

    >> stack in my head". Of course this isn't a problem in practice,

    >> particularly when you have type inference involved and can get a

    >> quick

    >> summary of what a function cares about, but it does seem to be the

    >> source of many negative first impressions.

    >

    > Now we're treading on the marshy ground of subjective judgments... I

    > don't think we're going to resolve this in this manner.

     Resolve what? Are you talking to the right John?

     > But I wasn't talking about subjective impressions; I'm talking about

    > mathematical analysis. We don't need to go into opinions.

    > Mathematically, every operation in a concatenative language is modeled

    > by passing the entire stack to each successive function, and yet the

    > mathematical analysis is exceedingly simple.

     I agree.

     > Therefore, if tail-calls are hard to analyze in a concatenative

    > language, the problem is NOT that "the entire stack is being passed".

    > The problem lies elsewhere.

     Of course.

     > Let me quote you: "No.  All you do is do an arbitrary stack shuffle

    > before the tail call."

     Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.

    - John

## John Cowan — 2008-03-06 20:17:26

    John Nowak scripsit:

     > Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.

     I think our William has a collision in his internal hash tables.

    He's responding to your message and taking you to task for contradicting

    something I said.  Or something like that.

    --

    You know, you haven't stopped talking           John Cowan

    since I came here. You must have been           http://www.ccil.org/~cowan

    vaccinated with a phonograph needle.            cowan@...

            --Rufus T. Firefly

## William Tanksley, Jr — 2008-03-06 22:20:41

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  > John Nowak <john@...> wrote:

    > >> Indeed, and I'd argue that this is exactly why many people find

    >  >> stack-

    >  >> based languages universally problematic. They're taking issue with

    >  >> all

    >  >> of this state passing, although they phrase it like "I can't keep the

    >  >> stack in my head". Of course this isn't a problem in practice,

    >  >> particularly when you have type inference involved and can get a

    >  >> quick

    >  >> summary of what a function cares about, but it does seem to be the

    >  >> source of many negative first impressions.

    >  > Now we're treading on the marshy ground of subjective judgments... I

    >  > don't think we're going to resolve this in this manner.

    >  Resolve what? Are you talking to the right John?

     I'm responding to your message, so I guess so -- I meant that I

    disagree that this is the cause of people's discomfort, and also that

    I disagreed that it was related to any trouble with tail-calls or

    recursion.

    However, after a good 5 minutes of digging, I found the source of our

    confusion. I DID mix up my mind when referring to you two back when

    you (Nowak) said that the entire state is passed through the

    tail-call, and he (Cowan) said "No.  All you do is do an arbitrary

    stack shuffle before the tail call."

    I agree with the facts of what you said, Nowak (although I don't agree

    that this makes concatenative languages "the ultimate GOTO", which

    seems to be the implication of what you wrote), and I disagree with

    you, Cowan, that performing an arbitrary stack shuffle complicates the

    analysis of the tail-call.

     >  > Let me quote you: "No.  All you do is do an arbitrary stack shuffle

    >  > before the tail call."

    >  Ah, now I'm sure you have the wrong John. I'm Mr. Nowak, he's Mr. Cowan.

     Ah! Man, that WAS confusing. Sorry about that -- my fault.

     >  - John

     -Wm

## John Cowan — 2008-03-07 06:55:56

    William Tanksley, Jr scripsit:

     > I agree with the facts of what you said, Nowak (although I don't agree

    > that this makes concatenative languages "the ultimate GOTO", which

    > seems to be the implication of what you wrote), and I disagree with

    > you, Cowan, that performing an arbitrary stack shuffle complicates the

    > analysis of the tail-call.

     Good, because that's the reverse of what I said, which is that to tail-call

    an arbitrary function, all you need to do is to execute an arbitrary shuffle

    to get the function arguments in the right order -- which is very simple.

    --

    Do I contradict myself?                         John Cowan

    Very well then, I contradict myself.            cowan@...

    I am large, I contain multitudes.               http://www.ccil.org/~cowan

            --Walt Whitman, Leaves of Grass

## William Tanksley, Jr — 2008-03-07 15:00:51

    John Cowan <cowan@...> wrote:

     > William Tanksley, Jr scripsit:

    >  > I agree with the facts of what you said, Nowak (although I don't agree

    >  > that this makes concatenative languages "the ultimate GOTO", which

    >  > seems to be the implication of what you wrote), and I disagree with

    >  > you, Cowan, that performing an arbitrary stack shuffle complicates the

    >  > analysis of the tail-call.

    >  Good, because that's the reverse of what I said, which is that to tail-call

    >  an arbitrary function, all you need to do is to execute an arbitrary shuffle

    >  to get the function arguments in the right order -- which is very simple.

     Seriously, I'm confused. Why did you start your paragraph with "no,"

    if you weren't intending to disagree with me? This probably all comes

    down to miscommunication again...

     >  Do I contradict myself?                         John Cowan

     Probably not.

    -Wm

## John Cowan — 2008-03-07 16:03:52

    William Tanksley, Jr scripsit:

     > Seriously, I'm confused. Why did you start your paragraph with "no,"

    > if you weren't intending to disagree with me? This probably all comes

    > down to miscommunication again...

     I can no longer fully sort this out, but your remark ended with a smiley,

    so I assumed it was ironic, and was answering (seriously) that the ironic

    statement was wrong, meaning that what I took to be your underlying actual

    opinion was correct.

    In any case, a tail-call in a concatenative language is a possible stack

    reshuffle to get the arguments in the correct order for the new function

    and then a GO TO to that function, which is essentially how it's implemented

    in tail-recursive applicative languages like Scheme: you shuffle the arguments

    about in registers, possibly spilling to the stack or restoring from the stack

    as needed, and then do a machine-language GO TO.

    Assembler: the ultimate concatenative language....

    --

    After fixing the Y2K bug in an application:     John Cowan

            WELCOME TO <censored>                   cowan@...

            DATE: MONDAK, JANUARK 1, 1900           http://www.ccil.org/~cowan

## William Tanksley, Jr — 2008-03-07 16:42:13

    John Cowan <cowan@...> wrote:

     > William Tanksley, Jr scripsit:

    >  > Seriously, I'm confused. Why did you start your paragraph with "no,"

    >  > if you weren't intending to disagree with me? This probably all comes

    >  > down to miscommunication again...

    >  I can no longer fully sort this out, but your remark ended with a smiley,

    >  so I assumed it was ironic, and was answering (seriously) that the ironic

    >  statement was wrong, meaning that what I took to be your underlying actual

    >  opinion was correct.

     I consider this fully sorted out. Excellent. The problem is that I

    failed to explain precisely why I said what I did, leaving you having

    to wonder whether I was being deep and ironic or just shallow and

    obvious. Your reading makes perfect sense.

     >  In any case, a tail-call in a concatenative language is a possible stack

    >  reshuffle to get the arguments in the correct order for the new function

    >  and then a GO TO to that function, which is essentially how it's implemented

    >  in tail-recursive applicative languages like Scheme: you shuffle the arguments

    >  about in registers, possibly spilling to the stack or restoring from the stack

    >  as needed, and then do a machine-language GO TO.

    >  Assembler: the ultimate concatenative language....

     This isn't a useful way to compare languages -- yes, they can all

    generate machine code, and given a hypothetical optimizer it'll be the

    same for the same semantics. Well, it'll be useful if you can specify

    what that optimizer looks like.

    A tail call in a concatenative language is a structured GOTO to the

    beginning of the function, nothing more. A tail call in an applicative

    function is a parameter reassignment combined with a structured GOTO

    to the beginning of the function.

     >  After fixing the Y2K bug in an application:     John Cowan

     -Wm

## John Cowan — 2008-03-07 19:19:16

    William Tanksley, Jr scripsit:

     > A tail call in a concatenative language is a structured GOTO to the

    > beginning of the function, nothing more. A tail call in an applicative

    > function is a parameter reassignment combined with a structured GOTO

    > to the beginning of the function.

     Correct, given that a shuffle may be needed before the concatenative

    function can be successfully called (tail or otherwise), and a compiler

    can arrange that the parameter reassignment requires no actual machine

    instructions.

    --

    At the end of the Metatarsal Age, the dinosaurs     John Cowan

    abruptly vanished. The theory that a single         cowan@...

    catastrophic event may have been responsible        http://www.ccil.org/~cowan

    has been strengthened by the recent discovery of

    a worldwide layer of whipped cream marking the

    Creosote-Tutelary boundary.             --Science Made Stupid

## Manfred Von Thun — 2008-03-11 05:11:45

    On 29/2/08 7:39 AM, "John Nowak" <john@...> wrote:

     >

    > Recently, I mentioned that if you disallow recursive definitions, then

    > definitions can be thought of as macros or rewrite rules.

    >

     This encourages me to ask a question about Forth which I have been

    too shy to ask. I¹ve read a number of times that recursion was not

    allowed or not easy to do at least in the earlier versions of

    Forth. I explained this to myself like this: the colon definitions are

    just macros, and the macro expansion is very simple.

    Was I right about the early Forths? Was is the current situation?

    I was very impressed by the current discussion in this topic.

      - Manfred

     >

     [Non-text portions of this message have been removed]

## Manfred Von Thun — 2008-03-11 05:41:30

    On 2/3/08 12:51 AM, "Stevan Apter" <sa@...> wrote:

     >

    > i'm still puzzled why authors of concatenative languages like cat and factor

            have resisted the incorporation of array primitives into their

    languages.

    But why do they need to be primitives? Many languages have a small core

    and a large library of defined functions. One such library might be for a

    collection of basic array functions in terms of which all other array

    functions

    can be defined. Then the library might be expanded by also giving the

    definitions of the most useful ones.

    There might be many different possible collections of basic ones, that seems

    to be true for most abstract algebras. Probably the ones offered by the

    existing array languages are both complete as a base and most useful.

    Are there any which cannot be defined in Joy (with lists instead of arrays)?

    If so, please let me know.

      - Manfred

    [Non-text portions of this message have been removed]

## Manfred Von Thun — 2008-03-11 05:58:49

    On 2/3/08 1:46 AM, "Stevan Apter" <sa@...> wrote:

     >

    > perhaps this is a special case of a wider problem, viz. imprecision about

    > the terms "array", "list", &c.  i use these terms interchangeably, whereas

    > others may not.

    >

     I now use ³sequence² when taking about an abstract data type, and similarly

    for

    ³set² as an abstract data type and (ordered) ³pair² as an abstract data

    type.

    It is well known that the three can be interdefined.

    I use ³list² and ³array² as the most commonly used implementations of

    sequences: lists as linked structures, arrays in consecutive memory.

    Lists are better for some operations on sequences, and arrays are better

    for other operations on sequences. But all operations on sequences

    implemented either way.

      - Manfred

     >

    >

     [Non-text portions of this message have been removed]

## Manfred Von Thun — 2008-03-11 06:54:17

    On 4/3/08 6:48 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     >

     [ apropos a discussion about tail recursion]

     >

    > Now, interestingly, a concatenative tail-call cannot do this. Does

    > this imply some superiority for concatenative optimizers? :-)

    >

    > -Wm

     The Joy interpreter (in file interp.c function exeterm() ) does tail

    recursion,

    and it is easy. This function is the core of the interpreter, it interprets

    the contents of quotations. If any defined function calls itself at the end

    of its body, then exeterm tail-recurses to the beginning of the body.

    This is possible and particularly easy because diefined functions, like

    any functions, do not have explicit parameters but take them off the stack.

     - Manfred

    [Non-text portions of this message have been removed]

## Manfred Von Thun — 2008-03-11 07:19:18

    On 4/3/08 12:38 PM, "Don Groves" <dgroves@...> wrote:

     >

    > A few months back, I finally caught on to this: by their nature,

    > concatenative languages enforce computation by continuation

    > passing. Would it be true to say there is no other way?

    > --

    > don

    >

     But continuation passing surely means something rather complex.

    Cancatenative languages interpret concatenations of atomic

    programs by starting at the beginning until they reach the

    end. For each atom something is changed. That is pretty much

    the same for all assembly languages, byte code interpreters etc.

    (True at least while not intercepted by a jump or goto).

    But as remember, continuation passing means giving

    a procedure an additional parameter which represents the

    rest of the program, and which will normally be executed

    before the procedure returns. Landin¹s papers from the 60¹s

    (and at least one much later) are good on this. Look for

    ³History of continuations² or similar.

      - Manfred

    [Non-text portions of this message have been removed]

## pml060912 — 2008-03-11 09:35:03

    --- In concatenative@yahoogroups.com, Manfred Von Thun <m.vonthun@...>

    wrote:

     >

    >

    >

    >

    > On 29/2/08 7:39 AM, "John Nowak" <john@...> wrote:

    >

    > >

    > > Recently, I mentioned that if you disallow recursive definitions, then

    > > definitions can be thought of as macros or rewrite rules.

    > >

    > This encourages me to ask a question about Forth which I have been

    > too shy to ask. I¹ve read a number of times that recursion was not

    > allowed or not easy to do at least in the earlier versions of

    > Forth. I explained this to myself like this: the colon definitions are

    > just macros, and the macro expansion is very simple.

    >

    > Was I right about the early Forths? Was is the current situation?

     Chuck Moore did use macros in some of his early experiments, I

    believe, but by the time there were enough features for it to be

    recognisably Forth he had already settled on compiling into indirect

    threaded code. Other implementation methods followed, and that one is

    now rare. Google for "history of Forth", which I think is at Forth

    inc.'s site.

    The problem with recursion was how the compiler was implemented, but

    it was usually quite minor. The compiler couldn't recognise a word

    that was still being compiled, as it hadn't yet been marked in the

    vocabulary as a successfully compiled word. You had to achieve

    recursion with a special keyword where you would have put the

    recursive call, sometimes called MYSELF and sometimes RECURSE, but it

    wasn't particularly difficult; you could even provide it yourself if

    it wasn't already there. Where things got a little more awkward was

    with mutual recursion, which required some set up work with vectors

    that you used in the main words where you would have had them calling

    each other. You had to reassign those to the right places after

    compiling the main words, and calling them usually imposed some more

    overhead. PML.

## Stan Katz — 2008-03-11 13:21:15

    Manfred von Thun wrote :

     > This encourages me to ask a question about Forth which I have been

    > too shy to ask. I¹ve read a number of times that recursion was not

    > allowed or not easy to do at least in the earlier versions of

    > Forth. I explained this to myself like this: the colon definitions are

    > just macros, and the macro expansion is very simple.

    >

    > Was I right about the early Forths? Was is the current situation?

       Recursion has always been available in Forth, but it needed some care because

      most implementations "hide" the current definition until it is complete. This was

      done so that it was possible to re-define a word and use the old definition within

      the new word, e.g. to add additional processing or checking to the operation, and

      possibly also to prevent a word that was not completely defined (or had an error

      while it was defined) from being used.

      Many Forths included the word RECURSE or MYSELF for recusrion and those that

      didn't have it as a standard word usually had it as an extension.

      There has actually been a discussion recently on the comp.lang.forth usenet

      newsgroup about this hiding of the current definition.

      Stan Katz

    ---------------------------------

    Looking for last minute shopping deals?  Find them fast with Yahoo! Search.

    [Non-text portions of this message have been removed]

## John Cowan — 2008-03-11 15:24:41

    Manfred Von Thun scripsit:

     > If any defined function calls itself at the end

    > of its body, then exeterm tail-recurses to the beginning of the body.

     Ideally this should happen if the last word is *any* non-primitive function,

    which is why the optimization is rightly called "tail-call" (Scheme) or

    "last call" (Prolog).

    --

    John Cowan    http://www.ccil.org/~cowan   <cowan@...>

        "Any legal document draws most of its meaning from context.  A telegram

        that says 'SELL HUNDRED THOUSAND SHARES IBM SHORT' (only 190 bits in

        5-bit Baudot code plus appropriate headers) is as good a legal document

        as any, even sans digital signature." --me

## William Tanksley, Jr — 2008-03-11 16:19:48

    Manfred Von Thun <m.vonthun@...> wrote:

     >  But as remember, continuation passing means giving

    >  a procedure an additional parameter which represents the

    >  rest of the program, and which will normally be executed

    >  before the procedure returns. Landin¹s papers from the 60¹s

    >  (and at least one much later) are good on this. Look for

    >  ³History of continuations² or similar.

     Joy doesn't have any functionality which is like this. Forth does,

    with its direct access to its return stack.

     >   - Manfred

     -Wm

## John Cowan — 2008-03-11 19:44:29

    William Tanksley, Jr scripsit:

     > Joy doesn't have any functionality which is like this. Forth does,

    > with its direct access to its return stack.

     In fact Joy does have a word "cont" which provides access to the implicit

    return stack.  It's been busted for a long time, though.

    --

                    Si hoc legere scis, nimium eruditionis habes.

## Don Groves — 2008-03-11 22:43:13

    On Mar 11, 2008, at 19:19 , Manfred Von Thun wrote:

     > On 4/3/08 12:38 PM, "Don Groves" <dgroves@...> wrote:

    >>

    >> A few months back, I finally caught on to this: by their nature,

    >> concatenative languages enforce computation by continuation

    >> passing. Would it be true to say there is no other way?

    >> --

    >> don

    >>

    > But continuation passing surely means something rather complex.

    > Cancatenative languages interpret concatenations of atomic

    > programs by starting at the beginning until they reach the

    > end. For each atom something is changed. That is pretty much

    > the same for all assembly languages, byte code interpreters etc.

    > (True at least while not intercepted by a jump or goto).

    >

    > But as remember, continuation passing means giving

    > a procedure an additional parameter which represents the

    > rest of the program, and which will normally be executed

    > before the procedure returns. Landin’s papers from the 60’s

    > (and at least one much later) are good on this. Look for

    > “History of continuations” or similar.

    >

    >   - Manfred

     Hello, Manfred --

    Your description above is the usual implementation of

    continuation passing but concatenative languages seem

    to me to embody that implementation implicitly. A simple

    Joy example:

    3 [dup *] i ==> 3 3 [*] i ==> 9

    I interpret this as 3 3 [*] is the continuation of the dup

    operation being passed to i which is executed before i

    returns.

    --

    don

     > [Non-text portions of this message have been removed]

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Manfred Von Thun — 2008-03-19 07:51:47

    On 12/3/08 3:19 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>

    > > wrote:

    >

    >> >  But as remember, continuation passing means giving

    >> >  a procedure an additional parameter which represents the

    >> >  rest of the program, and which will normally be executed

    >> >  before the procedure returns. Landin¹s papers from the 60¹s

    >> >  (and at least one much later) are good on this. Look for

    >> >  ³History of continuations² or similar.

    >

    > Joy doesn't have any functionality which is like this. Forth does,

    > with its direct access to its return stack.

    >

     Not so. In Joy all parameters are taken from the stack. Combinators

    expect quotations, and quotations are also good as continuation

    parameters. I have used it a number of times to implement

    backtracking (in the only way I know: with continuations.) There

    is one file in the Joy library

    http://www.latrobe.edu.au/philosophy/phimvt/joy/plglib.joy

     >

     which does what are variously called truth trees, semantic tableaux

    or Wang¹s algorithm. Most of the programs in that file are annotated

    as expecting

    t  f  c  F

    on the stack, with F on top. F is a formula in propositional logic which

    the tree method tries to make true (or false)  by assigning truth to some

    atoms (in t) and falsity to others (in f). The c parameter is the

    continuation,

    and it does all the hard work of the backtracking.

    So, because Joy has quotations, no extra mechanism is needed to

    implement continuations.

     >

     John Cowan was right about the abandoned cont operator. It turned

    out that quotations can do the job. However it may also be that a

    different cont operator might make backtracking programs easier

    to read.

     >

     Incidentally, the mainstream languages which allow procedures as

    continuations will also allow several continuations. That is true in

    Joy too. I seem to remember that the implementation of Snobol

    (and maybe of Icon) used two continuations: one for success,

    the other for failure.

      - Manfred

    [Non-text portions of this message have been removed]

## Manfred Von Thun — 2008-03-19 09:30:31

    On 8/3/08 3:03 AM, "John Cowan" <cowan@...> wrote:

     >

    > ....

    > Assembler: the ultimate concatenative language....

     Indeed, except for those jumps, as of course you know. But the

    mention of assembler triggers an old memory about something

    I have wanted to write about for some time. It concerns not

    so much the high or low level of a concatenative language,

    but what its shortest programs are whose concatenation

    computes the composition of what those shortest programs

    are. In just about all concatenative languages the shortest

    programs are atoms like swap, +, map, 123, ³hello², [a b],

    the first three operators and the lest three push-ops. It is

    from atoms such as these that programs are constructed by

    concatenation. But could there not be small programs, not

    formed by concatenating with others to form their composition,

    which nevertheless have parts: MOLECULES

    An assembly program consists of a sequence of lines, each

    holding one instruction, to be executed in sequence unless

    intercepted by a jump instruction. Each instruction produces

    a change somewhere, and the concatenation of the lines

    produces the composition of the changes. But instructions

    have part, too. They consist of an operator such as mul, fetch,

    store, ..., each followed by several inscrutables having to

    do with where things come from and where they should go.

    So an instruction is a sort of molecule composed of several

    atoms. Now think of concatenative languages in which programs

    are concatenated from molecules, each consisting of an

    operator (like swap, + etc) together with additional parts

    that complete what is meant. Note that the additional parts

    are not further parameters that should be taken from the stack.

    What useful additional parts may there be?

    I would take a hint from unix, which has a rich collection of

    what are called filters, programs that take one input fil and

    produce one output file. The names of such programs, foo, bar,

    baz and zot, can be concatenated to form what is called a pipe:

    (here i dare not think what my mailer will do with the vertical bar)

    foo | bar | baz | zot

    and this concatenation will take one input file and produce one

    output file such that ... You guessed it. But each of these programs

    may have a useful default behaviour and also allow switches to

    modify the default. The switches are typically single letters

    precededd by a minus sign. So the pipe might actually look like

    this:

    foo a g | bar x | baz -e q w e r | zot m d

    So in the terminology I am tempted to adopt, here we have

    the concatenation of four molecules or instructions,

    where the first instruction consists of  three atoms, namely

    a program and two switches.

    Apart from the pipe of output-input files, it may be necessary

    to use other files, and there are lots of ways of doing that.

    The upshot: have we in the concatenative world missed out

    on something useful by not allowing parts to the smallest

    programs. There is a lot one could and should discuss here,

    but not me, not tonight.

      - Manfred

    [Non-text portions of this message have been removed]

## Don Groves — 2008-03-19 19:42:29

    On Mar 19, 2008, at 19:30 , Manfred Von Thun wrote:

     >

    > On 8/3/08 3:03 AM, "John Cowan" <cowan@...> wrote:

    >>

    >> ....

    >> Assembler: the ultimate concatenative language....

    >

    > Indeed, except for those jumps, as of course you know. But the

    > mention of assembler triggers an old memory about something

    > I have wanted to write about for some time. It concerns not

    > so much the high or low level of a concatenative language,

    > but what its shortest programs are whose concatenation

    > computes the composition of what those shortest programs

    > are. In just about all concatenative languages the shortest

    > programs are atoms like swap, +, map, 123, “hello”, [a b],

    > the first three operators and the lest three push-ops. It is

    > from atoms such as these that programs are constructed by

    > concatenation. But could there not be small programs, not

    > formed by concatenating with others to form their composition,

    > which nevertheless have parts: MOLECULES

    >

    > An assembly program consists of a sequence of lines, each

    > holding one instruction, to be executed in sequence unless

    > intercepted by a jump instruction. Each instruction produces

    > a change somewhere, and the concatenation of the lines

    > produces the composition of the changes. But instructions

    > have part, too. They consist of an operator such as mul, fetch,

    > store, ..., each followed by several inscrutables having to

    > do with where things come from and where they should go.

    > So an instruction is a sort of molecule composed of several

    > atoms. Now think of concatenative languages in which programs

    > are concatenated from molecules, each consisting of an

    > operator (like swap, + etc) together with additional parts

    > that complete what is meant. Note that the additional parts

    > are not further parameters that should be taken from the stack.

    > What useful additional parts may there be?

    >

    > I would take a hint from unix,

     It occurred to me a while back that the stack is to concatenative

    languages as a pipe is to Unix programs and shell scripts.

     > which has a rich collection of

    > what are called filters, programs that take one input fil and

    > produce one output file. The names of such programs, foo, bar,

    > baz and zot, can be concatenated to form what is called a pipe:

    > (here i dare not think what my mailer will do with the vertical bar)

    >

    > foo | bar | baz | zot

    >

    > and this concatenation will take one input file and produce one

    > output file such that ... You guessed it. But each of these programs

    > may have a useful default behaviour and also allow switches to

    > modify the default. The switches are typically single letters

    > precededd by a minus sign. So the pipe might actually look like

    > this:

    >

    > foo –a –g | bar –x | baz -e –q –w –e –r | zot –m –d

    >

    > So in the terminology I am tempted to adopt, here we have

    > the concatenation of four molecules or instructions,

    > where the first instruction consists of  three atoms, namely

    > a program and two switches.

    >

    > Apart from the pipe of output-input files, it may be necessary

    > to use other files, and there are lots of ways of doing that.

    >

    > The upshot: have we in the concatenative world missed out

    > on something useful by not allowing parts to the smallest

    > programs. There is a lot one could and should discuss here,

     Agreed!

    --

    don

     > but not me, not tonight.

    >

    >   - Manfred

    >

    >

    >

    > [Non-text portions of this message have been removed]

    >

    >

    > ------------------------------------

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2008-03-19 20:47:02

    Manfred Von Thun <m.vonthun@...> wrote:

     >  The upshot: have we in the concatenative world missed out

    >  on something useful by not allowing parts to the smallest

    >  programs. There is a lot one could and should discuss here,

    >  but not me, not tonight.

     We do already do that. All concatenative languages (except 01 :-)

    support numbers, which are molecules by your definition. Most support

    strings. Joy quotations are molecules whose component parts happen to

    be a proper subset of Joy itself.

    Of course, we could do more. I'm reminded of REBOL, which has some

    interesting syntax that might be applicable (block modification).

     >   - Manfred

     -Wm

## Manfred Von Thun — 2008-04-01 04:56:07

    On 20/3/08 6:47 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>

    > > wrote:

    >> >  The upshot: have we in the concatenative world missed out

    >> >  on something useful by not allowing parts to the smallest

    >> >  programs. There is a lot one could and should discuss here,

    >> >  but not me, not tonight.

    >

    > We do already do that. All concatenative languages (except 01 :-)

    > support numbers, which are molecules by your definition. Most support

    > strings. Joy quotations are molecules whose component parts happen to

    > be a proper subset of Joy itself.

     No, I mean something quite different. I did not mean that a molecule

    consists

    of consecutive digits (as do numerals) or of other printing characters

    (as do most symbols). Nor do I mean strings or quotations (including lists).

    Using the terminology of the grammar of Joy, all of the above are factors,

    resulting in a single operation being performed on the stack. My analogy

    was with Unix pipes. Here each command (a molecule in my meaning)

    might consist of a primary command (an atom in my meaning)) together with

    any (often optional) additional atoms. Some of these are additional

    parameters,

    some of these are command modifiers. None of these is a command

    by itself. The Unix pipe is a concatenation of such molecules.

      - Manfred

    [Non-text portions of this message have been removed]

## John Cowan — 2008-04-01 17:15:19

    Manfred Von Thun scripsit:

     > My analogy was with Unix pipes. Here each command (a molecule in my

    > meaning) might consist of a primary command (an atom in my meaning))

    > together with any (often optional) additional atoms. Some of these

    > are additional parameters, some of these are command modifiers. None

    > of these is a command by itself. The Unix pipe is a concatenation of

    > such molecules.

     But surely a molecule like "ls -l -C 2" is just syntactic sugar for

    ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"

    word as a list, not a quotation?

    --

    "Well, I'm back."  --Sam        John Cowan <cowan@...>

## Manfred Von Thun — 2008-04-02 02:12:56

    On 2/4/08 3:15 AM, "John Cowan" <cowan@...> wrote:

     > Manfred Von Thun scripsit:

    >

    >> > My analogy was with Unix pipes. Here each command (a molecule in my

    >> > meaning) might consist of a primary command (an atom in my meaning))

    >> > together with any (often optional) additional atoms. Some of these

    >> > are additional parameters, some of these are command modifiers. None

    >> > of these is a command by itself. The Unix pipe is a concatenation of

    >> > such molecules.

    >

    > But surely a molecule like "ls -l -C 2" is just syntactic sugar for

    > ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"

    > word as a list, not a quotation?

     That is one possible notation. But if a command frequently uses no

    modifiers,

    then that notation  would force users to supply an empty list of modifiers,

    as ³[] ls² for your example, in the most frequent uses.

    My list of candidate notations, using your example of ³ls², and their

    drawbacks:

    1. [-l c 2] ls  # forces empty list of modifiers if none are wanted

    2. ³la² ls  # ditto, only useful for plain flags, no good for other

    parameters

    3. foo | ls l c 2 | bar # unix style pipe symbol, painful if modifiers are

    rare

    4. (ls l c 2) # Lisp notation optional modifier list

    5. ls(-l c 2) #  functional notation optional modifier list, currently my

    favourite

    I must confess that my own list of possible modifiers for concatenative

    languages

    is miniscule compared with the multitude of modifiers in unix. But I am

    hoping that

    that is mostly a failure of imagination on my part.

    If anything like this is introduced, then a decision has to be made whether

    modifiers

    are just for the primitives or also for user defined molecules.

      - Manfred

    [Non-text portions of this message have been removed]

## John Cowan — 2008-04-02 03:49:52

    Manfred Von Thun scripsit:

     > > But surely a molecule like "ls -l -C 2" is just syntactic sugar for

    > > ordinary Joy "[-l -c 2] ls", where the list is treated by the "ls"

    > > word as a list, not a quotation?

    >

    > That is one possible notation. But if a command frequently uses no

    > modifiers, then that notation  would force users to supply an empty list

    > of modifiers, as ³[] ls² for your example, in the most frequent uses.

     Indeed.  But I was only saying that arguments to a word are nothing

    *fundamentally* new, unlike (say) alternation.  That doesn't mean that

    the syntactic sugar isn't worth having.

     > 5. ls(-l c 2) #  functional notation optional modifier list, currently my

    > favourite

     I too prefer this syntax.

     > I must confess that my own list of possible modifiers for concatenative

    > languages is miniscule compared with the multitude of modifiers in

    > unix. But I am hoping that that is mostly a failure of imagination on

    > my part.

     Modifiers to primitives may not be that useful, but modifiers to

    user-written words are a different story.

     > If anything like this is introduced, then a decision has to be made

    > whether modifiers are just for the primitives or also for user defined

    > molecules.

     I think it's important to have them for both.

    --

    John Cowan   cowan@...    http://ccil.org/~cowan

    I am he that buries his friends alive and drowns them and draws them

    alive again from the water. I came from the end of a bag, but no bag

    went over me.  I am the friend of bears and the guest of eagles. I am

    Ringwinner and Luckwearer; and I am Barrel-rider.  --Bilbo to Smaug

## William Tanksley, Jr — 2008-04-02 17:58:00

    Manfred Von Thun <m.vonthun@...> wrote:

     > > > wrote:

    >  >> >  The upshot: have we in the concatenative world missed out

    >  >> >  on something useful by not allowing parts to the smallest

    >  >> >  programs. There is a lot one could and should discuss here,

    >  >> >  but not me, not tonight.

    >  > We do already do that. All concatenative languages (except 01 :-)

    >  > support numbers, which are molecules by your definition. Most support

    >  > strings. Joy quotations are molecules whose component parts happen to

    >  > be a proper subset of Joy itself.

    >  No, I mean something quite different. I did not mean that a molecule

    >  consists

    >  of consecutive digits (as do numerals) or of other printing characters

    >  (as do most symbols). Nor do I mean strings or quotations (including lists).

    >  Using the terminology of the grammar of Joy, all of the above are factors,

    >  resulting in a single operation being performed on the stack. My analogy

    >  was with Unix pipes. Here each command (a molecule in my meaning)

    >  might consist of a primary command (an atom in my meaning)) together with

    >  any (often optional) additional atoms. Some of these are additional

    >  parameters,

    >  some of these are command modifiers. None of these is a command

    >  by itself. The Unix pipe is a concatenation of such molecules.

     I see. You want not an ability to define ANY type of syntax (which is

    what I described), but rather a small, standard syntax suited to

    common problems.

    That's an interesting problem. The syntax you propose reminds me of

    strongForth's inline type specifiers: because Forth's "EXECUTE" (a

    rough equivalent to Joy's "i") could have any stack effect and

    StrongForth has no type inference, Becher did not define "EXECUTE",

    and instead defined "EXECUTE(", a word which parsed for a close-paren

    and interpreted the contents as a type signature.

    I also note that Joy currently has words which would benefit from

    this; for example, all the words that have a number as part of their

    name could be replaced by the single word without the number, but

    taking an optional argument.

    REBOL does this kind of thing with the "/" (refinement) construct.

     >   - Manfred

     -Wm

## Manfred Von Thun — 2008-04-09 08:02:03

    On 2/4/08 1:49 PM, "John Cowan" <cowan@...> wrote:

     > Manfred Von Thun scripsit:

    > ....

    > Indeed.  But I was only saying that arguments to a word are nothing

    > *fundamentally* new, unlike (say) alternation.  That doesn't mean that

    > the syntactic sugar isn't worth having.

    >

     What a coincidence. Last weekend I started work on a non-deterministic

    postfix stack language, which of course has alternation as one of its

    principal program forming operators. That makes it non-concatenative

    I suppose.

     >

    > ...

    > Modifiers to primitives may not be that useful, but modifiers to

    > user-written words are a different story.

    >

    >> > If anything like this is introduced, then a decision has to be made

    >> > whether modifiers are just for the primitives or also for user defined

    >> > molecules.

    >

    > I think it's important to have them for both.

     To have both would imply a huge revision of the language. To have modifiers

    just for primitives would be much easier. And there is a further, more

    modest, choice: Find a collection of fixed modifiers that make sense to

    apply to (just about) anything. Again I cannot think of any such beasts

    whose actions cannot be achieved equally well by combinators. They would

    be variants to the i combinator:

    [...] i

    [...] [f g h] flagged-i

    Now it may be that there are no flags of any kind that whose effects cannot

    be achieved by existing mechanisms. Well, that may be failure of the

    imagination,

    or it indicates that the existing machinery is really quite good already.

     - Manfred

    [Non-text portions of this message have been removed]