On Sat, Feb 8, 2025 at 10:16 AM Alexander Burger <picolisp@software-lab.de>
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))
1000000
5.249 sec
# Tail call
: (benchFun bstSearchTco (** 2 23))
1000000
4.998 sec
# Iterative
: (benchFun bstSearchIter (** 2 23))
1000000
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 1000000
(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)) ) ) )
