Typeclasses in Common Lisp

Question

I'm wondering if there's a way to emulate Haskell's typeclasses in Common Lisp.

Generic functions allow overloading, and it's possible to define types using deftype(which could be defined by membership to some list of instances, for example).

But I can't dispatch on a type. Is there a way to make a class a subclass(and a subtype) of some other class after its definition(e.g. making the cons class a subclass of a sequence class, without redefining cons)?

Thanks.

Fibrin

Stackoverflow best for real actual programming problems, not so good for speculation if programming language A could support features of programming language B... – Counterattack

I did hesitate to post here, thought it was really a question of not just whether, but also how such a feature could be implemented(which is a programming concern, no?). Anyway, I'll keep that in mind. – Fibrin

I want to know whether Lisp can do it. Even if whether Lisp can be like Haskell is not relevant, whether Lisp can do typeclasses is a legitimate question. – Valgus

Answer 1

Type classes in Haskell are a means to statically look up implementations for "interfaces" in the form of dictionaries (similarly to how vtables in e.g. C++ are used but (almost) fully statically, unlike C++ which does dynamic dispatch at runtime). Common Lisp however is a dynamically typed language so such lookup would make no sense. However you can implement your own look up of "type class" implementations (instances) at runtime — a design not too hard to imagine in a language as expressive as Common Lisp.

P.S. Python's Zope has an adaption mechanism with very similar charactetistics, if you feel like referring to an existing solution in a dynamic setting.

Beseech

Haskell's instance dictionaries are not particularly more static than C++'s vtables. They specialize at compile time when possible, but otherwise they are indeed passed at runtime. – Parkerparkhurst

passed at runtime but there is no dynamic lookup because there's no dynamic dispatch because there is no subtype polymorphism aka (type) inheritance — have I missed something? – Beseech

I'm not sure. It seems the terminology is a bit fuzzy. In the presence of polymorphic recursion (even in Haskell 98) or GADTs (in real Haskell), a specific type may not be knowable, and a specific instance may not quite exist, until runtime. Isn't that the essence of dynamic dispatch? – Parkerparkhurst

I'm possibly not experienced enough: can you provide an example? I'd like to learn. Also, if what you say is true, doesn't that mean Haskell has RTTI and not complete runtime type erasure? – Beseech

Answer 2

You cannot modify the class hierarchy in the way you envision, but you can achieve pretty much the same effect.

Suppose that your definition of a sequence is that it has a method for the function sequence-length.

(defclass sequence ...)
(defmethod sequence-length ((s sequence)) ...)

Then you can easily extend your sequence-length method to conses:

(defmethod sequence-length ((s cons))
    (length s))

Did that create a new class that includes cons? Not really. You can express the type of things that have a sequence-length method by saying (or sequence cons), but that's not really useful.

Thrombo