Jakob Ƙstergaard Hegelund

Tech stuff of all kinds
Archive for August 2016

Bitten by quotes


I got bittem by quotes twice in a day recently. When "obviously correct" code doesn't work, debugging quickly gets frustrating. In both cases I had super simple obviously correct code that malfunctioned.

Naturally, in both instances, my code was obviously wrong once I got to take a step back.

Modifying literals

So I was writing test cases for a newly written procedure which destructively modifies a parameter passed to it. This itself is an interesting concept in LISP and it's one of these pretty big "little differences" to C++ where my experience really is.

Let's digress. In C++ you can pass arguments by value or by reference; but can choose to pass a pointer to an object - this is technically passing by value (you pass the pointer by value) but the code that gets generated by the compiler is more like when you pass by reference (which passes a pointer). However, in C++ you would stick a const on every argument your function shouldn't modify (which can cause confusion when you stick a const on a pointer-type value but the function then modifies the non-const data that the constant-valued pointer is pointing at; but poor code and lack of insight can cause mistakes in any language of course).

In LISP on the other hand, you always pass references to data (except when you pass literals) and there's no const equivalent. Effectively that means any procedure can modify the arguments it's passed. Of course you don't generally want that, and the standard library has conventions on procedure names that modify versus those that don't (e.g. subst vs. nsubst) - so this is not really a problem in the real world.

Anyway, I wrote a function that modifies a subset of an s-expression representing an XML document; it modifies the given document in-place and returns the modified document. The implementation is not important but the snippet below shows that in one situation we modify the cdr of the document (sexp) given.

(defun sexp-add-parameter (sexp key value) " ... " (declare (type list sexp) (type string key) (type string value)) ... ;; We don't have an arg list; insert one (setf (cdr sexp) (cons (list :@ (cons key value)) (cdr sexp))))) sexp)

My test code uses the 5am framework and I had two tests that looked like:

;; Add parameter to empty element with non-empty parameter list (5am:is (equal '("foo" (:@ ("a" . "b") ("key" . "value"))) (sexp-add-parameter '("foo" '(:@ ("a" . "b"))) "key" "value"))) ;; Add parameter to non-empty element with empty parameter list (5am:is (equal '("foo" (:@ ("key" . "value")) "baz") (sexp-add-parameter '("foo" (:@) "baz") "key" "value")))

So in short these two tests supply S-expressions that represent simple XML documents and the sexp-add-parameter procedure is called to insert (or alter) a given parameter (or attribute if you will) on the top-level element.

On my developer machine, executing this code from the editor (C-x C-e from Emacs using SLIME integration to the running SBCL LISP system) just worked. But the CI system failed the build! Re-building locally with the build-system optimization settings also failed the test.

That just sucks; obviously correct code that works on one optimization setting and fails on another. Argh! I trust the SBCL implementation, it is my general impression that it is quite mature, so I didn't want to believe this was an optimizer error. But debugging stuff like this... Argh... The debugger stack traces showed some really strange things like my simple quoted parameters being different from what the code said. So for example, evaluating the call (sexp-add-parameter '("foo" (:@) "baz")) would result in a debugger stack trace with a top-level call being (sexp-add-parameter '("foo" (:@ ("a" . "b")) "baz")) for example. Super super strange - I mean, you do the most simple thing; you execute a call - then your debugger claims the top-level is different from the call you just evaluated. Ouch.

Anyway, after a bit of hair pulling, I eventually ended up locating this little tidbit in the CLHS about the quote operator. It says The consequences are undefined if literal objects (including quoted objects) are destructively modified. Well d'oh. What was I thinking? This simple change fixed everything:

;; Add parameter to empty element with non-empty parameter list (5am:is (equal '("foo" (:@ ("a" . "b") ("key" . "value"))) (sexp-add-parameter (list "foo" (list :@ '("a" . "b"))) "key" "value"))) ;; Add parameter to non-empty element with empty parameter list (5am:is (equal '("foo" (:@ ("key" . "value")) "baz") (sexp-add-parameter (list "foo" (list :@) "baz") "key" "value")))

Ever since I learned using the quote operator, I just saw it as a shorthand for list (and cons). It never once occurred to me that list returns a freshly consed (freshly allocated) list, whereas the quote operator produces a list literal. And in most situation I could get away with my ignorance because "usually" I don't provide literal lists to procedures that modify their arguments. Lesson learned. More importantly I think I need to rename this procedure to make it clear that it modifies its argument.

Redefining procedures

When working in the LISP REPL you quickly get used to redefining procedures and re-evaluating calls to them - this is probably the primary reason I like working in a LISP environment; the escape from the old edit-compile-run cycle. But you quicly get spoiled - I got used to redefining my procedures and calling them and expecting them to actually be redefined. Well... It turns out that this does not always work exactly like I had imagined.

Let's say we have a report generator that can generate a number of different reports. Let's further entertain the idea that it holds a data structure that describes the report generators and also refers to the actual report generator procedures (for easy invocation from some "driver" or scheduling procedure). It could look like this:

(defparameter *reporters* `(,(make-repgen ... :generator #'repgen/accounts ...) ,(make-repgen ... :generator #'repgen/accounts-full ...)))

So in this example I have a list that contains two repgen structure instances. Each instance has a number of members, one of them being generator which is initialized to one of two report generator functions; repgen/accounts and repgen/accounts-full respectively.

While working on this system, I did some corrections to my repgen/accounts procedure, redefined it, and then called the report generator. Much to my surprise my changes did not take effect. Of course, I tried this a number of times with variations by my changes kept not taking effect. Again, this was a case of the simplest thing not working - very difficult to debug.

The following example may shed some light on this; a simple REPL session:

* (defun foo () "hi") FOO * (defparameter fun #'foo) FUN * (funcall fun) "hi" * (defun foo () "there") STYLE-WARNING: redefining COMMON-LISP-USER::FOO in DEFUN FOO * (funcall fun) "hi" *

I would have expected the second call to return "there" of course. Again, the CLHS to the rescue; the page about the Sharpsign Single-Quote and the function. It turns out that using #'foo results in the definition of the function foo, not a "dynamic link" to whatever definition is currently pointed to by the function by that name. So in other terms it's akin to static linking.

Of course when you know it, it's simple enough. I just re-evaluate my defparameter as well, after redefining procedures it reference.

What to take away...

I didn't read the HyperSpec from start to finish before starting programming LISP. And if I had, I wouldn't remember it anyway. In general I think it has been pretty smooth sailing - the language being so syntactically small makes it relatively easy to get started and doing relatively complex things (simple macros are not syntactically hard - they can be hard to wrap your mind around, but that is because of the concept, not so much because of the syntax). Of course I get bitten by my own misunderstandings and lack of insight at times, but frankly I'm surprised at how well it goes in general. This day was special - getten bitten by the simplest things, twice. Special enough to get space here.

XML, JSON, trees and LISP


This post is a run-through of some of my thoughts around the formats we surround ourselves with, when developing networked systems - especially on the web but elsewhere as well.

As you may have realized, my web site is antisocial. I do not have a comments section and this is a deliberate choice. If, however, you wish to provide insights or factual corrections, I very much welcome them via e-mail.

Trees... it's all about trees

A web page is, behind the scenes, a DOM tree in the rendering engine of the browser. Usually when we want to serialize that tree, we serialize it to XML. This is not because XML is in some way superior to other representations, it is more an accident of history.

Back in the very early days of the web when HTML was created, it was created solely for markup and did not describe formal tree structures. For example, interlacing elements were allowed; <b>this <em>was</b> valid;</em>.

During the '90s browser wars, one of the things that came out of the standardization effort was that someone (W3C I suppose) realized that transforming HTML from very unstructured markup into a stricter structure and giving it a new name with some resemblance to the original, would probably be necessary if anyone were to ever produce standards of what browsers should support and how they should do it. Thus XML was born.

XML is a properly strict specification with clear rules of what is allowed and what isn't, very much unlike the days of ad-hoc HTML. In XML, interlacing elements as in the previous example, for example, are not allowed. Unlike the early HTML, XML only allows for actual tree structures - for example:

<body> <title>Hello world</title> <p>Some text</p> </body>
or as a graphical representation:

If you actually look at the XML, you'll notice that it is very verbose. The closing tag repeats the name of the element that is being closed, even though though this is completely unambiguous (as elements cannot be interlaced). As long as nobody has to type or read XML, and as long as the cost of networked transport or storage of XML documents is not important, this is all well and fine. But I think most people will agree, that one could think of shorter ways of representing trees.

One example, of course, is S-expressions. These date back to the 1950s, but they are every bit as fine for representing trees as XML is - the same tree would look like this;

(body (title Hello world) (p Some text))
While this style of formatting may seem alien to some, it is not too difficult to get used to either. For one, it is a lot more compact than XML and therefore can be read and written a lot faster by someone skilled.

At the time of the inception of HTML, nobody could of course know where HTML would eventually go; I am not saying that Tim Berners-Lee and his associates did not do well, or that W3C did a poor job of formalizing HTML into XML - but it should be clear that if your goal is to serialize a tree structure into readable text, XML is a far stretch from being compact or easy on the eyes. And it is indisputable that more compact representations predate XML by at least three decades.

So what's in a tree anyway?

Trees hold a lot more than just DOM structures. Any of the programming languages we use get parsed into a tree structure when we pass our source code to the computer (for compilation, interpretation or otherwise). An AST (abstract syntax tree) is one such tree structure. Let's cook up an example; a conditional statement that performs one of two operations based on a test:

This could be written in C++ as:

if (a == 0) zero(); else more();
which is just another way of representing the exact same tree as above.

But wait... If that is just a tree... could we write the code i XML too? I'm glad you asked!

<if> <==>a 0</==> <zero/> <more/> </if>

Now that clearly doesn't make the code more readable. I guess this explains why Bjarne didn't pick XML for his "C with Classes"... But how about if we chose a more compact representation, say, like S-expressions again?

(if (== a 0) (zero) (more))

How about that? Now both the C++ and the S-expression representations of the tree are a lot shorter than the XML representation. However, the C++ representation uses a rather intricate syntax; notice how a surrounding parenthesis is used to group the first argument to the if (the test), a semicolon is used to separate the second argument (the positive) from the else and the third argument (the negative). Finally, a semicolon is used to group this conditional expression from any expressions that may follow.

In comparison, the S-expression representation uses a surrounding parenthesis to group the expression - this replaces the ending semicolon from the C++ example. But every argument to if is simply separated by a space; this is why the S-expression is considerably shorter than the C++ example (and completely consistent in its syntax). Anyway this is not about measuring lengths of expressions (or anything else), it is merely about giving examples of the various ways in which we represent the tree structures that we surround ourselves with.

Anyone remember PHP?

So back in the days with "Personal Home Page", the HTML you wrote could be extended in clever ways with actual code that would be executed by the server on which your web site ran. This was almost really clever; since HTML lends itself to extension (eXtensible Markup Language - it got that name for a reason) simply by adding your own elements, PHP offered the HTML author an elegant way to escape from the HTML (that would become the DOM tree in the users browser) into the world of in-server processing.

<body> <h1>Hello world</h1> <?php if ($a == 0) zero(); else more(); ?> </body>

Top points for elegant extension here - the contents of the <?php> element in the document is simply evaluated on the server. Beautiful. But... what for consistency? Both the to-be DOM data (the static HTML) and the PHP code are tree structures, and one is a sub-tree of the other. Why do we use separate representations?

Looking at our previous attempt at representing the simple conditional in XML, I think it is quite clear why Rasmus didn't pick XML representation for his language either. Let's try it anyway:

<body> <h1>Hello world</h1> <?php> <if> <==>a 0</==> <zero/> <more/> </if> </?php> </body>

Yuck. So given the choice, I think it is clear why they chose inconsistency over the alternative. But... What if the web wasn't HTML? What if... say... Tim had used S-expressions? Let's try:

(body (h1 Hello world) (?php (if (== a 0) (zero) (more))))

Well, be that as it may - it's probably a little late to change the web from XML to S-expressions. But anyway, this example is a useful primer for what comes next.

Oh... and in case you're thinking that the four ending parenthesis look scary, don't worry. Any decent editor will do parenthesis matching and any decent developer should be using a decent editor. Trust me when I tell you, that sequences of parenthesis is not a practical problem when developing using S-expressions; it looks like trouble I know, but in the real world it just isn't.

Escaping XML - JSON to the rescue?

The JavaScript community has long worked with XML by means of the tight DOM integration in the language. Sometimes they would work with textual XML, other times they would manipulate objects in the DOM directly. The XMLHTTPRequest method performs an HTTP request and provides, as the name implies, immediate access to an internal representation of the XML response received.

No developer should ever have to write XML; developers will produce and manipulate tree structures, and if needed those can be serialized to XML or parsed from XML; but there should never be a situation in which an actual person sits down and types actual XML. XML is just too inconvenient, too verbose and too silly, for a human to type.

It appears that the Javascript community discovered that rather than working with XML documents, it would be more convenient to write plain JavaScript and use the eval() function on the receiver side to parse this. Once again, I have to award top points for consistency - using only JavaScript rather than using XML as well (one language is usually better than two if you have any amount of code and people on your project). Obviously of course, it wasn't long before the security implications of executing eval() on code received from foreign systems was realized. Today, the valid subset of JavaScript that can is sent between systems is called JSON, and it is no longer parsed using eval(). So far so good.

Inside a pure JavaScript system, JSON thus makes some sense as a textual representation of a tree structure. But in the effort to avoid the security problems of arbitrary code execution from remote systems, the JSON syntax is a far stretch from full JavaScript - therefore, as with the C++ versus XML code sample, JSON suffers from the same deficiency which causes the limited cumbersome syntax to become very verbose for representing arbitrary trees. An example is in place.

Let's take the original C++ example;

if (a == 0) zero(); else more();

Now let us try rewriting this into JSON:

{"if": [ {"==": ["a", "0"]}, {"zero": []}, {"more": []} ]}

While shorter than the XML representation it's still a long way from the briefness of the original C++ or the even shorter S-expression. Again, beauty is in the eye of the beholder, I shall refrain from commenting on what the JSON looks like.

This example is not as contrived as it may seem on the surface. There are indeed real-world projects that serialize their languages into JSON - one such example is the ElasticSearch Query DSL.

In all brevity, JSON does not bring anything to the table that XML or S-expressions didn't do already. It is slightly shorter than XML but it's clearly not the shortest representation. You can't possibly argue that it is significantly prettier than the others (I'll go as far as to agree it's different). It's not more (or less) efficient; it requires a specialized parser like anything else. It was never structured the way it was for any of those reasons either - JSON today looks like it does, because it's a valid subset of JavaScript.

In other words; JSON was never intended to be brief. It was never intended to be efficient. It was never intended to be easily readable. It was never intended to have any other particular quality one might wish from a tree representation language; it is what it is, because it is a valid subset of JavaScript.

The story is the same with XML of course, with XML not being designed from the ground up but looking like it does because of its HTML predecessor. So don't take this as a knocking of JSON in particular - all I'm saying is, JSON is no better than XML for all intents and purposes - and therefore in my view it is useless. It simply doesn't bring anything to the table that wasn't there already.

So is everything just bad then?

I'm glad you asked! No, of course everything isn't just bad. And this post isn't meant to make it sound like I think all is bad. I am simply trying to make you think about trees and how we represent them in writing.

I have been working quite a bit with XML data exchanges lately, and I have been fortunate enough to be able to do much of that work in a language that is itself an S-expression; namely LISP. This has been an interesting experience that has brought back memories from the days of PHP, but with actual elegance and consistency. It's almost too good to be true - and it's definitely good enough to share.

As we established earlier, XML and S-expressions are two of the same - they are simply representations of tree structures. XML is nasty to write though, so before doing anything else, I built an XML parser and an XML generator; two procedures that would convert a string of XML into an S-expression, and convert an S-expression into a string of XML. Like this:

* (sexp->xml '("body" ("title" "Hello world") ("p" "Some text"))) => "<?xml version=\"1.0\" encoding=\"utf-8\"?> <body> <title> Hello world </title> <p> Some text </p> </body> <!-- End of document --> " * (xml->sexp "<body><title>Hello world</title> <p>Some text</p></body>") => ("body" ("title" "Hello world") ("p" "Some text"))

Now hang on - how's that for consistency? LISP is homoiconic; the language itself is represented in a basic data type of the language. Or the code looks like the data, to put it in another way. While perhaps confusing to the novice, it's inarguably consistent. With the ability to construct our tree structure and then later convert it to a string of XML, this opens up for some very convenient XML processing.

Consider, for example, an API endpoint handler that must return an S-expression which the HTTP server then converts to XML:

(defun api-get-status () `("status" ("version" ,*version*) ("api-time" ,(universal->iso8601)) ("db-time" ,(car (query "SELECT now()" :flatp t))))

Is that sweet or what? Executing this code we get:

* (api-get-status) => ("status" ("version" "unknown") ("api-time" "2016-08-17T15:24:41Z") ("db-time" "2016-08-17T15:24:41.049531Z"))

Ultimately, when the HTTPd executes the api handler code it will also invoke the S-expression to XML conversion. So what is executed is of course more like:

* (sexp->xml (api-get-status)) => "<?xml version=\"1.0\" encoding=\"utf-8\"?> <status> <version>unknown</version> <api-time>2016-08-17T15:28:51Z</api-time> <db-time>2016-08-17T15:28:51.774258Z</db-time> </status> <!-- End of document -->"

Notice how my static document data (the status outer document and the version, api-time and db-time subdocuments structure) are written and how function calls and variables are trivially interwoven (by means of the comma operator). Building up large and complex tree structures from LISP is, in other words, a comparatively nice experience - and turning the S-expression to XML is trivial as already demonstrated.

Where do we go from here?

Where we can go with this exactly, I'm not sure. Doing XML API work in LISP is an absolute joy, that much I can say. The verbosity of S-expressions is minimal and I think the actual implementations are usually really elegant - having the language itself be an S-expression provides a level of consistency I am not used to from other languages.

I think it would be interesting to look into generating asm.js from LISP, as a way to efficiently deliver web applications but being able to write them in a more elegant language. Imagine that; having a server-side API server and the actual browser-side web application all developed in a language as elegant and mature as LISP. Certainly this would be a welcome contender to the current Node.js movement where we attempt to use the most inelegant language ever (hastily) conceived to run both the browser and the server.

Getting back on line


It's been quite a while since my last post - time flies when you're having fun. A lot has happened, but I had not taken the time to write about any of it until now. I'm going to try to get back into the habit of writing here. Here's some headlines...

An ode to the thin client

I've been an extremely happy user of the Sun (now Oracle) SunRay thin clients; both running with on Solaris- and Linux-backed terminal servers. I have up until late last year used a dual-head setup with two SunRays (one driving each monitor) since around 2002 or such. During those 13 years, the back end servers have been upgraded in various ways - ultimately, we ended up with virtual Linux servers running in a lage VMWare cluster backed with Oracle ZFS appliances. So my "desktop computer" (the SunRay server in the datacenter on which my applications ran) had more cores, memory and disks that would fit under and over the desk in my office.

The single big downside to this setup was video (as in full screen motion picture) performance. Everything else worked very well indeed - the SunRays accelerated 2d operations just fine so regular screen updates, scrolling, moving about and browsing the web was absolutely fine. Since my job isn't watching full screen video, this one limitation in the setup was not really a problem (sure, on fridays when a colleague links to a funny youtube video, it can be annoying to have to view it windowed rather than full screen - but really, this was the one downside for me). All in all, while we all like full screen video, I could perform my professional duties on this rig just fine.

There were some significant upsides to the setup - among the big ones I should mention: I had an identical setup at home - so all I had to carry from and to work was a small smart-card, my user session would follow the smart-card. Sometimes I run to work (it's a nice 10k jog), and all I needed to carry was a smart-card. No laptop can compete with that, however lightweight.

Also I never needed to worry about backups and hardware upgrades. My "desktop" computer was hooked up to a large storage system in the datacenter and other people would manage that - no unreliable or slow or too-small disks for me to worry about.

Anyway - since apparently everyone else (even nurses and doctors in hospitals) must be able to play full screen youtube while at work, the thin client has been discontinued by Oracle. In my opinion this is a shame - not so much that they discontinue the one true thin client product that existed (the X terminals died long before this) - but that IT people around the globe failed to realize the enormous savings a true thin client architecture does indeed provide in workplaces where thin clients are adequate graphically and where the ever-alive session provide massive savings in man-hours (saving personnel from starting and logging on to 5-8 different applications like they do in most hospitals in this country for example, every single time they need to enter a single data point about a single patient).

I can work with a lot of things, but I can't work on a discontinued product for many years - time to move on. I need a UNIX workstation, I want something that "just works", I want to be able to carry it around (bring it home now that my session can't travel with me any more) and while watching full screen Youtube still isn't part of my job, it would be great to be able to do that too (actually, CSS transitions on modern web could take a toll on the SunRay video performance too). So I chose a Macbook with a Cinema display for the office, as well as a bluetooth keyboard and trackpad. This way, when at the office I have a big screen and a normal keyboard and trackpad - when at home, I can work from the laptop.

I have not yet run to work after making this switch; clearly a 13" macbook is going to be a lot heavier than the smartcard was. We'll see how that goes... But aside from that, I really don't have any complaints. Emacs works in full screen mode just as well as it did on the SunRay, and that's where I spend most of my day anyway. Finally, I do love how full screen Youtube plays on this new rig.

Learning LISP

The second big thing that happened to me since last update is that I'm now doing a significant part of my professional work in Common LISP. Yup that's right - the language that was invented (or "discovered" if you will) in the late 1950s. I guess that deserves some explaining too.

I was faced with the challenge of having to run some "business processes" for a cloud service we're building. I've seen these things being built many times before and I know how it goes: Someone needs a mail to be sent out in some particular situation - so one developer hacks up a piece of Perl to do that and runs it from cron. Now someone needs to pull a report of some numbers, so another developer cooks up some Python to compile the numbers and a shell script to feed the output to the right location. And so it goes... Each of these individual processes is seen as too small or insignificant to warrant a properly structured approach and before you know it, you will have developed both a messaging, reporting, billing and operations automation system using at least five different languages (bash, perl and python (probably at least two incompatible versions of python) happen within weeks, then follows a java service (everybody needs those) and that guy who learned Ruby needs to use that and then the web developers figured they could write stuff in JS and run it under Node.js). Look me in the eyes and tell me that's not how it goes. Every. Single. Time... Not out of ill will, but because everyone wants a quick solution to a simple problem. Unfortunately, 10 quick solutions to just as many simple problems isn't quick at all and ultimately isn't really a solution.

So we don't want that. I've implemented a complete automated billing and invoicing system in PL/PGSQL in the past - that was a great experience but I don't want to do that again either (lessons learned). I've also implemented such services in C++ - and while that's my main language, I just really don't think this is a productive experience. The abstractions you can do in C++ are fine, but still, for such diverse jobs as mailing, accounting, reporting and communicating with dozens of systems, I find that in C++ I end up having to type a lot (regardless of the number of libraries I may be able to use). Worse, the continuous testing and incremental refinement of a big distributed and inherently parallel system using the "edit compile run" cycle is terribly inefficient. A massive focus on unit testing will help here, but it will not cure the fundamental problem, that re-starting the full application on every change you need to test there costs a lot of time, every time, all the time.

I was seriously looking at other languages - including the hypes of the day (Ruby and Python as far as I remember). But the thing is; these languages are so close to all the other languages. There's nothing you can do in these languages that you couldn't reasonably do in either Perl or C++ too. Sure, you can pull out some contrieved example that would demonstrate some superiority - but you would not be able to solve most real world problems significantly more elegantly, or be able to develop the solutions much faster. All these languages are the same... They look the same, and they fundamentally build on the same ideas; pile a fixed set of features into the language, add libraries for commonly needed functionality outside of that. And that's it. And everyone uses the old "edit compile and run" cycle. Is that really the best we can do?

It turns out, it's not the best we can do. LISP has two absolutely huge benefits over "all the other" (non-LISP) languages:

These two points basically means that: Especially the second point is probably not going to make much sense to you if you don't know LISP already - and if you do, you don't need me to praise it.

Some time has passed now and we run a good number of important business processes on this LISP system. It was definitely a gamble when we decided to start this experiment - I did not know the language and no-one else on the team did. You won't find many people who know the language - but hey, when hiring C++ developers I generally don't find many people who know that language either (I mean really know it). Compared to the traditional approach where you have a myriad of small components each written in their own language, I far prefer our structured single-language approach here. This system has been a huge success so far - I cannot imagine how much code and how much time had been needed, had we chosen to do this in PL/PGSQL, C++, Python or any other of the "traditional" (but younger) languages.