[racket] graph-structured syntax

From: David Herman (dherman at ccs.neu.edu)
Date: Tue Feb 22 12:37:29 EST 2011

Thanks everyone, I appreciate all the background.

(If you hadn't already guessed, I'm interested from the perspective of JavaScript. Mozilla's implementation of JavaScript has supported a non-standard #...= syntax for years, and I'm told it's suffered from a number of compiler bugs as a result. The JS team hopes to deprecate the syntax and offer a serialization library as an alternative.)

And I agree with Matthias: this is another instance of Scheme/Racket taking the "code is data" mantra less literally (pun intended) than Lisp.

Dave

On Feb 21, 2011, at 6:37 PM, Robby Findler wrote:

> Also, it is all to easy to break macros by writing arguments that are
> cyclic and, compared to the utility they bring (is there any if you're
> outside of 'quote'?), it seems right to me to get rid of it.
> 
> Robby
> 
> On Mon, Feb 21, 2011 at 5:35 PM, Matthias Felleisen
> <matthias at ccs.neu.edu> wrote:
>> 
>> 
>> David, Lisps have had cyclic syntax for decades [*]. When you use S-expressions to represent syntax (reading and macroing) and when your S-expressions support mutation, you don't have much of a choice. Once you separate syntax representation from S-expressions (your major data structure), you can simplify the representation of syntax and thus a good part of your compiler front end. -- Matthias
>> 
>> 
>> 
>> [*] In the beginning they used circularity to create loops, no kidding.
>> 
>> 
>> 
>> 
>> On Feb 21, 2011, at 5:35 PM, David Herman wrote:
>> 
>>> Hi Matthew,
>>> 
>>> Thanks very much for the response.
>>> 
>>>> The docs for `datum->syntax' say that graph structure is disallowed,
>>>> and I think the behavior of `eval' below follows from the default eval
>>>> handler's use of `datum->syntax'.
>>> 
>>> OK, thanks.
>>> 
>>>> Since `read-syntax' and `datum->syntax' don't support graph structure,
>>>> there's no way to construct cyclic input to the expander --- or, in
>>>> particular, to write a cyclic literal under `quote'. Literals with
>>>> cycles were supported at one point, but they were fragile and almost
>>>> never useful.
>>> 
>>> Presumably they might be more useful if we didn't have the `shared' notation, right?
>>> 
>>> But IIUC, cyclic literals are problematic because there's nothing stopping you from embedding arbitrary expressions inside literals, making it perhaps possible to trick the compiler into diverging or even create paradoxical cross-stage cycles. Which suggests that, despite its alluring simplicity, the "#...=" notation should be confined to {de}serialization libraries such as `read', while more restricted notations like `shared' are safer for providing graph-structured literals.
>>> 
>>> Does that sound like the (rough) rationale behind Racket's approach?
>>> 
>>> Dave
>>> 
>>>> 
>>>> At Mon, 21 Feb 2011 08:18:34 -0800, David Herman wrote:
>>>>> Any chance someone has an answer to my question below?
>>>>> 
>>>>> Thanks,
>>>>> Dave
>>>>> 
>>>>> On Feb 14, 2011, at 4:42 PM, David Herman wrote:
>>>>> 
>>>>>> One more data point:
>>>>>> 
>>>>>>> (eval (read (open-input-string "#1=(sin #1#)")))
>>>>>>  datum->syntax: cannot create syntax from cyclic datum: #0='(sin #0#)
>>>>>> 
>>>>>> So that's another clue: it looks like Racket goes to pretty great lengths to
>>>>> prevent the compiler from receiving cyclic AST's.
>>>>>> 
>>>>>> Anyway, it would be good to know if there's a place in the docs where this is
>>>>> spelled out.
>>>>>> 
>>>>>> Dave
>>>>>> 
>>>>>> On Feb 14, 2011, at 4:21 PM, David Herman wrote:
>>>>>> 
>>>>>>> I've never been fully acquainted with the graph reader, so I did a little
>>>>> REPL-experimenting and doc-hunting. It appears Racket is pretty conservative
>>>>> about where it allows you to use graph syntax:
>>>>>>> 
>>>>>>>> (define x '#0=(foo . #0#))
>>>>>>> read: #..-expressions not allowed in read-syntax mode
>>>>>>> 
>>>>>>> I imagine this is because cyclic AST's are Really Really Scary:
>>>>>>> 
>>>>>>> #0=(sin #0#))
>>>>>>> 
>>>>>>> But I can't quite figure out where, if anywhere, graph-structured
>>>>> S-expressions *are* allowed in the Racket syntax. Certainly, you can use them
>>>>> for a programmatic read:
>>>>>>> 
>>>>>>>> (read (open-input-string "#0=(foo . #0#)"))
>>>>>>> #0=(foo . #0#)
>>>>>>> 
>>>>>>> But is there no place in the surface syntax where you can ever use the graph
>>>>> syntax? Is the `shared' library the only declarative syntax for creating cyclic
>>>>> data structures?
>>>>>>> 
>>>>>>> Is this a pretty straightforward restriction that was already done in Common
>>>>> Lisp, or did they allow wild-and-wooly, unrestricted uses of cyclic AST's that
>>>>> (educated guess...) result in undefined behavior by the compiler?
>>>>>>> 
>>>>>>> Dave
>>>>>>> 
>>>>>>> PS Happy Valentine's Day!
>>>>>>> 
>>>>>>> 
>>>>>>> _________________________________________________
>>>>>>> For list-related administrative tasks:
>>>>>>> http://lists.racket-lang.org/listinfo/users
>>>>>> 
>>>>>> 
>>>>>> _________________________________________________
>>>>>> For list-related administrative tasks:
>>>>>> http://lists.racket-lang.org/listinfo/users
>>>>> 
>>>>> 
>>>>> _________________________________________________
>>>>> For list-related administrative tasks:
>>>>> http://lists.racket-lang.org/listinfo/users
>>> 
>>> 
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://lists.racket-lang.org/listinfo/users
>> 
>> 
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/users
>> 




Posted on the users mailing list.