Structure and Interpretation of Computer Programs
02 May 2012
With my recent motivations to learn Lisp, I’ve been feeling reconnected (or finally connected) to what Computer Science is really all about. This has given me a new interest in picking up on my math again and learn properly all of the math I should had groked back in college. The math that gives you the tools to be a better programmer, computer scientist, and thinker in general.
In order to start this and get the ball rolling, I am going to (finally) read Structure and Interpretation Of Computer Programs, this book has been in my shelf for a few years and I never actually got to sit and read it thoughtfully, maybe I wasn’t ready or maybe I am not smart enough to read it, but I will give it a serious shot this time, and as I work through the exercises, I am pretty sure I will be having to consult and read about math, since at least the first chapter exercises seem to be mostly math related.
I created a Github repository where I will be putting the source code of my solutions to the exercises in case you are interested in them.
After this I would probably tackle as many exercises in the Euler Project as I can, that will certainly be a good exercise in coding and mathematics in general.
I will be definitely writing about how I do and what I learn and the pieces I find most interesting as I go.
Exercises:
Chapter 1
1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 1.10, 1.11, 1.12, 1.16, 1.17, 1.18, 1.22, 1.23, 1.29, 1.30
Lisping and the word ladder puzzle
18 April 2012
I want to talk about Lisp because so far I can say that I am really loving it and I will certainly be spending more time with it and learning about it.
Allow me to quickly tell you about a little nice puzzle:
Word ladder Puzzle
This puzzle was invented by Lewis Carroll a long time ago, the puzzle is defined by three elements, a language (for our purposes a dictionary with plenty of words of the same length), a start word and an end word. The goal is to find a path between the two words by changing a single character at the time, and the resulting words from such change have to be valid words in the given language.
Example for HOME and MEAL:
HOME → HOLE → HOLD → HELD → HEAD → HEAL → MEAL
Solving it
So, armed with my new rudimentary skills of Common Lisp I decided to write a Lisp solver of this puzzle. The code is in Github, along with a ruby implementation I wrote a while ago. I will reproduce the Lisp version here in order to explain the way I solved it, maybe I can pique your interest and you want to learn about it too.
First, we have to have some dictionaries handy, I already have some up in github that you can download. Now that we have a nice dictionary, we have to read it and have it handy, in Common Lisp:
(defparameter *dictionary* ())
(defun read-dictionary-file (fname)
(with-open-file (stream fname)
(loop for line = (read-line stream nil 'foo)
until (eq line 'foo)
collect line)))
(defun initialize-dictionary (fname)
(let* ((dictionary (read-dictionary-file fname))
(first-len (length (first dictionary))))
(setq *dictionary*
(remove-if-not (lambda (word)
(eql (length word)
first-len))
dictionary))))
The first line simply defines a global variable named *dictionary* (the * around the name is a naming convention) to be an empty list. Then we declare two functions:
- read-dictionary-file
-
Opens the file with the given filename, reads every line and returns them as a list.
- initialize-dictionary
-
Calls read-dictionary-file and stores the given list in a local variable, then it gets the length of the first word in the dictionary and removes every word from the list if its length is not equals, a basic check, finally it saves the result into the *dictionary* global variable.
If you have a flavor of Common Lisp installed, we can already test this functions in the read-print-eval-loop (I am currently using clisp):
[10]> (initialize-dictionary "dictionaries/four-char-dictionary.txt")
("mitt" "that" "with" "they" "this" "have" "from" "word" "what" "were" "when"...
[11]> *dictionary*
("mitt" "that" "with" "they" "this" "have" "from" "word" ...
[12]> (length *dictionary*)
923
Now that we have our dictionary handy, let’s think a bit about the problem. We want to find a way between two given words, we start from one word, how do we know what our options are to move from a word to another?
A way to visualize this problem is as a graph, where every word is represented as node and the edges connect nodes which are apart only by a single character.
For example, in a dictionary with english words of four characters, the word “home” has the following neighbors:
Here’s the code to find the neighbors of a word in our dictionary in Lisp:
(defun one-apart-p (w1 w2)
(and (eql (length w1) (length w2))
(= 1 (loop
for c1 across w1
for c2 across w2
count (not (equalp c1 c2))))))
(defun find-neighbors (word dictionary)
(when (member word dictionary :test #'equalp)
(remove-if-not (lambda (x)
(one-apart-p word x))
dictionary)))
- one-apart-p
-
It’s a predicate, that is, it returns true or false. It is a convention in Common Lisp to suffix predicate functions with -p. What it does is that given two words, it loops across them counting how many differences they have. If they have only one difference it returns true, else false.
- find-neighbors
-
Takes a word and a dictionary and returns a list of all the words in the given dictionary that are one character apart from the given word. All its neighbors!
Running the code:
[61]> (find-neighbors "home" *dictionary*)
("some" "come" "hole" "hope" "hose" "Rome")
Now that we can find the adjacent words for each word in our dictionary, we can find our ladders. There are two basic ways to traverse the graph, which are:
- Breadth-first
-
We check the current level before moving onto the next one, that is, we check if our target word is in the neighbors list, in our example, home to meal we check if meal is in the neighbors of home, it is not so the next step is to move one level down, we do this by having a list of all the neighbors of the neighbors (recursivity), then we check again, if not we move down another level and so on. Wikipedia
- Depth-first
-
We get our list of neighbors, then we check against the first one, if it is not our target, we get its list of neighbors, check against the first one, if not we get its list of neighbors… you see what I mean, basically, you go as deep as you can in the graph, if you hit a dead-end you go back to a level where you have more neighbors and then you go deep on that too. Wikipedia has some nice animated gifs showing how this works. Wikipedia
In my implementation I chose breadth-first, is way faster than depth-first for this particular problem, other problems may be better served by a depth-first approach.
The code:
(defun find-ladder (first second dictionary)
(labels ((follow-ladders (ladders visited)
(let ((already-visited (nconc visited
(mapcar #'first ladders)))
(matching-ladder (find-if (lambda (ladder)
(equalp second (first ladder)))
ladders)))
(if matching-ladder
matching-ladder
(follow-ladders (mapcan (lambda (ladder)
(mapcar (lambda (neighbor)
(cons neighbor ladder))
(set-difference (find-neighbors (first ladder) dictionary)
already-visited
:test #'equalp)))
ladders)
already-visited)))))
(follow-ladders (list (list first)) nil)))
A bit long, but basically we are given two words and the dictionary, we define a local function with the labels keyword, this allows the function to call itself recursively.
Our local function takes two parameters, ladders and visited. Ladders is a list of lists where the first element is the word to follow, the function also creates two local variables, already-visited which holds a list of the nodes we have already checked and matching-ladder which checks if there is already a complete ladder.
If the ladder is found then return it and we are done. If not, follow-ladders calls itself recursively by adding the neighbors of all the current words to our ladders, always checking against already-visited so we don’t follow the same node twice.
find-ladder basically calls the local function by creating a list with the first word and an empty list of visited nodes.
Running the code:
[62]> (find-ladder "home" "meal" *dictionary*)
("meal" "heal" "head" "held" "hold" "hole" "home")
And that’s it! A breadth-first solver for the word ladder puzzle.
Closing remarks
One of the first shocks for programmers like me, accustomed to imperative languages (at the time of this writing I do C# for a living) is that there are too many parenthesis, but then I realized (thanks to Land Of Lisp) that they are simply lists of lists (or trees). Lisp is very homoiconic, which is a fancy word to say that the representation of the program is a primitive type of the programming language itself, this has the natural consequence of Lisp being able to process Lisp code itself, which is the concept of macros (unlike languages like C where a macro is simply text substitution), in Lisp functions take values and return values (as in every language) but macros take Lisp code and return Lisp code.
I am really liking Lisp, I will certainly be using it as often as I can to solve anything I can get my hands on to improve my almost non-existent skills. Which, if you are an amazing Lisper, please do not be offended if my code sucks, I am trying to learn, feel free to send me an email with any suggestion you may have!
Which reminds me, I would like to thank Peter Seibel, author of Coders at Work and Practical Common Lisp because he took the time to look at my original code and give me some very useful tips after I bugged him on IRC (go read his books, they are great).
Thank you Peter!
I shall learn Lisp
18 Mar 2012
I’ve been meaning to do this for a long time, finally get to learn Lisp, but for whatever reason I always end up procrastinating in this particular endeavor (and in others as well).
Everybody that already know Lisp say the same thing, that learning Lisp will forever change you as a programmer, this may seem over hyped but I truly believe such thing is possible, that learning a particular language can forever change the way you think about programming. I’ve felt such thing with a language I learned a long time ago: x86 assembly language, maybe not to the degree of Lisp, enlightening in the ways of computation, but I certainly have benefited a lot from my experience with assembly.
When I was learning to program, I wanted to make games, and I started learning QuickBasic, after some time I found it to be very slow to do anything interesting in the computer I had at the time (80386SX, 2MB RAM), the game coding community in QB back then suggested using a game programming library coded in assembly, there were many available (it was a very thriving community at the time), after playing with some, of course, I wanted to make my own, and CosmoX was born.
At first it had a very humble beginning but I found learning assembly and making my own graphic routines very fun, so I kept going and going, I began learning many intricacies of MS-DOS programming, like Expanded Memory and Extended Memory, I learned about 3D mathematics and added a matrix/vector math module using the FPU, custom “drivers” for the mouse/keyboard, so after a while, CosmoX got a bit popular in the QB community and some people/games began using it, talking about it, etc, it was a small community, but few times after that I’ve felt so much pride.
Now after all that reminiscence, the point at hand, I spent all those long nights learning assembly, crashing my computer and then trying to find what piece of code that was misbehaving (not an easy to do task when you are in MSDOS and a bad instruction meant a reboot), learning about how the machine worked, optimization, learning obsolete technologies (all this happened in 2000-2001) I was left with a lot of experience that may not applicable in every day work but it certainly helps.
Every line of code I write, in any language, C#, Java, C, even Javascript or SQL, I cannot stop thinking about the very metal of the machine. How is this language going to do this? How much memory is this going to use? How are the final instructions that the CPU is going to execute going to look like?
I’m forever cursed with X-ray vision into the innards of the machine and although I am no expert, I am pretty sure it certainly helps me write more effective code, code that benefits the most of the abstractions offered to me by my tools, because, most of the time, I know what the abstractions are trying to help me with, what they are shielding me from, and instead of blindly using them without a clue, I wield them effectively as I know what lies beneath them.
Armed with my faithful archlinux based netbook, Common Lisp, and a copy of Land Of Lisp I plan on learning Lisp.
I will embark in the journey of Lisp learning in order to get enlightening and understanding. I know about functional programming and some of its concept and I apply them in my day to day work using C# and Ruby. But I certainly do not grok it, I do not fully understand it and I do not like that feeling, I want to know, I want to understand, I want to see the light and join the ranks of the Lisp preachers and me too, be able to say to you, that if you learn Lisp, you will be forever changed.
Me having a good beer.