I was always curious about Lisp family of programming languages.
There are two reasons for that.
Firstly, there is Scheme[1], Closure[2], Common Lisp[3], Shen[4]
and they come in different flavors,
so there must be some really valuable property in Lisp,
that people want to have in their language.
Secondly, many people say, that you can “expand your programming horizons”
and that the best way to do it, is to learn about Lisp macros[5].
There is one book, that is particularly about Lisp and its macros
– “On Lisp” by Paul Graham[6].
I am an Erlang programmer, so chapters 2 – 5 were pretty basic for me.
Functions as data? Used every day. Closures? Easy.
Interactive shell? Can’t live without it now!
Recursion? Even looping over list is done this way.
Chapter 6 is called “Functions as Representation”
and I was curious, what does it mean,
so instead of jumping straight to “Macros” (chapter 7),
I started reading how can you use functions to model networks.
Simple problem was chosen to illustrate the idea:
write a 20 questions game.
User has to think of a person and then he
is asked question with only “yes” or “no” answers about that person.
Based on the answer, he is either asked another question
or he gets the person name from the program.
The tree of questions and answers was represented as a list of nodes.
Based on that data structure, there were two ways to solve the problem:
1. The usual way, where each time, we search for the node in a list,
ask question and based on the answer, we search for the new node.
2. The clever way, where we first preprocess the list to create a tree of functions.
As an exercise, I wanted to implement it in Erlang
and this is what I came up with:
-module(test). -compile([export_all]). %% node is either: %% {name, question, node for yes answer, node for no answer} %% {name, answer, undefined, undefined} %% undefined is a special value for not implemented parts of the tree list_of_nodes() -> [ {people, "Is the person a man?", male, undefined}, {male, "Is he living?", undefined, deadman}, {deadman, "Was he American?", us, undefined}, {us, "Is he on a coin?", coin, undefined}, {coin, "Is the coin a penny?", penny, undefined}, {penny, "Lincoln!", undefined, undefined} ]. usual_way() -> Nodes = list_of_nodes(), run_nodes(people, Nodes). %% searches for node and runs actual code run_nodes(NodeName, Nodes) -> Node = get_node(NodeName, Nodes), run_nodes1(Node, Nodes). %% if both "yes node name" and "no node name" is undefined %% this must be a leaf with answer run_nodes1({_Name, Answer, undefined, undefined}, _Nodes) -> Answer; %% ask question and run recursively run_nodes1({_Name, Question, YesNodeName, NoNodeName}, Nodes) -> {ok, [Answer]} = io:fread(Question, "~s"), case Answer of "yes" -> run_nodes(YesNodeName, Nodes); _ -> run_nodes(NoNodeName, Nodes) end. %% searching for undefined? it is either not implemented %% or we simply don't know get_node(undefined, _Nodes) -> {undefined, "I have no idea!", undefined, undefined}; %% if there is no such NodeName - we made a spelling mistake %% otherwise, return the node get_node(NodeName, Nodes) -> case lists:keyfind(NodeName, 1, Nodes) of false -> invalid_node_name; Node -> Node end. clever_way() -> Nodes = list_of_nodes(), RootFun = compile_net(people, Nodes), RootFun(). %% After compiliation a node is a fun(), %% which has pointers to other nodes. compile_net(Root, Nodes) -> %% it uses get_node as the previous one Node = get_node(Root, Nodes), case Node of %% if this is leaf node, %% we have to return Answer, but it has to be wrapped with a fun() {_Name, Answer, undefined, undefined} -> fun() -> Answer end; %% if this is some other node, %% we immidietly call compilie_net on both children %% this means, that we will process the whole tree {_Name, Question, YesNodeName, NoNodeName} -> YesFun = compile_net(YesNodeName, Nodes), NoFun = compile_net(NoNodeName, Nodes), %% this entire fun() is returned %% it asks the question when called %% but it doesn't have to look for the node in the node list, %% because nodes were precalculated above, %% even in other scope, YesFun and NoFun %% will still point to right functions %% based on the answer, it runs one of the nodes fun() -> {ok, [Answer]} = io:fread(Question, "~s"), Fun = case Answer of "yes" -> YesFun; _ -> NoFun end, Fun() end end.
You can see, that the clever way seems to be way more complicated.
One of the reasons for writing this program was to show,
that you can represent data with closures.
What are the advantages of this representation?
Firstly, it runs faster after compiling
(from now, by “compiling”, I mean calling “compile_net”).
Usual implementation searches for the node on the list each time,
user is asked a question.
In balanced tree, with N elements, we have to ask log(N) questions,
so the runtime of one game is O(N*logN).
Clever implementation takes only O(logN) to run single game,
because all the nodes are found earlier.
The compilation itself has to search entire node list for each node it compiles,
so it takes O(N^2).
This pattern of precomputing something expensive first,
so that next calculations can be performed faster, is really important.
Think of LU decomposition[7] for solving systems of linear equations.
You need O(n^3) operations to use Gaussian elimination[8],
but you can firstly decompose the matrix, which also takes O(n^3) operations,
but after that, you can solve systems of linear equations
for different vectors in O(N^2) time.
Second advantage of precompilation is finding bugs earlier.
In the usual way, if I misspell a node name,
I’ll get an error in runtime.
In the clever way, I’ll get the error during compilation.
This is huge win for me.
Last, but not least – at the end of the chapter,
you can read:
“To represent with closures” is another way of saying “to compile”
and since macros do their work at compile-time,
they are a natural vehicle for this technique.
For now, I don’t fully understand why representing with closures
is the same as compilation.
I can see, that is useful for precomputing things.
During my studies at AGH University of Science and Technology[9],
I had entire semester about compilers,
scanners, parsers, grammars and final code optimization,
but I have never fought about it this way.
This makes me even more interested in Lisp macros!
[1] http://groups.csail.mit.edu/mac/projects/scheme/
[2] http://clojure.org/
[3] http://www.clisp.org/
[4] http://shenlanguage.org/
[5] http://www.paulgraham.com/icad.html
[6] http://www.paulgraham.com/onlisp.html
[7] http://en.wikipedia.org/wiki/LU_decomposition
[8] http://en.wikipedia.org/wiki/Gaussian_elimination
[9] http://www.agh.edu.pl/en
tkowal 