Declaration of shared structures

[Emmanuel Medernach]

Hi all,

Thinking about shared structures I would prefer an alternative
parenthesis syntax for creating this kind of values like this one:

(make-shared ((a 'foo) (b (1 (a b) c)) (c #(2 b))) (list a b c))

equivalent to in SRFI-38:

('foo #1=(1 ('foo #1#) #2#) #2=#(2 #1#))

The rationale behind it is to avoid wild mutations when building
shared structures by considering the value being created as a whole
and to have a human-readable notation.

What do you think about it ? Anyone interested to take up the
implementation challenge ?

Best regards,
--
Emmanuel Medernach

[Aaron W. Hsu]

On Wed, 2010-06-09 at 11:39 -0700, Emmanuel Medernach wrote:

> Thinking about shared structures I would prefer an alternative
> parenthesis syntax for creating this kind of values like this one:
>
> (make-shared ((a 'foo) (b (1 (a b) c)) (c #(2 b))) (list a b c))
>
> equivalent to in SRFI-38:
>
> ('foo #1=(1 ('foo #1#) #2#) #2=#(2 #1#))

So, I'm not sure whether I consider this a better or worse thing. More
on that later.

> The rationale behind it is to avoid wild mutations when building
> shared structures by considering the value being created as a whole
> and to have a human-readable notation.

I'm not sure what you mean here by avoiding wild mutations. You really
are going to need mutation in the case of shared structures, I don't
know of any way to get around this. Even if you hide this at an upper
level, at the low level of what the compiler has to do, I don't see how
there could be a big or significant difference here.

> What do you think about it ? Anyone interested to take up the
> implementation challenge ?

Firstly, let's take a look at the implementation:

(define-syntax (let-shared x)
(define (matching-name? id names)
(syntax-case names ()
[() #f]
[(n . rest) (bound-identifier=? id #'n) #t]
[(n . rest) (matching-name? id #'rest)]))
(syntax-case x (private unquote)
[(_ ([name exp] ...) body ...)
(for-all identifier? #'(name ...))
#'(let-shared private (name ...) ([name exp] ...) () (body ...))]
[(_ private names () (clause ...) (body ...))
#'(let* (clause ...) body ...)]
[(_ prviate names ([tmp (head . ,id)] rest ...)
(clause ...) (body ...))
(matching-name? #'id #'names)
#'(let-shared private names ([ntmp head] rest ...)
([tmp (cons ntmp #f)] clause ...)
((set-cdr! tmp id) body ...))]
[(_ private names ([tmp (,id . tail)] rest ...)
(clause ...) (body ...))
(matching-name? #'id #'names)
#'(let-shared private names ([ntmp tail] rest ...)
([tmp (cons #f ntmp)] clause ...)
((set-car! tmp id) body ...))]
[(_ private names ([tmp (head . tail)] rest ...)
(clause ...) (body ...))
#'(let-shared private names ([ht head] [tt tail] rest ...)
([tmp (cons ht tt)] clause ...)
(body ...))]
[(_ private names ([tmp (unquote exp)] rest ...)
(clause ...) (body ...))
#'(let-shared private names (rest ...)
([tmp exp] clause ...)
(body ...))]
[(_ private names ([tmp exp] rest ...)
(clause ...) (body ...))
#'(let-shared private names (rest ...)
([tmp 'exp] clause ...)
(body ...))]))

This is similar to a common SRFI-1 MAKE-CIRCULAR form. I've implemented
a similar version in this manner:

(define-syntax (make-shared x)
(syntax-case x (private unquote)
[(_ name exp)
(identifier? #'name)
#'(make-shared private name ([name exp]) () (name))]
[(_ private name () (clause ...) (body ...))
#'(let* (clause ...) body ...)]
[(_ prviate name ([tmp (head . ,id)] rest ...)
(clause ...) (body ...))
(and (identifier? #'id) (bound-identifier=? #'name #'id))
#'(make-shared private name ([ntmp head] rest ...)
([tmp (cons ntmp #f)] clause ...)
((set-cdr! tmp name) body ...))]
[(_ private name ([tmp (,id . tail)] rest ...)
(clause ...) (body ...))
(and (identifier? #'id) (bound-identifier=? #'name #'id))
#'(make-shared private name ([ntmp tail] rest ...)
([tmp (cons #f ntmp)] clause ...)
((set-car! tmp name) body ...))]
[(_ private name ([tmp (head . tail)] rest ...)
(clause ...) (body ...))
#'(make-shared private name ([ht head] [tt tail] rest ...)
([tmp (cons ht tt)] clause ...)
(body ...))]
[(_ private name ([tmp (unquote exp)] rest ...)
(clause ...) (body ...))
#'(make-shared private name (rest ...)
([tmp exp] clause ...)
(body ...))]
[(_ private name ([tmp exp] rest ...)
(clause ...) (body ...))
#'(make-shared private name (rest ...)
([tmp 'exp] clause ...)
(body ...))]))

Both of these make use of the unexported private auxiliary syntax:

(define-syntax (private x)
(syntax-violation 'private "misplace aux keyword" x))

This would be defined in the enclosing library, but not exported (I'm
speaking R6RS here).

The above works only with quasiquoted values. Moreover, it only deals
with list forms. You could easily extend this to anything that has a
read syntax, but extending it beyond this to handle arbitrary
expressions is much harder. Additionally, if anyone wants to make it
possible to extend the reader, then it would need to provide some way of
knowing how to do this sort of thing with the resulting objects. I
haven't thought about that much.

You'll notice that I changed the syntax somewhat:

(let-shared ([a 'foo] [b (1 (,a ,b) ,c)] [c (2 ,b)]) (list a b c))
=> (#0='foo #1=(1 (#0# #1#) #2=(2 #1#)) #2#)

Namely, I do this because otherwise you wouldn't be able to have symbols
of the same name as the variables that are being bound.

Since this is really only something that works easily with quoted
things, unless someone thinks that there is real merit and capacity to
implement one for generic structures, and can provide a meaningful
formal semantics for such behavior, I'm not sure I want this. It is sort
of handy when you know the exact or close to the exact form of the
shared structure that you are going to be creating, but other than that
it makes things a little difficult. There are sneaky interactions and
hidden behaviors that are going on in the above implementation that
might result in strange errors. We would need to make sure that we
handled these in some way. Someone would have to come up with a much
more clear semantics on how this behaved and worked before I would be
comfortable with it.

Right now this strikes me as something that people should just implement
themselves, using it in a limited or restricted environment. I don't see
this in widespread use right now, so I'd probably avoid standardizing
it.

Aaron W. Hsu

[Aaron W. Hsu]

Oh, and of course, another clause needs to be added there to catch the
single unquoted expression clause [b ,a] case.

Aaron W. Hsu

[David Rush]

On 10 June 2010 03:55, Aaron W. Hsu <arc...@sacrideo.us> wrote:

Right now this strikes me as something that people should just implement

themselves, using it in a limited or restricted environment. I don't see
this in widespread use right now, so I'd probably avoid standardizing
it.

I think there is value in terms of having the read/write invariant for cyclic and/or shared data structures. Bog knows I've wasted too much of my life writing display projections, but I don't really see the point for anything more than an I/O hack, either...

david
--
GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt