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

On Sat, 09 Aug 2008 05:10:48 +0200, K. K. Subramaniam wrote:

...
> I can understand why someone may not wish to go so far into the past  
> that they
> cross the point of singularity (when the first image came into  
> existence).

Odds are that you will never achieve this: take an arbitrary computer  
system, with nothing on disk and nothing in memory after power on. You're  
allowed to choose one with the most convenient instruction set ever  
created on this our planet.

Your job: boot a compiler with which every program, which until then was  
not compiled by the compiler, is to be replaced (so that the pre-compiler  
area things can be eliminated).

Many/most of the historical records of the "pre-replacement" things are  
not available, for various reasons in the previous century, often because  
of the competive edge of enterprises and individuals.

That's the nature of the exercise, be it for an .image or whatsover.

/Klaus

 > > > what is so mysterious ;-) in a image that can't be captured in an
 > > > imperative environment?
 > >
 > > Nothing. (And I think you meant "declarative".)
 > >
 > > We're haggling over a matter of motivation at this point
 >
 > I can understand why someone may not wish to go so far into the past
 > that they cross the point of singularity (when the first image came
 > into existence).

      I was referring to the level of sophistication of the tools used,
not of the subject object memory. Neither constrains the other.

 > But the knowledge about how to create the primordial soup should not
 > be lost into oblivion. SystemTracer can be a source but should not be
 > the only source.

      It isn't. I've done all my Spoon work so far without it, for example.

 > ...if the primal image is so complex that it requires jiggery pokery
 > perhaps it is time to apply Occam's razor to it.

      Check out [1], with its explanation of each object. The smallest
object memory itself is quite simple, even if the process by which it
was composed is not (yet). Of course, that object memory is not useful
in itself, only as a demonstration of the process.

      I happen to be interested in creating object memories which are
self-sustaining (growable), rather than one-off object memories suitable
only for specific predetermined tasks. So the real question for me is:
for an object memory which is self-sustaining after creation, where is
the optimal compromise between "primal" (small) and useful? I don't
think anyone has ever answered that question before, not at PARC and not
since.

 > BTW, I meant imperative *environments* (OS platforms like Linux, Unix
 > or Windows). The image itself can be declarative.

      That made no sense to me; I don't think it really matters, so I
think we should drop it.


-C

[1] http://netjam.org/spoon/smallest

--
Craig Latta
improvisational musical informaticist
www.netjam.org
Smalltalkers do: [:it | All with: Class, (And love: it)]

Tony

I'm really interested into that.

>> Have a look at the bootstrapping process for Slate, starting  
>> perhaps with http://slate.tunes.org/repos/stable/src/mobius/vm/bootstrap.slate 
>> . The fact that the program is written in Slate does not detract  
>> from what the program does, which is (if I remember rightly!) to  
>> build and serialise a model of an image that does not rely on any  
>> characteristics of the host language.

Can you elaborate a bit more on the slate bootstrap process?

what is Image?

Stef

On Aug 9, 2008, at 11:41 AM, Tony Garnock-Jones wrote:

On Saturday 09 Aug 2008 4:03:48 pm Klaus D. Witzel wrote:
> > I can understand why someone may not wish to go so far into the past  
> > that they
> > cross the point of singularity (when the first image came into  
> > existence).
>
> Odds are that you will never achieve this: take an arbitrary computer  
> system, with nothing on disk and nothing in memory after power on. You're  
> allowed to choose one with the most convenient instruction set ever  
> created on this our planet.
I have done this on a computer (that looked somewhat like Altair 8800) in the
early 80s. All it had was a bank of LEDs and toggle switches (for address and
data input). On power-up, I had to load a small tapeloader program using the
switch bank to setup the i/o subsystem and then read in the rest of the code
from a paper-tape. Then I could enter commands on a teletypewriter (tty) to
bootstrap the rest of the environment. There was no disk, so a power failure
or brownout would put me back in square one.

I know first hand what Alan Kay means when he avers, 'hardware is software
frozen too soon'. To me, the most interesting transition is the one where we
move from a VM to VM+image.

Subbu

On Mon, 11 Aug 2008 16:54:07 +0200, K. K. Subramaniam wrote:

I happen know many people who have done that, in my team and at other  
sites. With varying input media (punched film for the Z3).

> I know first hand what Alan Kay means when he avers, 'hardware is  
> software
> frozen too soon'. To me, the most interesting transition is the one  
> where we
> move from a VM to VM+image.

I could email you a spec for a Smalltalk *) system (if you had none or  
want it).

The *first* transformation can be a subroutine of the VM (or of what it  
interprets: boot; boot {; boot} ;) , present as long as you still have  
those bugs ;) Thereafter you no longer need to compile that subroutine  
into the VM. But it can be a very small subroutine, which just reads a  
bytecode method.

For me code is code and VM is VM, for the initial transition, and I cannot  
see much difference when (re-)doing some initial transformation in the  
Smalltalk language itself, instead in any other language. Even in C and  
ASM you can code like you had method dictionaries and oops and #classOf:  
and function pointers -- it's a matter of style and elegance ;)

> Subbu

*) includes compiler and the full object supporting machinery, does GUI  
with primitives, has:

- 52 classes + their meta/dual
- 510 compiled methods
- 510 bytearrays (methods' bytecode)
- 713 arrays (mostly for method collections)
- 595 strings (mostly for class names + selector names)
- 22 character literals #($' $0 $9 $a $z $A $Z $$ $: $. $  $( $) $] $| $-  
$> $^ $[ $< $# $")

Comparing to its source code one can see that the compiler allows many  
more symbols for binary selectors ;)

/Klaus

Klaus D. Witzel wrote:
> I could email you a spec for a Smalltalk *) system (if you had none or
> want it).
>
> *) includes compiler and the full object supporting machinery, does GUI
> with primitives, has: [...]


That sounds really interesting! Can you make it publicly available?

Tony

On Sunday 10 Aug 2008 2:02:53 pm Craig Latta wrote:
>       I happen to be interested in creating object memories which are
> self-sustaining (growable), rather than one-off object memories suitable
> only for specific predetermined tasks. So the real question for me is:
> for an object memory which is self-sustaining after creation, where is
> the optimal compromise between "primal" (small) and useful? I don't
> think anyone has ever answered that question before, not at PARC and not
> since.
I like Spoon's minimalist approach. To me, a primal machine (VM+image) is not
necessarily the smallest machine. It is the smallest that has enough objects
to create a better machine. If the knowledge about creating a primal image
can be encoded in the VM itself, then when squeak is started without an
image, a primal image can be generated on the fly and the programmer can
build a better image.

An analogy is http://www.annexia.org/forth that shows how to bootstrap a
FORTH "machine" starting with a simple (physical) machine with very few
primitives (not even a GC) in about 2000 lines. It is written in x86 assembly
but is small enough for a single programmer to comprehend. Anyone who wishes
to bootstrap a FORTH environment can read it, understand it, port it to a
target machine and build better FORTH environments (including a GC memory
allocator).

Subbu

Hi Tony,

on Mon, 11 Aug 2008 18:01:10 +0200, you wrote:

> Klaus D. Witzel wrote:
>> I could email you a spec for a Smalltalk *) system (if you had none or  
>> want it).
>>  *) includes compiler and the full object supporting machinery, does  
>> GUI with primitives, has: [...]
>
> That sounds really interesting! Can you make it publicly available?

- http://squeak.cobss.ch/ImageSpecs/image.version0.82.bits.html

That page contains a short description and the data, let me know when  
something is missing or not clear.

/Klaus

> Tony
>
>

Hi Klaus,

Klaus D. Witzel wrote:
> - http://squeak.cobss.ch/ImageSpecs/image.version0.82.bits.html
> That page contains a short description and the data, let me know when
> something is missing or not clear.

I like it a lot! I've had a bit of fun throwing together a wee program
to explore it (hideous python script attached). I have some questions
for you:

1. It seems like there are two representations of SmallIntegers, e.g. "0
5" and "83 500" for 5 and 500, respectively. Do I have that right? Why
is it done that way?

2. Why do sometimes the number of instance variables not line up with
the number declared in an object's class? For instance,

  MetaApplication has 6 instvars, but Class claims its instances have 5
  MetaColor has 6 instvars, but Class claims its instances have 5
  MetaImage has 6 instvars, but Class claims its instances have 5
  MetaPoint has 6 instvars, but Class claims its instances have 5
  String has 6 instvars, but MetaString claims its instances have 5

3. Why are Chars represented specially? Couldn't they be represented in
the same style as Methods?

4. Why are False, True and Undefined represented specially? Couldn't
they, too, be in the same style as Methods?

5. Why don't all the rows have "0 -1" as the final two columns, if they
have no special instances?

And finally, I have a suggestion: if each row had an indication of how
many fields to expect before the human-readable name and the instance
data, that'd make parsing simpler. Alternatively, removing the
human-readable text and simply putting ":" or something to delimit the
instance data from the other data would be an improvement.

What led you to produce this artifact? It's very interesting.

Regards,
   Tony


# for reading image.version0.82.bits.html data

import sys

class K:
    def __init__(self, row):
        self.row = row
        self.index = row[2]
        self.classnum = row[0]
        self.instvars = []
        self.instances = []
        i = 1
        while type(row[i + 1]) is int:
            self.instvars.append((row[i], row[i+1]))
            i = i + 2
        self.humanname = row[i + 1]
        i = i + 2
        if i >= len(row):
            return
        numinsts = self.row[i]
        i = i + 1
        if numinsts == -1:
            self.instances.append('special' + self.humanname)
        else:
            if self.humanname in ['Array', 'Method']:
                self.parsearrays(i)
            elif self.humanname == 'Char':
                self.parsechars(i)
            else:
                self.parsebytes(i)
            if len(self.instances) != numinsts:
                print 'eek', len(self.instances), numinsts, self.humanname

    def parsearrays(self, i):
        while i < len(self.row):
            instlen = self.row[i]
            if instlen == -1:
                break
            i = i + 1
            pointers = self.row[i : i + instlen]
            inst = []
            x = 0
            while x < len(pointers):
                inst.append((pointers[x], pointers[x+1]))
                x = x + 2
            i = i + instlen
            self.instances.append(inst)

    def parsechars(self, i):
        while i < len(self.row):
            c = self.row[i]
            if c == -1:
                break
            self.instances.append('char' + chr(c))
            i = i + 1

    def parsebytes(self, i):
        while i < len(self.row):
            instlen = self.row[i]
            if instlen == -1:
                break
            i = i + 1
            inst = self.row[i : i + instlen]
            if self.humanname == 'String':
                inst = ''.join(chr(x) for x in inst)
            i = i + instlen
            self.instances.append(inst)

    def resolve(self, resolver):
        self.classobj = resolver(self.classnum)
        self.instvars = [resolver(t) for t in self.instvars]
        if self.humanname in ['Array', 'Method']:
            for inst in self.instances:
                for i in range(len(inst)):
                    inst[i] = resolver(inst[i])

    def check(self):
        if len(self.instvars) != self.classobj.instvars[3]:
            print 'eek'
            print self.humanname, len(self.instvars), self.classobj.humanname, self.classobj.instvars[3]
            print self.instvars
            print self.classobj.instvars

def load(f):
    lines = [line.strip().split() for line in f.readlines()]
    for row in lines:
        for i in range(len(row)):
            try:
                row[i] = int(row[i])
            except ValueError:
                pass

    specials = lines[0]

    o = []
    for row in lines[1:]:
        o.append(K(row))

    def resolver(t):
        print t
        if type(t) is int:
            return o[t - 1]
        else:
            (c, i) = t
            if c == 0:
                return i
            elif c == specials[8]:
                return 'smallint' + str(i)
            else:
                return o[c - 1].instances[i - 1]

    for v in o:
        o[v.classnum - 1].instances.append(v)

    for v in o:
        v.resolve(resolver)

    for v in o:
        v.check()

    return o

def r():
    f = file('image.version0.82.bits.csv')
    o = load(f)
    f.close()
    return o

Hi Stef,

I hope the following is of interest to you and other readers :-)

stephane ducasse wrote:
> what is Image?

Defined in src/lib/image.slate. Now, it's been a long time since I read
much slate, so please forgive any mistakes I make in reading the code.

Image is a singleton that is the chosen place to hang methods and non-VM
state related to the current, running image: for instance, command-line
options (??) and startup and shutdown actions.

So it has a role in everyday operation of a slate system.

It *also* has a special, but coincidental, role when bootstrapping a new
image from sources, in bootstrap.slate. However, the bootstrap.slate
code could have been hung anywhere: Image was simply convenient and
mnemonic. If you look at bootstrap.slate, notice how "Image" is never
(other than in the first line) used alone: it's always used as "Image
Bootstrap".

Now, Image Bootstrap contains tools for modelling an image. The tools
are completely VM-independent. For example, "Image Bootstrap
BytesPerWord" describes the model's notion of how many bytes there are
in a machine word, that may be different to the number of bytes per word
used by the VM that is running the image-building code.

Within the Image Bootstrap namespace exist

  - Chunk
  - SlotEntry
  - RoleEntry
  - MethodDefinition
  - Map
  - Object
  - Array
  - OopArray
  - ByteArray
  - CompiledMethod

and Generator. All of the above (except Generator) despite confusingly
having the same names as classes/objects in the image-building, running,
system, are completely distinct -- they could perhaps less confusingly
be called "ObjectModel", "ArrayModel" etc, since they *describe* objects
and arrays, without *being* objects and arrays in the running VM instance.

Generator's method "generateImageBooting:withPrims:" is what kick-starts
the whole image-building process.

   gen generateKernel.
   gen generateUtilities.
   gen generateKernelAccessors.
   gen generateInterpreterBooting: method.
   gen generateLobby.
   prims do: [| :assoc |
     gen generatePrimitive: assoc value at: assoc key].
   gen generateMaps.
   gen generateLinkage.

Each step constructs (in an abstract way) and encodes (concretely, for
the a particular model of a VM) models of objects in the model of the
image being built.

Perhaps most interesting is the generateKernel method, which creates the
models of the objects that form the "primeval soup", such as Root,
Boolean, Array, SmallInteger, Symbol, Method etc.

Once the kernel objects are constructed, the system can go on to put the
rest of the system together. It uses a model of the VM that the image is
intended for to compile the methods that go into the image (although I'm
not clear on the exact mechanism in play here).

Tony

Hi Tony,

on Wed, 13 Aug 2008 09:47:52 +0200, you wrote:

> Hi Klaus,
>
> Klaus D. Witzel wrote:
>> - http://squeak.cobss.ch/ImageSpecs/image.version0.82.bits.html
>> That page contains a short description and the data, let me know when
>> something is missing or not clear.
>
> I like it a lot!

I'm happy you like it :) In the below I attempt to answer your questions  
and comment your suggestions (message got a bit longish, sorry ;)

> I've had a bit of fun throwing together a wee program
> to explore it (hideous python script attached).

:) You can make (more) use of the integer constants in line zero, I for  
example have no text/word constants in my spec data reader ;) and the  
extra indices appended behind the text in line zero are for convenience  
only. Another invariant is the position of the Class row and the MetaClass  
row. Together with -1 that this paragraph contains all the axioms ;)

Another interesting and important subproblem is oop reconstruction. Igor  
advised me to make use stubs and I intend to use instances of Association  
(class index -> instance index) for stubs at reader time, which can serve  
as already perfect oop and the be resolved away in a 2nd swoop/slide over  
the rows. That way the time complexity meet O(n+m), space complexity also.

> I have some questions
> for you:
>
> 1. It seems like there are two representations of SmallIntegers, e.g. "0
> 5" and "83 500" for 5 and 500, respectively.

Yes, small integer 5 should be represented by the pair "0 5", the 500 (and  
the 300 right to it) as well. You found a bug (thank you :) which slipped  
through until now! see also next paragraph.

> Do I have that right? Why is it done that way?

When filing in the spec data (initially for a Palm iiiC and Tungsten|C),  
class SmallInteger is not needed for creating instances of it, therefore  
"0 5". And all classes must be initialized with oops for their slots, so  
this recursion is not needed for "0 5" pairs+friends. But the bug slipped  
through because at the time "83 500" is resolved, class SmallInteger  
already exists. The bug will be fixed with the next udpate :)

Note that SmallInteger was renamed from its original SmallInt (not a good  
idea, never change history!), change will be reverted soon. But the "typo"  
fix will be kept in Magnatude's name ;) and Number class' name change will  
also be kept as the convention of the original author wants it for all the  
meta classes.

> 2. Why do sometimes the number of instance variables not line up with
> the number declared in an object's class? For instance,

Let's s/instvars/slots/ for avoiding confusion at this level, thank you.

>   MetaApplication has 6 instvars, but Class claims its instances have 5
>   MetaColor has 6 instvars, but Class claims its instances have 5
>   MetaImage has 6 instvars, but Class claims its instances have 5
>   MetaPoint has 6 instvars, but Class claims its instances have 5
>   String has 6 instvars, but MetaString claims its instances have 5

Compute (aClass class instanceVariables size) for the correct number of  
slots as intended by the original author of the system. Method  
#instanceVariables goes up the superclass ladder as usual and sums the #  
of variables declared by the contributing entities. And class variables  
are instance variables in a class' class, in this system.

You are correct with the other part of your observation, class String has  
indeed 6 slots but has or inherits no class variables, similiar for others  
that you mention. This has historical reasons, the original class builder  
was a human being who has a method for adding variables but no method for  
removing them. So you see some unused (usually nil'ed) slots which could  
be reactivated by increasing the value in the 'size' slot and appending an  
item to the 'variables' slot's oop (an array).

> 3. Why are Chars represented specially? Couldn't they be represented in
> the same style as Methods?

Similiar reason as with SmallInts, the spec data of a Char's code point  
dosn't need to mention the "primordial" code point's class.

Same is so for ByteArrays and would be so for Floats.

> 4. Why are False, True and Undefined represented specially? Couldn't
> they, too, be in the same style as Methods?

There was no intention to represent them specially, its a consequence of:  
the instances of False, True and Undefined are not transferred, they are  
created upon arrival. When -1 was created for "nothing more of this  
instance data can come from this row" it became systematically used for  
indicating the presence of *instances* and as a consequence the absence of  
transfered *data* for instances of False, True and Undefined.

> 5. Why don't all the rows have "0 -1" as the final two columns, if they
> have no special instances?

The -1 signals absence of *more* instance *data*, but also that one or  
more instances *must* be created on arrival. The cases you mention have no  
instances to be created on arrival (for the system to get going properly).

> And finally, I have a suggestion: if each row had an indication of how
> many fields to expect before the human-readable name and the instance
> data, that'd make parsing simpler.

The rows are parsed by a flat loop, like "2 to: remainingFileLength by: 2  
do:", with a single #peek (or equiv.) in it for recognizing the human  
readable, redundant name item (the code here is conceptual level).

In a class based system the nature of what is parsed from spec data must  
tell an oop of another class and its instance -- most of that material is  
found only in other rows (String's class name slot is as exception, also  
SmallInt's size slot and Array's methods slot ;)

There are no other delimiters needed for fully (self-)describing the spec  
data with its own integer pointers, IMO. But if there is something simpler  
(for representation and for parsing) then I'd love to make use of it :)

> Alternatively, removing the
> human-readable text and simply putting ":" or something to delimit the
> instance data from the other data would be an improvement.

And I tought that text/word would make the spec data an interesting read  
;) Well, that text/word is supposed to be there for the convenience of the  
human being whose job title is debugger ;) I won't want to disappoint that  
already hard working person by eliminating ever more clues ;) I hope for  
your understanding :)

> What led you to produce this artifact? It's very interesting.

When the original .image data file was found on the web together with Tim  
Budd's source code for interpreting it (does it in javaneese), the first  
idea that came up was to recompile the system with inserted "I'm here" and  
"now I do that" snippets.

But at that time, no tool-chain was still available for producing a  
code/VM compatible *executable* for reading the data created by same  
tool-chain vendors' own serialization facility: they had "serialization  
data version mismatch" :( And looking for dubious backup copies from sites  
specialized on keeping "copied" material downloadable was ruled out  
because of the commercial status of the tool-chain/VM vendor.

So, luckily the original system does and is Smalltalk and a tracer*) was  
written in it for creating a usable data file with the .image spec, and a  
new #primitive was then written for parsing the spec data from its  
non-textual binary representation. This without basing anything on any  
tool-chain/VM vendors' "version mismatch" options any longer.

The result was then transfered to my Palm iiiC and Tungsten|C for seeing  
it in action, with additions for colors, a browser with #compile, tabbed  
GUI (workspace, browser panes), text selection #doIt and #printInt, on  
those small devices :)

The more actual .image is an update, makes use of the original author's  
new GUI primitives, but still uses the tool-chain/VM vendors' serialized  
representation (it's easy, when it works). Making spec data out of this  
updated .image was not a problem with a tracer who was born in the older  
.image ;)

> Regards,
>    Tony

*) this was quite an experience, max 16 literals per method (including  
selectors, but super selectors could be placed past the 16th literal), max  
16 temps (incl. *all* blocks' args), max 256-1 jump target locations (big  
#while*: loop anybody? nesting blocks a bit deeper anybody? single #if*  
around the remaining method body anybody?)

And, it was and is f-u-n :)

/Klaus

Thanks again everybody,

for your interest in this small piece of information on a web page (seen  
downloaders from so many locations, didn't think it would generate such  
interest :)

---------------

The page has now been updated, fixed things from the previous post  
(SmallInt name, also the class index of SmallInt which should be 0 in a  
class/instance pair of indices).

Thanks again Tony for pointing to that bug with your questions :)

---------------

- http://squeak.cobss.ch/ImageSpecs/image.version0.82.bits.html


The page will see some more updates, as soon and as often as time allows.

/Klaus