writing out lists sharing values
Masoud Pirnazar
and preserve any sharing of values between the lists, so I can read the
file and reconstruct the original structures?
For example,
list jane1 = (name "jane" age 14 mother (name "sue" age 32))
list john1 = (name "john" age 12 mother (name "sue" age 32))
where the (name "sue" age 32) list is actually shared between the two
items.
(actually in LISP, the symbols "name", "age" and "mother" are shared
too, but I will be writing them out as byte-code literals).
I want to output in compact binary form, not necessarily in a human
readable form. A C/C++ program will read the contents.
If there is code out there to do this, please point me to it.
My long-winded (and memory-expensive) method is below. I'm not sure if
the 'eq' method will work, i.e. if I can hash using object addresses.
make a hash table using 'eq' as the comparison (to compare memory
addresses)
(defun write-object (c)
"write 1 value/slot if it has not already been written, return its
address"
;; if have already written it, just use its address
(unless (setf addr (gethash ... c))
(setf addr (write-new-object c))
addr)
(defun write-new-object (c)
...writes contents of c to output,
(setf (gethash c) output-address-where-c-was-written)
return output-address-where-c-was-written)
to write contents of cons object c to output:
(let ((v1 (write-object (car c)))
(v2 (write-object (cdr c))))
(prog1 (get-current-output-address)
(write-address v1)
(write-address v2)))
Rainer Joswig
nospam-for...@poboxes.com wrote:
> Does anyone have ideas on how to write out a bunch of lists to a file
> and preserve any sharing of values between the lists, so I can read the
> file and reconstruct the original structures?
>
> For example,
> list jane1 = (name "jane" age 14 mother (name "sue" age 32))
> list john1 = (name "john" age 12 mother (name "sue" age 32))
(let ((*print-circle* t))
(print
(let ((some-list (list 'a 'b 'c)))
`(progn
(setf a ,(list 1 some-list))
(setf b ,(list 2 some-list))))))
writes
(PROGN (SETF A (1 #1=(A B C))) (SETF B (2 #1#)))
READ will construct a new list, with the same structure.
--
Rainer Joswig, Hamburg, Germany
Email: mailto:jos...@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
Marco Antoniotti
Rainer Joswig <jos...@corporate-world.lisp.de> writes:
> In article <39D2B0E3...@poboxes.com>,
> nospam-for...@poboxes.com wrote:
>
> > Does anyone have ideas on how to write out a bunch of lists to a file
> > and preserve any sharing of values between the lists, so I can read the
> > file and reconstruct the original structures?
> >
> > For example,
> > list jane1 = (name "jane" age 14 mother (name "sue" age 32))
> > list john1 = (name "john" age 12 mother (name "sue" age 32))
>
> (let ((*print-circle* t))
> (print
> (let ((some-list (list 'a 'b 'c)))
> `(progn
> (setf a ,(list 1 some-list))
> (setf b ,(list 2 some-list))))))
>
> writes
>
> (PROGN (SETF A (1 #1=(A B C))) (SETF B (2 #1#)))
>
> READ will construct a new list, with the same structure.
Excellent. Now, let's see the equivalent parser re-written (or better,
re-invented, in C/C++). :)
Cheers
--
Marco Antoniotti =============================================================
NYU Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://galt.mrl.nyu.edu/valis
Like DNA, such a language [Lisp] does not go out of style.
Paul Graham, ANSI Common Lisp
Rainer Joswig
<mar...@cs.nyu.edu> wrote:
> Rainer Joswig <jos...@corporate-world.lisp.de> writes:
>
> > In article <39D2B0E3...@poboxes.com>,
> > nospam-for...@poboxes.com wrote:
> >
> > > Does anyone have ideas on how to write out a bunch of lists to a file
> > > and preserve any sharing of values between the lists, so I can read the
> > > file and reconstruct the original structures?
> > >
> > > For example,
> > > list jane1 = (name "jane" age 14 mother (name "sue" age 32))
> > > list john1 = (name "john" age 12 mother (name "sue" age 32))
> >
> > (let ((*print-circle* t))
> > (print
> > (let ((some-list (list 'a 'b 'c)))
> > `(progn
> > (setf a ,(list 1 some-list))
> > (setf b ,(list 2 some-list))))))
> >
> > writes
> >
> > (PROGN (SETF A (1 #1=(A B C))) (SETF B (2 #1#)))
> >
> > READ will construct a new list, with the same structure.
>
As Kent pointed out, a should have added a quote, so you can evaluate
it:
(let ((*print-circle* t))
(print
(let ((some-list (list 'a 'b 'c)))
`(progn
(setf a ',(list 1 some-list))
(setf b ',(list 2 some-list))))))
> Excellent. Now, let's see the equivalent parser re-written (or better,
> re-invented, in C/C++). :)
But for XML. ;-)
Masoud Pirnazar
uses a hash table (the only solution I had come up with yesterday), so I'm
implementing my original solution for now.
FYI, here is the scaffolding for the code.
(defvar write-object-table nil "table of objects already written")
(defvar *addr* 0)
(defun write-address (v)
"write relative-address v to output buffer"
;;(format t "[~a]@~a " *addr* v)
(setf *addr* (1+ *addr*)))
(defun get-current-output-address () *addr*)
(defun write-object-init ()
(setf write-object-table (make-hash-table :key #'eq))
(setf *addr* 0)
(write-byte 0) ; reserve address 0 for nil
)
(defun write-byte (c) (setf *addr* (1+ *addr*)))
(defun write-object (c)
"write 1 value/slot if it has not already been written, return its output
address"
(if c
(or (gethash c write-object-table) ; if have already written it, just
use its address
(setf (gethash c write-object-table)(write-object-contents c)))
0 ;; nil object return 0 for address
))
(defmethod write-object-contents ((c cons))
"write contents of object c, return its address"
(let ((v1 (write-object (car c)))
(v2 (write-object (cdr c))))
(prog1 (get-current-output-address)
(format t "[~a]cons(~a,~a) " *addr* v1 v2)
(write-address v1)
(write-address v2))))
(defmethod write-object-contents ((c t))
"write contents of object c, return its address"
(format t "[~a]'~a " *addr* c)
(prog1 *addr*
(setf *addr* (+ 3 *addr*)))) ;; arbitraily take up 3 memory blocks, just
for testing purposes
for testing:
(progn
(setf some-list (list 'a 'b 'c))
(setf a (list 1 some-list))
(setf b (list 2 some-list))
(setf c (list a b))
(write-object-init)
(format t "a=") (write-object a) (format t "~%")
(format t "c=") (write-object c) (format t "~%")
;;(print-hash write-object-table)
(print some-list)
;;(write-object a) (format t "~%")
;;(write-object c)
(print a)
(print b)
(let ((*print-circle* t)) (print c)))
Marco Antoniotti
Rainer Joswig <jos...@corporate-world.lisp.de> writes:
> In article <y6cvgvg...@octagon.mrl.nyu.edu>, Marco Antoniotti
> <mar...@cs.nyu.edu> wrote:
>
> > Rainer Joswig <jos...@corporate-world.lisp.de> writes:
> >
> > > In article <39D2B0E3...@poboxes.com>,
> > > nospam-for...@poboxes.com wrote:
> > >
> > > > Does anyone have ideas on how to write out a bunch of lists to a file
> > > > and preserve any sharing of values between the lists, so I can read the
> > > > file and reconstruct the original structures?
> > > >
> > > > For example,
> > > > list jane1 = (name "jane" age 14 mother (name "sue" age 32))
> > > > list john1 = (name "john" age 12 mother (name "sue" age 32))
> > >
> > > (let ((*print-circle* t))
> > > (print
> > > (let ((some-list (list 'a 'b 'c)))
> > > `(progn
> > > (setf a ,(list 1 some-list))
> > > (setf b ,(list 2 some-list))))))
> > >
> > > writes
> > >
> > > (PROGN (SETF A (1 #1=(A B C))) (SETF B (2 #1#)))
> > >
> > > READ will construct a new list, with the same structure.
> >
>
> As Kent pointed out, a should have added a quote, so you can evaluate
> it:
>
> (let ((*print-circle* t))
> (print
> (let ((some-list (list 'a 'b 'c)))
> `(progn
> (setf a ',(list 1 some-list))
> (setf b ',(list 2 some-list))))))
>
>
> > Excellent. Now, let's see the equivalent parser re-written (or better,
> > re-invented, in C/C++). :)
>
> But for XML. ;-)
Of course. This is my understanding of XML. However, is there a
"standardized" way (for an appropriate definition of "standardized")
to define shared substructures?
(I don't know. I am just asking)
Steven M. Haflich
Marco Antoniotti wrote:
> Of course. This is my understanding of XML. However, is there a
> "standardized" way (for an appropriate definition of "standardized")
> to define shared substructures?
>
> (I don't know. I am just asking)
The ID and IDREF attributes provide for this. Think of them as
a surrogate memory address for a data structure that isn't smart enough
to live in memory and has been linearized. The potential advantage is
that sometimes an obvious existing attribute (e.g. a social security
number) can be used as the ID. The disadvantage is that a linearized
data structure has been, well, linearized.
Barry Margolin
Hmm, I wonder if the XML designers looked at Common Lisp -- those
attributes are suspiciously very similar to #n= and #n#.
--
Barry Margolin, bar...@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Erik Naggum
| Hmm, I wonder if the XML designers looked at Common Lisp -- those
| attributes are suspiciously very similar to #n= and #n#.
Well, fwiw, ID and IDREF are from SGML, and not new XMLisms. Their
use was originally only to provide more abstract identifications of
such things as figures, chapters, etc.
The XML crowd has been busy reinventing Lisp for data representation
from the start. The reason this pointy-haired syntax ever got off
the ground was that SGML makes a lot of sense in a very limited
problem domain and like the madman who gets a Phoney Doctor degree
in some irrelevant field can claim authority in any other field as
far as the TV-commercial-consuming public is concerned, if he is so
inclined and understands the machinery of marketing, but he is still
a madman and XML is still a pointy-haired syntax.
It has all the merits of a standard except that nobody is agreeing
on what to do with it. I haven't been able to find the one, truly
authoritative reference on XML that isn't subject to some number of
amendments that I'm never sure I have the complete set of, either.
The SGML designers didn't look at programming languages. At the
time, they though programming languages were designed to make life
harder for those who wanted to process documents. It wasn't false
at the time, but the animosity towards programmers and the desire to
"liberate documents from the programmers" caused a number of quite
interesting blunders, such as the incredibly botched notion of what
constitutes ambiguous grammar productions.
But I digress. To answer your question: Wonder not, it wasn't so.
The XML crowd is complete unto itself -- it does only exports, no
imports of either data or ideas. They're even trying to reinvent
the web in their own image. Of course Microsoft would embrace it.
I think everything should be expressed in SGML or XML, though, as
soon as we're through using it. Let the garbage information of the
world be encoded in XML. At least the archeologists of the future
will appreciate the way we poured liquid nitrogen over our data and
preserved it for eternal posterity with a syntax wholly unsuited to
living, evolving information.
#:Erik
--
If this is not what you expected, please alter your expectations.
Barry Margolin
> It has all the merits of a standard except that nobody is agreeing
> on what to do with it. I haven't been able to find the one, truly
> authoritative reference on XML that isn't subject to some number of
> amendments that I'm never sure I have the complete set of, either.
I think it's a little early to expect lots of stability in the XML arena.
IMHO, it should still be considered vaporware. Like many other Internet
technologies, the press releases make it seem like it's much further
developed than it really is. To some extent they need to do this with
substrate technologies like XML and Java, in order to get people started
playing with them so that the issues can be discovered. But it would be
nice if the articles in consumer-oriented publications would make it clear
that we're still a little way from widespread use of XML. Wireless
Internet is another technology where the hype is way ahead of reality (it's
a chicken-and-egg problem -- consumers want more content before purchasing
the services, and content providers want more customers before producing
WML pages -- so the service providers attract customers by making it sound
like there's lots of content available).
Espen Vestre
> we're still a little way from widespread use of XML.
it's amazing how fast it's spreading, though. One recent example: While
it's NeXt-derived father Mac OS X Server used curly-bracket-C-style
syntax for property lists in preference files, Mac OS X is using xml
property lists all over, it seems.
--
(espen)
Barry Margolin
It's not a problem when using it internally within a system -- any file
format is as good as any other, and you get to specify the interpretation
and use fully. The difficulties come when you're trying to specify public
file formats that are intended to be general enough to support applications
that have yet to be thought of.
For instance, if you're defining the XML format for a TV listing service,
you need to be able to predict all the attributes that someone might want
to display in a browser or search for with an agent. It's similar to
traditional database schema design, except that usually the schema designer
takes his instructions from the application designer (they're often the
same people), but on the web the application designers can be anyone in the
world.
Christopher Browne
the artist formerly known as Barry Margolin said:
>In article <w6lmw2m...@wallace.ws.nextra.no>,
>Espen Vestre <espen@*do-not-spam-me*.vestre.net> wrote:
>>Barry Margolin <bar...@genuity.net> writes:
>>
>>> we're still a little way from widespread use of XML.
>>
>>it's amazing how fast it's spreading, though. One recent example:
>>While it's NeXt-derived father Mac OS X Server used
>>curly-bracket-C-style syntax for property lists in preference files,
>>Mac OS X is using xml property lists all over, it seems.
>
>It's not a problem when using it internally within a system -- any file
>format is as good as any other, and you get to specify the interpretation
>and use fully. The difficulties come when you're trying to specify public
>file formats that are intended to be general enough to support applications
>that have yet to be thought of.
>
>For instance, if you're defining the XML format for a TV listing service,
>you need to be able to predict all the attributes that someone might want
>to display in a browser or search for with an agent. It's similar to
>traditional database schema design, except that usually the schema designer
>takes his instructions from the application designer (they're often the
>same people), but on the web the application designers can be anyone in the
>world.
The upside of XML (and anything "semantically equivalent" that can
express trees an the likes) is that while you may not be able to force
extra functionality into applications, you can at least have a
coherent way of attaching additional data in a way that shouldn't
interfere badly with the existing applications.
It's no big deal, in XML, to introduce an extra attribute ("property")
or an extra "subtree" of information. Applications that aren't aware
of the new entities/attributes can reasonably safely ignore them.
The same would still be generally true if you represented this stuff
as Lisp structures, or *step "property lists" (available to C-based
applications via libPropList; this is used by the WindowMaker window
manager and many related utilities, Balsa mail client, irssi IRC
client, FSViewer file viewer, and probably others), or even via
"Windows .ini"-style files (although in that case, there probably
isn't the ability to have "nested trees" to the same degree).
XML probably excites the folks that read "XML For Dummies" because
they might just expand their minds enough to grasp that it offers the
ability to have hierarchy, which _wasn't_ possible with the
traditional data interchange schemes, namely:
a) Comma Delimited files and
b) Fixed Record Length files.
Therein lies the likely excitement; we all know _here_ that there were
always _all sorts_ of ways to express this, with Lisp lists being the
canonical example that would come up here.
--
(concatenate 'string "cbbrowne" "@" "ntlug.org")
<http://www.ntlug.org/~cbbrowne/linux.html>
What do you get when you multiply six by nine?