CLAZY: lazy calling in Common Lisp

In a bout of Haskell envy I did a few tricks with macros, closures and
SYMBOL-MACROLET and added true lazy calling to CL. The result is (as
usual) in common-lisp.net. Check out the CLAZY project. Mailing
lists should be available as usual, but they are not yet reachable
from the web site.

The system should be ASDF-installable, YMMV.

Cheers
--
Marco

Marco,
here is some code you can take ideas from or publish directly.
See the examples for the difference between your approach and mine.

Cheers,
Mariano

(defmacro with-gensyms (vars &rest body)
`(let
,(mapcar (lambda (var) `(,var (gensym))) vars)
,@body))

(defmacro lazy-function (fname)
(with-gensyms (value exists)
`(multiple-value-bind (,value ,exists)
(gethash ',fname *lazy-funs*)
(when (not ,exists)
(error (format nil "Lazy function ~A does not exists" ',fname)))
,value)))

;; Manual lazy evaluation through delay/force constructs
(defstruct promise
value
thunk)

(defun force (promise)
(when (promise-thunk promise)
(setf (promise-value promise) (funcall (promise-thunk promise))
(promise-thunk promise) nil))
(promise-value promise))

(defun force (promise)
(labels ((force (promise)
(when (promise-thunk promise)
(setf (promise-value promise) (funcall (promise-thunk
promise))
(promise-thunk promise) nil))
(promise-value promise)))
(loop
with result = (force promise)
while (promise-p result) do (setq result (force result))
finally (return result))))

(defmacro delay (form)
`(make-promise :thunk #'(lambda () ,form)))

(defvar *lazy-funs* (make-hash-table) "The lazy functions")

;; NOTE: we use the symbol-macrolet code-walker
(defmacro lazy-defun (name lambda-list &rest body)
(let*
((bindings (make-hash-table))
(body
`(let
,(mapcar
(lambda (arg)
(setf (gethash arg bindings) (gensym (string arg)))
`(,(gethash arg bindings) ,arg)) lambda-list)
(symbol-macrolet
,(mapcar
(lambda (arg)
`(,arg (force ,(gethash arg bindings)))) lambda-list)
,@body))))
`(progn
(defmacro ,name (&rest args)
`(funcall
(lambda ,',lambda-list
,',body)
,@(mapcar (lambda (farg) `(delay ,farg)) args)))
;; We create a lambda that assumes its arguments to be lambdas
(setf (gethash ',name *lazy-funs*)
(lambda ,lambda-list
,body))
',name)))

(defmacro lazy-lambda (lambda-list &rest body)
(let
((bindings (make-hash-table)))
`(lambda ,lambda-list
(let
,(mapcar
(lambda (arg)
(setf (gethash arg bindings) (gensym (string arg)))
`(,(gethash arg bindings) ,arg)) lambda-list)
(symbol-macrolet
,(mapcar
(lambda (arg)
`(,arg (force ,(gethash arg bindings)))) lambda-list)
,@body)))))

(defmacro lazy-let (bindings &rest body)
(let
((binds (make-hash-table)))
`(let
,(mapcar
(lambda (binding)
(destructuring-bind (var value) binding
(setf (gethash var binds) (gensym (string var)))
`(,(gethash var binds) (delay ,value))))
bindings)
(symbol-macrolet
,(mapcar
(lambda (binding)
(destructuring-bind (var value) binding
(declare (ignore value))
`(,var (force ,(gethash var binds)))))
bindings)
,@body))))

(defmacro lazy-funcall (func &rest args)
`(funcall ,func ,@(mapcar (lambda (farg) `(delay ,farg)) args)))

;; Simple currification
(defmacro curry (&rest body)
(with-gensyms (x)
`(lambda (,x) (,@body ,x))))
;; Example:
;; (funcall (curry + 1) 2)

;; Examples:
;; (lazy-defun lazy-if (predicate then else)
;; (if predicate
;; then
;; else))
;; (lazy-if t 2 (print "hello")))
;; (lazy-if nil 2 (print "hello"))
;; (lazy-funcall (lazy-function lazy-if) nil 2 (print "hello"))

;; This demonstrates that we evaluate only once. We are using a hash
table to cache evaluated
;; thunks.
;; (lazy-defun single-eval (lazy-arg)
;; (print lazy-arg)
;; (print lazy-arg))
;; (single-eval (progn (print "im printed once") 3))

;; Problems: don't know about efficiency. The interpreter gets
embedded in the function definition. That
;; makes debugging quite difficult.

Hi

your code works as expected, but your macrofication of the results of
LAZY-DEFUN do not interact well with LAZY-FUNCALL.

(lazy-funcall 'lazy-if t 42 (loop))

results in an error. You have to call

(lazy-funcall (lazy-function lazy-if) 42 (loop))

It is true that it is nicer to write

(lazy-if t 42 (loop))

rather than

(lazy:call 'lazy-if t 42 (loop))

but macros and regular functions do not intermix well. I had thought
of going the macro way myself, but decided against it. I wanted to
preserve the ability to pass around lazy functional objects and to
keep the LAZY:CALL <=> FUNCALL symmetry as much as possible. But
maybe macroizing is better aesthetically after all.

I like the caching machinery using hash tables and that could be
reused.

The rest is just mucking the lambda list.

Cheers
--
Marco

http://common-lisp.net/project/clazy




On Jun 10, 3:35*pm, Mariano Montone <marianomont...@gmail.com> wrote:
> Marco,
> * * * here is some code you can take ideas from or publish directly.
> See the examples for the difference between your approach and mine.
>
> Cheers,
> * * * *Mariano
>
> (defmacro with-gensyms (vars &rest body)
> * `(let
> * * * *,(mapcar (lambda (var) `(,var (gensym))) vars)
> * * *,@body))
>
> (defmacro lazy-function (fname)
> * (with-gensyms (value exists)
> * * `(multiple-value-bind (,value ,exists)
> * * * * *(gethash ',fname *lazy-funs*)
> * * * *(when (not ,exists)
> * * * * *(error (format nil "Lazy function ~A does not exists" ',fname)))
> * * * *,value)))
>
> ;; Manual lazy evaluation through delay/force constructs
> (defstruct promise
> * * *value
> * * *thunk)
>
> (defun force (promise)
> * (when (promise-thunk promise)
> * * (setf (promise-value promise) (funcall (promise-thunk promise))
> * * * * * (promise-thunk promise) nil))
> * (promise-value promise))
>
> (defun force (promise)
> * (labels ((force (promise)
> * * * * * * *(when (promise-thunk promise)
> * * * * * * * *(setf (promise-value promise) (funcall (promise-thunk
> promise))
> * * * * * * * * * * *(promise-thunk promise) nil))
> * * * * * * *(promise-value promise)))
> * * (loop
> * * * * *with result = (force promise)
> * * * * *while (promise-p result) do (setq result (force result))
> * * * * *finally (return result))))
>
> (defmacro delay (form)
> * `(make-promise :thunk #'(lambda () ,form)))
>
> (defvar *lazy-funs* (make-hash-table) "The lazy functions")
>
> ;; NOTE: we use the symbol-macrolet code-walker
> (defmacro lazy-defun (name lambda-list &rest body)
> * (let*
> * * * ((bindings (make-hash-table))
> * * * *(body
> * * * * `(let
> * * * * * * *,(mapcar
> * * * * * * * *(lambda (arg)
> * * * * * * * * *(setf (gethash arg bindings) (gensym (string arg)))
> * * * * * * * * *`(,(gethash arg bindings) ,arg)) lambda-list)
> * * * * * *(symbol-macrolet
> * * * * * * * *,(mapcar
> * * * * * * * * *(lambda (arg)
> * * * * * * * * * *`(,arg (force ,(gethash arg bindings)))) lambda-list)
> * * * * * * *,@body))))
> * * `(progn
> * * * *(defmacro ,name (&rest args)
> * * * * *`(funcall
> * * * * * *(lambda ,',lambda-list
> * * * * * * *,',body)
> * * * * * *,@(mapcar (lambda (farg) `(delay ,farg)) args)))
> * * * * *;; We create a lambda that assumes its arguments to be lambdas
> * * * *(setf (gethash ',name *lazy-funs*)
> * * * * * * *(lambda ,lambda-list
> * * * * * * * *,body))
> * * * * *',name)))
>
> (defmacro lazy-lambda (lambda-list &rest body)
> * (let
> * * * ((bindings (make-hash-table)))
> * * `(lambda ,lambda-list
> * * * *(let
> * * * * * *,(mapcar
> * * * * * * *(lambda (arg)
> * * * * * * * *(setf (gethash arg bindings) (gensym (string arg)))
> * * * * * * * *`(,(gethash arg bindings) ,arg)) lambda-list)
> * * * * *(symbol-macrolet
> * * * * * * *,(mapcar
> * * * * * * * *(lambda (arg)
> * * * * * * * * *`(,arg (force ,(gethash arg bindings)))) lambda-list)
> * * * * * *,@body)))))
>
> (defmacro lazy-let (bindings &rest body)
> * (let
> * * * ((binds (make-hash-table)))
> * * `(let
> * * * * *,(mapcar
> * * * * * *(lambda (binding)
> * * * * * * *(destructuring-bind (var value) binding
> * * * * * * * *(setf (gethash var binds) (gensym (string var)))
> * * * * * * * *`(,(gethash var binds) (delay ,value))))
> * * * * * *bindings)
> * * * * *(symbol-macrolet
> * * * * * * *,(mapcar
> * * * * * * * *(lambda (binding)
> * * * * * * * * *(destructuring-bind (var value) binding
> * * * * * * * * * *(declare (ignore value))
> * * * * * * * * * *`(,var (force ,(gethash var binds)))))
> * * * * * * * *bindings)
> * * * * * *,@body))))
>
> (defmacro lazy-funcall (func &rest args)
> * `(funcall ,func ,@(mapcar (lambda (farg) `(delay ,farg)) args)))
>
> ;; Simple currification
> (defmacro curry (&rest body)
> * (with-gensyms (x)
> * * `(lambda (,x) (,@body ,x))))
> ;; Example:
> ;; (funcall (curry + 1) 2)
>
> ;; Examples:
> ;; (lazy-defun lazy-if (predicate then else)
> ;; * (if predicate
> ;; * * * then
> ;; * * * else))
> ;; (lazy-if t 2 (print "hello")))
> ;; (lazy-if nil 2 (print "hello"))
> ;; (lazy-funcall (lazy-function lazy-if) *nil 2 (print "hello"))
>
> ;; This demonstrates that we evaluate only once. We are using a hash
> table to cache evaluated
> ;; thunks.
> ;; (lazy-defun single-eval (lazy-arg)
> ;; * (print lazy-arg)
> ;; * (print lazy-arg))
> ;; (single-eval (progn (print "im printed once") 3))
>
> ;; Problems: don't know about efficiency. The interpreter gets
> embedded in the function definition. That
> ;; makes debugging quite difficult.

Marco Antoniotti wrote:
> In a bout of Haskell envy I did a few tricks with macros, closures and
> SYMBOL-MACROLET and added true lazy calling to CL. The result is (as
> usual) in common-lisp.net. Check out the CLAZY project. Mailing
> lists should be available as usual, but they are not yet reachable
> from the web site.
>
> The system should be ASDF-installable, YMMV.
>
> Cheers
> --
> Marco
>

Interesting. Have you written a prime number generator with this?
Something like,

;; http://clj-me.blogspot.com/2008/06/primes.html
;; in clojure:
(def primes (lazy-cons 2 ((fn this[n]
(let [potential-divisors (take-while #(<= (* % %) n) primes)]
(if (some #(zero? (rem n %)) potential-divisors)
(recur (inc n))
(lazy-cons n (this (inc n)))))) 3)))

On 15 Giu, 14:01, vanekl <va...@acd.net> wrote:
> Marco Antoniotti wrote:
> > In a bout of Haskell envy I did a few tricks with macros, closures and
> > SYMBOL-MACROLET and added true lazy calling to CL. The result is (as
> > usual) in common-lisp.net. Check out the CLAZY project. Mailing
> > lists should be available as usual, but they are not yet reachable
> > from the web site.
>
> > The system should be ASDF-installable, YMMV.
>
> > Cheers
> > --
> > Marco
>
> Interesting. Have you written a prime number generator with this?
> Something like,
>
> ;;http://clj-me.blogspot.com/2008/06/primes.html
> ;; in clojure:
> (def primes (lazy-cons 2 ((fn this[n]
> (let [potential-divisors (take-while #(<= (* % %) n) primes)]
> (if (some #(zero? (rem n %)) potential-divisors)
> (recur (inc n))
> (lazy-cons n (this (inc n)))))) 3)))

No, but you can try and then report back

More seriously, I ma interested in what people would like wrt the
choice of having each lazy function macrofied or not (as it is now).

Cheers
--
Marco

On Jun 15, 2:01*pm, vanekl <va...@acd.net> wrote:
> Marco Antoniotti wrote:
> > In a bout of Haskell envy I did a few tricks with macros, closures and
> > SYMBOL-MACROLET and added true lazy calling to CL. *The result is (as
> > usual) in common-lisp.net. *Check out the CLAZY project. *Mailing
> > lists should be available as usual, but they are not yet reachable
> > from the web site.
>
> > The system should be ASDF-installable, YMMV.
>
> > Cheers
> > --
> > Marco
>
> Interesting. Have you written a prime number generator with this?
> Something like,
>
> ;;http://clj-me.blogspot.com/2008/06/primes.html
> ;; in clojure:
> (def primes (lazy-cons 2 ((fn this[n]
> * *(let [potential-divisors (take-while #(<= (* % %) n) primes)]
> * * *(if (some #(zero? (rem n %)) potential-divisors)
> * * * *(recur (inc n))
> * * * *(lazy-cons n (this (inc n)))))) 3)))

So, you have not figured out yet?

Cheers
--
Marco

On Jun 15, 3:01 pm, vanekl <va...@acd.net> wrote:
> ;;http://clj-me.blogspot.com/2008/06/primes.html
> ;; in clojure:
> (def primes (lazy-cons 2 ((fn this[n]
> (let [potential-divisors (take-while #(<= (* % %) n) primes)]
> (if (some #(zero? (rem n %)) potential-divisors)
> (recur (inc n))
> (lazy-cons n (this (inc n)))))) 3)))

I don't think such calculations reflect the actual power behind lazy
evaluation. For instance, AFAIK, it's possible to construct similar
lazy streams using SERIES. While writing this, it makes me wonder that
what are the limits of lazy evaluation capabilities of SERIES package.
How far one can go using serie outputs produced by scanners supplied
by SERIES?

På Mon, 16 Jun 2008 13:10:26 +0200, skrev Volkan YAZICI
<volkan.yazici@gmail.com>:

> On Jun 15, 3:01 pm, vanekl <va...@acd.net> wrote:
>> ;;http://clj-me.blogspot.com/2008/06/primes.html
>> ;; in clojure:
>> (def primes (lazy-cons 2 ((fn this[n]
>> (let [potential-divisors (take-while #(<= (* % %) n) primes)]
>> (if (some #(zero? (rem n %)) potential-divisors)
>> (recur (inc n))
>> (lazy-cons n (this (inc n)))))) 3)))
>
> I don't think such calculations reflect the actual power behind lazy
> evaluation. For instance, AFAIK, it's possible to construct similar
> lazy streams using SERIES. While writing this, it makes me wonder that
> what are the limits of lazy evaluation capabilities of SERIES package.
> How far one can go using serie outputs produced by scanners supplied
> by SERIES?

to lazy for my taste at least.

I wrote a prime number finder and it completed in 0.047 s to count all
primes from 1 to 100000.

(defun prime-p (n)
(declare ((speed 3) (safety 0) (fixnum-safety 0))
(fixnum n))
(cond
((and (<= n 11) (member n '(2 3 5 7 11)) t)
((= (rem n 2) 0) nil)
((= (rem n 3) 0) nil)
((= (rem n 5) 0) nil)
((= (rem n 7) 0) nil)
(t
(loop for i fixnum from 11 to (isqrt n) by 2
(when (= (rem n i) 0) (return-from prime-p nil))
t)))

(defun count-primes (max)
(check-type max (fixnum 1 #.most-positive-fixnum))
(loop with count = 1
for i from 1 to max do
(when (prime-p i) (incf count))
finally (return count)))

(time (test 100000))
0.047s (50 ns pr. prime!)
(time (test 1000000))
1.015s (twice as long pr prime)

This is also a naive use of aristofanes but avoids the overhead of
remembering previous primes.
It isn't elegant, but is near optimally efficient for small numbers. (<
1000000)

A few tips.
The loop unrolling saves time.
The (< n 11) bit saves time.
rem is 10 times faster than mod because mod conses a remainder ratio on
the heap.

Of cource finding primes is only interesting for large prime numbers, but
I only invoke the more complex algorithm based on fermant's little theorem
on large numbers.

(Gauss observes that lim n-->inf pi(n) / (n / log n) = 1 where pi(n)
returns the number of prime numbers upto n.
Thus by aristophanes you would need O(n / log n) divisions to test
primality for each prime.
So counting/generating primes upto n would grow by O(n^2) which would
quickly become impractical.)

--------------
John Thingstad

Volkan YAZICI wrote:
> On Jun 15, 3:01 pm, vanekl <va...@acd.net> wrote:
>> ;;http://clj-me.blogspot.com/2008/06/primes.html
>> ;; in clojure:
>> (def primes (lazy-cons 2 ((fn this[n]
>> (let [potential-divisors (take-while #(<= (* % %) n) primes)]
>> (if (some #(zero? (rem n %)) potential-divisors)
>> (recur (inc n))
>> (lazy-cons n (this (inc n)))))) 3)))
>
> I don't think such calculations reflect the actual power behind lazy
> evaluation. For instance, AFAIK, it's possible to construct similar
> lazy streams using SERIES. While writing this, it makes me wonder that
> what are the limits of lazy evaluation capabilities of SERIES package.
> How far one can go using serie outputs produced by scanners supplied
> by SERIES?

Don't know what you mean by "actual power behind lazy evaluation."
This above algo puts off computation by using lazy constructs, which makes
it more efficient. This algo appears to be more efficient than John's
since it is not recomputing the factorization over and over again for
each new test of primality.

And if there's another package that has similar lazy constructs, so
what? I'm sure there is a lot of overlap between some libraries.
Doesn't mean the clazy library is any less useful.

På Mon, 16 Jun 2008 16:03:05 +0200, skrev vanekl <vanek@acd.net>:

> This algo appears to be more efficient than John's
> since it is not recomputing the factorization over and over again for
> each new test of primality.

Appears being the operative word.
Goes back to the old saying that Lispers know the value of everything and
the cost of nothing.

My algorithm can rest in the L1 cache. It doesn't need to access memory.
(no consing)
Although there are fewer iterations each step is sufficiently expensive
that you still loose.
For bigger primes there are more efficient algorithms also so that one is
never optimal.

--------------
John Thingstad