see also ootVm.txt; that file is older and needs to be integrated into the list in the following section

---

so i think some stuff that OVM should implement is:

• tail calls
• management of activation frames/stack frames (in some way) (e.g. save them on the heap when they need to escape for closures)
  • so do we introduce the confining stack abstraction here? i think so but am not sure
• "a 'closure' instruction which handles all of the issues related to nested lexical scoping, and the management of activation frames" or something
• serialization/pickling (see SEAM and their graph store (SEAM Abstract Store) for purposes of GC and pickling; for each bit of code they store both "Alice Abstract Code (so that it can be pickled), and also as compiled code (either compiled to bytecode or to native code). Compiled code is represented as binary 'chunk' nodes in the SEAM Abstract Store; since these are opaque to SEAM, the garbage collector can't tell which other nodes they reference, therefore binary code is wrapped by a pair node which contains (points to) both a binary chunk node and also to an "immediate environment" which is a node holding references to other nodes that are referred to by the binary code. Binary code is position-independent in anticipation of being moved around by the garbage collector.")
  • note: this layer can't by itself pickle functions, although it offers facilities for other layers to do so: because that requires some sort of programming language representation -- however, it can be extended to custom node types, so the HLL can define some sort of bytecode or AST representation, and the OVM backend/platform can define native code blobs; so, assuming that the HLL did that, functions can be pickled
  • note: one of the important functions here is to serialize the (probably cyclic) graph of pointers in stuff in memory
• GC/memory management, read/write barriers
  • ownership, e.g. distinction b/t 'move' and 'copy'
  • aliases, value types vs reference types ?
  • finalizers, 'resources' (in the SEAM sense of wrapping of external objects that cannot be fully reified inside the VM's object graph)
• register assignment (on the backend)
• arrays, aggregates, dicts, linked lists/S-expressions
  • and interop with native data structures
• something like futures (see SEAM transients)
• concurrency spawning, synchronization and communication
  • see L4
  • see Golang (channels and Goroutines)
  • see Erlang
• scheduler (note: interacts with I/O because knows not to reschedule a thread waiting on I/O until the I/O completes; also must support nonblocking I/O)
  • see L4
  • see Python event loops
  • since the HLL implementation on the layer above is trusted, we can use cooperative multitasking; the HLL must implement pre-emption if desired
• bounds-checking
• capabilities/sandboxing
  • however, the HLL implementation on the layer above is trusted; this is a service to make it easy for the HLL to implement capabilities, not a sandbox of the HLL implementation itself; does this mean we have an 'ambient authority/ring 0' notion so the HLL can turn off bounds-checking and debug secrets and the like?
  • guaranteed private methods and fields in OOP objects
  • seal/unseal
  • inability to create a reference unless you are given it (e.g. cannot cast an integer to a reference)
• virtualization
• calling conventions
  • interop; glue with calling to/from platform, and with platform globals and other stuff
• do we need to support any OOP stuff?
• polymorphism? parameteric or adhoc?
• expanded set of primitives (e.g. map, reduce); see ootAssemblyOps*
• first class functions? suspended computations (is this different from futures)?
• package management/binary module stuff
  • dynamic loading/importing/linking/hotpatching of modules (mb call them 'components')
• runtime
  • constant tables
• parsing and/or regexps?
• direct compilation possible even to some platforms that Boot can only be interpreted on due to its use of unrestricted indirect jumps to implement a call stack (provided that these platforms provide enough flexibility in terms of stuff like tail calls, first-class continuations, closures, lookup tables, activation records on the stack, etc to do the sort of control flow that we need)
• i guess it has to have structured control flow constructs so that it can support transpilation to native platforms. Should look at Haxe ( https://community.haxe.org/t/how-to-implement-new-haxe-target/1599/4 ).
• copy-on-write
• object model
• laziness?
• promises
• distributed message-passing/mailboxes/calls and 'eventual send'
• channels

todo should also read more about the OOP parts of JVM and CIL. todo should also read about Cmm/C-- runtime support todo update Oot todos

as you can see, the purpose of OVM is coming into focus:

• services e.g. GC that i think are annoying/administrative rather than 'cool semantics'
  • note; these services should be able to be overridden by their platform-native equivalents (e.g. in Python or Java, use Python's or Java's GC if possible). Note that this means that an Oot program can't depend on their exact semantics, since this will vary with platform
• code generation stuff that i think is annoying (eg register allocation)
• primitives
• maybe some optimization?
• interop

but everything should be not very dynamic/metaprogrammable/dynamically typed (remember the lesson from PyPy?), so this is different from Oot Core.

---

Instruction format (128-bit):

1 x 16-bit opcode 3 x (16-bit operand + 8-bit addr mode) 1 x (32-bit operand + 8-bit addr mode)

16 bytes

Note that there is no space for encoding length format bits here -- UNLESS you reduced the opcode by 5 bits to 11 bits. Which isn't crazy. So maybe:

5 encoding length format bits 1 x 11-bit opcode 3 x (16-bit operand + 8-bit addr mode) 1 x (32-bit operand + 8-bit addr mode)

16 bytes

We could also have a 64-bit encoding format:

4 encoding length format bits + 2 RESERVED bits + 10-bit opcode + 4 x (8-bit operand + 4-bit addr mode)

---

i dunno man, this seems like a lot of work to implement in assembly language.

also, what about the idea of incremental implementation? how is the porter going to be able to just implement the bare VM and use existing implementations of most of the opcodes?

i guess some of these things could be compile-time macros (eg hash tables).

but i feel like we really have a couple of levels here.

maybe some/many of these things would be 'standard library functions' at the OVM level (eg hash tables).

hmm, that makes a lot more sense to me. So we would specify a smaller core VM, which has to actually be implemented, and then a large standard library. And then porters would have to implement the VM, and then for better interoperability and efficiency on a given platform they could go ahead and incrementally override parts of the standard library with platform-specific stuff.

another issue is static typing. There's a tension here:

• if this is to be a language designed for IMPLEMENTING another language, like PyPy?'s RPython, then it has to be statically typed
• if this is to be a VM for a RUNTIME of another language, and then language on top is dynamic and supports distributed 'mobile code' and hotswapping/'live coding', then it has to support dynamicity

I think the solution is: (a) some of the dynamic stuff will be in the layer above (in the implementation of Oot Core on top of OVM) (b) there is some dynamic stuff at this level but it is easy to tell from looking at each instruction if it has any dynamicity. For example, if we use my idea for 'polymorphic assembly' by way of a type operand, then instructions whose type operands are constant mode are statically typed. This means that OVM code that is composed only of non-dynamic instructions can be efficiently compiled. And the language implementation itself will be like that.

Still, this suggests that maybe we are trying to do too many things at once.

Should we have one layer for a 'language implementing language', and then OVM is a 'runtime VM' implemented in that language? The problem with that may be that the 'runtime VM' has to support funky control flow like delimited continuations, so we don't want the language implementing language to impose and abstract away something like a restrictive call chain/stack abstraction, because then it seems like we have another interpreter-on-top-of-an-interpreter layer. But i'm not sure i fully understand that part, so that objection could be invalid. todo/hmmm.

My immediate thoughts are that Oot itself may be the 'language implementing language' that the reference implementation is ultimately written in. So when i say 'it's a lot of work to write this in assembly' that's not relevant, because the Oot implementation will be compiled to Boot, we don't have to write it in Boot directly (except maybe once to bootstrap). But is this really true? I don't expect our compiler to be smart enough to write efficient Boot code for things like context switches in the scheduler.

And, in any case we actually want the runtime VM to have the property that it supports dynamic typing yet you can easily identify code with static typing, because this will help JIT'ing, compilers, etc. This is certainly helpful for efficient compilation of a self-hosting implementation of Oot itself, but it'll be helpful for user code as well, because users will be able to write statically typed Oot code, we can use the ordinary toolchain to compile that to OVM, and then the toolchain will be able to recognize that the OVM code is statically typed and compile it down further rather than interpreting it.

---

so here's the design i'm coming up with. It seems odd to me, in that i don't think i've heard of it being done this way before, but it seems to satisfy the considerations noted in the previous section:

OVM is a VM with opcodes.

Some of the opcodes are primitive. A porter has to implement these. For example, BEQ.

The opcodes which are not primitive are 'standard library functions'. These have implementations provided in the language of OVM, in terms of primitive functions (or other library functions; but there are no circular dependencies between library functions, except for self-referencing recursion (a function can call itself)). For example, hashtable_get(table, key). A porter can start out not implementing these and then implement them incrementally later on to improve interoperation and efficiency.

Some of the opcodes, including some (but probably not all) of the primitive ones, and including some but not all of the standard library ones, are (what's the word for this? secured? protected? guarded? fenced? barricaded? shielded? defended? prohibited? restricted? controlled? secured? access-controlled? restrictedaccess? unsafe? let's say 'unsafe'), in a protection-ring-security-model sense. If we are given some untrusted user code to run, we had better scan through it and make sure it doesn't contain any of these opcodes (alternately, the OVM could have a special mode where it faults on privileged instructions). For example, array_get_noboundscheck(array, location).

Standard library opcode implementations can call unsafe opcodes.

Some of the opcodes can sometimes or always be 'dynamic' (the others are called 'static'). This may make them difficult to statically and efficiently compile to some targets. It is possible to determine whether each instruction instance is static or dynamic just by syntactically inspecting it. For example, 'ADD' (polymorphic addition) is dynamic when its type operand is not a constant.

The Oot implementation is written in terms of only static instructions, and can freely use unsafe opcodes.

User code that contains only static opcodes can be most efficiently compiled.

User code that is untrusted cannot contain unsafe opcodes. However, it can contain safe standard library opcodes which are themselves implemented using unsafe opcodes.

This design should:

• allow trusted, static code (such as the Oot toolchain) to be efficiently compiled to code that doesn't waste time bounds-checking, etc, and that can do anything (including serialize stuff, debug secrets, etc)
• allow untrusted code to run in a sandboxed fashion (where bounds-checking is guaranteed, privacy restrictions are enforced, etc)
• allow porters to start by implementing a small subset of the opcodes (the primitives) and add the rest incrementally (or never)
• allow static user code to be compiled
• not introduce another language layer or another layer of interpreter dispatch

Should we partition the opcode address space to make it easy to recognize unsafe and primitive and static opcodes? Yeah, why not, we have 16 bits.

I'm thinking that memory management would work like this: there are primitive operations that do stuff (like loading, storing, copying) without managing memory, and primitive operations that do things like incrementing/decrementing reference counts, and reading/writing through read/write barriers. Some or all of loading/storing/copying directly without memory management is unsafe, and messing with reference counts is unsafe. Then memory-aware variants of stuff like loading, storing, copying is provided, and untrusted code (or portable user code) uses that.

---

i guess OVM should have some optional instructions that some platforms and not others implement, and that are not provided by macros/stdlib unless implemented.

For example, unicode stuff: embedded platforms usually won't support this because it requires a lot of data, but desktop platforms usually will. We want the HLL to be able to use the platform unicode stuff if it is there because interop, but otherwise the HLL must do without.

---

some notes from RPython [1]:

"Note that there are tons of special cased restrictions that you’ll encounter as you go. The exact definition is “RPython is everything that our translation toolchain can accept” :)"

ok that's crazy

• "variables should contain values of at most one type as described in Object restrictions at each control flow point, that means for example that joining control paths using the same variable to contain both a string and a int must be avoided."
• "all module globals are considered constants. Their binding must not be changed at run-time. Moreover, global (i.e. prebuilt) lists and dictionaries are supposed to be immutable: modifying e.g. a global list will give inconsistent results. However, global instances don’t have this restriction, so if you need mutable global state, store it in the attributes of some prebuilt singleton instance."
• "for loops restricted to builtin types"
• "generators very restricted."
• "range does not necessarily create an array, only if the result is modified"
• "run-time definition of classes or functions is not allowed."
• "generators are supported, but their exact scope is very limited. you can’t merge two different generator in one control point."
• "exceptions fully supported"
• integer, float, boolean work
• strings: "a lot of, but not all string methods are supported and those that are supported, not necesarilly accept all arguments. Indexes can be negative. In case they are not, then you get slightly more efficient code if the translator can prove that they are non-negative. When slicing a string it is necessary to prove that the slice start and stop indexes are non-negative. There is no implicit str-to-unicode cast anywhere. Simple string formatting using the % operator works, as long as the format string is known at translation time; the only supported formatting specifiers are %s, %d, %x, %o, %f, plus %r but only for user-defined instances. Modifiers such as conversion flags, precision, length etc. are not supported."
• tuples: "no variable-length tuples...Each combination of types for elements and length constitute a separate and not mixable type."
• lists: "lists are used as an allocated array....if you use a fixed-size list, the code is more efficient....Negative or out-of-bound indexes are only allowed for the most common operations..."
• dicts: "dicts with a unique key type only, provided it is hashable"
• "sets are not directly supported in RPython. Instead you should use a plain dict and fill the values with None. Values in that dict will not consume space."
• "function declarations may use defaults and *args, but not keywords."
• "function calls may be done to a known function or to a variable one, or to a method....If you need to call a function with a dynamic number of arguments, refactor the function itself to accept a single argument which is a regular list."
• A number of builtin functions can be used. The precise set can be found in rpython/annotator/builtin.py (see def builtin_xxx())....int, float, str, ord, chr... are available as simple conversion functions. Note that int, float, str... have a special meaning as a type inside of isinstance only."
  • note: the current set is: range, enumerate, reversed, hasattr, zip, min, max. Plus conversions: bool, int, float, chr, unichr, bytearray, tuple, list
• "methods and other class attributes do not change after startup...single inheritance is fully supported...classes are first-class objects too"
• "The only special methods that are honoured are __init__, __del__, __len__, __getitem__, __setitem__, __getslice__, __setslice__, and __iter__. To handle slicing, __getslice__ and __setslice__ must be used; using __getitem__ and __setitem__ for slicing isn’t supported. Additionally, using negative indices for slicing is still not support, even when using __getslice__. Note that the destructor __del__ should only contain simple operations; for any kind of more complex destructor, consider using instead rpython.rlib.rgc.FinalizerQueue?."
• "Exceptions are by default not generated for simple cases...Code with no exception handlers does not raise exceptions...By supplying an exception handler, you ask for error checking. Without, you assure the system that the operation cannot fail. This rule does not apply to function calls: any called function is assumed to be allowed to raise any exception...Exceptions explicitly raised or re-raised will always be generated"

---

my conclusions from the previous section:

we should do:

• variables have a single type
• module globals are clearly marked as immutable or not; and the only type of mutable module global is a reference (whose dereferenced value might mutate, not the reference itself)
• some sort of for-loop iteration but only over built-in types
• generators but very restricted, and also you can't merge two different generator in one control point."
• exceptions
• int, float, bool
• strings (ASCII for us)
• no negative indices/slice indices
• a primitive printf-ish thing
• tuples are fixed length, their fields are typed
• fixed-length lists are typed as such
• dicts
• no sets
• no variadic functions
• range, enumerate, reversed, hasattr, zip, min, max
• bool, int, float, chr, unichr, bytearray, tuple, list
• here are the magic methods that should be used at some level: __init__, __del__, __len__, __getitem__, __setitem__, __getslice__, __setslice__, __iter__
• find out what RPython means by "simple operations" in [2]