From: =?ISO-8859-15?Q?Andr=E9_Thieme?=
Subject: How to dynamically create structs?
Date:
Message-ID: <d5q6qu$74l$1@ulric.tng.de>
A friend of mine, whom I teaching a bit of CL was inspired by Peter
Seibels PCL to write a little database program (chapter 3 of PCL).
At the moment he has a special variable *db* which is a list of
association lists, where each association list is a dataset. The user of
his database-program is allowed to enter how many categories he want and
can then name then. So it is not hardcoded in the sources what columns a
database has.
Now he thinks it is time to change the datatype of *db*. A good
candidate looks like a hashtable. When a user enters 20k entries and
wants to sort them or go through them access to a hashtable might be
much faster than traversing such a long list. Arrays could also be nice,
however, he doesn't know how many entries a user will enter into the db,
so a hashtable is nice as it can grow easily.
Now the real problem is: what datatype should he use for the datasets?
At the moment they are association lists. These could also be
hashtables, so he would have a hashtable full of hashtables. But there
will usually be less than 20 categories (columns), so I think
association lists are faster with few entries.
An idea are structures. These look like an ideal datatype. The problem
is that we are not sure how to create them dynamically at runtime. At
the moment my plan is: let the user enter all categories (for example:
first name, last name, age, address), let him chose a name for his db
(let's say "address") and then we create a list
(list 'defstruct (intern "ADDRESS")) to which we append the categories
as symbols:
(dolist (category '("first-name" "last-name" "age" "address"))
(setf struct (append struct (list (intern (string-upcase category))))))
CL-USER> struct
(DEFSTRUCT ADDRESS FIRST-NAME LAST-NAME AGE ADDRESS)
Some days ago I read in this newsgroup that someone who is new to Lisp
should not use EVAL for the first year.. something like that.
Now with my idea my friend could eval the list STRUCT at runtime and get
his structure which he could then use for the datasets and save them in
a hashtable.
So what would be the "real" solution without eval which is also good for
newbies?
And by the way, what do experienced users use eval for? And when?
Andr�
--
>But there
>will usually be less than 20 categories (columns), so I think
>association lists are faster with few entries.
Step 1: search through 20k entries in a hashtable to find an alist.
Step 2: search through 20 entries in the alist.
In the above program, which one looks like the bottleneck?
The idea of replacing that alist with a struct sounds annoying to me.
Every time you want to get "age" out of the "person" in your database
you will need to invoke the function person-age. This will require
concatenating three strings (person, age, -) then treating the result
as a function symbol. Also, in addition to the annoyance of programming
all this, the process of concatenating strings is probably slower than
searching the alist, so there goes any speed you were trying to get out
of this trick.
My advice: the alist would be fine. I would actually go with a hash
table just for uniformity. Forget about the speed difference - it will
be negligible.
>And by the way, what do experienced users use eval for?
>And when?
I don't know yet, but I expect Paul Graham's "On Lisp: Advanced
Techniques for Common Lisp" to teach me that. Until then I'll be
patient and not use it.
Andr� Thieme <······························@justmail.de> writes:
> A friend of mine, whom I teaching a bit of CL was inspired by Peter
> Seibels PCL to write a little database program (chapter 3 of PCL).
>
> At the moment he has a special variable *db* which is a list of
> association lists, where each association list is a dataset. The user
> of his database-program is allowed to enter how many categories he
> want and can then name then. So it is not hardcoded in the sources
> what columns a database has.
>
> Now he thinks it is time to change the datatype of *db*. A good
> candidate looks like a hashtable. When a user enters 20k entries and
> wants to sort them or go through them access to a hashtable might be
> much faster than traversing such a long list. Arrays could also be
> nice, however, he doesn't know how many entries a user will enter into
> the db, so a hashtable is nice as it can grow easily.
>
> Now the real problem is: what datatype should he use for the datasets?
> At the moment they are association lists. These could also be
> hashtables, so he would have a hashtable full of hashtables. But there
> will usually be less than 20 categories (columns), so I think
> association lists are faster with few entries.
> An idea are structures. These look like an ideal datatype. The problem
> is that we are not sure how to create them dynamically at runtime. At
> the moment my plan is: let the user enter all categories (for example:
> first name, last name, age, address), let him chose a name for his db
> (let's say "address") and then we create a list
> (list 'defstruct (intern "ADDRESS")) to which we append the categories
> as symbols:
>
> (dolist (category '("first-name" "last-name" "age" "address"))
> (setf struct (append struct (list (intern (string-upcase category))))))
>
> CL-USER> struct
> (DEFSTRUCT ADDRESS FIRST-NAME LAST-NAME AGE ADDRESS)
>
>
> Some days ago I read in this newsgroup that someone who is new to Lisp
> should not use EVAL for the first year.. something like that.
> Now with my idea my friend could eval the list STRUCT at runtime and
> get his structure which he could then use for the datasets and save
> them in a hashtable.
> So what would be the "real" solution without eval which is also good
> for newbies?
> And by the way, what do experienced users use eval for? And when?
I think that would be a valid use of eval. Types have no lexical
scope, so the reasons why eval is frowned upon for normal code don't
stand.
But since there's not (standard if at all) introspective API for
structures, it might still be worthwhile avoid runtime defstruct and
eval.
For example, assume you extend this db to handle several tables:
(select '(:title :duration)
(where :artist "Ensemble Gilles Binchois")
:from :cd)
(select '(:title)
(where :artist "Ensemble Gilles Binchois")
:from :partition)
From the keywords :title :duration :cd :artist :partitions you'll have
to find the symbols named: CD-TITLE CD-DURATION CD-ARTIST
PARTITION-TITLE and PARTITION-ARTIST to be able to fetch the wanted
fields from the structures.
You might as well use your own "symbol table".
(defmacro deftable (name &rest columns)
`(progn
(defparameter ,name (make-hash-table :test (function eql)
:size ,(length columns)))
(setf ,@(loop for column in columns
for index from 0
nconc `((gethash ,(intern (string column) "KEYWORD") ,name)
,index)))
(defun ,(intern (format nil "MAKE-~A" name)) (&key ,@columns)
(make-array '(,(length columns))
:initial-contents (list ,@columns)))
',name))
(defun get-field (row column table)
(aref row (or (gethash column table)
(error "No column ~A in table ~A" column table))))
(deftable partition title composer editor)
(setf p (make-partition :title "La jeune fille et la mort"
:composer "Franz Schubert" :editor "Czerny."))
(print (get-field p :title partition))
(deftable cd title artist reference)
(setf c (make-cd :title "Quartets de Schubert"
:artist "Quatuor Sine Nomine"
:reference "123456789"))
(print (get-field c :artist cd))
(defun select (fields where &key ((:from table) nil table-p))
(unless table-p (error ":FROM TABLE is mandatory"))
(mapcar
(lambda (row) (format t "~{~A~^ ~}~%"
(if (equal '(*) fields)
(coerce row 'list)
(mapcar (lambda (field) (get-field row field table)) fields))))
(select-rows where (find-table *db* table))))
And if you wanted to be able to manage several databases at the same
time, you'd even put the tables into data structures (a hash-table
again?) instead of using defparameter in deftable.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
I use a combination of standard class instances and keyword-value
plists to manage large amounts of data stored in CSV files. We found
CSV files to be the most universally accessable and require very little
maintenance. I can send you some of the code if you are interested.
Eval is very useful when you need to evaluate an expression, but most
of the time a macro form with backquotes and at-signs will accomplish
the same thing.
M
Andr� Thieme wrote:
>
[...]
> Some days ago I read in this newsgroup that someone who is new to Lisp
> should not use EVAL for the first year.. something like that.
[...]
> And by the way, what do experienced users use eval for? And when?
The true reason for the existence of EVAL is to make newbies fall in
love with Lisp by opening their eyes in an instant to the universe of
new ideas and possibilities that the language offers. In other words,
newbies should "discover" it as soon as possible, although they are not
supposed to use it. Then they become Lisp programmers and they realize
that it's not as useful as it looked at first glance, but by that time
it's too late, they have fallen into the trap and they're hooked for life ;)
Alberto
CLOS classes and objects have more infrastructure
built in than structs do. Using eval for this
purpose would be fine (as I personally do not
know of a way to programmatically create classes)
As a side note each implementation of CL
supporting CLOS needs some functional interface
to define classes (without eval).
An example with using CLOS (on LispWorks).
(in-package :db-user)
(defclass db-base ()
((owner :initarg owner :initform nil)
(security :initform :standard)))
(defvar *db-classes* (make-hash-table))
(defun create-db-class (symbol direct-slots)
(assert (not (gethash symbol *db-classes*)))
(let ((new-class
(eval `(defclass ,symbol (db-base)
(,@(mapcar (lambda (slot-name)
(list slot-name :initarg slot-name))
direct-slots))))))
(setf (gethash symbol *db-classes*) new-class)))
(defun get-db-class-slots (db-class-symbol)
(let ((class (gethash db-class-symbol *db-classes*)))
(assert class)
(mapcar #'slot-definition-name (class-direct-slots class))))
(defun db-slot-values (instance)
(loop for slot-name in (get-db-class-slots (class-name (class-of instance)))
collect slot-name
collect (slot-value instance slot-name)))
DB-USER 19 > (create-db-class 'person '(name address age sex))
#<STANDARD-CLASS PERSON 2070E994>
DB-USER 20 > (get-db-class-slots 'person)
(NAME ADDRESS AGE SEX)
DB-USER 21 > (setf p (make-instance 'person 'name "Fred"
'address "Home"
'age 24
'sex 'male))
#<PERSON 20687ABC>
DB-USER 22 > (db-slot-values p)
(NAME "Fred" ADDRESS "Home" AGE 24 SEX MALE)
DB-USER 23 > (slot-value p 'age)
24
DB-USER 24 > (setf (slot-value p 'age) 25)
25
DB-USER 25 >
This approach would seem to allow you enough introspection
to do anything you would like.
Wade
On Thu, 12 May 2005 04:45:55 GMT, Wade Humeniuk wrote:
> CLOS classes and objects have more infrastructure
> built in than structs do. Using eval for this
> purpose would be fine (as I personally do not
> know of a way to programmatically create classes)
> As a side note each implementation of CL
> supporting CLOS needs some functional interface
> to define classes (without eval).
That's what the MOP function ENSURE-CLASS is for.
> An example with using CLOS (on LispWorks).
> (in-package :db-user)
> (defclass db-base ()
> ((owner :initarg owner :initform nil)
> (security :initform :standard)))
> (defvar *db-classes* (make-hash-table))
> (defun create-db-class (symbol direct-slots)
> (assert (not (gethash symbol *db-classes*)))
> (let ((new-class
> (eval `(defclass ,symbol (db-base)
> (,@(mapcar (lambda (slot-name)
> (list slot-name :initarg slot-name))
> direct-slots))))))
> (setf (gethash symbol *db-classes*) new-class)))
> (defun get-db-class-slots (db-class-symbol)
> (let ((class (gethash db-class-symbol *db-classes*)))
> (assert class)
> (mapcar #'slot-definition-name (class-direct-slots class))))
(gethash db-class-symbol *db-classes*) == (find-class db-class-symbol)
--
Must the citizen ever for a moment, or in the least degree, resign his
conscience to the legislator? Why has every man a conscience, then?
I think that we should be men first, and subjects afterwards. It is not
desirable to cultivate a respect for the law, so much as for the right.
The only obligation which I have a right to assume is to do at any time
what I think right.
-- Henry David Thoreau
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
Paul Foley (http://public.xdi.org/=pf) wrote:
> On Thu, 12 May 2005 04:45:55 GMT, Wade Humeniuk wrote:
>
>
>>CLOS classes and objects have more infrastructure
>>built in than structs do. Using eval for this
>>purpose would be fine (as I personally do not
>>know of a way to programmatically create classes)
>>As a side note each implementation of CL
>>supporting CLOS needs some functional interface
>>to define classes (without eval).
>
>
> That's what the MOP function ENSURE-CLASS is for.
>
Ah. I have really not looked closely at the MOP, but
this case shows a good use for it.
So create-db-class becomes, (no eval)
(defun create-db-class (symbol direct-slots)
(assert (not (gethash symbol *db-classes*)))
(let ((new-class
(clos:ensure-class symbol
:direct-superclasses '(db-base)
:direct-slots
(mapcar (lambda (slot)
(list :name slot :initargs (list slot)))
direct-slots))))
(setf (gethash symbol *db-classes*) new-class)))
Wade
On Thu, 12 May 2005 13:13:55 GMT, Wade Humeniuk wrote:
> Paul Foley (http://public.xdi.org/=pf) wrote:
>> On Thu, 12 May 2005 04:45:55 GMT, Wade Humeniuk wrote:
>>
>>> CLOS classes and objects have more infrastructure
>>> built in than structs do. Using eval for this
>>> purpose would be fine (as I personally do not
>>> know of a way to programmatically create classes)
>>> As a side note each implementation of CL
>>> supporting CLOS needs some functional interface
>>> to define classes (without eval).
>> That's what the MOP function ENSURE-CLASS is for.
>>
> Ah. I have really not looked closely at the MOP, but
> this case shows a good use for it.
> So create-db-class becomes, (no eval)
> (defun create-db-class (symbol direct-slots)
> (assert (not (gethash symbol *db-classes*)))
> (let ((new-class
> (clos:ensure-class symbol
> :direct-superclasses '(db-base)
> :direct-slots
> (mapcar (lambda (slot)
> (list :name slot :initargs (list slot)))
> direct-slots))))
> (setf (gethash symbol *db-classes*) new-class)))
You don't need *db-classes* at all.
(defun create-db-class (symbol direct-slots)
(assert (not (find-class symbol nil)))
(mop:ensure-class symbol ...))
--
Must the citizen ever for a moment, or in the least degree, resign his
conscience to the legislator? Why has every man a conscience, then?
I think that we should be men first, and subjects afterwards. It is not
desirable to cultivate a respect for the law, so much as for the right.
The only obligation which I have a right to assume is to do at any time
what I think right.
-- Henry David Thoreau
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
Andr� Thieme wrote:
> Some days ago I read in this newsgroup that someone who is new to Lisp
> should not use EVAL for the first year.. something like that.
This is a shortcut to avoid explaining what eval actually does. The
problem is: You have to understand what eval does in order to see why
it's better to avoid it. Newbies should avoid it because they don't
fully understand (yet) what it does. If we explained it, there would be
no use in suggesting to avoid it because then you'd already know.
This shortcut is taken because in the beginning other things are simply
more important.
The problem with eval is this: As soon as you invoke eval, you are
executing code at the meta-level. If you take a look at a metacircular
implementation of Lisp, you will see that eval is a function of the
implementation that is repeatedly invoked by the interpreter. When you
invoked eval at the base level, you are switching the context from the
base level to the interpreter / meta level. This can create a number of
problems and confusions.
Furthermore, this probably has performance impacts. Eval gets an
s-expression as a parameter that it has to destructure and (in most CL
implementations) compile before it can be executed. Compilation itself
is usally slow (only the result is fast).
Note that there are similar potential problems (mistaking base and meta
level) when writing macros. Newbies sometimes try to execute code at the
base level that should rather be executed by the code-generating macro
definition. This is no surprise because macros can be regarded as a
"compile-time" version of a metacircular interpreter, in the sense that
they are hooks in the Lisp compiler to extend the language. However,
problems with mistaking base and meta levels in macros usually lead to
obvious bugs when testing code, so there's no real issue here except
that this is a usual stumbling block in the learning curve of Lisp newbies.
Eval is more problematic because most of the time it does what you want,
and the problems are much more subtle.
> Now with my idea my friend could eval the list STRUCT at runtime and get
> his structure which he could then use for the datasets and save them in
> a hashtable.
> So what would be the "real" solution without eval which is also good for
> newbies?
> And by the way, what do experienced users use eval for? And when?
I sometimes (rarely) use it to execute def-style macros at runtime. So
your attempt to use it for defstruct is not that bad. However, as Paul
Foley already pointed out, it's better to use the CLOS MOP for this.
Since not all CL implementations provide a CLOS MOP, eval is the only
portable solution though.
Pascal
--
2nd European Lisp and Scheme Workshop
July 26 - Glasgow, Scotland - co-located with ECOOP 2005
http://lisp-ecoop05.bknr.net/