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

I see, thanks for the detailed explanation. I understand the issue is whether the cost associated with cons checking arguments prior to creating the pair is acceptable or not but truly if cons is checking for list? by whether a bit is set or not, wouldn't that be negligible compared to the cost of creating the pair in the first place?

Now I'm curious enough to want to try modifying cons on my own and seeing what happens. Do you mind giving me pointers on how to do that? I imagine it'd require changing the source code and compiling racket?

> On Mar 8, 2014, at 1:00 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> 
> 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
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users