Tao of the Machine

My first macro

The other day I wrote my first real Lisp macro. Yay! (Not counting macros from tutorials, etc.) It's a first step in harnessing some of the amazing power of Lisp.

This macro implements a C-like ++ (postfix) operator:

(defmacro ++ (x)
    `(let ((old-x ,x)) 
      (progn 
       (setq ,x (+ ,x 1)) 
       old-x)))

and it's used like this:

(setq magic 42)
(print (++ magic))  ;; like magic++ in C: sets magic to 43, returns 42
(print magic)       ;; 43!

Nothing special, and maybe not very useful, but it's always nice if you have an idea and it can actually be implemented in a few lines of code. :-) This may be an important step on the road to more Lisp. A long, long road, I suspect. Not that I will leave Python anytime soon... I'll still need to get some actual work done.

[Update #1] Some people pointed out that the macro isn't 100% safe. More about this problem here. The safe solution is quite ugly, IMHO (using gensym to make sure there are no variable name clashes). I guess variable name conventions can be very useful here.

(It's a bit quiet here in the Python and Parentheses topic exchange. Anybody else join in?)

Nu even een geintje...

This code works in Lython:

(import wax)

(print wax.Application)
(:= app (wax.Application wax.Frame))
(app.Run)

Due to the limitations of Lython (which is at 0.1 currently), it's not very useful yet. If it supported keyword arguments, we could write

(:= app (wax.Application wax.Frame :direction "vertical" :title "Hello"))

And if it supported classes, we could subclass Frame. Then it wouldn't be very difficult anymore to write a Lython-wrapper around wxPython ("Lax"?). Allowing for the first Lisp dialect with a decent GUI. <ducking for cover>

Unrelated: I don't see car, cdr or cons in the code yet. Maybe the author doesn't plan on implementing them, if the goal is to just have a Python with Lispy syntax. I'm not sure they would be so easy to implement. Sure, (car x) as x[0] and (cdr x) as x[1:] would cover many cases, but AFAIK, Lisp's cdr doesn't make a copy, so code like this would be hard to implement:

[1]> (setq a '(1 2 3 4 5))
(1 2 3 4 5)
[2]> (setq b (cdr a))
(2 3 4 5)
[3]> (setf (cadr a) 42)
42
[4]> a
(1 42 3 4 5)
[5]> b
(42 3 4 5)

(I'm running into the same problems for my PyZetaLisp interpreter... how to implement setf? Not that it's really important, since it's only a toy implementation, but one wonders...)

The Little Lisper

Lispy links

Some links that might help get the Python and Parentheses thingy going...

• Successful Lisp: Seems like a good place to start. One day I want to work through this book and actually start *doing* something with Lisp rather than experimenting.

• Hedgehog Lisp: A small Lisp for embedded programming.

• Lisp500: Lisp in 500 lines of C. (Don't try to look at the code. )

• Lython: A Lisp front-end for Python. Much like a Lisp interpreter in Python, except that it compiles to Python bytecode. Given this fact, it's unsurprising that it integrates smoothly with Python (and its functions, classes, modules, etc), allowing for code like:

(import os)

(:= out "/tmp/lythontest")
(if (os.path.exists out)
    (os.unlink out)
  (print "target file does not exist"))

(:= f (open "/tmp/lythontest" "w+"))
(f.write "Hello World from Lython!")
(f.close)

(Lython's integration is a lot better than my PyZetaLisp interpreter's, but then again, PyZetaLisp was really meant as a prototype for a later implementation in C or OCaml or something; integration with Python was more of an afterthought. That's why PyZetaLisp has separate classes for integers, strings, etc, rather than using Python's built-in types directly.)

Python and Parentheses TopicExchange

http://topicexchange.com/t/python_and_parentheses/

Aaron Brady: "Given that Python & Scheme, and Python & Lisp have been recurring memes lately, I thought it would be good to group all of these posts tegether in one place. To that end, I've created a new topic on Phillip Pearson's *excellent* TopicExchange, for people to trackback when posting about it. It's like a manual "Buzz"."

Funny this should come up... lately I've been wondering what it would be like to have a language that's a mixture of Lisp and Python. A Pythonic Lisp. A Lispy Python. A Lisp designed with Pythonic principles in mind. It could have goodies like modules and objects.

(import 'foo)   ;; or maybe: (import foo) ...?

Maybe it could have special syntax for dicts, lists and object access.

(foo.bar 42)             ;; sugar for: (getattr foo 'bar)
(define a (range 10))    ;; a list
(print a[2])             ;; sugar for: (getitem a 2)
(define b sys.modules)   ;; a dict
(print b["os"])          ;; sugar for: (getitem a "os")
(define c (create-instance Point))
(print c.x c.y)          ;; sugar for: (getattr c 'x)

Maybe it could be very Pythonic. TOOWTDI, explicit is better than implicit, and all that jazz.

The language that I envision would be an independent implementation. It would not be a Lisp interpreter written in Python, or Pythonic syntax and libraries tacked onto Lisp. No, I think it should be designed from scratch, critically looking at the Lisp-vs-Python balance every step of the way.

Aside from the actual implementation, I think that the most difficult part would be, making it so that it would actually seem useful, natural, and a joy to program in... for people coming from Lisp, Python, and other languages. I'm not sure if that's possible. Sometimes I wonder if Lisp and Python, in spite of their similarities, are really based on vastly incompatible principles.

(Aside: The TopicExchange uses trackback. To make things easier, the development version of Firedrop is now capable of sending trackback pings. No, it's not available yet. )

The lisping snake

The time has come to look at integration of Python code with the Lisp interpreter. It's far from complete, but this time seems as good as any.

The main problem is the difference in types. The Lisp interpreter currently uses several special objects: LispInteger, Pair, LispSpecialAtom (for t and nil), LispIdentifier. There should be more types soon, like a LispString, etc. Some of these, like the string and the integer, should be trivial to translate to Python. Others are more of a challenge. There is already code to convert Lisp lists to Python lists and vice versa, but what about other Python types, like dicts? Classes and instances? File objects?

Let's look at some (hypothetical, for the moment) example code.

(setq os (py-import 'os))
(funcall (py-getattr os 'path 'join) "foo" "bar")
=> "foo\bar"

Two conversion problems occur here: once when we call os.path.join, because the LispStrings "foo" and "bar" need to be converted to Python strings; and once when Lisp gets the return value back, in this case a Python string that needs to be converted to a LispString. This is all fairly simple. But now consider:

(setq f (funcall (py-builtin open) "myfile.txt" "r"))
(setq poplib (py-import 'poplib))
(setq pop (funcall (py-getattr poplib 'POP3) "host"))

The Lisp interpreter now has several objects: a file object, a module, and a POP3 instance. How to represent these in Lisp? I wonder if it's best to use a thin wrapper class, call it PythonObject. PythonObjects can then be manipulated by selected "py-" functions. (For example, a file object wouldn't have dedicated Lisp functions to deal with it, but you would be able to use its methods and Python functions through the py- interface.) This would work, but we would still need an extra step or two to convert numbers and strings and such.

Thoughts welcome.

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. :-)

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... :-)

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.