# Please ignore

## phimvt@lurac.latrobe.edu.au — 2003-04-23 07:53:36

    Sorry folks,

    I broke all my mail files and need something to reply to.

    Do not reply to this (unless you are me - if you know what I mean).

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2003-04-23 08:28:36

    Sorry about the mess.

    Thank you all for the help with the "#!" flag.  On the web page in

    j09imp.html ("The current implementation" Section 5 "Initating a Joy

    session")  I have added a paragraph about using it.  There is a tiny demo

    file "gcd" for computing the greatest common divisor from a command line.

    I have studied the recursion pattern of ackermann in some depth, and

    noticed a similarity with one of the algorithms for gray codes. I found

    that the technical term for this is "nested recursion"  (also "compound

    recursion").  It also occurs in several other functions which people have

    used to illustrate a point but which have no intrinsic use. Joy needs two

    more combinators, "nestrec" and "condnestrec", and I have a vague idea how

    they should be implemented.  I'll write more about this shortly.

    I will also reply to Nick's question about patterns and recursion

    combinators. Please be patient.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2003-04-24 06:26:28

    Thanks for the question, Nick, it prompted me to think long and hard. Part

    of the answer is this draft for two new questions for the Further FAQ,

    FFAQ (visible only from the FAQ - I should change that, parhaps).

    ------------------------------------------------------------------

    Q: Why does Joy have all those recursion combinators?

       Why not just use plain explicit recursion?

    A: In the 70's it was recognised that programs using structured IFs

    and WHILEs are easier to get right and easier to read than programs

    which use GOTOs and in which the pattern of the flow of control

    has to be inferred by laborious analysis.

    In the functional languages which use lists a lot much of list

    processing falls into a few recursion patterns which are often

    abstracted as combinators such as map, filter and fold, and

    also a few variants such as zipwith. Programs which use these

    combinators by name are easy to write and easier to read than

    programs in which the pattern of recursion on lists has to

    be inferred.

    Joy takes this idea a step further by combinators for recursion

    patterns that are independent of any particular datatype such

    as lists above. For linear recursion there is the combinator

    linrec, its special case tailrec, and even more special case

    while. There is also the more flexible condlinrec. For binary

    recursion there is the combinator binrec, but so far no more

    special or more flexible versions. For recursion with arbitrary

    n-ary branching there is the combinator genrec, so far with

    no variants. For recursion on trees of any type other than lists

    there are several combinators. For nested recursion (as in the

    Ackermann function) there will soon be two combinators nestrec

    and condnestrec. So far there are no combinators for mutual

    recursion. All these combinators are more intuitive and descriptive

    than the well-known "paradoxical" all-purpose recursion combinators

    (Curry's) Y and (Turing's) T which are frequently defined but

    never used because they are all-purpose and hence not descriptive.

    Of course the execution of programs without explicit GOTOs typically

    involves its use internally. Similarly, the execution of programs

    with recursion combinators but without explicit recursion typically

    involves its use internally. But programs using combinators are

    easier to write and read than ones using explicit recursion and

    in which the pattern of all, not just list, recursions has to be

    inferred. So, if you like, "Recursion considered harmful".

    As a bonus, at least for the current implementation, programs

    using recursion combinators are more efficient than programs

    using explicit recursion.

    ------------------------------------------------------------------

    I am fairly happy with the above. Any comments?

    The answers to the next question are very much more tentative.

    ------------------------------------------------------------------

    Q: So why don't other languages have recursion combinators ?

    A: For several, mostly independent reasons:

    1. Joy combinators take quotations as arguments. Other languages

    would have to use lambda abstractions instead. But many have no

    way of capturing the current environments.

    2. Apart from this, many languages could not even define a lambda

    counterpart of Joy's simple i combinator - the "dequotation combinator".

    This rules out most mainstream languages. Some counterpart might be

    definable in the Lisps, ML, Haskell and Prolog/

    3. Again indpendently, there will be a problem about Joy's simple

    branching combinator ifte. With "eager" evaluation it is not

    possible to define an ordinary function for branching, as Eva Lou

    Ator will tell you, in SICP p 23. Branching has to be done with

    "special forms" cond or if. To define them one needs delayed

    evaluation or macros. Since the recursion combinators all

    involve branching they need the same.

    4. The next hurdle concerns the number of extra parameters

    apart from the quotation parameters for combinators. In Joy

    all parameters, including extra ones just sit on the

    stack. A different language might do one of the following:

    (a) Have several versions of combinators for each possible

    number of extra parameters. (b) If possible, use whatever

    facility the language has for optional parameters, and put

    the extras there. (c) Rewrite all functions including combinators

    as taking a stack (a list) as their sole parameter.

    5. Some languages are strongly statically typed, perhaps

    in a polymorphic way. Finite unions can then solve the

    problem that combinators are supposed to take as parameters

    functions of all sorts of base types but also lists of

    these and lists of lists of base types and so on. But I don't

    know whether this can handle lists of mixtures of lists of

    mixtures when the entire mix is unknowable at compile time.

    There are languages in which the Y or T combinators can

    be defined, or at least collections of variants for different

    number of parameters of the recursing function. Presumably

    using similar techniques it is possible to define counterparts

    of the recursion combinators of Joy. But I have never seen

    such definitions, and hence never their routine use.

    ------------------------------------------------------------------

    Any comments? Any additions?

    Does anyone in the group know how to implement some not too

    trivial combinator in other languages? Recursion combinators

    other than Y or T?

    These Q&A's in no way reflect the history of how it all happened

    when designing Joy. In fact the history is an embarassing comedy

    of many errors and occasional serendipity.

    Thanks again for the question, Nick. I should make my answers

    to the first question part of the sales pitch.

      - Manfred

    Coming soon:

      Sample module libraries, one with "fake" export list

      More on nested recursion, Ackermann, non-recursive definition.

## Nick Forde — 2003-04-24 14:33:34

    Manfred,

    Thanks for your detailed response. I did a little web searching and

    came across one attempt at formalising recursive patterns in a similar

    way to the GoF Design Patterns I referenced in my last post.

    Roundabout - A Pattern Language for Recursive Programming,

    by Eugene Wallingford

    http://www.cs.uni.edu/~wallingf/patterns/recursion.html

    I've not yet looked in detail at the patterns in Roundabout but it

    would be an interesting exercise to see if they are easily implemented

    using the Joy combinators.

    Regards,

    Nick.

## phimvt@lurac.latrobe.edu.au — 2003-04-28 03:08:41

    On Thu, 24 Apr 2003, Nick Forde wrote:

     > Manfred,

    >

    > Thanks for your detailed response. I did a little web searching and

    > came across one attempt at formalising recursive patterns in a similar

    > way to the GoF Design Patterns I referenced in my last post.

     Thanks for that. My response to the pattern movement had been

    tepid until now, but after your mail I might well have another look.

     > Roundabout - A Pattern Language for Recursive Programming,

    > by Eugene Wallingford

    > http://www.cs.uni.edu/~wallingf/patterns/recursion.html

    >

    > I've not yet looked in detail at the patterns in Roundabout but it

    > would be an interesting exercise to see if they are easily implemented

    > using the Joy combinators.

     I was intrigued by E.W.'s "decorator pattern", e.g. in Joy syntax

        [Peter Paul Mary] dec   =>   [ [Peter 1] [Paul 2] [Mary 3] ]

    A trace of my thoughts: "That's just the map combinator ... no, the

    numbers have to change ... but map can do that, by leaving the counter

    below the list ... oops, no that didn't work ... just use linrec:

    DEFINE

        dec ==

    	0 swap

    	[ null ]

    	[ popd ]

    	[ [succ dup] dip uncons swapd ]

    	[ [swap [] cons cons] dip cons ]

    	linrec.

    Not as elegant as I had hoped for, too many dips, swaps, swapds.

    I would have preferred to be able to use something like map.

    Can anyone think of a better way ?

    Or does Joy need a map-like "decorator" combinator ?

    Thanks, Nick.

      - Manfred

## Nick Forde — 2003-04-28 12:34:26

    phimvt@... writes:

      > > Thanks for your detailed response. I did a little web searching and

     > > came across one attempt at formalising recursive patterns in a similar

     > > way to the GoF Design Patterns I referenced in my last post.

     >

     > Thanks for that. My response to the pattern movement had been

     > tepid until now, but after your mail I might well have another look.

     When I first read about design patterns I wasn't particularly

    impressed as they didn't really give me any new insights into OO

    design. I'd encountered many of the patterns over the years and the

    books seemed to only offer labels for patterns already in common use.

    In hindsight I was missing the point. Naming these patterns IS their

    benefit. I have colleagues on 4 continents and although we all

    communicate in English there are quite significant differences in

    approach to software design. Patterns really help us communicate

    during design and code reviews.

    In much the same way as functions, modules, or objects give a level of

    abstraction above individual statements or expressions I find design

    patterns to be a useful level of abstraction above objects. Of course

    ideally programmers wouldn't need patterns as they could be considered

    something for a compilers to extract. Some functional programming

    languages already offer this to an extent and hence patterns are

    perhaps of less use to the functional programmer. Or maybe its just

    that the patterns become more problem specific and less about a

    solution implementation?

      > > Roundabout - A Pattern Language for Recursive Programming,

     > > by Eugene Wallingford

     > > http://www.cs.uni.edu/~wallingf/patterns/recursion.html

     > >

     > > I've not yet looked in detail at the patterns in Roundabout but it

     > > would be an interesting exercise to see if they are easily implemented

     > > using the Joy combinators.

     >

     > I was intrigued by E.W.'s "decorator pattern", e.g. in Joy syntax

     >

     >     [Peter Paul Mary] dec   =>   [ [Peter 1] [Paul 2] [Mary 3] ]

     >

     > A trace of my thoughts: "That's just the map combinator ... no, the

     > numbers have to change ... but map can do that, by leaving the counter

     > below the list ... oops, no that didn't work ... just use linrec:

     >

     > DEFINE

     >     dec ==

     > 	0 swap

     > 	[ null ]

     > 	[ popd ]

     > 	[ [succ dup] dip uncons swapd ]

     > 	[ [swap [] cons cons] dip cons ]

     > 	linrec.

     >

     > Not as elegant as I had hoped for, too many dips, swaps, swapds.

     > I would have preferred to be able to use something like map.

     > Can anyone think of a better way ?

     > Or does Joy need a map-like "decorator" combinator ?

     I couldn't find a reference to this on Eugene's pages, have you a

    link?

    This is actually very similar to a problem I was pondering over the

    weekend. I was reading a bit about Paul Graham's programming language

    Arc (http://www.paulgraham.com/arcfaq.html) and came across his

    Accumulator Generator challenge:

    "Write a function foo that takes a number n and returns a function

    that takes a number i, and returns n incremented by i.  Note: (a)

    that's number, not integer, (b) that's incremented by, not plus."

      http://www.paulgraham.com/accgen.html

    I thought I'd submit a Joy implementation but it turned out to be a

    bit trickier than I first thought and I'm not sure I've got the best

    solution.

    As functions can't be dynamically defined in Joy I decided I needed to

    create an accumulator quotation which could be executed using the i

    combinator. Recalling the clever use of infra in "Recursion Theory and

    Joy" I constructed the following:

      [[n [i +] infra dup rest cons] [i +] infra dup rest cons]

    The function foo therefore needs to generate the above given an

    argument i and run with the argument n.

    The best implementation I could come up with was:

      DEFINE foo ==

        [+] cons [infra dup rest cons] cons

        [dupd swons swons].

    This can then be run as:

      1 foo 2 swap i i i.

      1 foo 'A swap 33 [i] times.

      0.5 foo 0.25 swap 10 [i] times.

    Giving:

      [[4 [1 +] infra dup rest cons] [1 +] infra dup rest cons]

      [['a [1 +] infra dup rest cons] [1 +] infra dup rest cons]

      [[4.75 [0.5 +] infra dup rest cons] [0.5 +] infra dup rest cons]

    Can anyone suggest a better alternative? Constructing a quine is a lot

    of effort to solve this problem and the solution is far from obvious! :-)

    I'd also prefer a more general purpose approach which would work with

    something more complex than a simple accumulator.

    Regards,

    Nick.

## phimvt@lurac.latrobe.edu.au — 2003-05-02 07:03:23

    On Mon, 28 Apr 2003, Nick Forde wrote:

     > phimvt@... writes:

    >  > Thanks for that. My response to the pattern movement had been

    >  > tepid until now, but after your mail I might well have another look.

    >

    > When I first read about design patterns I wasn't particularly

    > impressed as they didn't really give me any new insights into OO

    > design. I'd encountered many of the patterns over the years and the

    > books seemed to only offer labels for patterns already in common use.

    >

    > In hindsight I was missing the point. Naming these patterns IS their

    > benefit.

     Yes, that is the conclusion I reached when writing my previous note.

    The "structured flow of control" patterns IF, WHILE, REPEAT, CASE

    LOOP-and-a-half (with single exit somewhere) are useful, common,

    descriptive and adequate almost everywhere. Similarly the various

    recursion patterns for lists MAP FOLD FILTER, and I suspect the

    other more general recursion patterns are useful, common, descriptibe

    and adequate almost everywhere.

    What goes on in the mind of programmers I do not know, but having

    found the right (common) pattern, it helps to give it a name.

    It also helps future maintainers to "see the pattern" as fast

    as they can read its name.

     > patterns to be a useful level of abstraction above objects. Of course

    > ideally programmers wouldn't need patterns as they could be considered

    > something for a compilers to extract.

     I disagree with the "ideally" - as I would want to see it the

    names are there to help the human reader (the original programmer

    and later the unknown maintainer).

    [..]

     >  > I was intrigued by E.W.'s "decorator pattern", e.g. in Joy syntax

    >  >

    >  >     [Peter Paul Mary] dec   =>   [ [Peter 1] [Paul 2] [Mary 3] ]

    >  >

    >  > A trace of my thoughts: "That's just the map combinator ... no, the

    >  > numbers have to change ... but map can do that, by leaving the counter

    >  > below the list ... oops, no that didn't work ... just use linrec:

    >  >

    >  > DEFINE

    >  >     dec ==

    >  > 	0 swap

    >  > 	[ null ]

    >  > 	[ popd ]

    >  > 	[ [succ dup] dip uncons swapd ]

    >  > 	[ [swap [] cons cons] dip cons ]

    >  > 	linrec.

    >  >

    >  > Not as elegant as I had hoped for, too many dips, swaps, swapds.

    >  > I would have preferred to be able to use something like map.

    >  > Can anyone think of a better way ?

    >  > Or does Joy need a map-like "decorator" combinator ?

    >

    > I couldn't find a reference to this on Eugene's pages, have you a

    > link?

     How embarassing, try as I may, I cannot find it again. I must have

    followed an external link without paying attention. Sorry, no link.

     >

    > This is actually very similar to a problem I was pondering over the

    > weekend. I was reading a bit about Paul Graham's programming language

    > Arc (http://www.paulgraham.com/arcfaq.html) and came across his

    > Accumulator Generator challenge:

    >

    > "Write a function foo that takes a number n and returns a function

    > that takes a number i, and returns n incremented by i.  Note: (a)

    > that's number, not integer, (b) that's incremented by, not plus."

    >

    >   http://www.paulgraham.com/accgen.html

     [..]

    I haven't had time yet to look at this or to examine your solution.

    But I will give it some thought.

    [..]

    Incidentally, I have finished (in interp.c) the nested recursion

    combinator, and some demos - hanoi, graycodes, ackermann, e.g.

    the following non-recursive definition:

        ack ==

    	[ [ [pop null]  [popd succ] ]

    	  [ [null]  [pop pred 1]  [] ]

    	  [ [[dup pred swap] dip pred]  []  [] ] ]

    	condnestrec.

    Remember, the point of not needing the recursive definition is

    that one can use the code _without_ a definition, as in

            3 4

    	[ [ [pop null]  [popd succ] ]

    	  [ [null]  [pop pred 1]  [] ]

    	  [ [[dup pred swap] dip pred]  []  [] ] ]

    	condnestrec.

    I am writing this up with all sorts of variants, so it will take

    another week to get to the Joy web page.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2003-05-02 09:05:09

    On Mon, 28 Apr 2003, Nick Forde wrote:

    [..]

    > This is actually very similar to a problem I was pondering over the

    > weekend. I was reading a bit about Paul Graham's programming language

    > Arc (http://www.paulgraham.com/arcfaq.html) and came across his

    > Accumulator Generator challenge:

    >

    > "Write a function foo that takes a number n and returns a function

    > that takes a number i, and returns n incremented by i.  Note: (a)

    > that's number, not integer, (b) that's incremented by, not plus."

    >   http://www.paulgraham.com/accgen.html

    I found the specification of the problem quite inscrutable, and

    eventually understood it only when I read some of the solutions

    in various languages. Apparantly I am not alone:

    In the "listbox archives" at htp://www.kx.com/listbox.k/msg05906.html

    I found what confirmed my reaction:

    [...]

    Similarly the input is ambiguous, is "number n" a variable of type number; or s

    uch a variable _and_ an initial value; or just an initial value and use a priva

    te storage location (forget he even mentioned "n")? i suppose there is a better

     language to state problems in than English... Clearly a lot of other people ha

    d much less difficulty deciding what the heck he means than i. So maybe this is

     just one of my dense days. Or maybe it is just a chance for all us language bi

    gots to show off our best -- In which case i prefer

    [...]

    greg heil

    [END OF QUOTE]

    First, "returns a function": that rules out languages which do not treat

    functions as first class values. Next, "number, not integer": that

    requires not too-rigid-typing. Then, "incremented, not plus": only when I

    read the imperative "set!" in the Scheme version did it become clear to me

    what he had in mind. So ... the problem requires assignable variables in

    the language, perhaps? And therefore it cannot be done in Joy.  I am not

    so sure any more, mainly after reading your clever solution.

    > I thought I'd submit a Joy implementation but it turned out to be a

    > bit trickier than I first thought and I'm not sure I've got the best

    > solution.

    I cannot do justice to your solution now, but I'll think about it more.

    [..]

      - Manfred

## Nick Forde — 2003-05-02 09:33:46

    phimvt@... writes:

      > > "Write a function foo that takes a number n and returns a function

     > > that takes a number i, and returns n incremented by i.  Note: (a)

     > > that's number, not integer, (b) that's incremented by, not plus."

     >

     > >   http://www.paulgraham.com/accgen.html

     >

     > I found the specification of the problem quite inscrutable, and

     > eventually understood it only when I read some of the solutions

     > in various languages. Apparantly I am not alone:

     Yes, me too. Looking at some of the other solutions I now think my

    initial attempt was over engineered.

      > [..]

     > First, "returns a function": that rules out languages which do not treat

     > functions as first class values. Next, "number, not integer": that

     > requires not too-rigid-typing. Then, "incremented, not plus": only when I

     > read the imperative "set!" in the Scheme version did it become clear to me

     > what he had in mind. So ... the problem requires assignable variables in

     > the language, perhaps? And therefore it cannot be done in Joy.  I am not

     > so sure any more, mainly after reading your clever solution.

     Looking at some of the other solutions the following may be

    sufficient:

    DEFINE foo == [+] cons.

    7 foo 2 swap i.      # => 9

    4 foo 'A swap i.     # => 'E

    0.5 foo 0.25 swap i. # => 0.75

    This of course can only be executed once but may be all that is

    required(?).

      > > I thought I'd submit a Joy implementation but it turned out to be a

     > > bit trickier than I first thought and I'm not sure I've got the best

     > > solution.

     >

     > I cannot do justice to your solution now, but I'll think about it more.

     My last solution was emulating a global variable by implementing a

    self replicating function. I described this as follows in my last mail:

      [[n [i +] infra dup rest cons] [i +] infra dup rest cons]

    I've only just noticed this is very misleading. In the above 'n' and

    'i' refer to the variables mentioned in the problem text. e.g.

      [[1 [2 +] infra dup rest cons] [2 +] infra dup rest cons]

    If the short definition of foo above is sufficient then following Paul

    Graham's matra "Succinctness is Power"

    (http://www.paulgraham.com/power.html) this must surely make Joy the

    most powerful language around! :-)

    Regards,

    Nick.

## Nick Forde — 2003-05-02 13:15:43

    Nick Forde writes:

      > Looking at some of the other solutions the following may be

     > sufficient:

     >

     > DEFINE foo == [+] cons.

     >

     > 7 foo 2 swap i.      # => 9

     > 4 foo 'A swap i.     # => 'E

     > 0.5 foo 0.25 swap i. # => 0.75

     >

     > This of course can only be executed once but may be all that is

     > required(?).

     Here's a slightly better description of the problem:

       http://www.paulgraham.com/accgensub.html

       1.  Takes, and returns functions that take, exactly one argument.

       2. Works for any numeric type-- i.e. can take both ints and floats

          and returns functions that can take both ints and floats.

       3. Generates functions that return the sum of every number ever

          passed to them, not just the most recent.

    OK, so this rules out the above solution. Ignore what I said earlier :-)

       4. Returns a real function, meaning something that you can use

          wherever you could use a function you had defined in the

          ordinary way in the text of your program.

       5. Doesn't store the accumulated value or the returned functions in

          a way that could cause them to be inadvertantly modified by

          other code.

    So my best solution is still:

      DEFINE foo ==

        [+] cons [infra dup rest cons] cons

        [dupd swons swons].

    Are there no other takers? There must be a better Joy implementation

    than this. Also the first call to this function only initialises the

    accumulator, whereas it should actually execute the first accumulate

    operation.

    Cheers,

    Nick.

## Martin Young — 2003-05-02 15:28:03

    On Fri, 2003-05-02 at 14:15, Nick Forde wrote:

     > So my best solution is still:

    >

    >   DEFINE foo ==

    >     [+] cons [infra dup rest cons] cons

    >     [dupd swons swons].

    >

    > Are there no other takers? There must be a better Joy implementation

    > than this. Also the first call to this function only initialises the

    > accumulator, whereas it should actually execute the first accumulate

    > operation.

     The problem statement is still opaque to me so I've probably

    misunderstood.  Below is a solution (?) in Monkey (my Joy-alike) but the

    Joy version (untested) would be:

    DEFINE foo ==

      [ + foo ] cons .

    Or is explicit recursion not allowed?

    ----snip--snip----

    << -----------------------

       Accumulator generators.

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

    module main provides main .

                uses     io .

    << Entry point of program. >>

    main ==

    {{

        3 accgen         << First invocation >>

        dup . nl         << Show result (accum=3). >>

        1 swap i         << 2nd invocation. >>

        dup . nl         << Show result (accum=4). >>

        dup              << Keep a copy of this accumulator function. >>

        5 swap i         << Accumlate again. >>

        dup . 10 emit    << Show result (accum=9). >>

        drop             << Drop the last accumulator, revery to

                            previously saved one. >>

        2 swap i         << Acuum. again. >>

        dup . 10 emit    << Show result (accum=6). >>

    }}

    << The generator. >>

    accgen ==

    {{

        [ + accgen ] cons programise

    }}

    ----snip--snip----

    Output is:

    [my@upstairs MONKEY]$ ./monkey accgen.mmod

    Creating stub module definition for "main".

    Creating stub module definition for "io".

    Will scan "io".

    Creating stub module definition for "control".

    Will scan "control".

    { 3 + accgen }

    { 4 + accgen }

    { 9 + accgen }

    { 6 + accgen }

## Nick Forde — 2003-05-02 16:35:58

    Hi Martin,

    Martin Young writes:

      > On Fri, 2003-05-02 at 14:15, Nick Forde wrote:

     > > So my best solution is still:

     > >

     > >   DEFINE foo ==

     > >     [+] cons [infra dup rest cons] cons

     > >     [dupd swons swons].

     > >

     > > Are there no other takers? There must be a better Joy implementation

     > > than this. Also the first call to this function only initialises the

     > > accumulator, whereas it should actually execute the first accumulate

     > > operation.

     >

     > The problem statement is still opaque to me so I've probably

     > misunderstood.  Below is a solution (?) in Monkey (my Joy-alike) but the

     > Joy version (untested) would be:

     >

     > DEFINE foo ==

     >   [ + foo ] cons .

     Nice! I think this _is_ a valid solution.

    I've also just noticed that my solution returns i incremented by n

    rather than n incremented by i. Oops.

    If nothing else this problem certainly highlights how bad English is

    for specifying such challenges.

    Regards,

    Nick.

## phimvt@lurac.latrobe.edu.au — 2003-05-05 07:15:08

    On Fri, 2 May 2003, Nick Forde wrote:

    [.. a propos solutions to the "accumulator challenge" ..]

    > Yes, me too. Looking at some of the other solutions I now think my

    > initial attempt was over engineered.

    No, I think you were exactly right. Over the weekend I did some

    paper-and-pencil programming at home and came up with something

    very similar to what you had. It is also based on the true/false

    alternating self-reproducing program in "Recursion Theory ..",

    as you suggested. Here is what I came up with. (A small

    modification was needed for non-commutative operators like "cons":

    without the first line "[swap] swoncat" the definition of

    cons-accu would have to be "[] [swons] accu-make" which would have

    been more efficient but not as clean.)

    FILE accu.joy:

    -----------------------------------------------------------

    2 setecho.

    # accumulator challenge

    # accumulators are similar to folding a list (by + or by * etc)

    # so they should be constructed by the same program constructor

    # from a binary operator and a suitable initial (unit) element.

    # The operator accu-make does that. For example,

    #   0 [+] accu-make   ==>  [..0..]     and then

    #   11 22 33  [..0..]  i  i   ==>  [..55..]

    DEFINE

        dureco  ==  dup rest cons;

        accu-make  ==		#  U [B]

    	[swap] swoncat		#  U [swap B]

    	[infra dureco] cons	#  U [[swap B] infra dureco]

    	[cons] swoncat		#  U [cons [swap B] infra dureco]

    	cons			#  [U cons [swap B] infra dureco]

    	dureco			# [[U cons [swap B] infra dureco]

    	;			#     cons [swap B] infra dureco]

        sum-accu  ==   0 [+] accu-make;

        prod-accu  ==   1 [*] accu-make;

        cons-accu  ==   [] [cons] accu-make;

    END.

    2 3 4 5 6  sum-accu  i i i . . . . .

    1.1  2.1  3.1  4.1   prod-accu  i i i  . . . . .

    11  22  33  44  55  cons-accu  i i i . . .

    -----------------------------------------------------------

    Enjoy. Slow? Well, yes. Useful? Who knows!

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2003-05-07 10:19:55

    On Thu, 24 Apr 2003 phimvt@... wrote:

    [...]

    > Coming soon:

        [...]

    >   More on nested recursion, Ackermann, non-recursive definition.

    07-MAY  On the Joy page, NEW:

       A (longish) note on nested recursion, several examples, several styles.

       A new combinator "condnestrec" (similar to condlinrec) in interp.c

    And belatedly, happy birthday concatenative !  (Thanks Billy)

      - Manfred

## John Cowan — 2003-05-08 21:08:55

    phimvt@... scripsit:

     > 07-MAY  On the Joy page, NEW:

    >    A (longish) note on nested recursion, several examples, several styles.

    >    A new combinator "condnestrec" (similar to condlinrec) in interp.c

     Very cool stuff.

    I am now beginning to play around with a Joy implementation in

    Scheme.  The current C implementation is usable, but it is not beautiful code,

    and it is quite difficult to learn and modify.  A R5RS Scheme implementation

    can be both, which will make it much more useful pedagogically.

    It will be very easy to add an integrator that expands embedded words

    recursively (stopping when *explicit* recursion occurs, of course, to

    avoid an infinite generation).  Furthermore, a trivial compiler from Joy to

    Scheme will be simple to add to the implementation.

    I will be using Petite Chez Scheme 6.0 to implement; there should only be a

    small number of functions that are Chez-specific (property lists and boxes,

    basically).

    Here is the (not yet debugged) main loop of the Joy interpreter.

    It's important to remember that Scheme implementations are required

    to be properly tail-recursive.

    ;; Execute a Joy quotation

    (define (joy q)

      (cond

        ((null? q) (if joy-undeferror (error "Undefined quotation") #f))

        ((pair? q) (joy-exec (car q)) (joy (cdr q))

        (else (error "Attempt to execute non-quotation"))))

    ;; Execute a Joy term

    (define (joy-exec e)

      (if (symbol? e) (joy-invoke (joy-lookup e)) (joy-push! e)))

    ;; Invoke a Joy or Scheme procedure

    (define (joy-invoke p)

      (if (procedure? p) (p) (joy p)))

    --

    Deshil Holles eamus.  Deshil Holles eamus.  Deshil Holles eamus.

    Send us, bright one, light one, Horhorn, quickening, and wombfruit. (3x)

    Hoopsa, boyaboy, hoopsa!  Hoopsa, boyaboy, hoopsa!  Hoopsa, boyaboy, hoopsa!

      -- Joyce, _Ulysses_, "Oxen of the Sun"       jcowan@...

## phimvt@lurac.latrobe.edu.au — 2003-05-09 06:29:20

    On Wed, 7 May 2003 phimvt@... wrote:

     > 07-MAY  On the Joy page, NEW:

    >    A (longish) note on nested recursion, several examples, several styles.

    >    A new combinator "condnestrec" (similar to condlinrec) in interp.c

     It was pointed out to me that the top-of-page banner and the

    botton-of-page banner make some of my web pages hard to read.

    History:

    For years I have been fighting various generations of "webmasters"

    who tell me that ALL (repeat:  AA-LL-LL) La Trobe pages MUST display

    those silly banners. ...corporate image.. and so on. After some

    heated discussion they agree to leave at least my non-html pages

    alone (well what would your C-compiler say to those 3 pages of

    Java and .pdf stuff needed to produce such banners ???).

    The last occasion was 6 months ago, when I had to spend time to

    delete all that junk.

    But recently I noticed something weird: now the devil does not actually

    change my files, it is the web server that inserts the junk dynamically.

    So, looking at the file (with, say, vi) when logged in, the junk

    is not there. But looking at the "source" from a browser, the junk

    is there. No wnder I am getting very confused.

    Here is today's miracle conversation:

    Manfred:

      "I wish your server would not insert stuff when displaying my files ..."

    Administrator:

      "...corporate image... university policy..."

    Repeat the above 10 times, with minor variations.

    Manfred:

      "But my readers get annoyed by that. They are grown-ups"

    Administrator:

      "Oh, .. oh.  Yes, well. Sure."

      To the man in the next room:

        "Bruce. Can you put this directory on the exception list?"

    30 seconds later: all my problems fixed.

    Yes, Virginia, miracles do happen.

    Greetings, my grown-up friends.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2003-05-09 09:39:54

    On Thu, 8 May 2003, John Cowan wrote:

    [...]

    > I am now beginning to play around with a Joy implementation in

    > Scheme.  The current C implementation is usable, but it is not beautiful code,

    > and it is quite difficult to learn and modify.

    Alas, yes. I have on occasions thought about a cleaner and more

    flexible implementation, but it is all rather vague.

    And that reminds me: I have been asked about Joy running under windows:

    a) does it work? Any porting problems?  b) would anyone be able to

    supply the executable for somebody who does not have a C for windows?

    >                                              A R5RS Scheme implementation

    > can be both, which will make it much more useful pedagogically.

    Yes, indeed. (I suppose you have looked at my antique version

    of mini-Joy in Common Lisp, somewhere on the Joy page under the

    "other implementations" heading.

    > It will be very easy to add an integrator that expands embedded words

    > recursively (stopping when *explicit* recursion occurs, of course, to

    > avoid an infinite generation).

    Two or three years ago there was some discussion on this group

    whether this is desirable. Some argued it is not. You might be

    able to find it, somebody might have a better memory than I.

    >                           Furthermore, a trivial compiler from Joy to

    > Scheme will be simple to add to the implementation.

    >

    > I will be using Petite Chez Scheme 6.0 to implement; there should only be a

    > small number of functions that are Chez-specific (property lists and boxes,

    > basically).

    I have not looked at Siod for years - does anyone have thoughts on Siod as

    an implementation language? It is suposed to be so small at least the very

    early versions were.  [This is relevant because if the implementation

    language (C vs Scheme)  requires too much effort to set up, much of the

    advantage is lost.] Maybe we'll hear more about the ocaml implementation

    and also an Oberon implementation.

      - Manfred

## John Cowan — 2003-05-09 14:23:15

    phimvt@... scripsit:

     > And that reminds me: I have been asked about Joy running under windows:

     Someone sent me an executable, dated 5 June 2001, so it does not have the

    latest fixes.  The URL is http://www.ccil.org/~cowan/joy1.exe ; feel free

    to copy this to the main site.

     > Yes, indeed. (I suppose you have looked at my antique version

    > of mini-Joy in Common Lisp, somewhere on the Joy page under the

    > "other implementations" heading.

     A long time ago, but I'm trying to write a clean-room version of Joy, not

    looking at any implementation at all, even the C one, but just working from

    your papers and my general memory of what Joy is about.

    I will write a Joy-syntax to Scheme-syntax translator, probably in Perl.

    Syntax is grotty, so it's appropriate to use a grotty language to fix it up.  :-)

     > > It will be very easy to add an integrator that expands embedded words

    > > recursively (stopping when *explicit* recursion occurs, of course, to

    > > avoid an infinite generation).

    >

    > Two or three years ago there was some discussion on this group

    > whether this is desirable. Some argued it is not. You might be

    > able to find it, somebody might have a better memory than I.

     It was indeed argued, but nobody had one, so the argument was more or less

    moot.  By providing one, we can play around with it.

     > I have not looked at Siod for years - does anyone have thoughts on Siod as

    > an implementation language? It is suposed to be so small at least the very

    > early versions were.

     The SIOD home page has vanished, and I can't find any other, so I don't know

    about its R5RS compliance.  There are lots of Schemes, proprietary and open

    source, at schemers.org; I chose Petite Chez because it is free (as in beer)

    though not open source, and it's close to the highly respected Chez

    implementation (basically lacks only the Scheme compiler).

    --

    Where the wombat has walked,            John Cowan <jcowan@...>

    it will inevitably walk again.          http://www.ccil.org/~cowan

## Stevan Apter — 2003-05-09 15:58:33

    thanks john.  finally, i'm able to actually run joy ...

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

    From: "John Cowan" <cowan@...>

    To: <concatenative@yahoogroups.com>

    Sent: Friday, May 09, 2003 10:23 AM

    Subject: Re: [stack] Joy in Scheme (was: patterns and recursion combinators)

    > phimvt@... scripsit:

    >

    > > And that reminds me: I have been asked about Joy running under windows:

    >

    > Someone sent me an executable, dated 5 June 2001, so it does not have the

    > latest fixes.  The URL is http://www.ccil.org/~cowan/joy1.exe ; feel free

    > to copy this to the main site.

    >

    > > Yes, indeed. (I suppose you have looked at my antique version

    > > of mini-Joy in Common Lisp, somewhere on the Joy page under the

    > > "other implementations" heading.

    >

    > A long time ago, but I'm trying to write a clean-room version of Joy, not

    > looking at any implementation at all, even the C one, but just working

    from

    > your papers and my general memory of what Joy is about.

    >

    > I will write a Joy-syntax to Scheme-syntax translator, probably in Perl.

    > Syntax is grotty, so it's appropriate to use a grotty language to fix it

    up.  :-)

    >

    > > > It will be very easy to add an integrator that expands embedded words

    > > > recursively (stopping when *explicit* recursion occurs, of course, to

    > > > avoid an infinite generation).

    > >

    > > Two or three years ago there was some discussion on this group

    > > whether this is desirable. Some argued it is not. You might be

    > > able to find it, somebody might have a better memory than I.

    >

    > It was indeed argued, but nobody had one, so the argument was more or less

    > moot.  By providing one, we can play around with it.

    >

    > > I have not looked at Siod for years - does anyone have thoughts on Siod

    as

    > > an implementation language? It is suposed to be so small at least the

    very

    > > early versions were.

    >

    > The SIOD home page has vanished, and I can't find any other, so I don't

    know

    > about its R5RS compliance.  There are lots of Schemes, proprietary and

    open

    > source, at schemers.org; I chose Petite Chez because it is free (as in

    beer)

    > though not open source, and it's close to the highly respected Chez

    > implementation (basically lacks only the Scheme compiler).

    >

    > --

    > Where the wombat has walked,            John Cowan

    <jcowan@...>

    > it will inevitably walk again.          http://www.ccil.org/~cowan

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## Nick Forde — 2003-05-09 15:47:31

    > > 07-MAY  On the Joy page, NEW:

    > >    A (longish) note on nested recursion, several examples, several styles.

    > >    A new combinator "condnestrec" (similar to condlinrec) in interp.c

    > >

    > Very cool stuff.

     I agree. I'm still getting my head around it!

     > I am now beginning to play around with a Joy implementation in

    > Scheme.  The current C implementation is usable, but it is not beautiful code,

    > and it is quite difficult to learn and modify.  A R5RS Scheme implementation

    > can be both, which will make it much more useful pedagogically.

     Great. A Scheme implementation would be much more elegant than the

    current C interpreter, although without compiling the Scheme code to C

    the need to install Petite Chez or equivalent does make it a bit more

    difficult to start experimenting with Joy.

    John Cowan writes:

      > I will write a Joy-syntax to Scheme-syntax translator, probably in Perl.

     > Syntax is grotty, so it's appropriate to use a grotty language to fix it up.  :-)

     Why do you need a translator? Is it to convert the Joy libraries into

    Scheme? Or do you intend your scheme implementation of Joy to use a

    different syntax?

    One approach I've been toying with is to write a lightweight minimal

    Joy interpreter for bootstraping a Joy implementation written in

    Joy. I've not yet had much free time to work on this but think a Joy

    language specification written in Joy would be really cool. It's also

    an interesting exercise to come up with the core Joy primitives as it

    becomes desirable to make them more flexible through polymorphism. Of

    course the tough part will be writing the combinators, but Brent's work

    in this area is a great start.

    Regards,

    Nick.

## John Cowan — 2003-05-09 18:43:43

    Nick Forde scripsit:

     > Great. A Scheme implementation would be much more elegant than the

    > current C interpreter, although without compiling the Scheme code to C

    > the need to install Petite Chez or equivalent does make it a bit more

    > difficult to start experimenting with Joy.

     Well, it depends on your environment: Unixes tend to come with gcc but not

    Scheme, so there is that hurdle to get over; still, the RPM package and

    the "./configure; make; make install" dance aren't really that hard.

    Eventually using Scheme->C and releasing the (very ugly) C is also a

    possibility, although AFAIK no one has updated Scheme->C to R5RS.

     > Why do you need a translator? Is it to convert the Joy libraries into

    > Scheme? Or do you intend your scheme implementation of Joy to use a

    > different syntax?

     I'm going to use Scheme syntax: parens instead of brackets, #t and #f instead

    of true and false, basically.  In addition, it turns out that one never needs

    to clearly differentiate between sets and lists, so I'm going to use lists

    to implement sets.  This mostly means that and, or, and xor need to sort

    their inputs, which is a Good Idea anyhow, and will allow sets to contain

    anything, not just 0-31.

    The translator will mostly be for the libraries, and it should be dead trivial

    in Perl.

     > One approach I've been toying with is to write a lightweight minimal

    > Joy interpreter for bootstraping a Joy implementation written in

    > Joy.

     A very interesting idea!  I'm also thinking about doing Joy in Java, taking

    advantage of the native polymorphism.

    --

    Yes, chili in the eye is bad, but so is your    John Cowan

    ear.  However, I would suggest you wash your    jcowan@...

    hands thoroughly before going to the toilet.    http://www.reutershealth.com

            --gadicath                              http://www.ccil.org/~cowan

## John Hodge — 2003-05-09 23:24:37

    --- In concatenative@yahoogroups.com, John Cowan <cowan@c...> wrote:

     > Nick Forde scripsit:

    >

    > > Great. A Scheme implementation would be much more elegant than the

    > > current C interpreter, although without compiling the Scheme code

     to C

     > > the need to install Petite Chez or equivalent does make it a bit

     more

     > > difficult to start experimenting with Joy.

    >

    > Well, it depends on your environment: Unixes tend to come with gcc

     but not

     > Scheme, so there is that hurdle to get over; still, the RPM package

     and

     > the "./configure; make; make install" dance aren't really that hard.

    > Eventually using Scheme->C and releasing the (very ugly) C is also a

    > possibility, although AFAIK no one has updated Scheme->C to R5RS.

    >

     [snip]

    Have you checked out Bigloo Scheme?  I believe it is compiled

    directly into C.  It's free, has .rpm's for several varieties of

    Linux and Unix, and has a plethora of built-in tools for parsing.

    Also, you might consider embedding Joy in Scheme, the same way that

    many Lisp programmers have embedded Prolog in Lisp: using macros to

    create a language that is semantically Joy while at the same time

    syntactically Scheme.  This technique also allows one to do some

    partial evaluation at macro-expansion-time.  There is quite a bit of

    material on embedded languages in Paul Graham's book, _On Lisp_.

    -Hodge

## John Cowan — 2003-05-10 00:28:59

    John Hodge scripsit:

     > Have you checked out Bigloo Scheme?  I believe it is compiled

    > directly into C.  It's free, has .rpm's for several varieties of

    > Linux and Unix, and has a plethora of built-in tools for parsing.

     Excellent point.  When I get the implemention done in Petite, I'll grab

    Bigloo and generate myself some C.

     > Also, you might consider embedding Joy in Scheme, the same way that

    > many Lisp programmers have embedded Prolog in Lisp: using macros to

    > create a language that is semantically Joy while at the same time

    > syntactically Scheme.

     Exactly what I have in mind:

    (j 32 45 +)

    (joydef swons swap cons)

    (joyprim2 swons (x y) (cons y x))

     > material on embedded languages in Paul Graham's book, _On Lisp_.

     I'm reading it even as we speak.

    --

    Híggledy-pìggledy / XML programmers       John Cowan

    Try to escape those / I-eighteen-N woes;        http://www.ccil.org/~cowan

    Incontrovertibly / What we need more of is      http://www.reutershealth.com

    Unicode weenies and / François Yergeaus.     jcowan@...

## Ben — 2003-05-10 00:53:15

    John Cowan wrote:

     > phimvt@... scripsit:

     [snip]

     >>I have not looked at Siod for years - does anyone have thoughts on Siod as

    >>an implementation language? It is suposed to be so small at least the very

    >>early versions were.

    >

    > The SIOD home page has vanished, and I can't find any other, so I don't know

    > about its R5RS compliance.  There are lots of Schemes, proprietary and open

    > source, at schemers.org; I chose Petite Chez because it is free (as in beer)

    > though not open source, and it's close to the highly respected Chez

    > implementation (basically lacks only the Scheme compiler).

        Ah, finally something I'm qualified to speak about around here  ;)

       (1996)      http://www.cs.indiana.edu/scheme-repository/imp/siod.html

       (1997)      http://people.delphiforums.com/gjc/siod.html

       (Win32)     http://people.delphiforums.com/gjc/winsiod.html

       (WinCE)     http://www.mazama.net/scheme/pscheme.htm

       (Win32 FFI) http://www.angelfire.com/wa/brianbec/siodffi.html

       The latest Win32 version of SIOD apparently is still striving towards

    R4RS compliance, let alone R5RS. Hygienic macros may not be feasible

    therein, unfortunately.

    	Ben

## John Hodge — 2003-05-10 01:31:22

    --- In concatenative@yahoogroups.com, John Cowan <cowan@c...> wrote:

     > John Hodge scripsit:

    >

    > > Have you checked out Bigloo Scheme?  I believe it is compiled

    > > directly into C.  It's free, has .rpm's for several varieties of

    > > Linux and Unix, and has a plethora of built-in tools for parsing.

    >

    > Excellent point.  When I get the implemention done in Petite, I'll

     grab

     > Bigloo and generate myself some C.

    >

    > > Also, you might consider embedding Joy in Scheme, the same way

     that

     > > many Lisp programmers have embedded Prolog in Lisp: using macros

     to

     > > create a language that is semantically Joy while at the same time

    > > syntactically Scheme.

    >

    > Exactly what I have in mind:

    >

    > (j 32 45 +)

    > (joydef swons swap cons)

    > (joyprim2 swons (x y) (cons y x))

    >

    > > material on embedded languages in Paul Graham's book, _On Lisp_.

    >

    > I'm reading it even as we speak.

    >

     Great!  The chapter on embedding Prolog is toward the back of the

    book ;)  Amazingly, Graham implements the entire language in a few

    hundred lines of unobfuscated code.

    I had been thinking of embedding Joy in Lisp also.  One idea that

    intrigued me was to implement Joy programs as Lisp metaprograms--that

    is, as macros.  There's the problem of the stack, though: macros

    aren't first class values and can't be passed as parameters; so, how

    does one go about creating a "meta-stack"?  I keep thinking there

    must be an obvious and elegant solution to that problem, but it

    always seems to be just out of my reach.  Perhaps it will occur to

    you.

    -Hodge

## John Cowan — 2003-05-10 04:03:36

    John Hodge scripsit:

     > I had been thinking of embedding Joy in Lisp also.  One idea that

    > intrigued me was to implement Joy programs as Lisp metaprograms--that

    > is, as macros.  There's the problem of the stack, though: macros

    > aren't first class values and can't be passed as parameters; so, how

    > does one go about creating a "meta-stack"?

     I sure don't see any way to do it using only R5RS hygienic macros.  So far

    my only deviation from R5RS is that in the Chez implementation symbols

    have property lists, and I'm using the 'joy and 'joydesc properties to

    store the Joy definitions and descriptions of Joy operators.  This could

    be done with a couple of hashtables in another Scheme, or for that matter

    totally portably in with a couple of a-lists (ugh, slow).

    The stack is simply a variable, joy-stack.  I was thinking about having a

    macro that fluidly binds the stack to () and then runs specified Joy code.

    (It suffices to bind to (), because if you want anything on the stack

    you can do the work in Joy rather than using Scheme to prearrange it.)

    But then "infra" does that, so maybe it just doesn't matter what is

    on the stack already: push what you want and use infra to do the work.

    And of course if the work is hard, add a new Joy primitive.

    --

    John Cowan                              <jcowan@...>

    http://www.ccil.org/~cowan              http://www.reutershealth.com

    Unified Gaelic in Cyrillic script!

            http://groups.yahoo.com/group/Celticonlang

## Steven Shaw — 2003-05-10 04:23:34

    > The SIOD home page has vanished, and I can't find any other, so I don't

     know

     > about its R5RS compliance.

     Pretty sure the most up-to-date page is

    http://people.delphiforums.com/gjc/siod.html.

    Another Scheme implementation in a similar vein is Gauche. I've only

    recently come across this one. It is R5RS.

        http://www.shiro.dreamhost.com/scheme/gauche/

    When the implementation is ready, I'd be happy to test with PLT-Scheme.

    Steve.

## John Cowan — 2003-05-10 04:58:56

    Steven Shaw scripsit:

     > Pretty sure the most up-to-date page is

    > http://people.delphiforums.com/gjc/siod.html.

     Ah, thanks.  As someone else said, not even R4RS here.

     > Another Scheme implementation in a similar vein is Gauche. I've only

    > recently come across this one. It is R5RS.

     Excellent.

     > When the implementation is ready, I'd be happy to test with PLT-Scheme.

     Even better!

    --

    Is a chair finely made tragic or comic? Is the          John Cowan

    portrait of Mona Lisa good if I desire to see           jcowan@...

    it? Is the bust of Sir Philip Crampton lyrical,         www.ccil.org/~cowan

    epical or dramatic?  If a man hacking in fury           www.reutershealth.com

    at a block of wood make there an image of a cow,

    is that image a work of art? If not, why not?               --Stephen Dedalus