What's the idiomatic equivalent of C structs in Lisp?

Question

In C-type languages, there is a strong emphasis on structs/records and objects from the very beginning and in every introductory book. Then, their complete systems are designed around managing such structs, their mutual relations and inheritance.

In Lisp documentation, you can usually find 1-2 pages about how Lisp "also" has a defstruct, a simple example, and thats usually it. Also, nesting of structures is never mentioned at all.

For someone coming from a C background, it first seems that organizing different data types hierarchically isnt the preferred method in Lisp, but apart from CLOS, which is a full blown object system and too complicated if you just want structs, and apart from craming everything into lists, there isnt an apparent way to transfer your C struct knowledge.

What is the idiomatic Lisp way of hierarchically organizing data which most resembles C structs?

--

I think the summary answer to my question would be: For beginner learning purposes, defstruct and/or plists, although "legacy features", can be used, since they most closely resemble C structs, but that they have been largerly superseded by the more flexible defclass/CLOS, which what most Lisp programs use today.

This was my first question on SO, so thanks everyone for your time answering it.

Answer 1

Use CLOS. It isn't complicated.

Otherwise use structures.

If you have a specific question how to use them, then just ask.

(defclass point ()
  ((x :type number)
   (y :type number)))

(defclass rectangle ()
  ((p1    :type point)
   (p2    :type point)
   (color :type color)))

Stuff like that eventually leads to interfaces like Rectangles in CLIM (the Common Lisp Interface Manager).

History

To expand on it a bit: Historically 'structures' have been used in some low-level situations. Structures have single inheritance and slot access is 'fast'. Some Lisp dialects have more to structures than what Common Lisp offers. Then from the mid-70s on various forms of object-oriented representations have been developed for Lisp. Most of the representation of structured objects moved from structures to some kind of object-oriented Lisp extension. Popular during the 80s were class-based systems like Flavors, LOOPS and others. Frame-based or prototype-based systems like KEE Units or Object Lisp were also popular. The first Macintosh Common Lisp used Object Lisp for all its UI and IO facilities. The MIT Lisp machine used Flavors basically everywhere. Starting in the mid 80s ANSI CL was developed. A common OO-system was developed especially for Common Lisp: CLOS. It was based on Flavors and Loops. During that time mostly nothing was done to really improve structures - besides implementors finding ways to improve the implementation and providing a shallow CLOS integration. For example structures don't provide any packing of data. If there are two slots of 4 bits content, there is no way to instruct Common Lisp to encode both slots into a single 8 bit memory region.

As an example you can see in the Lisp Machine Manual, chapter on structures (PDF), that it had much more complex structures than what Common Lisp provides. Some of that was already present in Maclisp in the 70s: DEFSTRUCT in the Maclisp manual.

CLOS, the Common Lisp Object System

Most people would agree that CLOS is a nice design. It sometimes leads to 'larger' code, mostly because identifiers can get long. But there is some CLOS code, like the one in the AMOP book, that is really nicely written and shows how it is supposed to be used.

Over time implementors had to deal with the challenge that developers wanted to use CLOS, but also wanted to have the 'speed' of structures. Which is even more a task with the 'full' CLOS, which includes the almost standard Meta Object Protocol (MOP) for CLOS. So there are some tricks that implementors provide. During the 80s some software used a switch, so it could compiled using structures or using CLOS - CLX (the low-level Common Lisp X11 interface was an example). The reason: on some computers and implementations CLOS was much slower than structures. Today it would be unusual to provide such a compilation switch.

If I look today at a good Common Lisp implementation, I would expect that it uses CLOS almost everywhere. STREAMs are CLOS classes. CONDITIONs are CLOS classes. The GUI toolkit uses CLOS classes. The editor uses CLOS. It might even integrate foreign classes (say, Objective C classes) into CLOS.

In any non-toy Common Lisp implementation CLOS will be the tool to provide structured data, generic behavior and a bunch of other things.

As mentioned in some of the other answers, in some places CLOS might not be needed.

Common Lisp can return more than one value from a function:

(defun calculate-coordinates (ship)
   (move-forward ship)
   (values (ship-x ship)
           (ship-y ship)))

One can store data in closures:

(defun create-distance-function (ship x y)
   (lambda ()
     (point-distance (ship-x ship) (ship-y ship) x y)))

For configuration one can use some kind of lists:

(defship ms-germany :initial-x 0 :initial-y 0)

You can bet that I would implement the ship model in CLOS.

A lesson from writing and maintaining CLOS software is that it needs to be carefully designed and CLOS is so powerful that one can create really complex software with it - a complexity which is often not a good idea. Refactor and simplify! Fortunately, for many tasks basic CLOS facilities are sufficient: DEFCLASS, DEFMETHOD and MAKE-INSTANCE.

Pointers to CLOS introductions

For a start, Richard P. Gabriel has his CLOS papers for download.

Also see:

• http://cl-cookbook.sourceforge.net/clos-tutorial/index.html
• A Brief Guide to CLOS
• Book chapter from Practical Common Lisp, Object Reorientation, Classes
• Book chapter from Practical Common Lisp, Object Reorientation, Generic Functions
• C++ Coder’s Newbie Guide to Lisp-style OO
• Book: The Art of the Metaobject Protocol. According to some guy named Alan Kay the most important computer science book in a decade, unfortunately written for Lispers ;-). The book explains how to modify or extend CLOS itself. It also includes a simple CLOS implementation as source. For normal users this book is not really needed, but the programming style is that of real Lisp experts.

Answer 2

Examples with defstruct are short and simple because there isn't much to say about them. C's structs are complicated:

• memory management

• complicated memory layout due to unions, inline nested structures In C, structs are also used for other purposes:

• to access memory

• due to the lack of polymorphism or ability to pass a value of 'any' type: it is idiomatic to pass around a void*
• due to inability to have other means of passing data; e.g., in Lisp you can pass a closure which has the needed data
• due to the lack of advanced calling conventions; some functions accept their arguments inside structures

In Common Lisp, defstruct is roughly equivalent to Java's/C#'s class: single inheritance, fixed slots, can be used as specifiers in defmethods (analogous to virtual methods). Structures are perfectly usable for nested data structures.

Lisp programs tend not to use deeply nested structures (Lisp's source code being the primary exception) due to that often more simple representations are possible.