[squeak-dev] The solution of (Was: Creating an image from first principles)

2008/7/8 Andreas Raab <[hidden email]>:
I think i have found a simple and lean solution how to instantiate an
object memory based on analysis & processing within another object
memory.
For this, we need a single primitive, which can be added to Hydra VM
to do all things for us, and there is no need to use simulator!

At first stage, the running image should designate all objects which
have to be cloned into new heap, by providing a collection of such
objects - this can be done completely using available tools & by
writing a proper code.

Then we simply call a primitive, which creating a new (empty) object
memory and cloning all objects found in collection to new heap.
It also should follow the rules, that if (objects at: x) having
reference to (objects at: y) then cloned (objects at: x) will have a
reference to cloned (objects at: y).
In this way, if our collection forms an isolated subgraph (which does
not referencing to any objects outside itself)  - we are able to
instantiate a new object memory without any risk of broken references.

There are three ways how primitive can deal with situation when some
object pointing to an object which is outside a given collection:
- be stupid, and simply fail
- fail as well, but return an array of objects which is the cause of failure
- do not fail and threat such references as far references . This is
for future use, when miracle happens and we can have a cross-heap
references.

I want to give a credit to Klaus, because this idea is born during
discussion with him :)

P.S. if you have noticed, the way how new object memory created is
very similar to http://en.wikipedia.org/wiki/Cell_division
The implementor don't need to care about object formats, different
bits, etc etc - he just needs to designate a full set of objects which
should appear in new object memory.


--
Best regards,
Igor Stasenko AKA sig.

On 6-Aug-08, at 3:14 AM, Igor Stasenko wrote:
>
> I think i have found a simple and lean solution how to instantiate an
> object memory based on analysis & processing within another object
> memory.
> For this, we need a single primitive, which can be added to Hydra VM
> to do all things for us, and there is no need to use simulator!

We've had this for decades. It's called the SystemTracer. It's way  
more flexible than a primitive. I (amongst others) have performed Acts  
Of Deep Magick with the tracer other the years. All it takes is a  
twisty mind and some patience.


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
The colder the X-ray table, the more of your body is required on it.

2008/8/6 tim Rowledge <[hidden email]>:
Surely, i'm aware of it.
The process of picking objects, dealing with unwanted references,
cutting an object graph - all this is on hands of developers.
But then, when you having a set of objects to be cloned, and a set of
references to be substituted - this can be done in atomic way.
It also allows to fire up new image without any file i/o.

>
> tim
> --
> tim Rowledge; [hidden email]; http://www.rowledge.org/tim
> The colder the X-ray table, the more of your body is required on it.
>


--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
> The process of picking objects, dealing with unwanted references,
> cutting an object graph - all this is on hands of developers.

And of course, all of this "picking objects, dealing with unwanted
references, cutting object graphs" is exactly why this process has
nothing in common with creating an image from first principles. It is
just transforming one mess into another and not all what I am after.

Cheers,
   - Andreas

Ok, well I was talking to someone a few weeks about this idea of
building an image from an XML file, I'm wondering how important it is
to anyone?

Likely such a system would allow you to build the same exact image
from a description of a versioned target, also of course give you the
ability to diff between two versions and exactly know what the image
differences are.

But I think in the past it's not been an important idea?

On Wed, Aug 6, 2008 at 10:04 PM, Andreas Raab <[hidden email]> wrote:

2008/8/6 Andreas Raab <[hidden email]>:
Okay, let me review the steps, how i seeing it with doing everything
in same interpreter without the need of simulation:

> Start with the interpreter simulator and a (literally) empty object memory.

Start with an empty IdentitySet, which will represent a set of objects
found in object memory to be created. All newly created objects which
we will want to see in our object memory will be put in this set.

> Read a series of class definitions (you can use either MC class defs or
> simply parse simple class definitions from sources) that are sufficient to
> define all of the kernel structures that are required by the running VM
> (incl. Object, Behavior, Class, Integer, Array, Process, CompiledMethod,
> ContextPart, Semaphore etc. etc. etc.).

- use a ClassBuilder, or add single method to Behavior to be able to
create the abovementioned classes, but without installing/registering
them anywhere (SystemDictionary etc) and treat them as anonymous
classes.

Also, we should create a 'shadow' dictionary which will represent a
future SystemDictionary and put these classed in new dict.

> At this point we have a skeleton of classes that we can use to instantiate
> all behaviors required by a running image.
>

- this statement is TRUE for newly created classes in such way.

> Next, make a modification to the compiler that allows one to create a
> compiled method in the simulator from a MethodNode (which should be
> straightforward since the simulator exposes all of the good stuff for
> creating new objects and instances).
>

Indeed, we have to change a compiler to use different environment than
default and use it for:
- creating new method instance
- creating new literal
- installing new method into given class

This is a simple and straightforward rewrite to replace all global
references used by compiler (like Array new: x), with messages sent to
environment (like env createArray: x)  for creating new objects:
strings, arrays, methods.
An environment object could pick proper classes for creating new
literals - by using previously generated kernel classes.

> Next, find a way of dealing with two issues: a) adding the compiled method
> "properly" (e.g., deal with symbol interning and modifying
> MethodDictionaries) and b) global name lookups performed by the compiler
> (since the image is prototypical we can't have it send actual messages; not
> even simulated ones ;-)
>

- not an issue. You creating a new MethodDictionary by sending a
(clonedSystemDict at: #MethodDictionary ) new , or 'environment
newMethodDictionary'.

> The latter issue is the only one that doesn't seem completely obvious which
> is why I would advocate that a bootstrap kernel mustn't use class variables
> or shared pools (in which case the lookup is again trivial since you know
> all the possible names from compiling the original structure).

This not an issue - all Pools, Globals could be created in same way as
everything - as instances of corresponding 'anonymous' classes.

> Lastly, do the bootstrap: Instantiate the first process, its first context,
> the first message. Run it in the simulator to set up the remaining parts of
> the kernel image (Delay, ProcessorScheduler etc).

same thing, except you don't need to simulate it (if you did
everything right, of course) - just send messages.

In result you will receive a fully isolated object graph, located in
same object memory. Except one thing - symbols, because we using same
symbols as in original image.
This is not a problem - we will substitute a Symbol class to new one,
during final cloning stage and include all symbols into new image.
An unused symbols will die by themselves, after few GCs running within
new image - because they are not referenced by anything except
SymbolTable.

--
Best regards,
Igor Stasenko AKA sig.

On Wed, 06 Aug 2008 22:04:10 +0200, Andreas Raab wrote:

> Igor Stasenko wrote:
>> The process of picking objects, dealing with unwanted references,
>> cutting an object graph - all this is on hands of developers.
>
> And of course, all of this "picking objects, dealing with unwanted  
> references, cutting object graphs" is exactly why this process has  
> nothing in common with creating an image from first principles.

What Igor decribes is indeed usable for doing such things, logically  
cutting an object graph out of the existing one, do one or two </grin>  
substitutions, then put it to work in another Hydra thread+heap.

But [what he describes] is also sufficient for creating a new class  
hierarchy (other metaclass concept anybody? traits anybody), with  
supporting instances created from themselves, with no backpointer into  
whatsoever, and then putting that object graph to work in another Hydra  
thread+heap. This view on the very same thing is perhaps of more interest  
to you.

And when looking to put first principles to work, the second view is what  
you want (I think so). Especially the "no backpointer into whatsoever"  
facility is offered in an elegant and typically smalltalkish way. The DSL  
is Smalltalk (what else?), no strange file format to care about, no bit  
level/header fiddling to care about. Just stay at the Smalltalk level,  
limited only by the currently running VM.

> It is just transforming one mess into another and not all what I am  
> after.

I think that the mess would be the result of the application of the  
proposed methods for arriving at the new image ;)

Only those things that are part of the contract with the currently running  
VM must be taken care of, and that is independend from how one would  
arrive at a new object graph.

Of course when one wants changes to the object/header format and other  
such things (better hash values, anyone?), one also wants the  
corresponding changes in the VM, but this would break compatibility.

/Klaus

 
> - use a ClassBuilder, or add single method to Behavior to be able to
> create the abovementioned classes, but without installing/registering
> them anywhere (SystemDictionary etc) and treat them as anonymous
> classes.
>  
This sounds like what SystemEditor does

Keith

2008/8/7 Keith Hodges <[hidden email]>:
>
>> - use a ClassBuilder, or add single method to Behavior to be able to
>> create the abovementioned classes, but without installing/registering
>> them anywhere (SystemDictionary etc) and treat them as anonymous
>> classes.
>>
>
> This sounds like what SystemEditor does
>

Then the better, because you don't need to reinvent the wheel - things
already at your disposal.
The only requirement is that newly created object should not
reference, by occasion to unwanted object,
this helps a lot for generating an isolated objects graph.

> Keith
>
>
>



--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
This doesn't work (try it sometime). It is impossible to create an empty
metaclass hierarchy since you can't send any messages to it. Which is
why you need a simulator to do it because the simulator can operate on
the data structures without requiring any of the objects to understand
any message. Most of the steps in your proposal have similar fundamental
flaws (like creating "new" SmallInteger instances etc).

FWIW, I've followed a similar set of ideas for a while back in 2002 and
the end result was dead-ugly and impossible to bootstrap cleanly. Every
step of your proposal is a mine field and the only recommendation I have
is to try it sometime and you'll be *amazed* how difficult the process
is that you are describing.

Cheers,
   - Andreas

2008/8/7 Andreas Raab <[hidden email]>:
Oh, come on!
Not sure if it will work, but hey:

Behavior subclass: #BootsrappingBehavior .

Which having special 'intercepting'  #basicNew and #basicNew: method
with something like:

| newObject |
newObject := super basicNew.
newObject primitiveChangeClassTo: (Substitutions
findOrCreateSubstitutionOf: self).
NewHeap add: newObject.
^ newObject

and then:

ClassDescription superclass: BootstrappingBehavior.
Behavior flushCache.

".. now you can run arbitrary code, and all objects created during it
will eventually find themselves in NewHeap and already with proper
class set.

At the end, you reverting hack:
"

ClassDescription superclass: Behavior.
Behavior flushCache.


Another thing, that you can populate method dicts on the fly while code running:

[ newObject some code involving sending potentially unknown messages
to an object which class having empty method dict ] on:
MessageNotUnderstood do: [:ex |
    (NewHeap findAndCompileAndInstallMethodForMessage: ex message
receiver: ex receiver) ifTrue: [
      ex return: ex message value. ] ifFalse: [
    ex pass. ]
].


> FWIW, I've followed a similar set of ideas for a while back in 2002 and the
> end result was dead-ugly and impossible to bootstrap cleanly. Every step of
> your proposal is a mine field and the only recommendation I have is to try
> it sometime and you'll be *amazed* how difficult the process is that you are
> describing.
>

I like to be amazed and i like to be challenged :)

> Cheers,
>  - Andreas
>


--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote:
Your line of argumentation reminds me of the old S. Harris cartoon:

http://www.sciencecartoonsplus.com/pages/gallery.php

The problem is that you simply cannot have an uncontaminated environment
without the simulator. It is trivial to show: Since you cannot
manipulate objects without sending messages, you will *necessarily* have
to send messages from the "old" to the "new" objects while the new
environment is being constructed. This *necessarily* implies that the
classes, metaclasses, literals, and methods of the "new" environment
will start out as instances of the "old" environment. There is simply no
way around this.

And that ultimately means that what you're creating is just a (modified)
clone of the old environment not an environment that I would consider to
be created from "first principles" (note that I'm not saying that such a
clone might not be useful, I'm just not interested in yet another
cloning approach).

Cheers,
   - Andreas

> The problem is that you simply cannot have an uncontaminated environment
> without the simulator. It is trivial to show: Since you cannot
> manipulate objects without sending messages, you will *necessarily* have
> to send messages from the "old" to the "new" objects while the new
> environment is being constructed. This *necessarily* implies that the
> classes, metaclasses, literals, and methods of the "new" environment
> will start out as instances of the "old" environment. There is simply no
> way around this.

I do agree that it's more complicated than it seems, but I'm not sure I
agree with your entire reasoning.  If your new image is only "growing
methods and classes" until it becomes self sufficient (so that you can
start it in a new VM, and a Process stored in the ProcessorScheduler
singleton will finish the initialization), then it may work.

My design pillars would be:

1) limit to the bare minimum the amount of classes from the creator
image, that are used in representing the new objects.  Use the creator
image's ObjectMemory as nothing more than malloc.

For example, new-side objects could be represented in the creator image
with an Array or with another class that has the right kind of instance
variables, e.g. a ByteArray.  Better yet, you can have your own class
that has indexed instance variables and derives directly from Object or
even ProtoObject.

If you want any kind of polymorphism between creator-side and new-side
classes, you should do that with adaptors (this doesn't mean that
indiscriminate usage of adaptors to rely on creator-side code is good --
more on this later).

2) you *can* even use modified tools from the creator image, such as the
compiler to compile methods for the "new" side, but only reuse tools in
the creator image if they have a clear input and output.

For example, all a compiler needs is a symbol table, and you can build
the symbol table from the Array representation of new-side classes.  All
it spits out, dually, is literals and bytecodes (more or less...), so
you also have to put in place the machinery to move this output from the
"creator" side to the "new" side.  It can be boring and it is
complicated, but it is "only programming" once you get the design right.
  The interesting thing is that if your needs change, you can also
choose to rely less on the code already in Squeak and write your own
compiler.

On the other hand, I think reusing code for class creation would do more
harm than good.

3) Plan in advance when your image will be self-sufficient.  True, you
can snapshot the creator image, do more work, and create your new-side
image again.  But you cannot just "reopen" an image that has already if
you have no compiler and no object serialization (supporting file or
network input) in the new image, you will have a hard time compiling any
there.

Paolo

On Wednesday 06 Aug 2008 3:44:43 pm Igor Stasenko wrote:
> P.S. if you have noticed, the way how new object memory created is
> very similar to http://en.wikipedia.org/wiki/Cell_division
> The implementor don't need to care about object formats, different
> bits, etc etc - he just needs to designate a full set of objects which
> should appear in new object memory
I think the original question about creating an image from first principles
was about transmutation, not cloning. How does one create a Smalltalk
environment (i.e. an image) starting with an environment that has only
imperative programming tools (e.g. C/C++, Forth etc.)? What is sought is a
process that can be replicated by anyone proficient in the imperative
environment.

Subbu

El 8/7/08 9:18 AM, "K. K. Subramaniam" <[hidden email]> escribió:

> I think the original question about creating an image from first principles
> was about transmutation, not cloning. How does one create a Smalltalk
> environment (i.e. an image) starting with an environment that has only
> imperative programming tools (e.g. C/C++, Forth etc.)? What is sought is a
> process that can be replicated by anyone proficient in the imperative
> environment.
>
> Subbu


Wondering nobody say nothing about PDST (Public Domain Smalltalk) yet .
Maybe is not a real Smalltalk, but shows how you could do exactly such
thing.
My idea of "Class Repository" I have in SqueakLightII comes from it.
Maybe you could mix the two things and have a minimal like Ale do with Fenix
and I call the Huevo.
And then this Huevo could "learn" from repository, exactly same
SqueakLightII "learn" from web the classes I rip from 3.10.
Very bad nobody says nothing and no feedback.
Maybe is too crap ?
Edgar

On 7-Aug-08, at 5:18 AM, K. K. Subramaniam wrote:
>>
> I think the original question about creating an image from first  
> principles
> was about transmutation, not cloning.

The SystemTracer can easily create new images from specs rather than  
'merely cloning' an existing image. It writes bits into a chunk of  
WordAray whic is then written out in a usable format. It would be  
trivial to provide a primitive that writes the new image memory to  
another process in a HydraVM instead of writing to a file. Cloning  
simply uses an existing image as a spec. There is nothing to prevent  
us using xml or some other horrific format as a spec to generate a  
completely from-scratch image via the tracer.

> How does one create a Smalltalk
> environment (i.e. an image) starting with an environment that has only
> imperative programming tools (e.g. C/C++, Forth etc.)? What is  
> sought is a
> process that can be replicated by anyone proficient in the imperative
> environment.

Why waste time using crappy tools. We already have working Smalltalk  
systems. It would be as silly as me replicating the work where I  
manually created stub images for testing back in 1987.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Fractured Idiom:- MERCI RIEN - Thanks for nothin'.

2008/8/7 Andreas Raab <[hidden email]>:
Yeah, this discussion worth very little without practical and working examples.
Lets then wait till i have a working example - the best argument.

> The problem is that you simply cannot have an uncontaminated environment
> without the simulator. It is trivial to show: Since you cannot manipulate
> objects without sending messages, you will *necessarily* have to send
> messages from the "old" to the "new" objects while the new environment is
> being constructed. This *necessarily* implies that the classes, metaclasses,
> literals, and methods of the "new" environment will start out as instances
> of the "old" environment. There is simply no way around this.
>

So, what is wrong with it?
A literal, like string carries just a buch of bytes. Unless you change
the object memory format, you will get the very same object at the
end.
An object who referencing to other objects can be pruned to contain
references only to objects in "new" environment.

Things can be contaminated if compier & image-building tools do not
creating objects directly but instead using an abstract environment
for this.
In this way, a Compiler is not responsible from creating new objects
(CompiledMethod, literals etc) - but environment object instead.
And depending on environment you can instantiate new objects in same
object memory or 'instantiate' them in simulator's bytearray.

I've used this model of compiler who speaks with environment to
bootstrap & instantiate a simulated object memory in CorruptVM
project.
Needless to say, that it works well and producing a functional object
memory as result, completely independent from environment where it
created (in a sense that it knows nothing about things which liying
outside it).

> And that ultimately means that what you're creating is just a (modified)
> clone of the old environment not an environment that I would consider to be
> created from "first principles" (note that I'm not saying that such a clone
> might not be useful, I'm just not interested in yet another cloning
> approach).
>

If we envision a process of creating new image as:

a) defining object formats
b) defining a set of objects which will be included in new image &
relations between them

then unless you changing formats, you can trivially use the very same
'old' heap for holding new objects - i see nothing wrong with it. In
the end what the difference between a bunch of bytes lying in VM's
heap and bunch of bytes lying in simulator's bytearray?


> Cheers,
>  - Andreas
>

--
Best regards,
Igor Stasenko AKA sig.

On Thu, 07 Aug 2008 17:15:12 +0200, tim Rowledge wrote:

Yeah, that was the thought behind the discussion with Igor, thank you for  
mentioning it.

> Cloning simply uses an existing image as a spec.

Hhm, the way this reads to me, partial "cloning" of a subsets of objects +  
substituting some of them means something incompatible (horrible?) versus  
what SystemTracer => HydraVM would do in sequence. What would be an  
understandable, acceptable term for it?

/Klaus

+1

> tim
> --
> tim Rowledge; [hidden email]; http://www.rowledge.org/tim
> Fractured Idiom:- MERCI RIEN - Thanks for nothin'.
>
>
>
>

2008/8/7 tim Rowledge <[hidden email]>:
Apart from ability to change object formats, a SystemTracer don't give
us the ways how you can truncate an unwanted stuff from current image
to produce new, smaller one.
In either case, you have to deal with this problem yourself - by
providing an algorithms for bisecting/populating object memory with
the only stuff which you want.
What i think don't needs the proof ,  is that such algorithms can be
completely abstracted from the media which will hold a new object
memory, because their main purpose is to establishing a correct
relationships between objects - they don't need to know about any
bits/formats.


--
Best regards,
Igor Stasenko AKA sig.

On Thursday 07 Aug 2008 8:45:12 pm tim Rowledge wrote:
> On 7-Aug-08, at 5:18 AM, K. K. Subramaniam wrote:
> > I think the original question about creating an image from first
> > principles
> > was about transmutation, not cloning.
>
> The SystemTracer can easily create new images from specs rather than
> 'merely cloning' an existing image.
SystemTracer is a Smalltalk utility. So it does not qualify as a transmutation
tool. The quest is to bootstrap a Smalltalk system (VM and image) from more
basic primitives. We know it is possible for the VM, but is it possible for
the image too?

> > How does one create a Smalltalk
> > environment (i.e. an image) starting with an environment that has only
> > imperative programming tools (e.g. C/C++, Forth etc.)? What is
> > sought is a
> > process that can be replicated by anyone proficient in the imperative
> > environment.
>
> Why waste time using crappy tools...
Mmm.. Why do the tools and utilities required to build a VM, garbage
collector, primitives and plugins suddenly become "crappy" when building an
initial image? Why is building an initial image using conventional
programming environment a reprehensible idea? I am confused.

Subbu