Re: Structures as literals

Not Dr!

I didn't mean undecidable although semantics is part of the problem.

What I meant is that if you want to do this in a way that is 'correct' it becomes extremely expensive and hairy.

Consider two Lisp images L and L'.  At some point, L sends and object o to L', which in L' is o'.  At some later point L sends it again resulting in o''.  If you want it to be the case that o' and o'' are identical in L' (so they are EQL), then L has to keep track of every object it has ever sent which can still be referenced in L.  And worse, L can't know (unless L' tells it) that o' can still be referenced in L' at the point it sends o for the second time.

It is much easier of course if you weaken things so that only during the transmission of a single object does this hold: that's a fancy version of *print-circle* since you don't have to deal with the whole object-becoming-unreferenced thing.  But, well, you might want to send more than one object.

But here's where semantics starts to matter: in many, many cases, you simply don't care about any of this, because the semantics of the objects are such that sharing is irrelevant.  Or, perhaps it is relevant to some parts of them (you want interned symbols to be shared almost always, for instance).

As an example the structures I wanted the compiler to be able to externalize certainly share all sorts of list structure in their slots because of how they are built.  But it's entirely irrelevant to their meaning, and I really do not want some heroic 'I will preserve everything' thing getting in the way and making my program slow and big.

You don't want a general hairy slow do-the-right-thing solution, you want a solution that works for the semantics of the object you care about.  And type information does not tell you enough about that.

All of this is very closely related to the fact that CL has no 'generic' equality predicate or 'generic' copy predicate.  Kent Pitman among others wrote some pretty good things about this back in the cll days: I expect most of it is effectively lost now.

Silly example

? (let ((c (make-collector)))
    (collect-into c 1)
    (equal c '((1) 1)))
t

which is entirely the wrong answer.

--tim


> On 3 Mar 2026, at 12:04, Bradford Miller (as bradford dot w dot miller at gmail dot com) <[email protected]> wrote:
> 
> I suspect Dr. Bradshaw was referring to Rice’s Theorem, and meant undecidable? That doesn’t mean you can’t have something that works on a finite syntactic set.
> 
>> On Mar 2, 2026, at 7:01 PM, David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote:
>> 
>> But I don’t understand your statement that it is a generally intractable problem. The system I have been using since 2009 has worked wonderfully well for me, and handles self-referential and circular references transparently. The only thing it can’t serialize is compiled code and functional closures.
>> 
>> - DM
>> 
>>> On Mar 2, 2026, at 15:34, Tim Bradshaw (as tfb at cley dot com) <[email protected]> wrote:
>>> 
>>> On 2 Mar 2026, at 18:50, David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote:
>>>> 
>>>> Instead of MAKE-LOAD-FORM, I use a binary interchange format for my serialization across the network and to file storage. So long as another Lisp reads them back, they are portable.
>>> 
>>> I was asking about the specific case of specific literal objects of objects in compiled files, not another attempt to solve a famously intractable-in-general problem.
>>> 
>>> _______________________________________________
>>> Lisp Hug - the mailing list for LispWorks users
>>> [email protected]
>>> http://www.lispworks.com/support/lisp-hug.html
>> 
>> 
>> _______________________________________________
>> Lisp Hug - the mailing list for LispWorks users
>> [email protected]
>> http://www.lispworks.com/support/lisp-hug.html
> 
> 
> _______________________________________________
> Lisp Hug - the mailing list for LispWorks users
> [email protected]
> http://www.lispworks.com/support/lisp-hug.html


_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html