Replacing a function in an expression

I am trying to understand the "code-is-data" motto in common lisp.
So I have an expression and I want to replace all occurrences of the function list by my-list, as follows.

(defparameter *expr* '(let ((list (quote (1 2 3)))) ;; comment list
                         (append list (list 4 5 'list "list, 'list, LIST"))))
(do-replacement  *expr*)
=>(LET ((LIST '(1 2 3)))
  (APPEND LIST (MY-LIST 4 5 'LIST "list, 'list, LIST")))

It seems that using the subst or subst-if function is a good idea,
but how do I check if the symbol list is used as a function in the expression?

(defun do-replacement (expr)
  (setf expr (macroexpand expr))
  (cond ((atom expr) expr)
		((eq 'list (car expr)) (cons 'my-list (mapcar #'do-replacement (cdr expr))))
		((special-operator-p (car expr))
        (case (car expr)
         ; special forms need special handling
         (quote expr)
         (let (list* 'let
                  (mapcar
                    (lambda (bind)
                    (if (symbolp bind)
                     bind
                     (list (car bind) (do-replacement (cadr bind)))))
                  (cadr expr))
                 (mapcar #'do-replacement (cddr expr))))
         (t (error "special operator ~s not supported" (car expr)))))
      (t (mapcar #'do-replacement expr))))

(do-replacement
  '(let ((list '(list 1 2 3)))
   (append list (list 4 5 'list "list, 'list, LIST"))))

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.

I think in a real situation macrolet is more appropriate and if we want to implement do-replacement I'd do simply this:

(defun do-replacement (expr)
  `(macrolet ((list (&rest args) `(my-list ,@args))) ,expr))

Yeah, if expr contains shadowing of list, it isn't replaced, but it's almost always the right thing.
You can also use macroexpand-dammit (it's available via quicklisp) to see what it's doing:

(defun do-replacement (expr)
  (macroexpand-dammit:macroexpand-dammit
    `(macrolet ((list (&rest args) `(my-list ,@args))) ,expr)))

Konfusius your solution doesn't work for me, I get an output the same as an input.

Goheeca wrote:Konfusius your solution doesn't work for me, I get an output the same as an input.

I've corrected the bug. It should work, now. But your solution is better.

Unfortunately, the code provided by Goheeca does not work for me.
I never used the macrolet operator before, maybe someone can point to a beginner friendly
introduction to macrolet? I have used macros before, but I don't understand the macrolet section
of the hyperspec at the moment.

CL-USER>  (defun do-replacement (expr)
                   `(macrolet ((list (&rest args) `(my-list ,@args))) ,expr))
(do-replacement  '(let ((list (quote (1 2 3)))) ;; comment list
                         (append list (list 4 5 'list "list, 'list, LIST"))))
=> (MACROLET ((LIST (&REST ARGS)
             `(MY-LIST ,@ARGS)))
  (LET ((LIST '(1 2 3)))
    (APPEND LIST (LIST 4 5 'LIST "list, 'list, LIST"))))

As let is for lexical variables, as flet is for functions, the macrolet is for macros.
An example:

(defun add (&rest args) (apply #'+ args))
(defun multiply (&rest args) (apply #'* args))
(add 2 3)
(macrolet ((add (&rest args) `(multiply ,@args))) (add 2 3))

// If I used + instead of add, it would complain about a package lock.

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.

Thanks for the answer, Goheeca, still I fail to see how it addresses the question.
macrolet does expansion then evaluation, doesn't it?
I want to transform the source code without evaluating it, in order to modify programmatically source files.

@ 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.

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?

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). Certainly you can be inspired by the source code of macroexpand-dammit for your version without compiler-macro expanding - I won't help you with this.
Moreover, I'd ask is it an ad hoc issue or you just need it?
In the first case I'd still let the wrapping macrolet in a source code.

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...

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).

@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.

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.

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.

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.

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.

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.

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).

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.

When formulating your problem, you should also think about lexical closures. Assume your piece of LISP code contains the following fragment:

(flet ((list (&rest argument) .........  definition ..........))
  (LIST a b)    
  (LIST c d e) 
 ....   et cetera ......
)

Are you sure you want to replace function occurences of LIST by "mylist" even in this fragment , inside flet?