proj-oot-ootAssemblyNotes8

https://en.m.wikipedia.org/wiki/Find_first_set gives more info on why count trailing zeros (ctz) and count leading zeros (clz) are popular operations; they are related to log base 2.

---

why have meta bits in the graph data representation, rather than only having meta bits in access fns, eg in the arguments to whatever we ops we have in program code to mimic __get and __set? b/c we want graph to be able to 'modify' accesses, ie, views, ie we want a node to be able to have an edge whose target is not just another node, but the 'meta view' of that other node.

---

so is the stuff i'm think of meta level 3? stuff like the 'metagraph'? no, actually, right now i think that stuff is still just meta level 2. Recall, metalevel 1 ('hyper') is 'a message about a message', metalevel 2 ('meta') is 'a message about the connection between (a message about a message M) and the underlying/target message M; metalevel 3 is about the metalevels, that is, the relation between metalevel1 and metalevel2. Now, you could say that the metagraph is itself metalevel3 because it may contain nodes representing 'views' corresponding to different meta-levels. But it probably contains a node representing a view for metaedges; and another node representing a view for meta-meta-edges. This is distinct from having one node representing 'hyper' and another node representing 'meta'. Also, metalevel 2 already contains the concept of an edge that points to an edge. Also, recall that metalevel 3 is analogous to perspective, eg the way that a 2-d perspective view of a 3-d scene has converging lines to cram 3-d information into 2-d in a 'bent' way; which is analogous to 'rotating' information and presenting it in different ways; a single 'metagraph' doesn't seem to contain this (although perhaps if there were ways to transform the metagraph in various ways to represent metainformation in different ways, such as transforming from a representation in which (there is one node representing a view with metaedges and another node representing a view with metametaedges) into a representation in which (there is one node representing metalevel1 and another node representing metalevel2...).

Similarly, one might think that the 'metagraph' is in fact metalevel4 because it contains many levels in one graph, but i don't think it is, as level 4 is supposed to be even further out there than level 3, and in fact is supposed to possibly generate/include new metalevels.

---

We only allow 12 bit operands in instructions. We are a '16-bit' system; however it is possible for the actual memory to be larger than 2^16, and for the (opaque) pointers to be implemented as larger than 16 bits. However, the 12/16 difference suggests that on at least some naive or small implementations, there will be 4 bits 'left over' in some cases. We could use these as type tags or 'fat pointer' bounds checks [1].

How would we use these 4 bits? How does Haskell GHC use pointer tagging? Who else does that?

---

" nabla9 5 hours ago

Memory allocation feature asked is not a language feature. It has to be baked into web assembly if you want to use portable byte masking with pointers.

It's very low level implementation level detail that enables fast execution of dynamically typed languages. Boxing has high cost and it consumes memory. Type tags embedded in pointers can be very fast. For that to work, you need objects that are aligned with power-of-two byte boundaries.

Adding this feature enables efficient execution strategy for scripting and dynamic languages.

reply "

---

i guess if we only had 4 types, Parrot's "INSP" is a good bet: integers, numbers (floats), strings, other. We could also replace 'floats' with either 'boxed' or 'pointer (reference)' or 'native pointer' or 'dyn'.

---

XPC primitive types:

• Data
• Boolean
• Double
• String
• Signed Integer
• Unsigned Integer
• Date
• UUID
• Array
• Dictionary
• Null

-- [2]

---

some random ideas on what it might take to make an IL (such as WebAssembly?) readable:

http://wllang.com/ https://github.com/wllang/wll

---

"Usually, a method accepts either a string or a number or a function or an object, etc" [3]

---

created ootVm.txt; moved old proposal from ootAssemblyThoughts to below this; copied current proposal from top of ootAssemblyNotes7.txt to ootVm.txt.

todos:

• add proposed list of ops

---

perhaps we put Java-esque restrictions on the data stack for safety? We still need to permit call stack manipulation though, so the HLL can easily implement continuations.

A different strategy would be to let the language implementation do whatever it likes, and only check user code libraries for stack safety restrictions.

todo

---

OLD proposal from ootAssemblyThoughts.txt moved to here (new version copied to ootVm.txt):

motivations and goals

The idea here is that Oot might have 3 well-defined compilation stages:

Oot -> Oot Core -> this Assembly/Bytecode -> platform-specific code

"Oot" would be the high-level language. It would be built from Oot Core using Oot Core's metaprogramming facilities.

The rationale for Oot Core is:

• to conceptually highlight which high-level operations are important in the language (for example, in Haskell we see that things like partially applied functions, closures (let-bound stuff), variables applied to arguments, and generic thunks are all pretty 'core')
• to focus implementation effort around these without worrying about VM impedence mismatch until the next level down

The rationale for Oot Assembly is:

• to inspire me with ideas for Oot Core 'from the bottom up'
• to make porting Oot easier
• to make the implementation of Oot Core easier to read by providing an additional layer decoupling the implementation of Oot Core constructs from platform-specific details

Oot Assembly will make porting Oot easier by:

• providing a small, compartmentalized language; all a porter needs to do is (a) implement the interpreter loop, (b) implement each opcode, (c) execute the reference implementation of Oot Core (which will be compiled to Oot Assembly) on top of the VM they've built

Some properties we want Oot Assembly to have:

• easy to implement
• simple
• portable, abstracted from implementation details
• a small set of opcodes, to ease implementation and to keep it simple
• preserve higher-level intent (expressivness)
• highly customizable
• cross-platform preprocessing that must be done in any case should be done at a higher level above Oot Assembly; for example, Oot code must be parsed before Oot Assembly is generated
• administrative automation such as garbage collection, lazy control flow, greenthread, and copy-on-write should be done at a lower-level beneath Oot Assembly, but should be exposed as primitives via Oot Assembly opcodes
• parallelizable decoding (this is why we align to fixed-length chunks)
• linear (but perhaps it should support more general graph shapes, too?)
• support for annotations
• efficient emulation
• targetting a world of 'brain-like computers' with tens of thousands or more CPUs (or at least virtual threads or 'kernels'), each of which have a small amount of attached local memory

Some things that many traditional assembly languages do that we don't:

• fixed length instructions
• purely linear
• purely imperative

What do we mean by 'preserve intent', and why do we want that?

What we mean is "don't map a specific operation S to a special case of a general operation G if, by looking at the result in the form of G, you cannot discover that this is actually S without doing non-local analysis".

Some examples:

• we use 3-operand instructions, and memory-to-memory (rather than registers), in order to make the code more closely match its meaning (e.g. not obscure "c = a + b" by having MOVs in the middle of it). In particular, we want to make it so that, often, when there is one variable at the source code level, that translates into one particular memory location in the Oot Assembly level, rather than translating into a bunch of different memory locations with MOVs etc in between them (ie need for inessential register transfers).
• having a way to explicitly state that an output value is 'discard'ed
• forcing jumps to use specific instructions (as opposed to just writing to the PC)

There are three reasons to 'preserve intent':

• to defer platform-specific optimization choices (eg if many platforms provide a primitive that efficiently implements a high-level construct, it would be a shame to instead use a slow reimplementation in Oot Assembly code of that same construct; better to have that primitive be a single Oot Assembly bytecode)
• to make it easier to write quick-and-dirty program analysis
• elegance/readability

Efficiency: We want Oot Assembly to be reasonably efficient to interpret; however, efficiency should not be at the expense of preservation of intent or customizability. We expect that performance-minded platform-specific implementations might compile Oot Assembly into custom high-performance bytecode formats anyways.

Examples of the consequnces of this choice:

• use of a variable length encoding (in this case, customizability trumps efficiency)
• mostly linear encoding (for efficiency)
• separate opcodes for the same operation on different types, rather than polymorphic opcodes and a separate type field (for efficiency)
• we don't precompute platform-specific addresses at compile-time, because we want to stay portable (but maybe at link-time?)

current proposal

note: as of 201602 this has been superceded by the proposal in ootAssemblyNotes7.

Design goals

Ease of implementation

(Massively) parallelizable decoding

supports linear instruction stream; also optionally supports tree structure

Message constituents with a hard upper bound on their length in bits (in this case, 32 bits is the upper bound of werds, and the payload is max length of 24 bits)

supports at least 12-bit addressing (in fact, we support 24-bit addressing, although using some addressing modes on operands of more than 12 bits requires two instructions)

Preservation of HLL intent

Extensibility

note: efficiency is NOT a primary design goal; as with the Dalvik encoding of JVM bytecode, or the LuaJIT?