For those who haven't heard about the book yet: it is a practical description of the main data structures and algorithms in use today. The book is also featuring a presentation of the most important algorithm development techniques, as well a examples of the real-world use cases in each chapter. It uses Common Lisp as an implementation language, and also contains a crash course into the language if you are not yet familiar with it.
I bought myself a copy of your book recently. I have not worked through it back to back, but I enjoyed taking a look at known things through the lens of CL.
However I have to admit that the reliance on additional external libraries kind of had me a bit disappointed, but I can understand the reasoning and advantages behind such a decision.
Is the goal of this book to teach algorithms to Lisp programmers, or to teach algorithms using Lisp as its a good pedagogical language, or something else?
Bought it yesterday when reading this and read it halfway now; I like it. And thanks for taking the effort writing it!
As for remarks;
I second the reliance on the additional libraries; I think most readers are in fact, as you say in the book, purist... And won't like his reliance. No matter if it makes things better or not.
To that point; I personally like your opinionatedness in the book; on HN (etc) you would be shot down for many remarks you make in the book, but I like them here from people and do like that about the writing.
I wouldn't put smileys :) in a book like this, but that's a matter of taste.
And maybe a proofread by a native English speaker could have been good, but nothing was bad per se, it's just, having worked for 5 years in Ukraine (Lviv/Kyiv), that I recognize the way sentences are constructed and that is sometimes not the most readable in English. But I am not native English, and, again, for this kind of book, it's definitely fine, it would just be a bit of icing on the cake.
Thanks for the feedback! I recognize the deficiencies of my English writing. Moreover, the current state of the book is, in fact, much-much better than the original manuscript thanks to the efforts of Dr. Robert Strandh, phoe, and Apress proofreaders. As for the residual ugliness -
c'est la vie...
It's great work anyway! The main point is the technical content; kudos for that! And of course persisting to write it to the very end instead of quitting like most of us do.
In the preface, I discuss a bit the topic of how algorithms are taught in the universities versus how they are actually used. I made a choice to lean heavily towards the "practical" approach. So, from the perspective of a student, this shouldn't be your principal manual, the theory isn't presented in the best possible way, to say the least. (As a manual I'd recommend Skiena, or you can use Cormen etc.) But if you read the book as supplementary material it can give you a different perspective on those theoretical concepts and, hopefully, you'll get more value from studying them as you'll see where it all leads and how you might be using the obtained knowledge in your further work.
As for Lisp, I don't think that picking it for any smart student should be a problem.
You're quite right that SICP is about the fundamentals. Progalgs is about writing efficient programs. It's for those who already understand the fundamentals.
Yes, I plan to have a paperback version for $20+shipment. If you send me an email to vseloved@gmail.com I'll include you in the distribution (and send the details on how to pay and receive a copy in a week or two)
thanks for the notice (my typing habit is such that I often don't press the keys hard enough which results in missing letters - easy to see thanks to the spellcheckers when a normal word is misspelled, not so hard for personal names though). Typo fixed
It depends on what you code and how. I hope the book explains some of the approaches and describes the tools that can be used to reduce that difference and avoid a tragedy :)
> but then just assumes that computational complexity and O-notation are known.
At the bottom, you can find a reference to the previously published chapters. Complexity & big-O was addressed in the initial. (This is part of a book, all the org details are explained in part 1)
> There is no path compression.
The second variant is path compression. Yes, it may also be implemented in find, but it will make the code more complicated, in my view.
> And then, the uf-union operation: No practical union-find implementation accesses the list of all entries in this operation.
You are correct here. I'll make a change, thanks.
> Also, uf-add seems to allow adding new entries to the data structure but does not add them to the points list
This isn't needed here as it is supposed that we already have the list of points, it's just not arranged for efficient disjoint test. I, actually, had the reference to it, initially, but removed as I considered it redundant. I
ll think of adding it back.
> At the bottom, you can find a reference to the previously published chapters. Complexity & big-O was addressed in the initial.
I stand corrected, thanks. I knew this was part of a book and did go to the sidebar to check the titles of older chapters, but there the first part is called '"Programming Algorithms" Book', not 'Introduction & Complexity' like at the bottom. Going only by the title, I didn't think there would be complexity there. My fault.
> The second variant is path compression.
Yes, but only on the "add" operation. It's more important to have it elsewhere. Imagine a set of elements {a, b, c, d, e} where you do a sequence of pairwise union operations on (a, b), (b, c), etc., and end up with the data structure degenerated into a linked list a -> b -> c -> d -> e. If you now repeatedly check whether a and b are in the same class, you end up searching the entire list twice, every time you do this search.
You could try adding path compression in union, but I don't think a complete, efficient solution is possible: You would always be able to construct small trees that you would have to link to produce bigger, deeper trees.
That's why path compression is always where it matters and can make a useful difference: In find. In the example above, depending on the details, you would have one or two full linear searches, and then every query on a and b would be constant time.
> Yes, it may also be implemented in find, but it will make the code more complicated, in my view.
That's one of the reasons why union-find might not be the best introductory data structure. As for your view, to some extent, when you teach standard stuff, your view is not as important as actually teaching what you claim to teach. If you claim to teach union-find, you don't get to pick something somewhat similar but with radically different complexity.
> This isn't needed here [...]. I ll think of adding it back.
No, don't! You're right that a full list of nodes is never needed by the data structure itself. A user of the data structure might need one, but also they might not. I have in the past used union-find in settings where it was more convenient not to have a complete list of entries.
I examined Union-Find in more detail and found the critical flaw in my description that you were pointing too. Unfortunately, I forgot about it and had a simplified view of this data structure that focused on improving Find but neglected Union. The funny thing is that it was discussed, at times, at group job interviews that I participated as one of the interviewers, and we didn't go these deep to uncover that flaw :) (or, maybe, it was long ago enough for me to forget).
Surely, that made the example not so bright (as we couldn't reduce everything to a constant-time version with very simple code), but I don't think that the example is inappropriate. It still remains quite simple from the code standpoint. Another reason I picked it was that it didn't require an explanation of any additional data-structure, even, an array, and all the information could be efficiently represented using structs. This still holds.
This was already discussed in great detail (greater than such minor thing should be) in the comments to the first and next chapter. And, by the way, Lispworks also allows it (see here: https://github.com/vseloved/rutils/pull/39 - a person even bothered to provide a fix to make it work there). So, get over it: this book is not about nitpicking but about trying to explain things in an intelligible and accessible manner. A luxury I didn't always have with these topics...
I'm not sure pointing out undefined behaviour is nitpicking. It could in some cases be crucial. At the very least, it ties your code to only some Common Lisp implementations.
I know you can assign to keywords in LispWorks (using a restart), but that should be done in your rutils library, wrapping the definition of :=, :*, :/. And then you should do the same for all other implementations, which may differ in what condition is signalled, and whether there really is a restart for this, and of course whether it actually is allowed in that implementation.
Sorry, getting back to the initial point: can you point to a statement in the standard that forbids assigning to symbol-function of keywords or dims it unspecified behavior? I see only this: http://www.lispworks.com/documentation/HyperSpec/Body/t_kwd.... that doesn't state anything like this. Besides these constraints, the keyword symbols are normal symbols so they should abide by the same rules.
Following your link:
"3. It causes the symbol to become a constant variable."
and following the link to constant variable: "constant variable n. a variable, the value of which can never change; that is, a keyword[1] or a named constant. ``The symbols t, nil, :direction, and most-positive-fixnum are constant variables.''"
This doesn't mention the function slot of the symbol, so one could perhaps argue that therefore the function slot is not meant to be a constant variable, but one could equally well argue the opposite. The various implementation obviously differ on this. That alone means that this is either undefined behaviour, or that some of them have this as a very long-standing bug, at least since their inception.
> This doesn't mention the function slot of the symbol, so one could perhaps argue that therefore the function slot is not meant to be a constant variable
Exactly
> but one could equally well argue the opposite
No, as variables and functions are different parts and there's a more general rule about functions applied to keywords.
Your argument seems to be based on a notion that keywords are something unique and special in CL. They are, but only to the extent that is specified in this section. Otherwise, they are the same as other symbols.
To me, Lisp is not about "forbidden all that's not explicitly allowed", but about "allowed all that's not explicitly forbidden" mentality. And it's, actually, an important trait of the language that makes me value it more than others. So, sorry, I value your opinion, but I think that such things as := need to exist if only to broaden the horizons of people with such opinions :)
I apologize for having said at the beginning that "This makes the book untrustworthy, whatever good features it might have." It was unwarranted, and not substantiated, and much too harsh.
I do however stand by my claim that it is undefined behaviour. (You could help by making the suggested changes to rutils.)
