headers
John Cowan | 23 Mar 2006 21:14

[stack] Implementing Joy sets

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 <at> ccil.org>
are the same thing.  --Hannah Arendt    http://www.ccil.org/~cowan

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
(Continue reading)

Permalink | Reply | 6 comments |
headers
sa | 23 Mar 2006 21:31

Re: [stack] Implementing Joy sets


use the extension, conform to the spec.

concatenative <at> 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 <at> ccil.org>
(Continue reading)

Permalink | Reply | 2 comments |
headers
John Cowan | 23 Mar 2006 21:41

Re: [stack] Implementing Joy sets

sa <at> dfa.com 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 <at> ccil.org
 I wish it were impossible."                    http://www.ccil.org/~cowan

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe <at> yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
Permalink | Reply | 1 comment |
headers
William Tanksley, Jr | 23 Mar 2006 23:48
Picon

Re: [stack] Implementing Joy sets

John Cowan <cowan <at> ccil.org> wrote:
> sa <at> dfa.com 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

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> To unsubscribe from this group, send an email to:
(Continue reading)

Permalink | Reply | 0 comments |
headers
Manfred Von Thun | 24 Mar 2006 09:20
Picon
Picon
Favicon

Re: [stack] Implementing Joy sets


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.
(Continue reading)

Permalink | Reply | 2 comments |
headers
John Cowan | 24 Mar 2006 14:51

Re: [stack] Implementing Joy sets

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?
(Continue reading)

Permalink | Reply | 0 comments |
headers
Greg Buchholz | 24 Mar 2006 18:44
Picon
Favicon

Re: [stack] Implementing Joy sets

--- Manfred Von Thun <m.vonthun <at> latrobe.edu.au> 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))
(Continue reading)

Permalink | Reply | 0 comments |
headers
John Cowan | 25 Mar 2006 06:53

[stack] How do modules work in Joy1?

Can someone (probably Manfred) explain to me how modules and hiding work
in Joy0/Joy1?  That was a part of the source I didn't need to figure
out in revising Joy0 to make Joy1, and it's pretty hard to follow.

I have deduced that it's the definitions of symbols rather than the
symbols themselves that are different inside a module.  Where are these
definitions stored, and how are they revived when you invoke a public
function?

--

-- 
Where the wombat has walked,            John Cowan <cowan <at> ccil.org>
it will inevitably walk again.          http://www.ccil.org/~cowan

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe <at> yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
Permalink | Reply | 4 comments |
headers
Manfred Von Thun | 31 Mar 2006 09:24
Picon
Picon
Favicon

Re: [stack] How do modules work in Joy1?


On 25/3/06 3:53 PM, "John Cowan" <cowan <at> ccil.org> wrote:

> Can someone (probably Manfred) explain to me how modules and hiding work
> in Joy0/Joy1?  That was a part of the source I didn't need to figure
> out in revising Joy0 to make Joy1, and it's pretty hard to follow.
> 
> I have deduced that it's the definitions of symbols rather than the
> symbols themselves that are different inside a module.  Where are these
> definitions stored, and how are they revived when you invoke a public
> function?

First, some general comments.

The symbol table and its associated functions could be implemented in
several ways. The choice would depend much on what the implementation
language has to offer. But it also depends on what the implementor¹s
brainware has to offer. I made some choices, partly based on what I was
familiar with, and partly on what I was able to pick up on the fly. This was
my first attempt at using a hash method: when encountering a symbol, use a
crude hash function to compute a small number (0..9 originally), have an
array (size 10) as starting points for (10) linear lists (in fact, treated
as stacks) of structs of strings (the names) and other info. It seems to
have worked.

All built-ins are entered at start-up time, by hashing the name and consing
a new element into the linear list. Then, when in definition mode and
reading ³foo == ... bar ...², cons foo into its list, possibly shadowing an
inbuilt foo. When reading the body, and encountering bar, find bar in its
list. Do the same when not in definition mode and reading ³...baz...² So far
(Continue reading)

Permalink | Reply | 1 comment |
headers
John Cowan | 31 Mar 2006 23:17

Re: [stack] How do modules work in Joy1?

Manfred Von Thun scripsit:

> This was my first attempt at using a hash method: when encountering
> a symbol, use a crude hash function to compute a small number (0..9
> originally), have an array (size 10) as starting points for (10) linear
> lists (in fact, treated as stacks) of structs of strings (the names)
> and other info.

Ah, this was what I didn't grasp before: the symbols *include* their
names, rather than being pointed to by their names.  In fact, the symbol
"bar" as used in a HIDE bar == ... IN ... END construction is a *different
C-level object* from the symbol "bar" used anywhere else, although the
implementation of the "=" word hides this fact.

My current Scheme design uses Scheme symbols to represent Joy names, and
looks up the definition of a symbol at run time in the global hash table.
The C system, on the other hand, looks up things in the hash table
at compile time (that is, when processing definitions).  The former
scheme doesn't do so well in the presence of hidden symbols, though
it's very convenient in other ways: it would be necessary to keep
the hidden-names list around with each word so it can be reinstated
at run time, kind of like a closure.

I have to think about this further before I see what makes sense.

> I reasoned that hashing is good for the all the inbuilts and the
> globally defined library and user functions, which will never be deleted
> (although they might be shadowed). But the number of hidden h's inside
> a HIDE will never be large, and so a single simple list should suffice,
> and no hashing is used.
(Continue reading)

Permalink | Reply | 0 comments |

Gmane