# sweetening concatenative syntax

## John Nowak — 2008-03-05 09:04:14

    I've had some thoughts recently on syntactic additions to

    concatenative languages that seem potentially quite useful. At the

    very least, they would put an end to silly discussions over largely

    imagined deficiencies of postfix syntax and pointfree programming.

    This is perhaps crucial if we expect any significant uptake of

    concatenative languages.

    Below are the four extensions that I'm proposing. I'm strongly

    considering one or more in the language I'm currently working on

    (named "Fifth" for what are likely obvious reasons). The first two

    should be fairly uncontroversial. The latter two are simple

    translations I've not seen discussed before that seem potentially very

    useful in practice.

    I. Lambda Expressions

    Assuming functions have the syntax '[<body>]', it seems useful to

    introduce the syntax '[<bindings> -> <body>], where bindings are

    ordered with the top of the stack towards the right as is familiar.

    For example, the following two functions are equivalent:

         foo :: -> [a b -> b a a]

         foo = [swap dup]

         foo = [a b -> b a a]

    Note that the type syntax mimics the lambda expression syntax (or vice

    versa if you prefer). The type notation is similar to Cat's with minor

    alterations for the purposes of brevity. In particular, scalar

    variables are all lowercase, row variables are all uppercase, and

    concrete types are title-case and of at least two characters (to avoid

    confusion with row variables).

    Variables should, of course, be lexically scoped. A translation of

    expressions with lambdas to efficient pointfree stack-based code is

    not especially difficult. This is the case regardless of if the

    language is linear (which introduces only small complications), typed,

    or "lacking" a retain stack. Of course, I elide the translation here

    for the sake of... space.

    II. Local Function Variables

    If you permit lambdas, it makes sense to offer a simple syntax for

    declaring functions with named variables. This is similar to how

    Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo

    (lambda (<bindings>) <body>))'. The declaration syntax proposed here

    mimics use. In particular, the name of the function being defined

    occurs *after* the arguments.

    The following two statements are equivalent (where 'i' is the identity

    combinator with the type 'A (A -> B) -> B'):

         a b foo = b a a

         foo = [a b -> b a a] i

    Here's another example in which 'unlist' is a deconstructor for a

    list; the first function provided handled the null case and the second

    handles the cons case:

         unlist :: A [b] (A -> C) (A b [b] -> C) -> C

         map :: [a] (a -> b) -> [b]

         list f map = list [] [x xs -> x f i xs f map cons] unlist

    It should be noted that both lambda expressions and functions declared

    with the local variable syntax may use more items on the stack than

    they explicitly bind. For example, the following definition of map is

    equivalent to the above and likely preferable in practice:

         f map = [] [x xs -> x f i xs f map cons] unlist

    III. Prefix Notation

    It occurred to me recently that there exists a simple syntactic

    translation from prefix code (a la Scheme), where '(foo a b c)' is the

    application of 'foo' to three arguments, to postfix code. This

    translation can be done without any type information. The translation

    consists of simply removing the parenthesis and placing the first

    element at the end. If that first element is a local binding or a

    lambda expression, an 'i' is prepended to cause it to be evaluated.

    Here are some simple translation examples:

         (cons 1 null) => 1 null cons

         (+ (- 1 2) 3) => 1 2 - 3 +

         [f -> (f 10)] => [f -> 10 f i]

         f foo = (f 5) => f foo = 5 f i

    Interestingly, you get partial application for free:

         double = (* 2)

    One thing that may seem like a problem is that '(1 2 3)' will be

    translated to '(2 3 1)' when really an error should occur as '1' is

    not a function. However, that's not the case: '1' *is* a function.

    More precisely, it is a row polymorphic function that consumes a stack

    and yields a new stack (1 :: A -> A int). As such, the above syntactic

    translation is completely valid and it would be wrong to reject it.

    Prefix notation may seem like a curiosity at first, perhaps existing

    only to lure over those familiar with prefix notation. However, I'd

    argue that prefix notation makes certain code objectively easier to

    read. This is especially the case when dealing with deconstructors

    like 'if' or 'unlist' as the higher order function of primary interest

    is "announced" earlier in the definition. In the following example,

    both functions are equivalent:

         f map = [] [x xs -> x f i xs f map cons] unlist

         f map =

           (unlist []

                   [x xs -> x f i xs f map cons])

    (Perhaps this is not the best example. Substitute a better one with

    nested ifs.)

    Prefix notation also has the benefit that you can express "nested"

    code (as above) in a way that allows editors to automatically intent

    properly. This is not at all the case with purely postfix code where

    type information and perhaps some heuristics would need to be involved

    to produce acceptable indentation.

    Here's a rewriting of map using *only* prefix notation in a way that

    most any Scheme or Haskell programmer would find comfortable:

         f map =

           (unlist []

                   [x xs -> (cons (f x) (map xs f))])

    IV. Indentation

    Prefix notation is often criticized for being overly verbose or noisy.

    The Python solution is to use indentation instead of paired

    delimiters, but this introduces a number of problems: It's harder for

    machines to generate valid code, pasting between sources can be messy,

    editors can't really automatically re-indent code, plenty of people

    (myself included) hate it, etc.

    The correct way to address this problem (if you are to address it at

    all) is to do what Haskell does and offer *optional* indentation-

    sensitive syntax that gets translated to the more explicit form. This

    can be implemented as a relatively trivial pre-parser pass and does

    not require modification of the parser itself.

    Indentation-sensitive syntax is introduced with a colon. Here are some

    simple examples showing how indentation-sensitive code is translated

    to prefix code which is then translated to "normal" code:

         a b c: d e f  =>  a b (c d e f)        =>  a b d e f c

         a b c:

           d e f:      =>  a b (c d e (f g h))  =>  a b d e g h f c

             g h

    Finally, here again is our map example, this time even spiffier:

         f map = unlist:

           []

           [x xs -> cons: (f x) (map xs f)]

    This looks quite close to the Haskell version, except that our

    programs are, after translation, still expressed only in terms of the

    functional forms of composition and quotation! (I was wrong in an

    earlier email when I started that composition is the only functional

    form in Joy. Quotation is also a functional form.) This definition is

    arguably easier to read than the postfix, pointfree alternative, as it

    clearly announces at the start that 'map' is a function that

    destructures a list, details the result of the destructization at the

    start of the relevant line, and indicates directly after that the

    result of the function will be a list via the prefixing of 'cons'.

    - John

## John Nowak — 2008-03-05 09:19:19

    Minor issues with the previous email:

    1. I fell back to a Cat-like syntax for type definitions. Here are the

    correct notations for 'i', 'map', and 'unlist':

         i      :: A [A -> B] -> B

         map    :: (List a) [a -> b] -> (List b)

         unlist :: A (List b) [A -> C] [A b (List b) -> C] -> C

    Arguably there should be a type abbreviation for '(List a)'; perhaps

    '{a}'.

    2. The phrase "allows editors to automatically intent" should read

    "allows editors to automatically INDENT".

    3. By "it's harder for machines to generate valid code", I mean that

    it is harder to generate *source* code when compiling to a language

    with indentation-sensitive syntax. Explicit paired delimiters are

    easier to deal with.

    4. It's too long. Unfortunately, I don't have the time to write a

    shorter version.

## Daniel Ehrenberg — 2008-03-05 14:14:13

    >  I. Lambda Expressions

    >  II. Local Function Variables

     Sure, these two seem reasonable seems reasonable. Factor and Cat

    support these. The only thing I have to say is, they shouldn't be used

    too often or for everything, since they can make code unnecessarily

    more verbose and less factorable.

     >  III. Prefix Notation

    >  Prefix notation may seem like a curiosity at first, perhaps existing

    >  only to lure over those familiar with prefix notation. However, I'd

    >  argue that prefix notation makes certain code objectively easier to

    >  read. This is especially the case when dealing with deconstructors

    >  like 'if' or 'unlist' as the higher order function of primary interest

    >  is "announced" earlier in the definition. In the following example,

    >  both functions are equivalent:

    >

    >  f map = [] [x xs -> x f i xs f map cons] unlist

    >

    >  f map =

    >  (unlist []

    >  [x xs -> x f i xs f map cons])

    >

    >  (Perhaps this is not the best example. Substitute a better one with

    >  nested ifs.)

    >

    >  Prefix notation also has the benefit that you can express "nested"

    >  code (as above) in a way that allows editors to automatically intent

    >  properly. This is not at all the case with purely postfix code where

    >  type information and perhaps some heuristics would need to be involved

    >  to produce acceptable indentation.

    >

    >  Here's a rewriting of map using *only* prefix notation in a way that

    >  most any Scheme or Haskell programmer would find comfortable:

    >

    >  f map =

    >  (unlist []

    >  [x xs -> (cons (f x) (map xs f))])

    >

     Now this I have a very hard time understanding the motivation for.

    Sure, when you're just learning concatenative languages, it can be a

    little weird that "if" comes after the quotations, but humans don't

    read completely linearly in normal circumstances, and it doesn't take

    too much effort to look to the end. In a case where you have to look a

    page ahead, I'd say the fault lies with the author of the code writing

    things unreadably, rather than the language being unreadable. Also,

    what happens if a function is given too many arguments? The result is

    very counterintuitive, and a more useful translation would take into

    account type information.

     >  IV. Indentation

    >

    >  f map = unlist:

    >  []

    >  [x xs -> cons: (f x) (map xs f)]

     I don't completely get it. This example doesn't take advantage of

    indentation, it only uses modified prefix syntax. I guess the

    indentation can make a difference if you have multiple arguments

    following the word, and then something else after that that's not an

    argument?

    Sure, there are lots of translations that we could make efficiently

    and accurately with concatenative languages, but I'm not sure if all

    of these are essential or beneficial to the nature of the languages.

    They make things more complicated and they remove all of the nice

    properties of concatenativity, which is useful in building software

    because it helps you factor code. We could easily create a translation

    from Scheme to a concatenative language, but that doesn't mean that

    we'd want to do all of our concatenative programming on a Scheme skin.

## John Nowak — 2008-03-05 20:14:47

    On Mar 5, 2008, at 9:14 AM, Daniel Ehrenberg wrote:

     > Sure, there are lots of translations that we could make efficiently

    > and accurately with concatenative languages, but I'm not sure if all

    > of these are essential or beneficial to the nature of the languages.

    > They make things more complicated and they remove all of the nice

    > properties of concatenativity, which is useful in building software

    > because it helps you factor code.

     I'm not convinced concatenativity offers a huge advantage in

    factoring. It's easy to write code in such a way that useful chunks

    can't be pulled out. It's also difficult to find useful abstractions

    unless you have some experience. For example, I'd guess the novice

    programmer looking to add two lists together wouldn't accidently write

    zip-with.

    I think how factorable a language is primarily depends on its

    usefulness in building abstractions rather than any particular syntax.

    Languages with first class functions offer factorability that language

    like Forth don't offer. Haskell's type classes over a level of safe

    and structured factorability that's inaccessible to Joy. ML's functors

    offer a means of factoring I often miss when using Haskell. Types

    offer a way of verifying my abstractions in a way I miss when using

    Scheme. Scheme offers macros as a means of factoring that I miss when

    using Haskell. Et cetera.

    If a syntax that is non-concatenative makes it any easier to use any

    of the other means of factoring, then it seems to me it's worth

    considering.

    - John

## John Nowak — 2008-03-05 20:39:53

    On Mar 5, 2008, at 3:14 PM, John Nowak wrote:

     > I think how factorable a language is primarily depends on its

    > usefulness in building abstractions rather than any particular syntax.

    > Languages with first class functions offer factorability that language

    > like Forth don't offer. Haskell's type classes over a level of safe

    > and structured factorability that's inaccessible to Joy. ML's functors

    > offer a means of factoring I often miss when using Haskell. Types

    > offer a way of verifying my abstractions in a way I miss when using

    > Scheme. Scheme offers macros as a means of factoring that I miss when

    > using Haskell. Et cetera.

     I forgot an obvious one: Joy's stack-based nature, which makes it

    possible to return multiple values from a function and then easily

    consume them in another, opens up many possibilities for factoring

    that I often miss when using other languages.

    - John

## Stevan Apter — 2008-03-05 22:26:51

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, March 05, 2008 3:39 PM

    Subject: Re: [stack] sweetening concatenative syntax

    > On Mar 5, 2008, at 3:14 PM, John Nowak wrote:

    >

    >> I think how factorable a language is primarily depends on its

    >> usefulness in building abstractions rather than any particular syntax.

    >> Languages with first class functions offer factorability that language

    >> like Forth don't offer. Haskell's type classes over a level of safe

    >> and structured factorability that's inaccessible to Joy. ML's functors

    >> offer a means of factoring I often miss when using Haskell. Types

    >> offer a way of verifying my abstractions in a way I miss when using

    >> Scheme. Scheme offers macros as a means of factoring that I miss when

    >> using Haskell. Et cetera.

    temperament, taste, and further imponderable subjectivities.  perhaps a

    useful distinction to make is between monoglot and polyglot programmers.

    i'm an extreme case of the former, and you sound like you belong way

    over on the other edge.  given the decision to code in a concatenative

    language, i want my concatenativity neat, straight no chaser.  the

    sharp, clear outlines of the basic syntax are no small part of what i

    like about joy.  in contrast to dan, i think introducing variables in

    any form should be resisted (although i've implemented both in my toy

    languages, just for the heck of it.)  moreover, i agree with something

    dr. tanksley has often said:  we don't yet know all the properties of

    these languages in their pure form, since no one (as far as i can tell

    from years on this list) has written any large-scale, multi-programmer,

    long-lived applications in any concatenative language.  many small

    examples, much tinkering under the hood, but nothing approaching the

    scale of, say, ebay.

    >

    > I forgot an obvious one: Joy's stack-based nature, which makes it

    > possible to return multiple values from a function and then easily

    > consume them in another, opens up many possibilities for factoring

    > that I often miss when using other languages.

    >

    > - John

    >

## john@johnnowak.com — 2008-03-05 23:08:35

    On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:

     > temperament, taste, and further imponderable subjectivities.  perhaps a

    > useful distinction to make is between monoglot and polyglot programmers.

    > i'm an extreme case of the former, and you sound like you belong way

    > over on the other edge.

     Heh, well, I'm largely playing devil's advocate here. My personal opinions

    towards this sort of thing are largely the same as your own. I generally

    consider myself a Scheme/Joy-pushing monoglot programmer. I do however

    have a growing, nasty, type system addiction.

    Still, I think there may be some value in permitting these things because

    they can be completely translated away. If you don't want to use them,

    then don't. No harm done. I think.

    - John

## Don Groves — 2008-03-06 01:34:28

    Hi, John --

    Where can we read about Fifth? Several years ago, someone

    announced a Fifth language, is yours a continuation of that effort,

    or was that you?

    --

    don

     On Mar 5, 2008, at 19:04 , John Nowak wrote:

    > I've had some thoughts recently on syntactic additions to

    > concatenative languages that seem potentially quite useful. At the

    > very least, they would put an end to silly discussions over largely

    > imagined deficiencies of postfix syntax and pointfree programming.

    > This is perhaps crucial if we expect any significant uptake of

    > concatenative languages.

    >

    > Below are the four extensions that I'm proposing. I'm strongly

    > considering one or more in the language I'm currently working on

    > (named "Fifth" for what are likely obvious reasons). The first two

    > should be fairly uncontroversial. The latter two are simple

    > translations I've not seen discussed before that seem potentially very

    > useful in practice.

    >

    > I. Lambda Expressions

    >

    > Assuming functions have the syntax '[<body>]', it seems useful to

    > introduce the syntax '[<bindings> -> <body>], where bindings are

    > ordered with the top of the stack towards the right as is familiar.

    > For example, the following two functions are equivalent:

    >

    >      foo :: -> [a b -> b a a]

    >      foo = [swap dup]

    >      foo = [a b -> b a a]

    >

    > Note that the type syntax mimics the lambda expression syntax (or vice

    > versa if you prefer). The type notation is similar to Cat's with minor

    > alterations for the purposes of brevity. In particular, scalar

    > variables are all lowercase, row variables are all uppercase, and

    > concrete types are title-case and of at least two characters (to avoid

    > confusion with row variables).

    >

    > Variables should, of course, be lexically scoped. A translation of

    > expressions with lambdas to efficient pointfree stack-based code is

    > not especially difficult. This is the case regardless of if the

    > language is linear (which introduces only small complications), typed,

    > or "lacking" a retain stack. Of course, I elide the translation here

    > for the sake of... space.

    >

    > II. Local Function Variables

    >

    > If you permit lambdas, it makes sense to offer a simple syntax for

    > declaring functions with named variables. This is similar to how

    > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo

    > (lambda (<bindings>) <body>))'. The declaration syntax proposed here

    > mimics use. In particular, the name of the function being defined

    > occurs *after* the arguments.

    >

    > The following two statements are equivalent (where 'i' is the identity

    > combinator with the type 'A (A -> B) -> B'):

    >

    >      a b foo = b a a

    >      foo = [a b -> b a a] i

    >

    > Here's another example in which 'unlist' is a deconstructor for a

    > list; the first function provided handled the null case and the second

    > handles the cons case:

    >

    >      unlist :: A [b] (A -> C) (A b [b] -> C) -> C

    >

    >      map :: [a] (a -> b) -> [b]

    >      list f map = list [] [x xs -> x f i xs f map cons] unlist

    >

    > It should be noted that both lambda expressions and functions declared

    > with the local variable syntax may use more items on the stack than

    > they explicitly bind. For example, the following definition of map is

    > equivalent to the above and likely preferable in practice:

    >

    >      f map = [] [x xs -> x f i xs f map cons] unlist

    >

    > III. Prefix Notation

    >

    > It occurred to me recently that there exists a simple syntactic

    > translation from prefix code (a la Scheme), where '(foo a b c)' is the

    > application of 'foo' to three arguments, to postfix code. This

    > translation can be done without any type information. The translation

    > consists of simply removing the parenthesis and placing the first

    > element at the end. If that first element is a local binding or a

    > lambda expression, an 'i' is prepended to cause it to be evaluated.

    > Here are some simple translation examples:

    >

    >      (cons 1 null) => 1 null cons

    >      (+ (- 1 2) 3) => 1 2 - 3 +

    >      [f -> (f 10)] => [f -> 10 f i]

    >      f foo = (f 5) => f foo = 5 f i

    >

    > Interestingly, you get partial application for free:

    >

    >      double = (* 2)

    >

    > One thing that may seem like a problem is that '(1 2 3)' will be

    > translated to '(2 3 1)' when really an error should occur as '1' is

    > not a function. However, that's not the case: '1' *is* a function.

    > More precisely, it is a row polymorphic function that consumes a stack

    > and yields a new stack (1 :: A -> A int). As such, the above syntactic

    > translation is completely valid and it would be wrong to reject it.

    >

    > Prefix notation may seem like a curiosity at first, perhaps existing

    > only to lure over those familiar with prefix notation. However, I'd

    > argue that prefix notation makes certain code objectively easier to

    > read. This is especially the case when dealing with deconstructors

    > like 'if' or 'unlist' as the higher order function of primary interest

    > is "announced" earlier in the definition. In the following example,

    > both functions are equivalent:

    >

    >      f map = [] [x xs -> x f i xs f map cons] unlist

    >

    >      f map =

    >        (unlist []

    >                [x xs -> x f i xs f map cons])

    >

    > (Perhaps this is not the best example. Substitute a better one with

    > nested ifs.)

    >

    > Prefix notation also has the benefit that you can express "nested"

    > code (as above) in a way that allows editors to automatically intent

    > properly. This is not at all the case with purely postfix code where

    > type information and perhaps some heuristics would need to be involved

    > to produce acceptable indentation.

    >

    > Here's a rewriting of map using *only* prefix notation in a way that

    > most any Scheme or Haskell programmer would find comfortable:

    >

    >      f map =

    >        (unlist []

    >                [x xs -> (cons (f x) (map xs f))])

    >

    > IV. Indentation

    >

    > Prefix notation is often criticized for being overly verbose or noisy.

    > The Python solution is to use indentation instead of paired

    > delimiters, but this introduces a number of problems: It's harder for

    > machines to generate valid code, pasting between sources can be messy,

    > editors can't really automatically re-indent code, plenty of people

    > (myself included) hate it, etc.

    >

    > The correct way to address this problem (if you are to address it at

    > all) is to do what Haskell does and offer *optional* indentation-

    > sensitive syntax that gets translated to the more explicit form. This

    > can be implemented as a relatively trivial pre-parser pass and does

    > not require modification of the parser itself.

    >

    > Indentation-sensitive syntax is introduced with a colon. Here are some

    > simple examples showing how indentation-sensitive code is translated

    > to prefix code which is then translated to "normal" code:

    >

    >      a b c: d e f  =>  a b (c d e f)        =>  a b d e f c

    >

    >      a b c:

    >        d e f:      =>  a b (c d e (f g h))  =>  a b d e g h f c

    >          g h

    >

    > Finally, here again is our map example, this time even spiffier:

    >

    >      f map = unlist:

    >        []

    >        [x xs -> cons: (f x) (map xs f)]

    >

    > This looks quite close to the Haskell version, except that our

    > programs are, after translation, still expressed only in terms of the

    > functional forms of composition and quotation! (I was wrong in an

    > earlier email when I started that composition is the only functional

    > form in Joy. Quotation is also a functional form.) This definition is

    > arguably easier to read than the postfix, pointfree alternative, as it

    > clearly announces at the start that 'map' is a function that

    > destructures a list, details the result of the destructization at the

    > start of the relevant line, and indicates directly after that the

    > result of the function will be a list via the prefixing of 'cons'.

    >

    > - John

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## john@johnnowak.com — 2008-03-06 02:03:15

    On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:

     > temperament, taste, and further imponderable subjectivities.

     Well, perhaps this is worth testing then. Here's how I'm suggesting one

    could write a non-tail-recursive 'map' in terms of 'cons' and 'unlist':

    f map = unlist:

      []

      [x xs -> (f x) (map xs f) cons]

     > i want my concatenativity neat, straight no chaser.

     How would you personally write this in a purely concatenative form? No

    cheating by using combinators like 'fold'; you only get to use 'cons' (a

    {a} -> {a}) and 'unlist' (A {b} [A -> C] [A b {b} -> C] -> C).

    - John

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

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

    From: <john@...>

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, March 05, 2008 9:03 PM

    Subject: Re: [stack] sweetening concatenative syntax

    > On Mar 5, 2008, at 5:26 PM, Stevan Apter wrote:

    >

    >> temperament, taste, and further imponderable subjectivities.

    >

    > Well, perhaps this is worth testing then. Here's how I'm suggesting one

    > could write a non-tail-recursive 'map' in terms of 'cons' and 'unlist':

    >

    > f map = unlist:

    >  []

    >  [x xs -> (f x) (map xs f) cons]

    >

    >> i want my concatenativity neat, straight no chaser.

    >

    > How would you personally write this in a purely concatenative form? No

    > cheating by using combinators like 'fold'; you only get to use 'cons' (a

    > {a} -> {a}) and 'unlist' (A {b} [A -> C] [A b {b} -> C] -> C).

    my joy is so rusty these days.  i'm on the wagon.

    in the g variant of my f language:

    [[dup!count![]top!]dip!swap!

     [[uncons!]dip!dup!top!

      [cons!unit!. first!swons!]dipd!]

     do!pop!pop!|]                          map             "[..][f]map!"

    and in XY:

    ; map [jump] [each* rot => map <= swons] [pop] ifte ;

    ; each* => uncons <= tuck 2slip ;

    in both languages, all words are bottom out in symbolic primitives.  six or

    seven for XY, rather more for g.

    details here:  www.nsl.com.

    >

    > - John

    >

    >

## John Nowak — 2008-03-06 02:52:32

    On Mar 5, 2008, at 8:34 PM, Don Groves wrote:

     > Where can we read about Fifth?

     At 5th.org, in a few weeks from now.

     > Several years ago, someone

    > announced a Fifth language, is yours a continuation of that effort,

    > or was that you?

     No, it wasn't me, nor is this a continuation of anything.

    - John

## Don Groves — 2008-03-06 02:58:23

    On Mar 5, 2008, at 19:52 , John Nowak wrote:

     >

    > On Mar 5, 2008, at 8:34 PM, Don Groves wrote:

    >

    >> Where can we read about Fifth?

    >

    > At 5th.org, in a few weeks from now.

     Thanks!

     >

    >> Several years ago, someone

    >> announced a Fifth language, is yours a continuation of that effort,

    >> or was that you?

    >

    > No, it wasn't me, nor is this a continuation of anything.

     I just figured that out. My references to Fifth are 20 years old ;-)

    --

    don

     >

    > - John

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## John Nowak — 2008-03-06 03:12:39

    On Mar 5, 2008, at 9:34 PM, Stevan Apter wrote:

     > ; map [jump] [each* rot => map <= swons] [pop] ifte ;

    > ; each* => uncons <= tuck 2slip ;

     So that, versus this:

    f map = unlist:

       []

       [x xs -> (f x) (map xs f) cons]

    It seems to me that the second version is objectively easier to

    understand. It's clear that 'map' destructures a list and it's clear

    how both possibilities (the null list and the non-null list) are

    handled. Even if we drop the prefix/indent syntax, it's still a good

    deal clearer:

    f map = []

             [x xs -> x f i xs f map cons]

           unlist

    Actually, I like that better.

    At the very least, it seems that there's a strong argument for

    offering lambda expressions and a locals syntax.

    It's less clear that the prefix syntax is worthwhile. In particular,

    point Dan made is valid:

     > Also, what happens if a function is given too many arguments? The

    > result is very counterintuitive, and a more useful translation would

    > take into account type information.

     I'd be strongly opposed to any translation that was not a purely

    syntactic preprocessing step as otherwise you truly are complicating

    the language. At the moment, my type system can't enforce that a given

    quotation isn't given "too many" arguments because this makes no

    sense; all functions operate on stacks. The type system can enforce

    that a given quotation will try to use no more than a given number of

    arguments when it is later evaluated, and this is critical for typing

    combinators like 'infra', but that isn't helpful here. It is therefore

    probably best to rule out prefix syntax.

    - John

## William Tanksley, Jr — 2008-03-06 17:22:11

    John Nowak <john@...> wrote:

     >  Daniel Ehrenberg wrote:

    >  > Sure, there are lots of translations that we could make efficiently

    >  > and accurately with concatenative languages, but I'm not sure if all

    >  > of these are essential or beneficial to the nature of the languages.

    >  > They make things more complicated and they remove all of the nice

    >  > properties of concatenativity, which is useful in building software

    >  > because it helps you factor code.

    >  I'm not convinced concatenativity offers a huge advantage in

    >  factoring.

     Sure it does! The referential transparency alone is worth the price of

    admission -- the famous "extract method" refactoring (considered by

    many to be the first indication of "true" refactoring support in a

    tool) is merely a cut-and-paste in any editor.

     > It's easy to write code in such a way that useful chunks

    >  can't be pulled out. It's also difficult to find useful abstractions

    >  unless you have some experience. For example, I'd guess the novice

    >  programmer looking to add two lists together wouldn't accidently write

    >  zip-with.

     You're totally right, but you're talking about a different subject.

    The experienced programmer isn't going to implement zip-with either;

    the experienced programmer knows it's already implemented. The

    experienced programmer is going to implement something that hasn't

    been done before, and notice that there's some redundancy, and if the

    language allows, will factor it out. If the language makes it hard,

    he'll tolerate a lot more redundancy.

    An really good programmer will also notice *almost* redundancies --

    places where the code would be the same if only things were a little

    bit different. _That_ is the point that leads to the creation of truly

    reusable tools like zip-with -- not a magic knowledge of what sort of

    things will be reusable, but rather a repeated creation of the same

    sort of thing, and progressive refinement of that thing until it can

    actually be used in all of those cases.

    A good library is rarely produced directly from pure theory. Usually

    it's produced by painstaking experiments -- although if it's not

    backed by a good clean conceptual model it's a bad library, and

    experience won't save it.

     >  I think how factorable a language is primarily depends on its

    >  usefulness in building abstractions rather than any particular syntax.

    >  Languages with first class functions offer factorability that language

    >  like Forth don't offer.

     100% agree, by the way. The problem of factoring can be addressed in

    many dimensions.

     >  If a syntax that is non-concatenative makes it any easier to use any

    >  of the other means of factoring, then it seems to me it's worth

    >  considering.

     At this point in our understanding of concatenative languages, this is

    a pure cop-out. Yes, we don't have a concatenative Haskell yet -- but

    give us time.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-06 17:31:56

    Stevan Apter <sa@...> wrote:

     > given the decision to code in a concatenative

    >  language, i want my concatenativity neat, straight no chaser.

     Heh. I'm the same way -- of course. That's a little bit of the

    language researcher speaking rather than the true polyglot programmer,

    though. Like the chemist that I was trained as, I'm always wondering

    what would happen if I made a slightly purer extract. Well, I guess I

    skip the step of blowing the resulting extract up in my face -- that's

    the fun part of chemistry.

     >  like about joy.  in contrast to dan, i think introducing variables in

    >  any form should be resisted (although i've implemented both in my toy

    >  languages, just for the heck of it.)

     Yup.

     > moreover, i agree with something dr. tanksley has often said:

     Thank you, but I'm just Mr. Tanksley so far. I'm just starting on a

    Master's degree, so perhaps you'll be able to address me as "dread

    lord tanksley" in a while. (Is that the correct form of address?)

     > we don't yet know all the properties of

    >  these languages in their pure form, since no one (as far as i can tell

    >  from years on this list) has written any large-scale, multi-programmer,

    >  long-lived applications in any concatenative language.  many small

    >  examples, much tinkering under the hood, but nothing approaching the

    >  scale of, say, ebay.

     I'm not so sure about that. Forth has been used in enormous

    applications; see http://www.forth.com/resources/appNotes/index.html

    (and that's just one Forth company). Postscript forms one of the

    largest systems ever built (just about every computer is able to hook

    up to just about every Postscript printer almost right out of the

    box); it's not an integrated or monolithic system like eBay, but it's

    phenomenally successful at what it's designed to do.

    -Wm

## William Tanksley, Jr — 2008-03-06 17:52:24

    John Nowak <john@...> wrote:

     > Stevan Apter wrote:

    >  understand. It's clear that 'map' destructures a list and it's clear

    >  how both possibilities (the null list and the non-null list) are

    >  handled.

    >  f map = []

    >          [x xs -> x f i xs f map cons]

    >        unlist

    >  At the very least, it seems that there's a strong argument for

    >  offering lambda expressions and a locals syntax.

     Of course, what you typed there is just ambiguous, or possibly

    requires phenominal lookahead (to see if one of the alternatives

    includes a "->" token). But in no case does this functionality REQUIRE

    lambdas or locals; why should it? All you're doing is patternmatching.

    Consider the famous FunForth, an implementation of a trivial little

    patternmatcher in a tiny bit of Forth code

    (http://wiki.forthfreak.net/index.cgi?FunForth, note that there

    appears to be a display bug in the upper right corner).

     >  - John

     -Wm

## John Nowak — 2008-03-06 20:32:02

    On Mar 6, 2008, at 12:52 PM, William Tanksley, Jr wrote:

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

    >

    >> f map = []

    >>         [x xs -> x f i xs f map cons]

    >>       unlist

    >>

    >> At the very least, it seems that there's a strong argument for

    >> offering lambda expressions and a locals syntax.

    >

    > Of course, what you typed there is just ambiguous, or possibly

    > requires phenominal lookahead (to see if one of the alternatives

    > includes a "->" token).

     Indeed. There's no way I'd implement it with that syntax, Scheme

    programmer and hater of parsing that I am. The actual syntax I have

    now doesn't require lookahead.

     > But in no case does this functionality REQUIRE

    > lambdas or locals; why should it? All you're doing is patternmatching.

     I'm actively trying to avoid defining the language in terms of pattern

    matching. Here, 'unlist' is just a normal function. But yes, of course

    it doesn't require locals. You could do this as well:

        map = swap

              []

              [rot dup 2keep swap map cons]

            unlist

    Anyway, saying that "all your doing is pattern matching" gets more

    complicated when types are involved. For example, when I eventually

    introduce GADTs, sum deconstructors like 'unlist' will need to

    introduce equality constraints. It also isn't clear how a macro could

    be able to inform you if you've not covered all of the possible cases

    when matching. Therefore, any sort of general pattern matching

    facility would need to be implemented into the language proper, and

    ideally I'd like to avoid that as it complicates things.

    - John

## John Nowak — 2008-03-06 20:36:15

    On Mar 6, 2008, at 3:32 PM, John Nowak wrote:

     >> But in no case does this functionality REQUIRE

    >> lambdas or locals; why should it? All you're doing is

    >> patternmatching.

    >

    > Anyway, saying that "all your doing is pattern matching"

     Ack. Excuse me for butchering the language while quoting you.

    s/your/you're

    - John

## Daniel Ehrenberg — 2008-03-06 20:41:09

    >  Anyway, saying that "all your doing is pattern matching" gets more

    >  complicated when types are involved. For example, when I eventually

    >  introduce GADTs, sum deconstructors like 'unlist' will need to

    >  introduce equality constraints. It also isn't clear how a macro could

    >  be able to inform you if you've not covered all of the possible cases

    >  when matching. Therefore, any sort of general pattern matching

    >  facility would need to be implemented into the language proper, and

    >  ideally I'd like to avoid that as it complicates things.

    >

    >  - John

     Pattern matching only has to be built into a language when its type

    system or syntax extension system is insufficiently expressive.

    There's no good reason why a complicated, library-based pattern

    matching macro couldn't cooperate with a type system or completeness

    constraints. Factor has two pattern matching libraries implemented,

    which take different tactics but are both fairly general and

    implemented without the help of the core.

    If Fifth ultimately gets a good enough macro system, you won't need to

    worry about all of those syntax extensions that started this

    discussion until writing your standard library. Even if a macro system

    is a big step and a big thing to think about, it can make your

    language much simpler overall.

    Dan

## John Nowak — 2008-03-06 20:43:35

    On Mar 6, 2008, at 12:22 PM, William Tanksley, Jr wrote:

     >> I'm not convinced concatenativity offers a huge advantage in

    >> factoring.

    >

    > Sure it does! The referential transparency alone is worth the price of

    > admission -- the famous "extract method" refactoring (considered by

    > many to be the first indication of "true" refactoring support in a

    > tool) is merely a cut-and-paste in any editor.

     Indeed, although this partially breaks down in the presence of

    modules. Types also complicate things. For example, you can't factor

    out the 'dup i' in '[swap] dup i' unless your system has higher-rank

    polymorphism or equi-recursive types.

     >> If a syntax that is non-concatenative makes it any easier to use any

    >> of the other means of factoring, then it seems to me it's worth

    >> considering.

    >

    > At this point in our understanding of concatenative languages, this is

    > a pure cop-out.

     Fair enough.

     > Yes, we don't have a concatenative Haskell yet -- but give us time.

     I'm working on it!

    - John

## John Nowak — 2008-03-06 20:58:59

    On Mar 6, 2008, at 3:41 PM, Daniel Ehrenberg wrote:

     >> Anyway, saying that "all your doing is pattern matching" gets more

    >> complicated when types are involved. For example, when I eventually

    >> introduce GADTs, sum deconstructors like 'unlist' will need to

    >> introduce equality constraints. It also isn't clear how a macro could

    >> be able to inform you if you've not covered all of the possible cases

    >> when matching. Therefore, any sort of general pattern matching

    >> facility would need to be implemented into the language proper, and

    >> ideally I'd like to avoid that as it complicates things.

    >>

    >> - John

    >

    > Pattern matching only has to be built into a language when its type

    > system or syntax extension system is insufficiently expressive.

    > There's no good reason why a complicated, library-based pattern

    > matching macro couldn't cooperate with a type system or completeness

    > constraints.

     This seems incredibly difficult in practice. Would the macro system be

    able to to query the type system? Would it be able to find out all

    constructors of a given data type? Would it be able to check if a

    given data type requires that equality constraints be introduced when

    matching? How would it generate code that handles such a thing anyway?

    Would it need to be smart enough to translate to a pre-defined

    deconstructor? How would it be able to give errors as intelligible as

    a built-in system for subtle matters like this? If the macro were to

    introduce variables, would the specification not have to indicate how

    this interacts with linearity? Does the macro not then need to be in

    the core anyway?

     > Factor has two pattern matching libraries implemented, which take

    > different tactics but are both fairly general and implemented

    > without the help of the core.

     Yes, it's all very easy when types aren't involved.

    - John

## William Tanksley, Jr — 2008-03-06 21:49:21

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  > But in no case does this functionality REQUIRE

    >  > lambdas or locals; why should it? All you're doing is patternmatching.

    >  I'm actively trying to avoid defining the language in terms of pattern

    >  matching. Here, 'unlist' is just a normal function. But yes, of course

    >  it doesn't require locals. You could do this as well:

    >     map = swap

    >           []

    >           [rot dup 2keep swap map cons]

    >         unlist

     ...but you're still doing patternmatching. Aren't you? What am I missing?

     >  Anyway, saying that "all your doing is pattern matching" gets more

    >  complicated when types are involved.

     Oh, I agree.

     >  when matching. Therefore, any sort of general pattern matching

    >  facility would need to be implemented into the language proper, and

    >  ideally I'd like to avoid that as it complicates things.

     Well, if you're incorporating types into the language, you've got to

    handle the effects of that.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-06 22:00:14

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > Sure it does! The referential transparency alone is worth the price of

    >  > admission -- the famous "extract method" refactoring (considered by

    >  > many to be the first indication of "true" refactoring support in a

    >  > tool) is merely a cut-and-paste in any editor.

    >  Indeed, although this partially breaks down in the presence of

    >  modules.

     I don't see why... Unless you're also talking about moving the

    resulting function out of the current module, which isn't something I

    intended to imply. In fact, is that what you're talking about? It

    can't be, because in general that's impossible (the function might

    refer to some stuff that's private to the original module).

    So I definitely don't know what you mean.

     > Types also complicate things. For example, you can't factor

    >  out the 'dup i' in '[swap] dup i' unless your system has higher-rank

    >  polymorphism or equi-recursive types.

     Well, technically if your typesystem was "concatenative" you could

    factor it out. If your typesystem isn't concatenative, then the

    resulting language is no longer strictly concatenative, although it

    may indeed appear concatenative, or it may be concatenative but

    require some kind of type annotation which isn't concatenative.

    I can't criticise anyone for failing to have a concatenative type

    system, since I don't know what such a thing would look like --

    _except_ in the special case where all types are declared (as in

    StrongForth). Clearly that's not an optimal case. It seems to me that

    it _should_ be possible to construct a truly concatenative type

    system, but again, I don't know what it would look like.

     >  > Yes, we don't have a concatenative Haskell yet -- but give us time.

    >  I'm working on it!

     Yes indeed, as is Chris -- and your work is very interesting.

     >  - John

     -Wm

## Stevan Apter — 2008-03-06 22:00:18

    ack.  it's been so long since i looked at this stuff that i'd

    forgotten that 'map' in f/g and XY is an extension of the standard

    definition:  given a list of k-length lists, it applies a n-ary

    function n>=k to each element of the list.  so e.g.

        [[1 2][3 4][5 6]][+]map -> [3 7 11]

    if n>k, then e.g. f "projects":

        [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]

    i knew it looked more complex than it had to be!  anyway, i'd

    be curious how you would write this combinator (call it 'mapx').

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Wednesday, March 05, 2008 10:12 PM

    Subject: Re: [stack] sweetening concatenative syntax

    > On Mar 5, 2008, at 9:34 PM, Stevan Apter wrote:

    >

    >> ; map [jump] [each* rot => map <= swons] [pop] ifte ;

    >> ; each* => uncons <= tuck 2slip ;

    >

    > So that, versus this:

    >

    > f map = unlist:

    >   []

    >   [x xs -> (f x) (map xs f) cons]

    >

    > It seems to me that the second version is objectively easier to

    > understand. It's clear that 'map' destructures a list and it's clear

    > how both possibilities (the null list and the non-null list) are

    > handled. Even if we drop the prefix/indent syntax, it's still a good

    > deal clearer:

    >

    > f map = []

    >         [x xs -> x f i xs f map cons]

    >       unlist

    >

    > Actually, I like that better.

    >

    > At the very least, it seems that there's a strong argument for

    > offering lambda expressions and a locals syntax.

    >

    > It's less clear that the prefix syntax is worthwhile. In particular,

    > point Dan made is valid:

    >

    >> Also, what happens if a function is given too many arguments? The

    >> result is very counterintuitive, and a more useful translation would

    >> take into account type information.

    >

    > I'd be strongly opposed to any translation that was not a purely

    > syntactic preprocessing step as otherwise you truly are complicating

    > the language. At the moment, my type system can't enforce that a given

    > quotation isn't given "too many" arguments because this makes no

    > sense; all functions operate on stacks. The type system can enforce

    > that a given quotation will try to use no more than a given number of

    > arguments when it is later evaluated, and this is critical for typing

    > combinators like 'infra', but that isn't helpful here. It is therefore

    > probably best to rule out prefix syntax.

    >

    > - John

    >

## John Nowak — 2008-03-06 22:09:04

    On Mar 6, 2008, at 4:49 PM, William Tanksley, Jr wrote:

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

    >> William Tanksley, Jr wrote:

    >>> But in no case does this functionality REQUIRE

    >>> lambdas or locals; why should it? All you're doing is

    >>> patternmatching.

    >

    >> I'm actively trying to avoid defining the language in terms of

    >> pattern

    >> matching. Here, 'unlist' is just a normal function. But yes, of

    >> course

    >> it doesn't require locals. You could do this as well:

    >>    map = swap

    >>          []

    >>          [rot dup 2keep swap map cons]

    >>        unlist

    >

    > ...but you're still doing patternmatching. Aren't you? What am I

    > missing?

     'unlist' is just a normal function that gets defined as a result of

    declaring the 'list' data type:

        unlist :: A {b} [A -> C] [A b {b} -> C] -> C

    This is different from general pattern matching as there's no way to

    match on particular values and "matching" here is guaranteed to be

    constant time. Alternatively, it isn't pattern matching as it doesn't

    involve patterns. The fact that it *looks* like pattern matching when

    lambda expressions are used is a very nice thing.

     >

     - John

## Stevan Apter — 2008-03-06 22:09:14

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, March 06, 2008 12:31 PM

    Subject: Re: [stack] sweetening concatenative syntax

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

    >> given the decision to code in a concatenative

    >>  language, i want my concatenativity neat, straight no chaser.

    >

    > Heh. I'm the same way -- of course. That's a little bit of the

    > language researcher speaking rather than the true polyglot programmer,

    > though. Like the chemist that I was trained as, I'm always wondering

    > what would happen if I made a slightly purer extract. Well, I guess I

    > skip the step of blowing the resulting extract up in my face -- that's

    > the fun part of chemistry.

    >

    >>  like about joy.  in contrast to dan, i think introducing variables in

    >>  any form should be resisted (although i've implemented both in my toy

    >>  languages, just for the heck of it.)

    >

    > Yup.

    >

    >> moreover, i agree with something dr. tanksley has often said:

    >

    > Thank you, but I'm just Mr. Tanksley so far. I'm just starting on a

    > Master's degree, so perhaps you'll be able to address me as "dread

    > lord tanksley" in a while. (Is that the correct form of address?)

    "your royal hic-haec-hoc-itude?"

    >

    >> we don't yet know all the properties of

    >>  these languages in their pure form, since no one (as far as i can tell

    >>  from years on this list) has written any large-scale, multi-programmer,

    >>  long-lived applications in any concatenative language.  many small

    >>  examples, much tinkering under the hood, but nothing approaching the

    >>  scale of, say, ebay.

    >

    > I'm not so sure about that. Forth has been used in enormous

    > applications; see http://www.forth.com/resources/appNotes/index.html

    > (and that's just one Forth company). Postscript forms one of the

    > largest systems ever built (just about every computer is able to hook

    > up to just about every Postscript printer almost right out of the

    > box); it's not an integrated or monolithic system like eBay, but it's

    > phenomenally successful at what it's designed to do.

    i'm not sure either.  i've often thought it would be useful to come

    up with something like the complement of fred brook's no-silver-

    bullet analysis:  a list of the properties which make an application

    "hard" -- for a programming language, for programmers, for companies,

    &c.  e.g. big data, need for speed, fault-tolerance, life-and-death

    consequences of bugs, rapidly changing demands, need to be shrink-

    wrapped for users (a.k.a. The Enemy), &c.  so an app can be hard

    in some dimensions, easy in others, &c.  and out of that you get

    consensus around a maxim i've always found somewhat depressing:

    use the right tool for the job.

    >

    > -Wm

    >

## Stevan Apter — 2008-03-06 22:10:40

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, March 06, 2008 12:22 PM

    Subject: Re: [stack] sweetening concatenative syntax

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

    >>  Daniel Ehrenberg wrote:

    >>  > Sure, there are lots of translations that we could make efficiently

    >>  > and accurately with concatenative languages, but I'm not sure if all

    >>  > of these are essential or beneficial to the nature of the languages.

    >>  > They make things more complicated and they remove all of the nice

    >>  > properties of concatenativity, which is useful in building software

    >>  > because it helps you factor code.

    >

    >>  I'm not convinced concatenativity offers a huge advantage in

    >>  factoring.

    >

    > Sure it does! The referential transparency alone is worth the price of

    > admission -- the famous "extract method" refactoring (considered by

    > many to be the first indication of "true" refactoring support in a

    > tool) is merely a cut-and-paste in any editor.

    >

    >> It's easy to write code in such a way that useful chunks

    >>  can't be pulled out. It's also difficult to find useful abstractions

    >>  unless you have some experience. For example, I'd guess the novice

    >>  programmer looking to add two lists together wouldn't accidently write

    >>  zip-with.

    >

    > You're totally right, but you're talking about a different subject.

    > The experienced programmer isn't going to implement zip-with either;

    > the experienced programmer knows it's already implemented. The

    > experienced programmer is going to implement something that hasn't

    > been done before, and notice that there's some redundancy, and if the

    > language allows, will factor it out. If the language makes it hard,

    > he'll tolerate a lot more redundancy.

    >

    > An really good programmer will also notice *almost* redundancies --

    > places where the code would be the same if only things were a little

    > bit different. _That_ is the point that leads to the creation of truly

    > reusable tools like zip-with -- not a magic knowledge of what sort of

    > things will be reusable, but rather a repeated creation of the same

    > sort of thing, and progressive refinement of that thing until it can

    > actually be used in all of those cases.

    >

    > A good library is rarely produced directly from pure theory. Usually

    > it's produced by painstaking experiments -- although if it's not

    > backed by a good clean conceptual model it's a bad library, and

    > experience won't save it.

    these are very useful and very deep insights.

    >

    >>  I think how factorable a language is primarily depends on its

    >>  usefulness in building abstractions rather than any particular syntax.

    >>  Languages with first class functions offer factorability that language

    >>  like Forth don't offer.

    >

    > 100% agree, by the way. The problem of factoring can be addressed in

    > many dimensions.

    >

    >>  If a syntax that is non-concatenative makes it any easier to use any

    >>  of the other means of factoring, then it seems to me it's worth

    >>  considering.

    >

    > At this point in our understanding of concatenative languages, this is

    > a pure cop-out. Yes, we don't have a concatenative Haskell yet -- but

    > give us time.

    >

    >>  - John

    >

    > -Wm

    >

## Stevan Apter — 2008-03-06 22:12:52

    >

    > if n>k, then e.g. f "projects":

    >

    >    [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]

     sorry - that should be:

        [[1][3 4][5 6 7]][+ *] map -> [[1 + *][7 *] 18]

    as i said, it's been a while.

## John Nowak — 2008-03-06 22:20:19

    On Mar 6, 2008, at 5:00 PM, William Tanksley, Jr wrote:

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

    >

    >> William Tanksley, Jr wrote:

    >>

    >>> Sure it does! The referential transparency alone is worth the

    >>> price of

    >>> admission -- the famous "extract method" refactoring (considered by

    >>> many to be the first indication of "true" refactoring support in a

    >>> tool) is merely a cut-and-paste in any editor.

    >>

    >> Indeed, although this partially breaks down in the presence of

    >> modules.

    >

    > I don't see why... Unless you're also talking about moving the

    > resulting function out of the current module, which isn't something I

    > intended to imply. In fact, is that what you're talking about?

     Yes. It isn't a particularly interesting observation.

     >> Types also complicate things. For example, you can't factor

    >> out the 'dup i' in '[swap] dup i' unless your system has higher-rank

    >> polymorphism or equi-recursive types.

    >

    > Well, technically if your typesystem was "concatenative" you could

    > factor it out.

     This is true. The original type system I had was concatenative (well,

    really "compositional" is the correct term). Unfortunately, this

    property gets lost quite quickly as you expand the power of the type

    system. The only reason the original system was compositional was

    because it would refuse to accept things like "[swap] dup i" as all

    variables were non-generic and you'd hit an occurs check no matter

    what order you attempted it in. At the moment, it seems that a truly

    compositional type system imposes too many limitations. If there are

    ways around this I've not discovered them yet.

     > If your typesystem isn't concatenative, then the resulting language

    > is no longer strictly concatenative

     This all depends on your definition of concatenative. The language is

    still expressed in terms of the functional forms of composition and

    quotation. Concatenation still denotes composition. The limitation is

    that you cannot compose functions in any order. This doesn't seem to

    be a problem in practice, although it certainly is unfortunate.

     > I can't criticise anyone for failing to have a concatenative type

    > system, since I don't know what such a thing would look like --

     I've been meaning to write up how to perform inference for a

    compositional type system. If anyone is interested I'll bump this up

    in my priority queue.

    - John

## William Tanksley, Jr — 2008-03-06 22:36:13

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  > ...but you're still doing patternmatching. Aren't you? What am I

    >  > missing?

    >  'unlist' is just a normal function that gets defined as a result of

    >  declaring the 'list' data type:

    >     unlist :: A {b} [A -> C] [A b {b} -> C] -> C

     Sorry, I have no idea how to read this. It's clearly a type signature,

    but I don't know any such languages more recent than ML (well, I know

    a little Scala), and that only from a few college assignments.

    I assumed that it was somewhat like 'i' in Joy (due to the name

    'unlist' being similar to Joy's technical term 'dequote').

     >  This is different from general pattern matching as there's no way to

    >  match on particular values and "matching" here is guaranteed to be

    >  constant time.

     Okay. I don't know of any pattern matching that doesn't work this way

    (my knowledge of the modern functional languages is highly pathetic).

     > Alternatively, it isn't pattern matching as it doesn't

    >  involve patterns. The fact that it *looks* like pattern matching when

    >  lambda expressions are used is a very nice thing.

     Okay. I don't know what your example meant, then. Suffice it to say

    that I'm just plain confused.

     >  - John

     -Wm

## John Nowak — 2008-03-06 22:40:51

    On Mar 6, 2008, at 5:00 PM, Stevan Apter wrote:

     > ack.  it's been so long since i looked at this stuff that i'd

    > forgotten that 'map' in f/g and XY is an extension of the standard

    > definition:  given a list of k-length lists, it applies a n-ary

    > function n>=k to each element of the list.  so e.g.

    >

    >    [[1 2][3 4][5 6]][+]map -> [3 7 11]

    >

    > if n>k, then e.g. f "projects":

    >

    >    [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]

    >

    > i knew it looked more complex than it had to be!  anyway, i'd

    > be curious how you would write this combinator (call it 'mapx').

     (I'm only going to handle the first case of 'map' above. There's no

    way for the type system to handle the second.)

    Here's one way, writing other highly useful combinators as we go:

    f map     = [ ] [x xs -> x f i xs f map cons] unlist

    z f foldl = [z] [x xs -> xs z x f i f foldl] unlist

    foldl1    = [uncons swap] dip fold

    mapx      = [foldl1] compose map

    Here's another, this time pointfree. I stole the definition of 'foldl'

    from Cat; there may be a better one. The 'pa' function is partial

    application (a [B a -> C] -> [B -> C]). Note that this version of map

    is tail recursive, unlike the above version:

    foldl  = swapd [dip] pa [uncons swap] swap compose [null? not] while

    foldl1 = [uncons swap] dip fold

    rmap   = null swap [cons] compose fold

    map    = rmap reverse

    mapx   = [foldl1] compose map

    - John

## John Nowak — 2008-03-06 22:52:19

    On Mar 6, 2008, at 5:36 PM, William Tanksley, Jr wrote:

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

    >> William Tanksley, Jr wrote:

    >>> ...but you're still doing patternmatching. Aren't you? What am I

    >>> missing?

    >> 'unlist' is just a normal function that gets defined as a result of

    >> declaring the 'list' data type:

    >>    unlist :: A {b} [A -> C] [A b {b} -> C] -> C

    >

    > Sorry, I have no idea how to read this. It's clearly a type signature,

    > but I don't know any such languages more recent than ML (well, I know

    > a little Scala), and that only from a few college assignments.

    >

    > I assumed that it was somewhat like 'i' in Joy (due to the name

    > 'unlist' being similar to Joy's technical term 'dequote').

     I explained what 'unlist' does in an earlier email. You may've missed

    it.

    The 'unlist' function is not like 'i' in Joy. Joy's 'i' has the

    following type:

        i :: A [A -> B] -> B

    In other words, given a stack and a function that transforms that

    stack to another stack, it yields the transformed stack.

    What 'unlist' does is take three arguments. The first is a list. The

    second is a function that says what to do if that list is null. The

    the third is a function that acts on the list after is has been

    unconsed if it is not null. The 'unlist' function is called a sum

    deconstructor as lists are sum types (they're either a "null" or a

    "cons").

    We can use 'unlist' to write the usual functions:

        uncons = [error] [] unlist

        head   = [error] [pop] unlist

        tail   = [error] [popd] unlist

        null?  = [true] [cons false] unlist

    - John

## John Nowak — 2008-03-06 22:58:08

    On Mar 6, 2008, at 5:52 PM, John Nowak wrote:

     >    null?  = [true] [cons false] unlist

     Wrong!

        null? :: {a} -> {a} bool

        null? = [null true] [cons false] unlist

    Better. Alternatively, if you *don't* want to keep the list around:

        null? :: {a} -> bool

        null? = [true] [pop pop false] unlist

    The first version makes a lot more sense in a linear language. The

    unconsing and consing can also be easily optimized out that way. Keep

    in mind that you never really use 'null?' if you have 'unlist' anyway.

    - John

## Stevan Apter — 2008-03-06 23:12:28

    forget about the partial application case.  what i want in my toolkit

    is a single combinator 'map' which takes an n-ary function and applies

    it to each of a list of length-n lists.  not map1, map2, ... for each

    case.  is that what's going on here?  or does typing rule out having

    such a combinator?

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, March 06, 2008 5:40 PM

    Subject: Re: [stack] sweetening concatenative syntax

    >

    > On Mar 6, 2008, at 5:00 PM, Stevan Apter wrote:

    >

    >> ack.  it's been so long since i looked at this stuff that i'd

    >> forgotten that 'map' in f/g and XY is an extension of the standard

    >> definition:  given a list of k-length lists, it applies a n-ary

    >> function n>=k to each element of the list.  so e.g.

    >>

    >>    [[1 2][3 4][5 6]][+]map -> [3 7 11]

    >>

    >> if n>k, then e.g. f "projects":

    >>

    >>    [[1][3 4][5 6 7]][+ *][map] -> [[1 + *][7 *] 18]

    >>

    >> i knew it looked more complex than it had to be!  anyway, i'd

    >> be curious how you would write this combinator (call it 'mapx').

    >

    > (I'm only going to handle the first case of 'map' above. There's no

    > way for the type system to handle the second.)

    >

    > Here's one way, writing other highly useful combinators as we go:

    >

    > f map     = [ ] [x xs -> x f i xs f map cons] unlist

    > z f foldl = [z] [x xs -> xs z x f i f foldl] unlist

    > foldl1    = [uncons swap] dip fold

    > mapx      = [foldl1] compose map

    >

    > Here's another, this time pointfree. I stole the definition of 'foldl'

    > from Cat; there may be a better one. The 'pa' function is partial

    > application (a [B a -> C] -> [B -> C]). Note that this version of map

    > is tail recursive, unlike the above version:

    >

    > foldl  = swapd [dip] pa [uncons swap] swap compose [null? not] while

    > foldl1 = [uncons swap] dip fold

    > rmap   = null swap [cons] compose fold

    > map    = rmap reverse

    > mapx   = [foldl1] compose map

    >

    > - John

    >

## John Nowak — 2008-03-06 23:38:16

    On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:

     > forget about the partial application case.  what i want in my toolkit

    > is a single combinator 'map' which takes an n-ary function and applies

    > it to each of a list of length-n lists.

     Ah, I think maybe there's some confusion here over what we mean by

    "list". (Yes, really!) In Joy, lists, stacks, and functions are all

    magically the same thing. I assume it's similar in XY as well. In

    Fifth, lists, stacks, and functions are all different things. This is

    just one more example of the endless complication that types introduce.

    The 'mapx' function I gave before took a list of lists and a function

    of type 'a b -> b'. In other words, the function is restricted to

    taking only two arguments as is standard for the 'fold' combinator.

    It sounds to me like what you're describing is a function that takes a

    list of *stacks* and applies an n-ary function to each stack in the

    list. This is doable, where 'map' below is the "normal" map you'd find

    in a language like ML, Haskell, or Fifth:

        mapx :: {(Stack A)} [A -> B] -> {(Stack B)}

        mapx = quote [infra] compose map

    There are some limitations. In particular, all stacks in the list need

    to be of the same type. Due to how row variables in stack types must

    get instantiated (the row variables are stripped out), all stacks must

    have the same number of elements and elements in corresponding

    positions in each stack must be of the same type.

    This limitation probably isn't too onerous in practice as I can't

    imagine the use case for mapping over a list of elements of various

    types. Note that when I say all elements must be the same type, I

    don't mean that they must all be ints or that they must all be

    strings. You can always introduce sum types for handling any

    combination of types you want. The only requirement is that you

    explicitly wrap up all types into the sum type with the appropriate

    constructors. A sum type deconstructor ensures that you handle all

    possible cases when you translate back to the "raw" types.

    - John

## Christopher Diggins — 2008-03-06 23:41:07

    On Thu, Mar 6, 2008 at 6:12 PM, Stevan Apter <sa@...> wrote:

     > forget about the partial application case. what i want in my toolkit

    > is a single combinator 'map' which takes an n-ary function and applies

    > it to each of a list of length-n lists. not map1, map2, ... for each

    > case. is that what's going on here? or does typing rule out having

    > such a combinator?

     It really has to do with how you structure your lists. In Cat this is

    feasible if your list is a lists of functions.

    define mapN { [apply] swap compose [quote] compose map }

    [[1 2] [3 4] [5 6]] list [+] mapN => [[3][7][11]]

    [[1] [2] [3] [4]] list [2 *] mapN => [[2][4][6][8]] //

    Cat however has untyped lists, so there is some cheating going on at

    the type-level, but this would be feasible with typed lists as well.

    The only serious restriction here AFAICS is that your function has to

    produce a single result even though it can consume n arguments.

    - Christopher

## William Tanksley, Jr — 2008-03-06 23:56:16

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  I explained what 'unlist' does in an earlier email. You may've missed

    >  it.

     Sorry, sure did.

     >  What 'unlist' does is take three arguments. The first is a list. The

    >  second is a function that says what to do if that list is null. The

    >  the third is a function that acts on the list after is has been

    >  unconsed if it is not null. The 'unlist' function is called a sum

    >  deconstructor as lists are sum types (they're either a "null" or a

    >  "cons").

     Cool! So 'unlist' does exactly what FunForth does (well, it's

    typesafe, unlike FunForth).

    I suppose I don't get why lambdas help with that, then. I assumed you

    were talking about pattern matching, since lambdas there could fit

    into the pattern, therefore helping you notate what is being

    extracted. But if you're only disassembling the parts of a structure,

    I don't see why you have to give the parts names.

     >  - John

     -Wm

## John Nowak — 2008-03-07 00:09:44

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

     >> What 'unlist' does is take three arguments. The first is a list. The

    >> second is a function that says what to do if that list is null. The

    >> the third is a function that acts on the list after is has been

    >> unconsed if it is not null. The 'unlist' function is called a sum

    >> deconstructor as lists are sum types (they're either a "null" or a

    >> "cons").

    >

    > Cool! So 'unlist' does exactly what FunForth does (well, it's

    > typesafe, unlike FunForth).

    >

    > I suppose I don't get why lambdas help with that, then. I assumed you

    > were talking about pattern matching, since lambdas there could fit

    > into the pattern, therefore helping you notate what is being

    > extracted. But if you're only disassembling the parts of a structure,

    > I don't see why you have to give the parts names.

     Ah, sorry if I've confused you. Lambdas don't have anything to do with

    it; they just let you write it in a way that makes it look more like

    pattern matching. You can write it without variables if you prefer.

    You can even write it with just one variable which is actually nicer:

        f map = []

                [xs -> f i xs f map cons]

              unlist

    Since we're not binding the element below 'xs' the element is simply

    left on the stack.

    - John

## William Tanksley, Jr — 2008-03-07 01:01:40

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > Cool! So 'unlist' does exactly what FunForth does (well, it's

    >  > typesafe, unlike FunForth).

    >  > I suppose I don't get why lambdas help with that, then. I assumed you

    >  > were talking about pattern matching, since lambdas there could fit

    >  > into the pattern, therefore helping you notate what is being

    >  > extracted. But if you're only disassembling the parts of a structure,

    >  > I don't see why you have to give the parts names.

    >  Ah, sorry if I've confused you.

     No prob -- my ignorance is not your responsibility.

     > Lambdas don't have anything to do with

    > it; they just let you write it in a way that makes it look more like

    > pattern matching. You can write it without variables if you prefer.

    > You can even write it with just one variable which is actually nicer:

    >     f map = []

    >             [xs -> f i xs f map cons]

    >           unlist

     Okay, so the challenge is to write that entirely without variables

    (i.e. without the benefit of lambdas). Let's try. I'll prototype it

    with my stack-shuffles, 'cause I like 'em.

    \ f = a function, x = car, s = cdr, y=x f i

    map = [] [ fxs--sfxf i sfy--ysf map cons ] unlist

    Okay, translate the shuffle notation to familiar operators:

    map = [] [ bury over i rot map cons ] unlist

    (I define 'bury' as the inverse of 'rot'. Forth calls it '-rot'. I

    prefer shuffles when possible, since a shuffle is essentially a

    mnemonic name for a series of stack operators, but let's go with what

    most people expect.)

    Arguably no worse than yours; the body of my definition contains six

    words, matching yours if we don't count your lambda and its variable

    (beating it otherwise). I consider it an advantage that mine uses only

    verbs, while yours mixes nouns and verbs.

     >  - John

     -Wm

## John Nowak — 2008-03-07 02:06:04

    On Mar 6, 2008, at 8:01 PM, William Tanksley, Jr wrote:

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

    >

    >> Lambdas don't have anything to do with

    >> it; they just let you write it in a way that makes it look more like

    >> pattern matching. You can write it without variables if you prefer.

    >> You can even write it with just one variable which is actually nicer:

    >>

    >>    f map = []

    >>            [xs -> f i xs f map cons]

    >>          unlist

    >

    > Okay, so the challenge is to write that entirely without variables

    > (i.e. without the benefit of lambdas). Let's try.

     You must've missed my response to you earlier where I gave this

    translation:

        map = swap

              []

              [rot dup 2dip swap map cons]

            unlist

     > map = [] [ bury over i rot map cons ] unlist

     Small point: You forgot the initial swap to put the list on top of the

    stack. The type system would've saved you of course.

     > Arguably no worse than yours; the body of my definition contains six

    > words, matching yours if we don't count your lambda and its variable

    > (beating it otherwise).

     This seems like a poor way of measuring how easy it is to read and

    write code. At least in my case, I know I wrote the pointful version

    in about 15 seconds. It took me over a minute to write the pointfree

    version. (Perhaps I just need more practice.) I also think the

    pointful version is easier to read, although we can certainly disagree.

    - John

## John Nowak — 2008-03-07 02:33:54

    On Mar 6, 2008, at 9:06 PM, John Nowak wrote:

     > You must've missed my response to you earlier where I gave this

    > translation:

    >

    >    map = swap

    >          []

    >          [rot dup 2dip swap map cons]

    >        unlist

    >

    >> map = [] [ bury over i rot map cons ] unlist

    >

    > Small point: You forgot the initial swap to put the list on top of the

    > stack. The type system would've saved you of course.

     Oh crap. We're both wrong. In particular, if the list is null, neither

    of us remembered to pop the function. I also put in a swap for no

    reason. We both forgot to place a null back on top in the empty case

    too. Oi!

    This should work:

        map = swap                    ; put the list on top

              [pop null]              ; remove 'f', restore the null

              [rot dup 2dip map cons] ; i swear this works now

            unlist

    Perhaps this series of errors is just another argument for lambda

    expressions and types. :) Considering the multitude of errors, I'd say

    it's a pretty strong one...

    - John

## Stevan Apter — 2008-03-07 15:11:25

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, March 06, 2008 6:38 PM

    Subject: Re: [stack] sweetening concatenative syntax

    >

    > On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:

    >

    >> forget about the partial application case.  what i want in my toolkit

    >> is a single combinator 'map' which takes an n-ary function and applies

    >> it to each of a list of length-n lists.

    >

    > Ah, I think maybe there's some confusion here over what we mean by

    > "list". (Yes, really!) In Joy, lists, stacks, and functions are all

    > magically the same thing. I assume it's similar in XY as well. In

    > Fifth, lists, stacks, and functions are all different things. This is

    > just one more example of the endless complication that types introduce.

    this is the sort of thing that makes me type-averse.  i understand that

    proponents of types have their reasons, but i can't help thinking that it's

    one of those things that language-designers like more than language-users.

    one of the beauties of joy is that quotations are lists are programs, and

    in some variants, are stacks.

    is there really no way to reconcile typing with this elegant simplification?

    >

    > The 'mapx' function I gave before took a list of lists and a function

    > of type 'a b -> b'. In other words, the function is restricted to

    > taking only two arguments as is standard for the 'fold' combinator.

    >

    > It sounds to me like what you're describing is a function that takes a

    > list of *stacks* and applies an n-ary function to each stack in the

    > list. This is doable, where 'map' below is the "normal" map you'd find

    > in a language like ML, Haskell, or Fifth:

    >

    >    mapx :: {(Stack A)} [A -> B] -> {(Stack B)}

    >    mapx = quote [infra] compose map

    >

    > There are some limitations. In particular, all stacks in the list need

    > to be of the same type. Due to how row variables in stack types must

    > get instantiated (the row variables are stripped out), all stacks must

    > have the same number of elements and elements in corresponding

    > positions in each stack must be of the same type.

    >

    > This limitation probably isn't too onerous in practice as I can't

    > imagine the use case for mapping over a list of elements of various

    > types. Note that when I say all elements must be the same type, I

    > don't mean that they must all be ints or that they must all be

    > strings. You can always introduce sum types for handling any

    > combination of types you want. The only requirement is that you

    > explicitly wrap up all types into the sum type with the appropriate

    > constructors. A sum type deconstructor ensures that you handle all

    > possible cases when you translate back to the "raw" types.

    >

    > - John

    >

## William Tanksley, Jr — 2008-03-07 15:20:38

    Stevan Apter <sa@...> wrote:

     >  this is the sort of thing that makes me type-averse.  i understand that

    >  proponents of types have their reasons, but i can't help thinking that it's

    >  one of those things that language-designers like more than language-users.

    >  one of the beauties of joy is that quotations are lists are programs, and

    >  in some variants, are stacks.

     There are two good things about types.

    The first is that, implemented right, they can help you write code

    (for example, Ada's attributes, c.f. e.g.

    http://www.csupomona.edu/reference/ada/rm95html-1.0/rm9x-A-05-03.html).

    Most people who design statically typed languages don't bother

    thinking of how types could be helpful beyond simple static

    polymorphism (or worse, overloading).

    The second is that they help clarify our understanding of what a

    language is doing. If an operation in a language cannot yet be typed,

    we do not have a complete idea of what it's doing yet.

    I'm not a static typing maniac, but I'm strongly in favor of figuring

    out static types, and I've often enjoyed using static languages.

    -Wm

## Stevan Apter — 2008-03-07 15:30:48

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, March 07, 2008 10:20 AM

    Subject: Re: [stack] sweetening concatenative syntax

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

    >>  this is the sort of thing that makes me type-averse.  i understand that

    >>  proponents of types have their reasons, but i can't help thinking that it's

    >>  one of those things that language-designers like more than language-users.

    >>  one of the beauties of joy is that quotations are lists are programs, and

    >>  in some variants, are stacks.

    >

    > There are two good things about types.

    >

    > The first is that, implemented right, they can help you write code

    > (for example, Ada's attributes, c.f. e.g.

    > http://www.csupomona.edu/reference/ada/rm95html-1.0/rm9x-A-05-03.html).

    > Most people who design statically typed languages don't bother

    > thinking of how types could be helpful beyond simple static

    > polymorphism (or worse, overloading).

    >

    > The second is that they help clarify our understanding of what a

    > language is doing. If an operation in a language cannot yet be typed,

    > we do not have a complete idea of what it's doing yet.

    but if the language is incapable of expressing a well-formed thought

    because the type-system prevents that, then so much the worse for typing.

    that is, i start with clear and distinct idea of the algorithm and its

    data-structures, and then must work around limits on expressibility created

    by the type-system ... ?

    >

    > I'm not a static typing maniac, but I'm strongly in favor of figuring

    > out static types, and I've often enjoyed using static languages.

    >

    > -Wm

    >

## Christopher Diggins — 2008-03-07 15:40:21

    On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <sa@...> wrote:

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

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

    > To: <concatenative@yahoogroups.com>

    > Sent: Thursday, March 06, 2008 6:38 PM

    > Subject: Re: [stack] sweetening concatenative syntax

    >

    > >

    > > On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:

    > >

    > >> forget about the partial application case. what i want in my toolkit

    > >> is a single combinator 'map' which takes an n-ary function and applies

    > >> it to each of a list of length-n lists.

    > >

    > > Ah, I think maybe there's some confusion here over what we mean by

    > > "list". (Yes, really!) In Joy, lists, stacks, and functions are all

    > > magically the same thing. I assume it's similar in XY as well. In

    > > Fifth, lists, stacks, and functions are all different things. This is

    > > just one more example of the endless complication that types introduce.

     Well you can design a statically language that makes a list synonymous

    with the function that generates it. In other words: lists are

    functions. I have been experimenting with this approach in Cat, and it

    seems to work well.

     > this is the sort of thing that makes me type-averse. i understand that

    > proponents of types have their reasons, but i can't help thinking that it's

    > one of those things that language-designers like more than language-users.

     Many language users like static type systems because it means that a

    huge chunk of program verification can be done at compile-time. In

    other words faster debugging.

     > one of the beauties of joy is that quotations are lists are programs, and

    > in some variants, are stacks.

     Yes I agree.

     > is there really no way to reconcile typing with this elegant simplification?

     I believe we can.

    - Christopher

## Stevan Apter — 2008-03-07 15:52:31

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, March 07, 2008 10:40 AM

    Subject: Re: [stack] sweetening concatenative syntax

    > On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <sa@...> wrote:

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

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

    >> To: <concatenative@yahoogroups.com>

    >> Sent: Thursday, March 06, 2008 6:38 PM

    >> Subject: Re: [stack] sweetening concatenative syntax

    >>

    >> >

    >> > On Mar 6, 2008, at 6:12 PM, Stevan Apter wrote:

    >> >

    >> >> forget about the partial application case. what i want in my toolkit

    >> >> is a single combinator 'map' which takes an n-ary function and applies

    >> >> it to each of a list of length-n lists.

    >> >

    >> > Ah, I think maybe there's some confusion here over what we mean by

    >> > "list". (Yes, really!) In Joy, lists, stacks, and functions are all

    >> > magically the same thing. I assume it's similar in XY as well. In

    >> > Fifth, lists, stacks, and functions are all different things. This is

    >> > just one more example of the endless complication that types introduce.

    >

    > Well you can design a statically language that makes a list synonymous

    > with the function that generates it. In other words: lists are

    > functions. I have been experimenting with this approach in Cat, and it

    > seems to work well.

    >

    >> this is the sort of thing that makes me type-averse. i understand that

    >> proponents of types have their reasons, but i can't help thinking that it's

    >> one of those things that language-designers like more than language-users.

    >

    > Many language users like static type systems because it means that a

    > huge chunk of program verification can be done at compile-time. In

    > other words faster debugging.

    i understand, although for various reasons i am not one of those users.

    mainly though, it seems to me that most of the programming errors i make

    are not the kind that would be caught by static type-checking.

    over the years i've come to believe that simplicity and low code-mass

    in the language implementation is the best way to reduce the worst kind

    of errors in end-user code.  i can't help but notice how frequently haskell

    and ocaml programmers (at least, those without black-belts) struggle with

    their respective type-systems.  the ramification of type-theories into

    so many alternative approaches alone should indicate that something is

    amiss.

    >

    >> one of the beauties of joy is that quotations are lists are programs, and

    >> in some variants, are stacks.

    >

    > Yes I agree.

    >

    >> is there really no way to reconcile typing with this elegant simplification?

    >

    > I believe we can.

    excelsior.

    >

    > - Christopher

    >

## Christopher Diggins — 2008-03-07 16:02:37

    > over the years i've come to believe that simplicity and low code-mass

    > in the language implementation is the best way to reduce the worst kind

    > of errors in end-user code. i can't help but notice how frequently haskell

    > and ocaml programmers (at least, those without black-belts) struggle with

    > their respective type-systems.

     And those with black-belts are so proud of themselves they think

    trivial software is worth publishing in academic journals. Anyway, for

    me happiness is in between the two. I like C# for this reason, as must

    or little type safety as you want.

     > the ramification of type-theories into

    > so many alternative approaches alone should indicate that something is

    > amiss.

     I don't quite follow what you are getting at

    On another note, I would really appreciate a list of "must-have" array

    primitives. Which ones need to be implemented in a language (so that

    they can be leverage by optimizers) and which ones can be defined as

    libraries. The Heron 0.19 release is around the corner, and I would

    like a happy Stevan Apter on my side. :-)

    I have also been wondering what it means to add a vector of two

    elements to a vector of four elements which I believe you mentioned in

    an earlier post. In my little type-safe world, this is undefined.

    Christopher Diggins

## William Tanksley, Jr — 2008-03-07 16:19:22

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

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

    > >> Lambdas don't have anything to do with

    >  >> it; they just let you write it in a way that makes it look more like

    >  >> pattern matching. You can write it without variables if you prefer.

    >  >> You can even write it with just one variable which is actually nicer:

    >  >>    f map = []

    >  >>            [xs -> f i xs f map cons]

    >  >>          unlist

    >  > Okay, so the challenge is to write that entirely without variables

    >  > (i.e. without the benefit of lambdas). Let's try.

    >  You must've missed my response to you earlier where I gave this

    >  translation:

    >     map = swap

    >           []

    >           [rot dup 2dip swap map cons]

    >         unlist

     No, I saw it -- actually, I saw one with a '2keep', so perhaps I

    missed the one you're showing. There are 2 reasons I wrote my own: 1.

    I wanted to accept your challenge; 2. I don't like words with numbers

    in them (2keep? I don't know what that does).

     >  > map = [] [ bury over i rot map cons ] unlist

    >  Small point: You forgot the initial swap to put the list on top of the

    >  stack. The type system would've saved you of course.

     I didn't forget it; I was imitating your lambda code, in which the

    list is already on top of the stack. Isn't that what "xs -> f i"

    implies? So is your lambda code also wrong?

    Anyhow, that makes my version look like this:

    map = [drop null] [ swap bury over i rot map cons ] unlist

    Or, using a shuffle:

    map = [drop null] [ fsx--sfxf i rot map cons ] unlist

     >  > Arguably no worse than yours; the body of my definition contains six

    >  > words, matching yours if we don't count your lambda and its variable

    >  > (beating it otherwise).

    >  This seems like a poor way of measuring how easy it is to read and

    >  write code. At least in my case, I know I wrote the pointful version

    >  in about 15 seconds.

     This is moving the goalposts. When you posted the challenge you didn't

    mention anything about programming time; all you did was post a few

    different variants, and then you posted one that you said was "better"

    (the one with only a single lambda variable). The only difference I

    see is that the single-variable one is shorter, so I assumed shortness

    was your criteria.

    I didn't time my coding, and I didn't know that was the goal, so I've

    got no way to compete here.

    Not that speed competition would be fair -- I've never seen your

    'unlist' API anyhow, and now it appears you're doing something tricky

    or incorrect in your example code (by putting the list on top).

     > It took me over a minute to write the pointfree

    >  version. (Perhaps I just need more practice.) I also think the

    >  pointful version is easier to read, although we can certainly disagree.

     Perhaps you find it easier, but there's objective reason why it

    shouldn't be easier. The point-free version is linear and has fewer

    symbols. (Your point-free version -- the '2dip' one -- is okay, but

    IMO anytime you play with 'dip' you introduce reading difficulty.)

     > Perhaps this series of errors is just another argument for lambda

    > expressions and types. :) Considering the multitude of errors, I'd say

    > it's a pretty strong one...

     Considering that all your lambda implementations had the same errors,

    I don't see how that applies. The specification was unclear, we both

    misunderstood, and produced correct programs for the wrong API.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-07 16:36:27

    Stevan Apter <sa@...> wrote:

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

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

    >  >>  this is the sort of thing that makes me type-averse.  i understand that

    >  >>  proponents of types have their reasons, but i can't help thinking that it's

    >  >>  one of those things that language-designers like more than language-users.

    >  >>  one of the beauties of joy is that quotations are lists are programs, and

    >  >>  in some variants, are stacks.

    >  > The second is that they help clarify our understanding of what a

    >  > language is doing. If an operation in a language cannot yet be typed,

    >  > we do not have a complete idea of what it's doing yet.

    >  but if the language is incapable of expressing a well-formed thought

    >  because the type-system prevents that, then so much the worse for typing.

    >  that is, i start with clear and distinct idea of the algorithm and its

    >  data-structures, and then must work around limits on expressibility created

    >  by the type-system ... ?

     Well, such a type system is simply inadequate. Yes, that describes all

    known type systems :-). The eternal hope is that there might exist

    some type system which will NOT place those limits on "well-formed

    thoughts", but will stop poorly formed or incomplete ones.

    It's known that typechecking is uncomputable -- a truly complete type

    system would have to be able to specify whether a program halts, for

    example. Almost all existing type systems are subsets that we HOPE

    will provide enough of the problem without having to do anything

    uncomputable. Type inference takes on an NP-complete problem (but, of

    course, avoids the uncomputable one).

    There are type systems that can easily specify uncomputable problems.

    So far I'm extremely unimpressed -- they are UGLY, and they provide no

    useful functionality, only restrictions.

    To me, unit tests are useful for many of the things static typing is

    used for, and contracts are useful for many of the rest. But there are

    things remaining that static typing is good for... Especially when

    your editor knows about them and can help you.

    -Wm

## John Nowak — 2008-03-07 19:15:56

    On Mar 7, 2008, at 11:19 AM, William Tanksley, Jr wrote:

     >> Small point: You forgot the initial swap to put the list on top of

    >> the

    >> stack. The type system would've saved you of course.

    >

    > I didn't forget it; I was imitating your lambda code, in which the

    > list is already on top of the stack. Isn't that what "xs -> f i"

    > implies? So is your lambda code also wrong?

     No, it's correct. The list wasn't already on the top of the stack, the

    function was. By binding the function to 'f', we remove it from the

    stack, causing the list to be on top. This is why the call to 'unlist'

    makes sense.

     > This is moving the goalposts. When you posted the challenge you didn't

    > mention anything about programming time;

    >

    > I didn't time my coding, and I didn't know that was the goal, so I've

    > got no way to compete here.

     I was just relaying my personal experience. There was no timed

    challenge.

     > Not that speed competition would be fair -- I've never seen your

    > 'unlist' API anyhow, and now it appears you're doing something tricky

    > or incorrect in your example code (by putting the list on top).

     I posted the type and explained it. I showed how you can use it to

    write head/tail/null?/uncons. I'm not sure what else I can do. At the

    very least, I did say that, "What 'unlist' does is take three

    arguments. The first is a list."

     >> It took me over a minute to write the pointfree

    >> version. (Perhaps I just need more practice.) I also think the

    >> pointful version is easier to read, although we can certainly

    >> disagree.

    >

    > Perhaps you find it easier, but there's objective reason why it

    > shouldn't be easier. The point-free version is linear

     They're both linear, at least where "linear" refers to how objects are

    referenced. If you mean that it reads left to right as a strict means

    of sequencing, then no, it isn't linear. I'm not sure that's

    necessarily something that makes something easier to read however.

    Certainly mathematicians have been inventing notations that read in

    many different ways for quite awhile.

     > IMO anytime you play with 'dip' you introduce reading difficulty.

     Maybe it's a matter of taste then. I find 'dip' a lot easier to keep

    in my head than shuffles.

     >> Perhaps this series of errors is just another argument for lambda

    >> expressions and types. :) Considering the multitude of errors, I'd

    >> say

    >> it's a pretty strong one...

    >

    > Considering that all your lambda implementations had the same errors,

    > I don't see how that applies.

     They did not have any errors, although it seems to me that the errors

    in our pointfree code were due to translating the lambda-based

    versions and getting it wrong. In particular, the lambda version

    didn't need to pop the function because binding it to 'f' removed it

    from the stack. When doing the translation, we both forgot to pop it

    explicitly.

    - John

## John Nowak — 2008-03-07 19:26:05

    On Mar 7, 2008, at 2:15 PM, John Nowak wrote:

     > They did not have any errors, although it seems to me that the errors

    > in our pointfree code were due to translating the lambda-based

    > versions and getting it wrong. In particular, the lambda version

    > didn't need to pop the function because binding it to 'f' removed it

    > from the stack. When doing the translation, we both forgot to pop it

    > explicitly.

     Actually, let me clarify. *I* forgot to pop it explicitly. You didn't

    pop it because apparently not clearly explaining how variables work.

    I'll try to get this written up in a more formal manner.

    - John

## John Nowak — 2008-03-07 19:41:51

    On Mar 7, 2008, at 10:30 AM, Stevan Apter wrote:

     > but if the language is incapable of expressing a well-formed thought

    > because the type-system prevents that, then so much the worse for

    > typing.

    > that is, i start with clear and distinct idea of the algorithm and its

    > data-structures, and then must work around limits on expressibility

    > created

    > by the type-system ... ?

     It's all a question of how much complexity the type system adds and

    how much it gets in your way compared to how much it helps you out.

    Before you start worrying that the type system will stop you from

    expressing things in clear ways, it's probably better to get some

    experience with the type system in question first. You may be

    surprised that it doesn't get in the way much at all.

    - John

## John Nowak — 2008-03-07 19:47:01

    On Mar 7, 2008, at 10:20 AM, William Tanksley, Jr wrote:

     > There are two good things about types.

    >

    > The second is that they help clarify our understanding of what a

    > language is doing. If an operation in a language cannot yet be typed,

    > we do not have a complete idea of what it's doing yet.

     This is a very important point, and it's the primary reason that I'm

    pursuing a typed concatenative language. I'm doing all of the

    prototyping in Scheme, so it isn't as if I'm insistent that typed

    languages are the old way to go. Even if you prefer untyped languages,

    I think further research in this direction will be helpful to

    concatenative languages as a whole.

    Oh I can't write anything that sounds nice in the morning...

    - John

## William Tanksley, Jr — 2008-03-07 20:13:18

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  >> Small point: You forgot the initial swap to put the list on top of

    >  >> the stack. The type system would've saved you of course.

    >  > I didn't forget it; I was imitating your lambda code, in which the

    >  > list is already on top of the stack. Isn't that what "xs -> f i"

    >  > implies? So is your lambda code also wrong?

    >  No, it's correct. The list wasn't already on the top of the stack, the

    >  function was. By binding the function to 'f', we remove it from the

    >  stack, causing the list to be on top. This is why the call to 'unlist'

    >  makes sense.

     The *function*?? I'm confused. The function can't possibly be at the

    top of the stack. Here's your code (slightly bugfixed).

     >    f map = [pop nil]

    >            [xs -> f i xs f map cons]

    >          unlist

     As far as I can see, 'unlist' doesn't pass any function around; it

    doesn't know about a function. Your 'f map' notation appears to be

    creating a named lambda with a parameter named 'f'; that is the

    function and it gets passed around, but if 'map' wasn't defined as a

    lambda the function would be _under_ the 'x' and 'xs' parameters that

    'unlist' creates for the second quotation to consume.

    Right? What am I missing?

     >  > This is moving the goalposts. When you posted the challenge you didn't

    >  > mention anything about programming time;

    > > I didn't time my coding, and I didn't know that was the goal, so I've

    >  > got no way to compete here.

    >  I was just relaying my personal experience. There was no timed

    >  challenge.

     I didn't take offense -- sorry for the ambiguity (I seem to be vague a

    lot). But you DID challenge us to implement this algorithm in a

    "purely concatenative form", and you claimed that your version with

    lambdas was "objectively easier to understand". Nothing about it

    taking 15 seconds to program.

    I think I've met your challenge, and am at least entitled to claim the

    your "objectively easier" claim is incorrect.

     >  > Not that speed competition would be fair -- I've never seen your

    >  > 'unlist' API anyhow, and now it appears you're doing something tricky

    >  > or incorrect in your example code (by putting the list on top).

    >  I posted the type and explained it. I showed how you can use it to

    >  write head/tail/null?/uncons. I'm not sure what else I can do. At the

    >  very least, I did say that, "What 'unlist' does is take three

    > arguments. The first is a list."

     I wasn't complaining about bad documents in that paragraph -- I'm just

    pointing out that I can't write a 15-second program in a brand new

    API, even one that's fully documented. So I admit that my version took

    longer than 15 seconds to write.

     > >> It took me over a minute to write the pointfree

    >  >> version. (Perhaps I just need more practice.) I also think the

    >  >> pointful version is easier to read, although we can certainly

    >  >> disagree.

    >  > Perhaps you find it easier, but there's objective reason why it

    >  > shouldn't be easier. The point-free version is linear

    >  They're both linear, at least where "linear" refers to how objects are

    >  referenced.

     'f' is referred to twice; that's nonlinear.

     > If you mean that it reads left to right as a strict means

    >  of sequencing, then no, it isn't linear. I'm not sure that's

    >  necessarily something that makes something easier to read however.

    >  Certainly mathematicians have been inventing notations that read in

    >  many different ways for quite awhile.

     Left to right IS easier than jumpy. That's a simple and clear rule. It

    doesn't mean that jumpy is bad; sometimes you need jumpy. But it's

    objectively more complex.

     >  > IMO anytime you play with 'dip' you introduce reading difficulty.

    >  Maybe it's a matter of taste then. I find 'dip' a lot easier to keep

    >  in my head than shuffles.

     I think that's reasonable. (Wow, agreement!) When considering shuffles

    versus dips, keep in mind that dip essentially *both* performs a

    shuffle and an execution. Shuffles are technically simpler (because

    they _only_ rearrange), but of course there's only one thing 'dip' can

    do, while there's a lot of things shuffles can do. In other words, I

    do have sympathy for your argument, and I concede that it's

    subjective.

     >  >> Perhaps this series of errors is just another argument for lambda

    >  >> expressions and types. :) Considering the multitude of errors, I'd

    >  >> say it's a pretty strong one...

    >  > Considering that all your lambda implementations had the same errors,

    >  > I don't see how that applies.

    >  They did not have any errors, although it seems to me that the errors

    >  in our pointfree code were due to translating the lambda-based

    >  versions and getting it wrong. In particular, the lambda version

    >  didn't need to pop the function because binding it to 'f' removed it

    >  from the stack. When doing the translation, we both forgot to pop it

    >  explicitly.

     I do concede that your lambda probably wasn't wrong; it looks right to

    me. What seems wrong to me is your recent claim that in the stack

    version, the function is on top of the stack rather than car and cdr.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-07 20:18:15

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  This is a very important point, and it's the primary reason that I'm

    >  pursuing a typed concatenative language. I'm doing all of the

    >  prototyping in Scheme, so it isn't as if I'm insistent that typed

    >  languages are the old way to go. Even if you prefer untyped languages,

    >  I think further research in this direction will be helpful to

    >  concatenative languages as a whole.

     I very much look forward to the results of your research.

     >  Oh I can't write anything that sounds nice in the morning...

     Hmm, you made sense to me. And I also appreciate your ability to

    respond to criticism politely, even when it makes little sense.

     >  - John

     -Wm

## Stevan Apter — 2008-03-07 20:30:02

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

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, March 07, 2008 2:41 PM

    Subject: Re: [stack] sweetening concatenative syntax

    > On Mar 7, 2008, at 10:30 AM, Stevan Apter wrote:

    >

    >> but if the language is incapable of expressing a well-formed thought

    >> because the type-system prevents that, then so much the worse for

    >> typing.

    >> that is, i start with clear and distinct idea of the algorithm and its

    >> data-structures, and then must work around limits on expressibility

    >> created

    >> by the type-system ... ?

    >

    > It's all a question of how much complexity the type system adds and

    > how much it gets in your way compared to how much it helps you out.

    > Before you start worrying that the type system will stop you from

    > expressing things in clear ways, it's probably better to get some

    > experience with the type system in question first. You may be

    > surprised that it doesn't get in the way much at all.

    yes, i think that's reasonable.  my first test is:  can it manage

    a polyvalent map combinator?  bzzzzt!

    ok, seriously (but i wasn't being altogether facetious just now)

    my suspicion, which lacks sufficient evidence to be an opinion or

    a belief, is that an adequate type system for an array language is

    much more difficult to achieve than one for a scalar language, and since i

    am a devoted arrayhead, the bar is pretty high for me:  no convenience

    offered by any statically-typed scalar language will offset the advantages i

    derive from any dynamically-typed array language.

    >

    > - John

    >

## John Nowak — 2008-03-07 20:57:08

    On Mar 7, 2008, at 3:13 PM, William Tanksley, Jr wrote:

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

    >> William Tanksley, Jr wrote:

    >>>> Small point: You forgot the initial swap to put the list on top of

    >>>> the stack. The type system would've saved you of course.

    >>> I didn't forget it; I was imitating your lambda code, in which the

    >>> list is already on top of the stack. Isn't that what "xs -> f i"

    >>> implies? So is your lambda code also wrong?

    >

    >> No, it's correct. The list wasn't already on the top of the stack,

    >> the

    >> function was. By binding the function to 'f', we remove it from the

    >> stack, causing the list to be on top. This is why the call to

    >> 'unlist'

    >> makes sense.

    >

    > The *function*?? I'm confused. The function can't possibly be at the

    > top of the stack. Here's your code (slightly bugfixed).

    >

    >>   f map = [pop nil]

    >>           [xs -> f i xs f map cons]

    >>         unlist

     Er, almost. It does need to call 'nil' in the first quote, but not

    pop. (Maybe it *was* buggy before as I forgot the null, I can't even

    recall at this point.)

    Perhaps I should break it down so this is all crystal clear.

    Here's the type for map:

        map :: {a} [a -> b] -> {b}

    What this says is that the top element of the stack must be a

    function. The element below the top must be a list. If the list is of

    elements of type 'a', the function must be one that can transform

    elements of type 'a' to type 'b'. The result of calling map is then a

    list of type 'b'.

    Alright, so when we're writing the map function, we have to keep in

    mind that the function passed in will be on top of the stack.

    Now let's review the type of unlist again:

        unlist :: A {b} [A -> C] [A b {b} -> C] -> C

    This is somewhat complicated. What it says is that the top two items

    on the stack must be functions. The third item must be a list. The

    function on top of the stack gets called with the list unconsed if the

    list is not null. The other function gets called with nothing on the

    stack if the list is null. 'A' and 'C' represent "the rest of the

    stack". It isn't too important to full understand them here.

    Here's a quick example that might help:

        add-ignoring-list  = 1 2 null        [+] [pop pop +] unlist

        add-ignoring-list2 = 1 2 {"hi" "lo"} [+] [pop pop +] unlist

    (The curly braces indicate a list literal.)

    Both functions will return "3". In the first, the list is null, so +

    is just called on the stack '1 2' (the list has been permanently

    killed at this point). In the second, the list is not null, so the

    other function gets called with the list unconsed. At this point, the

    stack is '1 2 "hi" {"lo"} null'. After we pop twice, we add 1 and 2

    together yielding 3.

    If you go back now and look at the type, maybe it makes some sense.

    So let's look at pointfree map again:

        map = swap

              [pop null]

              [rot dup 2dip map cons]

            unlist

    Now when map gets called, the function supplied to map will be on the

    top. Therefore, the first thing we need to do is 'swap' so that the

    list is on top as unlist needs it as the third argument. After the

    swap, the stack looks something like this:

        <fn> <list of a>

    We then push on the quotations:

        <fn> <list of a> [pop null] [rot dup 2dip map cons]

    And then we call unlist. Now if the list is null, we get this scenario:

        <fn> pop null

    In that case, we pop the function and push on a new null list.

    Therefore, mapping a function over null yields null.

    Now, if the list isn't null, we get this scenario:

        <fn> a <list of a> rot dup 2dip map cons

    So we rotate and dup:

        a <list of a> <fn> <fn> 2dip map cons

    2dip is the same as dip except that it saves and restores the top two

    elements instead of only the top element. This is the same as '2keep'

    in factor (I think). Therefore, 2dip calls the top function with the

    list and the other function off the stack, and then restores them when

    finished. So we get something like this, where 'fn(a)' is the result

    of applying 'fn' to 'a':

        fn(a) <list of a> <fn> map cons

    Right, so now we're back in the situation with a function on top and a

    list below it. We can call 'map' again. It should be understandable

    from this point on I think.

    Now let's look at the pointful translation:

        f map = [null]

                [xs -> f i xs f map cons]

              unlist

    This version of 'map' binds the top element passed to 'map' to 'f'. As

    before, the top element passed to map must be a function, so we bind

    this function to 'f'. This binding in effect *removes* the function

    from the stack. Therefore, when map gets called, we have something

    like this:

        <list of a>

        f = <fn>

    Right. So the list is on the top and the function is in 'f'. Now we

    push on the quotations:

        <list of a> [null] [xs -> f i xs f map cons]

        f = <fn>

    Assuming the list is null, we get this scenario:

        null

        f = <fn>

    And so the final result is null as we want after evaluating 'null' to

    push a new null onto the stack.

    If the list isn't null, we get this:

        a f i xs f map cons

        f  = <fn>

        xs = <list of a>

    Normally '<list of a>' would be on the stack above 'a' (as before),

    but we bind the top element to 'xs' instead. Evaluating 'f' then

    pushes 'f' onto the stack and 'i' calls it to apply it to a. We then

    have this:

        fn(a) xs f map cons

        f  = <fn>

        xs = <list of a>

    So we go ahead and push on 'xs':

        fn(a) <list of a> f map cons

        f  = <fn>

        xs = <list of a>

    And then 'f':

        fn(a) <list of a> <fn> map cons

        f  = <fn>

        xs = <list of a>

    And then you can see we are right where we were before the recursion

    in the pointfree example.

    If you managed to read that, hopefully it cleared things up a bit. If

    it helps, you can think of lambdas as a more powerful shuffle

    notation. Where you might write 'abc--cabb', you can write '[a b c ->

    c a b b] i' instead.

    - John

## John Nowak — 2008-03-07 21:11:27

    On Mar 7, 2008, at 3:13 PM, William Tanksley, Jr wrote:

     >>> Perhaps you find it easier, but there's objective reason why it

    >>> shouldn't be easier. The point-free version is linear

    >

    >> They're both linear, at least where "linear" refers to how objects

    >> are

    >> referenced.

    >

    > 'f' is referred to twice; that's nonlinear.

     Keep in mind that the pointful version gets translated to pointfree

    code. It's just syntactic sugar. After the translation, each value is

    referenced only once. The function will need to be copied once (as it

    does when writing the pointfree version by hand), but no actual

    copying needs to occur if the function was not created via composing

    or partial application; it's just a pointer assignment. That's just an

    implementation detail though.

    Perhaps it'll be easier to show that it's linear once I can actually

    do the conversion... *ahem*

    - John

## William Tanksley, Jr — 2008-03-07 21:45:39

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  >> Types also complicate things. For example, you can't factor

    >  >> out the 'dup i' in '[swap] dup i' unless your system has higher-rank

    >  >> polymorphism or equi-recursive types.

    >  > Well, technically if your typesystem was "concatenative" you could

    >  > factor it out.

    >  This is true. The original type system I had was concatenative (well,

    >  really "compositional" is the correct term).

     Why? I'm going to start pushing back hard on this.

    "Concatenative" refers to a language in which the syntax is based on

    concatenation, and in which the semantics maps concatenation to some

    associative operation (function composition is the most interesting

    one currently defined). I suppose "compositional" means a language

    that's somehow based on function composition, which certainly

    describes all the interesting concatenative languages (and also some

    non-concatenative subsets of other languages).

     > Unfortunately, this

    >  property gets lost quite quickly as you expand the power of the type

    >  system.

     Or more accurately, it gets lost when you change the type system and

    inferrer without regard for maintaining associativity. I don't mind

    that, but a nagging question remains: is it possible to infer types

    for a concatenative language?

     > The only reason the original system was compositional was

    >  because it would refuse to accept things like "[swap] dup i" as all

    >  variables were non-generic and you'd hit an occurs check no matter

    >  what order you attempted it in.

     Makes sense.

     > At the moment, it seems that a truly

    >  compositional type system imposes too many limitations. If there are

    >  ways around this I've not discovered them yet.

     I agree; there may not be any ways around it (aside from giving up on

    most of the type inference). I wish I knew enough to experiment with

    this; I've been thinking of a few things, but I'm hindered by a tiny

    bit of knowledge, enough to know that HM type inference is exponential

    in the worst case, and I kind of expect that the changes I'm thinking

    about are bad cases.

     >  > If your typesystem isn't concatenative, then the resulting language

    >  > is no longer strictly concatenative

    >  This all depends on your definition of concatenative.

     And on your definition of "language", and "type", and "is". I think

    we've got an excellent definition; let's go forward with it. Or

    propose a new one.

     > The language is

    >  still expressed in terms of the functional forms of composition and

    >  quotation. Concatenation still denotes composition. The limitation is

    >  that you cannot compose functions in any order. This doesn't seem to

    >  be a problem in practice, although it certainly is unfortunate.

     It means that the properties of the semantics fail to match the

    properties of the syntax. That's a pretty severe change.

     >  > I can't criticise anyone for failing to have a concatenative type

    >  > system, since I don't know what such a thing would look like --

    >  I've been meaning to write up how to perform inference for a

    >  compositional type system. If anyone is interested I'll bump this up

    >  in my priority queue.

     I'll read it.

     >  - John

     -Wm

## William Tanksley, Jr — 2008-03-07 22:15:56

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

    >  >>> Perhaps you find it easier, but there's objective reason why it

    >  >>> shouldn't be easier. The point-free version is linear

    >  >> They're both linear, at least where "linear" refers to how objects

    >  >> are referenced.

    >  > 'f' is referred to twice; that's nonlinear.

    >  Keep in mind that the pointful version gets translated to pointfree

    >  code. It's just syntactic sugar.

     We're comparing lambda notation to pure concatenative notation. Your

    claim is that lambda notation is "objectively" superior. It's a

    comparison of notations, not of underlying machine architectures.

    You can't have it both ways, using lambda notation to make something

    look good (subjectively) and then converting it to a concatenative

    notation to make it meet some objectively measurable property.

    It's objectively true that lambda notation freely allows nonlinear

    references. It's also true that this can be optimized away, but it's

    NOT clear how expensive that will be (the expense is always up-front

    with a concatenative notation, which is sometimes uncomfortable but

    always clear).

     > After the translation, each value is

    >  referenced only once.

     And before the translation, the variable is used nonlinearly.

     >  Perhaps it'll be easier to show that it's linear once I can actually

    >  do the conversion... *ahem*

     In order to implement my version I directly translated your code... So

    I know it can be done.

     >  - John

     -Wm

## John Nowak — 2008-03-08 02:37:16

    On Mar 7, 2008, at 5:15 PM, William Tanksley, Jr wrote:

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

    >

    >> William Tanksley, Jr wrote:

    >>

    >>> 'f' is referred to twice; that's nonlinear.

    >>

    >> Keep in mind that the pointful version gets translated to pointfree

    >> code. It's just syntactic sugar.

    >

    > We're comparing lambda notation to pure concatenative notation. Your

    > claim is that lambda notation is "objectively" superior.

     My claim was that it was superior for a particular case, to be clear.

    I certainly don't believe this is true in the general case.

     > You can't have it both ways, using lambda notation to make something

    > look good (subjectively) and then converting it to a concatenative

    > notation to make it meet some objectively measurable property.

     I don't understand. It seems I can indeed have it both ways. Isn't

    converting a language to a simpler language what compilers do all the

    time? Maybe I'm misunderstanding.

     > It's objectively true that lambda notation freely allows nonlinear

    > references.

     This is incorrect. "Linear" means that *values* have at most one

    reference to them. It has nothing to do really with how often a given

    variable shows up the source code. Take a look at Henry Baker's Linear

    Lisp. It certainly has lambdas, but it is also certainly linear. There

    are also languages like Clean that enforce linearity through the type

    system. Likewise, you can have non-linear languages that do not have

    variables. Look at Joy for example.

     > It's also true that this can be optimized away, but it's

    > NOT clear how expensive that will be (the expense is always up-front

    > with a concatenative notation, which is sometimes uncomfortable but

    > always clear).

     There actually are clear rules for determining how many times copying

    will be necessary when using lambda expressions. The rule is that a

    variable will be copied N-1 times where N is the number of times it is

    used. There is only one exception to this rule: Uses in separate

    functions "directly applied" to a sum deconstructor (unlist, if, etc)

    do not require copying. The implementation may choose to eliminate

    additional copies if possible as well, just as it may do when you

    write code in a purely pointfree form, but that's besides the point.

    One of my requirements for introducing lambdas is that there be very

    clear rules for when copying will occur, so you can be sure this will

    be formally specified, simple, and not implementation-dependent.

     >

     - John

## John Nowak — 2008-03-08 03:12:27

    On Mar 7, 2008, at 4:45 PM, William Tanksley, Jr wrote:

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

    >

    >> William Tanksley, Jr wrote:

    >>

    >>

    >>> Well, technically if your typesystem was "concatenative" you could

    >>> factor it out.

    >>

    >> This is true. The original type system I had was concatenative (well,

    >> really "compositional" is the correct term).

    >

    > Why? I'm going to start pushing back hard on this.

     Ah, I should be more careful here. This has nothing to do with the

    concatenative versus compositional discussion from awhile back. I use

    the word "compositional" as it already has an established meaning with

    respect to type systems. (See http://www.cs.ioc.ee/~ando/publications/cats06.pdf

      for one example). Compositional also implies that that we're talking

    about a language where programs are expressed in terms of the

    associative operation of composition. This isn't necessarily the case

    with all concatenative languages. Regardless, my primary insistence on

    the term was due to it already being established. I've no interest in

    calling Joy "compositional" instead of "concatenative" or anything

    like that.

     >> Unfortunately, this property gets lost quite quickly as you

    >> expand the power of the type system.

    >

    > Or more accurately, it gets lost when you change the type system and

    > inferrer without regard for maintaining associativity.

     I'd argue that you need to drop associativity if you want a more

    powerful system.

     > I don't mind that, but a nagging question remains: is it possible to

    > infer types for a concatenative language?

     A Cat-like language without generic type variables does allow a

    compositional type system (even with the addition of first-class

    stacks and parameterized types). The downside is that you can't apply

    a single polymorphic function to arguments of different types. (This

    is often called let polymorphism.) My original system worked as such.

    As I've expanded it, I've had no choice but to drop the compositional

    nature of the system. I should note the current system types all

    functions that the original compositional system did, occasionally

    with more general types, so no expressivity is lost.

    Perhaps this isn't answering your question. If not, could you be more

    clear?

     >>> If your typesystem isn't concatenative, then the resulting language

    >>> is no longer strictly concatenative

    >>

    >> This all depends on your definition of concatenative.

    >

    > And on your definition of "language", and "type", and "is". I think

    > we've got an excellent definition; let's go forward with it. Or

    > propose a new one.

     Well, my point is this: If a concatenative language is one where

    concatenation denotes function composition, then the language is still

    concatenative. If a concatenative language also requires that you be

    able to extract any portion of a program and replace it with a name

    that represents that portion, then no, it wouldn't be concatenative.

    For example, if 'a b c d e' must be equivalent to 'a f e' where 'f ==

    b c d', then it isn't concatenative.

    There may be a solution to this. Functions could be annotated to

    indicate that it is okay if they fail to type check in certain ways.

    When they are used in another function, the body of the first function

    would be substituted in directly and would make use of the additional

    contextual information. This would allow you to write a function like

    'm = dup i' provided that it produces a valid type in the contexts in

    which it is used. Of course you could always just do this with the

    macro system as well, so it isn't clear that there's an additional

    need for such annotations in practice.

    Perhaps the system could be smart enough to detect that a function

    that fails to check could be checked if more information were given

    and then would appropriately delay checking. This isn't such a weird

    idea: ML does something similar with overloaded operators, albeit in a

    more limited form. It isn't clear that this is worth the additional

    complexity however (especially as macros can be used to compensate),

    or that it would be able to cover all cases, or even that the cases it

    could cover would be useful functions you'd want to have anyway.

    If you really want to preserve the simplicity of Joy and its

    compositional nature, and yet also get some of the benefits of static

    typing, I have a strong suspicion that you'll need a soft type system.

    Of course, practical soft type systems introduce entirely new levels

    of complexity...

    - John

## William Tanksley, Jr — 2008-03-08 18:14:21

    John Nowak <john@...> wrote:

     >  William Tanksley, Jr wrote:

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

    >  >> William Tanksley, Jr wrote:

    > >>> 'f' is referred to twice; that's nonlinear.

    >  >> Keep in mind that the pointful version gets translated to pointfree

    >  >> code. It's just syntactic sugar.

    >  > We're comparing lambda notation to pure concatenative notation. Your

    >  > claim is that lambda notation is "objectively" superior.

    >  My claim was that it was superior for a particular case, to be clear.

    >  I certainly don't believe this is true in the general case.

     I didn't notice that claim; if I had I wouldn't have responded. I

    agree that there are situations and needs for which lambdas are better

    than stack shuffles. I don't think this is one.

     >  > You can't have it both ways, using lambda notation to make something

    >  > look good (subjectively) and then converting it to a concatenative

    >  > notation to make it meet some objectively measurable property.

    >  I don't understand. It seems I can indeed have it both ways. Isn't

    >  converting a language to a simpler language what compilers do all the

    >  time? Maybe I'm misunderstanding.

     But you can't measure the readability of a language NOTATION in

    comparison to a different notation by converting the first one into

    the second. By that standard Brainf**k and Haskell have the same

    readability (they can both be converted to x86 machine code).

     >  > It's objectively true that lambda notation freely allows nonlinear

    >  > references.

    >  This is incorrect. "Linear" means that *values* have at most one

    >  reference to them. It has nothing to do really with how often a given

    >  variable shows up the source code. Take a look at Henry Baker's Linear

    >  Lisp. It certainly has lambdas, but it is also certainly linear. There

    >  are also languages like Clean that enforce linearity through the type

    >  system.

     I'm trying to find where linear lisp or Clean's uniqueness types allow

    multiple uses of the same variable. I'm not finding that; it appears

    to me that the opposite of what you claim is true: those languages

    claim to be linear BECAUSE they enforce only one use of each variable.

    What am I missing?

     > Likewise, you can have non-linear languages that do not have

    >  variables. Look at Joy for example.

     Joy appears to be linear. What am I missing?

     >  > It's also true that this can be optimized away, but it's

    >  > NOT clear how expensive that will be (the expense is always up-front

    >  > with a concatenative notation, which is sometimes uncomfortable but

    >  > always clear).

    >  There actually are clear rules for determining how many times copying

    >  will be necessary when using lambda expressions. The rule is that a

    >  variable will be copied N-1 times where N is the number of times it is

    >  used. There is only one exception to this rule: Uses in separate

    >  functions "directly applied" to a sum deconstructor (unlist, if, etc)

    >  do not require copying. The implementation may choose to eliminate

    >  additional copies if possible as well, just as it may do when you

    >  write code in a purely pointfree form, but that's besides the point.

    >  One of my requirements for introducing lambdas is that there be very

    >  clear rules for when copying will occur, so you can be sure this will

    >  be formally specified, simple, and not implementation-dependent.

     I think that would be excellent. Objectively so :-).

     >  - John

     -Wm

## john@johnnowak.com — 2008-03-08 19:22:43

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

    >

    >>  I don't understand. It seems I can indeed have it both ways. Isn't

    >>  converting a language to a simpler language what compilers do all the

    >>  time? Maybe I'm misunderstanding.

    >

    > But you can't measure the readability of a language NOTATION in

    > comparison to a different notation by converting the first one into

    > the second. By that standard Brainf**k and Haskell have the same

    > readability (they can both be converted to x86 machine code).

     I didn't think I was doing that. I don't mean to suggest that lambda

    expressions are superior to pointfree code because they can be converted

    to pointfree code and therefore are just as readable if not more so. There

    are certainly cases where lambda expressions are less readable. We got

    confused somewhere back there...

     >>  This is incorrect. "Linear" means that *values* have at most one

    >>  reference to them. It has nothing to do really with how often a given

    >>  variable shows up the source code. Take a look at Henry Baker's Linear

    >>  Lisp. It certainly has lambdas, but it is also certainly linear. There

    >>  are also languages like Clean that enforce linearity through the type

    >>  system.

    >

    > I'm trying to find where linear lisp or Clean's uniqueness types allow

    > multiple uses of the same variable. I'm not finding that; it appears

    > to me that the opposite of what you claim is true: those languages

    > claim to be linear BECAUSE they enforce only one use of each variable.

    >

    > What am I missing?

     Here's a function from Baker's "The Forth Shall Be First":

       (defun abs (x)

         (if-minusp x (- x) x))

    Here, 'x' appears more than once in the source code, yet it is still

    linear. The only claim I was making is that variables can appear more than

    once and the language can still be linear.

    What Linear Lisp disallows is implicit copying. For example, to write

    "square", you need to do something like this:

       (defun square (x)

         (let* ((x x-prime (dup x)))  ; use Dylan syntax [Shalit92].

           (* x x-prime)))

    The difference between Linear Lisp and Fifth is that Fifth essentially

    just inserts the 'dup' expressions for you. Dan has suggested that perhaps

    there should be an option to disallow this behavior so that copying is

    explicit. I'm not sure this is necessary provided that there is a clear

    and simple set of rules for when copying will occur as I've laid out.

     >> Likewise, you can have non-linear languages that do not have

    >> variables. Look at Joy for example.

    >

    > Joy appears to be linear. What am I missing?

     Joy is not linear because Joy allows values to have multiple references to

    them. For example, if I do '[1 2 3] dup', the list does not get copied.

    Instead, there are now two references to the same list on the stack.

    Because values can have multiple references to them, it is not safe to

    mutate values because you will have visible side effects. This is in

    contrast to Fifth where you can always mutate, and hence use more

    efficient non-persistent data structures, while remaining purely

    functional. (The one exception to this are references. The type system

    separates functions that read from or write to reference values from

    "pure" code.) Joy's non-linear nature is also the reason it requires a

    garbage collector whereas Fifth gets on fine without one as no garbage is

    ever created.

    In short, enforcing that values are singly referenced is the definition of

    linearity. Use-once variables are a means to achieve this that requires

    explicit copying. However, you can also have a linear language by

    automatically inserting the necessary copying which is what Fifth does.

    - John

## Don Groves — 2008-03-08 19:58:45

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

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

    >>  William Tanksley, Jr wrote:

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

    >>>> William Tanksley, Jr wrote:

    >>>>> 'f' is referred to twice; that's nonlinear.

    >

    >>>> Keep in mind that the pointful version gets translated to pointfree

    >>>> code. It's just syntactic sugar.

    >

    >>> We're comparing lambda notation to pure concatenative notation. Your

    >>> claim is that lambda notation is "objectively" superior.

    >

    >>  My claim was that it was superior for a particular case, to be

    >> clear.

    >>  I certainly don't believe this is true in the general case.

    >

    > I didn't notice that claim; if I had I wouldn't have responded. I

    > agree that there are situations and needs for which lambdas are better

    > than stack shuffles. I don't think this is one.

    >

    >>> You can't have it both ways, using lambda notation to make something

    >>> look good (subjectively) and then converting it to a concatenative

    >>> notation to make it meet some objectively measurable property.

    >

    >>  I don't understand. It seems I can indeed have it both ways. Isn't

    >>  converting a language to a simpler language what compilers do all

    >> the

    >>  time? Maybe I'm misunderstanding.

    >

    > But you can't measure the readability of a language NOTATION in

    > comparison to a different notation by converting the first one into

    > the second. By that standard Brainf**k and Haskell have the same

    > readability (they can both be converted to x86 machine code).

    >

    >>> It's objectively true that lambda notation freely allows nonlinear

    >>> references.

    >

    >>  This is incorrect. "Linear" means that *values* have at most one

    >>  reference to them. It has nothing to do really with how often a

    >> given

    >>  variable shows up the source code. Take a look at Henry Baker's

    >> Linear

    >>  Lisp. It certainly has lambdas, but it is also certainly linear.

    >> There

    >>  are also languages like Clean that enforce linearity through the

    >> type

    >>  system.

    >

    > I'm trying to find where linear lisp or Clean's uniqueness types allow

    > multiple uses of the same variable. I'm not finding that; it appears

    > to me that the opposite of what you claim is true: those languages

    > claim to be linear BECAUSE they enforce only one use of each variable.

    >

    > What am I missing?

     My understanding of linearity is that a value have only a single

    reference

    at any one instant. So, for example, if a value is pushed on the stack,

    it may not be held anywhere else simultaneously as it is now referenced

    by the stack. This seems to rule out the possibility of pushing a

    variable's

    value onto the stack, then doing it again later from the same variable.

    Unless I'm missing something...

    --

    don

     >> Likewise, you can have non-linear languages that do not have

    >>  variables. Look at Joy for example.

    >

    > Joy appears to be linear. What am I missing?

    >

    >>> It's also true that this can be optimized away, but it's

    >>> NOT clear how expensive that will be (the expense is always up-front

    >>> with a concatenative notation, which is sometimes uncomfortable but

    >>> always clear).

    >

    >>  There actually are clear rules for determining how many times

    >> copying

    >>  will be necessary when using lambda expressions. The rule is that a

    >>  variable will be copied N-1 times where N is the number of times

    >> it is

    >>  used. There is only one exception to this rule: Uses in separate

    >>  functions "directly applied" to a sum deconstructor (unlist, if,

    >> etc)

    >>  do not require copying. The implementation may choose to eliminate

    >>  additional copies if possible as well, just as it may do when you

    >>  write code in a purely pointfree form, but that's besides the point.

    >>  One of my requirements for introducing lambdas is that there be very

    >>  clear rules for when copying will occur, so you can be sure this

    >> will

    >>  be formally specified, simple, and not implementation-dependent.

    >

    > I think that would be excellent. Objectively so :-).

    >

    >>  - John

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

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

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

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

    >  >> William Tanksley, Jr wrote:

    >  >> This is true. The original type system I had was concatenative (well,

    >  >> really "compositional" is the correct term).

    >  > Why? I'm going to start pushing back hard on this.

    >  Ah, I should be more careful here. This has nothing to do with the

    >  concatenative versus compositional discussion from awhile back. I use

    >  the word "compositional" as it already has an established meaning with

    >  respect to type systems. (See http://www.cs.ioc.ee/~ando/publications/cats06.pdf

    >   for one example). Compositional also implies that that we're talking

    >  about a language where programs are expressed in terms of the

    >  associative operation of composition. This isn't necessarily the case

    >  with all concatenative languages. Regardless, my primary insistence on

    >  the term was due to it already being established. I've no interest in

    >  calling Joy "compositional" instead of "concatenative" or anything

    >  like that.

     That's a cool paper; thank you. However, that's not what the paper

    appears to mean by "compositionality". Look it up; compositional

    appears to refer to the property that a program or statement can be

    understood correctly by synthesizing the meaning of its component

    phrases. The paper actually claims that the language it's studying is

    "non-compositional" due to it not being composed of discrete phrases

    -- which means that concatenative languages (by my definition) are

    also non-compositional by his definition.

     >  >> Unfortunately, this property gets lost quite quickly as you

    >  >> expand the power of the type system.

    >  > Or more accurately, it gets lost when you change the type system and

    >  > inferrer without regard for maintaining associativity.

    >  I'd argue that you need to drop associativity if you want a more

    >  powerful system.

     I'd love to hear that argument. Go for it (although in a new thread)!

    The implication would be that it's impossible to define a

    strongly-typed and type-inferenced concatenative language (at least by

    my definition).

    To me, that implies in turn that my definition of 'concatenative' is

    most probably wrong.

     >  > I don't mind that, but a nagging question remains: is it possible to

    >  > infer types for a concatenative language?

    >  A Cat-like language without generic type variables does allow a

    >  compositional type system (even with the addition of first-class

    >  stacks and parameterized types). The downside is that you can't apply

    >  a single polymorphic function to arguments of different types. (This

    >  is often called let polymorphism.) My original system worked as such.

     I'm confused by "apply a single polymorphic function to arguments of

    different types". Does that refer to, for example, mapping a

    polymorphic function to a list containing two values of different

    types, either of which is acceptable to the function's polymorphic

    type?

    So for example, let

    [2.0f 2] [2.0f 2] [*] over-each == [4.0f 4].

    In other words, it applies a dyadic function to a pair of lists.

    I think you're saying that the simple type system can't infer the

    types for that code snippet, right? And then you go on to say that

    it's impossible to build a type system that can both infer the types,

    AND remain associative, right?

     >  As I've expanded it, I've had no choice but to drop the compositional

    >  nature of the system. I should note the current system types all

    >  functions that the original compositional system did, occasionally

    >  with more general types, so no expressivity is lost.

     I would expect more general types to be helpful -- for example, in the

    above example I would expect a union type into which both integers and

    floats fit.

     >  Perhaps this isn't answering your question. If not, could you be more

    >  clear?

     It's confirming my suspicion about what you meant, yes. And BTW, I

    don't have any rebuttal or anything like that... I'd like to hear your

    argument.

     >  >>> If your typesystem isn't concatenative, then the resulting language

    >  >>> is no longer strictly concatenative

    >  >> This all depends on your definition of concatenative.

    >  > And on your definition of "language", and "type", and "is". I think

    >  > we've got an excellent definition; let's go forward with it. Or

    >  > propose a new one.

    >  Well, my point is this: If a concatenative language is one where

    >  concatenation denotes function composition, then the language is still

    >  concatenative. If a concatenative language also requires that you be

    >  able to extract any portion of a program and replace it with a name

    >  that represents that portion, then no, it wouldn't be concatenative.

    >  For example, if 'a b c d e' must be equivalent to 'a f e' where 'f ==

    >  b c d', then it isn't concatenative.

     Yes, the latter is an implication of associativity. Note that

    concatenation is an associative operation, as is composition.

     >  There may be a solution to this. Functions could be annotated to

    >  indicate that it is okay if they fail to type check in certain ways.

    >  When they are used in another function, the body of the first function

    >  would be substituted in directly and would make use of the additional

    >  contextual information. This would allow you to write a function like

    >  'm = dup i' provided that it produces a valid type in the contexts in

    >  which it is used. Of course you could always just do this with the

    >  macro system as well, so it isn't clear that there's an additional

    >  need for such annotations in practice.

    >  Perhaps the system could be smart enough to detect that a function

    >  that fails to check could be checked if more information were given

    >  and then would appropriately delay checking. This isn't such a weird

    >  idea: ML does something similar with overloaded operators, albeit in a

    >  more limited form. It isn't clear that this is worth the additional

    >  complexity however (especially as macros can be used to compensate),

    >  or that it would be able to cover all cases, or even that the cases it

    >  could cover would be useful functions you'd want to have anyway.

     This is exactly what I've been pondering over the last few days. And

    yes, the fact that ML is the only type-inferencing language I know has

    contributed to those speculations. I don't insist on the type system

    performing the inference automatically, although I do think that if we

    can't even guess at how it could be done we don't understand the

    problem yet.

     >  If you really want to preserve the simplicity of Joy and its

    >  compositional nature, and yet also get some of the benefits of static

    >  typing, I have a strong suspicion that you'll need a soft type system.

    >  Of course, practical soft type systems introduce entirely new levels

    >  of complexity...

     After a brief google, I have to say that I'd rather not back up to a

    soft type system quite yet... It may be necessary, but I'd rather

    understand the static system first.

    Note, by the way, that there's very few languages that can be fully

    hard-typed. The only one I know is SPARK Ada, and it's hard to code

    in; you have to code proofs in addition to your code. (IMO, a language

    is fully hard typed ONLY IF it's possible to write serious programs in

    it that don't require a runtime, i.e. exception handling.)

     >  - John

     -Wm

## john@johnnowak.com — 2008-03-08 20:06:14

    On Sat, March 8, 2008 2:58 pm, Don Groves wrote:

     > My understanding of linearity is that a value have only a single

    > reference at any one instant.

     Right.

     > So, for example, if a value is pushed on the stack, it may not be held

    > anywhere else simultaneously as it is now referenced by the stack.

     Right.

     > This seems to rule out the possibility of pushing a variable's

    > value onto the stack, then doing it again later from the same variable.

     There's no variable to push "from". Lambda expressions are translated to

    pointfree stack-based code. If a variable is used more than once, explicit

    copying is automatically inserted as I described earlier.

    - John

## William Tanksley, Jr — 2008-03-08 20:20:31

    <john@...> wrote:

     >  > But you can't measure the readability of a language NOTATION in

    >  > comparison to a different notation by converting the first one into

    >  > the second. By that standard Brainf**k and Haskell have the same

    >  > readability (they can both be converted to x86 machine code).

    >  I didn't think I was doing that. I don't mean to suggest that lambda

    >  expressions are superior to pointfree code because they can be converted

    >  to pointfree code and therefore are just as readable if not more so. There

    >  are certainly cases where lambda expressions are less readable. We got

    >  confused somewhere back there...

     I'm one of the confused. You said your lambda code was objectively

    superior and challenged me to write concatenative code. I did, and

    then produced objective measures for my code's acceptability (function

    count, token count, linearity, and smooth left-to-right reading). You

    *apparently* responded by claiming that those somehow applied to your

    notation too because your notation could be translated to mine.

    If that's not what you meant, cool; but what DID you mean?

     >  >>  This is incorrect. "Linear" means that *values* have at most one

    >  >>  reference to them. It has nothing to do really with how often a given

    >  >>  variable shows up the source code. Take a look at Henry Baker's Linear

    >  >>  Lisp. It certainly has lambdas, but it is also certainly linear. There

    >  >>  are also languages like Clean that enforce linearity through the type

    >  >>  system.

    >  > I'm trying to find where linear lisp or Clean's uniqueness types allow

    >  > multiple uses of the same variable. I'm not finding that; it appears

    >  > to me that the opposite of what you claim is true: those languages

    >  > claim to be linear BECAUSE they enforce only one use of each variable.

    >  > What am I missing?

    >  Here's a function from Baker's "The Forth Shall Be First":

    >    (defun abs (x)

    >      (if-minusp x (- x) x))

    >  Here, 'x' appears more than once in the source code, yet it is still

    >  linear.

     Read Baker's discussion -- he admits that this is a special case with

    "relaxed" rules. It's admittedly not "strictly" linear (his words).

    Your code doesn't even meet that special case; it's nonlinear in 'f',

    which appears twice sequentially.

     > The only claim I was making is that variables can appear more than

    >  once and the language can still be linear.

     You actually claimed that your implementation was linear, which it's not.

    I would concede that variables can appear twice, if the variable can

    only possibly be encountered once (for example, in both branches of an

    'if').

     >  What Linear Lisp disallows is implicit copying. For example, to write

    >  "square", you need to do something like this:

    >    (defun square (x)

    >      (let* ((x x-prime (dup x)))  ; use Dylan syntax [Shalit92].

    >        (* x x-prime)))

    >  The difference between Linear Lisp and Fifth is that Fifth essentially

    >  just inserts the 'dup' expressions for you. Dan has suggested that perhaps

    >  there should be an option to disallow this behavior so that copying is

    >  explicit. I'm not sure this is necessary provided that there is a clear

    >  and simple set of rules for when copying will occur as I've laid out.

     I look forward to reading more about Fifth. I agree with you that

    linearity is interesting, and that the rules you hint at should make

    linear coding with variables a little easier. I don't see how your

    rules can improve over established techniques like SSA.

     >  >> Likewise, you can have non-linear languages that do not have

    >  >> variables. Look at Joy for example.

    >  > Joy appears to be linear. What am I missing?

    >  Joy is not linear because Joy allows values to have multiple references to

    >  them.

     Touche'. Thank you, I definitely have to entirely concede that point.

    Well played :-).

     >  In short, enforcing that values are singly referenced is the definition of

    >  linearity. Use-once variables are a means to achieve this that requires

    >  explicit copying. However, you can also have a linear language by

    >  automatically inserting the necessary copying which is what Fifth does.

     Actually, this sounds like it should be pretty cool.

     >  - John

     -Wm

## Don Groves — 2008-03-08 20:29:22

    On Mar 8, 2008, at 19:06 , john@... wrote:

     > On Sat, March 8, 2008 2:58 pm, Don Groves wrote:

    >

    >> My understanding of linearity is that a value have only a single

    >> reference at any one instant.

    >

    > Right.

    >

    >> So, for example, if a value is pushed on the stack, it may not be

    >> held

    >> anywhere else simultaneously as it is now referenced by the stack.

    >

    > Right.

    >

    >> This seems to rule out the possibility of pushing a variable's

    >> value onto the stack, then doing it again later from the same

    >> variable.

    >

    > There's no variable to push "from". Lambda expressions are

    > translated to

    > pointfree stack-based code. If a variable is used more than once,

    > explicit

    > copying is automatically inserted as I described earlier.

     OK, thanks. The same thing happens in ACL, my as yet unfledged

    contribution to the cause. Explicit copying allows you to immediately

    free memory when a stack item is consumed, hence there's no way

    a value can have multiple references.

    --

    don

     >

    > - John

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## john@johnnowak.com — 2008-03-08 21:07:24

    William Tanksley, Jr wrote:

     > That's a cool paper; thank you. However, that's not what the paper

    > appears to mean by "compositionality".

     Ah, you're right. Maybe that wasn't the paper I was thinking of... scratch

    that then.

     >>> Or more accurately, it gets lost when you change the type system and

    >>> inferrer without regard for maintaining associativity.

    >>  I'd argue that you need to drop associativity if you want a more

    >>  powerful system.

    > I'd love to hear that argument. Go for it (although in a new thread)!

     I've hinted at the reasons in previous emails. I'll try and write up

    something more detailed soon. I'll take a stab at it briefly below...

     > To me, that implies in turn that my definition of 'concatenative' is

    > most probably wrong.

     Perhaps it's just a case of having "strong concatenative" and "weak

    concatenative" languages? Different levels of purity are certainly useful

    when talking about other paradigms.

     > I'm confused by "apply a single polymorphic function to arguments of

    > different types". Does that refer to, for example, mapping a

    > polymorphic function to a list containing two values of different

    > types, either of which is acceptable to the function's polymorphic

    > type?

    >

    > So for example, let

    > [2.0f 2] [2.0f 2] [*] over-each == [4.0f 4].

     In that example, there'd be no way to even create such lists in the first

    place without type classes (where Int and Float are instances of some Num

    class) or intersection types. You could of course always wrap things up in

    a sum (union/variant) type.

    Anyway, what I meant is something like this:

       foo = 0 "hi" [pop] dup dip i

    Here, the same pop function is applied to both an integer and a string.

    Without a notion of generic (aka "free") type variables, this function is

    not typeable. This is because the variable in the type of the quotation

    (pop :: a -> ) gets instantiated to 'String' for both functions because

    the variable in the second function is not free with respect to the first.

    Here's the evaluation of the above function on the type level which may help:

       Int                        -- 0

       Int String                 -- "hi"

       Int String [a -> ]         -- [pop]

       Int String [a -> ] [a -> ] -- dup

       Int [String ->]            -- dip

    At this point, we'd get a type error when composing 'i' as we can't unify

    the types Int and String. Now here's the same thing allowing variables to

    be free:

       Int                        -- 0

       Int String                 -- "hi"

       Int String [a -> ]         -- [pop]

       Int String [a -> ] [b -> ] -- dup -- note the difference!

       Int [b ->]                 -- dip

                                  -- i

    Hopefully that makes some sense. Now, let me briefly explain why the

    second system (the one with free type variables) breaks concatenativity

    with the function '[swap] dup i'. First, without generic type variables:

       [a b -> b a]               -- [swap]

       [a b -> b a] [a b -> b a]  -- dup

    At this point, we get a type error when composing 'i' as we fail an occurs

    check. Here's the derivation:

       -- initial composition

       R -> R [S a b -> S b a] [S a b -> S b a]

            T                  [T     -> U    ] -> U

       -- unify 'S b a' and 'U'

       R -> R [S a b -> S b a] [S a b -> S b a]

            T                  [T     -> S b a] -> S b a

       -- unify 'S a b' and 'T'

       R -> R   [S a b -> S b a] [S a b -> S b a]

            S a b                [S a b -> S b a] -> S b a

       -- fail! cannot unify 'b' and '[S a b -> S b a]' due to infinite type

    Not sure if that makes any sense. Probably not. I'll explain how to do

    these compositions by hand when I eventually write this up. If it does

    make sense though, then great.

    Now, here's the same thing with generic variables:

       [a b -> b a]               -- [swap]

       [a b -> b a] [c d -> d c]  -- dup -- note the difference!

    And here we can compose 'i' properly without running into the occurs

    check. Again, here's the derivation:

       -- initial composition

       R -> R [S a b -> S b a] [V c d -> V d c]

            T                  [T     -> U    ] -> U

       -- unify 'V d c' and 'U'

       R -> R [S a b -> S b a] [V c d -> V d c]

            T                  [T     -> V d c] -> V d c

       -- unify 'V c d' and 'T'

       R -> R   [S a b -> S b a] [V c d -> V d c]

            V c d                [V c d -> V d c] -> V d c

       -- unify '[S a b -> S b a]' and 'd' -- oh line wrap...

       R -> R   [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a] c]

            V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a]

    c] -> V [S a b -> S b a] c

       -- unify 'R' and 'V c'

       V c -> V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a] c]

              V c [S a b -> S b a] [V c [S a b -> S b a] -> V [S a b -> S b a]

    c] -> V [S a b -> S b a] c

       -- final type

       V c -> V [S a b -> S b a] c

       -- or more nicely

       a -> [b c -> b c] a

    Right. So what I've shown is that the system without free type variables

    cannot type '[swap] dup i' and the system with free type variables can.

    However, neither system can type 'dup i' by itself. In order to type

    '[swap] dup i', you need free type variables and you *must* compose types

    left to right in order to gather the necessary constraints. Hence, the

    system is not purely concatenative.

    Languages like ML and Haskell work exactly the same way. For example, this

    is untypeable in Haskell:

       \x -> x x

    However, this is fine as we're letting it know what the type of 'x' is:

       let x = flip in x x

    There are ways to lift such restrictions. One is equi-recursive types,

    although all you tend to get out of this is are valid types that you can't

    do much with (and hence the system will still not be purely

    concatenative). The other is to allow rank-n polymorphism. Unfortunately,

    systems with rank-n polymorphism are undecidable and require type

    annotations for all higher rank functions (except perhaps rank-2 depending

    on your particular system). This is something I'd like to tackle

    eventually but will not be dealing with in earlier versions of the

    language.

    - John

## john@johnnowak.com — 2008-03-08 21:31:01

    > I'm one of the confused. You said your lambda code was objectively

    > superior and challenged me to write concatenative code. I did, and

    > then produced objective measures for my code's acceptability (function

    > count, token count, linearity, and smooth left-to-right reading). You

    > *apparently* responded by claiming that those somehow applied to your

    > notation too because your notation could be translated to mine.

    >

    > If that's not what you meant, cool; but what DID you mean?

     I meant that it could be reasoned about as easily as the pointfree version

    as there would be a well-defined translation. That's what I meant by

    saying you get the best of both worlds; the worlds were "simple

    concatenative semantics" and "lexically scope variables".

     > Read Baker's discussion -- he admits that this is a special case with

    > "relaxed" rules. It's admittedly not "strictly" linear (his words).

     I obviously have to re-read it! It's been awhile.

     > Your code doesn't even meet that special case; it's nonlinear in 'f',

    > which appears twice sequentially.

     In the program that results from my code, all values are referenced once

    (due to implicit copying). Values can be mutated without visible side

    effects. No garbage collection is needed. In seems that it offers all of

    the same benefits as Baker's Linear Lisp, does it not?

    If it does offer the same benefits, then why is not linear? Is it because

    all copying is not explicit? If that's the case, do macros make a language

    non-linear because they can compile down to code that calls dup? If macros

    do not make a language non-linear, then why do lambda expressions make it

    non-linear if lambda expressions are just macros?

    It seems to me that you're saying the addition of macros makes a language

    non-linear. Perhaps Baker was simply not precise enough in his definition?

    Perhaps I'm way off somehow?

    - John

## Don Groves — 2008-03-08 21:48:08

    On Mar 8, 2008, at 19:31 , john@... wrote:

     >> I'm one of the confused. You said your lambda code was objectively

    >> superior and challenged me to write concatenative code. I did, and

    >> then produced objective measures for my code's acceptability

    >> (function

    >> count, token count, linearity, and smooth left-to-right reading). You

    >> *apparently* responded by claiming that those somehow applied to your

    >> notation too because your notation could be translated to mine.

    >>

    >> If that's not what you meant, cool; but what DID you mean?

    >

    > I meant that it could be reasoned about as easily as the pointfree

    > version

    > as there would be a well-defined translation. That's what I meant by

    > saying you get the best of both worlds; the worlds were "simple

    > concatenative semantics" and "lexically scope variables".

    >

    >> Read Baker's discussion -- he admits that this is a special case with

    >> "relaxed" rules. It's admittedly not "strictly" linear (his words).

    >

    > I obviously have to re-read it! It's been awhile.

    >

    >> Your code doesn't even meet that special case; it's nonlinear in 'f',

    >> which appears twice sequentially.

    >

    > In the program that results from my code, all values are referenced

    > once

    > (due to implicit copying). Values can be mutated without visible side

    > effects. No garbage collection is needed. In seems that it offers

    > all of

    > the same benefits as Baker's Linear Lisp, does it not?

    >

    > If it does offer the same benefits, then why is not linear? Is it

    > because

    > all copying is not explicit? If that's the case, do macros make a

    > language

    > non-linear because they can compile down to code that calls dup? If

    > macros

    > do not make a language non-linear, then why do lambda expressions

    > make it

    > non-linear if lambda expressions are just macros?

     My version of dup makes an explicit copy automatically.  Does that

    solve the problem?

    --

    don

     > It seems to me that you're saying the addition of macros makes a

    > language

    > non-linear. Perhaps Baker was simply not precise enough in his

    > definition?

    > Perhaps I'm way off somehow?

    >

    > - John

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## john@johnnowak.com — 2008-03-08 21:56:54

    > My version of dup makes an explicit copy automatically.  Does that

    > solve the problem?

     Bah. We need to get on IRC. There is a #fifth channel on freenode by the

    way... although I'm the only one to have ever entered it.

    Anyway: What problem? My contention is that there is no problem.

    (But yes, dup must make a deep copy immediately.)

    - John

## Manfred Von Thun — 2008-03-11 07:58:22

    On 5/3/08 8:04 PM, "John Nowak" <john@...> wrote

     >

    >

    > I've had some thoughts recently on syntactic additions to

    > concatenative languages that seem potentially quite useful.

    > ...

    > I. Lambda Expressions

    >

    > Assuming functions have the syntax '[<body>]', it seems useful to

    > introduce the syntax '[<bindings> -> <body>], where bindings are

    > ordered with the top of the stack towards the right as is familiar.

    > For example, the following two functions are equivalent:

    >

    > foo :: -> [a b -> b a a]

    >  foo = [swap dup]

    >  foo = [a b -> b a a]

    >

     That is exactly the conclusion I came to when playing with a Joy in Prolog,

    PJoy

    Here are swap, +,your foo and stack in this notation (with help from

    Prolog¹s

    way of allowing simple modification of its native syntax:

    swap   turns  [A,B|R] into [B,A|R].

    +        turns  [A,B|R] into [C|R]  :- C is A+B.

    foo      turns  [B,A|R] into [A,A<B|R].

    stack   turns  S  into [S|S].

    These are not documentation, but the implementation!

    R means the rest (of the Joy stack), the vertical bar is Prolog notation.

    The last one, for stack, is an example that would be difficult

    in the proposed lambda notations I have seen.

     >

     Pattern matching, which is one of Prolog¹s strengths,

    is also useful when defining new operators in terms of

    several others. The output stack from one operator has

    to match the input stack of the next operator, and in

    a crude compiler (from Joy to Prolog) which I write,  Prolog did all

    the checking  before I even noticed that it was doing that.

     >

    >

    > II. Local Function Variables

    >

    > If you permit lambdas, it makes sense to offer a simple syntax for

    > declaring functions with named variables. This is similar to how

    > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo

    > (lambda (<bindings>) <body>))'. The declaration syntax proposed here

    > mimics use. In particular, the name of the function being defined

    > occurs *after* the arguments.

    >

     Indeed. They are useful when things get messy, such as the annoying

    quadratic formula. With ³local variables²  in Pjoy it can be defined rather

    intelligibly. I¹ll have to bring the example from my home computer.

      - Manfred

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

## Manfred Von Thun — 2008-03-19 02:17:03

    On 11/3/08 6:58 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

     >

    > On 5/3/08 8:04 PM, "John Nowak" <john@...

    > <mailto:john%40johnnowak.com> wrote

    >

    > ...

    >> > II. Local Function Variables

    >> >

    >> > If you permit lambdas, it makes sense to offer a simple syntax for

    >> > declaring functions with named variables. This is similar to how

    >> > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo

    >> > (lambda (<bindings>) <body>))'. The declaration syntax proposed here

    >> > mimics use. In particular, the name of the function being defined

    >> > occurs *after* the arguments.

    >> >

    > Indeed. They are useful when things get messy, such as the annoying

    > quadratic formula. With ³local variables²  in Pjoy it can be defined rather

    > intelligibly. I¹ll have to bring the example from my home computer.

    >

     Here it is, copied to paper, ported by car, sent as mail:

    A, B, C are the three input variables, R is the rest of the stack.

    P and Q are the output variables, the positive and negative roots.

    Every datum on the stack is typed as shown. Two local variables

    are used: Diff and Root.

    quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-

     > Diff is B*B -$*A*C,

    > (   Diff < 0.0,

    > ->  write(quadratic: cannot take root of negative argument¹)

    > ;   Root is sqrt(Diff),

    >     P is (0-B+Root)/(2*A),

    >     N is (0-B-Root)/(2*A)

    > ).

    >

     Looks a lot more intelligible this way with local variables than when

    written in [urely concatenative style.

     >

    > - Manfred

    >

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

## Christopher Diggins — 2008-03-19 02:35:56

    On Tue, Mar 18, 2008 at 10:17 PM, Manfred Von Thun

    <m.vonthun@...> wrote:

     >

    > On 11/3/08 6:58 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

    >

    > >

    > > On 5/3/08 8:04 PM, "John Nowak" <john@...

    > > <mailto:john%40johnnowak.com> wrote

    > >

    > > ...

    >

    > >> > II. Local Function Variables

    > >> >

    > >> > If you permit lambdas, it makes sense to offer a simple syntax for

    > >> > declaring functions with named variables. This is similar to how

    > >> > Scheme offers '(define (foo <bindings>) <body>)' to mean '(define foo

    > >> > (lambda (<bindings>) <body>))'. The declaration syntax proposed here

    > >> > mimics use. In particular, the name of the function being defined

    > >> > occurs *after* the arguments.

    > >> >

    > > Indeed. They are useful when things get messy, such as the annoying

    > > quadratic formula. With ³local variables² in Pjoy it can be defined rather

    > > intelligibly. I¹ll have to bring the example from my home computer.

    > >

    > Here it is, copied to paper, ported by car, sent as mail:

    >

    > A, B, C are the three input variables, R is the rest of the stack.

    > P and Q are the output variables, the positive and negative roots.

    > Every datum on the stack is typed as shown. Two local variables

    > are used: Diff and Root.

    >

    > quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-

    > > Diff is B*B -$*A*C,

    > > ( Diff < 0.0,

    > > -> write(Œquadratic: cannot take root of negative argument¹)

    > > ; Root is sqrt(Diff),

    > > P is (0-B+Root)/(2*A),

    > > N is (0-B-Root)/(2*A)

    > > ).

    > >

    > Looks a lot more intelligible this way with local variables than when

    > written in [urely concatenative style.

     I agree. I think it is worth mentioning that Slava made some

    interesting points on the subject of quadratics in a concatenative

    style:

    http://factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html

    When you see ">r ... r>" in Factor I believe you can just replace it

    with "[...] dip".

    - Christopher

## John Nowak — 2008-03-19 07:06:42

    On Mar 18, 2008, at 10:17 PM, Manfred Von Thun wrote:

     > quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-

    > Diff is B*B -$*A*C,

    > (   Diff < 0.0,

    > ->  write(‘quadratic: cannot take root of negative argument’)

    > ;   Root is sqrt(Diff),

    >    P is (0-B+Root)/(2*A),

    >    N is (0-B-Root)/(2*A)

    > ).

     Here's another version of the above with a syntax more suited to a

    concatenative language:

    quad a b c = p n

        where 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 /

    Ah, syntax is fun.

    - John

## John Nowak — 2008-03-19 07:29:55

    On Mar 19, 2008, at 3:06 AM, John Nowak wrote:

     > Here's another version of the above with a syntax more suited to a

    > concatenative language:

    >

    > quad a b c = p n

    >    where 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 /

     Or in a manner requiring less heroics for people with more taste and

    sophisticated structural editors:

       (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))

    Unlike Manfred's original example, these return 'p' and 'n' on the

    stack directly. '[...]' is just sugar for '(lambda () ...)', where

    'lambda' expands to point-free code if variables are introduced.

    Yes, I want a typed Scheme where functions can easily produce (and

    subsequently consume) multiple values. Is that so wrong?

    - John

## Chris Double — 2008-03-19 07:32:37

    On Wed, Mar 19, 2008 at 8:29 PM, John Nowak <john@...> wrote:

     >  Yes, I want a typed Scheme where functions can easily produce (and

    >  subsequently consume) multiple values. Is that so wrong?

     With pattern matching and destructuring assignment too please :-)

    Chris

## Don Groves — 2008-03-19 07:43:47

    And a compiler that will generate code for any platform, including

    the JVM, Parrot, etc...

    --

    don

     On Mar 19, 2008, at 19:32 , Chris Double wrote:

    > On Wed, Mar 19, 2008 at 8:29 PM, John Nowak <john@...>

    > wrote:

    >>  Yes, I want a typed Scheme where functions can easily produce (and

    >>  subsequently consume) multiple values. Is that so wrong?

    >

    > With pattern matching and destructuring assignment too please :-)

    >

    > Chris

    >

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

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Manfred Von Thun — 2008-03-19 08:04:57

    On 7/3/08 9:00 AM, "Stevan Apter" <sa@...> wrote:

     > ack.  it's been so long since i looked at this stuff that i'd

    > forgotten that 'map' in f/g and XY is an extension of the standard

    > definition:  given a list of k-length lists, it applies a n-ary

    > function n>=k to each element of the list.  so e.g.

    >

    > [[1 2][3 4][5 6]][+]map -> [3 7 11]

    >

     Isn¹t what you want just

    [[1 2] [3 4] [5 6]  [sum] map => [3 7 11]

    where it is not even required that the sublists are of the same

    length. Or did I miss something?

     > - Manfred

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

## Manfred Von Thun — 2008-03-19 08:43:49

    On 8/3/08 2:40 AM, "Christopher Diggins" <cdiggins@...> wrote:

     > On Fri, Mar 7, 2008 at 10:11 AM, Stevan Apter <sa@...

    > <mailto:sa%40nsl.com> > wrote:

    >

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

    >> > From: "John Nowak" <john@... <mailto:john%40johnnowak.com> >

    >> > To: <concatenative@yahoogroups.com <mailto:concatenative%40yahoogroups.com>

    >

    >

    > ....

    >>> > > Ah, I think maybe there's some confusion here over what we mean by

    >>> > > "list". (Yes, really!) In Joy, lists, stacks, and functions are all

    >>> > > magically the same thing. I assume it's similar in XY as well. In

    >>> > > Fifth, lists, stacks, and functions are all different things. This is

    >>> > > just one more example of the endless complication that types introduce.

    >

     In Joy, stacks, list, and quotations are the same thing.  A mathematician

    would

    tell you that a set is a truth function, giving truth for its members and

    falsity

    for everything else. They would also tell you that a sequence

    (list,vector,array...)

    is a function from an initial portion of the positive natural numbers (1 2 3

    ...)

    to its members, and undefined beyond that (all this is done by the indexing

    function, of course). But function can have all sorts of things as

    argument(s)

    and give all sorts of things as value. But don¹t confuse functions with

    programs

    that compute them. [My favourite example: there is just one doubling

    function,

    and there many programs that compute it: 1: (add the argument to itself),

    2: (multiply the argument by 2), 3: (leftshift its binary representation by

    1)

    4: (lots more)]  So a quotation in Joy is NOT a function, it is a program

    to compute a function.

      - Manfred

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

## Manfred Von Thun — 2008-03-19 10:05:51

    On 19/3/08 6:06 PM, "John Nowak" <john@...> wrote:

     >

    > On Mar 18, 2008, at 10:17 PM, Manfred Von Thun wrote:

    >

    >> quad turns [C:num, B:num, A:num | R] into [[P:num,N:num] list | R] :-

    >> Diff is B*B -$*A*C,

    >> (   Diff < 0.0,

    >> ->  write(quadratic: cannot take root of negative argument¹)

    >> ;   Root is sqrt(Diff),

    >>    P is (0-B+Root)/(2*A),

    >>    N is (0-B-Root)/(2*A)

    >> ).

    >

    > Here's another version of the above with a syntax more suited to a

    > concatenative language:

    >

    > quad a b c = p n

    >     where 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 /

    >

     Yes, I entirely agree. What I gave was the Prolog program, and if

    someone implementing a concatenative language has to choose

    a notation for arithmetic and other types, our form would be best.

    But to get the unification for the variables in the input and the

    output stacks, you have to write a little Prolog  and that is not so easy.

    So I just used an excellent existing Prolog, SWI-prolog.

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

## Christopher Diggins — 2008-03-19 14:33:48

    > 4: (lots more)] So a quotation in Joy is NOT a function, it is a program

    > to compute a function.

     I view a quotation to be a function that takes any stack and returns a

    copy of that stack with a function on top.

    I don't believe that this is an incorrect model.

    - Christopher

## John Cowan — 2008-03-19 17:31:25

    Manfred Von Thun scripsit:

     > 4: (lots more)]  So a quotation in Joy is NOT a function, it is a program

    > to compute a function.

     Scheme makes essentially the same distinction between a procedure (a

    piece of Scheme code), a closure (a run-time object binding a procedure

    to a lexical environment), and a function (a mathematical relation).

    OTOH, the closely related Common Lisp uses "function" for all three.

    --

    They do not preach                              John Cowan

      that their God will rouse them                cowan@...

        A little before the nuts work loose.        http://www.ccil.org/~cowan

    They do not teach

      that His Pity allows them                         --Rudyard Kipling,

        to drop their job when they damn-well choose.   "The Sons of Martha"

## Christopher Diggins — 2008-03-19 17:36:04

    > Scheme makes essentially the same distinction between a procedure (a

    > piece of Scheme code), a closure (a run-time object binding a procedure

    > to a lexical environment), and a function (a mathematical relation).

    > OTOH, the closely related Common Lisp uses "function" for all three.

     While the language description makes this distinction, but AFIAK the

    run-time semantics of Scheme do not make a distinction between these

    kinds of values.

    In other words you can't write code (in R5RS) that distinguishes

    whether a given value is a closure, a function or a procedure.

    - Christopher

## John Cowan — 2008-03-19 18:08:49

    Christopher Diggins scripsit:

     > In other words you can't write code (in R5RS) that distinguishes

    > whether a given value is a closure, a function or a procedure.

     Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific

    predicates).  Functions are abstracta, and don't have representations

    in Scheme.

    --

    I now introduce Professor Smullyan,             John Cowan

    who will prove to you that either               cowan@...

    he doesn't exist or you don't exist,            http://www.ccil.org/~cowan

    but you won't know which.                               --Melvin Fitting

## Christopher Diggins — 2008-03-19 18:27:39

    > > In other words you can't write code (in R5RS) that distinguishes

    > > whether a given value is a closure, a function or a procedure.

    >

    > Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific

    > predicates). Functions are abstracta, and don't have representations

    > in Scheme.

     That is interesting. I can't find in the specification

    (http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures

    must not satisfy "PAIR?". Can you point it out?

    - Christopher

## John Cowan — 2008-03-19 19:09:55

    Christopher Diggins scripsit:

     > > > In other words you can't write code (in R5RS) that distinguishes

    > > > whether a given value is a closure, a function or a procedure.

    > >

    > > Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific

    > > predicates). Functions are abstracta, and don't have representations

    > > in Scheme.

    >

    > That is interesting. I can't find in the specification

    > (http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures

    > must not satisfy "PAIR?". Can you point it out?

     3.2 says that PROCEDURE? and PAIR? are disjoint.  It's true that in R5RS

    "procedure" is used instead of "closure", but in talking about Scheme

    I usually hear "closure" for the object, and "procedure" for the text.

    --

    A mosquito cried out in his pain,               John Cowan

    "A chemist has poisoned my brain!"              http://www.ccil.org/~cowan

            The cause of his sorrow                 cowan@...

            Was para-dichloro-

    Diphenyltrichloroethane.                                (aka DDT)

## Christopher Diggins — 2008-03-19 19:17:41

    On Wed, Mar 19, 2008 at 3:09 PM, John Cowan <cowan@...> wrote:

     > Christopher Diggins scripsit:

    > > > > In other words you can't write code (in R5RS) that distinguishes

    > > > > whether a given value is a closure, a function or a procedure.

    > > >

    > > > Closures satisfy PROCEDURE?, procedures satisfy PAIR? (and more specific

    > > > predicates). Functions are abstracta, and don't have representations

    > > > in Scheme.

    > >

    > > That is interesting. I can't find in the specification

    > > (http://schemers.org/Documents/Standards/R5RS/r5rs.pdf) that closures

    > > must not satisfy "PAIR?". Can you point it out?

    >

    > 3.2 says that PROCEDURE? and PAIR? are disjoint. It's true that in R5RS

    > "procedure" is used instead of "closure", but in talking about Scheme

    > I usually hear "closure" for the object, and "procedure" for the text.

     And 4.1.4 is says that a lambda expression evaluates to a procedure.

    - Christopher