John Cowan — 2006-03-23 20:14:48

As some of you know, I've been working for a long time on a replacement
interpreter for Joy in Chicken Scheme. I chose Chicken because its
compiler generates C which can be compiled stand-alone, so we can maintain
the program in Scheme (very clean and pretty, unlike the existing C)
and then distribute it as C (even uglier than the existing C). Of course
the Scheme implementation would be made available as well.

I'm now at the point where I want to implement Joy sets. The obvious
approach is to use a Chicken integer wrapped in a structure, as the C
interpreter does. However, a native Chicken integer is only 31 bits
long (or 63 bits on 64-bit architectures).

Unfortunately, the standard setlib.joy assumes at least 32-bit sets are
provided by the implementation. As a result, it allows the manipulation
of truth tables with up to five variables. Limiting sets to 31 elements
would constrain the library to four variables only.

There is a Chicken extension that supports arbitrary-precision integers,
but they are fairly expensive to use.

What do people recommend?

--
In politics, obedience and support John Cowan <cowan@...>
are the same thing. --Hannah Arendt http://www.ccil.org/~cowan

sa@dfa.com — 2006-03-23 20:31:19

use the extension, conform to the spec.

concatenative@yahoogroups.com wrote on 03/23/2006 03:14:48 PM:

> As some of you know, I've been working for a long time on a replacement
> interpreter for Joy in Chicken Scheme. I chose Chicken because its
> compiler generates C which can be compiled stand-alone, so we can

maintain

> the program in Scheme (very clean and pretty, unlike the existing C)
> and then distribute it as C (even uglier than the existing C). Of course
> the Scheme implementation would be made available as well.
>
> I'm now at the point where I want to implement Joy sets. The obvious
> approach is to use a Chicken integer wrapped in a structure, as the C
> interpreter does. However, a native Chicken integer is only 31 bits
> long (or 63 bits on 64-bit architectures).
>
> Unfortunately, the standard setlib.joy assumes at least 32-bit sets are
> provided by the implementation. As a result, it allows the manipulation
> of truth tables with up to five variables. Limiting sets to 31 elements
> would constrain the library to four variables only.
>
> There is a Chicken extension that supports arbitrary-precision integers,
> but they are fairly expensive to use.
>
> What do people recommend?
>
> --
> In politics, obedience and support John Cowan <cowan@...>
> are the same thing. --Hannah Arendt http://www.ccil.org/~cowan
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>

John Cowan — 2006-03-23 20:41:41

sa@... scripsit:

> use the extension, conform to the spec.

Alas, it's not so simple. The Joy papers explicitly say that the maximum
size of a set is implementation-dependent, so 31-bit sets are in fact
conformant. The paper on sets assumes, without requiring, that sets
(which it calls "small sets") are fast. Bignums aren't fast.

--
Samuel Johnson on playing the violin: John Cowan
"Difficult do you call it, Sir? cowan@...
I wish it were impossible." http://www.ccil.org/~cowan

William Tanksley, Jr — 2006-03-23 22:48:08

John Cowan <cowan@...> wrote:

> sa@... scripsit:

> > use the extension, conform to the spec.

> Alas, it's not so simple. The Joy papers explicitly say that the maximum
> size of a set is implementation-dependent, so 31-bit sets are in fact
> conformant. The paper on sets assumes, without requiring, that sets
> (which it calls "small sets") are fast. Bignums aren't fast.

Urk. Not to mention that giving MORE bits would make programs written
for Chicken-Joy not compatible with C-Joy.

I'm in favor of unlimited bits, though, and thus bignums. One thought:
you might consider changing the specification of Joy so that for any
set, the maximum number of elements must be configured at set creation
time, thus allowing the possibility of fast specializations when and
if they're needed/possible.

> Samuel Johnson on playing the violin: John Cowan

-Billy

Manfred Von Thun — 2006-03-24 08:20:02

These are difficult questions. I seem to remember about 20 years ago there
was a lot of discussion about the advantages of tagged architectures, in
which ever computer word (of 32 or so bits) has some additional tags bits
for all sorts of useful purposes. Looks like Scheme really wants something
like that, and any Scheme-to-C translator will have just this problem.

When Pascal became available on the DEC10 and later on the VAX, sets had up
to 64 members, obviously using two 32 bit words. But there was immediate
criticism that 64 is too small, and that any implementation should provide
at least SET OF char, of 128 or even 256 members. I toyed with the idea of
256 members for Joy by having either a list of length 8, each of 32 bits, or
a similar array of length 8 (with some complications for the garbage
collector), or somehow use strings to encode small sets of that size (and
like normal strings, not to have them collected)). But I gave up on all
these ideas because small sets of small numbers were really quite peripheral
to the main idea of Joy. I did look at possible implementations of arbitrary
sized sets of arbitrary elements, but only got as far as an ordered list
implementation (a binary tree implementation is usually recommended as being
better).

For your chicken implementation, I think you might also keep in mind that
small sets of small numbers are indeed peripheral to Joy, and that up to 31
members is almost as good as 32. It is only for the fast truth table
implementation that it really makes a difference of only 4 versus 5. The
fast small truth table program was really only a proof of concept, I doubt
whether anyone would really want to use Joy to run it in preference to the
truth tree (semantic tableaux) program for formulas of (essentially)
unlimited number of variables.

I did not know that you were still working on this project, and I am very
pleased to hear about your progress. Getting a very new implementation with
all its advantages is surely more important than allowing truth tables with
only 16 as opposed to 32 lines.

But there is one question I want to ask here, and it concerns a programming
technique in Joy that the various libraries use a fair bit: what in the
documentation is called ³using constructed programs². There is some value on
the stack, an incomplete quotation is pushed, and then the value is consed
into the quotation, to be used by a combinator. I was always afraid that
this technique might not be possible in a compiled implementation, or that
at least it would mean that the two (before and after the consing)
quotations cannot be compiled in the way most others can. Would you care to
comment on this, please?

Thank you very much for maintaining an interest in Joy, and for working on
a more maintainable source. I look forward to seeing more of it.

And thanks to Stevan and Billy for their comments on this, too.

- Manfred

On 24/3/06 7:14 AM, "John Cowan" <cowan@...> wrote:

> As some of you know, I've been working for a long time on a replacement
> interpreter for Joy in Chicken Scheme. I chose Chicken because its
> compiler generates C which can be compiled stand-alone, so we can maintain
> the program in Scheme (very clean and pretty, unlike the existing C)
> and then distribute it as C (even uglier than the existing C). Of course
> the Scheme implementation would be made available as well.
>
> I'm now at the point where I want to implement Joy sets. The obvious
> approach is to use a Chicken integer wrapped in a structure, as the C
> interpreter does. However, a native Chicken integer is only 31 bits
> long (or 63 bits on 64-bit architectures).
>
> Unfortunately, the standard setlib.joy assumes at least 32-bit sets are
> provided by the implementation. As a result, it allows the manipulation
> of truth tables with up to five variables. Limiting sets to 31 elements
> would constrain the library to four variables only.
>
> There is a Chicken extension that supports arbitrary-precision integers,
> but they are fairly expensive to use.
>
> What do people recommend?

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

John Cowan — 2006-03-24 13:51:51

Manfred Von Thun scripsit:

> When Pascal became available on the DEC10 and later on the VAX, sets had up
> to 64 members, obviously using two 32 bit words. But there was immediate
> criticism that 64 is too small, and that any implementation should provide
> at least SET OF char, of 128 or even 256 members.

Of course, that would be tough in the Unicode world, with a theoretical
maximum of 17 * 2^16 = 1,114,112 characters!

> For your chicken implementation, I think you might also keep in mind that
> small sets of small numbers are indeed peripheral to Joy, and that up to 31
> members is almost as good as 32.

Last night it occurred to me that I could use Chicken's support for vectors
of 16-bit integers, which would probably make Billy happy. Based on this,
though, I'll go with a plain Chicken integer wrapped in a trivial structure.

> I did not know that you were still working on this project, and I am very
> pleased to hear about your progress. Getting a very new implementation with
> all its advantages is surely more important than allowing truth tables with
> only 16 as opposed to 32 lines.

I had shelved it for a long time, but I got interested in it again.

> I was always afraid that this technique might not be possible in a
> compiled implementation, or that at least it would mean that the two
> (before and after the consing) quotations cannot be compiled in the
> way most others can. Would you care to comment on this, please?

I must have misled you. The new implementation will not be a Joy compiler,
any more than the old one was. It will itself be compiled, but will
implement an interpreter.

It's simply that compiling the interpreter will now be a two-step process:
compile Scheme to C and C to machine code. Chicken makes all this very
easy, including distributing the C form (just don't try reading it).
Currently I am running the Joy interpreter under the Scheme interpreter
that comes with Chicken, which works perfectly well; of course it is
much slower.

> Thank you very much for maintaining an interest in Joy, and for working on
> a more maintainable source. I look forward to seeing more of it.

You can see the current state of the source at
http://ccil.org/~cowan/joy.ss . Loading this into a Scheme interpreter
will produce a running Joy system, except that you have to use
Lispy syntax (use parens instead of brackets and wrap everything in an
outer layer of parens). Any error, though, will drop you back into
the Scheme interpreter; you can resume by evaluating "(joy-repl)".

> And thanks to Stevan and Billy for their comments on this, too.

Indeed.

--
John Cowan cowan@... www.ccil.org/~cowan www.ap.org
In the sciences, we are now uniquely privileged to sit side by side
with the giants on whose shoulders we stand.
--Gerald Holton

Greg Buchholz — 2006-03-24 17:44:32

--- Manfred Von Thun <m.vonthun@...> wrote:

>
> But there is one question I want to ask here, and it concerns a
> programming technique in Joy that the various libraries use a fair bit:
> what in the documentation is called ³using constructed programs². There

> some value on the stack, an incomplete quotation is pushed, and then

the

> value is consed into the quotation, to be used by a combinator. I was
> always afraid that this technique might not be possible in a compiled
> implementation, or that at least it would mean that the two (before and
> after the consing) quotations cannot be compiled in the way most others
> can. Would you care to comment on this, please?

The problem isn't with "cons", it's with "uncons" and friends. The
Joy language doesn't distinguish between lists and functions, which is
very different from how most compiled languages work. A quotation in Joy
like...

[1 + 2 * dup *]

...can be thought of in two ways. As a composition of functions, which
when applied to a number (say using the i combinator), subsequently
increments it, doubles it, and then squares it. It is easy to represent
that in a compiled language. For example, in Scheme, it could look
like...

(define (compose f g) (lambda (x) (f (g x))))

(define (inc a) (+ 1 a))
(define (dbl a) (* 2 a))
(define (sqr a) (* a a))

(display
((compose sqr (compose dbl inc)) 9))

...But in Joy, the above quotation can also be thought of as a list of
individual combinators. Or in Scheme...

(list sqr inc dbl)

...So now the question is "How do I represent Joy quotations in Scheme".
On the one hand, you can say quotations are functions and Joy's "cons" is
really Scheme's "compose". This gets you the fast(er) compiled code.
Unfortunately, there's no such thing as "uncompose" so you can't take
quotations apart, only stick them together. On the other hand, you could
treat Joy's quotations as Scheme lists, which would allow arbitrary
munging of quotations, but when you want to execute them with the "i"
combinator, you have to take the "interpreter speed hit." In Scheme, it
might look something like...

(define (id x) x)

(define (i lst)
(lambda (stack) ((foldr compose id lst) stack)))

...Of course there are a number of ways to try to avoid the problem. You
could perform some static analysis to determine which Joy quotations
never need to be "unconsed" and treat those as functions, and treat the
rest as lists. Or try to keep both representations around at all times
(like in a pair)...

(cons (list sqr dbl inc) (compose sqr (compose dbl inc)))

...Or as a more radical solution, you could decide that lists and
executable quotations are two separate types. And not allow "uncons" on
things that are executable quotations (but you could still have a
polymorphic/overloaded "cons" which does the right thing with respect to
list/executable-quotations). Then you might want to have some different
syntax for creating list literals vs. executable quotation literals.
That's the approach I used in my "Almost Joy" to Scheme compiler.
Executable quotations are enclosed in square brackets, while lists are
enclosed in ordinary parenthesis.

Greg Buchholz

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com