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.

Donnie

LISP programming is typically done in a completely different style. If you want to write C style code into LISP, you'd probably just be better off sticking to C. – Kurtz

This is why I am asking how this completely different style typically looks like. – Donnie

It contains a lot of lists! – Kurtz

For example: struct point {int x, int y;}; struct square {struct point pt1, struct point pt2; int col} sq; What would be the usual way to represent, store and access nested structures like this, also maybe more than two levels deep? – Donnie

You can do it exactly the same way, using CLOS, using conses, whatever fits your application, the example you gave me has no context at all. – Fou

Rudimentary C knowledge does not translate to Lisp. But years of C coding on big systems gives you plenty that translates to Lisp. Why? Because in Lisp you recognize all the things you've done clumsily in C that are being done in a concise, disciplined, slick way. – Abydos

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.

Speculum

I do not have specific problems with usage. I wanted to know, since many introductory Lisp texts neglect defstruct and C texts on the other side put a heavy emphasis on them, what the preferred Lisp construct is to hierarchically structure data. I know that CLOS does the job, but i dont think CLOS is introductory type material. As of now, I think plists are what most closely resembles simple C structs, even though they seem to be considered an outdated way to do this. – Donnie

@Donnie Don't use plists. Structures are a legacy feature. Most software will use CLOS classes for structured data. There are even books explaining the basics if CLOS and how to use it. On that level it is no more difficult than structs in C. Actually it is simpler, because Common Lisp lacks the feature of data layout. – Speculum

@kanak: I have added a few pointers to the end of my above answer. – Speculum

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.

Andreeandrei

I would argue that defstruct is more similar to a C++ struct while defclass is closer to Java/C#/C++ class. – Snowshed

Answer 3

Property Lists (plists)

Replacement

Answer 4

I think the idiomatic equivalent of a C struct is to not need to store the data in structs in the first place. I'd say at least 50% of the C-style code I've ported to Lisp, rather than storing the data in some elaborate structure, I just compute what it is I want to compute. C needs structs to store everything temporarily because its expressions are so weak.

If you a specific example of some C-style code, I'm sure we could demonstrate an idiomatic way to implement it in Lisp.

Beyond that, remember that Lisp's s-exps are hierarchical data. An if expression in Lisp, for example, is itself hierarchical data.

Krp

I dont have a specific example. – Donnie

Sorry, SO ate my comment: struct point {int x, y;}; struct square {point pt1, pt2; int col} sq; What would be the usual way to represent (and access) such hierarchical data, maybe several levels deep, like sq.pt1.x and sq.col would be done in C? – Donnie

I often represent (x,y) points as (x y) or (x . y) in Lisp. Once you get to squares (or certainly by the next step = "thing I'm putting the squares in"), I step back and ask what I'm using this for. You can defclass yourself a big hierarchy if you want but it's often not necessary. Most programming I do in Lisp isn't about putting things in structs. – Krp

I'm afraid this all sounds somewhat hypothetical and hand-wavey right now. Perhaps if we had an example of a problem to solve, or a program to write, this would be easier. You're asking about pt.x, which (even in other languages) is a means, not an ends. – Krp

I dont know how to rephrase my initial question better. I also do not have a specific problem to solve but am trying to learn the Lisp way of thinking. In C, in order to structure and describe your data, you group simple types together in structs and form new types, which are then combined to new structs and new types and so on. In the end you get a hierarchical description of all your data, which you then work with. Since defstruct seems to be a legacy/deprecated feature in Lisp, I was looking in how nowadays data are named/structeured in Lisp. – Donnie

I think defstruct is deprecated because defclass is better in pretty much every way. – Krp

Answer 5

(defclass point ()
          ( x y z))

(defun distance-from-origin (point)
               (with-slots (x y z)
                   point
                 (sqrt (+ (* x x) (* y y) (* z z)))))

I think this is kind of what I was looking for, can be found here:

http://cl-cookbook.sourceforge.net/clos-tutorial/index.html y

Goldfarb

Answer 6

Why not use hash tables? Every member in the struct can be a key in a hash table.

Reena

You probably can, but I wanted to know how it is usually done in Lisp, especially when you have to nest data. A hash table in a hash table in a hash table just to get something like square.pt1.x seems like overkill. – Donnie