Aug 04, 2005
Programming Languages Concepts
Terceiro commented about my post about lisp macros and pointed out why he had a bad impression of lisp while in college. He says that classes like Programming Languages Concepts are taught in a limited perspective and agrees with me that Sebesta's book doesn't go any further.Of course I've never taken a Programming Languages Concepts course, but for what I have seen in syllabus and stuff like that, even when things like high-order functions are mentioned is in a context like:
object orientation: java, C++ or your-favorite-language-here functional programming: Haskell or your-favorite-language-here
and so on. That's not bad, actually, but it would be even nicer to show how these paradigms really work from the inside out. It's good to know about classes, objects, inheritance and the syntax java provides for them, but for me is much more comforting to know that, even if my language provides a very sophisticated object-oriented system, I can build my own in my language using things like lexical closures or macros. That helps me to understand the underlining abstraction in a much deeper level.
It's comforting to know that 16 of 23 design patterns are either transparent (i.e. the language already have them for free) or very easy to implement in my language because of things like first-class types and functions, macros, method combination, multimethods, and modules. That shows that even if new buzzwords get invented and new half-working languages and tools to support these new buzzwords (let's not even talk about XML) get invented, having a flexible and powerful language allows me to implement new ideas on the top of the language without much fuss.
So what's my point? My point is that I would rather prefer if instead of showing one or two languages for each paradigm, they focused in showing how all paradigms can be used in each language. That would give a much deeper and thoughtful idea about the paradigms themselves, what languages are more flexible, how you can adapt a language for a new paradigm and so on. Imposible? I'm not sure, I've even seen a book about functional programming in C!
Posted at 15:00
Aug 03, 2005
Why is Lisp so great? or Why so many parenthesis?
The funny thing about Lisp is that everybody asks why it has so may parenthesis. Quite a few friends of mine who have studied Lisp in college don't like it that much. I couldn't really understand why, until I realized they usually take a class that uses the book Concepts of Programming Languages by Robert W. Sebesta as a textbook. I'm in no position to review this book because I haven't read it. But from what I've skimmed, Lisp is not very well represented in this book, to put it very nicely. He describes Lisp only as a functional programming language, tells a little bit about cons cells, and that's pretty much it! No object orientation in lisp, no syntactic abstraction, no meta-programming, and so on. My feeling is that if I didn't know Lisp and read this book I wouldn't be very impressed by Lisp.So why is Lisp so great and why so many parenthesis? These two different questions have the same answer; because Lisp have syntactic abstraction trough the use of macros. If you are used to macros in languages like C, forget it. Lisp macros have nothing to do with C macros, except by the unfortunate coincidence of having the same name.
Lisp syntax is composed of lisp expressions and it uses a prefix syntax so expressions can be represented unambiguously. And since lisp expressions can be nested, the representation of the program will be like a tree, pretty much like an abstract syntactic tree. And because lisp code is composed of lisp expressions, the code can be changed in compile-time or run-time. That's the idea of macros, they are programs that write programs. How that works? Imagine that the language doesn't have support for a construction like if elif ... elif-n else. In most languages there is not much you can do, you can't define if as a function like if(clause,elif-clause1,elif-clause2) because all the elif statements would be evaluated, and you want one to be evaluated only if the previous clause evaluated to false. In lisp you have special forms, usually defined as macros, that are evaluated differently. You could easily define this kind of if construct if it wasn't available in lisp.
This is a quick, dirty, and incomplete description of lisp syntax and macros. If you want a more deep and complete explanation, I recommend the chapter Syntax and Semantics of Practical Common Lisp. My point here is that you can expand the syntax the language in any way you can.
I have friends who are very impressed by Haskell's syntactic powers (who wouldn't? it's a very nice language). For example, the quick sort algorithm can be implemented in Haskell with as little code as:
qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y < - xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
While lisp has a more verbose implementation (In Paul Graham
(defun quicksort (vec l r)
(let ((i l)
(j r)
(p (svref vec (round (+ l r) 2)))) ; 1
(while (< = i j) ; 2
(while (< (svref vec i) p) (incf i))
(while (> (svref vec j) p) (decf j))
(when (< = i j)
(rotatef (svref vec i) (svref vec j))
(incf i)
(decf j)))
(if (> (- j l) 1) (quicksort vec l j)) ; 3
(if (> (- r i) 1) (quicksort vec i r)))
vec)
Although the lisp version is nice and elegant, why is the Haskell version so concise? Because it uses an appropriate abstraction called list comprehension. A few languages like Haskell, Python, and Miranda have list comprehension built-in. Common Lisp doesn't. So, how one would implement a major syntactic feature like list comprehension in a language like C or Pascal? It's "impossible" unless one have access to the source of the particular compiler he is working and change it to implement this feature. That would mean dealing with the parser of the compiler, recompiling the compiler, and so on. It would also mean that the language was changed and that the code written for this compiler wouldn't run in another compiler. Well in case you haven't noticed, lisp is different. You can change the language all the time and you don't have to change the compiler for that. In fact, if you do it in ANSI Common Lisp, your code will run in any Common Lisp implementation. So, in Miranda one can write list comprehension using a syntax like [x | x < - xs ; odd x]. That's very different from lisp, right? How about implementing list comprehension in lisp and been able to write directly in lisp the expression above as [x (x < - xs) (oddp x)]? That's what macros are for. Guy Lapalme has a 20+ lines macro for list comprehension in the article Implementation of a "Lisp comprehension" macro:
(defun open-bracket (stream ch)
(defmacro comp ((e &rest qs) l2)
(if (null qs) `(cons ,e ,l2) ; rule A
(let ((q1 (car qs))
(q (cdr qs)))
(if (not(eq (cadr q1) `< -)) ; a generator?
`(if ,q1 (comp (,e ,@q),l2) ,l2) ; rule B
(let ((v (car q1)) ; rule C
(l1 (third q1))
(h (gentemp "H-"))
(us (gentemp "US-"))
(us1 (gentemp "US1-")))
`(labels ((,h (,us) ; corresponds to a letrec
(if (null ,us) ,l2
(let ((,v (car ,us))
(,us1 (cdr ,us)))
(comp (,e ,@q) (,h ,us1))))))
(,h ,l1)))))))
(do ((l nil)
(c (read stream t nil t)(read stream t nil t)))
((eq c `|]|) `(comp ,(reverse l) ()))
(push c l)))
(defun closing-bracket (stream ch) `|]|)This is necessary to tell the lisp reader what to do when it sees an open or closing bracket:
(eval-when (compile load eval) (set-macro-character #\[ #'open-bracket) (set-macro-character #\] #'closing-bracket))And this is it! Less than 30 lines and you not only have a full implementation of list comprehension, but you have one that is very close to the mathematical representation (and close to Haskell's and Miranda's).
Having list comprehension, the quick sort algorithm can be expressed as:
(defun qsort (ax)
(and ax
(let ((a (car ax))
(x (cdr ax)))
(append (qsort [y (y < - x) (< y a)]) ; A
(list a) ; B
(qsort [y (y <- x) (>= y a)]))))) ; C
Which is very close to the Haskell code. The Haskell code has 5 lines and this has 7. But it hasn't to do with counting lines. I could represent it with the same number of lines as Haskell's version, if I kept the A, B, and C expressions together, like in Haskell version (second line).
(defun qsort (ax)
(and ax
(let ((a (car ax))
(x (cdr ax)))
(append (qsort [y (y < - x) (< y a)]) (list a) (qsort [y (y <- x) (>= y a)])))))
If the goal was to reduce lines, I would even get one line less then the Haskell version:
(defun qsort (ax)
(and ax
(let ((a (car ax)) (x (cdr ax)))
(append (qsort [y (y < - x) (< y a)]) (list a) (qsort [y (y <- x) (>= y a)])))))
But that's not the point. The point is that one can implement a different syntactic abstraction in lisp like it was part of the language. And because it captures the basic idea of the abstraction, it serves not only for one particular case but for all kinds of stuff. This is a very powerful technique and lispers use it all the time. Of course one (for example a python user) might think something like "all that trouble to implement what I already got in my language". But what if you are dealing with an abstraction that is different, specific and is not implemented in your language? In lisp all you have to do is to define a few macros...
update 2006-03-15:
The main point of this article is, of course, to show how Lisp can be extended and changed in any way you want. Don't have a feature in it? Just write it. But, as Tommy Hallgren pointed to me, Common Lisp already has a good support for lisp comprehension, especially using loop:
(defun qsort (lst)
(when lst
(let* ((x (car lst))
(xs (cdr lst))
(lt (loop for y in xs when (< y x) collect y))
(gte (loop for y in xs when (>= y x) collect y)))
(append (qsort lt) (list x) (qsort gte)))))
This code is as elegant, concise and easy to understand as the Haskell version. The great thing about Common Lisp is that the language has so many cool things that many times you will not have to extend it, even if you can.
The loop macro is very powerful and comprehensive. If you don't know it very well, start learning today!
Posted at 15:00
Aug 02, 2005
More books
Not only I'm getting older, but I'm getting nerdier :-) I just got my copy of Rosen's Discrete Mathematics and its Applications.
It's usually expensive (Amazon has it for $149!) but I got an used copy for $3.94 plus 9.79 for shipping), not bad isn't it? If you haven't tried, I really recommend buying used books at amazon. The prices are usually terrific and you can find brand new books.
The reason I got this book is because I was watching a few lectures of ArsDigita University on discrete mathematics and got hooked. And since I don't have a proper mathematical background, it's always good to me to learn more.
If you don't know ArsDigita University stop reading this and go fast here. They had the following courses and many of them are available online on video:
- Math for Computer Science - Tara Holm
- Structure and Interpretation of Computer Programs - Holly Yanco
- Discrete Math - Shai Simonson
- How Computers Work - Gill Pratt
- Object-oriented Program Design - David Goddeau
- Algorithms - Shai Simonson
- Systems - Luis Rodriguez
- Web Applications - Philip Greenspun
- Theory of Computation - Shai Simonson
- Artificial Intelligence - Patrick Winston
- Unix Workshop
- Database Management Systems - Ravi Jasuja
- Applied Probability - Tina Kapur
Posted at 15:00
Jul 28, 2005
Gut strings
I program in a 45+ year-old language, I use fountain pens, paper-based journals, and play the violin (which is an old instrument). Do you still need more proofs I'm old? I'm using unwound gut strings now. :-) Yeah, unwound sheep (but not cheap!) strings. I've been using wound gut strings for 4 years. I started with eudoxas and switched to olives a couple of years ago. I just love then and going back to synthetic strings is just not a choice. A always wanted to try unwound strings to see how they felt like, specially because the violin and viola players I admire most have used strings like that, but I never got the chance. Well, I decided to buy some and they just arrived. My setup is inspired by Heifetz's, so I'm using a Goldbrokat E, plain gut D and A (Pirastro Chorda) and wound gut G (Pirastro Olive). The sound is terrific already and I'm very curious to see how they'll involve during the next week.Posted at 15:00
Lisp videos
Why videos of programming languages are useful? Because you'll have the unique opportunity to see real-life hackers in action working with theirs language and environment of choice. I like to learn from books, specially because I can read really fast and skip things that I'm not interest or skim over parts I'm comfortable with. So I'm not usually interested in books-on-tape or video-classes. But is a great thing to see über hackers like Gerald Sussman and Hal Abeson in the videos lectures of SICP. One can learn much more than simply reading a book, specially because their lecture is not a "reading" of the book. The same goes to Lisp. It has a unique model of dynamic development that is difficult to capture on written words. Marco Baringer created a 20 minutes movie showing how to develop a simple application with uncommon web using slime. The movie was so successful that he made another movie (this time it has almost an hour!) showing a few slime features. Another great movie is Rainer Joswig's about Domain Specific Languages in Lisp. It's a response to an article by Martin Fowler. This movie is a great way to see how lisp hackers develop code and why lisp is such a great language. He also has a related article in his blog.Posted at 15:00