Re: functional ADT / shadowing built-in destructive macros

"codyk........@xxxxxxxxx" <codykoeninger@xxxxxxxxx> writes:

> I've been reading Algorithms: a functional programming approach, and
> wanted to try implementing some of the code in lisp, starting with
> abstract data types. The first ADT covered is stacks, so i'd like to
> be able to use "push" as an operation; however the built-in cl:push is
> destructive.
>
> I didn't like the idea of having to write functional:push or the like
> every time. So I decided to try shadowing push, and implementing it as
> a generic function that defaults to calling cl:push, with other methods
> specialized to do the right thing on functional data types. The
> specialized methods work, but the default no longer causes side effects
> - for example:
>
> CL-USER> (defparameter l (list 0))
> L
> CL-USER> (push 'a l)
> calling cl:push...
> (A 0)
> CL-USER> l
> (0)
> CL-USER> (cl:push 'a l)
> (A 0)
> CL-USER> l
> (A 0)
>
> I'm assuming this is because cl:push is implemented as a macro, because
> built-in destructive functions such as nconc still cause side effects
> in this situation. I've got 2 questions:
>
> 1. Is the assumption that the issue is with push's implementation as a
> macro correct? In other words, there's no way to extend built-in
> destructive macros without re-implementing them?

Well, you need to understand what CL:PUSH does--it operates on a
"place" such as a variable (which is why it has to be a macro).

> 2. Am I going about this in completely the wrong way? I'd appreciate
> any advice; relevant pieces of code follow:

The real problem is that Lisp lists are not really first class
objects. The cons cells that make them up are but the (object)
identity of the list changes every time you add a new element to the
front. For more on this you might want to look at:

<http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>

Anyway, I'd advise you to just implement your ADTs, if that's what
you're into, and not worry about integrating them with Lisp lists
since you pretty much can't. On the other hand, looking at your code,
your STACK class behaves pretty much exactly like Lisp cons
cells--each time you push a new item on the stack, the object identity
of the stack changes (because you make a new instance of STACK) so
it's not clear what you're gaining by this exercise.

> (defgeneric push (object place)
> (:documentation
> "If place is a functional ADT, returns a new data structure with the
> contents of place, plus object added to the top.
> If place is not a functional ADT, defaults to cl:push.")
> (:method (object place)
> (progn
> (format t "calling cl:push...~%")
> (cl:push object place))))
> ;;calling cl:push above doesn't work correctly, because it is a macro?

Right you're just changing the value of the local variable OBJECT.

> (defmethod push (object (place stack))
> (make-instance 'stack
> :contents (cons object (contents place))))
>

-Peter

--
Peter Seibel * peter@xxxxxxxxxxxxxxx
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
.

Relevant Pages

  • [OT] PostLisp, a language experiment
    ... IMHO the worst thing in Lisp is its many parentheses. ... The worst thing about Forth IMHO is the stack clutter. ... And while I could write a macro like (with bla ... The ret is the explicit return continuation. ...
    (comp.lang.lisp)
  • Re: Three questions
    ... of the functionality you are doing here already exists in lisp. ... Another way to implement this macro, ... really understand all of the binding forms in Common Lisp and also make ... often KEY for properly implementing control structures. ...
    (comp.lang.lisp)
  • Re: Program compression
    ... problems to be solved much more concisely than with Lisp. ... In Common Lisp, it's another one line of code: ... My point is that different languages are based on different things ... it would be impossible for the author of a macro (in the Lisp ...
    (comp.programming)
  • Re: [OT] PostLisp, a language experiment
    ... a preconception that there isn't a language for which longer ... > latter method in Lisp, and C and many other languages so that the code ... >> apparently no runtime checks for stack mismatches, ... > the complexity and number of stack items for each definition. ...
    (comp.lang.lisp)
  • Re: Why is LISP syntax superior?
    ... that lisp was the most powerful programming language ever invented, ... It is precisely the lack of syntax that I admire in Lisp ... (setf (elt seq i) ... I guess one could write a reader macro to transform foointo (elt ...
    (comp.lang.lisp)