closures in clojure

A friend of mine said that he read somewhere that you couldn’t do a closure in clojure. I thought that was probably incorrect – but I haven’t really done much in clojure. He couldn’t find the link so I thought I’d put it to the test:

(defn plusn [x]
(fn [y] (+ x y)))

(def plus5 (plusn 5))
(plus5 3)

>> 8

Yep, it’s got closures

 

Common Lisp Lexer

I’ve been interested in compilers lately, leading me to purchase the
last book I blogged about and a $6 copy of the 1st ed. Dragon book, and I
have a copy of the ANTLR reference book coming.

Of course, knowing that Lisp is well suited to working with compilers,
I wanted to play with some of this stuff in lisp.

I loaded cl-yacc and messed with their list lexer that they had in the
examples. This led me to wanting to get a more complex lexer that
would work well with a file or string.

Of course I could just use the lisp read which is in essence a lexer,
it doesn’t handle things like “parse this line;” where you want the
semicolon to be a token in it’s own right. Lisp read will happily pull
in the last symbol ‘line;’.

So . . I used ASDF to load up regex and clawk from cliki, and
downloaded lexer from wherever Google led me. This is where my
problems began – and I’m hoping that I can avoid you some pain.

The lexer that I downloaded referenced a function
macroexpand-regex-expr which was not available, and when I tried to
figure out what it might be referencing, I still had problems. Perhaps
I would have gotten to the end of it, but then again, maybe not.

The right thing to do (in this case) was to use the lispbuilder code
that is at sourceforge. Because
they weren’t immediately installable with asdf-install I had to
extract them and re tgz them. I added these to cliki so
that we can just asdf-install them. Just for grins, here is some of
the code that I’m playing with.

 

(defparameter test-lexer)

(lispbuilder-lexer:deflexer test-lexer
    ("[0-9]+([.][0-9]+([Ee][0-9]+)?)"
      (return (values 'flt (read-from-string lispbuilder-lexer:%0))))
    ("[0-9]+"
      (return (values 'int (parse-integer lispbuilder-lexer:%0))))
    ("[:alpha:][:alnum:]*"
      (return (values 'id (read-from-string lispbuilder-lexer:%0))))
    ("(-|[+*/])"
      (return (values (read-from-string lispbuilder-lexer:%0) (read-from-string lispbuilder-lexer:%0))))
    ("[(]"
      (return (values '|(| '|(|)))
    ("[)]"
      (return (values '|)| '|)|)))
    ("[:space:]+") )

(defvar *expression-parser*)

(yacc:define-parser *expression-parser*
  (:start-symbol expression)
  (:terminals (int id + - * / |(| |)|))
  (:precedence ((:left * /) (:left + -)))

  (expression
   (expression + expression #'i2p)
   (expression - expression #'i2p)
   (expression * expression #'i2p)
   (expression / expression #'i2p)
   term)

  (term
   id
   int
   (- term)
   (|(| expression |)| #'k-2-3)))

(setq *test* (yacc:parse-with-lexer (test-lexer "x * - (2 + 3) * y") *expression-parser*))

(print *test*)

 (* (* X (- (+ 2 3))) Y)

 

Review of Constructing Language Processors for Little Languages

Randy Kaplan ISBN 0-471-59753-8

This book is an introduction to interpreters and compilers. It is intended to
be down a level from the dragon book. I found the book accessible, an
easy read for the most part. (I read the book mostly over the weekend,
but I did do some skimming) If anything, it connected the
dots just a little too much, but the book stays true to it’s purpose.

Kaplan starts with a survey of little languages, and discusses design
of languages. That discussion was one of the reasons why I bought the
book and I was a bit disappointed with that aspect because it
covered just a few pages (37-39). Other parts of the tour were quite
adequate and you come away with a firm grasp of what a lexer and a
parser do as well as a basic understanding of lex & yacc and how all
of this stuff is brought together to make an interpreter or a
compiler. I particularly enjoyed the section on computation engines &
finite state automata (82 ff)

The author is careful to point out that the standard book on the topic
is the dragon book, and points you to it in several instances.

Most of the book revolves around a language that the author made up
for a specific purpose and takes if cradle to grave. He develops a
grammar, lexer, parser (both from scratch and using lex & yacc) and
shows in very fine detail (too much at times) how each fits into the
overall picture. All source code is given in c, often with a walk
through of each procedure and data structure.

How does this relate to lisp? Well he does have an interesting chapter
in the back showing how do manage the same task (i.e. a little
language) in both prolog and lisp. He doesn’t start with the same
input as he uses for his grammar and example in the rest of the book
but shows how to modify the grammar slightly to allow you to write
your little language. I would certainly like to revisit both of those
sections, but they are just a tiny part of the book. I was hoping to
find some references to fuller works on the topic with these languages
in mind. (for lisp he pointed to CLTL2 and SICP)

Also, it has been a very long time since I have programmed in c. It
was striking how verbose the source code really was for the
project. After he presents the prolog code for one of the statements
he comments: “This may seem like a lot of code, but it translates and
executes …”.

In the last chapter, it seems that he is making the case for a richer
environment for making little languages and that prolog, lisp and
forth were all better platforms for creating them, even
with the helper programs lex and yacc. However, as I read along and
noticed several places where things would have been much easier in
lisp it may have been mere projection on my part.

I am glad that I read the book, but I think that I probably should
have saved my book buying $$ for the dragon book and tried to borrow
this one. On the other hand, I actually got through this book and I
found it useful for thinking about the upcoming design of a little
language, and I don’t know if either could be said about the dragon
book.

 

(cond (n00b flame) (t work))

I was messing around with a cond statement and ended up with a bunch
of ugly looking statements. One of the problems with lisp, is that it
gives you the sense that you can do anything anywhere. You pretty much
can, but not without some problems every now and then.

I thought I would solve the problem by making a macro so it would look
something like:

(cond (macro parm1 parm2 parm3)
      (macro parm1 parm2 parm3))

Any lisp veteran is probably chuckling to themselves thinking that I
probably have also tried to do the functional equivalent of something like:

(setq x '(pred sexpr))

(cond x)

As I learned quite quickly, you just can’t do this because of the
macro expansion of cond.

>(print (macroexpand-1 '(cond (macro param1 param2)
		      (macro param1 param2))))

(IF MACRO (PROGN PARAM1 PARAM2) (COND (MACRO PARAM1 PARAM2)))

The problem in both of these scenarios is that the cond macro gets
expanded before any of the other macros, essentially goofing up our
original plan.

To solve the problem I just changed it around so I had a macro that
took the list of parameters that I wanted and created the entire cond
statement for me.

(cond-macro (param1 param2)
	    (param1 param2))

Which did exactly what I wanted.

 

Cat in the Hat

On planet lisp the other day (ok, it’s been months – it took me a while to get around to posting this) there was an entry for a lisp job at Streamtech in the Netherlands. In their job posting they had links to a number of fun problems. I decided to take a stab at one of them and here is what I came up with.

(PDF can be found here)

Background

(An homage to Theodore Seuss Geisel)

The Cat in the Hat is a nasty creature,
But the striped hat he is wearing has a rather nifty feature.

With one flick of his wrist he pops his top off.

Do you know what’s inside that Cat’s hat?
A bunch of small cats, each with its own striped hat.

Each little cat does the same as line three,
All except the littlest ones, who just say “Why me?”

Because the littlest cats have to clean all the grime,
And they’re tired of doing it time after time!

The Problem
A clever cat walks into a messy room which he needs to clean. Instead of doing the work alone, it decides to have its helper cats do the work. It keeps its (smaller) helper cats inside its hat. Each helper cat also has helper cats in its own hat, and so on. Eventually, the cats reach a smallest size. These smallest cats have no additional cats in their hats. These unfortunate smallest cats have to do the cleaning.

The number of cats inside each (non-smallest) cat’s hat is a constant, N. The height of these cats-in-a-hat is times the height of the cat whose hat they are in.

The smallest cats are of height one;
these are the cats that get the work done.

All heights are positive integers.

Given the height of the initial cat and the number of worker cats (of height one), find the number of cats that are not doing any work (cats of height greater than one) and also determine the sum of all the cats’ heights (the height of a stack of all cats standing one on top of another).

The Input
The input consists of a sequence of cat-in-hat specifications. Each specification is a single line consisting of two positive integers, separated by white space. The first integer is the height of the initial cat, and the second integer is the number of worker cats.

Sample Input

216 125
5764801 1679616
0 0

Sample Output

31 671
335923 30275911

Solution – Math

The key to understaning this problem is to understand that the relationship of the levels given in the problem description. This equation is just as true for the bottom most level of the worker cats as it is for any of the rest of it. Here we know that and so we know that and it follows that and we can also derive

by substituting it back into the equation as we go up the levels.

As we go down the list we can see that the number of cats increases by powers so at the top level we have one cat (). On the second level we have or cats, on the third level we have cats and so on up to for the number of levels that we have. We can see the same kind of relationship going from the bottom up. On the lowest level, the level with the worker cats we start with a size of 1 or on the next to the lowest level we have and going up to the top level as we described above.

We are given numbers for both of these equations for the number of levels we have, the height of the top cat and the number of worker cats at the bottom The numbers we really need is the number of cats in each hat and the number of levels . If we play with these formulas we can say : and and that for some :

because we do not have a n-root function in our target computer language, we will rewrite the above expression

Lets try it for the first set of inputs:

So we can say that there are 4 levels () and we know that and the height of the second level cats is

and this allows us to calculate the actual output that we need to know.

First we solve for the total number of all of the non working cats:

And then we solve for the total height of all of the cats:

The Code

The following code doesn’t follow exactly the formulas above. What it does is recursively descends until we find our level, and then it performs the sums on the two items we are interested in as it works it’s way back up. While it is not tail recursive, the number of levels should be serviceable.

(defun catwalk (height workers)
  (if (eq height 1) ; kitty must work alone
      (list 0 1)
    (let ((retlist (catwalk-sub height workers 0)))
      (subseq  retlist 0 2 ))))

(defun catwalk-sub (height workers level )
  (let ((power (if (not (zerop level)) (/ 1.0 level) 0)))
    (cond
     ((eq 1 (ceiling (- (expt height power) (expt workers power ))))

      (list 0 workers (round (expt workers (/ 1.0 level))) level))
     (t (destructuring-bind (sumworkers sumheight n depth)
	    (catwalk-sub height workers  (+ 1 level))
	  (progn
	    (print (list sumworkers sumheight n depth level))
	    (list (+ (expt n level) sumworkers)
		  (+ (* (expt n level) (expt (+ n 1) (- depth level))   ) sumheight)
		  n depth)))))))

(catwalk   216 125)
(31 671)

(catwalk 5764801 1679616)
(335923 30275911)

 

cffi-uffi-compatible

Last night when I was trying to get clsql working on solaris, I had some problems installing uffi which is a requirement. I saw the cffi-uffi-compat.asd in the cffi area and figured there must be a way to go and make it look like uffi to the rest of the world.

After a bit of googling . . .

cat uffi.asd
;;;-*- Mode: Lisp; Package: COMMON-LISP-USER -*-

(defpackage :asdf-uffi (:use #:asdf #:cl))
(in-package :asdf-uffi)
(defsystem uffi :depends-on (:cffi-uffi-compat))

;;; End file uffi.asd

I removed the uffi package that I had installed and added this to my site-systems and I was off and running. Well, OK with clsql I was off and crawling, but that is a different post.

 

‘Fixed’ cl-opengl bindings

For some reason I have often had a desire to get cl-opengl working. I don’t have any particular purpose in mind, but it seems to be a requirement for some of the interesting projects that come up from time to time, such as perfectstorm or cello.

I run 64 bit gentoo on an AMD system and because I had a hard time compiling sbcl there, I managed to get a 32bit version installed. By now you might have an inkling of what my problem was.

I checked to make sure that I had libglut installed:

/usr/lib32/libglut.so.3
/usr/lib32/libglut.so
/usr/lib32/libglut.so.3.7.1
/usr/lib64/libglut.a
/usr/lib64/libglut.so.3
/usr/lib64/libglut.la
/usr/lib64/libglut.so
/usr/lib64/libglut.so.3.8.0

To make a long story short, I had freeglut installed, but for some reason the 32 bit libraries had openglut installed which (by google search) seems to be incompatible with the cl-opengl package.

At first I just thought that it was an older version of freeglut, but after compiling both a couple of times the version 3.7.1 seems to corrospond to openglut and 3.8.0 to freeglut.
After trying and failing to get the 32 bit package built, I copied the library over from another machine and put it in /usr/lib32 and re-set up my symbolic links to libglut.so and libglut.so.3 and then everything started working – YAY!

 

UTF conversion

I needed a script that ran a conversion to utf8 from an unknown encoding.

I originally had a file that would work on multiple files, but I needed a script that would work on only one file, but returned a status .

There are a few inherent problems with it, such as we are just guessing what encoding a file might be in if it is not in utf-8, but for my purpose that will be the right guess very close to 100% of the time making it ‘good enough’

 # we only want to do the conversion if we have problems with it in the first
 # place

	if iconv -f utf8 -t utf8 $* > /dev/null
   then
     echo “$* doesn’t need conversion”
   else
     if iconv -f WINDOWS-1252  -t utf8 $* > /dev/null
      then
       echo “performing WINDOWS conversion on $*”
       iconv -f WINDOWS-1252 -t utf8 $* > $*.utf8
       mv $*.utf8 $*
     elif iconv -f latin1  -t utf8 $* > /dev/null
       then
      echo “performing LATIN conversion on $*”
      iconv -f latin1 -t utf8 $* > $*.utf8
      mv $*.utf8 $*
     else
       echo “I don’t have any idea what kind of encoding this has”
       exit 65  # return error
     fi

fi

exit 0

No warranty express or implied.

 

Convert Mac OpenType fonts for Linux

I purchased a group of fonts for a project I was working on, and I got the mac version of OpenType fonts in the hopes that some day, I too will be a mac owner.

I unzipped the file and found that all of the files were xxx.otf.bin which of course would not work with GIMP.

After a bit of investigation, I found that if you just strip the first 129 bytes from the file, it will take off enough of the mac file stuff and give you a working otf file.

I did this by doing something like the following:

cat ACaslonPro-Italic.otf.bin | tail -c+129 > ACaslonPro-Italic.otf

of course, I had a bunch of these, and I didn’t want to type that every time so I did the following:

ls *.bin | awk 'BEGIN{FS="."}{print "cat " $1 "." $2 "." $3 " | tail -c+129 > " $1 "." $2}' | bash

which basically creates a command like the above for each .bin file in the directory, and feeds it to a bash shell where it executes all of the commands, and then I have a directory full of shiny new fonts that I can use with gimp.

Hope this helps someone.

 

Lisp Sticks

In which a silly old bear does useless exercises with lisp for personal amusement.
In my last posting I created a simple macro to ‘tweak’ the predicate of a while loop. If the predicate was < something then I changed it to <= something. Anyone who looked at the macro may be asking a few questions.

(defmacro while2 (test &body body)
  (let ((lastpart (cdr test)))
  (if (eq (car test) '<)
      `(do ()
        ((not (or ,test
	      	   (eql ,@lastpart))))
        ,@body)
      `(do ()
        ((not ,test))
        ,@body))))

Why didn’t you just use (<= ,@lastpart), or even replace the (not (< ,@lastpart)) with (> ,@lastpart)?
And they’d be right, of course, but I was trying to use the section to learn a thing or two about lisp. I wanted to simulate the case where we were evaluating something more than once where the user expected it to be evaluated only once.
Using either of the above replacements would cause the macro to work as expected. As it is written it doesn’t work as expected. This is actually by design, so be nice and play along with me!
Here is what happens when I call Grahams macro with some new code.

CL-USER> (while (< (incf x) 5)
	   (format t "I'm at ~a~&" x))
I'm at 1
I'm at 2
I'm at 3
I'm at 4
NIL
CL-USER> x
5

No big surprises there, but then I ran my macro which we would expect to print out 1 through 5 since the macro is intending to do the same thing as if I had replaced the < in the while2 expression with <=

CL-USER> (setq x 0)
0
CL-USER> (while2 (< (incf x) 5)
	   (format t "I'm at ~a~&" x))
I'm at 1
I'm at 2
I'm at 3
I'm at 4
NIL

Whoops, what went wrong? Why did the macro not run as expected? The value after the run is what we expected, but the output is not.

CL-USER> x
6

We start to see what happened when we look at the expansion of the macro . ..

(DO () ((NOT (OR (< (INCF X) 5) (EQL (INCF X) 5)))) (FORMAT T "I'm at ~a~&" X))

when (incf x) is equal to 5, the first condition fails so we check to see if (incf x) is equal to 5. By evaluating the expression again, the current value is now 6 and it’s not equal to 5 so we break from our loop.
The problem here is that we are evaluating (incf x) two times in some cases when we really want to evaluate only once.
Again, we are working with an artificial problem because we could solve the whole thing rather nicely by just replacing < with <= in our macro. We are solving the case for where we really would need to evaluate something in a similar fashion as we currently our with our where2 macro.
What we need to do is assign all the potential arguments to a gensym and then use the gensym in our expression like this:

(defmacro while2 (test &body body)
  (let* ((lastpart (cdr test))
         (symlist  (mapcar (lambda (x) (list (gensym) x)) lastpart)))
  (if (eq (car test) '<)
      `(do ()
        ((let ,symlist
	     (not (or (< ,@(mapcar #'car symlist))
	      	   (eql ,@(mapcar #'car symlist))))))
        ,@body)
      `(do ()
        ((not ,test))
        ,@body))))

now if we expand the macro we get:

(macroexpand-1 '(while2 (< (incf x) 5)
	   (format t "I'm at ~a~&" x)))
(DO ()
    ((LET ((#:G1906 (INCF X)) (#:G1907 5))
       (NOT (OR (< #:G1906 #:G1907) (EQL #:G1906 #:G1907)))))
  (FORMAT T "I'm at ~a~&" X))

And it works fine:

(setq x 0)
(while2 (< (incf x) 5)
	   (format t "I'm at ~a~&" x))
I'm at 1
I'm at 2
I'm at 3
I'm at 4
I'm at 5
CL-USER> x
6

Except when we throw it a curve ball:

(setq x 0)
(while2 (< (incf x) 5 6)
	   (format t "I'm at ~a~&" x))
invalid number of arguments: 3

So we change it so that we check whether each element is less than or equal. (Yes, yes, if we wouldn’t have had a <= operator, we would have been much smarter to write just that piece in the beginning, but I had to see this through)

 

(defmacro while2 (test &body body)
  (let* ((lastpart (cdr test))
         (symlist  (mapcar (lambda (x) (list (gensym) x)) lastpart)))
  (if (eq (car test) ‘<)
      `(do ()
        ((let ,symlist
	     (not (every (lambda (z) (or (< ,(caar symlist) z)
	     	  	 	     	 (eql ,(caar symlist) z)))
					 (list ,@(mapcar #‘car (cdr symlist)))))))

        ,@body)
      `(do ()
        ((not ,test))
        ,@body))))

Which expands to:

(DO ()
    ((LET ((#:G2002 (INCF X)) (#:G2003 5) (#:G2004 6))
       (NOT (EVERY (LAMBDA (Z) (OR (< #:G2002 Z) (EQL #:G2002 Z))) (LIST #:G2003 #:G2004)))))
  (FORMAT T "I'm at ~a~&" X))

Which finally does the exact same thing it would do as if we called it with the <= that we wanted in the first place

(defmacro while2 (test &body body)
  (let ((lastpart (cdr test)))
  (if (eq (car test) '<)
      `(do ()
        ((not (<= ,@lastpart)))
        ,@body)
      `(do ()
        ((not ,test))
        ,@body))))