Replacing a function in an expression

Discussion of Common Lisp
Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Replacing a function in an expression

Post by Paul » Sun Nov 11, 2012 5:45 pm

stackman wrote:@ Paul
Are there implementation independant common lisp code walkers?
A quick google search suggests that there are a few edge cases which are not so easy to handle.
The trouble is, the environment access stuff didn't make it into the standard, so if you want to write a portable code-walker, you have to write all of it -- reimplementing most of Common Lisp in the process -- or have implementation-specific code.
I am using sbcl, so maybe there is a way to leverage some sbcl compatible code walker
to deal with code substitution, without having to roll my own?
There's a code-walker in the "WALKER" package in CMUCL; don't know if it's in SBCL...

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Replacing a function in an expression

Post by Paul » Sun Nov 11, 2012 5:58 pm

Goheeca wrote:Check the version with macroexpand-dammit out, but it also expands into the implementation-dependent code because of compiler macros (for example append with two args into sb-impl::append2 under SBCL).
But that shouldn't matter, because SB-IMPL::APPEND2 must be a function (assuming it's been fully macro-expanded) -- and you already know how to deal with those (i.e., there's nothing special going on with the arguments).

stackman
Posts: 28
Joined: Sat Oct 06, 2012 5:44 am

Re: Replacing a function in an expression

Post by stackman » Mon Nov 12, 2012 4:01 am

@Paul
I found that the pcl code walker ships with sbcl. A bit of googling even dug up
a thread showing how to use it in my particular case.

Many thanks to all the people that answered my question.
I now understand a lot more about code transformation in common lisp,
and I will try to build up my own walker.

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Replacing a function in an expression

Post by Konfusius » Mon Nov 12, 2012 9:20 am

Paul wrote:
Konfusius wrote:Unfortunately there is no implementation independent way to do this since every implementations has it's own special forms. But usually the number of special forms is small wich makes it feasible to write different versions for different implementations.
No. The special forms/operators are defined in the standard. Implementations are permitted to implement other macros as special operators, but must also supply macro definitions, so a code-walker doesn't have to know about them.
Afaik, macros may expand into expressions containing implemetation specific special forms.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Replacing a function in an expression

Post by Paul » Mon Nov 12, 2012 2:53 pm

Konfusius wrote:
Paul wrote:
Konfusius wrote:Unfortunately there is no implementation independent way to do this since every implementations has it's own special forms. But usually the number of special forms is small wich makes it feasible to write different versions for different implementations.
No. The special forms/operators are defined in the standard. Implementations are permitted to implement other macros as special operators, but must also supply macro definitions, so a code-walker doesn't have to know about them.
Afaik, macros may expand into expressions containing implemetation specific special forms.
Of course they can. But implementation-specific special forms must have macro-expansions...so if you fully-macroexpand, there can't be any implementation-specific special forms remaining -- just functions and standard special forms.

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Replacing a function in an expression

Post by Goheeca » Mon Nov 12, 2012 3:25 pm

Paul wrote:
Goheeca wrote:Check the version with macroexpand-dammit out, but it also expands into the implementation-dependent code because of compiler macros (for example append with two args into sb-impl::append2 under SBCL).
But that shouldn't matter, because SB-IMPL::APPEND2 must be a function (assuming it's been fully macro-expanded) -- and you already know how to deal with those (i.e., there's nothing special going on with the arguments).
But SB-IMPL::APPEND2 is a function provided by the particular implementation and if we want to use the generated code somewhere else we can't, so it's implementation-dependent in a certain way.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Replacing a function in an expression

Post by Konfusius » Tue Nov 13, 2012 1:18 am

Paul wrote:Of course they can. But implementation-specific special forms must have macro-expansions...so if you fully-macroexpand, there can't be any implementation-specific special forms remaining -- just functions and standard special forms.
The ANSI spec says that
3.1.2.1.2.2 Macro Forms wrote:...
An implementation is free to implement a Common Lisp special operator as a macro. An implementation is free to implement any macro operator as a special operator, but only if an equivalent definition of the macro is also provided.
...
But this doesn't imply that a standard macro must not expand to a non-standard special form.

Don't get me wrong. I don't want to troll to prove myself right. In fact, I'd love to hear that I'm wrong. I just don't know of any passage in the ANSI spec that requires standard macros to expand only into standard special forms.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Replacing a function in an expression

Post by Paul » Tue Nov 13, 2012 2:24 am

Konfusius wrote:
Paul wrote:Of course they can. But implementation-specific special forms must have macro-expansions...so if you fully-macroexpand, there can't be any implementation-specific special forms remaining -- just functions and standard special forms.
The ANSI spec says that
3.1.2.1.2.2 Macro Forms wrote:...
An implementation is free to implement a Common Lisp special operator as a macro. An implementation is free to implement any macro operator as a special operator, but only if an equivalent definition of the macro is also provided.
...
But this doesn't imply that a standard macro must not expand to a non-standard special form.

Don't get me wrong. I don't want to troll to prove myself right. In fact, I'd love to hear that I'm wrong. I just don't know of any passage in the ANSI spec that requires standard macros to expand only into standard special forms.
Macros can expand into non-standard special forms. The implementation that macro was written for can then implement those special operators and be done. But "an implementation is free to implement any macro operator as a special operator, but only if an equivalent definition of the macro is also provided" (the implementation doesn't have to use them, obviously!), so each of those non-standard special operators has to have a macro expansion available. If that macro expands into something with non-standard special operators in it, those special operators must have a macro expansion. And so on. Eventually you have to end up with only functions and standard special operators, or the macro expansion would never terminate.

pjstirling
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

Re: Replacing a function in an expression

Post by pjstirling » Tue Nov 13, 2012 6:55 am

Paul wrote:
Konfusius wrote:
Paul wrote:Of course they can. But implementation-specific special forms must have macro-expansions...so if you fully-macroexpand, there can't be any implementation-specific special forms remaining -- just functions and standard special forms.
The ANSI spec says that
3.1.2.1.2.2 Macro Forms wrote:...
An implementation is free to implement a Common Lisp special operator as a macro. An implementation is free to implement any macro operator as a special operator, but only if an equivalent definition of the macro is also provided.
...
But this doesn't imply that a standard macro must not expand to a non-standard special form.

Don't get me wrong. I don't want to troll to prove myself right. In fact, I'd love to hear that I'm wrong. I just don't know of any passage in the ANSI spec that requires standard macros to expand only into standard special forms.
Macros can expand into non-standard special forms. The implementation that macro was written for can then implement those special operators and be done. But "an implementation is free to implement any macro operator as a special operator, but only if an equivalent definition of the macro is also provided" (the implementation doesn't have to use them, obviously!), so each of those non-standard special operators has to have a macro expansion available. If that macro expands into something with non-standard special operators in it, those special operators must have a macro expansion. And so on. Eventually you have to end up with only functions and standard special operators, or the macro expansion would never terminate.
I'm quite sure you are wrong here, the special operators are the true primitives, they don't have anytthing below them. What the standard is talking about here is that the implementation needs to have an macro expander for the special operators which understands which parts of the code being compiled need to be macroexpanded in turn.

MACROEXPAND and MACROEXPAND-1 both return two values: the expanded form, and a boolean saying whether the expansion changed the form. MACROEXPAND calls MACROEXPAND-1 on each subform, and checks this second value, if it is T then MACROEXPAND-1 is called again on the new expansion. This loops until the second value is nil (this is why macroexpansion always terminates eventually).

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Replacing a function in an expression

Post by Paul » Tue Nov 13, 2012 7:31 am

pjstirling wrote:I'm quite sure you are wrong here, the special operators are the true primitives, they don't have anytthing below them. What the standard is talking about here is that the implementation needs to have an macro expander for the special operators which understands which parts of the code being compiled need to be macroexpanded in turn.
I'm not sure what you're trying to say here, but I assure you I'm not ;)

Special operators don't need to have macro-expansions -- only non-standard special operators do, and not because the implementation needs to expand them (it doesn't -- that's what makes them special operators): that rule is just there to enable non-implementation code to understand them.
pjstirling wrote:MACROEXPAND and MACROEXPAND-1 both return two values: the expanded form, and a boolean saying whether the expansion changed the form. MACROEXPAND calls MACROEXPAND-1 on each subform, and checks this second value, if it is T then MACROEXPAND-1 is called again on the new expansion. This loops until the second value is nil (this is why macroexpansion always terminates eventually).
It doesn't always terminate. MACROEXPAND doesn't call MACROEXPAND-1 on each subform, it just calls it on the form you give it (there's not a "macroexpand-fully" function in CL); and I think perhaps you're confused about what the second value means: it isn't NIL if the form merely looks the same, it's only NIL if the form isn't a macro form. If you define a macro that expands into itself -- e.g., (defmacro foo (x) `(foo ,x)) -- then (macroexpand-1 '(foo 42)) will return (foo 42) and T -- the first value looks the same as what you put in, but the second value is T, not NIL. (macroexpand '(foo 42)) will infloop, because it keeps doing MACROEXPAND-1 and getting the same result. It only stops if it eventually bottoms out in something that isn't a macro.

Post Reply