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:picolisp@software-lab.de?subject=Unsubscribe
How do I distinguish a list from cons pair?
Is there a way to distinguish a list from a cons pair? The 'pair' function does not seem to do what I want. : (pair (cons 1 2)) -> (1 . 2) : (pair (list 1 2)) -> (1 2) : (pair (list 1 (2 3))) -> (1 (2 3)) : (pair (cons 1 (2 3))) -> (1 2 3) I would like to be able to distinguish the cons pair structure from 'list' /Lindsay : (view (cons 1 2)) +-- 1 | 2 : (view (list 1 2)) +-- 1 | +-- 2 : (view (cons 1 (2 3))) +-- 1 | +-- 2 | +-- 3 : (view (list 1 (2 3))) +-- 1 | +---+-- 2 | +-- 3 >
Re: How do I distinguish a list from cons pair?
Hey, I'm curious myself honestly. Lists are kind of a virtual type, it's just a bunch of cons cells in a sequencial pattern. I think you'd need to write your own function that walks the list to see if its proper or improper (ends with non-nil). Best regards, Geri On Wed, Feb 12, 2025, 08:28 Lindsay Lawrence wrote: > Is there a way to distinguish a list from a cons pair? > > The 'pair' function does not seem to do what I want. > > : (pair (cons 1 2)) > -> (1 . 2) > : (pair (list 1 2)) > -> (1 2) > : (pair (list 1 (2 3))) > -> (1 (2 3)) > : (pair (cons 1 (2 3))) > -> (1 2 3) > > I would like to be able to distinguish the cons pair structure from 'list' > > /Lindsay > > : (view (cons 1 2)) > +-- 1 > | > 2 > > : (view (list 1 2)) > +-- 1 > | > +-- 2 > > : (view (cons 1 (2 3))) > +-- 1 > | > +-- 2 > | > +-- 3 > > : (view (list 1 (2 3))) > +-- 1 > | > +---+-- 2 > | > +-- 3 > >>
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 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:picolisp@software-lab.de?subject=Unsubscribe
Re: How do I distinguish a list from cons pair?
On Tue, Feb 11, 2025 at 10:16:14PM -0800, Lindsay Lawrence wrote: > Is there a way to distinguish a list from a cons pair? > > The 'pair' function does not seem to do what I want. It depends on how you define a list. 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. I would also call (1 . (2 . 3)) # (1 2 . 3) a list. BTW, 'fin' can be used to distinguish them: : (fin (1 2)) -> NIL : (fin (1 2 . 3)) -> 3 > I would like to be able to distinguish the cons pair structure from 'list' So perhaps : (lst? (cdr Pair)) ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: How do I distinguish a list from cons pair?
On Wed, Feb 12, 2025 at 08:31:03AM +0200, GB wrote: > Lists are kind of a virtual type, it's just a bunch of cons cells in a > sequencial pattern. Exactly. > I think you'd need to write your own function that walks the list to see if > its proper or improper (ends with non-nil). Right. 'fin' does this though. ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
