Marco Baringer  <mb@bese.it> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) writes:
| > But note that even in trampolined CPS form it is not necessary to use
| > THROW (which, when deeply nested, might be quite slow) to achieve the
| > desired result. Consider this slight rewrite [which, with no THROW,
| > allows replacing #'TOPLEVEL-K with #'IDENTITY]:
| 
| 1) this means that the trampolined function can never return a function. 
+---------------

Well, you *can*, but it takes a small hack to the loop and the
reintroduction of a top-level value function to use instead of
#'IDENTITY, and it also helps to change the API for RUN-TRAMP
slightly, something like this, perhaps:

    ;;; RUN-TRAMP takes a function of one argument which calls the
    ;;; desired target function with the given argument as a continuation,
    ;;; e.g., (lambda (k) (foo arg1 arg2 ... k))
    (defun run-tramp (func)
      (let ((cookie nil))
	(flet ((top-k (v) (setf cookie v) nil))
	  (loop for f = (funcall func #'top-k) then (funcall f)   
		while (functionp f)
	    finally (return (or cookie f))))))

[Note: The (RETURN (OR COOKIE F)) is unnecessary; it could just be
(RETURN COOKIE). I used the overly-defensive OR in case some called
function directly returned a non-function value instead of a trampoline
continuation.]

The function LEN-TRAMP remains the same as in my last reply, but
instead of starting it like this:

    (run-tramp (lambda () (len-tramp '(a b c d e) #'identity)))

now you call it like this:

    > (run-tramp (lambda (k) (len-tramp '(a b c d e) k)))
      0: (LEN-TRAMP (A B C D E) #<Interpreted Function TOP-K {48536249}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853AF89}>
      0: (LEN-TRAMP (B C D E) #<Interpreted Function "LAMBDA (LIST K)" {4853B571}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853BEE9}>
      0: (LEN-TRAMP (C D E) #<Interpreted Function "LAMBDA (LIST K)" {4853C4B1}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853CE09}>
      0: (LEN-TRAMP (D E) #<Interpreted Function "LAMBDA (LIST K)" {4853D3F1}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853DD29}>
      0: (LEN-TRAMP (E) #<Interpreted Function "LAMBDA (LIST K)" {4853E2F1}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853EC09}>
      0: (LEN-TRAMP NIL #<Interpreted Function "LAMBDA (LIST K)" {4853F1D1}>)
      0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853FAA1}>
    5
    > 

Now if you want to return a function, you can do like this [with apologies
for the continual wrapping & unwrapping of CONSTANTLY forms, just to get
a function result, but it does let the code resemble LEN-TRAMP's]:

    > (defun func-val-tramp (count k)
	(if (zerop count)
	  (lambda () (funcall k (constantly 0)))
	  (lambda ()
	    (func-val-tramp (1- count)
			    (lambda (v)
			      (funcall k (constantly (1+ (funcall v)))))))))
    > (trace func-val-tramp)
    > (run-tramp (lambda (k) (func-val-tramp 3 k)))
      0: (FUNC-VAL-TRAMP 3 #<Interpreted Function TOP-K {485E5B41}>)
      0: FUNC-VAL-TRAMP returned
	   #<Interpreted Function "LAMBDA (COUNT K)" {485EA751}>
      0: (FUNC-VAL-TRAMP 2 #<Interpreted Function "LAMBDA (COUNT K)" {485EAD51}>)
      0: FUNC-VAL-TRAMP returned
	   #<Interpreted Function "LAMBDA (COUNT K)" {485EB631}>
      0: (FUNC-VAL-TRAMP 1 #<Interpreted Function "LAMBDA (COUNT K)" {485EBC31}>)
      0: FUNC-VAL-TRAMP returned
	   #<Interpreted Function "LAMBDA (COUNT K)" {485EC501}>
      0: (FUNC-VAL-TRAMP 0 #<Interpreted Function "LAMBDA (COUNT K)" {485ECB01}>)
      0: FUNC-VAL-TRAMP returned
	   #<Interpreted Function "LAMBDA (COUNT K)" {485ED3F1}>
    #<Closure Over Function "DEFUN CONSTANTLY" {485EDB49}>
    >

So we got a function as a result, o.k.? Now let's call it and see what
the real result is:

    > (funcall *)

    3
    >

+---------------
| 2) the throw will never have to search more than two stack frames
|    (shortening the stack is the whole point of trampolining).
| 
| afaict. am i missing something?
+---------------

Not really. It's just a difference of perception in the cost of THROW
(which I assume to be high, even across a small number of stack frames)
versus an extra FUNCALL or two.


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607