Equivalence Tester

I finally got an equivalence tester for Common Lisp created. The code can be found by following the previous link or by reading more. Here's its description:

This method is used to compare classes. Override it to specialize it's testing for your classes. There's already a method specialized for built in classes that uses EQUAL, cons cells, and any standard object.

Ruby Style Continuations In Lisp


A few days ago I found out Ruby supported continuations. I started playing with them in an experiment to be detailed later. One of the things Ruby has over Lisp is an understandable syntax for them. In Lisp all I had was Paul Graham's continuation code from his Lisp book:

(setq *cont* #'identity)

(defmacro =lambda (params &body body)
  `#'(lambda (*cont* ,@params) ,@body))

(defmacro =defun (name params &body body)
  (let ((f (intern (concatenate 'string
				"=" (symbol-name name)))))
      (defmacro ,name ,params
	`(,',f *cont* ,,@params))
      (defun ,f (*cont* ,@params) ,@body))))

(defmacro =bind (params expr &body body)
  `(let ((*cont* #'(lambda ,params ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

(defmacro =funcall (fn &rest args)
  `(funcall ,fn *cont* ,@args))

(defmacro =apply (fn &rest args)
  `(apply ,fn *cont* ,@args))

PG also provided some examples using that. One of them was a depth first traversal. It creates the continuation when it pushes a lambda. The syntax basically offers no help in understanding how to use it as you can see:

(setq *saved* nil)

(=defun dft-node (tree)
  (cond ((null tree) (dft-restart))
	((atom tree) (=values tree))
	(t (push #'(lambda () (dft-node (cdr tree)))
	   (dft-node (car tree)))))

(=defun dft-restart ()
  (if *saved*
      (funcall (pop *saved*))
      (=values 'done)))

(=defun dft2 (tree)
  (setq *saved* nil)
  (=bind (node) (dft-node tree)
    (cond ((eq node 'done) (=values nil))
	  (t (princ node)

Even with that example, I still couldn't wrap my head around it until I started playing with Ruby's. Ruby has a callcc keyword that creates a continuation. It's syntax is basically:

callcc do |cc|
   # Do some stuff
# Do some other stuff when we call 'cc' above

That syntax makes it pretty easy to understand how to use them which is all that matters. PG's example code offered nothing in that direction, so I recreated PG's DFT example in Ruby and got the following:

$conts =

def dft_restart()
  if $conts.length > 0
    return nil

def dft_node(tree)
  if tree == nil
  elsif tree.class != Array
    return tree
    callcc do |cc|
      $conts.push cc
      return dft_node(tree[0])
    return dft_node(tree[1, tree.length])

def dft2 tree
  $conts =
  node = dft_node tree
  if node != nil
    puts node
Ruby's callcc helped me understand exactly what was going on. So I started messing around and created a macro that creates Ruby's callcc in Lisp. This is the macro:

;; Ruby style syntax
(defun search-replace (list key value)
  "Replace all instances of KEY found in LIST with VALUE."
  (cond ((null list) nil)
	((symbolp list) (if (eq list key) value list))
	((atom list) list)
	(t (cons (search-replace (car list) key value)
		 (search-replace (cdr list) key value)))))

(defmacro callcc (inner &body body)
  (let ((var-name (first inner))
	(var-exp `#'(lambda () ,@body)))
    `(progn ,@(search-replace (cdr inner) var-name var-exp))))

The syntax for that is essentially like Ruby's:

(callcc (cc do some stuff)
   Do some more stuff when we call 'cc')

The cc variable name can be changed to whatever, and it represents the continuation that you can save to call later. So back in Lisp PG's DFT-NODE then becomes:

(=defun dft-node (tree)
  (cond ((null tree) (dft-restart))
	((atom tree) (=values tree))
	(t (callcc (cc
		    (push cc *saved*)
		    (dft-node (car tree)))
 	      (dft-node (cdr tree))))))

To me anyway that makes more sense because the voodoo isn't up front. It's tucked into the callcc. To you innocent bystanders, it probably still makes no sense, but now you have some code to play with.



I just got done reading a transcript of a speech Richard M. Stallman did back in 2002 about Lisp and Emacs. I've clipped a quote that's included below about his motivations to create Guile. One of my thoughts are: Why wasn't this done for the web? Lisp lists as markup, Lisp to script, and nirvana with a Lisp. The quote is also along the lines of what MS wants to do with their common language runtime.

There's an interesting benefit you can get from using such a powerful language as a version of Lisp as your primary extensibility language. You can implement other languages by translating them into your primary language. If your primary language is TCL, you can't very easily implement Lisp by translating it into TCL. But if your primary language is Lisp, it's not that hard to implement other things by translating them. Our idea was that if each extensible application supported Scheme, you could write an implementation of TCL or Python or Perl in Scheme that translates that program into Scheme. Then you could load that into any application and customize it in your favorite language and it would work with other customizations as well. (RMS's "My Lisp Experiences and the Development of GNU Emacs")

Why Lisp Is Unpopular

Brian Mastenbrook made a post questioning why Lisp is unpopular. To be quick, it's unpopular for these reasons:

  • Sockets: Where's my standard socket library to talk with the rest of the world?
  • GUI: Where's my GUI API that's on par with Trolltech's Qt, C#'s Forms, or Java's [whatever it's called, Swing?]?
  • Threads: Not so important, but where's my standard thread library?
  • FFI: A standard way of being able to interface with programs written in other languages would be nice too. There is UFFI but a standardized way would go farther.

I think those are the big four. I can pick and choose what XML parser I want to use. The above are required to be on par with the languages Brian mentioned.

Unicode and Lisp

I finally managed to prove to myself that Lisp (SBCL anyway) supports Unicode. It took some persevarence, especially with a borked ebuild for Emacs that failed to install LEIM. This is how I managed to demonstrate Unicode in the Lisp REPL within Slime.

Using Unicode in the Lisp REPL requires a couple of things to start. A Unicode aware Lisp implementation such as Clisp or SBCL and Emacs version 21.4 or greater. I won't go into setting those up here, but in Gentoo you'll need to be sure SBCL is emerged with the "unicode" USE flag, and Emacs with the "leim" use flag and possibly some tweaking to the ebuild.

To get started you need to tell Emacs and Slime that you want to use UTF-8. For Emacs this can be done in the Options > MULE > Set Language Environment menu or with the command set-language-environment. utf-8 is a good value.

You'll also need Slime. To get Slime setup for Unicode you need to set its slime-net-coding-system Emacs variable. This can be done in either your .emacs file or in the *scratch* buffer. Just evaluate or add:

(setq slime-net-coding-system 'utf-8-unix)

The utf-8-unix is the coding system Slime uses for Unicode. The Emacs variable slime-net-valid-coding-systems lists other valid options for Slime's coding system, but for Unicode the above value is what you want.

Once Emacs and Slime know that you want stuff done in Unicode you can start Slime up. Now you'll be wondering if anything has changed. Now for the fun.

Getting Unicode characters entered than Slime is a real PITA. Slime choked on the characters I punched in with the Japanese input method. Even pasting from some applications only produced a question mark. Firefox is friendly though. You can copy a Unicode string and in Emacs it'll insert the hexdecimal value of the characters prepended by \u. That comes in handy, but it could be better.

So to get your first sign of Unicode support you can copy and paste it into Emacs. You should see \u2211. To get that printed evaluate:

(code-char #x2211)
; => #\∑

You may only see a box though, but do take note of the #x instead of the \u. That tells Lisp that it's a hexadecimal number. If you only see a box then your selected font can't render that character. You can try another one if you want like ɥ which has a hexadecimal value of 0x0265.

If you're using CLisp then your output might be different. CLisp is a bit better than SBCL about Unicode. You can specify the Unicode character above by using either #\u2211 or #\N-ARY_SUMMATION. The latter may also be what CLisp prints out too. If that's the case, then you'll have to coerce it into a string before going onto the next step because you'll need an actual character to copy and paste, and actual characters don't work.

(coerce '(#\u2211) 'string)

Now we can define the function with some copy and paste. You'll need to copy the character after #\ in SBCL or the one between the quotes in CLisp to create:

(defun ∑ (list)
   (if list
       (+ (first list) (∑ (rest list)))
; => ∑
(∑ '(1 2 3 4 5))
; => 15

So that's the pain that is Emacs, Lisp, and Unicode. Perhaps in the future this will be easier and we can just punch in a bunch of Japanese and math characters to create some funky programs.

Update (2006-08-16): An article describing how to convert between character encodings and such is available on CLiki titled CloserLookAtCharacters.

Syndicate content

Ad's by Google