[plt-scheme] `shared' syntax confusing

At Mon, 10 Nov 2008 16:14:41 +0900, Alex Shinn wrote:
> I was somewhat surprised that the expression
> 
>     (shared ((x (list* 1 2 3 x))) x)
> 
> did not patch the `x' in the body of the `list*'.
> 
> The manual is not particularly enlightening:
> 
>     (shared ([id expr] ...) expr)
> 
>     Like letrec, but when an expr next to an id is a cons,
>     list, vector, quasiquoted expression, or make-structid
>     from a define-struct, the expr can refer directly to any
>     id, not just ids defined earlier. Thus, shared can be
>     used to create cyclic data structures.

That's the documentation for the HtDP "Advanced" language. We should
improve those docs.

The documentation for `scheme/shared' (or `scheme'), however, is
considerably more detailed already:

   http://docs.plt-scheme.org/reference/shared.html


> I think it's trying to say that if the binding `expr's are a
> list whose car is one of the listed identifiers, then any of
> the arguments may directly refer to any `id', but _not_ use
> an `id' inside another expression.  Which is not quite
> correct, because `expr' can contain directly nested
> references to other constructors, so that
> 
>     (shared ((x (cons 1 (cons 2 x)))) x)
>     => #0=(1 2 . #0#)
> 
> but not references nested inside other expressions
> 
>     (shared ((x (cons 1 (if #t x x)))) x)
>     => (1 . #<undefined>)

Right. This is more precisely specified in the docs for
`scheme/shared'.


> Why the limitation?  It seems very unintuitive, and there
> are useful graphs that can't be represented this way.

It was easy to support the second example when `cons' created mutable
pairs. Now that it creates immutable pairs, `shared' must be able to
predict more of the shape of the resulting data to be able to construct
the circular version, and there will obviously be approximations in its
analysis of the shape. Not being able to see through `(if #t ...)' is
one of the approximations.

[In other words, I don't know how to implement it.]


> And if you are going to have this limitation, why is the
> line drawn at the listed forms?  It's not just primitive
> constructors, because `list' is allowed (which is just a way
> to generate chains of pairs) but not the related `list*' or
> `append.'  Without `append' you can't even define SRFI-1's
> `circular-list' in terms of `shared'.

Adding `list*' sounds like a good idea.

I don't quite see how it helps you implement `circular-list', though.
It seems like you'd need `append' for that, so maybe we can add
`append', too.


> P.S. Wouldn't `let-shared' have been a more natural name?

Yes.


Matthew