Re: recursion performance

(message (Hello 'Pascal)
(you :wrote :on '(Wed, 30 Nov 2005 00:20:33 +0100))
(

PC> If you don't want to cheat, you can only do this by encoding numbers
PC> manually, for example implicitly by the number of atoms in a list, or
PC> some such.

or better using Church numerals :)

(setq *zero* (lambda (f x) x))
(setq *one* (lambda (f x) (funcall f x)))
(setq *two* (lambda (f x) (funcall f (funcall f x))))
(defun val (n) "function that converts Church numerals to normal ones"
(funcall n #'1+ 0))

;;let's test that it works:
;;CL-USER> (mapcar #'val (list *zero* *one* *two*))
;;(0 1 2)

(defun succ (n) "1+" (lambda (f x) (funcall f (funcall n f x))))
(defun pred (n) "1-" (lambda (f x)
(funcall
(funcall n (lambda (g) (lambda (h) (funcall h (funcall g f))))
(lambda (u) x))
(lambda (u) u))))

;;test them
;;CL-USER> (val (pred *one*))
;;0
;;CL-USER> (val (succ *two*))
;;3
;;CL-USER> (val (succ (pred *one*)))
;;1

;;note that there are no negative Church numerals (at least i can't imagine
such)
;;CL-USER> (val (pred *zero*)
;;0
;;also an interesting fact
;;CL-USER> (val #'funcall)
;;1

(defun zero? (n) (funcall n (constantly nil) t))

;;and now our recursive plus

(defun plus (n m)
(if (zero? n) m
(plus (pred n) (succ m))))

;;CL-USER> (val (plus *two* (succ *two*)))
;;5

;;working but fantastically slow

;;actually there's a simplier version

(defun plus* (n m)
(lambda (f x)
(funcall n f
(funcall m f x))))

PC> Again, this exercise doesn't teach anything about Lisp.

this one teaches that functional programming in Lisp is tricky but possible
:)

P.S. Zermelo numerals can be simulated as

(setq *zero* nil)
(setq *one* '(nil))
(setq *two* '((nil)))

(defun succ (n) (cons n nil))
(defun pred (n) (car n))
(defun val (n) (if n (1+ (val (pred n))) 0))
(defun zero? (n) (null n))

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")


.