Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!sdcsvax!ucsdhub!hp-sdd!hplabs!otter!sfk
From: sfk@otter.hple.hp.com (Stephen Knight)
Newsgroups: comp.lang.lisp
Subject: Re: Filtering Vectors in CL Question
Message-ID: <1350010@otter.hple.hp.com>
Date: 28 Jan 88 18:20:44 GMT
References: <1350001@otter.HP.COM>
Organization: Hewlett-Packard Laboratories,Bristol,UK.
Lines: 37

The neat collection of solutions proposed by Barry only work for lists and not
vectors.  The idiom Chris is trying to investigate (I believe) is 
that of constructing vectors without going through an 
intermediate structure when the size of the vector is not known beforehand.
Of course, this problem can be generalised to :-

    Construct a structure with an unknown number of components
    in which some computation needs to be done to figure out the
    components.  This construction should generate as little garbage
    as possible (none) and be reasonably efficient (order of the 
    number of components with constant factor < 3, say.)

The trick which makes this possible in Pop11 is the global, open stack PLUS
the knowledge that this stack is efficient to access.  The problem in Lisp
style languages is that there is no dynamically growable structure that 
is comparably efficient.  As such, I think that all solutions in Lisp have to
be justified in terms of the guaranteed performance of the primitives.

The two styles of solution I see are either to arrange to have a stack-like
entity that is fairly cheap or to reclaim the intermediate store.  The first
solution leads into extensible arrays -- and then insisting that implementors
should be obliged to guarantee space & time efficiency.  The second approach
is to construct all lists with a version of "cons" that checks a free list
first before allocating fresh store and then provide an operation for returning
list cells to the free list.  This is a fairly widely known hack that 
should have found its way into CLtL.

The general problem, stated roughly above, finds its way into my code with
surprising regularity.  Similarly, the use of partially applied functions
and multiple results are elegantly facilitated by the "open stack" approach
of Pop11.  Although, coming from a Lisp background, I found the idioms 
associated with the open stack a bit strange at first, I found myself
missing it when I went back to Lisp.  These days I hack in Pop11 almost
exclusively & feel sure that a lot of people who find Lisp frustrating
would get a lot out of looking at this language, too.

Steve Knight