About me

About me

Feeds

RSS feed

Lisp through the looking-glass

26th November 2017

The most fundamental construct in Lisp is the list, implemented as a linked list of cons cells, represented in every Lisp textbook with a diagram like this:

LookingGlass1.gif

which, of course, is the internal representation for the list:

(a b c d)

Looking-Glass Lisp

However, Lisp could equally well have been implemented with the lists going right to left, rather than left to right. So in Looking-Glass Land the internal representation for this list would be:

LookingGlass2.gif

In normal Lisp this has the representation:

((((nil . d) . c) . b) . a)

Exploring this a bit further, let's write the Looking-Glass equivalents of first, rest, and cons. Initially I decided to call these tsrif, tser, and snoc, but that soon became a bit annoying, so I settled on ~first, ~rest, and ~cons.

Here are the definitions:

(defun ~first (list) (cdr list))
(defun ~rest (list) (car list))
(defun ~cons (a d) (cons d a))

Next, here's a function ~ to convert a list in normal Lisp representation to Looking-Glass representation:

(defun ~ (list)
  (cond
   ((null list) nil)
   (t (cons (~ (cdr list)) (car list)))))

For example:

CL-USER > (~ '(a b c d))
((((nil . d) . c) . b) . a)

Defining a reader macro

For convenience, we can define { and } as reader macros to represent Looking-Glass lists:

(set-macro-character #\{ '~list-reader)
(set-macro-character #\} (get-macro-character #\) nil))

(defun ~list-reader (stream char)
  (declare (ignore char))
  (~ (read-delimited-list #\} stream t)))

This defines { as a macro character that calls ~list-reader, and } as a second macro character that behaves like ). So now we can write:

CL-USER > '{a b c d}
((((nil . d) . c) . b) . a)

Longest Common Subsequence

Finally, to prove that this alternative Looking-Glass representation works just as well as the standard representation, here's a Looking-Glass version of the recursive Longest Common Subsequence routine I presented in the earlier article Longest Common Subsequence. It finds the longest sequence of elements that occur in the same order in both sequences, and is called ~lcs.

First we need to define ~length:

(defun ~length (list)
  (cond
   ((null list) 0)
   (t (1+ (~length (~rest list))))))

Then here's the definition of ~lcs:

(defun ~longest (a b)
  (if (> (~length a) (~length b)) a b))

(defun ~lcs (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((eql (~first a) (~first b))
       (~cons (~first a) (~lcs (~rest a) (~rest b))))
    (t (~longest (~lcs a (~rest b)) (~lcs (~rest a) b))))) 

Trying it out:

CL-USER > (~lcs '{1 2 3 5 6 8 9} '{2 3 1 4 6 7 8})
((((nil . 8) . 6) . 3) . 2)

In other words,

{2 3 6 8}

which is the correct answer.


blog comments powered by Disqus