proj-oot-ootAssemblyNotes7

---

so the current proposal for OA (Oot Assembly):

EXTENSIBILITY

This proposal allow us to start with a tiny, very easy to implement set of primitives, and then expand them using the language itself, rather than to make a tradeoff between ease of porting and expansiveness of instruction set.

There are various types of 'custom' metaprogrammabilty, eg custom ops, custom types. i think this means that ops, types etc should be classified into:

My language may be a little sloppy below, since i made up that terminology right now, after writing the rest.

ENCODING FORMAT

Instructions are encoded in a sequence of 64-bit frames.

2 format bits + 62 bits depending on format

The format bits are as follows:

In the MEDIUM format, each 64-bit frame represents a single instruction. The MEDIUM format is the workhorse of OA. Most OA code can be straighforwardly represented in MEDIUM format. It is 3-operand register-based with addressing modes. You might call it a '4-operand format' because the opcode itself has an associated addressing mode, allowing 'first-class functions' to be stored in memory and called in one instruction (provided they take 2 arguments).

In the LONG format, many 64-bit frames may be combined to represent a single instruction or "sentence". The LONG format is an extremely extensible format which can represent each operand as a 'phrase' which may contain various modifiers and subphrases; this is an extensible AST serialization format. It is intended to be used when modes, modifiers, and metadata must be attached to instructions or to individual operands within instructions, as well as to allow OA to be extended to cleanly represent other programming styles.

In the SHORT format, one 64-bit frame represents 8 instructions. The SHORT format is intended to be used to concisely represent the calculation of single expressions. It is stack-based.

SHORT FORMAT

1 format bit + (2 bit addr mode + 5 bit operand) + 7 x (1 subformat bit + 2 bit addr mode + 5 bit operand)

The SHORT format is a 64-bit packed grouping of 8 sub-instructions, each one 8 bits long except for the first one, in which the first bit was consumed by the format bit (which is '0').

Because the leaf and interior nodes of expressions produce values which are consumed exactly once, and because the interior and top nodes of expressions consume their inputs (as opposed to assigning them to a variable from which they might be re-used in some other expression later), expressions can be represented in a concise RPN form in which there is a sequence of various operations which are all implicitly assumed to take their inputs from, and push their inputs onto, the stack. The SHORT format provides for arguments to be PUSHed onto the stack from any of the first 16 registers, for a sequence of any of the first 32 opcodes to be called with stack-implicit arguments, and for a single value produced at the end to be optionally POPed from the stack and stored into any of the first 16 registers. Stretches of code which require no control flow operations besides function calling and value selection, no more than the first 16 registers, no more than the first 32 opcodes, no more than the first 4 addressing modes, and no metadata or modifiers, could conceivably be written entirely in this format.

The first instruction is a 'PUSH' instruction which pushes a value onto the stack. The next 6 instructions are each either PUSHs or operations which take their arguments from, and push their results to, the stack. The last instruction is either POP instruction which pops a value from the stack, or another operation.

In the first subinstruction, the addressing mode and the operand specify the data which is to be PUSHed onto the stack.

In the next six subinstructions, the subformat bit chooses between 'PUSH' or 'OPERATION'. In the case of PUSH, the addressing mode and the operand are used as in the first subinstruction, to specify the data which is to be PUSHed onto the stack. In the case of OPERATION, the addressing mode and the operand are used to specify an opcode which is executed.

In the last, 8th subinstruction, the subformat bit chooses between 'POP' or 'OPERATION'. In the case of POP, the addressing mode and the operand are used to specify the effective address to which the result which is POPed from the stack is to be stored. In the case of OPERATION, the addressing mode and the operand are used as in the previous six instructions, to specify an opcode which is executed against the stack.

The inputs and outputs of the OPERATION instructions are all implicitly the data stack (stack0) (eg the inputs are POPed from the stack and the outputs are PUSHd to the stack). Note that OPERATION instructions may consume any number of inputs from the stack (todo must this number be fixed for each operation, or can some eg consume the stack up to some terminator? i'm thinking if not fixed, then known at compile-time at least).

MEDIUM FORMAT

(OLD idea: 2 format bits + (2 custom flag bits + 4 addr mode bits + 8 operand bits) + 3 x (4 addr mode bits + 12 operand bits))

2 format bits + (2 addr mode bits + 12 operand bits) + 3 x (2 custom addr mode bits + 2 addr mode bits + 12 operand bits)

(note: when the 2 'custom addr mode bits' are 00, then the addr mode is fully determined by the 2 addr mode bits; when the 2 custom addr mode bits are nonzero, then custom code is executed; in other words, if we put these together to form 4 total addr mode bits/16 addr modes, then the first 4 of these addr modes are specified and the other 12 addr modes are custom)

OPCODES

The first field is the opcode field. The first four bits of the opcode field are the address mode bits. The addressing mode is applied to the 11-bit operand to generate the opcode field value. The opcode field value is broken down into:

LONG FORMAT

todo

see ootAssemblyThoughts for the previous proposal (um, it's not there anymore? perhaps i moved it to ootAssemblyNotes8?). Note that now that we are stealing 2 format bits from the header, it would have to be modified at least a little. Maybe since we have short formats now we should ditch the 8-bit payload format; that saves 1 bit, we still need another. Also, the addr modes are probably custom, not 'split addressing'. Also, since we have the other formats now, no need to specify anything for role 6.

Also, do we want to add a 'map' that says what the child nodes will be and what their offsets are, rather than just linearly reading and encountering roles and then a stop?

Also, do we want to add backwards offsets at each child node to say how to find its parent?

Both of these ideas make sense if we think of this as an AST serialization rather than as a natural language 'stream encoding'.

Also, the format currently described at ootAssemblyThoughts was designed to permit arbitrarily long sentences, by using 'stops' instead of headers with length. But in the real world, we'd probably prefer to have header, perhaps with a 'combine with next' semantic if the header says the max length.

We might also want to have a map to the starting location (offset) of each child of the current node, and the role of that child. And maybe, if the node has a single parent, the offset back (or forwards) to that parent. Otoh this information is implicit in the data in any case, and who is to say that it is more efficient to store it explicitly; that depends a lot on the application. And besides, i'm not trying to make some complicated red-black tree or anything, i'm trying to make something very simple.

But if we did have a map, it would have to have length limits. And maybe the numbers 4 and 16 are useful here (and possibly 8). If we had a 4-bit role and a 4-bit offset for each child, that's 8 bits in the map, so if we had 8 children we'd already fill up a 64-bit frame. If we had a 3-bit role and a 3-bit offset, and 8 children, that's 48 bits, so at least we have room for a little data here or maybe an offset to the parent. If the length needed for the children exceeds these limits, we can ay 'use the parenthesis construct' which is a 64-bit frame that is mostly just a size of the subtree.

ALL FORMATS

CUSTOM INSTRUCTIONS In addition to custom instructions, there are first-class functions that can be called like instructions via using the addressing mode on the opcode field; this functionality is referred to as 'call3'. Typically the opcode's addressing mode is immediate constant; but by using 'constant table' addressing mode, module functions can be called, and by using the other addressing modes, function pointers sitting in memory can be called (so in this last case, which function is executed is only known at run-time, not compile-time).

call3s are like macros that substitute their 'body' inline whenever they are seen, except with references to the special ARG0 memory location replaced by the effective address indicated by the first operand, and references to ARG1 and ARG2 replaced by either references to the values indicated by the second and third operands, or the effective addresses, depending upon if the assigned opcode is less than 0xC00; and 'JMP' appended to their body whose target is the instruction following their invocation. Custom instructions do create a new 'scope' with respect to label numbers; custom instructions are not aware of and cannot jump to labels outside of their own implementation, and labels within custom instructions are only accessible from jumps within those instructions; if custom instructions containing labels are inline expanded, the labels must be re-numbered so as not to conflict with labels in the calling code.

Some interpreters may implement custom instructions using a hidden stack instead of inline expansion.

Custom instructions may not invoke themselves; and they may not make use of custom instructions defined after themselves. There is no way to recursively call much less 'tailcall' a custom instruction; when you define a custom instruction, please use iteration instead of recursion. This limitation ensures that custom instructions may be inlined (or, that if they are implemented using a hidden stack, that there is a fixed upper bound on the hidden stack depth).

todo: do we place some requirements on call3'd subroutines that they must complete quickly and cannot utilize the underlying platform, for the purpose of being able to use the underlying platform stack as the hidden stack without saving it when we want to return control to the underlying platform?

Custom instructions are declared by a map of opcodes to a tuple (module identifier, function).

Custom instructions must not have cyclic dependencies, and must be defined in order such that when one of them is defined, any custom instructions used within its implementation have already been defined. (the order of the assigned opcodes may be different from dependency order).

The form of first-class functions is the same as custom instruction declarations (with a 0 in the opcode field). If the opcode operand resolves to an integer, then an instruction (built-in or custom) is indicated; if it resolves to a pointer, a first-class function is indicated (note: this means that there must be a 'function type' which can be represented as either an integer or a pointer).

Function declarations include:

Custom addressing mode declarations include:

The first four custom addressing modes are 'direct'; their operands represent registers, and their effective address is that register; these are the only ones whose effective address may be a register.

Custom addressing modes must leave the stacks unchanged (except if they are direct and the register operand is a memory-mapped register). This makes it easier to analyze the program for changes to the stack.

TODO: actually what if we want to use the extra addr mode bits to represent per-operand custom flags? in that case we need to wrap the whole instruction, not just the argument evaluation.

There are also custom flag bits, which are defined by a wrapper that is called in place of and wraps the following op. Like call3s, they can look at the link register to get a pointer to the instruction that they are supposed to wrap. When they are called INTROSPECT_INSTRUCTION is automatically called on the wrapped instruction to break that instruction into (4 operands and 4 addressing modes) and put those parts on the stack. The custom flag implementation can and typically does use a form of EVAL to execute those parts, possibly after modifying them.

Requirements on custom flag bit semantics:

OA does not support variadic instructions.

Self-modifying code per se is not supported, although EVAL is.

ADDRESSING MODES

There are 4 built-in 'core' addressing modes and 12 custom addressing mode slots.

Built-in addr modes are:

'immediate constant' in the output addressing mode with operand '0' means 'discard'. Other operands for 'immediate constant' addressing mode in the output are forbidden, except in certain compile-time metaprogrammy operations, for example IMPORT.

'constant table' in the output addressing mode is forbidden unless the constant referenced is a global static pointer.

some ideas for other addressing modes:

MODULES

Modules must declare custom instructions, custom addressing modes, and their constant table. All of these declarations must be done completely at compile-time. Custom types don't need to be declared; they are just stored as pointers.

There are two places to declare custom instructions; as unused opcode immediates, and as function-typed entries in a constant table. There (probably) is a separate constant table for instructions (ie for when the opcode field has constant table addressing mode). tombdo is there any difference between custom instructions as immediate opcodes, and as function-typed entries in a constant table? I'm thinking that the latter would be more like library functions and the former would be more like new 'instructions' but what is the difference? Perhaps the difference between the two is that the former is hardwired as builtins in the OA implementation and the latter is per-module; or that the former is per-whole-program (allowing faster dispatch) and the latter is per-module. Or that the former can be either OA code or hardwired in the implementation, while the latter can be OA code or an external C library. Or the latter can be used by a module loaded at runtime but the former cannot. Or something. Currently my best guess is that only constant table customs are per-module; the others are either per-program, or part of the implementation (perhaps an interchangable part though, eg each program can specify an Oot 'profile' different ones of which have different selections, and some profiles are implementation-dependent..).

Modules may import other modules. This is done by listing the other module in the imports table within the module info table. There is also a runtime instruction IMPORT. This instruction must use immediate-mode addressing to specify the destination integer identifier (this is to allow the implementation to know what module identifiers are being used at compile-time).

Modules may also import custom opcodes, types, and addressing modes from the other modules into their own. This is done by listing the other module into the metaprogramming imports table within the module info table. There is no way to do this at runtime. Trying to import metaprogramming from different modules that define overlapping opcode, type, or addressing mode identifiers is a compile-time error.

There is a special module BUILTINS. This is meant to be an implementation-dependent module that contains opcodes, types, and addressing modes that might be given special treatment by an Oot Assembly implementation. By tracing imports of opcodes, types, and addressing modes from this module, the implementation can know at compile-time where its optimizations can be applied. The semantics of standard opcodes, types, and addressing modes, even non-core ones, must not be altered in the BUILTINS module's implementation; however BUILTINS can also define non-standard opcodes, types, and addressing modes. (todo is this a good idea? or just autoimport all implementation-dependent builtins to EVERY module?)

The BUILTINS module is auto-imported at module identifier 0. The current module is auto-imported at module identifier 1.

Absolute memory addresses (constant table mode), eg those in the operands of JMPs, are all implicitly module relative (pointers, however, can be shared between modules). Integer JMP addresses refer to a count of Oot Assembly instructions in the module.

Each module has:

Length fields are 16-bits, but their values cannot be more than 4k. Lengths mean how many items each table has (not the number of bytes that the table takes up).

(todo: is this really the best format? should we (just) place the lengths in the tables themselves, or only have lengths and let the pointers be computed?)

Symbol names data is the data which can be stripped for more compact builds. It contains ASCII string names and source maps for the module and for each defined custom addr mode, custo opcode, function declaration.

TYPES

There are some built-in types that don't need to be declared (the first 16, perhaps?).

types todo: probably want at least integer, floating point, string (bytestring or unicode or both?), object?; the INSP of Parrot, and mb also of MoarVM?

another idea for 4 core types: pointer int16 other/custom static type (has already been statically typechecked) dynamic (boxed/wrapped, tagged type; runtime typechecking requested)

an idea for another 12 'base' types:

boolean/single bit unsigned int16 byte float64 arbitrarily large/precise rational unicode string array cons cell/linked list/binary tree graph/hash/dict (opaque, as opposed to AST) function/callable, thunk/promise/future/lazy value AST/expression/block/logic greenthread/process/channel(/actor?)

(note that some implementations might not support all of these types; eg an embedded implementation might not support floating point, arbitrarily large/precise rational, unicode)

OA is typed in the sense that every scope has a type declaration for every register it uses, and every instruction has a declared type signature; there is however a 'dynamic' type. 'dynamic' type means that this location can hold a value of any boxed type. Boxed types have a type tag. Values in locations with 'dynamic' type must be 'coerced' via a COERCE instruction to their actual type before they are moved to locations with their actual type, or passed as arguments to instruction demanding their actual types; the COERCE instruction causes a runtime exception if the value isn't actually the correct type (as determined by its type tag). Type identifiers are 12-bit integers.

There are also a few special memory locations whose type varies by scope, namely the call3 inputs and output registers. In addition, there are stacks; stacks are typed via 'stack maps' like in the JVM. Stack maps are like regexps, and can contain unbounded repetitions of patterns. Instruction type signatures include a specification of their alteration of the stack (in the form of eg: upon entry, i expect the top of the stack to contain an int8 and an int16, which will be consumed; upon exit, the top of the stack will contain an int16 (note: the instruction does not HAVE to consume the inputs, but if it does not, it must list these as outputs)).

(i suppose in the end we also need a way to coerce raw bytes to typed something, for interop?)

Some instructions have polymorphic forms, eg forms whose input type signature includes 'dynamic'. Some of these instructions also have specialized forms, that is, forms where the 'dynamic' in the type signature is replaced by a specific type. In this case, the instruction will have the same mnemonic but a different opcode, and the Oot implementations handles dispatch to the specific form if there is one (by, at runtime, checking for a specific form before each call to an instruction with a dynamic input type signature).

Just like memory locations are typed, the stack is typed. But since the program is allowed to arbitrarily manipulate the stack, we cannot always statically know what the 'type signature' of the stack (the stack map) will be. So, what we do is we say that, so long as the number of things on stack0 is predicatable, and stack1 is only being accessed implicitly by CALLs and RETURNS and their associates, we can infer the stack map (like the JVM verifier does (used to, now i think stack maps are made by the compiler)), but if the program wants to change the stack in a weird unpredictable way, then it has to start including assertions saying "i'm about to add an arbitrary number of things to the stack" and "i'm about to directly manipulate stack1, consuming n elements" (so that the compiler can remember that, at that point in time, the stack-so-far (above the n consumed elements) is known but everything added to the stack on top of that is unknown). When the program is done doing weird stack writes, it can then assert how much it consumed and then the program continues with the rest of the implicit stack map governing (i could probably find a clearer way to write that...). And if it wants to read the unpredictable regions of stack0, or any of stack1, then each time before reading, it must assert that there is no stack underflow, and also the type of the thing it read (which can be 'dynamic'). This allows the program to use the stack efficiently in normal circumstances; to manipulate the stack arbitrarily if it wants to, at the expense of runtime checks; and to do one-time manipulations (such as handling exceptions) which leave the stack in a predictable state after which efficient stack usage can resume.

Although OA is designed for optional static typing, unlike eg the JVM, there may not be any typechecking done at runtime; typechecking is provided as a separate OA program (written in OA). OA users are urged to typecheck any untrusted or newly written code before running it.

(do we allow 'subtypes'? eg can we write a function that says "i'll take anything which is an int or a float" and then assert at runtime that some value is an int or a float, without saying which one?)

Type declarations include:

Values of the 'pointer' type are not necessarily 'pointers' on the underlying platform; they are simply some implementation-dependent reference value that allows dereferencing via the indirect addressing mode, and 'pointer arithmetic' to traverse adjacent fields. A 'pointer' could be represented by a machine pointer although with information about the width of record fields, by an integer into an array of emulated 'memory locations', by an object with methods to 'get' and 'set' its value and to get the 'next' and 'previous' locations, etc. Dereferencing a 'pointer' could involve calling garbage collection read-barriers, and writing to it could involve calling GC write-barriers, all 'under the hood'.

MEMORY

4k local variable locations or 'registers' (or less; in each module header it says how much it needs; perhaps memory sizes are always powers of two (this apparently makes eg pointer tagging easier))

memory map and memory-mapped special locations 

0: PC (program counter)  (do we forbid writing to this? i think so; we want to make programs use control flow ops like JMP for easier analysis)
1: ERR
2: stack0 push/pop
3: direct read/write access to the top of stack0 (without pushing or popping)
4-7: GPRs
8: stack1 push/pop
9: direct read/write access to the top of stack1 (without pushing or popping)
10: current size of stack 0
11: current size of stack 1
12: MODE
13: ARG0 (call3 operand0/output)
14: ARG1 (call3 operand1/usually input)
15: ARG2 (call3 operand2/usually input)
0x010-0x7FF: general purpose registers (GPRs) (accessible in the opcode field)
0x800-0xFFF: general purpose registers (GPRs) (not accessible in the opcode field)

note: this is not to say that the virtual machine can only access 4k of memory, just that it has only 4k of registers. A pointer can be placed in any of these memory locations, and that pointer can point to somewhere else. Likewise, the PC can point to memory locations outside of this map. These alien memory locations are always considered to be 'higher' than this memory (eg if compared, the alien memory address is 'greater than' 0xFFFF) but don't have to actually be that way in the underlying hardware. The alien memory addresses can be incremented as usual. These 4k locations are the only ones that can be accessed in direct addressing mode; however other locations can be accessed via indirect addressing mode. There are also absolute JMPS, which although 'absolute' are actually relative to each module.

There is no way to get a pointer to a register.

note: there are two stacks, intended to be used as data stack (stack0) and call stack (stack1) but the result is undefined if a program attempts to access beyond the end of the stack; this means that these can be implemented as a single stack

I call these locations 'registers' but really they are more like local variables.

If you do an operation on 'the contents of register 7' but the operation calls for some struct, then it is implicit that register 7 actually holds a pointer to that struct. If the contents of register 7 is typed as a struct (of some specific type), then the semantics of 'copy register 7 into register 8' is to copy the STRUCT (with COW? maybe not, if it is not boxed), not the pointer.

It is illegal and undefined to read from uninitialized registers.

The machine handles much of memory allocation/garbage collection transparently.

MODES

The MODE register sets various modes. It has 1 bits. By default, it starts out in mode 0.

bits in MODE from MSB to LSB:

Aside from 'external' state such as memory and I/O, and the stack, OA itself has no 'hidden state'; the state is visible in the registers.

ERRORS

There are four error handling modes, controlled by the MODE register.

In 'crash' mode, any attempt to write a non-zero value to the ERR register is immediately fatal.

In 'handle' mode, any attempt to write a non-zero value to the ERR register succeeds and then immediately causes the current value of the PC to be pushed onto stack1, and then causes a JMP to the beginning of the program. Note that programs run in this mode should be sure to check the ERR register at the beginning and if it is non-zero, to 'handle' the error in some fashion.

In 'restart' mode, any attempt to write a non-zero value to the ERR register immediately causes the stacks to be emptied and a JMP to the beginning of the program. Note that 'restart' could be emulated by putting a routine to clear the stacks and the ERR register at the beginning of the program and running in 'handle' mode.

In 'tolerant' mode, any attempt to write to the ERR register succeeds.

Note that it is possible for a subroutine to leave the ERR register in a non-zero state by saving the current MODE, setting the error-handling mode to 'tolerant', setting the ERR register, then restoring the error-handling mode. By this method (or by the NONFATALERROR opcode, which does the same thing), a subroutine can return an 'error code' which is (unchanged) upon success and non-zero otherwise, which may be more convenient than returning multiple values via the stack.

CALLING

There are (at least) three explicit CALL instructions, in addition to CALL3 functionality:

LIMITS

Note than although the instructions can only hold 12-bit immediate values, other addressing modes can be used to give larger values. Unless otherwise specified, anywhere an integer may be given, its size may range up to 64k - 1 (and possibly larger in some implementations). Many things have a limit of 4k - 1, however. These include:

(todo: is the 4k limit really needed for any of these?)

OA implementations may also limit the number of allowed labels. The limit must be at least 4k.

FLAGS (lack thereof)

There are two flag bits per instruction.

Note that further use-cases for operand-level flags can be emulated by custom opcodes.

BOXING

in the boxing:

CUSTOM FLAG BITS SUGGESTIONS

ATOMICS AND MEMORY MODEL todo

how about:

but mb we are not even having shared memory at all?? in which case we need some IPC/message passing primitives at least, instead.

NOTES ON SOME INSTRUCTIONS

JMP: if given a pointer, JMP to that pointer (can you JMP to 'data' locations or just locations marked as 'code'?); if given an integer argument, jumps to the n-th Oot Assembly instruction. NONFATALERR, see above

CORE INSTRUCTIONS These instructions must be implemented by someone porting OA. All other 'base' instructions are ultimately reduced to these.

When an instruction 'returns' a value, this means that the contents of effective address of operand 0 is set to this value.

probably not core but still considering:

add-on profile modules:

---

so two things to note:

Some things that may be a problem:

so the Call3s require a hidden stack, and we are exposing two stacks. The two stacks we are exposing could be combined into 1 by the implementation, and this could also be combined into the Call3 hidden stack, because the Call3 stack must behave itself. And in fact the 'registers' could be combined into this stack, too. But if we expose any stack to the OA user code, we have two issues: this bumps up the memory requirements for greenthreads this makes interoperation more complex, because we have to preserve OA user-visible stack state across periods of time when other code is executing on the underlying platform, and if we tried to use the underlying platform stack for this, in some cases we may have to move our stack info off of the stack when we return control to the underlying platform perhaps the call3 hidden stack could even be combined with the platform stack; in this case either we'd have the same problem of saving stack state when control is returned to the underlying platform, or we must ensure that we never return control to the underlying platform within a call3 we could eschew any use of the underlying platform stack and heap-allocate our own stack, but this will cause worse performance and eat up more memory for the greenthreads

so the idea of this interoperation is that, although the naive OA implementation includes a naive scheduler (as custom opcodes themselves written in OA), etc, and although optimized OA implementations running close to the metal will implement their own scheduler (replacing these custom opcodes, but more difficult to implement), there is a third situation: when an OA implementation is running on top of a platform that itself already contains a suitable scheduler (eg Golang), it should be easy (for non-compiler programmers) to replace the naive scheduler with reliance on the platform's scheduler. Similarly, it should be easy for a non-compiler-writer to allow Oot functions and platform functions to call back and forth into each other, and even being passed between as first-class functions, if the platform allows first-class functions. The problem with this is that OA enables more powerful control flow than many underlying languages. For example, in Oot you have closures and upvariables which can be modified by the enclosed inner function, and these modifications can be seen in the outer function. This is not the case in Python, where the inner function cannot modify upvalues. The Oot behavior requires that the upvariables be stored in a way that remains accessible after the creating scope terminates, since the closure could be returned by the creating function. This can be accomplished by storing locals on the heap rather than the stack. But this means that Oot functions and control flow cannot simply be Python functions and control flow, at least not always. But if Oot was implemented on top of Python by simply executing OA in a VM, how would Oot functions and Python functions call into each other? The solution, if one is even possible, would seem to be some combination of:

---

expression trees:

so what is needed to store an AST?

i guess we could have a format similar to the 64-bit one above, except:

i guess that a linear 3-operand register bytecode representation can actually be pretty close to an AST; you just write the AST from bottom to top instead of top-down (ie instead of having some child nodes (operands) be in a mode that says "see parenthesized expression x spaces over to the right" (operands being 'lower' in the tree, so this is top-down), you have the operands all refer to things already defined, and sometimes the result of the node isn't used immediately but is used by another node defined farther to the right), and when you write each node, the 'destination operand' specifies which to-be-defined-later node is the parent of this node. This actually isn't too different from linear bytecode except that (a) in a tree (an expression tree, or AST, is a tree), each node can only have one parent (hierarchy not heterarchy), in contrast to linear 3-operand register bytecode, in which a local variable (the memory location in which a result is stored) may appear in multiple later instructions (which is as if a node in the AST had multiple parents; it's a DAG rather than a tree) (b) the 'destination operand' would refer directly to the location in the code of the parent node, rather than to a memory location; in an AST representation i would want to be able to quickly navigate from any node to its children and from any child to its parent, but in a linear 3-operand register bytecode, this would involve seeking backwards and forwards for other instructions that write to/read from the same local variable (register) that you are using. Now, you could look at the 'memory locations' as names for the nodes in the AST, but this only works if they are not reused across the AST, unlike registers which may be re-used (the not reusing condition is like SSA, i guess).

this stuff is interesting.

how does it relate to stack-based instructions representing expressions? stack-based bytecode works like RPN. The expression tree is represented bottom-up (in the sense i just gave; children of an expression node are written before parents; note that children also related to causal dependencies of a node, in the sense that you can't compute a node's value without computing the value of its children (except in some special cases where the operation of a node gives the same result no matter what some of its children are, conditional upon the other children)). Like linear 3-operand register bytecode, you first write a child node, and then at the end you store the result, without explicitly representing when it will be used. Unlike linear 3-operand register bytecode, you don't specify a storage location; storage is always just pushed onto the stack. Later on, when a parent node uses this value, instead of explicitly specifying the name or offset to the child node (like an explicit AST repr), or the memory location where it was stored (like linear 3-operand register bytecode), the stack-based representation just pops a value from the stack. Because the value was popped, it is consumed and cannot be used again, so this is a tree, not a DAG (a hierarchy, not a heterarchy), unless you have stuff like DUP that manipulates the stack directly (DUP can be considered 'metaprogramming' compared to ordinary stack-based representation of an expression tree, in which the stack is not explicitly manipulated, just implicitly popped from and pushed to whenever an argument is needed/a result becomes available).

---

could say that custom instructions can only use 4 'scratch' GPR regs

---

note: why do JMPs output their old location?

(a) we had some extra bits; 24 bits to specify a label is already more than we want (b) this is useful for reversible computing

---

note: for LONG format, or indeed any tree encoding, if you have fixed-length 'length' and 'offset' headers, there are two possibilities for any interior node of the tree:

(a) all children are within the range of the offset header (b) the data in this node, or in some of its children, are so large, or the children are so numerous, that some of the children are at an offset too distant to fit in the fixed-length offset field.

---

one nice thing about the 2k limit is that even with 64-bit fields this is only 2k*8 = 16k total, which fits in most of today's L1 caches with room to spare, even eg http://dsg.uwaterloo.ca/seminars/notes/2014-15/Lehner.pdf 'Application Core' with 16k cache.

---

so in the above MEDIUM format, i seem to keep going back and forth about some things. what do we really need, given our basic design choices for this sort of format?

so that's about 2 + 8 + 36 + 8 = 54 bits. So we have 10 bits left over.

So the obvious thing to do, to avoid making any design decisions for no reason, and since we are doing custom stuff here, is:

so yeah, get rid of the 'signature class bits' esp. because we have no room for them in SHORT format anyways

now, with all these 'flag bits', maybe we can get rid of 'prefix modifiers'? That would make instructions truly fixed-length, simplifying decoding esp. parallel decoding. If those are really needed, the programmer can use LONG format. OK, done, i got rid of them (and changed the wording on the constraints on their semantics to apply to the custom flag bits instead).

---

so about the LONG format. Can we simplify it? What are some of its goals?

Going just on "arbitrarily many custom modifiers attached to any part" and "ability to represent arbitrarily long sentences, phrases", we get XML. XML lets each node have any many children as you want (mb there's a limit that i dont know of, but if so, it's big), and each node can have custom attributes (which are modifiers). So maybe i should look at:

One thing that XML does not allow (afaict) is modifier phrases recursively modifying modifiers. Do the others have that?

So what do we really need? 8 is not a beautiful number, do we really need 8 roles? I think all we really need is:

Now do we even need to explictly mark these roles? It seems that everything has a base or 'head' (am i just being influenced by my previous study of HPSG (head-driven phrase structure grammar)?), so the first thing can always be the head. Which is reminiscent of Lisp. In an S-expr, you could have a list for the head element of another list, this would be like replacing the verb with a verb phrase, which might even include modifiers. Maybe i should look at:

S-exprs are only trees, though, not DAGs and not cyclic graphs, and without reifiable edges; so if representing Oot Graphs is really a criterion, then S-exprs are not quite enough. However apparently some sexprs CAN do cyclic; http://c2.com/cgi/wiki?EssExpressions says Common Lisp can, via "#1=("blah" #1#)". I dont see how DAGs would be represented this way, though.

Now thinking of XML, one thing that annoyed me about XML was the distinction between attributes and children. It seemed that in some cases it was difficult to decide whether some conceptual attribute should be an attribute or a child of a node when represented in XML. Do we really need this distinction here? Yes, i think we do; eg if you have the opcode ADD, you clearly want to separate the opcode-specific semantics of the arguments (children) from the (somewhat) opcode-independent semantics of modifiers such as "atomic" or "blocking". This isn't quite the right way to state it b/c of course the 'semantics' of the children are also independent of the opcode, eg in "ADD 3 5", "3" means the integer 3, and you can know that without knowing what ADD means. Maybe the thing is that 'modifiers' affect the semantics of the opcode in some way that the interpreter must know about; whereas 'children' are just passed blindly to the opcode.

Incidentally, i suppose that once i figure out how to state that precisely, that design criterion solves my issue with that part of XML; node attributes should be things whose semantics are relatively independent of the node identity.

And similarly, i think we need metadata.

We may not really need separate roles for direct vs indirect object, modality vs constraint, ordinary argument vs conjunction, meta vs alternate formats, meta vs grouping; although many of these would be nice. But it's probably nicer to have only 4 roles. The idea is that the HLL can expand this with custom attributes labeling stuff, eg you could have an 'HLL_role' modifier or metadata. Since we're not positive about the need for those other things, we leave them open to custom.

Although clearly we can always transform the graph to lump together 'children', 'modifiers', and 'metadata' attached to a node into just node children.

Now, do we want to have fields that say how many of each of these things there will be, and/or their offsets? This is not strictly necessary but it would help efficient access. But it would limit the length of stuff, and it's difficult to choose the bit-width of the length field so that longish things are supported, without wasting too much space given that the common cases will be length 1, and sometimes up to 3. Since the goal here is simplicity and generality, not efficiency, I guess it would be both simpler and less limiting to stick with our current scheme of just having terminators, although i'm a little bit worried that this might make interpreters too hard to implement on some systems (since the interpreter would have to be ready to dynamically allocate memory/stack/etc to acommodate with very long phrases).

And if we want to support not just trees but arbitrary graphs, including DAGs and cycles, then i'm guessing that at some point we have to just support edgelists, because there will be times when one element can't contain or even be immediately adjacent to all of its (conceptual) children. This could be a special case, though; the default could be including the child directly, and then the special case could be a 'reference' or 'pointer' to a 'named node' elsewhere (perhaps with an offset, if we are willing to limit the structure's total size). Another thing we could do is imperatively use the registers, eg instead of a 'reference' you would actually assign part of the graph to a register, and then when building the rest of the graph, use direct addressing mode to refer to what is in that register. This has the advantage of smoothly merging with the rest of the language, but the disadvantage that complex graphs take multiple execution steps to construct (and hence take more time, are more resistant to optimizing into one constant during compilation, confuse program analysis, and take up space in registers).

In addition, if we want this to support Oot graphs, then choosing a representation forces me to nail down the semantics of things like hyperedges and multiedges and references between graphs a little, although this is not a bad thing, because one of the main goals of thinking about Oot Assembly was to provide inspiration for that sort of thing ("that sort of thing" meaning the design of the rest of the language particularly in terms of reducing it to a small set of 'fundamentals').

Now, if we have edge lists or references, then we must be able to 'name' nodes, and this means either having an awkward variable-length encoding, or fixing an upper bound on the number of nodes (or at least the number of nodes that can participate in certain ways in DAG or cyclic substructures).

This would seem to be an argument for allowing imperative construction of graphs, because you could get many more graphs if you can construct it piece by piece (can you get all of them, though? probably but i'm not sure yet..). Just like elsewhere in the system, the idea is that the OA machine may be able to support larger things in memory locations than can be explicitly represented as an immediate constant in code (some OA implementations may even support arbitrarily large integers in a single memory location via a variable-length/multiple-precision encoding). But if we have imperative construction, do we really want that to be a part of the graph syntax? Shouldn't it just be ordinary opcodes operating on an ordinary composite data structure? Furthermore it would be nice if the graph representation could accomodate the representation of complex graphs in a non-imperative way; this would allow a naive OA implementation to just reuse the same datastructure produced by OA LONG code for actual internal storage of Oot graphs (rather than making the only representation of large, complex graphs be imperative).

This suggests that we do need to use 'addressing modes' although here they seem to not refer to registers, but rather to labeled/named nodes/edges within the graph. So we have obvious definitions for:

So, what does indirect mean? Perhaps it means a 'pointer' outside the current graph, clarifying the semantics for links between graphs? Or perhaps it means the current/imperative contents of a register? I'm leaning towards the former (a pointer, which must be into main memory, NOT to a register).

"pointer" pre-runtime (pre-link time, i guess) constants in code could refer to globals

Should we have 'custom' roles, or should we leave that up to the language to express through metadata labels? I'm thinking the latter.

Should we have 'custom' addr modes? Hmm, i dont quite see the need for that here, but mb.

So far we have:

per 64-bit frame: 2 format bits ; possibly, an EOS (or BOP/EOS) bit

per argument: 2 bit role (except for HEAD), 2 bit addr mode, 12 bit operands

since the 'per argument' is nicely 16 bits, this suggests we make use of that somehow.

since HEAD doesn't need a role, we appear to gain 2 bits to use for something else. This would dovetail with the 2 format bits. So we could have:

64-bit frame = HEAD node + 3 other nodes

is that all? no, as is, this would just be a trinary graph with role labels; we don't have any BOP/EOS bits in there.

Also, if HEAD doesn't need a role, then we have one role free, right, b/c we have 2 role bits? Or do we leave that unusued so that the same enum can be used if we directly introspect and query the role of HEAD (yes, i think we should do that: leave it unused). Oh wait, i forgot, we need HEAD to mark leaf/value nodes anyways.

OK, so what do we do about the BOP/EOS bits? Clearly we need to lose at least one of the other nodes, freeing up 16 bits. What do we do with these 16 bits?

So we currently have:

HEAD (16-bits):

do child0 and child1 have different semantics, or are they just packed in there together for no reason? What if we have more children with no HEAD, then what does the next frame look like?

The consideration of possibly having more children with no HEAD makes me think that it was unwise to eliminate the role bits from HEAD. So:

frame header (16-bits):

Now, if we can't have HEAD except at the beginning of a phrase, we no longer need BOP bits, because a ROLE value of HEAD suffices for BOP. We still would seem to need an EOS somehow, though, or at least a sentence length at the beginning. We could have a special sentence header at the beginning of sentences, though.

we can't say that every frame starts a new phrase. But we can say that new phrases only start on phrase boundaries (do we want to say that?)

what about edge reification? what about hyperedges? do we want to reify everything to make hyperedges easier, perhaps making nodes 0,1,2 into an RDFish triple? do we want more addressing modes for edge reification and/or for hyperedges? do we want to use indirect addressing for these? or is reification a role? if so, is it he 'meta' role? do we not reify everything by default, but then when some nodes are eg hyperedges, we use reification? it would not seem wrong to throw out the 'indirect addressing as actual pointer' idea, and have actual pointers be encoded as ordinary values attached to nodes.

do node0, node1, node2 have different semantics or are they just packed in there?

do we want direct addressing to name nodes by a fixed name, or by an offset from the place where the direct addressing occurs? if the former, how are nodes 'named'? By a LABEL opcode right before them? Or by a lookup table at the beginning of the graph? Or by those 14 bits that we have in the frame header?

it's tempting to have use 2 of the 14 bits as a 'frame role', and use the remaining 12 to label/name this frame. One frame role could be an RDF-ish hyperedge triple, another could be an ordinary list of nodes. I don't see why every frame needs an explicit name, though, can't we just take the position of the frame as its name?

also, this format is getting close to MEDIUM format for the frame (if not in semantics), so maybe just sorta-unify them (still keep them separate, b/c of semantics) by having:

if we do that, this suggests:

if we go this route, then even if it isn't 'imperative' in the sense i used before (of building of the graph in parts using ordinary register-based computation), it is 'imperative' in that these various frames are really just a recipe for building the graph. There is a danger here in allowing too many ways to express the same graph (which is not a danger from the point of view of compilation, since these 'instructions' can be executed at compile time and used to build an optimized representation, eg an edge list; but it is a danger from the point of view of manipulation/analysis, since to detect some particular structure you either have to 'compile' the object into another representation, or have various special cases for the various opcodes that can be used to produce the same thing). Either we should be careful to minimize this (by maximizing 'orthogonality' of our LONG opcodes), or we should just accept this and assume that this object will be 'compiled' before subjected to any analysis. This might be hard to avoid if we allow mixing of multiple levels of reification (eg one opcode that can say "the children of A are B and C" and another that says "there is an edge from A to B with label L"; both of these add an edge from A->B, but the latter is more reified).

Note that when i speak of LONG opcodes (or maybe encoding opcodes, or reifying opcodes, or meta opcodes), these are NOT instruction opcodes, and indeed the LONG encoding can encode instructions (via encoding "the opcode is X and the output operand is Y and the output addr mode is Z and the first input operation is...", and the encoded instructions will have ordinary opcodes!

---

some ideas for encoding opcodes (LONG opcodes):

modifiers? roles? addr modes, operands, etc?

variables, metavariables?

is offering both STOP terminators and lengths going too far into useless variant encodings?

is offering variables going too far into runtime metaprogramming/imperative stuff?

ok wait this is too many opcodes. We're not trying to invent some super-inefficient self-describing uber format. Just b/c we have space for 256 opcodes doesn't mean we have to use all of them. We don't need both of: length and stop-erminated for everything.

---

so how about:

opcodes:

edge: first argument is the source node of this edge. Second argument is the reified edge. Third argument is the destination node of this edge. Each have addressing modes. If the edge doesn't need to be reified, then the second argument can just be an immediate constant, which is the role. Similarly, if the destination node only has a value and no other outgoing edges (a leaf node), then it can just be an immediate constant, or constant table.

2 frame-level flags: one of them is "last frame" (EOS, end-of-sentence). The other is reserved. 2 operand-level flags/custom addr modes: reserved

eg: to say ADD 3 2:

EDGE 0 #1 #ADD-opcode (there is an edge from node 0 (the root), with role 1, 'base', to the opcode for ADD) EDGE 0 e1 #3 (there is an edge, reified edge e1, from node 0 (the root), to the value 3) EDGE 0 e2 #2 (there is an edge, reified edge e2, from node 0 (the root), to the value 2) EDGE e1 #0 #0 (there is an from reified edge e1, with role 0, 'meta', to the value 2; this says that e1 is an edge of role 2, "children") EDGE e2 #0 #0 (there is an from reified edge e2, with role 0, 'meta', to the value 2; this says that e2 is an edge of role 2, "children") EDGE e1 #1 #0 (there is an from reified edge e1, with role 1, 'base' (in this case, the label or lookup 'key' associated with the edge), to the value 0) EDGE e2 #1 #1 (there is an from reified edge e1, with role 1, 'base' (in this case, the label or lookup 'key' associated with the edge), to the value 1)

So, there is a node representing the root; there is an edge from this node to the value node for ADD's opcode; there is an edge e1 from the root to 3, and an edge e2 from the root to 2; both e1 and e2 have role 'children'; e1 has label 0 and e2 has label 1 (so the root node is sort of like a dict with keys 0 and 1 and associated values 3 and 2).

(note/todo: it seems kinda restrictive for role 0, 'meta' to only mean the ROLE label, when applied to a reified edge)

(note/todo: seems a bit verbose, should mb include a 'node' or 'children' opcode for more efficient conveyance of non-reified stuff)

could also have a CHILD opcode:

CHILD 0 #3 CHILD 1 #2

which substitutes for much of the above:

EDGE 0 e1 #3 (there is an edge, reified edge e1, from node 0 (the root), to the value 3) EDGE 0 e2 #2 (there is an edge, reified edge e2, from node 0 (the root), to the value 2) EDGE e1 #0 #0 (there is an from reified edge e1, with role 0, 'meta', to the value 2; this says that e1 is an edge of role 2, "children") EDGE e2 #0 #0 (there is an from reified edge e2, with role 0, 'meta', to the value 2; this says that e2 is an edge of role 2, "children") EDGE e1 #1 #0 (there is an from reified edge e1, with role 1, 'base' (in this case, the label or lookup 'key' associated with the edge), to the value 0) EDGE e2 #1 #1 (there is an from reified edge e1, with role 1, 'base' (in this case, the label or lookup 'key' associated with the edge), to the value 1)

in fact could have a separate opcode for each role:

BASE 0 #ADD-opcode CHILD 0 #0 #3 CHILD 0 #1 #2 META 0 #'version' #1 MOD 0 #'when' #3:30pm

so now ADD 3 2 is just:

BASE  0  #ADD-opcode
CHILD 0 #0 #3
CHILD 0 #1 #2

or with addressing modes:

BASE  0  #ADD-opcode
CHILD 0 #0 n1
CHILD 0 #1 n2
BASE n1 #3
MOD n1 #'addrmode' 0
BASE n2 #2
MOD n2 #'addrmode' 0

and actually 'addrmode' would be an enum, not a string; and actually we'd need an assembler directive to makeup the fake names for nodes, which are actually just integers; and we may as well predeclare how many nodes there are; and let's put an ';' in the assembler for EOS:

DECL-NODES 3
.DECL-NODES [root n1 n2]
BASE   root  #ADD-opcode
CHILD root #0 n1
CHILD root #1 n2
BASE   n1 #3
MOD   n1 #addrmode 0
BASE   n2 #2
MOD   n2 #addrmode 0
;

and if we had an addr mode and operand for the opcode field:

DECL-NODES 4
.DECL-NODES [root op n1 n2]
BASE   root  op
BASE   op #ADD-opcode
MOD    op #addrmode 0
CHILD  root #0 n1
CHILD  root #1 n2
BASE   n1 #3
MOD    n1 #addrmode 0
BASE   n2 #2
MOD    n2 #addrmode 0
;

so this is 8 64-bit frames just to express ADD 2 3, which could have been expressed in 1. But it can express any graph, can reify edges, and have as many modifiers as needed, can have even a verb (base) or modifier be a 'phrase' with its own modifiers.

a more concise notation that obscures the frames might be:

root= @op[#ADD-opcode :addrmode=0] /[n1@[3 :addrmode=0] n2@[2 :addrmode=0]];
;;

leaving out the fact that we first deal with the root node, which is assumed:

@op[#ADD-opcode :addrmode=0] /[n1@[3 :addrmode=0] n2@[2 :addrmode=0]];
;;

leaving out the other names, which are unnecessary here b/c this graph is a tree:

[#ADD-opcode :addrmode=0] /[[#3 :addrmode=0] [2 :addrmode=0]];
;;

key: 

nodename=  ... ;  a line having to do with one node, 'nodename'
[]                node
name@[...]       name the following node
name@/           name the following edge (and reify it into a node)
#word             constant enum
:key=value        modifier
[] []             ordered, keywordless list of children
;;                EOS

instead of 'META', can just have 'LABEL' (node labels; but what if you try to LABEL it 'key' or 'role'? i assume this will be 'mangled' eg by prefixing it with 'LABEL:' in the underlying representation, or something like that)

need a HYPERE for hyperedges: HYPERE e role node

should hyperedges also have a type? if so, is that a metadata label 'type=?' on the hyperedge node? i guess so.

note that the word 'role' here is being used twice in different ways (the 'instruction role' of meta, base, child, modifier, and the hyperedge role). Mb 'hyperedge role' should be called 'port'. Should we rename 'instruction role' to? Probably, todo.

also, right now, BASE is being used to give atomic values to nodes (eg BASE op #ADD-opcode), but also to replace otherwise atomic things with subnodes (phrases) (eg BASE root op). Probably should split that into a VAL and a BASE, so:

BASE root op VAL op #ADD-opcode

also, when VAL is used with direct addressing, it can be used to 'quote' a subgraph.

also, how does LABEL work? at one level, labels should be pairs (label-key, label-value), but at another level, they should be reifiable into edges, edges which are themselves labeled with label-key and whose target is a node whose value is label-value. However, these edges should be meta-edges, or 'special' edges that aren't seen when enumerating the ordinary edges of a node.

METAHYPERE e role node note: METAHYPERE is only used to connect the lower-level (non-meta, or at least less meta) node to the hyperedge; meta-level-"peer" nodes are connected via HYPERE METAEDGE e node target-node short for METAHYPERE e #from source-node HYPERE e #to target-node LABEL n key val equivalent to METAEDGE e n val; LABEL e key. Note that this is recursive, so we don't actually expand LABEL to this; we don't actually create the meta-edges as reified nodes in this graph unless METAEDGE or METAHYPERE is used; but (when we define functions to access this structure later) they are still 'there' and can be seen in meta-edge enumerations (recursing into a metaedge enumeration on a label would give an infinite recursion).

mb rename META to ASTMETA

so what we have here appears to be a simple data format (and hence an implied data model) for oot graphs, plus a little bit on top of it.

The Oot graph stuff is:

On top of that, we add some basic semantics for AST-ish stuff:

So the opcodes are:

todo: how does this compare to the graph data model i was exploring before?

and for the AST stuff also:

todo: since some of the AST stuff is just graph stuff at a higher 'level', can we combine them? eg combine BASE and VAL, make CHILD a shortcut for EDGE in some way, combine META and LABEL?

---

so one goal is to try and unify the underlying graph ops and the 'AST opcodes' as stated in the previous sentence by using the concept of 'levels' somehow.

---

hmm, having second thoughts about separating BASE and VAL. Why not just combine BASE and VAL again and just let direct addressing be BASE and constant addressing be VAL? Currently we have also shoehorned that 'quoting' thing into VAL direct addressing but we could remove that, or we could give it its own opcode?

---

could use one of the 2 per-operand flag bits/custom addr mode bits to specify 'meta level', and thereby unify edge/metaedge (and hypere/metahypere). More generally, by using both of the 2 per-operand flag bits/custom addr mode bits, could select between one of 4 'meta levels' for each operand. This conveniently maps onto the 4 'meta levels' that i think about in my mostly-unrelated personal 'meta project'. Perhaps i could oversimplify my meta project into a concrete semantics for Oot Graphs!

The hypothesized collapse at level 4 could map onto the graph representation that i described above; all 'meta' stuff is treated as actual nodes, eg label metaedges are reified as actual nodes, causing an infinite regress/infinitely large graph.

Now the ASTMETA vs underlying METAEDGE distinction feels different; i wonder if it maps onto my 'meta level' project at all. Even if not, it might be good to include it here ('application level') rather than care about actually making a direct correspondence to my 'meta project levels'.

In some sense Oot Graphs feel like they can only ever be Level 2 on the meta project levels, which is another reason why this might be an oversimplification.

---

how could we use 2 bits PER OPERAND for meta levels? or do we only want to use the 2 per-instruction bits for this?

---

i guess the word for the thing corresponding to an opcode is not 'instruction' but 'operation' or 'op'; the 'instruction' is an instance of op+arguments found in a program, the 'op' is the thing that the opcode enumerates/identifies/represents.

(i already copied this into Asm Lang Principals)

---

upon further reflection, i guess my 'meta project levels' have 5 levels, not 4, because there is also the non-meta, 0-level (which is like the VAL op above). Recall that "a message about a dog" is meta-level 0 but "a message about a message" is meta-level 1.

Now what is the graph analogy of a 'message about a message'? It could be a node pointing to another node, as opposed to pointing to a non-node object.

Now meta-level 2 seems like can clearly be represented by reified edges (although these may have to be reified meta-edges). But what about meta-level 3, where we ascend to talking about the meta-levels themself? Clearly in this context we want something more generally useful than something like declaring a constant to represent the concept of "meta-level n" and have nodes pointing to it. Perhaps something like reification of the instructions in the LONG format, and in particular reification of the meta-level bits? I think we can do better: there are multiple views of a graph depending on if you care about metainfo or not. For example, you might want to enumerate the children of a node, excluding meta-edges; or you might want to enumerate the children of a node, including metaedges such as labels. You might want to consider a subgraph as just the base-level nodes; or you might want to consider the infinite subgraph given by reifying meta-nodes of every rank. Now, these are views of an entire graph, so how is this useful for the metabits? Because you can also consider an edge as 'pointing' to either the base-level VIEW of a node, or to the meta-level VIEW of the same node. So eg you might follow one edge from node B and find yourself at node A, base view, and follow another edge from node C (or even another edge from node B), and find yourself at the same node A, but in some meta view; a mutation to either should cause the corresponding change in the other.

Another related thing is quoting, e.g. quoted subgraphs, or mb even quoted nodes within graphs (which amounts to the same thing in the special case where the quoted subgraph is just a single node, along with its labels and other meta-info).

And if possible remember that we also would like to work in the 'application-level distinction', that is allowing something like the distinction between ASTMETA and CHILD without making ASTMETA the same as METAEDGE.

---

Not related to the previous, but something we need to think about for encoding; we need a way to say that the VAL of a node is the struct found at some memory address (so the instruction itself only contains a pointer, or perhaps a register ID, because the instruction is of fixed size but the value is of unbounded size), but we also need a way to say that the VAL of a node is a pointer itself.

---

since reified edges are just nodes, you don't need per-operand meta-level bits to distinguish them; but you do need per-operand meta-level bits to distinguish views. hmm, i'm beginning to wonder if the application-level distinction and the views is not in fact the main thing, and the use of meta-edges for labels is more the special case. That idea could be a breakthrough for my 'meta project' as well.

---

perhaps we could collapse most of the ops to just one, hypere, by using all these meta bits (we have 8) to select level ascents, application level meta, platform meta, quoting, etc

---

actually, the distinction between pointers as opaque values and as pointers IS relevant; this is sorta just another application-level meta, although in a way it's the opposite, because it concerns the underlying platform rather than the overlying application. eg, the underlying platform gives us memory and pointers, and sometimes we want the value of a node to be just the pointer itself, but other times we want it to be a structure that is pointed to by a pointer.

is this related to quoting? or is it more like a metaedge?

---

i wrote this in the meta project:

i had a great idea in proj-oot-ootAssemblyNotes7:

Related:

By including the hyperview within the same graph as the ordinary data, and allowing ordinary edges to target the hyperview of nodes within that graph, it is like you have added the word 'meta' to your language (by allowing meta to be represented within the semantics of your graph data structure).

Note that the metaedges can themselves be reified; this process could go infinitely deep, so that there is no 'completely reified graph', in the same way that there is no 'first real number greater than 0'; each time you can reify an edge and get another edge connecting its source to the reified edge, and similarly with labels if label-keys are used: each time you can reify the label into an edge between the labeled node and the label value, with one of these edges themselves labeled with the label key.

Now this hyperview may (or may not) be type-1 meta ('hyper'), but how do we get to type 2 ('meta'), where we are talking about the transition from ordinary dialog to meta-dialog? We need to be able to reify the edge connecting node A to the hyperview of node B; or perhaps we need to reify its 'metaness'. Perhaps just being able to reify edges is enough here, since this is now just an edge. Or perhaps we need to introduce in addition a 'metagraph' which describes the various levels of meta available. What i mean is, each node in the 'metagraph' represents one 'metalevel'. By 'metalevel' we could mean eg ordinary view vs hyperview, or we could mean eg meta-1 vs meta-2. I think actually there will be multiple 'metagraphs' available depending on just which facet of meta-ness we choose to represent; for example application level metas (eg if the application also has a concept of 'metaedge' that is ordinarily not included in enumerations of edges from nodes) vs reified edges vs platform-level meta (like pointers themselves vs. what the pointer points to); recall that meta level 3 was like the introduction of perspective in 3-d (or more accurately, projections of 3d into 2d).

---

short and long forms could be encoded as 'custom' decoders, allowing Porter to only implement MEDIUM

---

like in category theory, these graphs could have a 'homogeneous view' in which nodes are just edges that are self-loops (this is another alternative in addition to/instead of reifying nodes into edges).

---

meta bits can be relative/local, denoting (sub)level ascent/descent, rather than global

---

BayleShanks RecentChanges Bayle Shanks's website
Comments on proj-oot-ootAssemblyNotes7 This page is read-only View other revisions Administration
Last edited 2016-07-20 09:40 UTC by BayleShanks (diff)