[racket] first vs car ; last vs cdr ; empty? vs null?

I've never measured carefully enough to be sure that it's better to put
the cost in `list?` instead of `cons`, but my guess is that the cost is
better in `list?`.

There's an `unsafe-cons-list` function sets the is-a-list bit when
creating a pair. That is, it always sets the bit without a test on the
second argument.

Some function, such as `list`, internally use `unsafe-cons-list`, since
the pairs that the function creates always form a list. In some limited
cases, the compiler effectively replaces `cons` with `unsafe-cons-list`
to set the bit early where no run-time test is needed. Currently,
`make-list` does not use `unsafe-cons-list` and the compiler is not
smart enough to replace its `cons` with `unsafe-cons-list`.

At Sat, 8 Mar 2014 12:53:06 -0500, Matthias Felleisen wrote:
> 
> I sit corrected :-) (I had it right at some point)
> 
> 
> On Mar 8, 2014, at 12:52 PM, Carl Eastlund wrote:
> 
> > If every cons set those bits, it would still take constant time because 
> you'd only have to look one deep.  However, the important part is that 
> currently cons never has to inspect its arguments.  Given that cons may be 
> called frequently in a program that never uses list?, one does not want to pay 
> for inspecting those arguments until needed.
> > 
> > Carl Eastlund
> > 
> > 
> > On Sat, Mar 8, 2014 at 12:47 PM, Matthias Felleisen <matthias at ccs.neu.edu> 
> wrote:
> > 
> > You want cons (the frequent action) to take constant time: allocate pointer, 
> set two fields.
> > 
> > 
> > On Mar 8, 2014, at 12:33 PM, David T. Pierson wrote:
> > 
> > > On Fri, Mar 07, 2014 at 11:03:57PM -0500, Carl Eastlund wrote:
> > >> The first/rest operations do not use a memoization table.  They test using
> > >> the list? primitive, which is built in and actually has a couple of tag
> > >> bits reserved on every cons object for memoizing its results.  So the
> > >> operation really is quite fast.
> > >
> > > I take this to mean there is a bit in the cons object for storing
> > > whether it is a list, and that this bit is set via `list?'.
> > >
> > > Why wouldn't the bit be set via `cons'?
> > >
> > > Also, when I do:
> > >
> > >  $ racket
> > >  Welcome to Racket v6.0.0.2.
> > >> (let ((ls (make-list 50000000 0)))
> > >    (time (list? ls))
> > >    (time (list? ls))
> > >    (time (list? ls))
> > >    (time (list? ls))
> > >    (time (list? ls)))
> > >
> > >  cpu time: 220 real time: 220 gc time: 0
> > >  cpu time: 112 real time: 112 gc time: 0
> > >  cpu time: 60 real time: 58 gc time: 0
> > >  cpu time: 28 real time: 29 gc time: 0
> > >  cpu time: 16 real time: 15 gc time: 0
> > >  #t
> > >
> > > Why does the time decrease gradually, rather than the 2nd and subsequent
> > > times being roughly equivalent?
> > >
> > > Thanks.
> > >
> > > David
> > > ____________________
> > >  Racket Users list:
> > >  http://lists.racket-lang.org/users
> > 
> > 
> > ____________________
> >   Racket Users list:
> >   http://lists.racket-lang.org/users
> > 
> > 
> 
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users