Lars Wirzenius: Hedgehog Lisp, 2003
Contents
- December 3: Common errors
- October 24: Blurb
- October 20: Blurb being written
- September 27: AVL trees, data structures, comp.lang.lisp
- September 16: let
- September 1: Lack of profiling tools
- August 31: Lack of static type checking, Bluetooth
- July 8: Getting GPRS to work is difficult if the network crashes
- June 26: Documentation extraction
- June 14: Bad day
- June 12: Aplicom bootstrapping
- June 11: Shaping up
- June 6: Porting to BlueGiga
- June 5: I hate embedded programming
- June 3: Fixing old problems
- June 2: New implementation
Wednesday, December 3, 2003
Hedgehog Lisp: Common errors
Lately, I've made two types of errors repeatedly: either I use the wrong index into an index data structure (an AVL tree, roughly corresponding to a hash map in Perl or a dictionary in Python), or I update the data structure but return the old value. This is becoming common enough for me that it annoys me. I'll have to figure out things that can be done about this.
Friday, October 24, 2003
Hedgehog Lisp: Blurb
Cessu and I wrote a short blurb for Hedgehog, as a first step in the preparation for a release as free software. Don't hold your breath on the actual release, however, it might be months off. I need to restructure the code base, and such, before it can happen, and this needs to happen while I'm working full time on customer projects.
Hedgehog is a very concise implementation of a LISP-like language for low-end and embedded devices. It consists of a compiler to byte code and a corresponding interpreter. The byte code interpreter is written in standard conforming C, is efficient and easily portable, and can be compiled to a very small executable or library of only some 20 kilobytes.
The Hedgehog LISP dialect has proper support for local and lambda functions, lexical scoping, variable argument functions, garbage collection, exceptions, macros, and over a hundred predefined functions or special forms. The built-in types are lists, symbols, strings, 32-bit integers, AVL-trees, and tuples up to 16 elements wide. Proper 32-bit wide integers are necessary for various bit-level operations in embedded systems.
For a half-written tutorial and reference, see Oliotalo's site. If you have questions, feel free to mail me.
Monday, October 20, 2003
Hedgehog Lisp: Blurb being written
About three weeks ago, I wanted to write a blurb for Hedgehog that could be put on a web page to describe it, and in the README for an eventual GPL release, and so on. About half a page of text. I had a difficulty writing keeping it short enough, and it is now 40 pages of text, plus front matter, with at least two chapters that have only a place keeper, no content. My megalomania strikes again.
As a result, Cessu wrote a new blurb, and we edited it for a few iterations. It really is short, and I think it mentions all the important features. As soon as the boss approves it, I'll put it on the web.
I'd like to see a GPL release of Hedgehog sometime early next year, but we'll see whether that happens for real. There's all these other things I need to do at work, which customers are actually paying for... (It's good to have customers, especially paying ones: I've had two employers go bankrupt on me, and it is not the most pleasant of experiences.)
Saturday, September 27, 2003
Hedgehog Lisp: AVL trees, data structures, comp.lang.lisp
Cessu added primitives for AVL trees this week. They have made our dictionary data structure tens of times faster than even the most optimized versions written in pure Lisp. This helps some of our applications significantly.
I added simple functional queues to the library. We've implemented queues in a few places in several applications, usually badly. Since functional queues are so simple to do reasonably well, putting them in the library is long overdue. At least six months overdue.
I made the first release for almost two months. All Hedgehog releases are internal to Oliotalo for now, so I can't point you at a tar ball. Hopefully one day we can make Hedgehog free software; right now we're concentrating on making the company profitable.
It seems that Hedgehog was mentioned on comp.lang.lisp for the first time in August. This would be thrilling, except the mention basically said he couldn't find any information. Of course, since we aren't making public releases, there's little point in discussing Hedgehog on public newsgroups.
Tuesday, September 16, 2003
Hedgehog Lisp: let
I got fed up with the lack of a let
construction in Hedgehog Lisp, so I wrote a couple of macros
to make one. Now I can write code like this:
(let
foo 1
bar (+ 2 3)
(do (pr "sum: " (+ foo bar))
(pr "product: " (* foo bar))))Cessu suggests an alternative syntax, however:
(let
((foo 1)
(bar (+ 2 3)))
(pr "sum: " (+ foo bar))
(pr "product: " (* foo bar)))Cessu suggestion follows more closely the Lisp tradition,
I think, but I find my version clearer due to the fewer number
of parentheses, even if it does force use of do
pretty often.
I've been experimenting with my syntax today, writing code that uses it, and I'm happy. I suspect I'd be happy with Cessu's syntax as well. The important point here being that it becomes rather much easier to do calculations in many steps and naming intermediate results with auxiliary symbols.
Monday, September 1, 2003
Hedgehog Lisp: Lack of profiling tools
Spent today fixing a performance problem on an application we're making for a client. It was quite a simple problem, actually: we have a data structure similar to a Python dictionary or a hash table in various languages. It had been implemented as a linked list for simplicity, with the intention that it would be written properly later, when there was more time. Way too much time was spent traversing the linked list in the application in question. The problem was fixed by changing it to use an unbalanced binary tree. This was fast enough, so there was no need to implement a balanced tree or other fancy data structure, though that will eventually be necessary.
It took way too long to find this problem. I'd like to have better profiling tools for Hedgehog. What we have now is crude, but it might be possible to augment it so that it serves our needs better. Tool making isn't quite what I should be doing right now, however, and it will have to wait.
Sunday, August 31, 2003
Hedgehog Lisp: Lack of static type checking, Bluetooth
During the past week at work, we've found several bugs that would have been found by static type checking. Unfortunately, the Hedgehog Lisp does not do that and the language does not really allow it, either. Cessu is eager to design a completely new language, with static type checking, but that will not happen until next year. In the mean while, I suspect that more thorough testing is required, and that means building better simulation environments of the trucks and what not our boxes are attached to. That should be good anyway, in the long run, so it's not wasted effort.
I've also been working on getting Bluetooth connections between boxes, and it progresses slowly, but nicely. Most pleasantly, all Bluetooth traffic is either via sockets at the server end or through a simple serial port protocol in the client end, so all the work can be done in Hedgehog Lisp itself, no need to write C code. This is quite fun.
Tuesday, July 8, 2003
Hedgehog Lisp: Getting GPRS to work is difficult if the network crashes
Spent today combining the three different versions of the code we have for setting up a GPRS link and TCP connection. They were all broken in some way. During the afternoon, Telia's GPRS network seemed to go down or something else mysterious happened: while I was running a test run, the code stopped working without my changing anything. Four or five hours later, it still wasn't working and it wasn't until then that I tested a SIM card from another operator. That one worked immediately. Half a day of wasted debugging effort; I hate it when that happens.
Thursday, June 26, 2003
Hedgehog Lisp: Documentation extraction
Spent all day setting up a system for extracting documentation from source code and generating Docbook and formatting that to HTML using a custom XSLT file. Cessu sent in the updated tutorial and I proofread and edited that. The result is that we finally have documentation for the new implementation.
Saturday, June 14, 2003
Hedgehog Lisp: Bad day
Some work days are tiresome. Yesterday, a few boxes were installed at a customer site and these were the first boxes with the new Hedgehog Lisp implementation. Not completely unexpectedly, when the boxes were powered up, they didn't seem to work. Specifically, they didn't fetch bytecode from our server over GPRS. The big problem, however, was that no-one at the installation site had a laptop so they could check what the log said and so we have no clue as to what is going on.
Combined with minor health troubles this really spoiled the day.
Thursday, June 12, 2003
Hedgehog Lisp: Aplicom bootstrapping
Our interpreter now bootstraps on Aplicom by downloading, over GPRS, from our application distribution server the application byte code. I implemented this by writing the code to fetch the byte code with HTTP in Hedgehog Lisp itself, then embedded the corresponding byte code into the interpreter. The bootstrap program stores the byte code it loads into a suitable memory area, from which the interpreter executes it after the bootstrap terminates. Nothing particularly magic or difficult, but many details that had to be right.
Wednesday, June 11, 2003
Hedgehog Lisp: Shaping up
During the weekend, Cessu implemented closures, which in practice seems to mean that lamda functions and local functions now work. I've been working on adding more support for Aplicom's hardware to Cessu's implementation. CAN and I2C buses should now work, and the Lisp heap is reserved from "UPmem", a 300+ kilobyte memory area that the C dynamic memory management won't touch. The C heap is only about 32 kilobytes, so this is pretty good. All in all things are shaping up well.
Friday, June 6, 2003
Hedgehog Lisp: Porting to BlueGiga
I have today made a quick initial port of Hedgehog Lisp to an embedded Linux box by BlueGiga. It was rather easy, since BlueGiga's Linux pretty much the same as desktop Linux. Will need to write drivers for some of the box's special features (LEDs, bluetooth, etc.) but time enough for that later.
Thursday, June 5, 2003
Hedgehog Lisp: I hate embedded programming
Yesterday was representative of the kinds of days why I hate embedded programming. While I was on my way to the office, the boss called me and told some boxes at a customer's site had crashed. Totally. And wouldn't come up even after a power cycle. Ugh. After a while, they managed to turn off the internal battery in the boxes and then they would work. Now if we could only figure out what the problem is. So far, the best description of the symptoms I have is that the some of the LEDs blink a red color at about two hertz and there's about nothing that can make that happen. Sigh.
Couldn't replicate the problem at the office, either. Such fun. Had this been a server application, there would have been log files and possibly core dumps. Luckily, other people at work will continue to try to replicate this, while I concentrate on other things.
Today, I managed to get TCP sockets and and PPP over GPRS to work on the Aplicom boxes, i.e., I solved the problem I had on Tuesday. It turned out to be a bug in my lisp program. I was using some bootstrap code from my old implementation that had been working for many months. Unfortunately, it worked only by coincidence. It had a nasty race condition, which was triggered only rarely, if ever, by my old implementation, since it was so slow. Cessu's new implementation is a hundred times faster and triggered the race condition every time.
What happened, slightly simplified, was that the operating system can report three states for the PPP connection: 'offline', 'connecting', and 'on-line'. When my code initiated the connection, the state changed from 'offline' to 'connecting'. There is a small lag for the state to change, however. My lisp code was written so that it would initiate the connection and then wait until the state was either 'on-line' (connection succeeded) or 'offline' (it failed). Since my old implementation is so slow, this worked pretty well. Cessu's implementation is so fast, it would initiate the attempt and then immediately notice that the state is 'offline', since it hadn't yet had time to become 'connecting'. Therefore, my lisp code promptly disconnected and killed the connection attempt it had just started.
I fixed a small problem with Cessu's code. He had used
snprintf. That in itself is a good thing, of
course, but it pulled in over ten kilobytes of extra code
from the standard library. I had already implemented my own
subset of printf and adding my own version of
snprintf cut away ten kilobytes from the binary.
That is, I saved about 9% of the binary size.
That reminds me of my changing attitude towards bloat. I worry about an extra ten kilobytes of code and find it rather distasteful that the TCP/IP stack for the box is about whopping 40 kilobytes. At the same time, friends are using Java development tools that require hundreds of megabytes of memory to run at all. I have a nagging feeling that there is something seriously wrong when a glorified editor is so large.
Tuesday, June 3, 2003
Hedgehog Lisp: Fixing old problems
Today I have mostly been fixing old problems. I spent all of today porting over existing platform specific code from my implementation to Cessu's. I decided to clean it up in the process. The old code had been written at various stages during the past year and it was pretty messy. It is now neatly divided into a portability layer with stuff that must be available on every platform and platform specific stuff that is only available on that platform.
I've half way into porting the PPP/GPRS and TCP/IP socket code to the Aplicom embedded box. The sockets work under Linux already, but the Aplicom bindings behave strangely. Probably nothing big, since the code did work before, after all.
Monday, June 2, 2003
Hedgehog Lisp: New implementation
Hedgehog Lisp is the embedded language of the Lisp family we implement and use at Oliotalo, where I work. It is incompatible with every other Lisp in the world. I should probably write a short essay on why it is like it is, and why we made it, and whether it has been any good. Later.
So far, we've been using my implementation, but it is proving to be a tad slowish. We commissioned a new, faster implementation from Kenneth 'Cessu' Oksanen. His is about one to six hundred times faster than mine, depending on the benchmark. Since last week, I've been porting it to the embedded environment we use. So far, progress has been slow.
Today I have, finally, progressed far enough to be able to send byte code to the box's interpreter over a serial line. So far, all the byte code had to be compiled into the interpreter, which made it kinda tedious to write any programs. Now I only need to make interpreter support all the capabilities of the hardware and then I'll be able to write applications in lisp.