# Implementing Joy sets

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

     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?

         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