However, if my-list had been declaimed notinline, then the compiler
is definitely constrained by the spec from open-coding it, because the
notinline declaration/declamation is one of only 4 delaration specifiers
(besides declaration, (greater) safety, and special) that the compiler
cannot ignore.

Thus, to make this code completely portable, you could place a
  (declaim (notinline mylist))
before the defun.

When you write a user-defined datatype, the compiler can't just be free to
lose the identity of the sub-parts becuase it doesn't understand the
interrelation.  If a compiler dumped me out into a fasl file and then read
me back in, it would not suffice to just conjure two new kidneys and say
"well, you should have declared them separate constants if you wanted the
human beingness of kent to work again after you loaded him".  It's better
for the language to make it clear that you can't save a complex object
at all and expect to get it back unless you write the code to do it because
it would be lying to you if it declared otherwise.

I think the reason a lot of you think the language should do this is
that you're not used to thinking like a language designer.  I don't
mean the technical part--there are a lot of sharp technical people.  I
mean the guilt thing.  Language design is a lot about seeing people
flail because you gave them enough rope to hang themselves and they
did.  And I claim that what separates good design from bad design is
that good designers not only look for things that are hard in hopes of
making them easier, but also they look to where people get in trouble
a lot and are willing to take the personal guilt involved in making
life more difficult by saying "you won't be allowed to get X for free"
because they know that "for free" is a lie and they don't want you to
just end in a mire.

Just about anyone could design a more functional set of tools than a
language designer can design a language because tools only have to
work most of the time and you can kinda shrug and document the places
where they don't work.  But the importance of being linguistic is that
you are the very concrete of the foundation on which all future things
will sit, and if you are not designed to be strong, even the tiniest
little cracks will add up after a while and their implications will
start to be felt in places that are far removed from the places that
people are focused on.

I'll give you an example that is off-topic but maybe illustrates what I
mean by things felt other places.  Just the other day, I was talking
to someone about having systems tell you when you make certain dumb
little errors.  An example might be calling a function with stupid arguments.
Not wrong, just stupid.  For example:
 (read-from-string stream :start 2)
is a classic.  This is completely valid code and it doesn't start
reading from position 2.  I would allege that it's appropriate to warn
about it because the probability is so high that even a mechanical program
wouldn't do it that it's worth the warning.  But take the following case
that Maclisp used to warn about a lot:
 (member x '(a))
I used to get warnings saying one argument to OR was probably a mistake
because it would open code this to
 (or (eq x 'a))
and it would think it was dumb for me to use OR without at least two things.
This warning happened a lot and was well-appreciated for years until
macros came into common use, and then it was disastrous.  I had code
that said:
 (member x '(a $make-compiler-happy$))
because it was constructed by other code that did
 `(member x '(,@things $make-compiler-happy$))
and I did not know how many things I would be given.  The argument made
by the people who wanted the warning about the OR was that the warning was
"useful" but the argument made by the others was that "useful or not,
it doesn't scale".  The language foundation has to be built on things
that scale.  Similar problems came up about dead code.  It's handy to
get warnings about code like
 (cond (foo x) (t y) (bar z))
if no macros are involved, but if a macro is involved, and if the compiler
is deadset on issuing a warning, you're in a real problem and you have
to do weird things like:
 (cond (foo x) (*lisp-wont-be-told-until-after-compilation-that-this-is-t* y) (bar z))
And even then, it's probably going to result in slower code.

I can see differing interpretations.  It seems to me the whole point of
DEFCONSTANT is to say "the compiler may aggressively view the result of
this computation" and the whole point of saying LOAD-TIME-VALUE it to
say "the compiler may not aggressively view the result of this
computation".  Do they cancel?  Is the entire form evaluated as if by
EVAL and is "load-time" for the "EVAL" the same as compile-time?  I don't
know if I know the answer.  I know I've spent so long replying to this that
I'm not going to spend more time researching it today.  

    Erik>   just for the heck of it: I have tuned a _very_ CPU-heavy function I wrote
    Erik>   in Common Lisp over a year ago so it went from the unsatisfactory 623 µs
    Erik>   per call to the very pleasant 4.7 µs per call.

Would it be possible to provide the before and after versions of the
code?

I think it would be very instructive.

Hartmann Schaffer

  OK, I'll do the steps thing.  at issue was hacking up and printing a time
  representation.  the naïve solution is to use a bignum of seconds since
  some human-inspired epoch, use FORMAT with ~D to print it.  however, I
  also needed proper timezone support (CL's support is suitable only if you
  deal with times in a single timezone), and milliseconds (since a second
  is a really long time to modern computers, and even milliseconds are).
  the zone was represented as the number of hours west of Greenwich.

  the time representation is now split up into day, time, and milliseconds.
  the zone is changed to seconds eas of Greenwich.  day 0 is 2000-03-01,
  because that's when a new 400-year leap year period starts, which means
  that the leap day is at the end of the four years, the centennium, and
  the quatercentennium, and thus no expensive computations are needed to
  check for leap years.  however, the main culprit was division.  it is an
  expensive operation, table lookup not, so I precomputed tables for the
  146097 days of a quatercentennium and the 86400 seconds of a day, and did
  a nifty data representation hack so the values fit in a single fixnum.

  the full time representation was changed from a class to a structure, and
  proper declarations meant that the access functions were inlined and the
  type (fixnum) propagated properly.

  time comparison functions now compared three fixnums instead of bignums
  and a fixnum (milliseconds) and that meant the timezone tables (extracted
  from the Unix timezone database that the C library uses (but also gives
  you exactly one handle on)), were searched much faster.  in addition, the
  interval of the timezone was made available to the caller upon demand (it
  affects the length of a local day, which can be 23, 24, or 25 hours!) and
  also cached, since most times decoded were in the same timezone.  the
  time zone adjustment function also did simple addition and subtraction
  instead of new divisions into day and time.

  what really made a difference once I had figured out how to store the
  values in a fixnum (I'll leave that as an exercise for the reader --
  since it's so far from obvious how to do it, some people will get a real
  kick out of how simple it is, and I don't want to take that kind of joy
  away form anyone), was to pass a preallocated vector for the decoding
  functions to store its values into instead of returning them as multiple
  values.

  finally, printing turned out to be very division-intensive, too, so I
  precomputed a pair of tables of high and low digits for 100 numbers.
  streams were also very expensive, so I deposited characters directly into
  a preallocated string and returned a copy or wrote it out (depending on
  whether the stream argument was NIL or a stream, like FORMAT).  centuries
  were easy to change into numbers in the 16 to 99 range instead of 1600 to
  9900.

  (granted, I have built myself a system with a serious Y10K problem, but
  I'll print a warning in the year 9900 if it makes anyone less worried.
  rumor has it that Y1K brought us the Dark Ages because it took 400 years
  to update all the software to four instead of three digits in the year.)

  the only real problem I had with tuning this stuff was that a 400 MHz CPU
  is damn hard to get useful statistics from every 10 ms.  it manages to do
  a tremendous lot of work in 10 ms, so I had to let profiling run for many
  minutes to collect useful data as I got closer to the optimum.

On 02 Apr 1999 11:52:50 +0000, Erik Naggum wrote:

..

..

Groetjes, Peter

  no, the individual (day month year) and (second minute hour) triples.

| So (year,month,day,hour,minute,second) in a fixnum, right?

  no.  keep trying.  :)

| Aha.  Is it not possible to use the cycle-counter on modern x86's to
| check this.  You would have to insert get-the-count instructions here and
| there, but it gives you a resolution of 1 clock tick.  IIRC

  yes, this is possible, but as far as I can see, Allegro CL does not
  support this mode of operation.  I think it's a little too much to ask,
  too, but if I can get over the _disgusting_ machine language in the Intel
  CPU's, I might play with this one day...

I knew that this issue is going to teach me more than just about
constants and constantness.  I can see more clearly now that
my mindset about objects goes like this: the identity of an
object lasts only as long as it lives in core, i.e. there is
a `live' reference to it.  Externalising and internalising
in the general case means losing its identity.  There is no
_general_ way to prevent this: achieving this prevention can only
be considered on a case per case basis.

(I am not saying that my mindset is right or wrong, just want to
grasp it better.  And it does need more refinement.)

(...)  ;on language design

You are right that I don't think like a language designer, and I
should try to imagine myself in a language designer's shoes, as it
were, more often.  I guess I am now rather irresponsibly testing
how far the cracks would open...

As an aside, isn't one of the good things about Lisp that with it
one plays with a _language_, while with C one plays with a _machine_
(and with C++ one---well, is engaged in non-playful activities with
a machine).

I think that this is at least one of the reasons why it is important
to distinguish between program writing time and compile time.

(Or should it be `program write time'?)

(...)

You got me!

<annoying-Latin-mode-again>
Next I'll be putting into my signature `Ceterum, censeo, names of
constant variables should have equal signs around them.'
</annoying-Latin-mode-again>

(...)  ;number of times a DEFCONSTANT initialisation form is evaluated
       ; vs. number of times a LOAD-TIME-VALUE form in a symbol macro
       ; expansion is evaluated

I may be missing the point again but the concept of files has a clear
presence via LOAD and COMPILE-FILE.  My concern here is related not to
externalisation but to side effects (including functions such as RANDOM
that return different values on each invocation), and I wanted to
highlight differences I can see between DEFCONSTANT and
DEFINE-SYMBOL-MACRO (straighforward use of the latter in particular,
imitating #define).

As far as I can see,

  (defconstant =foo= '(a b c) "a list")

and

  (define-symbol-macro =foo= '(a b c))

do the same job; but consider these two scenarios (untested, sorry!):

(i)  DEFCONSTANT:

  ;;; setting the stage:
  (defparameter *counter* 0 "to be incremented by one")
  (defun counter () (list 'counter (incf *counter*)))
  (defconstant =foo-const= (load-time-value (counter) t)
    "a list containing an integer")

  File one:
  (format t "~&one/1: ~S" =foo-const=)
  (format t "~&one/2: ~S" =foo-const=)

  File two:
  (format t "~&two/1: ~S" =foo-const=)
  (format t "~&two/2: ~S" =foo-const=)

Whether constant variables are inlined or not, loading these files
one after the other would print

  one/1: (COUNTER 1)
  one/2: (COUNTER 1)
  two/1: (COUNTER 1)
  two/2: (COUNTER 1)

(ii)  DEFINE-SYMBOL-MACRO:

  ;;; setting the stage:
  (defparameter *counter* 0 "to be incremented by one")
  (defun counter () (list 'counter (incf *counter*)))
  (define-symbol-macro =foo-macro= (load-time-value (counter) t))

  File one:
  (format t "~&one/1: ~S" =foo-macro=)
  (format t "~&one/2: ~S" =foo-macro=)

  File two:
  (format t "~&two/1: ~S" =foo-macro=)
  (format t "~&two/2: ~S" =foo-macro=)

And the printout would be:

  one/1: (COUNTER 1)
  one/2: (COUNTER 1) _or_ (COUNTER 2)
  two/1: (COUNTER 2) _or_ (COUNTER 3)
  two/2: (COUNTER 2) _or_ (COUNTER 4)

Yes, there's some ambiguity in `reference.'  If we agree to visualise
references as arrows, sometimes `reference' means the start of the
arrow and sometimes the end of the arrow, I think.  So in the above
LET* form there are three arrows (one for +QUUX+, one for X, one
for Y), with X's being used twice, and all of which end at the same
object.

(...)

(...)

(defconstant =foo= (list 1 2 3))
(eql =foo= =foo=) => true

vs.

(define-symbol-macro =foo= (list 1 2 3))
(eql =foo= =foo=) => false

R5RS has this:

   In the following example the only tail call is the call to f.  None
   of the calls to g or h are tail calls.  The reference to x is in a
   tail context, but it is not a call and thus is not a tail call.

      (lambda ()
        (if (g)
            (let ((x (h)))
              x)
            (and (g) (f))))

    Note: Implementations are allowed, but not required, to recognize
    that some non-tail calls, such as the call to h above, can be
    evaluated as though the were tail calls. (...)

See http://www.sonic.net/~bear/scheme/r5rs.html#SEC24 .

I.e. the result of EQL on constant variables is unspecified except
for data objects such as symbols where EQUAL is the same as EQL.

So EQL is unspecified in the former case and false in the latter;
the real difference I can see between these two examples is that
one can destructively modify the value coming from the symbol macro.

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

Not to mention that ill fated attempt in one of the states of the USA
to vote on a formula implying a rather poor approximation of pi.

(...)

(...)

(...)

Thanks for the followup clarifications about the example.

(...)  ;using LOAD-TIME-VALUE to get a `lock' on a reference
       ; (not in the usual sense of `lock' for mutual exclusion,
       ; but in the same sense as a radar locks on a target---
       ; sorry for the military metaphor)

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

My point was not about what Scheme does now, but rather that we
discussed how it should be defined and it was, as I recall, decided
that without making it formal exactly what was to be detected, it
wasn't the right time to define that (h) in the above is a tail call.
But that might change in the future.  Various people are getting
psyched to make the whole business of storage usage in these
situations more formal.

It might help a little if you knew the 0d array was also simple.(I
never saw a displaced or adjustable 0d array, but I think it's
possible in principle. :-)

Perhaps you are thinking of some other funny case? This one seems pretty
clear (even without resorting to R5RS). Since (even in R4RS) "let" is a
"derived expression", its defining semantics are given in terms of a
procedure call of its body, i.e., translating your example:

        ((lambda (x) x) (+ y 3))

Now that being the case, and given that Scheme is a call-by-value
variant of the lambda calculus, if I understand these things correctly
the "(+ y 3)" is *not* in a tail position, since it must be evaluated
*before* the call to the lambda.

The lambda itself is not in a tail position, either, for the
same reasons. But the *body* of the lambda ("x", in this case) is...

Hmmm... I see here that R5RS *allows* the beta-reduction to "(+ y 3)"
[which would convert it to a tail call of "+"], in section "3.5 Proper
Tail Recursion" [just after the example Darius(?) quoted which contained
a (let ((x (h))) x) as one branch of an "if"], where it says:

        Note: Implementations are allowed, but not required, to recognize
        that some non-tail calls, such as the call to "h" above can be
        evaluated as though they were tail calls. In the example above,
        the "let" expression could be compiled as a tail call to "h".

So it's only "in a tail position" if your compiler is smart enough to
*prove* that making it so won't break the semantics...

-Rob

Several Scheme implementations have such a notion for a half-cons,
conventially called a "box":

        > (define foo (box 37))              ; some call it "make-box"
        > (box? foo)
        #t
        > (unbox foo)
        37
        > (set-box! foo 24)
        > (unbox foo)
        24
        >

In Common Lisp, of course, I guess you could always do:

        > (defstruct box (content))
        BOX
        > (setq foo (make-box :content 37))
        #S(BOX :CONTENT 37)
        > (box-content foo)
        37
        >

but I'm not sure how much overhead CL drags along with a structure instance
(in addition to the slots themselves)...

-Rob

p.s. FWIW, MzScheme provides the following
printer & reader syntax for boxes:

        > foo
        #&24
        > (box? #&51)
        #t
        > (unbox #&51)
        51

I hope I mentioned it that I was aware of higher costs---the reason
why I still put forward 0d arrays has to do with expressing intent,
see below.

(In fact, assuming 64 bits of header and, in a 64-bit architecture,
64 bits per reference, a simple array with room for a single element
would occupy as much storage as a cons cell.  But this is just
hypothetical.)

But, before worrying about storage, I worry about a clear expression
of my intent to use something as a singleton reference.

(1) Using a cons is most efficient but is one of those `cancer of the
    semicolon' cases:

    (let ((ref (cons foo nil)))  ;the cdr will not be used
      ...)                       ^^^^^^^^^^^^^^^^^^^^^^^^^

(2) Using a structure makes for a program where adding a second slot
    is an easy change to the program: a structure with just one slot
    still sort of implies that a second slot might appear some day,
    and I don't want that.  For the same reason, I want a _zero_
    dimensional array, not a vector of length 1: (AREF REF) means
    there is just this one, period, while (AREF REF 0) again sort of
    implies that one day we might see (AREF REF 1) etc.

(3) Of course I could say

    (defstruct ref obj)  ;thou shalt have just this slot

    but on the other hand sometimes I (perhaps others too) prefer
    idioms to Doing the Right Thing by introducing abstractions
    for each and every purpose and thus cluttering the program
    with defining forms and the concept space with datatypes,
    accessors, etc.  (For the same reason I am not very keen on
    wrapping calls to CONS and FIRST in calls to MAKE-REF and REF.)

Anyway, this exercise is not worth more than the proverbial two cents
since even if `efficient singleton references' makes it to a wish
list it would have very nice(1) priority...

I also remember the case of Algol-68, which among other things tried
to Get references Right, I believe.

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

Thanks, this is interesting to know.  I am afraid I can't find the
time to follow Scheme developments, so it is good that I can catch
at least some pieces from comp.lang.lisp.

Are boxes as efficient as cons cells in terms of speed of access and
memory use?  (By the latter I mean, does a box take up half the space
for a cons?)

But I suspect that reading this back would produce a fresh box---
is that so?  If yes, this may or may not be what I want, and we have
hit the externalisation issue again...

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

  Constant variables defined in the compilation environment must have a
  similar value at run time. A reference to a constant variable in
  source code is equivalent to a reference to a literal object that is
  the value of the constant variable.

so similarity is already mentioned here.

Second:

  3.2.4 Literal Objects in Compiled Files

  The functions eval and compile are required to ensure that literal
  objects referenced within the resulting interpreted or compiled code
  objects are the same as the corresponding objects in the source code.
  compile-file, on the other hand, must produce a compiled file that,
  when loaded with load, constructs the objects defined by the source
  code and produces references to them.

  In the case of compile-file, objects constructed by load of the
  compiled file cannot be spoken of as being the same as the objects
  constructed at compile time, because the compiled file may be loaded
  into a different Lisp image than the one in which it was compiled.
  This section defines the concept of similarity which relates objects
  in the evaluation environment to the corresponding objects in the
  run-time environment.

  The constraints on literal objects described in this section apply
  only to compile-file; eval and compile do not copy or coalesce
  constants.

(By the way, it was easy to find these as the links to them still show
up as recently visited in my browser.)

I find the above to mean that the file compiler _may_ inline the value
of a constant variable: it treats it like it treats a literal object
(3.2.2.3), and for that only similarity, and not necessarily eqlness,
must be observed (3.2.4, 2nd paragraph).

To make sure there's no misunderstanding, for me

  (EQL =FOO= =FOO=) may return T or NIL

is shorthand for:

  if a file has, say, (DEFUN FOO1 () =FOO=), and another file has, say,
  (DEFUN FOO2 () =FOO=), then (EQL (FOO1) (FOO2)) may return T or NIL.

(While (EQL =FOO= =FOO=) does not necessarily imply programmer
silliness if it is seen by the compiler (since one or both foo's may
come from macro expansion), I would find it hard to argue that the
latter form may return NIL as it can occur but within a single file.)

So if (EQL (FOO1) (FOO2)) => NIL, one might be right to say that the
implementation worked in a counter-intuitive, unexpected, or harmful
way (I would disagree but I wouldn't argue about that here), but one
would *not* be right to say the implementation broke the rules.

Once again, my summary of the issue (which maybe deserves attention
if and when the standard is reviewed) is: like DEFINE-SYMBOL-MACRO,
DEFCONSTANT does not provide a constant reference (non-inlinable)
to an object.  (DEFCONSTANT differs from DEFINE-SYMBOL-MACRO with
respect to other things: when and how many times the value form is
evaluated, and also with respect to the possibility of the same
symbol appearing in a binding form.)

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

It all depends on the implementation, I'd guess. In MzScheme a box is an
instance of "Scheme_Small_Object", which is a type field [a short, but
most compilers will force that to a PSV] and a pointer-sized value (PSV).
A cons is an instance of "Scheme_Object", which is a type field and
two PSVs. So for MzScheme, a box is 2/3 (or maybe 3/5) the size of a cons.

In an implementation I've been working on [play project], the same is true:
a box is 2/3 the size of a cons.

Chez Scheme (see http://www.cs.indiana.edu/eip/workshop1/lab7/lab73.html)
also has boxes, but I don't know if they're 1/2, 2/3, or 1 times a cons...

-Rob

(defun encode-time-values (days seconds milliseconds)
  (dpb seconds (byte 17 10)
       (dpb milliseconds (byte 10 0)
            (ash days 27))))

?  That runs out of fixnum range on 32-bit machines pretty quickly.

Assuming Lisp Machine locatives are singleton references, I'm also
curious to know what were the reasons why they didn't make it into
Common Lisp (to avoid complexity? to avoid expensive implementation
on stock hardware? ...)

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)