Simple polymorphism in Common Lisp

Discussion of Common Lisp
lispamour
Posts: 18
Joined: Wed Jun 02, 2010 12:29 am

Simple polymorphism in Common Lisp

Post by lispamour » Tue Jun 22, 2010 3:01 am

I'm now starting on Practical Common Lisp, having gone through Gentle Introduction to Symbolic Computation, and I'm playing around with the sample CD database that PCL describes on pp. 20-36. PCL uses a p-list to store each record of a CD collection. I decided to vary the storage implementation a little bit by using a p-list, a hash, and a struct to store the CD record

Code: Select all

(defstruct database
  (type    'plist)    ; Could also be a 'hash or a 'struct
  (storage nil))      ; A list which stores the collection of records

(defun db-create (db-type)
  (make-database :type db-type :storage nil))
The function DB-CREATE takes a symbol specifying the particular type of implementation: PLIST, HASH, or STRUCT.

I then create an a-list of functions corresponding to the particular type of implementation:

Code: Select all

(defconstant *dispatch-table*
      '((plist  (:construct plist-construct  :get plist-get))
        (struct (:construct struct-construct :get struct-get))
        (hash   (:construct hash-construct   :get hash-get))))

(defun dispatch (database operation)
  (let ((dbtype  (database-type database)))
    (getf (second (assoc dbtype *dispatch-table*))
          operation)))

(defun dbrecord-construct (db title artist rating ripped)
  (let ((func (dispatch db :construct)))
    (funcall func title artist rating ripped)))
         
(defun dbrecord-get (db record field)
  (let ((func (dispatch db :get)))
    (funcall func  record field)))
The DBRECORD-CONSTRUCT function resolves to PLIST-CONSTRUCT, STRUCT-CONSTRUCT, or HASH-CONSTRUCT to build a record out of CD data, while DBRECORD-GET retrieves a particular field out of a database record.

This approach should be familiar to C-programmers who implement polymorphism by indexing into an array of function pointers. I've merely applied the technique to Lisp. My question is: Is this a standard practice in Lisp? When I read about polymorphism in Lisp, I usually encounter generic functions (which are covered in a later chapter of PCL), but I wonder if this approach is as commonly accepted.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Simple polymorphism in Common Lisp

Post by ramarren » Tue Jun 22, 2010 4:44 am

Generic functions are already rather simple, at least on surface. What you did is essentially rebuild them in a limited form, making the code more verbose, less clear, and losing many compiler optimizations. While reinventing the wheel is quite common in Lisp community, such as it exists, I don't really see a point in this case. Although I guess it might be an interesting exercise in applying abstractions.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Simple polymorphism in Common Lisp

Post by nuntius » Tue Jun 22, 2010 9:48 am

As Ramarren said, generic functions are a powerful implementation of polymorphism. In a naive implementation, they look somewhat like your code; but the dispatch table is kept on a per-function basis, and macros clean up the syntax. Code like yours is common in languages without object-orientation. See for example the Scheme frameworks in SICP. To learn how CL's generic functions are implemented, try to find a copy of the AMOP.

lispamour
Posts: 18
Joined: Wed Jun 02, 2010 12:29 am

Re: Simple polymorphism in Common Lisp

Post by lispamour » Mon Jun 28, 2010 5:49 am

Thanks for both of your comments. I've skipped ahead a bit to chapter 16 in PCL to read further on generic functions. They do seem very powerful. Correct me if I'm wrong, but I gather that generic functions only work with objects defined by defclass, but not ordinary structures.

When I was reading CL:GISC, I was pleasantly surprised to find out that structures already have a notion of inheritance and subtyping.
Eg, pp 380-381:

Code: Select all

(defstruct ship
   (name nil)
   (captain nil)
   (crew-size nil))

(destruct (starship (:include ship))
   (weapons nil)
   (shields nil))

(setf z1 (make-starship :captain "James T. Kirk"))


(ship-p z1) => T
(starship-p z1) => T
(ship-captain z1) => "James T. Kirk"
(starship-captain z1) => "James T. Kirk"

Ie, z1 is a STARSHIP which satisfies the IS-A relation for SHIP; accessor functions for SHIP get inherited by STARSHIP.

This strikes me as going quite far down the OO path without involving CLOS. Have Lispers ever written macros which implement my earlier example so that they have a stripped down OO implementation In Common Lisp using only structures and a few macros for polymorphism?

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Simple polymorphism in Common Lisp

Post by ramarren » Mon Jun 28, 2010 6:24 am

lispamour wrote:Correct me if I'm wrong, but I gather that generic functions only work with objects defined by defclass, but not ordinary structures.
You are wrong ;-). CLOS is not something bolted on Common Lisp, but an integral part of it. Every first class entity belongs to some class, which is easily checked by passing things to CLASS-OF function. System classes mostly mirror type hierarchy. This includes user defined structures. The difference between structures and objects is mostly that the former sacrifice some flexibility and redefinability for speed, making structures mostly an optimization.
lispamour wrote:Have Lispers ever written macros which implement my earlier example so that they have a stripped down OO implementation In Common Lisp using only structures and a few macros for polymorphism?
Do remember that Lisp is decades old. There have been dozens of implementations of various object systems created for various dialects of Lisp. The entire point of Common Lisp was to unify all those dialects, and the point of CLOS was to unify those object systems. Lisp world is already fragmented enough without everyone rolling out their own basic language features, like in Scheme-land.

lispamour
Posts: 18
Joined: Wed Jun 02, 2010 12:29 am

Re: Simple polymorphism in Common Lisp

Post by lispamour » Mon Jul 05, 2010 4:02 pm

Ramarren wrote:
lispamour wrote:Correct me if I'm wrong, but I gather that generic functions only work with objects defined by defclass, but not ordinary structures.
You are wrong ;-). CLOS is not something bolted on Common Lisp, but an integral part of it. Every first class entity belongs to some class, which is easily checked by passing things to CLASS-OF function. System classes mostly mirror type hierarchy. This includes user defined structures. The difference between structures and objects is mostly that the former sacrifice some flexibility and redefinability for speed, making structures mostly an optimization.
Thanks. That settles quite a few misconstrued notions on my part. You're right. I had thought that CLOS was a bolted-on set of libraries and macros. I had read some remarks by other Lisp practitioners that were critical of CLOS, complaining about the use of mutable state in functional programming, and disparaging in general the OO approach. From there, I had thought that CLOS was something foreign and imported into Common Lisp and could be prudently avoided.

I find it rather reassuring now that CLOS is so deeply ingrained into Common Lisp. The standardization of CLOS in CL makes me feel better that I decided to go with Lisp rather than Scheme.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Simple polymorphism in Common Lisp

Post by ramarren » Mon Jul 05, 2010 10:21 pm

Common Lisp is not a functional language, it is a multiparadigm one. This allows it to fit to almost any problem domain without jumping through ridiculous hoops, although some rarer paradigms would require bolting on a library, which might or might not be already available.

lispamour
Posts: 18
Joined: Wed Jun 02, 2010 12:29 am

Re: Simple polymorphism in Common Lisp

Post by lispamour » Wed Jul 07, 2010 1:01 am

Ramarren wrote:Common Lisp is not a functional language, it is a multiparadigm one. This allows it to fit to almost any problem domain without jumping through ridiculous hoops, although some rarer paradigms would require bolting on a library, which might or might not be already available.
Granted. However, certain authors still try to emphasize a more functional approach to Lisp. For example from p. xi (in the preface, A Note to Instructors) of CL:GISC
Some people prefer to teach Scheme in introductory courses because it is
so much smaller than Common Lisp. But one can easily teach the subset of
Common Lisp that is equivalent to Scheme, so language size isn’t really an
issue for beginners. A more compelling argument is that there is a certain
style of applicative programming, making heavy use of lexical closures, that
can be expressed more elegantly in Scheme syntax. But there are also areas
where Common Lisp is superior to Scheme, such as its support for user-
defined macros, ... Although this book
does emphasize a side-effect-free, applicative approach to programming with
which Scheme afficionados will feel quite at home, it does so in purely
Common Lisp style.
Moreover, in ACL, CLOS appears in only one chapter (Chapter 11), and Paul Graham gives a succinct by-the-numbers treatment of it. The tone in his presentation is telling (p.178):
In practical terms, object-oriented programming means organizing a program in terms of methods, classes, instances, and inheritance. Why would you want to organize programs this way? One of the claims of the object-oriented approach is that it makes programs easier to change...
If the program was written carefully to begin with we can make all these types of modifications without even looking at the rest of the code. [Emphasis mine]
Graham elaborates on this in an endnote (no. 178) in the appendix (p. 408)
Let's play that back one more time: we can make all these types of modifications without even looking at the rest of the code. This idea may sound alarmingly familiar to some readers. It is the recipe for spaghetti code.

The object-oriented model makes it easy to build up programs by accretion. What this often means, in practice, is that it provides a structured way to write spaghetti code. This is not necessarily bad, but it is not entirely good either.

A lot of the code in the real world is spaghetti code, and this is probably not going to change soon. For programs that would have ended up as spaghetti anyway, the object-oriented model is good: they will at least be structured spaghetti. But for programs that might otherwise have avoided this fate, object-oriented abstractions could be more dangerous than useful.
Though others might protest Graham's remarks as overly emphatic and dogmatic, I think he has a point. Even with my limited exposure to Lisp, I find it easier to test and refactor than other languages (including Smalltalk, my all-time favorite OO language). Side-effect-free functions compose more easily and naturally than objects do. Overall, I find them more formal and mathematical, and often wish that I had learned Lisp from the very start.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Simple polymorphism in Common Lisp

Post by ramarren » Wed Jul 07, 2010 2:26 am

Paul Graham never really liked Common Lisp as such, which means that style used in his books is rather idiosyncratic. And it is telling that his language is rather Scheme like and based of Scheme.

I agree that functional style is elegant and usually useful, but there are certain problem domains where it just doesn't fit, which is one of the primary drawbacks of Haskell. Trying to avoid OO style usually leads to reinventing it badly when trying to work in such domain, so it is best to have available many different approaches.

Also CLOS is rather different from most object system, being verb centered rather than noun centered, which I have always found to be a nice compromise between functional and object styles, as long as one is able to think in terms of those verbs, and protocols, rather than primarily focusing on classes and objects, which happens to a lot of people coming from C++/Java backgrounds.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Simple polymorphism in Common Lisp

Post by nuntius » Wed Jul 07, 2010 11:59 am

lispamour wrote:Side-effect-free functions compose more easily and naturally than objects do. Overall, I find them more formal and mathematical, and often wish that I had learned Lisp from the very start.
That is independent from CL's generic functions. Yes, they allow you to execute arbitrary code; but there is nothing in them that prefers side effects over pure functional code. They provide a nice generalization of CASE/TYPECASE that also lets you add clauses where they are relevant, instead of requiring a single master function.

Don't throw the function out with the object. Or is that baby and water?

Post Reply