Re: Tail call optimization
On Fri, Feb 14, 2025 at 8:58 AM Alexander Burger wrote: > The old algorithm needed for 10 digits 8369 sec (02:19 h), the new > one (I use the coroutine version) just 726 sec. That's about 12 times as > fast! > 👍 👍 :) /Lindsay
Re: Tail call optimization
> > How about a coroutine version? > > Neat! You have options over what to do with the digits with the coroutine. And negligible difference in performance, if it matters, either. I didn't expect that. /Lindsay : (bench (out "pi-digits.1.txt" (makePi 1))) 3.150 sec -> NIL : (bench (out "pi-digits.1.txt" (prinPi 1))) 3.166 sec -> NIL : (bench (out "pi-digits.1.txt" (makePi 2))) 13.553 sec -> NIL : (bench (out "pi-digits.1.txt" (prinPi 2))) 13.811 sec -> NIL : (bench (out "pi-digits.1.txt" (prinPi 5))) 97.809 sec -> NIL : (bench (out "pi-digits.1.txt" (makePi 5))) 98.387 sec -> NIL :
Re: Tail call optimization
On Fri, Feb 14, 2025 at 05:21:46PM +0100, Alexander Burger wrote: > Wow, that's cool! I'll measure it now :) The old algorithm needed for 10 digits 8369 sec (02:19 h), the new one (I use the coroutine version) just 726 sec. That's about 12 times as fast! ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Fri, Feb 14, 2025 at 07:30:59AM -0800, Lindsay Lawrence wrote: > On Thu, Feb 13, 2025 at 9:49 PM Lindsay Lawrence < > [email protected]> wrote: > > > > A bit of searching came up with the paper with the haskell version > > > > https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf > > > > Interestingly enough there is another version of PI in there, recursive, > > based on the Gosper series, > > that a faster... although it is based on a conjecture they haven't proven > > in that paper. > > > > The picolisp version of that one is below ('tco' is a nice fit for it as > > well!) > > > > There was an error in the variable scoping of the function I posted in > previous email. Here is the corrected version > > (de makePi (N) > (let (G 1 R 180 S 60 I 2) >(tco (G R S I N) > (let > (U (* 3 (+ (* 3 I) 1) (+ (* 3 I) 2) ) > Y (/ (+ (* G (- (* 27 I) 12)) (* 5 R) ) (* 5 S) ) ) > (prin Y) > (if (or (not N) (gt0 N)) > (tc >(* 10 G I (- (* 2 I) 1)) >(* 10 U (- (+ (* G (- (* 5 I) 2)) R) (* Y S) ) ) >(* S U) >(+ I 1) >(dec N) ) ) ) ) )) Wow, that's cool! I'll measure it now :) How about a coroutine version? (de pi (Flg) (if Flg (co 'pi (yield 3) (yield ".") (let (G 60 R 13440 S 10080 I 3) (tco (G R S I) (let (U (* 3 (inc (* 3 I)) (+ (* 3 I) 2)) Y (/ (+ (* G (- (* 27 I) 12)) (* 5 R) ) (* 5 S)) ) (yield Y) (tc (* 10 G I (dec (* 2 I))) (* 10 U (- (+ (* G (- (* 5 I) 2)) R) (* Y S ))) (* S U) (inc I) ) ) ) ) ) (co 'pi) ) ) (de prinPi (N) (do N (prin (pi T)) ) (pi) (prinl) ) ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Thu, Feb 13, 2025 at 9:49 PM Lindsay Lawrence < [email protected]> wrote: > A bit of searching came up with the paper with the haskell version > > https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf > > Interestingly enough there is another version of PI in there, recursive, > based on the Gosper series, > that a faster... although it is based on a conjecture they haven't proven > in that paper. > > The picolisp version of that one is below ('tco' is a nice fit for it as > well!) > There was an error in the variable scoping of the function I posted in previous email. Here is the corrected version (de makePi (N) (let (G 1 R 180 S 60 I 2) (tco (G R S I N) (let (U (* 3 (+ (* 3 I) 1) (+ (* 3 I) 2) ) Y (/ (+ (* G (- (* 27 I) 12)) (* 5 R) ) (* 5 S) ) ) (prin Y) (if (or (not N) (gt0 N)) (tc (* 10 G I (- (* 2 I) 1)) (* 10 U (- (+ (* G (- (* 5 I) 2)) R) (* Y S) ) ) (* S U) (+ I 1) (dec N) ) ) ) ) )) /Lindsay
Re: Tail call optimization
On Thu, Feb 13, 2025 at 9:37 AM Alexander Burger
wrote:
> On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote:
> > I think it is also a good a test/example of picolisp's support for
> bignums.
>
> Indeed. The numbers in the 'E' environment get quite big. After ten
> thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748
> digits.
>
> I verified that the first hundred thousand ouput digits are correct.
>
A bit of searching came up with the paper with the haskell version
https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Interestingly enough there is another version of PI in there, recursive,
based on the Gosper series,
that a faster... although it is based on a conjecture they haven't proven
in that paper.
The picolisp version of that one is below ('tco' is a nice fit for it as
well!)
(de piDigits (N)
(default Q 1 R 180 S 60 I 2)
(tco
(Q R S I N)
(let
(U
(*
3
(+ (* 3 I) 1)
(+ (* 3 I) 2) )
Y
(/
(+
(* Q (- (* 27 I) 12))
(* 5 R) )
(* 5 S) ) )
(prin Y)
(if (or (not N) (gt0 N))
(tc
(* 10 Q I (- (* 2 I) 1))
(*
10
U
(-
(+ (* Q (- (* 5 I) 2)) R)
(* Y S) ) )
(* S U)
(+ I 1)
(dec N) ) ) ) ) )
On my machine that outputs digits of PI like below
: (bench (out "pi-digits.1.txt" (piDigits 1)))
8.751 sec
-> NIL
: (bench (out "pi-digits.1.txt" (piDigits 5)))
117.745 sec
-> NIL
: (bench (out "pi-digits.1.txt" (piDigits 10)))
613.212 sec
-> NIL
/Lindsay
Re: Tail call optimization
On Thu, Feb 13, 2025 at 9:37 AM Alexander Burger wrote: > On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote: > > I think it is also a good a test/example of picolisp's support for > bignums. > > Indeed. The numbers in the 'E' environment get quite big. After ten > thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748 > digits. > > I verified that the first hundred thousand ouput digits are correct. > > Super. I learned a new (to me) picolisp function from the updated code in your other email, 'env', as well as the utility of 'prog1'. It takes a while to get to 100K on my machine! Thanks! /Lindsay
Re: Tail call optimization
On Thu, Feb 13, 2025 at 08:50:16AM -0800, Lindsay Lawrence wrote: > I think it is also a good a test/example of picolisp's support for bignums. Indeed. The numbers in the 'E' environment get quite big. After ten thousand digits of PI, 'S' and 'Q' have 145746 digits and 'R' has 145748 digits. I verified that the first hundred thousand ouput digits are correct. ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
> > > > Sorry again for the confusion! > > 👍 I think it is also a good a test/example of picolisp's support for bignums. It could be a fun exercise to implement a version of this with one of the other Pi algorithms that discards already computed digits so it could essentially just churn out digits of pi as long as it existed without any loss of performance. /Lindsay
Re: Tail call optimization
On Thu, Feb 13, 2025 at 07:38:10AM +0100, Alexander Burger wrote: > When I built the tco version yesterday, I experimended with both > versions, and somehow the 'M' code was lost :( OK, I will settle with this version: # Print next digit of PI (de digit (Env) (job Env (tco (Q R S K N L) (if (>= (- (+ R (* 4 Q)) S) (* N S)) (tc (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) ) (prog1 N (let M (- (/ (* 10 (+ R (* 3 Q))) S) (* 10 N)) (setq Q (* 10 Q) R (* 10 (- R (* N S))) N M) ) ) ) ) ) # Print 'N' or all digits of PI (de pi (N) (let E (env 'Q 1 'R 0 'S 1 'K 1 'N 3 'L 3) (prin (digit E) ".") (do (or N T) (prin (digit E)) (flush) ) ) (prinl) ) The 'job' environment is factored out of 'digit' so that 'pi' can be restarted like: $ ./pil misc/pi.l + : (pi 7) 3.1415926 -> NIL : (pi 30) 3.141592653589793238462643383279 -> NIL : (pi) 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669... ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
Oops, sorry! Yesterday evening I noticed that I messed it up, but was too tired to dig into it. On Wed, Feb 12, 2025 at 02:28:25PM -0800, Lindsay Lawrence wrote: > Question: Without fully understanding the algorithm, it seems N is the next > digit to return... Right. I posted the original 'while' version many years ago in Rosetta Code: https://rosettacode.org/wiki/Pi#PicoLisp I translated it from the Haskell version, also without fully understanding the algorithm :) > But why write that as (swap 'N M)? M is NIL if not defined but otherwise > may have some other random value which, if set, does cause results to go > astray. Exactly! I noticed yesterday that 'lint' complained about the 'M'. When I built the tco version yesterday, I experimended with both versions, and somehow the 'M' code was lost :( But very very strange that it seems to output the correct digits as long as 'M' is NIL! This is the correct original version: (de piDigit () (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) (while (>= (- (+ R (* 4 Q)) S) (* N S)) (mapc set '(Q R S K N L) (list (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) ) ) (prog1 N (let M (- (/ (* 10 (+ R (* 3 Q))) S) (* 10 N)) (setq Q (* 10 Q) R (* 10 (- R (* N S))) N M) ) ) ) ) and this the tco version: (de piDigit () (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) (tco (Q R S K N L) (if (>= (- (+ R (* 4 Q)) S) (* N S)) (tc (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) ) (prog1 N (let M (- (/ (* 10 (+ R (* 3 Q))) S) (* 10 N)) (setq Q (* 10 Q) R (* 10 (- R (* N S))) N M) ) ) ) ) ) Sorry again for the confusion! ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
> Hmm, it seems that I begin to detect some advantages in tco/tc :) > > For example, in pil64 I had a function calculating the digits of pi ad > infinitum: > ># Print next digit of PI >(de piDigit () > (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) > (while (>= (- (+ R (* 4 Q)) S) (* N S)) > (mapc set '(Q R S K N L) >(list > (* Q K) > (* L (+ R (* 2 Q))) > (* S L) > (inc K) > (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) > (+ 2 L) ) ) ) > (setq > Q (* 10 Q) > R (* 10 (- R (* N S))) ) > (swap 'N M) ) ) > ># Print all digits of PI >(prin (piDigit) ".") >(loop > (prin (piDigit)) > (flush) ) > > We see, it has a 'while' loop using 'set' and 'list' to get an atomic > assignment of the six variables. > > > Now, here tco/tc come in handy, as it *is* a loop with atomic > assignment! :) > ># Print next digit of PI >(de piDigit () > (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) > (tco (Q R S K N L) > (if (>= (- (+ R (* 4 Q)) S) (* N S)) >(tc > (* Q K) > (* L (+ R (* 2 Q))) > (* S L) > (inc K) > (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) > (+ 2 L) ) >(setq > Q (* 10 Q) > R (* 10 (- R (* N S))) ) >(swap 'N M) ) ) ) ) > ># Print all digits of PI >(prin (piDigit) ".") >(loop > (prin (piDigit)) > (flush) ) Very cool! Comparing the two functions is worth a bit of study. The tco version does look a lot cleaner. The application of mapc for assignment in the first function is very neat. I had not thought of that use. Question: Without fully understanding the algorithm, it seems N is the next digit to return... But why write that as (swap 'N M)? M is NIL if not defined but otherwise may have some other random value which, if set, does cause results to go astray. Thanks for sharing this code. /Lindsay
Re: Tail call optimization
On Wed, Feb 12, 2025 at 08:14:04AM +0100, Alexander Burger wrote: > If a problem is a linear operation, like traversing a list, a loop is > more natural for me. For traversing a tree, recursion is better of > course. Hmm, it seems that I begin to detect some advantages in tco/tc :) For example, in pil64 I had a function calculating the digits of pi ad infinitum: # Print next digit of PI (de piDigit () (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) (while (>= (- (+ R (* 4 Q)) S) (* N S)) (mapc set '(Q R S K N L) (list (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) ) ) (setq Q (* 10 Q) R (* 10 (- R (* N S))) ) (swap 'N M) ) ) # Print all digits of PI (prin (piDigit) ".") (loop (prin (piDigit)) (flush) ) We see, it has a 'while' loop using 'set' and 'list' to get an atomic assignment of the six variables. Now, here tco/tc come in handy, as it *is* a loop with atomic assignment! :) # Print next digit of PI (de piDigit () (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3)) (tco (Q R S K N L) (if (>= (- (+ R (* 4 Q)) S) (* N S)) (tc (* Q K) (* L (+ R (* 2 Q))) (* S L) (inc K) (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L)) (+ 2 L) ) (setq Q (* 10 Q) R (* 10 (- R (* N S))) ) (swap 'N M) ) ) ) ) # Print all digits of PI (prin (piDigit) ".") (loop (prin (piDigit)) (flush) ) Looks more clean! 3.14159265358979323846264338327950288419716939937510582097494459230781640... ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Tue, Feb 11, 2025 at 11:25 PM Alexander Burger wrote: > > If a problem is a linear operation, like traversing a list, a loop is > more natural for me. For traversing a tree, recursion is better of > course. > > Thanks! >(de fiboSwap (N) > (let (A 0 B 1) > (do N > (swap 'B (+ (swap 'A B) B)) ) ) ) > > That is really cool! Something to keep in mind. I took a moment to rewrite the tco versions of the swap, mtf, mft functions I had using my newly realized understanding of nth, con, conc, insert (code below). Shorter, simpler, and much! faster on large lists. : (swappXchg (1 . 7) (1 2 3 4 5 6 7 8 9)) # Swap -> (7 2 3 4 5 6 1 8 9) : (mtfConc (1 2 3 4 5 6 7 8 9) 7) # Move to front -> (7 1 2 3 4 5 6 8 9) : (mftConc (1 2 3 4 5 6 7 8 9) 7) # Move from top -> (2 3 4 5 6 7 1 8 9) /Lindsay # Swap two elements in a list (de swappXchg (P L) (when (and (pair P) (lst? L)) (ifn (> (cdr P) (car P)) (setq P (cons (cdr P) (car P))) ) (let (Lst L Lhs (car P) Rhs (cdr P) LhsN (nth L Lhs) RhsN (nth LhsN (inc (- Rhs Lhs))) ) (when (and LhsN RhsN) (xchg LhsN RhsN)) L ) ) ) # Move from top (de mftConc (X N) (cond ((and (> N 1) (lst? X)) (let (Elt (cons (car X)) Lhs (head (dec N) (cdr X)) Rhs (cdr (nth X N)) ) (con Elt Rhs) (conc Lhs Elt) Lhs ) ) (T X) ) ) (de mftInsert (X N) (cond ((and (> N 1) (lst? X)) (insert N (cdr X) (car X))) (T X))) # Move to Front (de mtfConc (X N) (cond ((and (> N 1) (lst? X)) (let (Lhs (head (dec N) X) Rhs (cdr (nth X (dec N))) Elt (cons (car Rhs)) ) (ifn Rhs X (con Elt Lhs) (conc Elt (cdr Rhs)) Elt ) ) ) (T X) ) )
Re: Tail call optimization
On Tue, Feb 11, 2025 at 02:41:01PM -0800, Lindsay Lawrence wrote: > > I usually approach such tasks with loops, with a rather > > different mental model. > > > That is interesting! Can you say more about your mental model? > I am often surprised by how often I end up with recursive solutions when > hacking on a particular problem in picolisp. If a problem is a linear operation, like traversing a list, a loop is more natural for me. For traversing a tree, recursion is better of course. One of the first examples in SICP is (de sqrt-iter (Guess X) (if (good-enough? Guess X) Guess (sqrt-iter (improve Guess X) X) ) ) I would never get the idea to write it that way. Instead, I would (de sqrt-iter (Guess X) (until (good-enough? Guess X) (setq Guess (improve Guess X)) ) Guess ) > Concerning swap, we could for completeness mention that there is also > > the built-in 'xchg' function: > > > >: (let L (1 2 3 4 5 6 7) > > (xchg (nth L 3) (nth L 5)) > > L ) > >-> (1 2 5 4 3 6 7) > > > > The swap function I implemented was an exercise after working with some > particularly large lists. Yes, I thought so. > > I did find after writing that code that there is xchg as well as a few > other useful functions in this vein in picolisp...'insert' and even 'swap'! Yeah. 'swap' is btw useful to make an iterative version of our good old fibo function. Instead of (de fibo (N) (if (>= 2 N) 1 (+ (fibo (dec N)) (fibo (- N 2))) ) ) or (de fiboTco (N) (let (A 0 B 1) (tco (N A B) (if (=0 N) A (tc (dec N) B (+ A B)) ) ) ) ) we can write (de fiboSwap (N) (let (A 0 B 1) (do N (swap 'B (+ (swap 'A B) B)) ) ) ) :) > I sometimes don't realize (at first) when a particular function returns a > 'pointer' into a list, vs a 'value'. I see, these are valid terms. The reference calls such a 'pointer' a 'var'. > A slight change to your little function achieves the single pass > performance...in far less code than the function I shared! > > : (let (L (1 2 3 4 5 6 7 8 9) > lhs (nth L 3) > rhs (nth lhs (inc (- 5 3 > (xchg lhs rhs) L) > -> (1 2 5 4 3 6 7 8 9) Indeed, this is better for very long lists, as the second traversal is shorter. Note, however, that for shorter lists (less than perhaps a hundred cells), it is in fact slower because of the overhead for the additonal variable bindings and the function calls 'inc' and '-'. ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
> I usually approach such tasks with loops, with a rather > different mental model. > > That is interesting! Can you say more about your mental model? I am often surprised by how often I end up with recursive solutions when hacking on a particular problem in picolisp. Concerning swap, we could for completeness mention that there is also > the built-in 'xchg' function: > >: (let L (1 2 3 4 5 6 7) > (xchg (nth L 3) (nth L 5)) > L ) >-> (1 2 5 4 3 6 7) > The swap function I implemented was an exercise after working with some particularly large lists. I did find after writing that code that there is xchg as well as a few other useful functions in this vein in picolisp...'insert' and even 'swap'! I sometimes don't realize (at first) when a particular function returns a 'pointer' into a list, vs a 'value'. 'nth' and 'put', in particular, are far more powerful than I initially thought. I wanted to do the swap action in a single pass (and it was a good exercise in understanding destructive list manipulation a bit better). A slight change to your little function achieves the single pass performance...in far less code than the function I shared! : (let (L (1 2 3 4 5 6 7 8 9) lhs (nth L 3) rhs (nth lhs (inc (- 5 3 (xchg lhs rhs) L) -> (1 2 5 4 3 6 7 8 9) I have bottlenecked performance of my code in the past by not remembering some functions have to necessarily traverse the list to do their work. e.g. the recent json parser I implemented was calling 'length' at various points in its process and had very poor performance over large sets until I realized that. Thanks Alex! As always, I appreciate the shared insight /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 10:18:41PM -0800, Lindsay Lawrence wrote: > I realized several existing recursive functions I use were trivially > convertible and are now able to work with much larger lists. > > I put a few examples here: swap, mtf (move to front), mft (move from top) > > https://github.com/thinknlive/picolisp-lisp-basics/blob/master/tco.l Thanks! It is very interesting for me to see TCO in such elaborated examples. I usually approach such tasks with loops, with a rather different mental model. Concerning swap, we could for completeness mention that there is also the built-in 'xchg' function: : (let L (1 2 3 4 5 6 7) (xchg (nth L 3) (nth L 5)) L ) -> (1 2 5 4 3 6 7) ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Mon, Feb 10, 2025 at 2:49 AM Alexander Burger wrote: > > I'd like to point out, however, that recursion and tail call > optimization are not fully equivalent. We always need to keep that in > mind! > > The original idea of TCO (not the 'tco' function in PicoLisp) is to > avoid that calling the very last function in a function does > > ... > PicoLisp is an interpreter, and performing such code modifications would > be extremely inefficient. > > But for PicoLisp (I think Scheme doesn't even address such issues), > there are also other implications. The above example has the call to 'f' > only in the body of a single 'if' expression. But what if you have more > complicated nestings? > > ... Thanks Alex. I appreciate the insight into picolisp's tco given here. I realized several existing recursive functions I use were trivially convertible and are now able to work with much larger lists. I put a few examples here: swap, mtf (move to front), mft (move from top) https://github.com/thinknlive/picolisp-lisp-basics/blob/master/tco.l /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 6:32 AM Alexander Burger wrote: > On Mon, Feb 10, 2025 at 02:06:52PM +0100, Alexander Burger wrote: > > : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) > > 0.038 sec > > -> 0 > > For the records - and to show the absurdity of TCO - this is of course > the same as > > : (let N 99 (bench (until (=0 N) (dec 'N > 0.032 sec > -> 0 > > 👍👍 /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 2:49 AM Alexander Burger wrote: > I'd like to point out, however, that recursion and tail call > optimization are not fully equivalent. We always need to keep that in > mind! > > ... > So what PicoLisp does is first clean up everything, by first *leaving* > all enclosing expressions, and then jumping to the start of the loop. > > ... > If we reduce the example to just a 'finally': > >(de f (N) > (finally (printsp N) > (if (=0 N) > (printsp 'OK) > (f (dec N)) ) ) ) > >: (f 3) >OK 0 1 2 3 -> OK > > Now, if we use 'tco' and 'tc' instead of the recursive call: > >(de f (N) > (tco (N) > (finally (printsp N) > (if (=0 N) >(printsp 'OK) >(tc (dec N)) ) ) ) ) > >: (f 3) >3 2 1 OK 0 -> OK > > the result is completely different! > > Thanks for the insight! This is interesting and really helps my understanding of the mechanics of how tc is implemented in picolisp. /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 02:06:52PM +0100, Alexander Burger wrote: > : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) > 0.038 sec > -> 0 For the records - and to show the absurdity of TCO - this is of course the same as : (let N 99 (bench (until (=0 N) (dec 'N 0.032 sec -> 0 ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Sun, Feb 09, 2025 at 02:13:13PM -0800, Lindsay Lawrence wrote: > It is interesting that I don't see much performance difference between tco > and recur in most cases. The difference is better visible if you avoid as much additional processing as possible, and boil it down to the essential 'recur' and 'tco' calls: : (let N 99 (bench (recur (N) (or (=0 N) (recurse (dec N)) 0.067 sec -> 0 : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) 0.038 sec -> 0 ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Sun, Feb 09, 2025 at 11:32:38PM -0800, Lindsay Lawrence wrote: > In trying to compare tco vs recur for my own use I came up with > the following: > ... Nice examples, thanks a lot! I'd like to point out, however, that recursion and tail call optimization are not fully equivalent. We always need to keep that in mind! The original idea of TCO (not the 'tco' function in PicoLisp) is to avoid that calling the very last function in a function does 1. first push the current address on the stack 2. call that last function 3. pop the return address 4. return from the current function Instead, the code can just *jump* to that last function. This is done by e.g. Scheme, and indeed is faster and avoids growing the stack with each iteration. This optimization is done by the compiler, which modifies the program flow. For the simple case of a single recursive function calling itself: (de f (N) (if (=0 N) (printsp 'OK) (printsp N) (f (dec N)) ) ) : (f 3) 3 2 1 OK -> OK this results in a *loop* and an assignment instead of a real *call*: (de f (N) (loop (T (=0 N) (printsp 'OK)) (printsp N) (setq N (dec N)) ) ) : (f 3) 3 2 1 OK -> OK (for mutually recursive functions it is the same principle) PicoLisp is an interpreter, and performing such code modifications would be extremely inefficient. But for PicoLisp (I think Scheme doesn't even address such issues), there are also other implications. The above example has the call to 'f' only in the body of a single 'if' expression. But what if you have more complicated nestings? Consider this silly but simple example: (de f (N) (finally (printsp N) (out "file" (if (=0 N) (printsp 'OK) (f (dec N)) ) ) ) ) The recursion in the last line properly nests the 'finally' and 'out' calls, closing the output file and executing the 'finally' clause upon each return. We cannot simply jump from the last line of 'f' to the first! It would leave all the output file descriptors open, and never execute any 'finally' clause. So what PicoLisp does is first clean up everything, by first *leaving* all enclosing expressions, and then jumping to the start of the loop. But this results in the above "are not fully equivalent". If we reduce the example to just a 'finally': (de f (N) (finally (printsp N) (if (=0 N) (printsp 'OK) (f (dec N)) ) ) ) : (f 3) OK 0 1 2 3 -> OK Now, if we use 'tco' and 'tc' instead of the recursive call: (de f (N) (tco (N) (finally (printsp N) (if (=0 N) (printsp 'OK) (tc (dec N)) ) ) ) ) : (f 3) 3 2 1 OK 0 -> OK the result is completely different! ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On Sun, Feb 9, 2025 at 11:18 PM Alexander Burger wrote: > Exactly. 'tco' does not make much difference in total running time. It > is all about stack usage. > > Thanks Alex! > Try with a limited stack size: > > : (stack 8 8) # Stack sizes 8 KiB > -> 8 > : (co 'a (yield)) # Start a coroutine to segment the stack > -> NIL > > : (fiboTco 99) > -> 218922995834555169026 > > : (fiboRecur 99) > !? ((N A B) (if (=0 N) A (recurse (dec N) B (+ A B > T -- Stack overflow > ? > Give up: No stack > > Nice example. 'stack' is yet another function I haven't fully appreciated until recently /Lindsay
Re: Tail call optimization
In trying to compare tco vs recur for my own use I came up with the following: The two functions 'bstInsertTco', 'bstInsertRecur' (see code at end) are identical except for tco,tc and recur,recurse. The repl examples show the degenerate case of inserting an ordered list into a BST without rebalancing, and also inserting random values (more balanced) Speed wise there doesn't seem to be that much difference over recurse. At least for my use case. The difference in resource usage is significant though. A nice optimization and the choice of using it is a great feature in itself. Thanks! /Lindsay # Ordered inserts into BST (the degenerate case) : (off *Tree) (bench (for N (** 2 15) (bstInsertTco '*Tree N))) T 48.250 sec : (off *Tree) (bench (for N (** 2 15) (bstInsertRecur '*Tree N))) T 55.248 sec : (off *Tree) (bench (for N (** 2 16) (bstInsertTco '*Tree N))) T 192.705 sec : (off *Tree) (bench (for N (** 2 16) (bstInsertRecur '*Tree N))) T .. Stack overflow ? Give up: No stack When building from randomized values, there is not much difference in performance (although 'tco' is consistently slightly faster). : (off *Tree) (bench (for N (** 2 14) (bstInsertRecur '*Tree (rand 1 (** 2 32) T 0.053 sec : (let (L (make (bstInOrder link *Tree))) (println (head 3 L) (tail 3 L) (length L) (apply < L))) (975009 1096393 1301832) (4294487248 4294754706 4294841759) 16384 T : (off *Tree) (bench (for N (** 2 14) (bstInsertTco '*Tree (rand 1 (** 2 32) T 0.038 sec : (let (L (make (bstInOrder link *Tree))) (println (head 3 L) (tail 3 L) (length L) (apply < L))) (546090 725497 1200269) (4293939971 4294665037 4294749566) 16384 T # The functions (de bstInsertRecur (Tree Key) (let (TreeE (if (sym? Tree) (eval Tree) Tree)) (ifn (and TreeE (lst? TreeE)) (set Tree (list Key NIL NIL)) (recur (TreeE Key) (when (and (car TreeE) (lst? (car TreeE))) (setq TreeE (car TreeE)) ) (ifn (car TreeE) (set TreeE (list Key NIL NIL)) (unless (= (car TreeE) Key) (if (< (car TreeE) Key) (recurse (cddr TreeE) Key) (recurse (cdr TreeE) Key) ) ) ) ) ) ) ) (de bstInsertTco (Tree Key) (let (TreeE (if (sym? Tree) (eval Tree) Tree)) (ifn (and TreeE (lst? TreeE)) (set Tree (list Key NIL NIL)) (tco (TreeE Key) (when (and (car TreeE) (lst? (car TreeE))) (setq TreeE (car TreeE)) ) (ifn (car TreeE) (set TreeE (list Key NIL NIL)) (unless (= (car TreeE) Key) (if (< (car TreeE) Key) (tc (cddr TreeE) Key) (tc (cdr TreeE) Key) ) ) ) ) ) ) )
Re: Tail call optimization
On Sun, Feb 09, 2025 at 02:13:13PM -0800, Lindsay Lawrence wrote: > It is interesting that I don't see much performance difference between tco > and recur in most cases. > Perhaps the primary difference is their resource usage? Exactly. 'tco' does not make much difference in total running time. It is all about stack usage. Try with a limited stack size: : (stack 8 8) # Stack sizes 8 KiB -> 8 : (co 'a (yield)) # Start a coroutine to segment the stack -> NIL : (fiboTco 99) -> 218922995834555169026 : (fiboRecur 99) !? ((N A B) (if (=0 N) A (recurse (dec N) B (+ A B T -- Stack overflow ? Give up: No stack ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
> > > It is interesting that I don't see much performance difference between tco > and recur in most cases. > Perhaps the primary difference is their resource usage? > > For example, using (mike)'s fibo example and simply replacing tco with > recur (see code at end) > I initially expected (fiboRecur) to have a similar bench profile to (fibo). > > Thinking about this a bit more a bit more, and rewriting the first fibo function in the style of tco and recur (de fibo2 (N A B) (default A 0 B 1) (if (=0 N) A (fibo2 (dec N) B (+ A B)) ) ) We get : (bench (fibo2 37)) 0.000 sec -> 24157817 Which is on par with tco and recur. /Lindsay : (bench (fibo 37)) > 2.779 sec > -> 24157817 > : (bench (fiboRecur 37)) > 0.000 sec > -> 24157817 > : (bench (fiboTco 37)) > 0.000 sec > -> 24157817 > > # The functions used > > (de fibo (N) >(if (>= 2 N) > 1 > (+ (fibo (dec N)) (fibo (- N 2))) ) ) > > (de fiboTco (N) > (let (A 0 B 1) > (tco (N A B) > (if (=0 N) >A >(tc (dec N) B (+ A B)) ) ) ) ) > > (de fiboRecur (N) > (let (A 0 B 1) > (recur (N A B) > (if (=0 N) >A >(recurse (dec N) B (+ A B)) ) ) ) ) > > > >
Re: Tail call optimization
On Sun, Feb 9, 2025 at 2:36 AM Alexander Burger wrote: > > You can also have use cases for both at the same time. > > For example, a tree can be iterated by recursing on the left branches > and then looping on the right branches: > > Noted. A good thing to remember. It is interesting that I don't see much performance difference between tco and recur in most cases. Perhaps the primary difference is their resource usage? For example, using (mike)'s fibo example and simply replacing tco with recur (see code at end) I initially expected (fiboRecur) to have a similar bench profile to (fibo). : (bench (fibo 37)) 2.779 sec -> 24157817 : (bench (fiboRecur 37)) 0.000 sec -> 24157817 : (bench (fiboTco 37)) 0.000 sec -> 24157817 /Lindsay # The functions used above (de fibo (N) (if (>= 2 N) 1 (+ (fibo (dec N)) (fibo (- N 2))) ) ) (de fiboTco (N) (let (A 0 B 1) (tco (N A B) (if (=0 N) A (tc (dec N) B (+ A B)) ) ) ) ) (de fiboRecur (N) (let (A 0 B 1) (recur (N A B) (if (=0 N) A (recurse (dec N) B (+ A B)) ) ) ) )
Re: Tail call optimization
On Sat, Feb 08, 2025 at 07:23:45PM -0800, Lindsay Lawrence wrote: > I gave 'tco' a try. I appreciate the syntax. The similarity with existing > recur syntax > makes it trivial to convert code where tail calls are possible. You can also have use cases for both at the same time. For example, a tree can be iterated by recursing on the left branches and then looping on the right branches: : (use Idx (balance 'Idx (range 1 7)) (recur (Idx) (tco (Idx) (when Idx (printsp (car Idx)) (recurse (cadr Idx)) (tc (cddr Idx)) ) ) ) ) 4 2 1 3 6 5 7 -> NIL ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
Hi Mike, > Here are my results: http://pb1n.de/?ce28f3 > === > $ pil t1.l + > 1.997 sec > 0.000 sec Hmm, function 'f' is not correct: (de f (N) (tco (N A B) (let A 0 B 1 (if (=0 N) A (tc (dec N) B (+ A B)) ) ) ) ) It always returns zero: : (for N 9 (printsp (f N))) 0 0 0 0 0 0 0 0 0 -> 0 Better is: (de f (N) (let (A 0 B 1) (tco (N A B) (if (=0 N) A (tc (dec N) B (+ A B)) ) ) ) ) : (for N 9 (printsp (f N))) 1 1 2 3 5 8 13 21 34 -> 34 : (bench (fibo 36)) 1.224 sec -> 14930352 : (bench (f 36)) 0.000 sec -> 14930352 ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
Hi Lindsay, > In my bench tests below with a bst search, tail call is on par with > iterative and consistently slightly faster then recur. Very nice insights! Thanks a lot! ☺/ A!ex -- UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
Re: Tail call optimization
On 09-02-2025 04:23, Lindsay Lawrence wrote: On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger wrote: PicoLisp now has a kind of tail call optimization! I gave 'tco' a try. I appreciate the syntax. The similarity with existing recur syntax makes it trivial to convert code where tail calls are possible. In my bench tests below with a bst search, tail call is on par with iterative and consistently slightly faster then recur. You just chose an example that is not demonstrative and does not show the power of optimization. The reverse Fibonacci example puts a significant strain on the core itself, calling a func is not for free. fibo(36) ===> ~30M func calls. Here are my results: http://pb1n.de/?ce28f3 === $ pil t1.l + 1.997 sec 0.000 sec ok === (mike)
Re: Tail call optimization
On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger wrote: > PicoLisp now has a kind of tail call optimization! > I gave 'tco' a try. I appreciate the syntax. The similarity with existing recur syntax makes it trivial to convert code where tail calls are possible. In my bench tests below with a bst search, tail call is on par with iterative and consistently slightly faster then recur. Very cool! /Lindsay (P.S. In hindsight, BST search trees not being deeply recursive, the benefit of less resource usage with 'tco' doesn't really apply here) # - # Bench search in a binary search tree (** 2 23) nodes # using recursive, iterative and tail call search functions. (see code for functions used at end) # 1. BST Search for 1M random values in given range that we know are in tree (so 1M matches) # Recursive : (benchFun bstSearch (** 2 23)) 100 5.249 sec # Tail call : (benchFun bstSearchTco (** 2 23)) 100 4.998 sec # Iterative : (benchFun bstSearchIter (** 2 23)) 100 4.872 sec # 2. BST Search for 1M random values in given range, most of which may not be in the tree # Recursive : (benchFun bstSearch (** 2 32)) 1951 2.962 sec # Tail call : (benchFun bstSearchTco (** 2 32)) 2014 2.575 sec # Iterative : (benchFun bstSearchIter (** 2 32)) 1975 2.475 sec # The bench function (calls given bst search function 1M times with random values in given range) (de benchFun (Fun Range) (bench (let (N 0) (do 100 (let (Rnd (rand 1 Range)) (when (Fun '((X) (- X Rnd)) *Tree) (inc 'N) ) ) ) (prinl N) ) ) ) # Create a balanced binary tree with 2^23 (8388608) nodes : (gc 256 256) 256 : (off *List) (bench (setq *List (make (for N (** 2 23) (link N) T # First a list 0.204 sec -> T : (off *Tree) (bench (setq *Tree (bstMake *List))) T # Make BST from list 4.014 sec -> T : (println (head 7 (make (bstInOrder link *Tree T # InOrder traversal, head (1 2 3 4 5 6 7) -> T : (println (tail 7 (make (bstInOrder link *Tree T # InOrder traversal, tail (8388602 8388603 8388604 8388605 8388606 8388607 8388608) -> T # The BST functions : (mapc pp '(bstMake bstInOrder bstSearch bstSearchIter bstSearchTco)) # Recursive (de bstSearch (Fun Tree) (use (Cmp) (recur (Fun Tree) (cond ((or (not Tree) (=0 (setq Cmp (Fun (car Tree ) Tree ) ((lt0 Cmp) (recurse Fun (caddr Tree))) (T (recurse Fun (cadr Tree))) ) ) ) ) # Tail Call (de bstSearchTco (Fun Tree) (use (Cmp) (tco (Fun Tree) (cond ((or (not Tree) (=0 (setq Cmp (Fun (car Tree ) Tree ) ((lt0 Cmp) (tc Fun (caddr Tree))) (T (tc Fun (cadr Tree))) ) ) ) ) # Iterative loop (de bstSearchIter (Fun Tree) (let (Fin NIL Cmp NIL) (while (and Tree (not Fin)) (setq Cmp (Fun (car Tree))) (cond ((=0 Cmp) (setq Fin T)) ((lt0 Cmp) (setq Tree (caddr Tree))) (T (setq Tree (cadr Tree))) ) ) Tree ) ) # Make a BST from ordered list (de bstMake (L) (let (BST '((L Len) (recur (L Len) (when L (let (Mid (/ Len 2) LeftT (cut Mid 'L) Root (++ L) RightT L ) (list Root (recurse LeftT Mid) (recurse RightT (if (gt0 Mid) (dec Mid) Mid)) ) ) ) ) ) ) (BST L (length L)) ) ) # In order BST traversal (de bstInOrder (Fun Tree) (recur (Fun Tree) (when Tree (if (atom Tree) (setq Tree (list Tree))) (recurse Fun (cadr Tree)) (Fun (car Tree)) (recurse Fun (caddr Tree)) ) ) )
Re: Tail call optimization
On 08-02-2025 20:41, Lindsay Lawrence wrote: On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger wrote: PicoLisp now has a kind of tail call optimization! https://software-lab.de/doc/refT.html#tco Hi Alex, I just downloaded the rolling release, why you do not use git for distribution? https://git.envs.net/mpech/pil21 - updates hourly. https://github.com/picolisp/pil21 - unknown update interval. https://nest.pijul.com/tankf33der/picolisp - experimental. (mike)
Re: Tail call optimization
On Sat, Feb 8, 2025 at 11:41 AM Lindsay Lawrence < [email protected]> wrote: > I just downloaded the rolling release, but it seems to be missing > picolisp "bin/picolisp: not found" > Other bits like httpGate etc are missing from bin/ as well. > > Please disregard this previous email. I completely forgot, for a moment, to (cd src; make) /Lindsay
Re: Tail call optimization
On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger wrote: > > PicoLisp now has a kind of tail call optimization! > > https://software-lab.de/doc/refT.html#tco > > Hi Alex, I just downloaded the rolling release, but it seems to be missing picolisp "bin/picolisp: not found" Other bits like httpGate etc are missing from bin/ as well. Regards, Lindsay
Re: Tail call optimization
On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger wrote: > > PicoLisp now has a kind of tail call optimization! > > 👍 👍 Yes! I am looking forward to trying this /Lindsay
