>>> (define (range n) ; returns a list of integers [0 ... n-1]

When i was young, i studied Spice Lisp source code from CMU.
Where are they (Skef, Rob, ...) now?

They almost-always used this idiom of Push, Push, ... Nreverse.

e.g. for (iota N)

(do ((res nil)
(n 100 (1- n))
.....)
((zerop n) ... (nreverse res))

(push n res))

On Tue, 27 Feb 2024 14:56:39 -0800, HenHanna wrote:

> They almost-always used this idiom of Push, Push, ... Nreverse.

Neither are available in Guile, that I can see.

On 2024-02-27, HenHanna <HenHanna@gmail.com> wrote:
>
> >>> (define (range n) ; returns a list of integers [0 ... n-1]
>
> When i was young, i studied Spice Lisp source code from CMU.
> Where are they (Skef, Rob, ...) now?
>
> They almost-always used this idiom of Push, Push, ... Nreverse.

Yes, that idiom is still used in Common Lisp and similar dialects.

There are other tools; here are some.

Common Lisp's loop macro has a collect{ing} clause.

(defun iota (n)
(loop for i from i to n
collect n))

Guy Steele describes, in CLTL2, a module which supports procedural
list construction. See the "Generators and Gatherers" appendix chapter.
This is not in Common Lisp.

(let ((g (gatherer #'collect)))
(next-out g 1)
(next-out g 2)
(next-out g 3)
(result-of g))
-> (1 2 3)

If you use (gatherer #'collect-sum) you will get 6.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

HenHanna <HenHanna@gmail.com> writes:
> They almost-always used this idiom of Push, Push, ... Nreverse.

That is an old school Lisp thing, I think. Scheme tends to frown on
mutation, though it has reverse! which can destructively reverse lists
that you explicitly built using cons.

It was before my time but I think historically, mutation (nreverse,
rplaca/rplacd, etc.) was more important in machines that were starved
for memory. Once memory got bigger, it tended to get used primarily for
caches, images, numerical arrays, and other pointer-free data that
didn't need to be garbage collected, and you didn't have to worry as
much about squeezing the size of your program heap. Another sign of
that change was switching to semispace garbage collectors from intricate
BIBOP or similar schemes.

On 2024-02-28, Paul Rubin <no.email@nospam.invalid> wrote:
> HenHanna <HenHanna@gmail.com> writes:
>> They almost-always used this idiom of Push, Push, ... Nreverse.
>
> That is an old school Lisp thing, I think. Scheme tends to frown on
> mutation, though it has reverse! which can destructively reverse lists
> that you explicitly built using cons.
>
> It was before my time but I think historically, mutation (nreverse,
> rplaca/rplacd, etc.) was more important in machines that were starved
> for memory. Once memory got bigger, it tended to get used primarily for
> caches, images, numerical arrays, and other pointer-free data that
> didn't need to be garbage collected, and you didn't have to worry as
> much about squeezing the size of your program heap. Another sign of
> that change was switching to semispace garbage collectors from intricate
> BIBOP or similar schemes.

If you don't think performance is important, you can use non-destructive
reverse. A list can be built in reverse without mutating a variable,
using tail recursion, and then reversed by constructing a new list,
so that everything is purely funtional.

For instance, here is a tail-recursive mapcar that explicitly passes the
stack of items pushed so far:

(defun map (fn list &optional so-far)
(if (null list)
(reverse so-far)
(map fn
(cdr list)
(cons (funcall fn (car list)) so-far))))

nreverse is used when it is obvious that the cells allocated to the
reversed list have not been shared with the rest of the program.

If those cells are not are not returned to the caller, but only used
as a template for creating a reversed list, those original cells
immediately become garbage.

If the function itself has allocated the reverse list, it can build the
forward list out of those original cells without breaking anything.

Destructive reverse remains a current technique in manipulation of
cons-based lists. It can make a measurable difference on a 3 GHz
machine just like on a 30 MHz machine.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Kaz Kylheku <433-929-6894@kylheku.com> writes:
> For instance, here is a tail-recursive mapcar that explicitly passes the
> stack of items pushed so far:...

That is Lisp, not Scheme. It's possible that some similar looking code
would work in Scheme, but I notice that Scheme seems to distinguish
explicitly consed lists from e.g. quoted lists. reverse! in my
experiments only seems to work on explicitly consed lists.

If the lists are large, I think idiomatically in Scheme one would tend
to use lazy streams (implemented with force and delay) rather than
building and reversing an entire intermediate list. Then you would
generate the mapped elements in order. I expect there are SRFI's for
this but I'm not that familiar with them. Of course in Haskell the
laziness is built into the language.

> Destructive reverse remains a current technique in manipulation of
> cons-based lists. It can make a measurable difference on a 3 GHz
> machine just like on a 30 MHz machine.

As always, justifying such a claim about any particular application
requires benchmarking that application with both reversal methods. The
application might not spend much of its time reversing lists. Even if
it does, the wider implementation is then suspect, because large lists
tend to have poor memory locality. You might look to instead use
generators, or packed vectors, or whatever.

On 2024-02-28, Paul Rubin <no.email@nospam.invalid> wrote:
> Kaz Kylheku <433-929-6894@kylheku.com> writes:
>> For instance, here is a tail-recursive mapcar that explicitly passes the
>> stack of items pushed so far:...
>
> That is Lisp, not Scheme. It's possible that some similar looking code
> would work in Scheme, but I notice that Scheme seems to distinguish
> explicitly consed lists from e.g. quoted lists. reverse! in my
> experiments only seems to work on explicitly consed lists.

In Common Lisp, modifying quoted lists is undefined behavior.

This would not arise in code that builds a dynamic list in reverse.

> If the lists are large, I think idiomatically in Scheme one would tend
> to use lazy streams (implemented with force and delay) rather than
> building and reversing an entire intermediate list. Then you would
> generate the mapped elements in order. I expect there are SRFI's for
> this but I'm not that familiar with them. Of course in Haskell the
> laziness is built into the language.

In a well built Common Lisp implementation, all the library functions
that accumulate lists, like mapcar or the collect clause of Loop and
whatnot, can be reasonably expected not to just push conses onto a stack
and then nreverse. Typically, a tail pointer is maintained and the last
cons cell is mutated to add the next one.

There is a way to do this with a single variable. We accumulate
a circular list, keeping a pointer to its tail cons cell, which points
to the head. For each new item, we make the tail point to a new
cell, such that that cell points to the head. When we are done, we
replace the head pointer with the terminating object, () or nil or
whatever it is in that Lisp dialect.

E.g. in our tail-recursive map, we can pass a context that is the
tail of the circular list:

(defun get-result (tail)
(if tail
(prog1 (cdr tail) ;; (cdr tail) is the head we are returning
(rplacd tail nil)))) ;; clobbered with nil to terminate list

(defun collect (tail item)
(if tail
;; non-empty case: add into circular list after tail
(let* ((head (cdr tail))
(ntail (cons item head)))
(rplacd tail ntail)
ntail))
;; empty case: create new head node, pointing to itself
(let ((ntail (cons item nil)))
(rplacd ntail ntail)
ntail))

(defun map (fn list &optional tail)
(if (null list)
(get-result tail)
(map fn
(cdr list)
(collect tail (funcall fn (car list))))))

If we write:

(defun get-result (x) (reverse x))
(defun collect (x y) (cons y x))

we get the original implementation.

>> Destructive reverse remains a current technique in manipulation of
>> cons-based lists. It can make a measurable difference on a 3 GHz
>> machine just like on a 30 MHz machine.
>
> As always, justifying such a claim about any particular application
> requires benchmarking that application with both reversal methods. The
> application might not spend much of its time reversing lists.

This is tricky because a function that generates garbage can increase
garbage collection time later, after that function is no longer running.

(And there are times when that's a good thing, like if the image
terminates before that GC ever happens, so the time is never spent.)

Typically in Lisps we have a profiling function which tells us how
much time was spent in some code, and how much memory was allocated.

If one stays the same, lowering the other one is better. If both
drop, that's a win.

You will rarely see a situation where an improvement in a function
resulting in less bytes consed, and less time, will be worse (more time
is spent somewhere else, cleaning-up after the function).

A counterexample might be a function that obtains a speedup via
memoization/caching. Once the cache is warmed up, it is fast, and conses
little memory, but the cache sticks around, and causes the garbage
collector to sometimes have to visit a larger reachable graph.

> Even if
> it does, the wider implementation is then suspect, because large lists
> tend to have poor memory locality. You might look to instead use
> generators, or packed vectors, or whatever.

Sure, but that is more work compared to a minor decision of whether
to drop-in replace reverse with nreverse, or other similar decisions
that have to do with "basic tidiness".

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Kaz Kylheku <433-929-6894@kylheku.com> writes:
> In a well built Common Lisp implementation, all the library functions
> that accumulate lists, like mapcar or the collect clause of Loop and
> whatnot, can be reasonably expected not to just push conses onto a stack
> and then nreverse. Typically, a tail pointer is maintained and the last
> cons cell is mutated to add the next one.

Sure, but that still builds the list in memory before processing it,
instead of making a pipeline that generates, processes, and garbage
collects elements.

> There is a way to do this with a single variable. We accumulate
> a circular list, keeping a pointer to its tail cons cell

There is a cute way to do nreverse with three registers that is possibly
faster than messing with a tail pointer, in the absence of cache
effects.

> Sure, but that is more work compared to a minor decision of whether
> to drop-in replace reverse with nreverse, or other similar decisions
> that have to do with "basic tidiness".

I'll believe nreverse is faster for application X when I see a benchmark
showing it. It's not a matter of a definite gain that might be
negligible. Nreverse might actually slow the program down, since it
results in new conses pointing to older ones, which can cause fallback
behaviour in some generational gc schemes.

Regarding your 3 ghz vs 30 ghz computer example, see:

https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf

Basically the 30 ghz computer likely won't be running the same programs
(or anyway the same inputs) as the 3 ghz one. The faster machine makes
it possible to handle bigger problems, and the execution profile will
change. Look at the stupendous number of cpu cycles going to whatever
bitmap display you're reading with right now, compated with old-school
character terminals.

Paul Rubin <no.email@nospam.invalid> writes:

I'll believe nreverse is faster for application X when I see a benchmark
showing it. It's not a matter of a definite gain that might be
negligible. Nreverse might actually slow the program down, since it
results in new conses pointing to older ones, which can cause fallback
behaviour in some generational gc schemes.

NREVERSE is not required to re-use the original cons cells in any
particular way. In fact, NREVERSE can do exactly the same thing as
REVERSE if an implementation determines that there is nothing better
that it can do. NREVERSE just gives the implementation permission to
re-use the old strucure, it doesn't force the implementation to do so.
So it's a good bet that using NREVERSE, whenever it is safe to do so,
will result in better performance.

Of course there might always be _some_ application where changing
NREVERSE to REVERSE will improve performance, but that's not going to be
the common case in a high quality Common Lisp implementation.

Always use NREVERSE (where you can) because in the unlikely event that
that proves to be the wrong choice, you can _always_ change it to plain
REVERSE without worry. (And in practice, I don't think that has ever
happened to me!)

- Alan

Alan Bawden <alan@csail.mit.edu> writes:
> NREVERSE is not required to re-use the original cons cells in any
> particular way. In fact, NREVERSE can do exactly the same thing as
> REVERSE if an implementation determines that there is nothing better
> that it can do.

Oh interesting, I didn't realize that. I see that reverse! in Guile
throws exceptions if it doesn't like the conses that you give it. I'd
expet the compiler can also replace REVERSE with NREVERSE if it can
prove that the difference is not observable.

> Always use NREVERSE (where you can) because in the unlikely event that
> that proves to be the wrong choice, you can _always_ change it to plain
> REVERSE without worry.

Fair enough, NREVERSE in Lisp is certainly idiomatic. I don't know
whether reverse! is equally idiomatic in Scheme. Python tends to prefer
vectors or generators while Haskell uses generators for everything.

Here's an old talk by Guy Steele about Fortress, suggesting that lists
(and generators) in a context like this are an antipattern:

http://groups.csail.mit.edu/mac/users/gjs/6.945/readings/MITApril2009Steele.pdf