XPost: comp.lang.scheme
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)