Tao of the Machine

The little interpreter that could

My Lisp interpreter is growing rapidly. It is really nice, how you can add little pieces to it, bit by bit, to grow a better Lisp. Since this will not be a real-world version, one of my goals is to write as much in Lisp as possible... if something can be written in Lisp, it shouldn't be a built-in function. (I realize that this will be very different when you're writing a Lisp that actually needs to have decent performance.)

As said before, it's based on Zetalisp, and some differences with Common Lisp are visible already. For example, Zetalisp uses / as an escape character, and as a result, the division operator is written // (vs / in CL). Another example: CLISP doesn't like the expression (>), complaining that > should have more arguments. In Zetalisp this evaluates to true (or t, if you wish). One could argue that > without arguments doesn't make any sense, but neither does (> 1), which CLISP does allow. Ditto for other comparison operators, like =.

The current version is becoming more and more usable. It supports numerical comparison operators, car, cdr, cons, eq, funcall, and, cond, defun, function, if, incf, lambda, let, or, quote, and setq. It also supports ; comments, 'symbols and #' function lookups, and has a (limited) standard library. It knows about t and nil, and has an interactive interpreter. There's still much to add: strings, for example, and floats, rationals, etc. Also, macros, constants, keywords, and extended function arguments. And a lot of functions and special forms. Once that is into place, I'll look at integration with Python. (Which may not be as easy as it seems.)

Code is available in the usual place (look for pyzetalisp-x.x.zip). Don't expect too much. Remember, this is a toy interpreter, and still quite incomplete.

Note: I did add a Lisp category, and stuck the recent Lisp-related posts in it. I have a feeling I haven't seen the last of Lisp. :-)

No credit for the wicked

The stupidity of some laws and regulations never cease to amaze me. Especially here in the US, or maybe it's just Florida, people seem eager to reward stupid or anti-social behavior. My latest encounter was with this phenomenon called "credit".

It sounds reasonable at first. You buy something, pay it off in terms, and if everything goes well you get "good credit". If you fail to pay your bills (in time), then you get "bad credit". Cool. Except that 1) if you just pay things cash, up front, then you will have no credit at all, and 2) everybody and their dog seem to have access to your credit history.

#1 bites me, #2 amazes me. In the Netherlands, when you want a loan, or you want to rent a house, etc, people look at your income and expenses. When I applied to rent a house, the corporation didn't have access to my full credit history, and rightfully so... it's none of anybody's business. (I suppose this is arguable -- after all, banks need to be able to make an informed decision whether it's a good idea to lend you money. But should others, like employers, have access to this kind of data? I don't think so.) Either way, I don't think there's an organization that keeps track of it. (If there is, I've never heard of it.)

Anyway, my experience is that the best way to buy something expensive, is to save for it, then pay all of it at once. Not only will paying it off in terms often be more expensive, it also introduces a risk: if your financial situation changes, will you still be able to pay? I did that in the Netherlands, and I have been doing that over here as well, but now my credit history says that I have "no credit". Great, so I am punished for prudent management of my finances. If I had done it the other way, I would have been rewarded... I would have had "good credit", which is useful when buying a house, for example.

Oh well. I guess you just have to play the game and go with the rules, no matter how stupid they are.

Improving Wax

To everybody who is interested in Wax, here's a request. Please download the latest version and look at the controls that are currently available. (They're all listed in __init__.py.) What *crucial* controls are, in your opinion, missing? I'm talking important components here, not a Throbber or something like that.

Please mail any suggestions to the usual address, or leave a comment. ¹) If possible/necessary, I'd like to hear a motivation of why you think this control is important.

The idea is to have a "roadmap" towards a stable version of Wax that has all the necessary ingredients for building an (average) application.

¹) Although Haloscan seems to have problems with comments lately... sometimes it doesn't show the correct number of comments, and occasionally comments just disappear. I never deleted any, so that can't be it. Hmm.

Sawdust

See yesterday's post about the namespace split. The decision I made can be grokked from this piece of code:

(C:\cvsroot\zeta\python) $ tiny.py
Welcome to PyZetalisp 0.1.5
>>> (let ((+ 3)) (+ + +))
6

Once the interpreter is a bit more usable (currently it doesn't have lambda or if, to name a few things), I will upload it. Presuming I will get that far...

Once the Lisp core is done, I wonder if some integration with Python is possible. You know, like, import Python modules, access their contents, create objects, maybe evaluate Python code, etc. But maybe that would be out of scope for a toy project.

Clever readers will notice that the recent posts are just filler to keep people busy while I prepare for the next Python article. Kind of like certain coffee brands add sawdust to their melange. The question is, what shall the article be about? I'm not sure yet. (Suggestions welcome.)

One of my plans for next year is to write a book. I have a number of ideas, but I haven't decided yet what the target audience will be... newbies, or advanced programmers. Possibly newbies, but I don't want to have to explain the basics of programming, or how to install Python. I will probably assume that the reader already has at least a bit of programming experience with other languages.

More on the Lisp namespace split

I'm still wondering if I should implement separate namespaces in my little Lisp interpreter, or just use one, like Scheme has. On the one hand, I want to follow the manual as closely as possible, at least for now. On the other hand, I am not convinced that having separate namespaces is a good idea.

This entry in the Common Lisp Cookbook illustrates the problem. You can, for example, write a function that returns a function, but you cannot call the returned function the usual way; you have to use funcall or apply instead.

Apparently this issue has been discussed on c.l.lisp before. Here's one argument in favor of it, but I am unconvinced. Although this argument is interesting:

"What if one wrote a macro FIRST that took the CAR of a list. In CL this might look like

(defmacro first (x) `(car ,x))

(let ((car 'ford)
      (desired-vehicles '(bmw mercedes)))
   (eq? car (first desired-vehicles)))

Does the lexical binding of CAR to 'FORD shadow the expanded code from the macro FIRST and cause it to fail? If so, I claim that this is a bad property since one doesn't want to have to know what functions a macro uses in its expansion in order to be sure of avoiding problems."

Here's what Kent Pitman has to say about it.

I do like the extra bit of syntax (#'foo), but overall, the Scheme solution still seems cleaner. Not surprising, considering I'm a Pythonista. :-) However, I will probably stick to the manual anyway and implement environments with two namespaces.

Writing a Lisp interpreter...

...is a good exercise, because it forces you to know the internals of the language. I'm not quite done yet with my version, modeled after Zetalisp, but I've already had a few moments of enlightenment.

One such revelation was that symbols are not a special type. a and 'a can be stored in an expression tree with the same type. For the former, we look up a value when evaluating. The latter is translated to (quote a) and not looked up at all. In earlier, naive implementations ¹), I always tried to add a Symbol type or something like that. Maybe that's possible, but not necessary. The clue was that the Zetalisp manual doesn't mention 'a as a special type at all.

Another is, that special forms are actually, well, special... they are not functions that happen to have different evaluation rules; rather, they are (or can be) hard-coded in the interpreter. In this CLISP session, note that there is a built-in function +, but not an if or a quote:

> #'+
#<SYSTEM-FUNCTION +>
> #'quote

*** - FUNCTION: undefined function QUOTE
> #'if

*** - FUNCTION: undefined function IF
>

Which leads me to something else, the Lisp namespace dichotomy. Unlike Scheme (and Python), Lisp has a namespace for functions, and a separate one for variables. The following works in Scheme:

> (define twice (lambda (x) (* 2 x)))
#<unspecified>
> (twice 3)
6
> (define (twice x) (* 2 x))
#<unspecified>
> (twice 3)
6

In Lisp, this looks like:

> (setq twice (lambda (x) (* 2 x)))
#<CLOSURE :LAMBDA (X) (* 2 X)>
> (twice 3)
*** - EVAL: the function TWICE is undefined
;; this doesn't work; use funcall instead
> (funcall twice 3)
6

Here, twice is a variable that happens to contain a function. Since it isn't defined in the function namespace, we cannot call it with (twice 3). To define a function in the function namespace, use defun:

> (defun thrice (x) (* 3 x))
THRICE
> (thrice 3)
9
> #'thrice
#<CLOSURE THRICE (X) (DECLARE (SYSTEM::IN-DEFUN THRICE))
  (BLOCK THRICE (* 3 X))>

I wonder what the rationale is behind this variable/function namespace split. A namespace for code, and one for data? That seems especially odd in a language like Lisp, where code is often treated as data, or data as executed as code. Apparently the Scheme designers didn't like this either. So, I'm curious if there is a good reason for it.

¹) Hey, what do you expect, I don't have a computer science background... :-)

Kylix in limbo

Slashdot: Kylix in limbo. "LinuxWorld is reporting that Kylix development is in limbo. Many speculate this is a politically correct way of saying the project has been abandoned. [...] Why didn't Kylix sell? Does this say something about the application or about the difficulties of marketing a commercial Linux application?"

I'm not sure, but it seems to me that there a vast differences between development cultures on Windows vs Linux. Three of the reasons that Kylix didn't make it could have been:

1. On Windows, development is often done with a high-level tool or IDE. Visual Studio and Delphi are well-known and used by many. On Linux (and possibly Unixoid systems in general), such tools exist as well, but it's still very common to use the command line and scripts. An editor (vim, emacs) often gets you a long way, and Unix developers actually use this; this is much less common on Windows. As a result, there might have been less interest among Linux developers for a product like Kylix.

2. Pascal is, and has been, an acceptable development language on Windows. With Delphi, it has a reasonably strong position nowadays; during the DOS era, it was even stronger with Turbo Pascal. On Linux/Unix, though, people seem to have taken a leaf out of Brian Kernighan's book... C has traditionally been king. (Not surprising since the OS is written in it.) There are Pascal compilers for Linux, but it never seemed a reasonable alternative for C or other languages.

3. The Linux world seems much more oriented toward free software. Many a piece of software that is "free as in speech" also happens to be "free as in beer". That is not to say that there are no commercial packages for Linux, or that users are not willing to pay for them, but it's only natural that an open source OS, built on open source/free software, has a lot of free programs available. On Windows, on the other hand, developers often pay for professional software. So, there could simply be less of a market for commercial Linux software, and on top of that, there's more competition from free software.

All this is of course mere speculation since I don't really use Linux. But since when has that stopped any blogger from voicing his opinion?

Speech impediments

I'm trying my hand at writing a little Lisp interpreter, just for fun. (I'm using the old Lisp Machine manuals I found earlier as a reference, by the way. Even though these documents are 20 years old, I find them a joy to work with. They're to the point, and without the hype that seems to be pervasive in modern Lisp texts.)

I'm writing it in Python, so I'm obviously not too worried about performance (writing an interpreter in an interpreted language...). While this is much easier than writing it in, say, C or Pascal, I can think of a couple of drawbacks too. Python already has a list type, so my first thought was that it can be used for the Lisp lists as well. However, this is not how Lisp does it internally; rather, it uses cons cells. ¹) So I added a Pair class, emulating a cell, and tried creating lists with that, and converting Python lists, but it's a big old mess. ²) After all, Lisp handles lists much differently than Python. So, back to the drawing board. Maybe I will use Python lists anyway, and put up with the obvious problems it has. (Inefficiency, for example... (cdr lst) translates to lst[1:], which creates a new list.)

This is one area where a more limited language like Pascal may have unexpected benefits. Pascal doesn't have a list type, so you have to write one. And while you're at it, it's only a natural choice to create a system of linked lists like Lisp does. As a result, your list-using code will be closer to Lisp, and your expressions will be parsed into cons-cell-based expression trees.

Even if I fail, writing such an interpreter is a good exercise, and I learn more about Lisp along the way. ^_^ (If I don't fail, I will upload the code sometime.)

¹) However, many Lisp and Scheme texts insist that it can be implemented in other ways too, as long as cons glues two elements together, and car and cdr retrieve them correctly. SICP, for example, uses closures and lambdas at some point to reimplement cons, car and cdr.

²) For example, looping over a linked list works differently than looping over a Python list. There are several ways to make this easier, though, e.g. by writing an iterator.

Magi-Nation

Magi-Nation is a cool CCG by Interactive Imagination. When it came out a few years ago, it was not just a Magic knockoff, but rather it had some new, refreshing ideas, an interesting storyline, and cool art.

Like most CCGs, it has factions... Cald (fire), Naroom (earth/forest), Arderial (air), Orothe (water), etc. Where Magic uses a player's life points, Magi-Nation uses Magi that need to be defeated. There are no resource cards, allowing you to fill your deck with useful spells and creatures rather than lands. The basic casting mechanism is simple: to cast a spell with cost X, you discard X energy from your active Magi. If you cast a creature, then X is also that creature's power. (See more rules.)

Also, it plays right out of the box. Buy two starter sets and you're ready to go. I like the art as well; it's nice and colorful.

I'm not sure the company is doing very well though. There were layoffs last year, and quite a few of the promised goodies were never delivered -- no GBA game, no second GBC game, new expansion sets are late, etc. There used to be a lot of news sites too, but I can't seem to find them anymore.

This may be a good time to support them by buying a cool t-shirt with a card on it. All cards can be found here. I like the Ash Hyren. ^_^