Andrei Dubovik
Blog

On Lisp or Blog Autobiography

The village of Den Haag
Oct. 24, 2016

“Day One”

Once upon a midnight dreary, while I googled weak and weary... While my attempt at a poetic parody is lame, it nails the story. In essence, I had nothing to do one evening and I decided that doing a simple website powered by Lisp would be fun. Why? Well, I will learn a new programming language, I will likely improve my functional programming skills (albeit, as a frequent user of Mathematica, I consider them passable), and I will hopefully finally figure out what all the fuss about the mighty macros is about.

I understand what a macro is at a conceptual level, but I do not have a feeling why it is useful. My only comparison is working on one mathematical model, which you cannot solve analytically—at least I cannot—but a purely numerical solution is also not feasible. Therefore you need a mix of the two, which Mathematica allows you to do. Compare this problem to a macro: you work through your formulas at compile time and then apply them during run time. Then again, you can shift all such logic to run time. But then again, you will need to develop a specific runtime language for that purpose...

Anyway, let me cut short on pointless philosophical digressions. So, first impressions:

  • REPL is great but I new that already. I used it in Mathematica, Stata, R and Python (via Spyder). That is not to say, of course, that anyone is mad enough to program a website in Stata.

  • What annoyed me as a beginner and still does is a lack of a good development environment. Slime is good but Emacs itself makes me crazy. The proponents of Emacs can argue about its objective virtues but from my personal subjective experience it is cumbersome and unintuitive. The infinite monkey theorem states that a monkey forever typing on a typewriter will almost surely produce the complete works of William Shakespeare. I do not think the theorem can be generalized to the monkey using Emacs. Rather, almost surely just one of the following events is bound to happen: writing the complete works of William Shakespeare, programming emacs to render the operating system unusable, programming emacs into a loop that no key sequence can break, programming an artificial intelligence that takes control away from the monkey.

  • Iteration macros are richer than in other programming languages but consequently I become more upset when they are a bit lacking. do does not allow to concisely assign initial and consecutive values of an iterator to the result of the same function, loop does not indent properly in Emacs, iterate—which I use by default now—does not allow for parallel bindings and its substitute construct, for ... previous, cannot always solve the situation at hand. Is it a right of passage into the Lisp community, writing your personal iteration macro that works best for you?

  • Writing a syntax parser for latex-like source files is much harder than I have expected. Scientific problems aside, this is the most challenging programming task in recent memory. Tokens follow many different patterns. Environments change token recognition rules. All sort of stuff can be nested. I end up writing a recursive chain of streams, where the behaviour of the streams is governed by a dynamically scoped list of test functions.

  • Having a tree data structure built into the language, plus a lot of useful convenience functions—notwithstanding cadadr and the like—is a bonus when writing a parser, or working with XML. I am a little bit surprised that Lisp didn’t grow in popularity with the advent of the World Wide Web.

The question of the day, have I written my own macros? Yes, I have. A few macros that avoid code repetition but so far they save less code then they occupy themselves. And I have moved the unit-tests to compile time so that a unit test raises an exception during compilation if it fails. If only I could write a program that handles the exceptions by debugging and improving my code... I find it neat but clearly nothing essential. Generic functions and the ability to dispatch them on eql operator proved more useful so far.

“Day Two”

I start to like the prefix syntax. Programming in lisp is simply writing down my thoughts, without the need to translate them into a foreign grammar. After all, I always say: “Let us add x and y,” I never say: “Let us compute x plus y.”

Regarding macros, I have found one application where they are convenient. Any language has constructs to define literals: numbers, strings, vectors, etc. (A good friend of mine once told me that any program that features numeric literals other that 0, 1, and maybe 2, is highly suspicious.) Often there is a need to define more complex literals, e.g. user interface. In my case I needed to define certain rules/properties for parsing LaTeX. With macros you can define your own syntax for more complex literals and therefore quite a bit of repeating code is reduced. I guess this application is a trivial example of what falk call domain specific languages.

Am I writing my programs any faster in Lisp? I dunno. Are my Lisp programs running any faster/slower? Let us do a simple test that is relevant for a website: generating an html string from some internal html representation. I will use whatever feels most natural for a given programming language: lists and property lists with Lisp, objects, lists and maps with C++, and lists and dictionaries with Python. For fun, let me also drop Mathematica into the mix, with lists and association maps. As is traditional, I am going to test

<html>
  <head><title>Hello, world!</title></head>
  <body style="background-color: salmon">
    <p style="font-family: serif">Hello, <i>world</i>!</p>
  </body>
</html>

Firstly, Lisp. Suffices it to say that I have managed to write this code while frying a sausage? C++ I am postponing till I have some free time on a weekend...

(defparameter *html*
  '((:html ((:head ((:title ("Hello, world!"))))
	    (:body ((:p ("Hello, " (:i ("world")) "!") :style "font-family: serif"))
		   :style "background-color: salmon")))))

(defun keyword-name (keyword)
  (string-downcase (symbol-name keyword)))

(defun write-args (args)
  (apply #'concatenate 'string
	 (loop for (key value) on args by #'cddr
	    collect (concatenate 'string " " (keyword-name key) "=\"" value "\"" ))))

(defun write-html (list)
  (apply #'concatenate 'string
	 (mapcar (lambda (elt) (if (consp elt) (apply #'write-tag elt) elt)) list)))

(defun write-tag (tag body &rest args)
  (let ((tag (keyword-name tag)))
    (concatenate 'string "<" tag (write-args args) ">" (write-html body) "</" tag ">")))

(defun speed-test ()
  (time (dotimes (i 1000000) (write-html *html*))))

Secondly, Mathematica. 5 long lines of reasonably readable code, 1 dynamic binding, 310 euros for a Home Desktop license.

html = tag["html", {tag["head", {tag["title", {"Hello, world!"}]}],
    tag["body", <|"style" -> "background-color: salmon"|>, {
      tag["p", <|"style" -> "font-family: serif"|>, {
        "Hello, ", tag["i", {"world"}], "!"}]}]}];

writeArgs[args_] := StringJoin[KeyValueMap[StringJoin[" ", #1, "=\"", #2, "\""] &, args]]
writeHTML[tag_, body_] := StringJoin["<", tag, ">", writeHTML[body], "</", tag, ">"]
writeHTML[tag_, args_, body_] := StringJoin["<", tag, writeArgs[args], ">", writeHTML[body], "</", tag, ">"]
writeHTML[list_] := StringJoin[list]
speedTest := Timing[Do[Block[{tag = writeHTML}, html], {1000000}]]

Thirdly, Python. At the moment that I am writing this sentence I do not know the results yet. Frankly, I am quite curious myself. I always held a superstition that Lisp is generally faster than Python and my choice of Lisp for this website was in part driven by this conviction. We will see.

import timeit

html=[('html',[
('head',[('title',['Hello, world!'])]),
('body',[('p',['Hello, ',('i',['world']),'!'],{'style':'font-family: serif'})],
         {'style':'background-color: salmon'})])]

def write_args(args):
    return ' '.join(['{}="{}"'.format(k,v) for (k,v) in args.items()])

def write_html(lst):
    return ''.join([e if isinstance(e, str) else write_tag(*e) for e in lst])

def write_tag(tag, body, args={}):
    return '<' + tag + write_args(args) + '>' + write_html(body) + '</' + tag + '>'

def speed_test():
    return timeit.timeit("x=write_html(html)", number=1000000, globals=globals())

print(speed_test())

Finally, C++. If you have a beard, take a look at the code. Skip otherwise. (If you choose not to follow my advice, do not complain about multiple inheritance, and inheriting from standard containers.) For fun, I managed to define my html object in C++ with this syntax:

Html html {
  Tag("html", {
    Tag("head", {Tag("title", {TextElement("Hello, world!")})}),
    Tag("body", {{"style", "background-color: salmon"}}, {
      Tag("p", {{"style", "font-family: serif"}}, {
        TextElement("Hello, "),
        Tag("i", {TextElement("world")}),
        TextElement("!")})})})};

Obviously, a finite but rather large number of disclaimers should be made regarding the validity of these comparisons. For once, Lisp adepts will say I do not know Lisp (which I don’t), Python adepts will say Python code is more clear (which it is). But let us skip that boring talk and go straight to the results.

LanguageLinux (Intel Xeon)Linux (ARM Cortex-A7)Mac (Intel Core i5)
C++ (g++ -O3)1.5 sec.31 sec.4.2 sec.
SBCL Lisp4.8 sec.429 sec.57 sec.
Python13 sec.270 sec.22 sec.
Mathematican.a.n.a.29 sec.

Well, well, well, I have to make a classical conclusion now. Speed wise it does not matter that much which of the “scripting” languages to use (in this case at least). It also seems that SBCL gets lazy when on Mac or on more rare architectures.

“Day Three”

My website is up and running. All five pages of it. Hurrah! In the end, how much effort did it take, counting the custom LaTeX parser? Well, they say Lisp is good for working with Lisp code, so let us find out. The moment you downloaded this page the statistics were as follows:

StatisticValue
Lisp files9
Lines of code (including docstrings)978
Functions (defun, defmethod)153
Macros (defmacro)13
Lines per file, average108.7
Lines per function, average5.0
Broken keyboards0

Supposedly, the holy grail of functional programming are small utility functions that you write whenever you spot recurring patterns. How many such functions did emerge in my effort? You can view a Lisp program as a network, where each function is a node, and an arc from function A to function B means that B uses A. Then an outdegree of function A is the number of other functions that use A. The table below gives the outdegree distribution for the Lisp program powering this website.

OutdegreeNumber of functions
09
177
223
39
44
≥ 56

Evidently, I am a poor functional programmer. So I stop with programming, at least for now, and I go back to watching Ergo Proxy. I like the overall atmosphere and style of the series, reminds me of Dark City somewhat.

On Lisp
Motorbike Diaries
Raspberry Pi
2