DEFSTRUCT and lexical environment
in [Lisp]
|
From: Tim Bradshaw on 17 Oct 2009 06:51 On 2009-10-17 00:31:09 +0100, Ron Garret <rNOSPAMon(a)flownet.com> said: > There are two kinds of symbol capture. GENSYM only solves one of them. > Madhu's DEFSTRUCT (re-)introduces the other kind. I'm confused, can you explain? Or may be I'm not. The traditional bad-macro one is, I think, where you write something like: (defmacro collecting (&body forms) `(let ((.secret. '())) (flet ((collect (x) ...)) ,@forms) .secret.)) Here COLLECT is meant to be introduced, but .SECRET. is not. So instead you write (defmacro collecting (&body forms) (let ((sn (make-symbol "SECRET"))) `(let ((,sn '())) (flet ((collect (x) ...)) ,@forms) ,sn))) Where the secret variable is now really secret. I guess the bad-DEFSTRUCT one is kind of this inside out, where I've done something like (let ((x ...)) (lambda (y) ... x )) But somehow what I've got has not closed over the X so it will "see" other bindings of X where it is used. Is that what you mean?
From: Ron Garret on 17 Oct 2009 11:59 In article <2009101711515316807-tfb(a)cleycom>, Tim Bradshaw <tfb(a)cley.com> wrote: > On 2009-10-17 00:31:09 +0100, Ron Garret <rNOSPAMon(a)flownet.com> said: > > > There are two kinds of symbol capture. GENSYM only solves one of them. > > Madhu's DEFSTRUCT (re-)introduces the other kind. > > I'm confused, can you explain? Or may be I'm not. The traditional > bad-macro one is, I think, where you write something like: > > (defmacro collecting (&body forms) > `(let ((.secret. '())) > (flet ((collect (x) > ...)) > ,@forms) > .secret.)) > > Here COLLECT is meant to be introduced, but .SECRET. is not. So > instead you write > > (defmacro collecting (&body forms) > (let ((sn (make-symbol "SECRET"))) > `(let ((,sn '())) > (flet ((collect (x) > ...)) > ,@forms) > ,sn))) > > Where the secret variable is now really secret. That's right. There are two types of capture situations, those that involve code that is passed into the macro as an argument and appears in the macro expansion, and code that surrounds the macro. AFAIK, the two types of capture don't really have names, so I'll coin some new terminology: let's call them INWARD and OUTWARD capture respectively. What you have just described in inward capture, and it is fixed using gensyms. > I guess the bad-DEFSTRUCT one is kind of this inside out, where I've > done something like > > (let ((x ...)) > (lambda (y) > ... x > )) > > But somehow what I've got has not closed over the X so it will "see" > other bindings of X where it is used. > > Is that what you mean? I'm not sure, because this is not an example of capture. The problem with Madhu's semantics is outward capture, but kind of in reverse from the usual situation. The usual situation is something like this: (defun my-helper (...) (something)) (defmacro mac (...) `(... (my-helper ...) ...)) and now a user does: (flet ((my-helper (...) (something-different))) (mac ...)) This is the kind of capture that is solved by separating value and function namespaces and adding packages. In a Lisp-1 without packages there is the following classic screw case: (define-macro lisp1-macro (...) (... (list ...) ...)) (defun foo (list) (... (lisp1-macro ...) ...)) Hopefully it's obvious how Lisp-2 and packages fix this. The point is, the macro's proper operation depends on the environment in which it is *used*. LISP1-MACRO depends on LIST being bound -- AT THE POINT OF INVOCATION -- to a function that makes lists. MAC depends on MY-HELPER being FBOUND to a function that does "something" (as opposed to "something-else"). If the environment is not correct, the macro will fail. Madhu's DEFSTRUCT has this exact same problem. Consider the canonical example: (let ((x ...)) (defstruct foo (slot (... x ...)))) Under Madhu's semantics, FOO acts like a macro that now depends on X being bound at the point of :inclusion (which is the DEFSTRUCT analog of macro invocation under Madhu's semantics). i.e. the following will fail: (defstruct (baz (:include foo)) ...) because X is not bound here, i.e. the environment is not correct. rg
From: Tim Bradshaw on 17 Oct 2009 16:01 On 2009-10-17 16:59:16 +0100, Ron Garret <rNOSPAMon(a)flownet.com> said: > I'm not sure, because this is not an example of capture. Yes, it's not. I think I was thinking of some alternative dialect of Lisp where it would be though clearly not being coherent (I *think* that I remember things in Cambridge Lisp, which was the first Lisp I used, where things like this gave problems. I like your terminology though: i was thinking of upward & downward (based on the funarg terminology) but that's not right because that was based on stacks, and this is based on position in source. So, I think: Inward capture is where something wraps itself around your code and inserts names it should not into the scope of your code. This can be resolved by just introducing such names. Outward capture is where something inserts code within the scope of your code, and that code depends on names which your code may (or may not) have introduced. In general this is harder, because of things like your FLET case, but in many specific cases it's not that hard (for instance the DEFSTRUCT case).
From: Ron Garret on 17 Oct 2009 23:11 In article <2009101721013316807-tfb(a)cleycom>, Tim Bradshaw <tfb(a)cley.com> wrote: > On 2009-10-17 16:59:16 +0100, Ron Garret <rNOSPAMon(a)flownet.com> said: > > > I'm not sure, because this is not an example of capture. > > Yes, it's not. I think I was thinking of some alternative dialect of > Lisp where it would be though clearly not being coherent (I *think* > that I remember things in Cambridge Lisp, which was the first Lisp I > used, where things like this gave problems. > > I like your terminology though: i was thinking of upward & downward > (based on the funarg terminology) but that's not right because that was > based on stacks, and this is based on position in source. > > So, I think: > > Inward capture is where something wraps itself around your code and > inserts names it should not into the scope of your code. This can be > resolved by just introducing such names. I presume you meant "... by just NOT introducing such names" i.e. by using gensyms. That's right. > Outward capture is where something inserts code within the scope of > your code, and that code depends on names which your code may (or may > not) have introduced. In general this is harder, because of things > like your FLET case, I'd phrase it slightly differently: outward capture is where the macro expansion contains a free reference, i.e. a reference that is not bound by the macro expansion itself. You have a choice of environment in which to resolve that free reference. You can resolve it in the environment where the macro is defined (this is what hygienic macros do) or you can resolve it in the environment where the macro is invoked (this is what CL does). Note that the reason hygienic macros are hairy and tend to be associated with weird-looking things like SYNTAX-RULES is that in a fully general macro facility it is hard to figure out what the free references *are*. In a fully general DEFMACRO it is actually impossible to do this at macro-definition time because that would require solving the halting problem. SYNTAX-RULES constrains the kinds of computations that macro-expanders can perform in order to make the problem of identifying the potential free references tractable at macro-definition time. Note that imposing this kind of constraint is not actually necessary because you can elect to identify the free references at macro-expansion time, which is obviously a tractable problem (assuming the macro expansion terminates of course). There's an interesting recent result due to Pascal Costanza and his students that shows that not only is the problem tractable, but that it can be done without a code walker. > but in many specific cases it's not that hard (for > instance the DEFSTRUCT case). The DEFSTRUCT case is a complete red herring because the spec is ambiguous, so you can choose whether to use (unhygienic-)macro-like semantics with all its attendant problems, or function-like semantics. This is notwithstanding the fact that DEFSTRUCT is a macro. DEFUN is a macro too, but obviously the things that DEFUN defines have function-like semantics. It's a no-brainer that function-like semantics is the better choice because then everything is lexically scoped and the capture issues simply evaporate. rg
From: Madhu on 18 Oct 2009 00:10
* Tim Bradshaw <2009101721013316807-tfb(a)cleycom> : Wrote on Sat, 17 Oct 2009 21:01:33 +0100: | Inward/Outward capture [I see no need to invent new terminology which is then used to wrongly address the issues at hand] You may be interested in the propopsal to bind initforms to new names (via gensym) in the defstruct-generated-constructor's lambda-list which was termed NOT-BOUND[1]. [NOTE however that this has issues with boa constructors and also will not work when there is any ordering of evaluation in the initforms (which can be theoretically imposed by the user)] [1] http://www.lispworks.com/documentation/HyperSpec/Issues/iss111_w.htm Issue DEFSTRUCT-CONSTRUCTOR-SLOT-VARIABLES (not part of the Common Lisp Standard). -- Madhu |