lrphill <lrph...@sandia.gov> writes: > I remember that back in the early 80's (?) Douglas Hofstadter wrote > a series of articles for Scientific American called "Metamagical > Themas." Embedded in it was a sub-series (like 6-8 articles) about > Lisp. It was a pretty good gentle introduction (recursion, Towers of > Hanoi, etc.). But I don't know where to get them. I even wrote to > Hofstadter, who informed me that no, they weren't anywhere on > line. I don't even have paper copies of them. Anybody have them?
Hofstader's Metamagical Themas columns we're reprinted in 1989, and are currently available in a Basic Books edition. There are three articles, IIRC, about Lisp. They won't serve as a good tutorial for Common Lisp, but are an interesting read.
_Metamagical Themas : Questing for the Essence of Mind and Pattern_ Douglas Hofstadter Basic Books; ISBN: 0465045669 -- party naked
* lrphill <lrph...@sandia.gov> | I remember that back in the early 80's (?) Douglas Hofstadter wrote a | series of articles for Scientific American called "Metamagical Themas." | Embedded in it was a sub-series (like 6-8 articles) about Lisp. It was a | pretty good gentle introduction (recursion, Towers of Hanoi, etc.). But | I don't know where to get them. I even wrote to Hofstadter, who informed | me that no, they weren't anywhere on line. I don't even have paper | copies of them. Anybody have them?
upon question, my bookshelves returned with Douglas R. Hofstadter: "Metamagical Themas, Questing for the Essence of Mind and Pattern, an Interlocked Collection of Literary, Scientific and Artistic Studies". it's a Penguin paperback, acquisition date 1987-06-01, copyright Basic Books, Inc, 1985. the ISBN is probably useless, but is 0-14-008534-3.
books.com and amazon.com both report it in stock as a trade paperback March 1996 _reissue_ at USD 20 (retail USD 25). ISBN 0-465-04566-9.
it contains three articles on Lisp: Atoms and Lists; Lists and Recursion; Recursion and Generality; encompassing 59 pages out of 880 total.
#:Erik -- The Microsoft Dating Program -- where do you want to crash tonight?
lrphill <lrph...@sandia.gov> writes: > I remember that back in the early 80's (?) Douglas Hofstadter wrote a > series of articles for Scientific American called "Metamagical Themas." > Embedded in it was a sub-series (like 6-8 articles) about Lisp. It was a > pretty good gentle introduction (recursion, Towers of Hanoi, etc.). But > I don't know where to get them. I even wrote to Hofstadter, who informed > me that no, they weren't anywhere on line. I don't even have paper > copies of them. Anybody have them?
Douglas Hofstadter re-released his whole "Metamagical Themas" series (and then some) in book form. In the UK it is[1] available from Penguin as a paperback. Have a look on Amazon.com unter Hofstadter, Douglas R.: ``Metamagical Themas: Questing for the Essence of Mind and Pattern''.
Regs, Pierre.
Footnotes: [1] At least it was some four years ago. Haven't checked recently for geographical reasons... ;)
* lrphill wrote: > I remember that back in the early 80's (?) Douglas Hofstadter wrote a > series of articles for Scientific American called "Metamagical Themas." > Embedded in it was a sub-series (like 6-8 articles) about Lisp. It was a > pretty good gentle introduction (recursion, Towers of Hanoi, etc.). But > I don't know where to get them. I even wrote to Hofstadter, who informed > me that no, they weren't anywhere on line. I don't even have paper > copies of them. Anybody have them?
There was a book with them in, and the other articles he wrote. I think it was called `Metamagical Themas' too, I probably have it somewhere and could find ISBN &c.
Barry Margolin <bar...@bbnplanet.com> wrote: +--------------- | One reason why REDUCE is often used in favor of APPLY is that REDUCE | doesn't have a limit on the number of entries... | However, in the case of APPEND, the performance impact of REDUCE can be | severe. A single call to APPEND should only need to traverse and copy each | argument once, so it should be O(n). REDUCE of APPEND, on the other hand, | will end up being O(n^2) in both space and time... +---------------
Sounds like there's a need for a REDUCE that takes another (keyword?) arg to say how many things to pass at once to the function you're REDUCE'ing the list on, sort of like the "xargs" program in Unix, where:
will never call try to call a single involcation of "foo" with more args [in either number of total character count] than the system limit, even though there may be many more than that generated by the "find".
With the equivalent refinement to REDUCE, you could pass large (but not *too* large) "gulps" to APPEND at once. Maybe something like this:
Or if you knew something about the way a specific compiler generated code, e.g., that there was a limit on the number of args that could be passed in regeisters, you might set "&max-args" lower:
< Barry Margolin <bar...@bbnplanet.com> wrote: < +--------------- < | One reason why REDUCE is often used in favor of APPLY is that REDUCE < | doesn't have a limit on the number of entries... < | However, in the case of APPEND, the performance impact of REDUCE can be < | severe. A single call to APPEND should only need to traverse and copy each < | argument once, so it should be O(n). REDUCE of APPEND, on the other hand, < | will end up being O(n^2) in both space and time... < +--------------- < < Sounds like there's a need for a REDUCE that takes another (keyword?) arg < to say how many things to pass at once to the function you're REDUCE'ing < the list on, sort of like the "xargs" program in Unix, where: < < % find {path}... {predicates}... -print | xargs foo
> * Dobes Vandermeer <do...@mindless.com> > | Ill be honest.. I've been to both places, and both are completely > | hopeless attempt to describe the language. > | Nevertheless, its pretty frustrating learning LISP at first, with such > | poor material, but once you get into the swing of things you can figure > | it out with the help of a book, instructor, or newsgroup.
> sigh. for me, it's more than just "pretty frustrating" to have to listen > to whining losers who can't read technical literature to learn something > highly tehcnical in nature, and who blame the literature, not themselves.
Its even more frusterating to listen to whining losers attempt to flame others for having a difference in opinion. I am sorry if my individuality offends you.. but please take your crap to alt.flames
Compare and contrast the following two statements:
1) It is a poor craftsman who blames the tools 2) It is a poor teacher that blames the students
(Personally, I blame the Internet because no matter how often you post a list of good books, people have missed it and request it again.)
Three GREAT Lisp books: "On Lisp" by Graham (small and really damn good. Not as small and good as Kernighan and Ritchie, but definitely leaning in that direction.)
"Paradigms of AI Programming" by Norvig (big and beefy with lots of examples)
"Concrete Abstractions" by Max Hailperin et al. (This last one is really about Scheme, not Lisp, and my friend wrote it, but it's a cool book, so you should check it out. You can pre-order it at www.amazon.com now, and also read a description by the author. It should be relatively inexpensive when it does ship.)
> Arrays are cumbersome and wasteful for storing things which need to be > accessed sequentially, also I believe that arrays can be slower to > initially allocate (dynamically) than a cons cell or two. On the other > hand, arrays usually take up less space, but (cons 1 2) is probably > equal to #(1 2).
In most lisp implementations, the list '(1 2) will take up less space than the array #(1 2), because arrays have some overhead for storing type information (which usually takes up an additional machine word on everything except lisp machines) and information about the number of dimensions and their limits. This will often be 3 to 5 machine words for one-dimensional arrays.
Conses on the other hand, typically have no overhead beyond the storage space for the pointers to their values. [Type codes on stock hardware are embedded in the pointers to conses or handled in some other way that doesn't require an additional word]. True lists have the need for one additional word to hold the (hidden) pointer to NIL in the last cons.
Therefore you would often get the following space requirements:
(1 . 2) 2 words (1 2) 3 words #(1 2) 5 to 7 words (2 words + overhead of 3 to 5)
The upshot of this is that in most lisp implementations you will have the following space requirements:
List N + 1 words Vector N + C words where C is the array overhead.
-- Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
> Steve Gonedes <jgone...@worldnet.att.net> writes:
> > Arrays are cumbersome and wasteful for storing things which need to be > > accessed sequentially, also I believe that arrays can be slower to > > initially allocate (dynamically) than a cons cell or two. On the other > > hand, arrays usually take up less space, but (cons 1 2) is probably > > equal to #(1 2).
This is true in Allegro CL.
> In most lisp implementations, the list '(1 2) will take up less space > than the array #(1 2), because arrays have some overhead for storing > type information (which usually takes up an additional machine word on > everything except lisp machines) and information about the number of > dimensions and their limits. This will often be 3 to 5 machine words > for one-dimensional arrays.
This may be true for lisp implementations on lisp machines, but it is not true for Allegro CL. Other stock-hardware vendors will have to comment on their own implementations. In Allegro CL, a simple-array has one word of overhead.
> Conses on the other hand, typically have no overhead beyond the storage > space for the pointers to their values. [Type codes on stock hardware > are embedded in the pointers to conses or handled in some other way that > doesn't require an additional word].
This is true in Allegro CL; conses are two words each.
> True lists have the need for one > additional word to hold the (hidden) pointer to NIL in the last cons.
This would be true for lisp machines where cdr-coding is possible (practical), but I don't know of any stock-hardware lisp implementations which implement cdr-coding (I would of course be very interested in hearing of any that do, along with the experiences of profiling such an implementation). In Allegro CL, lists cost two words per element.
> Therefore you would often get the following space requirements:
> (1 . 2) 2 words
Yes
> (1 2) 3 words
4 words in Allegro CL
> #(1 2) 5 to 7 words (2 words + overhead of 3 to 5)
4 words in Allegro CL (3 words rounded up to the nearest 2-word boundary, for tagging purposes).
> The upshot of this is that in most lisp implementations you will have > the following space requirements:
> List N + 1 words
N * 2 in Allegro CL
> Vector N + C words where C is the array overhead.
N + 1 [+ 1] in Allegro CL
> -- > Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
-- Duane Rettig Franz Inc. http://www.franz.com/ (www) 1995 University Ave Suite 275 Berkeley, CA 94704 Phone: (510) 548-3600; FAX: (510) 548-8253 du...@Franz.COM (internet)
> The upshot of this is that in most lisp implementations you will have > the following space requirements: > List N + 1 words
2N words. Each cons cell has a car & cdr pointer, unless it's cdr coded (do any implementations cdr code now?). And lists often have have rotten locality, which can cost you a lot (copying GCs should make this better over time, I don't know if they really do in practice).
> Vector N + C words where C is the array overhead.
> On 12 Nov 1998 09:40:24 -0800, Thomas A. Russ <t...@sevak.isi.edu> wrote: > > Therefore you would often get the following space requirements:
> > (1 . 2) 2 words > > (1 2) 3 words
> Given that you'd said 2 words for a cons, shouldn't the above be:
> (1 . 2) 2 words > (1 2) 4 words
> Isn't the list (1 2) two conses? As in:
> (1 . (2 . NIL))
> Or am I missing something?
No, you are correct.
I answered too quickly and miscounted the conses. Oops.
Excursion: Although I wasn't thinking of it when I made my initial response, there was a technique called cdr-coding that allowed a more space efficient storage of lists by laying them out more like arrays.
-- Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
> Excursion: Although I wasn't thinking of it when I made my initial > response, there was a technique called cdr-coding that allowed a more > space efficient storage of lists by laying them out more like arrays.
Cdr coding trades off address space (it requires 2 bits per pointer regardless of whether the pointer is a cons), and performace (calls to CDR must call CAR first to see if the CDR exists), for improved space efficiency (CDR coded lists can be up to half the size).
We did an analysis at LMI in 1985 and decided that the tradeoff wasn't worth it anymore. Modern systems have a lot more memory, and modern lisps support vectors, arrays, and defstructs. If I remember correctly, a typical Lisp machine band had only about 20% conses and less than half of them could take advantage of CDR codes.
CDR coding does have the one feature that you can easily represent the stack as a CDR coded list. This was used to advantage on the Lisp Machine for handling &rest arguments and a couple of other quirky hacks.
