Short koan-like code snippets (was: coerce for arbitrary types)

Regarding that proposed koan earlier: Does anybody have a
collection of short code snippets which likewise illustrate a whole
mess of deep understanding, where just trying to understand why
this particular snippet of code produces the result it does will
enlighten a newbie?
From: vanekl <va...@xxxxxxx>
a 10-line recursive BFS
I assume you mean breadth-first search (in some sort of tree,
possibly binary)? Why would anybody want to write that recursively?
From: Alan Crowe <a...@xxxxxxxxxxxxxxxxxxxxxxx>
For fun :-)
Let me see if I can find the 10-line recursive BFS algorithm ...
Will four lines do?
(defun bfs6 (test children pending)
(and pending
(or (some test pending)
(bfs6 test children (mapcan children pending)))))

Um, that is a bit inscrutable. It needs some documentation as to
what are natural values and what are continuations or other unusual
types of data. I studied that code for quite some time, and it
seems reasonable that perhaps:
- test is a predicate for filtering the nodes as to which satisfy
the toplevel goal and which don't.
- children is a function which, given a node, returns a list of all
children to that node, but furthermore always makes a copy of
that list before returning, so that it's safe to use mapcan on
the result.
- pending is a list of nodes at the current level, each of which
has been discovered at the previus level but not yet processed
The algorithm seems to be a tail-recursive expression of what
is essentially an iterative algorithm:
(defun bfs6 (test children pending) ;At start, pending = (topOfTree)
(loop ;One cycle of loop per level of tree being traversed
(unless pending (return NIL)) ;If we've bottomed out already
(let ((founds (some test pending)))
(when founds (return founds))) ;If we've found our target at this level
(setq pending (mapcan children pending)) ;Step down to next level
))
Note that test and children are *constants* throughout the entire
tail-recursive, or iterative, algorithm, and it unnecessarily
complicates the expression of the algorithm to pass each explicitly
through each level of recursion emulating iteration.
WIth the iterative expression I proposed, there's only one setq, on
the *variable* pending, so it's obvious that test and children are
constants, not requiring careful study to deduce that fact.

I don't like using tail recursion to emulate iteration, for the
simple reason that Common Lisp does not specify that tail recursion
will be optimized to *not* push deeper and deeper on the stack, and
also for the simple reason that *any* iterative algorithm can be
contorted to be emulated via tail-recursion, and *one* example for
the student, any example, the most trivial example the best, is
sufficient to get the point across. It's not necessary to use an
unnecessarily complicated example like this just to show how tail
recursion can emulate iteration.

In either case, there's an obvious re-write I'd prefer. Instead of
requiring the children function to always make a copy of the list
of children before return, I'd define an auxilary function
copy-children which did that, and have a functional variable
cchildren so that the name made it clear to pass the auxilary
function instead of the basic data-field accessor function.

Or I'd write a function called mapappend which worked just like
mapcan except it appended instead of effecting nconc. Then I could
call the basic data-field accessor function directly. That would be
my preferred solution, to avoid horrible bugs when the application
programmer mistakenly passes the wrong function.

So now let me say how I'd teach the tail-recurse-to-emulate-interation
lesson if I were teaching a class: First I'd demonstrate a totally
frivilous use of iteration, to build a copy of an integer by
counting that integer down to zero while another integer is counted
up from zero in parallel:

(defun copy-n-i (n verbose &aux (ncopy 0))
(loop
(when verbose (format t "n=~D ncopy=~D~%" n ncopy))
(cond ((< 0 n) (decf n) (incf ncopy))
(t (return ncopy)))))
(copy-n-i 5 t)
n=5 ncopy=0
n=4 ncopy=1
n=3 ncopy=2
n=2 ncopy=3
n=1 ncopy=4
n=0 ncopy=5
5
(copy-n-i 947 nil)
947

Next I'd show how to do exactly the same algorithm via tail-recursion:

(defun copy-n-r (n &optional (ncopy 0))
(if (< 0 n) (copy-n-r (- n 1) (+ ncopy 1))
ncopy))
(trace copy-n-r)
(copy-n-r 5)
0: (COPY-N-R 5)
1: (COPY-N-R 4 1)
2: (COPY-N-R 3 2)
3: (COPY-N-R 2 3)
4: (COPY-N-R 1 4)
5: (COPY-N-R 0 5)
5: COPY-N-R returned 5
4: COPY-N-R returned 5
3: COPY-N-R returned 5
2: COPY-N-R returned 5
1: COPY-N-R returned 5
0: COPY-N-R returned 5
5

Next I'd assign a task of building a list of length n, every
element NIL, both iteratively and recursively, using only CONS to
do the building, but using (decf n) in the iterative algorithm and
(- n 1) in the recursive algorithm just as in the above example.
The functions should be named make-nil-list-i and make-nil-list-r
respectively.

I'd provide two test benches like this:

(make-nil-list-i 5 t)
(trace make-nil-list-r)
(make-nil-list-r 5)

(untrace make-nil-list-r)
(setq *gc-verbose* nil)
(loop for exp from 0 upto 500 do
(format t "~&** exp=~D " exp) (finish-output)
(let ((pwr (expt 2 exp)))
(format t "pwr=~D " pwr) (finish-output)
(prog (time0 ires rres len time9)
(format t "~& iterative...") (finish-output)
(setq time0 (get-universal-time))
(setq ires (make-nil-list-i pwr nil))
(setq time9 (get-universal-time))
(format t "~D seconds, " (- time9 time0)) (finish-output)
(setq len (length ires))
(if (= pwr len) (format t "correct.~%")
(error "Wrong!! Length should be ~D but is actually ~D" pwr len))
(format t "~& recursive...") (finish-output)
(setq time0 (get-universal-time))
(setq rres (make-nil-list-r pwr nil))
(setq time9 (get-universal-time))
(format t "~D seconds, " (- time9 time0)) (finish-output)
(setq len (length rres))
(if (= pwr len) (format t "correct.~%")
(error "Wrong!! Length should be ~D but is actually ~D" pwr len))
)
)
(sleep 0.3))

I'd expect the student to write code somewhat like this:
(defun make-nil-list-i (n verbose &aux (list nil))
(loop
(when verbose (format t "n=~D list=~S~%" n list))
(cond ((< 0 n) (decf n) (setq list (cons nil list)))
(t (return list)))))
Or maybe NCONC the new element at the end (shows as really really slow
on second benchmark test, but maybe that's the best way to learn).
Or maybe use APPEND instead of NCONS.
Or mabye CONS at start of the list and also NREVERSE before return
to be flexible code anticipating that I might next want the
elements to be the index rather than always NIL.
(defun make-nil-list-r (n &optional (list nil))
(if (< 0 n) (make-nil-list-r (- n 1) (cons nil list))
list))

By the way, running the second benchmark test with the sample code
I showed in CMUCL on my ISP's unix shell account gives in part:

** exp=17 pwr=131072
iterative...3 seconds, correct.
recursive...5 seconds, correct.
** exp=18 pwr=262144
iterative...5 seconds, correct.
recursive...6 seconds, correct.
** exp=19 pwr=524288
iterative...9 seconds, correct.
recursive...18 seconds, correct.
** exp=20 pwr=1048576
iterative...23 seconds, correct.
recursive...27 seconds, correct.
** exp=21 pwr=2097152
iterative...51 seconds, correct.
recursive...106 seconds, correct.
** exp=22 pwr=4194304
iterative...103 seconds, correct.
recursive...151 seconds, correct.
** exp=23 pwr=8388608
iterative...177 seconds, correct.
recursive...330 seconds, correct.

In XLISP it doesn't work at all because DECF isn't defined.
So I defined it using code that came in source form with the download.
Also *gc-verbose* isn't defined, so I skipped that step.
But then:
error: unbound variable - exp
which presumably means they don't have the new LOOP macro, or it's
broken. So I'll change the LOOP a little bit to make it run with
the old CL1 version ... but now I get:
error: unbound function - finish-output
so I commented out all those calls, but now I get:
error: unbound function - get-universal-time
And neither of the common-lisp files have a definition for it.
I give up! XLISP is useless!!
I wish there were a halfway decent free Common Lisp for Mac system 7.5.5
.

Relevant Pages

  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: Software bugs arent inevitable
    ... >> resource-requirement differences between iteration and recursion can be ... make the difference between an elegant solution that runs like a lame duck ... floats have a finite precision will cause that algorithm to give incorrect ...
    (comp.lang.python)
  • Re: Why is recursion so slow?
    ... etc but wow how can it be THAT much slower for computing fibonacci- ... The comparison below has nothing to do with recursion versus iteration. ... O, algorithm with a linear, O, algorithm. ...
    (comp.lang.python)
  • Re: newbie question: recursion algorithm and iterative algorithm
    ... > "In addition he says that every recursion algorithm can be translated ... Or the existance is proved but transform ... Good compilers often transform tail recursion into iteration. ...
    (comp.lang.prolog)
  • Re: Simple recursive functions in Lisp
    ... (labels ((rev (lst acc) ... becomes a loop variable. ... to the naive car/cdr recursion). ... Another way to express Graham's algorithm is iteration. ...
    (comp.lang.lisp)