From: Jeff Dalton
Subject: Becoming less EQL?
Date:
Message-ID: <7519@skye.ed.ac.uk>
The file compiler can make things "more EQL" by coalescing, but
can it ever make things "less EQL"? For instance, if I carefully
arrange for two quoted lists to be EQL (via a macro, say), can
the file compiler make them be completely separate lists?
There's something in CLtL II that says _substructures_ that are
EQL must stay EQL. But what if they're not substructures of some
larger common data object?
Empirical results are strange:
----------------------------------------------------------------------
;;; Can objects become less EQL as well as more?
(defun M () ''(a b c))
(defun f () (M))
(defun g () (M))
(defun h () '(a b c))
(defun i () '(a b c))
(eval-when (eval compile load)
(defun a-list () '(a b c)))
(defmacro M2 ()
(list 'quote (a-list)))
(defun j () (M2))
(defun k () (M2))
(defun coalesce-test ()
(values (eq (f) (g))
(eq (g) (h))
(eq (h) (i))
(eq (i) (j))
(eq (f) (j))
(eq (j) (k))))
;;; Results:
;;; akcl-1-505 t, nil, nil, nil, nil, t
;;; cmucl 16d t, nil, t, t, nil, t
;;; lucid 4.0 t, nil, nil, nil, nil, t
;;; allegro 4.0 t, nil, nil, nil, nil, nil
;;; allegro 4.1 t, nil, nil, nil, nil, t
----------------------------------------------------------------------
Only CMU CL is making quoted lists more EQL. I find this surprising.
But then there's Allegro 4.0, which makes lists less EQL in the M2
case. Also strange. What's so different about M2?
But now look at this:
----------------------------------------------------------------------
;;; Can objects become less EQL as well as more?
(defun M () (list 'quote '(a b c)))
(defun f () (M))
(defun g () (M))
(defun h () '(a b c))
(defun i () '(a b c))
(defun coalesce-test ()
(values (eq (f) (g))
(eq (g) (h))
(eq (h) (i))))
;;; Results:
;;; cmucl 16d nil, nil, t
----------------------------------------------------------------------
Why is the first value nil? Why should redefining M in this
trivial way have this effect? Especially since M2 and the old
M did not have this result?
Conclusion: In practice, you can't trust the file compiler to leave
EQL things EQL if the things are lists.
But can anyone explain why some of the more bizarre bahaviors occur?
-- jd
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>The file compiler can make things "more EQL" by coalescing, but
>can it ever make things "less EQL"? For instance, if I carefully
>arrange for two quoted lists to be EQL (via a macro, say), can
>the file compiler make them be completely separate lists?
P.3-28, Section 3.2.4.4 "Additional Constraints on Externalizable Objects",
of the dpANS, first paragraph, says, "If two literal objects appearing in
the source code for a single file processed with the file compiler are the
[sic] identical, the corresponding objects in the compiled code must also
be the [sic] identical."
>Only CMU CL is making quoted lists more EQL.
I wouldn't be surprised if you got different results if you first disksave
and then run the tests. I think some implementations may do coalescing by
collusion between the file compiler and the disksave routine, since it's
often disksave that moves constants into the read-only text segment.
> I find this surprising.
>But then there's Allegro 4.0, which makes lists less EQL in the M2
>case. Also strange. What's so different about M2?
Notice that Allegro 4.1 obeys the rule. Apparently someone else noticed
the bug and it got fixed.
Symbolics Genera 8.1.1 has the same results as Allegro 4.0. I agree that
it's strange. I think the Symbolics compiler implements literal lists by
copying them into the literal pool of the referencing function, and this
results in each function getting its own copy, so they're not EQL.
>(defun M () (list 'quote '(a b c)))
>
>(defun f () (M))
>
>(defun g () (M))
>
>(defun h () '(a b c))
>
>(defun i () '(a b c))
>
>(defun coalesce-test ()
> (values (eq (f) (g))
> (eq (g) (h))
> (eq (h) (i))))
>Why is the first value nil? Why should redefining M in this
>trivial way have this effect? Especially since M2 and the old
>M did not have this result?
The first value is NIL because M calls LIST, which is required to cons a
different list each time it's called. Did you intend this M to be a macro
rather than a function?
>Conclusion: In practice, you can't trust the file compiler to leave
>EQL things EQL if the things are lists.
Right. This requirement was not in CLtL, and no implementations yet
conform to all the new requirements that X3J13 added.
Note that conforming to this requirement isn't trivial. Consider the
following code:
(eval-when (compile eval load)
(defparameter literal '(a b c)))
(defmacro m1 () '(1 . #.literal))
(defmacro m2 () '(2 . #.literal))
(defun f1 () (cdr (m1)))
(defun f2 () (cdr (m2)))
(defun coalesce-test ()
(eq (f1) (f2)))
Recognizing the sharing when generating the object file requires walking
all levels of all literal structures that appear in the code.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
From: Jeff Dalton
Subject: Re: Becoming less EQL?
Date:
Message-ID: <7523@skye.ed.ac.uk>
In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
>In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>>The file compiler can make things "more EQL" by coalescing, but
>>can it ever make things "less EQL"? For instance, if I carefully
>>arrange for two quoted lists to be EQL (via a macro, say), can
>>the file compiler make them be completely separate lists?
>
>P.3-28, Section 3.2.4.4 "Additional Constraints on Externalizable Objects",
>of the dpANS, first paragraph, says, "If two literal objects appearing in
>the source code for a single file processed with the file compiler are the
>[sic] identical, the corresponding objects in the compiled code must also
>be the [sic] identical."
Excellent. I was hoping to be able to rely on this (given conformance
to the std)
>>Only CMU CL is making quoted lists more EQL.
>
>I wouldn't be surprised if you got different results if you first disksave
>and then run the tests. I think some implementations may do coalescing by
>collusion between the file compiler and the disksave routine, since it's
>often disksave that moves constants into the read-only text segment.
I almost never use disksave except when building a system, so it
won't help me much if it only does it then. So CMU CL wins again!
>>(defun M () (list 'quote '(a b c)))
>>
>>(defun f () (M))
>>
>>(defun g () (M))
>>
>>(defun h () '(a b c))
>>
>>(defun i () '(a b c))
>>
>>(defun coalesce-test ()
>> (values (eq (f) (g))
>> (eq (g) (h))
>> (eq (h) (i))))
>
>>Why is the first value nil? Why should redefining M in this
>>trivial way have this effect? Especially since M2 and the old
>>M did not have this result?
>
>The first value is NIL because M calls LIST, which is required to cons a
>different list each time it's called. Did you intend this M to be a macro
>rather than a function?
Not only did I intend it to be a macro, I'm pretty sure it was a macro
at an earlier point. But I must hve been WRONG, because I just tried
it again w/ a macro and got t,t,t. Another win for CMU CL!
Good. I was worried about that one.
Thanks. I knew I could count on you to set me straight if I blew it.
-- jeff