# impure concatenativity: let without translation

## John Nowak — 2008-03-19 08:58:13

    Just moments ago, I gave this example of the quadratic formula:

       (define (quad a b c)

         (let ((d b 4 a c * * -)

               (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

               (x 2 a *)

               (p b r - x /)

               (n b r + x /))

           p n))

    How it works should be obvious after you get used to looking at this

    sort of prefix/postfix syntax. It's a very nice way to write this

    function; arguably nicer than what you can do in Scheme as the

    multiple values returned can be easily consumed (or ignored) by

    another function. For example, if we only cared about the positive

    root, we could do 'quad pop'.

    Now here's the quadratic formula in Joy:

       quad ==

           [[[pop pop 2 *]

               [pop 0 swap -]

               [swap dup * rollup * 4 * - sqrt]]

             [i] map]

           ternary i

           [[[+ swap /]

               [- swap /]]

             [i] map]

           ternary.

    Clearly we want to be able to write the first version of 'quad' as

    this version is truly awful (both in terms of readability and likely

    execution speed).

    Let's go back and examine how the first version works. I'd suggest

    that each variable introduced via 'let' must bind the result of a

    function that requires *no* arguments on the stack. This is a

    necessary restriction as otherwise the order in which you evaluate the

    functions matters and a bug in one can screw up the other. (Well, you

    could save and restore the stack for each binding, but that requires

    you represent the stack as a linked list.)

    I argue that translating the 'let' expression into point-free code is

    a *bad* idea. Why? Let's say we wrote this buggy version instead:

       (define (quad a b c)

         (let ((d b 4 a c * * * -)

               (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

               (x 2 a *)

               (p b r - x /)

               (n b r + x /))

           p n))

    See it? The 'd' function has an extra call to '*'. If we don't

    translate the 'let' away, we are able to give an intelligent error

    that implicates the call to '*' in the expression 'b 4 a c * * *' in

    the binding of 'd'. If we translate the let away however, who knows

    what the error will be. It depends how the compiler does the

    translation of course. The likely result will be an unhelpful type

    error that requires the programmer to tediously go over the entire

    function to try and find the problem.

    Worse yet, the translation might actually yield code that type checks

    by requiring an additional argument on the stack, but produces the

    wrong result and has the wrong type! (I'd guess that would be the case

    here actually.) You'd not catch this until much later when actually

    using 'quad' somewhere and getting confusing error messages. This sort

    of problem can take a long time to track down. If the reason we're

    introducing types is to get rid of these scenarios, then it seems

    translating everything to a point-free form is a bad idea. Such a

    translation necessarily discards the very information that allowed the

    programmer to write the function more easily in the first place!

    What I'm suggesting is that dropping any pretense of being purely

    concatenative offers some clear usability benefits with no loss in

    expressiveness. It would likely offer efficiency advantages as well;

    splicing quotes together to embed variables into the middle of

    anonymous functions is less than fun. Additionally, you can define

    primitives like 'swap' within the language itself:

    	(define (swap a b) b a)

    Are there any other proposals for an impure (or, more nicely,

    "hybrid") concatenative language out there? What are the negative

    practical implications of being impure?

    - John

## Joe Bowbeer — 2008-03-19 15:58:27

    On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:

     > Just moments ago, I gave this example of the quadratic formula:

    >

    >   (define (quad a b c)

    >     (let ((d b 4 a c * * -)

    >           (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

    >           (x 2 a *)

    >           (p b r - x /)

    >           (n b r + x /))

    >       p n))

    >

    >

     Is quad invoked postfix or prefix?

    The (quad a b c) syntax for declaration in scheme is especially nice because

    it looks like the expression that's used to invoke the function.

    I'm confused by the mixture of prefix and postfix in your example.

    Actually, I'm confused by all postfix, but I'd prefer to have consistency

    with my confusion:)

    --Joe

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

## John Nowak — 2008-03-19 18:58:04

    On Mar 19, 2008, at 11:58 AM, Joe Bowbeer wrote:

     > On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:

    >

    >> Just moments ago, I gave this example of the quadratic formula:

    >>

    >>  (define (quad a b c)

    >>    (let ((d b 4 a c * * -)

    >>          (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

    >>          (x 2 a *)

    >>          (p b r - x /)

    >>          (n b r + x /))

    >>      p n))

    >>

    >>

    >

    > Is quad invoked postfix or prefix?

     Postfix, as are *all* procedures. Only special forms are infix.

    Perhaps this is a better declaration form:

         (define (a b c quad)

            ...)

    - John

## Daniel Ehrenberg — 2008-03-19 20:31:27

    >  Are there any other proposals for an impure (or, more nicely,

    >  "hybrid") concatenative language out there? What are the negative

    >  practical implications of being impure?

    >

    >  - John

     Another stack-based language with prevalent use of named variables is

    Raven (http://mythago.net/language.html). The only downside to

    encouraging lots of variables is that the resulting language is more

    complicated. But, more fundamentally, focusing on variables in your

    efforts in language design draws attention away from creating

    abstractions in your library, both ones that depend on the stack and

    don't. This doesn't mean that you shouldn't make some way to have

    lexically scoped variables, of course.

    I don't understand why you say this is without translation. Of course

    translation exists at some level; you're just proposing that it

    happens at a level that the user not see, and that the translation be

    tightly integrated into the development environment so that type

    errors and such are easier to read.

    Dan

## Joe Bowbeer — 2008-03-19 20:51:38

    On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:

     >

    > On Mar 19, 2008, at 11:58 AM, Joe Bowbeer wrote:

    >

    > > On Wed, Mar 19, 2008 at 1:58 AM, John Nowak wrote:

    > >

    > >> Just moments ago, I gave this example of the quadratic formula:

    > >>

    > >>  (define (quad a b c)

    > >>    (let ((d b 4 a c * * -)

    > >>          (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

    > >>          (x 2 a *)

    > >>          (p b r - x /)

    > >>          (n b r + x /))

    > >>      p n))

    > >>

    > >>

    > >

    > > Is quad invoked postfix or prefix?

    >

    > Postfix, as are *all* procedures. Only special forms are infix.

    > Perhaps this is a better declaration form:

    >

    >     (define (a b c quad)

    >        ...)

    >

    > - John

    >

     Better.  Better yet is:

       (...

          (a b c quad) define)

    This maintains a consistent right-to-left reading direction.  If postfix is

    the "right thing," there's no such thing as too much, right?

    But if that's even better, then why not go right-to-left all the way?

       (...

          (c b a dauq) enifed)

    Naive question: Is there any reason why concatenative languages are

    (uniformly) postfix?  Would prefix work just as well, pushing elements onto

    the stack from right to left?

    --Joe

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

## Robbert van Dalen — 2008-03-19 21:04:23

    another postfix language with named 'variables' is enchilada.

    <disclaimer>

    this may seem like a shameless plug :)

    or i haven't been talking about enchilada that much lately :(

    </disclaimer>

    anyway, i don't think 'variables' defy pureness. let's consider

    symbols instead.

    symbols are placeholders for values to be. symbols can be bound so

    that they can be replaced by values.

    consider the following postfix expression with unbound symbols:

    x y + z *

    how do we bind z?

    to do this we enclose the expression with an enchilada 'macro' operator:

    {z=x y + z *}

    prefixing this macro with a value, binds symbol 'z:

    4 {z=x y + z *}

    x y + 4 *

    a macro acts like a monadic operator, binding a value with it's

    internal expression at each reduction step.

    in a sense, a macro fills in the blanks.

    macros bind lexically, i.e.

    1 2 3 {z={x={y=x y + z *}}}

    reduces to:

    1 2 3 {z={x={y=x y + z *}}}

    1 2 {x={y=x y + 3 *}}

    1 {y=2 y + 3 *}

    2 1 + 3 *

    3 3 *

    9

    another convenient (and operationally equal) form would be:

    1 2 3 {y x z=x y + z *}

    1 2 {y x=x y + 3 *}

    1 {y=2 y + 3 *}

    2 1 + 3 *

    3 3 *

    9

    'replacing' a symbol with a value doesn't need to be destructive: it

    can be pure: just leave every expression untouched. use pure copy

    semantics all the time.

    making copy semantics efficient and scalable: that's what enchilada is

    about.

    <end-shameless-plug/>

    - robbert

## Daniel Ehrenberg — 2008-03-19 21:06:12

    >  Naive question: Is there any reason why concatenative languages are

    >  (uniformly) postfix? Would prefix work just as well, pushing elements onto

    >  the stack from right to left?

    >

    >

    >  --Joe

     Naive answer: prefix is readable for simple things, but when things

    like "swap" are included, it gets more awkward to do prefix. It ends

    up that you're reading things backwards. Neither prefix nor postfix

    allows a completely left-to-right reading, but in my experience,

    postfix has things *mostly* left-to-right once you're comfortable with

    the language. Anyway, if the program is broken up into small units, it

    doesn't matter what order things are in! And concatenativity, whether

    in prefix or postfix, makes this much easier.

    Dan

## John Nowak — 2008-03-19 21:11:26

    On Mar 19, 2008, at 4:51 PM, Joe Bowbeer wrote:

     > On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:

    >

    >> Postfix, as are *all* procedures. Only special forms are infix.

    >> Perhaps this is a better declaration form:

    >>

    >>    (define (a b c quad)

    >>       ...)

    >>

    >> - John

    >>

    >

    > Better.  Better yet is:

    >

    >   (...

    >      (a b c quad) define)

    >

    > This maintains a consistent right-to-left reading direction.  If

    > postfix is

    > the "right thing," there's no such thing as too much, right?

     There is. Special forms and macros need access to the entire tree to

    do their work. If you were to put 'define' at the end, then there's no

    way for it to act on the tree (without some bizarre backtracking).

    Keep in mind that even [a b c] is really (lambda () a b c). Putting

    meta-level things like 'define' and 'let' up front also aids in

    readability.

     > Naive question: Is there any reason why concatenative languages are

    > (uniformly) postfix?  Would prefix work just as well, pushing

    > elements onto

    > the stack from right to left?

     Let's say these two are equivalent:

        -- postfix

        hypot -> sqr swap sqr + sqrt

        -- prefix

        sqrt + sqr swap sqr <- hypot

    Sure, both mean the same thing, but which is easier to read (provided

    you're used to reading left to right)?

    - John

## John Nowak — 2008-03-19 21:25:06

    On Mar 19, 2008, at 4:31 PM, Daniel Ehrenberg wrote:

     >> Are there any other proposals for an impure (or, more nicely,

    >> "hybrid") concatenative language out there? What are the negative

    >> practical implications of being impure?

    >>

    >

    > I don't understand why you say this is without translation. Of course

    > translation exists at some level; you're just proposing that it

    > happens at a level that the user not see, and that the translation be

    > tightly integrated into the development environment so that type

    > errors and such are easier to read.

     No, I'm proposing that there be no translation. (Or rather, if there

    is any translation, it would be something entirely up to the compiler

    author.)

    In other words, I'm extending the core language by making 'lambda' a

    fundamental component of the language. This is the reason you can

    write '(lambda (a b) b a)' without needing some built-in 'swap'

    primitive (or something equivalent using auxiliary stacks, etc) to

    translate it to. Basic operations like 'swap' are defined in terms of

    'lambda', not the other way around.

    The result is significantly better error reporting, a reduction in

    complexity on some level (you don't have to reduce things to the point-

    free translation to reason about them as 'lambda' is a fundamental

    part of the semantics), and a more efficient implementation (as you

    don't have to quote values and compose quotations together at runtime

    to create closures -- the implementor can choose whichever approach is

    best).

    Yes, you lose some interesting theoretical properties by defining the

    language as such. I don't think any of these are of practical concern,

    although if you can think of any, I'd be interesting in hearing them.

    It seems all of the (minor) additional complexity would be born by the

    implementor.

    - John

## rahul — 2008-03-19 21:48:56

    ....snip...

     > There is. Special forms and macros need access to the entire tree to

    > do their work. If you were to put 'define' at the end, then there's no

    > way for it to act on the tree (without some bizarre backtracking).

     Actually post script does:

    /inc3 { 3 add } def

    (and so does V :) )

    I think the reverse is true, it is harder to go against the flow

    when you are using postfix and give special treatment to syntactic markers

    like define/let etc.

     > Keep in mind that even [a b c] is really (lambda () a b c). Putting

    > meta-level things like 'define' and 'let' up front also aids in

    > readability.

     not entirely. '[a b c]' is really '<quote literal> lambda' :)

    On the second point, on One-sentence defitions (like the above) I find

    the postfix define easier to parse visually. - I guess it boils down to

    a matter of taste.

     >> Naive question: Is there any reason why concatenative languages are

    >> (uniformly) postfix?  Would prefix work just as well, pushing

    >> elements onto

    >> the stack from right to left?

    >

    > Let's say these two are equivalent:

    >

    >     -- postfix

    >     hypot -> sqr swap sqr + sqrt

    >

    >     -- prefix

    >     sqrt + sqr swap sqr <- hypot

    >

    > Sure, both mean the same thing, but which is easier to read (provided

    > you're used to reading left to right)?

     --

## William Tanksley, Jr — 2008-03-19 22:02:13

    John Nowak <john@...> wrote:

     >  translate it to. Basic operations like 'swap' are defined in terms of

    >  'lambda', not the other way around.

     I have proposed using stackshuffles instead of stack operators.

    Lambdas take that a little too far, though; a stack operator or a

    stack shuffle works in at worst constant time; a lambda may never

    terminate, and it's impossible in principle to tell.

     >  The result is significantly better error reporting,

     Only when you have a macro language laid on top of the base language

    and the macro language has inadequate error reporting.

     > a reduction in

    >  complexity on some level (you don't have to reduce things to the point-

    >  free translation to reason about them as 'lambda' is a fundamental

    >  part of the semantics),

     Point-free is reducible to atomic components. Lambda is not. That's

    not a reduction in complexity "on some level".

     > and a more efficient implementation (as you

    >  don't have to quote values and compose quotations together at runtime

    >  to create closures -- the implementor can choose whichever approach is

    >  best).

     I do agree that composing quotations shouldn't be necessary; but

    indeed, it never was considered as such until Joy came along. More

    power to Joy, but it's still only a convenience to be SOMETIMES used,

    not a requirement.

     >  Yes, you lose some interesting theoretical properties by defining the

    >  language as such. I don't think any of these are of practical concern,

    >  although if you can think of any, I'd be interesting in hearing them.

    >  It seems all of the (minor) additional complexity would be born by the

    >  implementor.

     You lose the ability to refactor a function using only cut-and-paste.

    You lose the ability to reason about a program in chunks as small as

    you want (that is, in a concatenative language if you see a phrase

    whose meaning you don't grasp you can work with that phrase in

    isolation, and you can be sure that the phrase in context means the

    exact same thing).

    Add variables, and you have to think about the program in the same way

    the author thought about it.

     >  - John

     -Wm

## John Nowak — 2008-03-19 22:31:29

    On Mar 19, 2008, at 5:48 PM, rahul wrote:

     > ....snip...

    >> There is. Special forms and macros need access to the entire tree to

    >> do their work. If you were to put 'define' at the end, then there's

    >> no

    >> way for it to act on the tree (without some bizarre backtracking).

    >

    > Actually post script does:

    > /inc3 { 3 add } def

    >

    > (and so does V :) )

     This is a nice approach for a dynamically typed, late-binding

    language. If 'def' is just a procedure that takes a symbol and a

    quotation on the stack, you can do things like quote values on the

    stack and define them at runtime for later use. There are a number of

    nice tricks actually. All of the interpreters I've written for

    concatenative languages work like this.

    Unfortunately, this approach doesn't work for a statically-typed,

    early-binding, compiled language. There are a number of reasons for

    this:

    1. It is necessary to run the program in order to get the definitions.

    This is obviously massively complicates, well, everything really.

    2. Type checking is awkward as you run into errors in the definition

    before you know what the definition will be named. Error reporting

    becomes more difficult.

    3. There's no way to introduce recursive definitions as the recursive

    call needs to be resolved before the name of the function is known.

    4. Tool support is largely out the window.

    5. You can't ensure that type checking or compilation will ever

    terminate.

     >> Keep in mind that even [a b c] is really (lambda () a b c). Putting

    >> meta-level things like 'define' and 'let' up front also aids in

    >> readability.

    >

    > not entirely. '[a b c]' is really '<quote literal> lambda' :)

     The same issues described above apply here. This is actually even more

    problematic as there's no way to guarantee that you can statically

    resolve bindings.

    - John

## John Nowak — 2008-03-19 22:47:47

    On Mar 19, 2008, at 6:02 PM, William Tanksley, Jr wrote:

     > John Nowak <john@...> wrote:

    >

    >> translate it to. Basic operations like 'swap' are defined in terms of

    >> 'lambda', not the other way around.

    >

    > I have proposed using stackshuffles instead of stack operators.

    > Lambdas take that a little too far, though; a stack operator or a

    > stack shuffle works in at worst constant time; a lambda may never

    > terminate, and it's impossible in principle to tell.

     Indeed. Of course lambdas can do a lot more than just shuffle.

     >> The result is significantly better error reporting,

    >

    > Only when you have a macro language laid on top of the base language

    > and the macro language has inadequate error reporting.

     Yes, we might imagine some wonderful macro system that has all sorts

    of hooks into the type checker and can inform it in various ways to

    allow it to somehow present code as it was written, preserving

    variable names and so on, when giving type errors. I don't think this

    is really possible in practice though without some massively

    complicated system and a truly heroic series of macros. Ultimately, I

    think it's a necessity for the type checker to be able to deal with

    let/lambda/etc if you're going to offer them.

     >> a reduction in

    >> complexity on some level (you don't have to reduce things to the

    >> point-

    >> free translation to reason about them as 'lambda' is a fundamental

    >> part of the semantics),

    >

    > Point-free is reducible to atomic components. Lambda is not. That's

    > not a reduction in complexity "on some level".

     Agreed. I don't dispute that this adds complexity to the semantics

    overall.

     >> and a more efficient implementation (as you

    >> don't have to quote values and compose quotations together at runtime

    >> to create closures -- the implementor can choose whichever approach

    >> is

    >> best).

    >

    > I do agree that composing quotations shouldn't be necessary; but

    > indeed, it never was considered as such until Joy came along. More

    > power to Joy, but it's still only a convenience to be SOMETIMES used,

    > not a requirement.

     Compositing quotations is equivalent to composing functions. I see

    this as a necessity. In either case, I don't see how you can create

    closures without quoting values and composing functions.

     >> Yes, you lose some interesting theoretical properties by defining the

    >> language as such. I don't think any of these are of practical

    >> concern,

    >> although if you can think of any, I'd be interesting in hearing them.

    >> It seems all of the (minor) additional complexity would be born by

    >> the

    >> implementor.

    >

    > You lose the ability to refactor a function using only cut-and-paste.

     You lose this the moment you introduce macros anyway. In either case,

    you only lose it if you use variables. If you don't use them, you're

    right where you were.

     > You lose the ability to reason about a program in chunks as small as

    > you want (that is, in a concatenative language if you see a phrase

    > whose meaning you don't grasp you can work with that phrase in

    > isolation, and you can be sure that the phrase in context means the

    > exact same thing).

     This ignores the possibility that lambdas might allow you to write

    code that doesn't put you in those situations as often to begin with.

    Variables are again only optional. Yes, you're stuck with them when

    looking at someone else's code, but no language is going to prevent

    programmers from writing terrible, confusing messes. I'm not a big fan

    of denying programmers powerful tools on the grounds that others might

    abuse them (not that that's what you were suggesting necessarily).

    - John

## rahul — 2008-03-19 23:20:15

    ...

     > 1. It is necessary to run the program in order to get the definitions.

    > This is obviously massively complicates, well, everything really.

    >

    > 2. Type checking is awkward as you run into errors in the definition

    > before you know what the definition will be named. Error reporting

    > becomes more difficult.

    >

    > 3. There's no way to introduce recursive definitions as the recursive

    > call needs to be resolved before the name of the function is known.

     Why cant we build a tree of tokens (first pass) and work with the tree?

    ie, once we assure that the quotes are balanced, it resolves into a pure

    expression tree (same as a prefix-lang) right?

     > 4. Tool support is largely out the window.

    >

    > 5. You can't ensure that type checking or compilation will ever

    > terminate.

    >

    >>> Keep in mind that even [a b c] is really (lambda () a b c). Putting

    >>> meta-level things like 'define' and 'let' up front also aids in

    >>> readability.

    >>

    >> not entirely. '[a b c]' is really '<quote literal> lambda' :)

    >

    > The same issues described above apply here. This is actually even more

    > problematic as there's no way to guarantee that you can statically

    > resolve bindings.

## John Nowak — 2008-03-19 23:26:10

    On Mar 19, 2008, at 7:20 PM, rahul wrote:

     > ...

    >> 1. It is necessary to run the program in order to get the

    >> definitions.

    >> This is obviously massively complicates, well, everything really.

    >>

    >> 2. Type checking is awkward as you run into errors in the definition

    >> before you know what the definition will be named. Error reporting

    >> becomes more difficult.

    >>

    >> 3. There's no way to introduce recursive definitions as the recursive

    >> call needs to be resolved before the name of the function is known.

    >>

    >> 4. Tool support is largely out the window.

    >>

    >> 5. You can't ensure that type checking or compilation will ever

    >> terminate.

    >

    > Why cant we build a tree of tokens (first pass) and work with the

    > tree?

     We can.

     > ie, once we assure that the quotes are balanced, it resolves into a

    > pure

    > expression tree (same as a prefix-lang) right?

     Yes, but I don't see how that helps with the five issues I mentioned.

    - John

## rahul — 2008-03-19 23:42:50

    >>

    >> Why cant we build a tree of tokens (first pass) and work with the

    >> tree?

    >

    > We can.

    >

    >> ie, once we assure that the quotes are balanced, it resolves into a

    >> pure

    >> expression tree (same as a prefix-lang) right?

    >

    > Yes, but I don't see how that helps with the five issues I mentioned.

     | 1. It is necessary to run the program in order to get the

    | definitions. This is obviously massively complicates, well, everything

    | really.

    Once you have an expression tree, you are no longer waiting for the symbol

    name to bind to .

    | 2. Type checking is awkward as you run into errors in the definition

    | before you know what the definition will be named. Error reporting

    | becomes more difficult.

    See above. You can check the wellformed-ness of the code during tree

    creation,

    once the tree is created, you know the symbol name to bind to, any further

    error reporting can make use of the symbol that you have at the root.

    | 3. There's no way to introduce recursive definitions as the recursive

    | call needs to be resolved before the name of the function is known.

    | 4. Tool support is largely out the window.

    | 5. You can't ensure that type checking or compilation will ever

    | terminate.

    see above, once the expression tree is created, there is n't any difference

    in what you can do with prefix and postfix notation.

    i.e. 'sum(sum(1,2),3)' and  '1 2 sum 3 sum' will yield the same tree,

    sum - 3

      |- sum - 2

         |- 1

    so what am I missing?

## John Nowak — 2008-03-19 23:57:08

    On Mar 19, 2008, at 7:42 PM, rahul wrote:

     > | 1. It is necessary to run the program in order to get the

    > | definitions. This is obviously massively complicates, well,

    > everything

    > | really.

    >

    > Once you have an expression tree, you are no longer waiting for the

    > symbol

    > name to bind to .

     Yes, this all can work if define is a special form. It doesn't work if

    define is a normal procedure though, which is, I thought, what you

    were suggesting. If that's not what you're suggesting, then '(define

    foo x y z)' or '\foo [x y z] define' is just a matter of taste

    perhaps. Even then, I'd still prefer the former, if for no other

    reason than it's apparent that 'define' is a special form.

    - John

## William Tanksley, Jr — 2008-03-20 00:03:30

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > John Nowak <john@...> wrote:

    >  >> translate it to. Basic operations like 'swap' are defined in terms of

    >  >> 'lambda', not the other way around.

    >  > I have proposed using stackshuffles instead of stack operators.

    >  > Lambdas take that a little too far, though; a stack operator or a

    >  > stack shuffle works in at worst constant time; a lambda may never

    >  > terminate, and it's impossible in principle to tell.

    >  Indeed. Of course lambdas can do a lot more than just shuffle.

     Right; they can additionally do anything the rest of  the language can

    do. Only the rest of the language doesn't need them in order to do it.

     >  >> The result is significantly better error reporting,

    >  > Only when you have a macro language laid on top of the base language

    >  > and the macro language has inadequate error reporting.

    >  Yes, we might imagine some wonderful macro system that has all sorts

    >  of hooks into the type checker and can inform it in various ways to

    >  allow it to somehow present code as it was written, preserving

    >  variable names and so on, when giving type errors. I don't think this

    >  is really possible in practice though without some massively

    >  complicated system and a truly heroic series of macros. Ultimately, I

    >  think it's a necessity for the type checker to be able to deal with

    >  let/lambda/etc if you're going to offer them.

     I admit that it's entirely unproven whether an inferential static type

    checker can work at all in a concatenative language, let alone one

    with macros. The ones we have now are not concatenative (or are only

    partially concatenative), and it makes good theoretical sense that

    this should be so.

    A non-inferential typechecker would be able to do better, but I don't

    see how such a thing would work with macros. Plus, inference is SUCH a

    good thing.

     >  >> and a more efficient implementation (as you

    >  >> don't have to quote values and compose quotations together at runtime

    >  >> to create closures -- the implementor can choose whichever approach

    >  >> is best).

    >  > I do agree that composing quotations shouldn't be necessary; but

    >  > indeed, it never was considered as such until Joy came along. More

    >  > power to Joy, but it's still only a convenience to be SOMETIMES used,

    >  > not a requirement.

    >  Compositing quotations is equivalent to composing functions. I see

    >  this as a necessity. In either case, I don't see how you can create

    >  closures without quoting values and composing functions.

     What do you mean "closures"? In my book, a closure is a function which

    refers to lexically available variables outside its local scope. A

    purely concatenative language does not have variables, and so does not

    have closures in that sense.

    I think you're referring to partially applied functions, which are

    useful when one wishes to specialize a function. Forth is able to do

    that, albeit messily, without quotations or their concatenation.

    There's a lot you can't easily do in Forth; Factor is in many ways a

    remediation of that. See

    http://factor-language.blogspot.com/2007/08/compiled-curry.html for

    the obvious way to do partial application in Factor.

     >  >> Yes, you lose some interesting theoretical properties by defining the

    >  >> language as such. I don't think any of these are of practical

    >  >> concern,

    >  >> although if you can think of any, I'd be interesting in hearing them.

    >  >> It seems all of the (minor) additional complexity would be born by

    >  >> the implementor.

    >  > You lose the ability to refactor a function using only cut-and-paste.

    >  You lose this the moment you introduce macros anyway.

     No, you only lose it over syntax macros, not expansion macros.

     > In either case,

    >  you only lose it if you use variables. If you don't use them, you're

    >  right where you were.

     I concede this, of course.

     >  > You lose the ability to reason about a program in chunks as small as

    >  > you want (that is, in a concatenative language if you see a phrase

    >  > whose meaning you don't grasp you can work with that phrase in

    >  > isolation, and you can be sure that the phrase in context means the

    >  > exact same thing).

    >  This ignores the possibility that lambdas might allow you to write

    >  code that doesn't put you in those situations as often to begin with.

     Well, actually, rather than ignoring it, it dismisses the possibility

    with a tired wave of its hand. Metaphorically speaking. Seriously,

    code has to be read carefully to be understood. Nothing will fix that.

    There is no algorithm that will cause code to be understood.

    I do concede and admit that having more tools is more practical than

    having fewer tools, so including locals and lexical scoping is better

    than not doing so; the problem isn't the locals, but the fact that

    most programmers are trained in nothing but them, and use them as

    crutches for their own lack of understanding rather than as poles to

    vault over problems that are truly helped by them. (Problems such as

    the infamous quadratic formula. I'm preparing an alternate, purely

    concatenative approach to that, one which is not as pretty but has

    interesting features to it.)

     >  Variables are again only optional. Yes, you're stuck with them when

    >  looking at someone else's code, but no language is going to prevent

    >  programmers from writing terrible, confusing messes. I'm not a big fan

    >  of denying programmers powerful tools on the grounds that others might

    >  abuse them (not that that's what you were suggesting necessarily).

     I concede that this is a large factor in my worry, and I concede that

    I share your attitude in general.

    I want to make it clear that there are many techniques that result in

    clear, simple concatenative code, and using locals is a distraction

    from them. Concatenative languages are in their infancy.

     >  - John

     -Wm

## John Nowak — 2008-03-20 00:27:37

    On Mar 19, 2008, at 8:03 PM, William Tanksley, Jr wrote:

     > I admit that it's entirely unproven whether an inferential static type

    > checker can work at all in a concatenative language,

     I swear I'm going to post that example soon...

     > let alone one with macros.

     I don't see why macros would complicate the type checker. Perhaps you

    were suggesting that macros complicate concatenativity.

     >> Compositing quotations is equivalent to composing functions. I see

    >> this as a necessity. In either case, I don't see how you can create

    >> closures without quoting values and composing functions.

    >

    > What do you mean "closures"? In my book, a closure is a function which

    > refers to lexically available variables outside its local scope. A

    > purely concatenative language does not have variables, and so does not

    > have closures in that sense.

     What I'm suggesting is code like this, where 'foo' is a function that

    takes an argument 'x' and returns a function with 'x' closed over:

        x foo = [bar x quux]

    That would get translated to point-free code like this (assuming a

    clever translation mechanism):

        foo = quote [bar] swap compose [quux] compose

    It seems that there's no way to do a proper translation of something

    like 'foo' without 'quote' and 'compose'.

     > See http://factor-language.blogspot.com/2007/08/compiled-curry.html

    > for

    > the obvious way to do partial application in Factor.

     The obvious way to implement partial application is in terms of quote

    and compose:

        pa = [quote] dip compose

    The Factor example seems to only avoid this when the function created

    via partial application is not returned from the context in which it

    was created.

     >>> You lose the ability to refactor a function using only cut-and-

    >>> paste.

    >>

    >> You lose this the moment you introduce macros anyway.

    >

    > No, you only lose it over syntax macros, not expansion macros.

     Fair enough. I was assuming a more powerful macro system.

     > I do concede and admit that having more tools is more practical than

    > having fewer tools, so including locals and lexical scoping is better

    > than not doing so; the problem isn't the locals, but the fact that

    > most programmers are trained in nothing but them, and use them as

    > crutches for their own lack of understanding rather than as poles to

    > vault over problems that are truly helped by them.

     This is a good point, although I see this as more of a problem to be

    solved via education and community conventions than anything else

    really.

     > (Problems such as the infamous quadratic formula. I'm preparing an

    > alternate, purely concatenative approach to that, one which is not

    > as pretty but has interesting features to it.)

     Sometimes though, you just need something to work as quickly as

    possible. If your language requires that you sit down and ponder how

    to translate something like the quadratic formula, you have a problem.

    I'm not suggesting that you agree or disagree with this; just stating

    my opinion.

     > Concatenative languages are in their infancy.

     This is a very, very good point. I'm experimenting with one particular

    aspect of concatenative languages; that is, placing them into a typed

    context. Alternatively, I'm experimenting with effect systems and type

    systems in a concatenative context if you'd prefer to put it that way.

    There's so much that I'm necessarily ignoring to be able to focus on

    these things. I'm still very interested in the purely concatenative

    approach as a way of writing simple, concise programs in a highly

    simplified language. The language I'm working on is not that language;

    I'm trying to convince myself to focus on just one for the moment.

    - John

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

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

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

    :

    >

    > I want to make it clear that there are many techniques that result in

    > clear, simple concatenative code, and using locals is a distraction

    > from them. Concatenative languages are in their infancy.

    this is a very important point to make.  also important is that people

    write applications in joy/cat/factor/whatever.  that's really the only

    way to discover new techniques and push the language(s) forward.  it

    can't be done by theory alone.

    >

    >>  - John

    >

    > -Wm

    >

## Don Groves — 2008-03-20 02:48:18

    On Mar 19, 2008, at 19:11 , John Nowak wrote:

     >

    > On Mar 19, 2008, at 4:51 PM, Joe Bowbeer wrote:

    >

    >> On Wed, Mar 19, 2008 at 11:58 AM, John Nowak wrote:

    >>

    >>> Postfix, as are *all* procedures. Only special forms are infix.

    >>> Perhaps this is a better declaration form:

    >>>

    >>>    (define (a b c quad)

    >>>       ...)

    >>>

    >>> - John

    >>>

    >>

    >> Better.  Better yet is:

    >>

    >>   (...

    >>      (a b c quad) define)

    >>

    >> This maintains a consistent right-to-left reading direction.  If

    >> postfix is

    >> the "right thing," there's no such thing as too much, right?

    >

    > There is. Special forms and macros need access to the entire tree to

    > do their work. If you were to put 'define' at the end, then there's no

    > way for it to act on the tree (without some bizarre backtracking).

    > Keep in mind that even [a b c] is really (lambda () a b c). Putting

    > meta-level things like 'define' and 'let' up front also aids in

    > readability.

    >

    >> Naive question: Is there any reason why concatenative languages are

    >> (uniformly) postfix?  Would prefix work just as well, pushing

    >> elements onto

    >> the stack from right to left?

    >

    > Let's say these two are equivalent:

    >

    >     -- postfix

    >     hypot -> sqr swap sqr + sqrt

    >

    >     -- prefix

    >     sqrt + sqr swap sqr <- hypot

     I'm partial to the syntax I'm using in ACL:

    [sqr swap sqr + sqrt] -> hypot

    This reads left-to-right and solves the problem of the

    as yet undefined symbol, hypot, which is read by ->

    Actually, I use "def" instead of "->" for clarity but the

    meaning is the same.

    --

    don

     > Sure, both mean the same thing, but which is easier to read (provided

    > you're used to reading left to right)?

    >

    > - John

    >

    >

    > ------------------------------------

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2008-03-20 16:03:53

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > I admit that it's entirely unproven whether an inferential static type

    >  > checker can work at all in a concatenative language,

    >  > let alone one with macros.

    >  I don't see why macros would complicate the type checker. Perhaps you

    >  were suggesting that macros complicate concatenativity.

     I was replying to your message, in which you appear to be talking

    specifically about the problems of making the type checker emit

    reasonable error messages in the presence of a sophisticated macro

    system. Did you mean something else?

     >  >> Compositing quotations is equivalent to composing functions. I see

    >  >> this as a necessity. In either case, I don't see how you can create

    >  >> closures without quoting values and composing functions.

    >  > What do you mean "closures"? In my book, a closure is a function which

    >  > refers to lexically available variables outside its local scope. A

    >  > purely concatenative language does not have variables, and so does not

    >  > have closures in that sense.

    >  What I'm suggesting is code like this, where 'foo' is a function that

    >  takes an argument 'x' and returns a function with 'x' closed over:

    >     x foo = [bar x quux]

     Okay, got it. You want dynamic code assembly. Forth (for example) does

    this by driving the compiler, which is available at runtime. Joy uses

    lists and interprets them. Either way, same basic idea: you need a

    word that incorporates a value as a literal and a word that

    incorporates a value as a function call into an ongoing definition.

    Your "compositing functions" is my "incorporates a value as a function call".

     >  > See http://factor-language.blogspot.com/2007/08/compiled-curry.html

    >  > for the obvious way to do partial application in Factor.

    >  The obvious way to implement partial application is in terms of quote

    >  and compose:

    >     pa = [quote] dip compose

     You're right; I apologize. I meant the obvious way to make it

    reasonably fast, not the obvious way to do it.

     >  The Factor example seems to only avoid this when the function created

    >  via partial application is not returned from the context in which it

    >  was created.

     I don't see why this is a limitation.

     >  > I do concede and admit that having more tools is more practical than

    >  > having fewer tools, so including locals and lexical scoping is better

    >  > than not doing so; the problem isn't the locals, but the fact that

    >  > most programmers are trained in nothing but them, and use them as

    >  > crutches for their own lack of understanding rather than as poles to

    >  > vault over problems that are truly helped by them.

    >  This is a good point, although I see this as more of a problem to be

    >  solved via education and community conventions than anything else

    >  really.

     You're totally right. I see part of the purpose of this group as

    finding what those conventions are, or at least might be. I admit that

    I take that purpose too seriously; there's also another purpose of

    this group, to find and explore uses of concatenative languages (which

    definitely includes useful things like math syntax and lambda syntax).

    Stevan makes a good point -- as fun as theory is, we need written

    code, and even an application written by a newbie who had to lean on

    the crutch of local variables almost the entire time is probably more

    likely to contain something unique than something written by an old

    Forther who's set in his ways.

    With that said, it makes sense to learn from the programmers of the

    old stack languages. There are two rules they use that seem

    appropriate: avoid syntax-changing macros, and avoid local variables.

    The interesting lesson for ME to take from these are that in both

    cases, the language provides facilities for these; the instruction to

    "avoid" them is just a recommendation, not a rule.

     >  > (Problems such as the infamous quadratic formula. I'm preparing an

    >  > alternate, purely concatenative approach to that, one which is not

    >  > as pretty but has interesting features to it.)

    >  Sometimes though, you just need something to work as quickly as

    >  possible. If your language requires that you sit down and ponder how

    >  to translate something like the quadratic formula, you have a problem.

     Then every language short of Mathematica or MathCAD has "a problem" --

    the quadratic formula isn't an obvious translation even in a lambda

    notation, and it's one of the simpler practical formulas.

    We're dealing with largely imperative languages here; they're always

    going to be clearer when expressing algorithms than they are when

    expressing formulas. This is one reason I find the idea of a math

    sublanguage attractive, because it adds something that the main

    language simply does not possess.

     >  > Concatenative languages are in their infancy.

    >  This is a very, very good point. I'm experimenting with one particular

    >  aspect of concatenative languages; that is, placing them into a typed

    >  context. Alternatively, I'm experimenting with effect systems and type

    >  systems in a concatenative context if you'd prefer to put it that way.

     Either way, your work is very interesting. I don't know what an

    "effect system" is, by the way.

     >  There's so much that I'm necessarily ignoring to be able to focus on

    >  these things. I'm still very interested in the purely concatenative

    >  approach as a way of writing simple, concise programs in a highly

    >  simplified language. The language I'm working on is not that language;

    >  I'm trying to convince myself to focus on just one for the moment.

     That's a very good point. Your field contains enough to explore

    anyhow; no need to add yet more unknowns.

     >  - John

     -Wm

## John Nowak — 2008-03-20 17:41:55

    On Mar 20, 2008, at 12:03 PM, William Tanksley, Jr wrote:

     > John Nowak <john@...> wrote:

    >>

    >

    >> I don't see why macros would complicate the type checker. Perhaps you

    >> were suggesting that macros complicate concatenativity.

    >

    > I was replying to your message, in which you appear to be talking

    > specifically about the problems of making the type checker emit

    > reasonable error messages in the presence of a sophisticated macro

    > system. Did you mean something else?

     Ah, no, I didn't. I thought you were suggesting macros would make type

    inference itself more difficult, not simply the ability to report

    useful errors.

     >> The Factor example seems to only avoid this when the function created

    >> via partial application is not returned from the context in which it

    >> was created.

    >

    > I don't see why this is a limitation.

     It's not; it's quite nice in fact. I was only pointing out that it

    isn't a general solution. You do need the ability to quote/compose in

    certain cases.

     > We're dealing with largely imperative languages here; they're always

    > going to be clearer when expressing algorithms than they are when

    > expressing formulas.

     Perhaps this shows a difference in our thinking here. I'm interested

    in making concatenative languages feel as declarative as possible. It

    seems to me that variables are necessary to achieve that in some cases.

     >> This is a very, very good point. I'm experimenting with one

    >> particular

    >> aspect of concatenative languages; that is, placing them into a typed

    >> context. Alternatively, I'm experimenting with effect systems and

    >> type

    >> systems in a concatenative context if you'd prefer to put it that

    >> way.

    >

    > Either way, your work is very interesting. I don't know what an

    > "effect system" is, by the way.

     An effect system is what Haskell programmers wish they had, even if

    they don't know it. Such a system as it works in Fifth allows you to

    freely mix effectful and pure code however you wish. The effect system

    is powerful enough to sort out what you're doing and, with complete

    accuracy, tell you which functions are pure and which aren't. In the

    case of combinators, it can tell you which functions provided to the

    combinator must be pure in order for the total effect of using the

    combinator to be pure. If a programmer isn't at all interested in

    purity, they simply ignore the system.

    The system can be used to enforce that certain functions are pure

    which is very useful when dealing with things like contracts, futures,

    map-reduce, et cetera. On the other hand, it allows free use of things

    like shared mutable arrays without them contaminating the rest of your

    code. Unlike the Haskell situation with monads, you don't run into all

    sorts of composability issues. See http://tinyurl.com/yvfhnf for some

    of Oleg's thoughts on this.

    - John

## Stevan Apter — 2008-03-20 22:54:48

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, March 20, 2008 11:03 AM

    Subject: Re: [stack] impure concatenativity: let without translation

    > John Nowak <john@...> wrote:

    >> William Tanksley, Jr wrote:

    >>  > I admit that it's entirely unproven whether an inferential static type

    >>  > checker can work at all in a concatenative language,

    >>  > let alone one with macros.

    >

    >>  I don't see why macros would complicate the type checker. Perhaps you

    >>  were suggesting that macros complicate concatenativity.

    >

    > I was replying to your message, in which you appear to be talking

    > specifically about the problems of making the type checker emit

    > reasonable error messages in the presence of a sophisticated macro

    > system. Did you mean something else?

    >

    >>  >> Compositing quotations is equivalent to composing functions. I see

    >>  >> this as a necessity. In either case, I don't see how you can create

    >>  >> closures without quoting values and composing functions.

    >

    >>  > What do you mean "closures"? In my book, a closure is a function which

    >>  > refers to lexically available variables outside its local scope. A

    >>  > purely concatenative language does not have variables, and so does not

    >>  > have closures in that sense.

    >

    >>  What I'm suggesting is code like this, where 'foo' is a function that

    >>  takes an argument 'x' and returns a function with 'x' closed over:

    >>     x foo = [bar x quux]

    >

    > Okay, got it. You want dynamic code assembly. Forth (for example) does

    > this by driving the compiler, which is available at runtime. Joy uses

    > lists and interprets them. Either way, same basic idea: you need a

    > word that incorporates a value as a literal and a word that

    > incorporates a value as a function call into an ongoing definition.

    >

    > Your "compositing functions" is my "incorporates a value as a function call".

    >

    >>  > See http://factor-language.blogspot.com/2007/08/compiled-curry.html

    >>  > for the obvious way to do partial application in Factor.

    >>  The obvious way to implement partial application is in terms of quote

    >>  and compose:

    >>     pa = [quote] dip compose

    >

    > You're right; I apologize. I meant the obvious way to make it

    > reasonably fast, not the obvious way to do it.

    >

    >>  The Factor example seems to only avoid this when the function created

    >>  via partial application is not returned from the context in which it

    >>  was created.

    >

    > I don't see why this is a limitation.

    >

    >>  > I do concede and admit that having more tools is more practical than

    >>  > having fewer tools, so including locals and lexical scoping is better

    >>  > than not doing so; the problem isn't the locals, but the fact that

    >>  > most programmers are trained in nothing but them, and use them as

    >>  > crutches for their own lack of understanding rather than as poles to

    >>  > vault over problems that are truly helped by them.

    >

    >>  This is a good point, although I see this as more of a problem to be

    >>  solved via education and community conventions than anything else

    >>  really.

    >

    > You're totally right. I see part of the purpose of this group as

    > finding what those conventions are, or at least might be. I admit that

    > I take that purpose too seriously; there's also another purpose of

    > this group, to find and explore uses of concatenative languages (which

    > definitely includes useful things like math syntax and lambda syntax).

    >

    > Stevan makes a good point -- as fun as theory is, we need written

    > code, and even an application written by a newbie who had to lean on

    > the crutch of local variables almost the entire time is probably more

    > likely to contain something unique than something written by an old

    > Forther who's set in his ways.

    >

    > With that said, it makes sense to learn from the programmers of the

    > old stack languages. There are two rules they use that seem

    > appropriate: avoid syntax-changing macros, and avoid local variables.

    > The interesting lesson for ME to take from these are that in both

    > cases, the language provides facilities for these; the instruction to

    > "avoid" them is just a recommendation, not a rule.

    my experience can't be unique.  i've been close to language development

    for 30 years.  the APL community had a high proportion of kibbitzers,

    urging the addition of this or that language extension.  the developers

    (who were also users -- no one wrote more APL code than iverson) were

    always searching for new ways to solve problems which emanated from

    the user community.  sometimes those were unexpected uses of existing

    resources, and sometimes the problems clumped together in some new

    way to suggest natural language extensions.  the evolution of k in

    the direction of database programming is a case in point:  new primitives,

    new datatypes.  but that wouldn't have happened if the language's author

    and many of his users weren't themselves immersed in database problems.

    so the developer can't restrict his attention to the inner workings

    of the language.  he needs data about what's important and what's not.

    those facts cannot be acquired purely deductively.

    i agree with billy that teaching a concatenative language with training

    wheels might be a useful approach.  newbies to APL often get a mixed diet of

    looping solutions and array solutions.  good programmers will shed the

    former quickly.  others won't.

    >

    >>  > (Problems such as the infamous quadratic formula. I'm preparing an

    >>  > alternate, purely concatenative approach to that, one which is not

    >>  > as pretty but has interesting features to it.)

    >

    >>  Sometimes though, you just need something to work as quickly as

    >>  possible. If your language requires that you sit down and ponder how

    >>  to translate something like the quadratic formula, you have a problem.

    >

    > Then every language short of Mathematica or MathCAD has "a problem" --

    > the quadratic formula isn't an obvious translation even in a lambda

    > notation, and it's one of the simpler practical formulas.

    >

    > We're dealing with largely imperative languages here; they're always

    > going to be clearer when expressing algorithms than they are when

    > expressing formulas. This is one reason I find the idea of a math

    > sublanguage attractive, because it adds something that the main

    > language simply does not possess.

    >

    >>  > Concatenative languages are in their infancy.

    >

    >>  This is a very, very good point. I'm experimenting with one particular

    >>  aspect of concatenative languages; that is, placing them into a typed

    >>  context. Alternatively, I'm experimenting with effect systems and type

    >>  systems in a concatenative context if you'd prefer to put it that way.

    >

    > Either way, your work is very interesting. I don't know what an

    > "effect system" is, by the way.

    >

    >>  There's so much that I'm necessarily ignoring to be able to focus on

    >>  these things. I'm still very interested in the purely concatenative

    >>  approach as a way of writing simple, concise programs in a highly

    >>  simplified language. The language I'm working on is not that language;

    >>  I'm trying to convince myself to focus on just one for the moment.

    >

    > That's a very good point. Your field contains enough to explore

    > anyhow; no need to add yet more unknowns.

    >

    >>  - John

    >

    > -Wm

    >

## William Tanksley, Jr — 2008-03-20 22:18:54

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > We're dealing with largely imperative languages here; they're always

    >  > going to be clearer when expressing algorithms than they are when

    >  > expressing formulas.

    >  Perhaps this shows a difference in our thinking here. I'm interested

    >  in making concatenative languages feel as declarative as possible. It

    >  seems to me that variables are necessary to achieve that in some cases.

     That's a great goal. One odd thing about concatenative languages is

    that even the least functionally pure of them (like Forth) tends to

    feel declarative while I'm coding in it -- my mental patterns are

    similar to the ones I fall into while coding in declarative functional

    languages. But, at the same time, Forth is undeniably imperative.

    There's definitely more that can be done to make concatenative

    languages that feel declarative. I suspect, however, that making

    concatenative languages that simply look familiar to applicative

    language programmers is risky since it can cause false positives.

    But I'm not sure that local variables are bad here. I'm of two minds on this.

     >  > Either way, your work is very interesting. I don't know what an

    >  > "effect system" is, by the way.

    >  An effect system is what Haskell programmers wish they had, even if

    >  they don't know it. Such a system as it works in Fifth allows you to

    >  freely mix effectful and pure code however you wish. The effect system

    >  is powerful enough to sort out what you're doing and, with complete

    >  accuracy, tell you which functions are pure and which aren't. In the

     Oh, very nice!

     >  - John

     -Wm

## William Tanksley, Jr — 2008-04-03 22:35:37

    John Nowak <john@...> wrote:

     > Just moments ago, I gave this example of the quadratic formula:

    >    (define (quad a b c)

    >      (let ((d b 4 a c * * -)

    >            (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if)

    >            (x 2 a *)

    >            (p b r - x /)

    >            (n b r + x /))

    >        p n))

    >  How it works should be obvious after you get used to looking at this

    >  sort of prefix/postfix syntax.

     I'd like to deal with this post in two parts: first, exploring the

    interesting issues you raise, and second, <ironic>solving once and for

    all</ironic> the pesky problem of finding the roots of a quadratic

    equation in a concatenative language. I'll do the latter in a distinct

    post.

    IMO, this is a very nice convention for special forms such as define,

    let, and others. It would in general make macros a lot less risky,

    since their scope would be explicitly delimited.

    To take this to an extreme, one could imagine making the parens

    optionally switchable with xml-style notation; such notation is useful

    when the special form spans a large block, as for example with Joy's

    LIBRA form. One shouldn't do this for a small block, but just as an

    example:

    <define>(quad a b c)

        <let>(d b 4 a c * * - )

               (r d 0 >= [d sqrt] ["quad: sqrt of negative" error] if )

               (x 2 a * )

               <p> b r - x / </p>

               <n> b r + x / </n>

       </let>

          p n

    </define>

    The rules for the transform I used should be quite obvious, and I

    failed to perform it in some places just to make it clear that it's

    purely syntactic, totally optional, and has no semantic effect.

    Such a syntax would be unbearable over short ranges (like in the 'let'

    above), but I suspect it would be convenient over large syntatic

    blocks -- and would make counting parentheses a thing of the past.

    I started this as a joke; now I'm tempted to modify a Scheme

    interpreter to see if it's realistic.

     > It's a very nice way to write this

    >  function; arguably nicer than what you can do in Scheme as the

    >  multiple values returned can be easily consumed (or ignored) by

    >  another function. For example, if we only cared about the positive

    >  root, we could do 'quad pop'.

     Agreed.

     >  What I'm suggesting is that dropping any pretense of being purely

    >  concatenative offers some clear usability benefits with no loss in

    >  expressiveness.

     The only loss is in referential transparency -- it's no longer true

    that cut and paste is always precisely sufficient to perform an

    "extract method" refactoring. BUT, frankly, that's not an unworkable

    loss.

     >  It would likely offer efficiency advantages as well;

    >  splicing quotes together to embed variables into the middle of

    >  anonymous functions is less than fun.

     I wouldn't encourage doing that anyways, but it's true that some

    problems lend themselves nicely to this type of solution.

     >  Are there any other proposals for an impure (or, more nicely,

    >  "hybrid") concatenative language out there?

    > What are the negative practical implications of being impure?

     The problem is that we don't know. I'd like to understand the negative

    practical implications of being purely concatenative. I know they

    exist.

     >  - John

     -Wm

## John Nowak — 2008-04-04 02:03:52

    On Apr 3, 2008, at 6:35 PM, William Tanksley, Jr wrote:

     > second, <ironic>solving once and for

    > all</ironic> the pesky problem of finding the roots of a quadratic

    > equation in a concatenative language. I'll do the latter in a distinct

    > post.

     I look forward to it. I assume it's nicely doable even if I've not

    seen it done yet.

     > <define>(quad a b c)

    >    <let>

    >        ...

    >   </let>

    >      p n

    > </define>

    >

    > Such a syntax would be unbearable over short ranges (like in the 'let'

    > above), but I suspect it would be convenient over large syntatic

    > blocks -- and would make counting parentheses a thing of the past.

     In all honesty, I've not ever counted parentheses since I began using

    DrScheme for all my Scheme editing needs years ago. I really do think

    this is a tool problem. For example, to give the benefits of what you

    show here, the editor could flash the name of the first element of

    each list as you close them. Mousing over a closing paren could do the

    same. I do think the current state of things though in DrScheme (and

    presumably emacs) is quite sufficient.

     >> What are the negative practical implications of being impure?

    >

    > The problem is that we don't know. I'd like to understand the negative

    > practical implications of being purely concatenative. I know they

    > exist.

     After working more on this recently, I've become convinced that having

    a concatenative language that is not *purely* concatenative is simply

    a horrible idea (macros and so on are fine). It complicates not only

    the implementation, but also how you can fundamentally reason about

    the language. Additionally, as you say, we simply don't know

    everything we'd be losing yet.

    I've mentioned this before, but I believe such an argument possibly

    extends to recursive definitions as well (e.g. fact = [zero?] [succ]

    [pred dup pred fact *] if). To make a completely and wholly

    unconvincing argument, such definitions destroy the soundness of my

    termination checker. A special form like 'letrec' would do similarly.

    At the moment, I'm going forward with a purely concatenative language

    that also does away with recursive definitions and is hence

    "nameless". In other words, there's no difference between a function

    definition and a (simple expanding) macro definition except in terms

    of implementation details (provided that quotations are opaque). I've

    posted a bit about this previously, and I'm now beginning to

    understand some of the implications with respect to the type system

    and optimization possibilities.

    I don't think it should be surprising though that such a "restriction"

    helps reasoning; if the type system prevents an 'm' combinator in any

    form ('dup i'), then your recursive possibilities depend entirely on

    the combinator set you are given. You therefore only need to

    understand the fundamental properties of each combinator to understand

    the properties of a program as a whole. Any sort of indefinite looping

    would require use of an appropriate combinator (e.g. "while"). You can

    also take advantage of the situation to prove that a given function

    uses a bounded amount of stack (where functions involving 'linrec' or

    similar would not).

    - John

## William Tanksley, Jr — 2008-04-04 18:30:51

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  > second, <ironic>solving once and for

    >  > all</ironic> the pesky problem of finding the roots of a quadratic

    >  > equation in a concatenative language. I'll do the latter in a distinct

    >  > post.

    >  I look forward to it. I assume it's nicely doable even if I've not

    >  seen it done yet.

     Given all the time I've had, one would think I'd be finished already.

    I'm not. (Of course, I haven't really put much time into it.)

    Don't expect too much -- I don't make the quadratic equation's

    *formula* obvious in a concatenative syntax. Instead, I make

    completing the square's *process* obvious. From what I can see,

    formulas learned in infix will only be recognizable when expressed

    using infix. But because computers perform processes better than they

    "evaluate formulas", I can always express the quadratic formula as its

    equivalent process -- and even if you've never learned how to complete

    the square, you'll be able to confirm or deny that the process will

    find the roots of the polynomial.

     >  > <define>(quad a b c)

    >  >    <let>

    >  >        ...

    >  >   </let>

    >  >      p n

    >  > </define>

    >  > Such a syntax would be unbearable over short ranges (like in the 'let'

    >  > above), but I suspect it would be convenient over large syntatic

    >  > blocks -- and would make counting parentheses a thing of the past.

    >  In all honesty, I've not ever counted parentheses since I began using

    >  DrScheme for all my Scheme editing needs years ago. I really do think

     I'll check it out -- I do have some recently acquired Scheme editing needs.

     >  this is a tool problem. For example, to give the benefits of what you

    >  show here, the editor could flash the name of the first element of

    >  each list as you close them. Mousing over a closing paren could do the

    >  same. I do think the current state of things though in DrScheme (and

    >  presumably emacs) is quite sufficient.

     The nice thing about such an editor is that it's essentially a static

    debugger. I've often thought of doing something like that for a

    concatenative language -- flashing thin little arrows to and from the

    sources and sinks of the data each word is consuming.

    But... I've never found flashing parens sufficient for reading complex

    structures, neither in SQL nor in Lisp. I want to be able to *look* at

    any part of the code and have some hope of seeing what it's connected

    to. I suppose I don't have an actual complaint with Scheme's syntax,

    really, and I've never had a problem figuring out Scheme's parens

    (after I learned it).

     >  >> What are the negative practical implications of being impure?

    >  > The problem is that we don't know. I'd like to understand the negative

    >  > practical implications of being purely concatenative. I know they

    >  > exist.

    >  After working more on this recently, I've become convinced that having

    >  a concatenative language that is not *purely* concatenative is simply

    >  a horrible idea (macros and so on are fine). It complicates not only

    >  the implementation, but also how you can fundamentally reason about

    >  the language. Additionally, as you say, we simply don't know

    >  everything we'd be losing yet.

     Good arguments. I'll have to remember them.

     >  I've mentioned this before, but I believe such an argument possibly

    >  extends to recursive definitions as well (e.g. fact = [zero?] [succ]

    >  [pred dup pred fact *] if). To make a completely and wholly

    >  unconvincing argument, such definitions destroy the soundness of my

    >  termination checker. A special form like 'letrec' would do similarly.

     Now this is fascinating -- and I find your termination checker

    argument to be profoundly convincing. I've long been interested in

    establishing a more useful lower bound for termination proofs.

    (Charity always succeeds,

    http://pll.cpsc.ucalgary.ca/charity1/www/home.html, but the language

    seems to have passed away.)

    In general, limiting the capabilities of a language in order to make

    reasoning about the language has much precedent; that was (as we've

    discussed) the original purpose of the FP language.

     >  At the moment, I'm going forward with a purely concatenative language

    >  that also does away with recursive definitions and is hence

    >  "nameless". In other words, there's no difference between a function

    >  definition and a (simple expanding) macro definition except in terms

    >  of implementation details (provided that quotations are opaque). I've

    >  posted a bit about this previously, and I'm now beginning to

    >  understand some of the implications with respect to the type system

    >  and optimization possibilities.

     Very nice.

     >  - John

     -Wm

## John Nowak — 2008-04-04 20:39:53

    On Apr 4, 2008, at 2:30 PM, William Tanksley, Jr wrote:

     >> this is a tool problem. For example, to give the benefits of what you

    >> show here, the editor could flash the name of the first element of

    >> each list as you close them. Mousing over a closing paren could do

    >> the

    >> same. I do think the current state of things though in DrScheme (and

    >> presumably emacs) is quite sufficient.

    >

    > The nice thing about such an editor is that it's essentially a static

    > debugger. I've often thought of doing something like that for a

    > concatenative language -- flashing thin little arrows to and from the

    > sources and sinks of the data each word is consuming.

     DrScheme will do exactly this when you hover over bindings (after

    clicking "check syntax"). Very useful sometimes... I've not seen

    anything else that does similarly.

    - John