Re: How do I distinguish a list from cons pair?
On Tue, Feb 11, 2025 at 11:38 PM Alexander Burger wrote: > I would say it is a cell with a non-NIL and non-atomic CDR, then (1 . 2) > is not a list but > >(1 . NIL) # (1) > > or > >(1 . (2 . NIL)) # (1 2) > > is. > > 👍 BTW, 'fin' can be used to distinguish them: > >: (fin (1 2)) >-> NIL >: (fin (1 2 . 3)) >-> 3 > > 'fin' may be the function I am looking for. I will have to play with it a bit and probably rethink my data structure. I was trying to 'rotate' a tree structure and for the purpose of 'set' I needed to distinguish between (1 . 2) (1 2) (1 . (2 3 4)) (1 (2 3 4)) In the case of the pair, I can't use 'set' to update the cdr and would have to use 'con' and reference the appropriate node. : (lst? (cdr Pair)) > I tried that expression, but the way I was thinking about lists, and trying to use them, didn't give me the results I expected. : (lst? (cdr (1 . 2))) -> NIL : (lst? (cdr (1 2))) -> T : (lst? (cdr (1 . (2 3 4 -> T : (lst? (cdr (1 (2 3 4 -> T /Lindsay
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:picolisp@software-lab.de?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 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:picolisp@software-lab.de?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
