Neues in der Kategorie Lisp

According to Gulli News, Windows 8 will not shut down completely, but keep a memory image which is then loaded to RAM, to improve the speed of the startup. This reminds me of a quote regarding Smalltalk:

I always show this, when asked by C/C++ programmers, as a typing in of "Hello, World!," preferably into an empty Transcript pane. And then I save the image. Loading the program subsequently brings up: "Hello, World!" Individuals will quibble over this relentlessly, saying, "It's not the same!" I can only agree that it's not the same, but that was my point about the languages and their environments in the first place.

Has a bit of Smalltalk's philosophy reached the practical world?

I was searching for a simple way of experimenting with Turing machines for a small course I will give, but most of the software out there is either too complicated or has restrictions, like a predefined alphabet. So I hacked together a small turing machine:

(defun run-turing-machine
  (statelist current-state-name band bandptr)
   (let* ((bandlen (length band))
	  (cstate (cdr (assoc current-state-name statelist)))
	  (calpha (elt band bandptr))
	  (cdo (cdr (assoc calpha cstate)))
	  (do-write (car cdo))
	  (do-move (cadr cdo))
	  (do-goto (caddr cdo)))
     (setf (elt band bandptr) do-write)
     (incf bandptr (cond ((eql do-move 'R) 1)
                         ((eql do-move 'L) -1)
                         ((eql do-move 'S) 0)))
     (dotimes (i 70)
       (format t "~d" (elt band (+ i bandptr -35))))
     (format t "~%")
     (if (eql do-goto 'HALT) nil
	 (run-turing-machine statelist do-goto band bandptr))))

As it is very short, it is very easy to customize, so maybe it is the right thing for other people who are able to use lisp and want something similar. Which is why I am blogging about it, even though it is nothing special.

The code should be self-explanatory, as an example, the following is a machine which increases a dual number (consisting of 0s and 1s, bounded by 2 in the beginning and 3 in the end), and its output:

(run-turing-machine 
 '(
  (anf (0 2 S HALT) (1 2 S HALT) (2 2 R zu3))
  (zu3 (0 0 R zu3) (1 1 R zu3) (3 3 L letzteziffer))
  (letzteziffer (0 1 L andenanf) (1 0 L letzteziffer) (2 1 L anf))
  (andenanf (0 0 L andenanf) (1 1 L andenanf) (2 2 S HALT))
 )
 'anf
 (make-array '(100) :initial-contents
 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 3 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 50)

0000000000000000000000000000000000211111300000000000000000000000000000
0000000000000000000000000000000002111113000000000000000000000000000000
0000000000000000000000000000000021111130000000000000000000000000000000
0000000000000000000000000000000211111300000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000021111130000000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000000211110300000000000000000000000000000000
0000000000000000000000000000000021110030000000000000000000000000000000
0000000000000000000000000000000002110003000000000000000000000000000000
0000000000000000000000000000000000210000300000000000000000000000000000
0000000000000000000000000000000000020000030000000000000000000000000000
0000000000000000000000000000000000001000003000000000000000000000000000
0000000000000000000000000000000000021000003000000000000000000000000000

Tröööt! There is a new protocol joining the small group of network protocols which I like. The Network Block Device protocol. It seems like it is exactly as complicated as it needs to be. It just has a major disadvantage: It is not well documented. Surprisingly, the German Wikipedia has a quite nice article about NBD, and this article is not that bad! It even has a protocol documentation - as one wishes when consulting an encyclopedia. (So it will probably be deleted soon.)

Actually, I had a closer look at NBD while I was actually looking for something else, but the implementation of an NBD server took some time. I wanted to create an NBD server which allocates a specified amount of memory and populates it as block device - just as a proof of concept telling me that I have "understood" the protocol and that I am able to implement it.

I began with C and finally succeeded, after finding out that every adress has to be sent in network byte order, and finding some useful header files like <linux/nbd.h>. Still, my C implementation has some bug, and as I did not have any special aim, I re-implemented everything in Common Lisp. The code can be found at GitHub (exercise: find out where its name comes from).

Its only dependency so far is usocket, and as I did not yet create an asd file it has to be loaded manually, which I do via Quicklisp.

CL-USER> (ql:quickload "usocket")

Then I load my file and start a server with a 10 megabyte block device.

CL-USER> (load #P"~/projects/7-chloro-4-nitrobenzofurazan/nbdserver.lisp")
CL-USER> (defvar *pool* (run-rampool 13337 (* 10 1024 1024)))

This will block until an nbd client connected and returned again. So let us connect via the linux nbd client. We create an ext2 filesystem and then mount it and create a file GANS with the content NILPFERD in the shell

# nbd-client localhost 13337 /dev/nbd0
Negotiation: ..size = 10240KB
bs=1024, sz=10240
# mkfs.ext2 /dev/nbd0
[...]
# mount /dev/nbd0 /mnt
# echo "NILPFERD" > /mnt/GANS
# sync
# cat /mnt/GANS
NILPFERD

Then we unmount it again and detatch the device.

# umount /mnt
# nbd-client -d /dev/nbd0
Disconnecting: que, disconnect, sock, done

Now, the REPL is free again, and *pool* contains the data. We have just created an ext2 filesystem on a lisp vector. Now we should find the word "NILPFERD" in *pool*, and indeed

CL-USER> (search (map 'list #'char-code "NILPFERD") *pool*)
2098176

Now let us see what happens if we replace this string (as this returns the whole *pool*, we set *print-length* first):

CL-USER> (setf *print-length* 10)
10
CL-USER> (replace *pool* (map 'list #'char-code "nilpferd") :start1 2098176)
#(0 0 0 0 0 0 0 0 0 0 ...)

Now, let us re-run the nbd-server with the modified *pool*

CL-USER> (run-rampool 13337 (* 10 1024 1024) *pool*)

And attatch and mount it again

# nbd-client localhost 13337 /dev/nbd0
Negotiation: ..size = 10240KB
bs=1024, sz=10240
# mount /dev/nbd0 /mnt

Now, about the file:

# cat /mnt/GANS
nilpferd

Yep, it is indeed lowercase now. Which is ... nice ... somehow. Though useless, of course.

Besides that, I found an implementation of a server in python, though I have not tested it. Same for this Java implementation.

Unfortunately, there seems to be a lack of clients. A port to some other Unices and Windows would be nice. Especially, looking at these implementations of block device drivers, there should be people who can easily implement an NBD Client for Windows.

I have found a bug that I was searching for since a long time. Now finally, the level-editor works - well, at least as long as you do not use OpenGL in the mean-time (this should be just a minor bug, I assume some confusion of the standard input by OpenGL or something).

Even though there are a lot of alternatives, I think I will stay with ltk and skippy for the level-editor, simply because the level-editor was meant to be a development tool for me rather than part of the software.

The background is still not working and currently I do not have the time to make it work, though it is probably easy.

Anyway, if you want to have fun with it, or get inspiration (or just look at CL-Code dealing with OpenGL), it can be found under https://github.com/dasuxullebt/uxul-world.

I wonder wheter any of the "modern" object systems and their reflection APIs can do this:

;; define classes a and b
(defclass a () ())
(defclass b () ())

(defgeneric test (obj))
(defmethod test ((obj a)) 'a-method)
(defmethod test ((obj t)) 't-method)

;; the t-method is called, since b is not subclass of a
(assert (eql 't-method
	     (test (make-instance 'b))))

;; now we add the class a as an additional superclass
(reinitialize-instance
 (find-class 'b)
 :direct-superclasses (list (find-class 'a)))

;; and now, the a-method is called, since b is subclass of a
(assert (eql 'a-method
	     (test (make-instance 'b))))

Assuming the continuum hypothesis, there is a black-withe-coloring of the real plane <m>\mathbb{R}</m> into two colors, such that on every line parallel to the x-axis, there are only countably many white points, andon every line parallel to the y-axis, there are only countably many black points. I have found this, including a proof, on Mathoverflow.

Well, something similar holds for the rational plane <m>\mathbb{Q}^2</m>. In that case, there is a coloring such that on every line parallel to the x-axis we only have finitely many white points, and on every line parallel to the y-axis, we only have finitely many black points.

The proof is simple: We know there exists a bijection <m>b:\mathbb{Q}\rightarrow\mathbb{N}</m>. Now color every point <m>(p,q)\in\mathbb{Q}^2</m> white if <m>b(p)<b(q)</m>, and black otherwise. For every q there can only be finitely many p such that <m>b(p)<b(q)</m>, and for every p there can only be finitely many q such that <m>b(q)\le b(p)</m>.

The interesting part about that is that this is a constructive result - it can actually be calculated - but still, it is highly counter-intuitive that such a coloring exists, and its rather difficult to find it when you do not know it already.

The awesomeness of Common Lisp gives a great opportunity to actually code it, using its included facilities of fractions:

(defun cantor-pair (n m)
  (+ (* (+ n m) (+ n m 1) (/ 2)) m))

(defun z-to-n-0 (z)
  (+ (* 2 (abs z)) (signum z)))

(defun rat-pair (q)
  (cantor-pair (z-to-n-0 (numerator q)) (1+ (denominator q))))

(defun white-p (p q)
  (< (rat-pair p) (rat-pair q)))

It uses Cantor's pairing function. I thought it'd be interesting to actually draw these points. Well, actually, it is not really interesting, anyway, here is the code that uses lispbuilder-sdl:

(sdl:with-init ()
  (sdl:window 400 400)
  (let ((zoom 100))
    (flet ((draw-zoomed ()
         (sdl:clear-display (sdl:color :r 0 :g 0 :b 0))
         (dotimes (i 400)
           (dotimes (j 400)
         (when (white-p (/ i 400 zoom) (/ j 400 zoom))
           (sdl:draw-pixel-* i j :color (sdl:color :r 255 :g 255 :b 255)))))
         (sdl:update-display)))
      (draw-zoomed)
      (sdl:update-display)
      (sdl:with-events ()
    (:mouse-button-down-event
     (:button btn)
     (cond
       ((= btn sdl:mouse-wheel-up)
        (incf zoom)
        (draw-zoomed))
       ((= btn sdl:mouse-wheel-down)
        (decf zoom)
        (draw-zoomed))))
    (:quit-event () t)))))

with the scroll-wheel you can change the interval that is shown (but be careful, if you scroll down 100 times, you get a division by zero, since the zoom will be 0 - as it was not that interesting I did not put that much effort into making it work). For everybody who does not want to do this, here is an image of some screenshot (I do not actually remember the zoom-factor):



It looks sort of nice when you scroll through it. The stripes are probably some boundaries of denominators.

[PS: For some reason, at the time of publishing this post, MathJax does not render the set-symbols correctly. I will probably investigate on this later. It should be clear anyway.]

In a mood of procrastination I had a few thoughts on how to create simple GUIs with Common Lisp. For the leveleditor in Uxul World I use LTK - it is installable via QuickLisp meanwhile, and it seems to be the best and most portable possibility so far. The main disadvantage is that it runs the TCL shell in a separate process. Then there is CLIM of course, and though there seem to be a few quite interesting libraries around CLIM, the only one I have ever used is McCLIM (with Climplayer). McClim seems to have several backends, and a nice API for creating new ones, but in the past I could not manage to run it under MS Windows which was why I focused on LTK - and then never concentrated on CLIM.
But actually, I do not really think that GUIs are that important. I think webinterfaces are meanwhile sufficient for most purposes, they are simple to code, and they are portable (and I am not the only one who thinks this apparently). A problem with local webinterfaces is that I do not know any webbrowser that supports connecting to, say, unix domain sockets. Therefore, there are two possibilities of securing the interface from other users on the same computer: Using IPTables and a local shared secret - and I do not like both possibilities. Maybe someday, some browsers will be able to connect to unix domain sockets, projects like uzbl seem to be predestined for that. What is already possible is to let them open FIFOs. So I was doing a little experiment with it, using SBCL's posix-binding: For every link I create a FIFO and a Thread that tries to write on it. Opening a FIFO blocks until both sides of the FIFO are opened by default, thus, as long as the created thread is blocked, you know that the FIFO was not opened by the browser, as soon as it is not blocked anymore, you know that it was opened and can generate the content. So the basic handling mechanism looks like

(require :sb-posix)

(defun make-handle (f)
  (let
      ((fname (sb-posix:mktemp "/tmp/clgui.XXXXXX"))
       (fkeep t))
    (sb-thread:make-thread
     (lambda ()
       (loop while fkeep do
        (sb-posix:mkfifo fname #o700)
        (with-open-file (str fname :direction :output :if-exists :overwrite)
          (setf fkeep (funcall f str))
          (finish-output str))
        (delete-file fname))))
    fname))

It takes a function that itself takes a stream (the one sent to the browser) as an argument and returns a generalized boolean - if it returns true, then the fifo keeps being listened to, if nil, its deleted and not listened anymore. Then I define a few variables and two handlers that increment and decrement a variable:

(defparameter *ctr* -1)
(defparameter *incf* "")
(defparameter *decf* "")

(defun do-inc (str)
  (incf *ctr*)
  (format str "
<html><body><a href=~s>&lt;&lt;</a>~d<a href=~s>&gt;&gt;</a></body></html>
"
      *decf* *ctr* *incf*) T)

(defun do-dec (str)
  (decf *ctr*)
  (format str "
<html><body><a href=~s>&lt;&lt;</a>~d<a href=~s>&gt;&gt;</a></body></html>
"
      *decf* *ctr* *incf*) T)

Finally, I create the handles and set the appropriate links:

(setf *incf* (format nil "file:///~a" (make-handle #'do-inc)))
(setf *decf* (format nil "file:///~a" (make-handle #'do-dec)))
(format t "Now open ~a in your browser." *incf*)

Opening the link in the browser should show you two links and a number that can be incremented and decremented by these links. Be careful: Reading from a FIFO when no process writes to it may freeze Firefox.

There are a lot of drawbacks in this approach: A lot of files are created. And the amount of data sent back to the application is very limited. Formdata cannot be passed - this could be solved using JavaScript and additional protocol handlers for Firefox - which is very complicated.

After all, it was just a little experiment. In theory, user interfaces that only contain links but no text fields and checkboxes could be implemented with it. In practice, I would not do it, but anyway it would be great to make browsers be able to connect to unix domain sockets I think.

Its bloated, its old, it has only few common modern extensions, it can run code from the 1960s. Things that can be said about Common Lisp. I already heard people recommend to "forget about Common Lisp" and use one of the shiny (new) other lisp dialects.

Still, I prefer Common Lisp to others.

Well, firstly of course, the mighty object system, the CLOS, is one reason for me to do. Few other languages have an object system so versatile and still so easy to deal with, and so well-optimized. I saw QT implementing its own C++-Preprocessor to have proper signal-passing-mechanisms, and the GLib doing similar things programmatically. Well, CL has it.

And one reason why I prefer it especially to Clojure: It encourages functional programming, but does not try to enforce it. Sometimes, a statefull loop is the easiest way to express something. Purely functional programming is - in my opinion - useful when I want to have formally verified code using strong type-systems, because thats something I am willing to put more effort into. And of course, good functional code can look pretty. But I dont share the ideology of everything having to be functional without any further use.

Well, with purely functional programming, there is a major lack of Common Lisp: When really programming purely functional, lazy evaluation is something desirable (its also desirable in other situations). There are some projects trying to implement lazy evaluation, but of course thats extremely hard without having to re-implement half of the language. Maybe that one will stay a lack of CL. But maybe not. At least lazy lists are not a real problem.

Something similar to this problem are continuations which also appear to be hard to implement - but there is a library, called cl-cont, which has some minor limitations but works.

For a larger community, the main problem of Common Lisp, I think, is the lack of libraries. With the many new "standards" that evolve every day, with the many new programming libraries doing magic that is not portable, it is hard to stay up to date. The IT-World changes every day, so software that isnt maintained will soon be deprecated.

And here is the one major advantage of Common Lisp: It is a stable standard. This is sometimes criticized, but in my opinion, thats a major advantage. Common Lisp offers a lot of high-level and low-level-features, there is one CL for almost every platform, and still its a standard that has been stable for a long time and is not likely to change.

But even though the ANSI-Standard hasnt changed, there are a few extensions that are de-facto-standards which are supported by vitally every implementation. For example gray-streams, the metaobject protocol and the common foreign function interface. And there are some portable libraries for threads, weak references, file access and sockets.

Any of these extensions defines as much as necessary, but not more. Most features that one may want can be implemented by the mighty macro system. Just today, I read about a new project "SPARK" on reddit - well, some nice ideas, and I hope that this project will achieve its aims (but to be honest, I doubt it). One idea mentioned is special syntax for regular expressions - something that can also be done comparably easy in Common Lisp, using reader macros.

Maybe also a major problem of Common Lisp: You can do almost everything. Therefore, there is no need for extending the standard, which is why some API-designs appear very old-fashioned.

But I prefer stable old-fashioned but sufficient API to API that constantly changes.

Instead of just providing a .deb-Package, the Racket-Developers decided to provide a binary executable installer for Debian as precompiled version. This binary installer has the extension ".sh", which suggests that its a shellscript. So if you want to create a package out of such an installer, the first thing you will probably do is to look inside it. Binary executables are normally suffixed with ".bin".

Then this installer has no "--help"-Argument, no way of telling non-interactively where to put its files, no way of removing the links you have made again. Thats why you normally have a package manager taking care of this for you.

I wonder what made them think that giving such an installer would be good in any way. Would it have been more work to provide a debian-package?

A few very nice examples on how GCC optimizes code can be found at ridiculousfish.com.

An example of generalized tail recursion was given, the transformal of

int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}

into

int factorial(int x) {
   int result = 1;
   while (x > 1) result *= x--;
   return result;
}

This is a well-known optimization and Iwas wondering whether SBCL also does this optimization. The second declaration becomes

(defun fact2 (x)
 (declare (type fixnum x))
 (let ((res 1))
  (loop while (> x 1)
   do (setf res (* res (decf x))))))

the firts one becomes

(defun fact1 (x)
 (declare (type fixnum x))
 (if (> x 1) (* x (fact1 (1- x))) 1))

Of course I have to declare the type here, otherwise it will put code to distinguish between several numeric types. And I did a

(declaim (optimize (speed 3)
                   (safety 0)
                   (space 0)
                   (debug 0)
                   (compilation-speed 0)))

just to be fair. The second one disassembles into

CL-USER> (disassemble #'fact2)
; disassembly for FACT2
; 248173A4:       BA04000000       MOV EDX, 4                 ; no-arg-parsing entry point
;       A9:       EB18             JMP L2
;       AB: L0:   8BC3             MOV EAX, EBX
;       AD:       83E804           SUB EAX, 4
;       B0:       8BD8             MOV EBX, EAX
;       B2:       895DFC           MOV [EBP-4], EBX
;       B5:       8BF8             MOV EDI, EAX
;       B7:       E8F18E7EFD       CALL #x220002AD            ; GENERIC-*
;       BC:       7302             JNB L1
;       BE:       8BE3             MOV ESP, EBX
;       C0: L1:   8B5DFC           MOV EBX, [EBP-4]
;       C3: L2:   83FB04           CMP EBX, 4
;       C6:       7FE3             JNLE L0
;       C8:       BA0B001022       MOV EDX, 571473931
;       CD:       8BE5             MOV ESP, EBP
;       CF:       F8               CLC
;       D0:       5D               POP EBP
;       D1:       C3               RET
NIL

Somehow I cannot make the GENERIC-* disappear, not even with a the or coerce declaration around the numbers. But the disassembly of the first one is

CL-USER> (disassemble #'fact1)
; disassembly for FACT1
; 24783F0D: L0: L1:83F904           CMP ECX, 4                ; no-arg-parsing entry point
;       10:       7F09             JNLE L3
;       12:       B804000000       MOV EAX, 4
;       17: L2:   8BE5             MOV ESP, EBP
;       19:       5D               POP EBP
;       1A:       C3               RET
;       1B: L3:   894DFC           MOV [EBP-4], ECX
;       1E:       8BC1             MOV EAX, ECX
;       20:       8BD0             MOV EDX, EAX
;       22:       83EA04           SUB EDX, 4
;       25:       8BDD             MOV EBX, EBP
;       27:       8D4424F8         LEA EAX, [ESP-8]
;       2B:       83EC20           SUB ESP, 32
;       2E:       8BCA             MOV ECX, EDX
;       30:       8918             MOV [EAX], EBX
;       32:       8BE8             MOV EBP, EAX
;       34:       E819000000       CALL L5
;       39:       8B4DFC           MOV ECX, [EBP-4]
;       3C:       8BD1             MOV EDX, ECX
;       3E:       8BF8             MOV EDI, EAX
;       40:       E868C387FD       CALL #x220002AD            ; GENERIC-*
;       45:       7302             JNB L4
;       47:       8BE3             MOV ESP, EBX
;       49: L4:   8BC2             MOV EAX, EDX
;       4B:       EBCA             JMP L2
;       4D:       8F4504           POP DWORD PTR [EBP+4]
;       50:       EBBB             JMP L1
;       52: L5:   8F4504           POP DWORD PTR [EBP+4]
;       55:       EBB6             JMP L1
NIL

From 10 to 1A, this seems to check whether the first argument is greater than something (1?), and if so, it jumps to L3, if not, it returns. In L3, it does a lot of things, especially it calls L5, which then jumps to L1, the first line, again. That is, it seems like it really does recursion here.

This is not very nice. Why is it that way?