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 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
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