Wednesday, June 9, 2010

the power of SUBTYPEP

Everyone who is serious about Common Lisp should read this article - http://www.pipeline.com/~hbaker1/Subtypep.html. If you came to Common Lisp from C/C++ or similar language background it is hard to understand merits of the such very abstract function. In fact, this is one the unknown gems of Common Lisp.

Sunday, June 6, 2010

Databases are categories

Read the presentation: Databases are categories. Really nicely written, but the last conclusion is just so boring - "Thus databases and programs can be smoothly integrated". Of course they can be, it is known for decades now (at least in Common Lisp)

BTW, Yes, RDF can be based on relational database as well.

Wednesday, June 2, 2010

lazy evaluation in Common Lisp

One of interesting features of Haskell is a lazy evaluation. This is not always desirable but sometimes it allows to implement some tricks which are not obvious for someone with eager language experience.

If you started to learn Haskell with "Gentle introduction in Haskell" (BTW, I feel your pain) one of the first examples is calculating list of well known Fibonacci numbers. In Haskell it looks like this:


fib = 1 : 1 : [ x + y | (x,y) <- zip fib (tail fib) ]


If you are not familiar with Haskell it looks like complete Vodoo magic. Something like if you are a mathematician and you see expression like
x = x + 1
Surely, it it is never true!

Anyway, this function goes like this:
  • First two numbers of the result list are the ones
  • The rest values are the sum of previous value of the list and one preceding that value. zip fib (tail fib) does the trick.
Lazy evaluation here make sure fib is not evaluated fully. It might be called "greedy" because it gives values up only when necessary.

Anyway, lazy evaluation can be replicated by Lisp if you hide values in lambda. It won't be evaluated unless you explicitly asked it to do so by funcall.

For conses it can be presented like this:

(defmacro fcons (first list)
(let ((f-var (gensym)))
`(let (,f-var)
(lambda ()
(if (null ,f-var)
(progn (setf ,f-var ,list)
,first)
(funcall ,f-var))))))


Define zip function:

(defun zip (l1 l2)
(lambda ()
(list (funcall l1) (funcall l2))))


We also need a special map function which "lift" some function into our lazy lists:

(defun fmap (f iter)
(lambda ()
(funcall f (funcall iter))))


This function transforms lazy list into it's tail:

(defun ftail (list)
(funcall list)
list)


So, finally we can write a Fibonacci numbers function:

(defun fib ()
(fcons 1
(fcons 1
(fmap (lambda (x)
(+ (first x) (second x)))
(zip (fib) (ftail (fib)))))))

Try it in REPL:
CL-USER> (setq *fib-function* (fib))

CL-USER> (funcall *fib-function*)
1
CL-USER> (funcall *fib-function*)
1
CL-USER> (funcall *fib-function*)
2
CL-USER> (funcall *fib-function*)
3
CL-USER> (funcall *fib-function*)
5

Or even better:

(defun take (n list)
(loop repeat n
collect (funcall list)))

(take 100 (fmap #'print (fib)))
...

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946