WIP: Design of a transparent/local AVM

Protocol Design
1

This post is a WIP, posting to save – please ignore for now.

What might it look like to design a local AVM?

This post aims to explore this question. Note that a local AVM is the same thing as a transparent AVM, for by “local” we can infer both (a) an ordering domain and (b) a trust domain, so there is no need to regulate information disclosure (except between applications running in the AVM – but not in terms of the operations of the AVM itself).

The reader of this post may find it more comprehensible (I hope) with the prior context of @graphomath’s current draft AVM paper. I will attempt to define concepts in a standalone way, but for the sake of brevity I will elide the mathematical precision which the paper renders more explicit and may be helpful.

What is the AVM?

Abstractly, the AVM is a state machine, i.e. a function of the form

(S, I) \rightarrow (S, O)

where:

  • S is the type of AVM state (a collection of objects).
  • I is the type of AVM programs.
  • O is the type of AVM outputs.

An instance of the AVM is simply the pair of a specific state s (an inhabitant of S) and this transition function. Note that an instance of the AVM is thus itself an object. This will come in handy later.

What is the AVM state?

Roughly, the AVM state consists of a collection of objects, each associated with a unique identifier. For the sake of simplicity in this exposition, we can assume that identifiers are just natural numbers, although this is not necessary in practice. An object is a pair of an input history and a characteristic function which defines the future behavior of that object (see 4.1 of the ART report for a precise definition).

What are AVM programs?

An AVM program p is either:

  1. x <- INPUT; p', which:
    a. Reads the input (the message sent to this object)
    b. Stores the result in the variable x
    c. Continues execution of program p' in the updated context (now including x).
  2. x <- <VALUE>; p', which:
    a. Stores the value <VALUE> in the variable x. VALUE may be either a literal or another variable (so this instruction can be used to copy variables).
    b. Continues execution of program p' in the updated context (now including x)
  3. x <- FUNCTION_CALL <FUNC> <DATA>; p'
    a. Calls function FUNC on value VALUE. FUNC must be a computable function. Functions are represented by a multiformat. VALUE may be a literal or a variable.
    b. Stores the result in the variable x.
    c. Continues execution of program p' in the updated context (now including x)
  4. x <- CREATE <FUNC>; p', which:
    a. Creates a new object with characteristic function FUNC. FUNC must be a valid AVM program.
    b. Stores the new object’s identifier in the variable x.
    c. Continues execution of program p' in the updated context (now including x).
  5. DESTROY <ID>; p', which:
    a. Destroys the object with identifier ID. ID may be a literal or a variable.
    b. Continues execution of program p'.
  6. x <- CALL <ID> <MSG>; p', which:
    a. Sends the message MSG to the object associated with identifier ID. ID and MSG may be literals or variables.
    b. Stores the result in the variable x.
    c. Continues execution of program p' in the updated context (now including x).

    TODO: This is where we might want to allow “generalized method calls”, i.e. methods can also be programs which execute multiple calls (but make no state changes). This could probably also be done w/EVAL though.

  7. SWITCH x PROGS, a generalized case analysis, which:
    a. Selects a specific program in PROGS depending on the value of the variable x. PROGS is just a function (map) from values to programs.
    b. Executes that program in the current context.

    TODO: I think this instruction can be implemented w/FUNCTION_CALL and EVAL.

  8. x <- SCRY <FILTER>; p', “scry” or object lookup, which:
    a. Searches for objects matching FILTER
    b. Returns the results in the variable x (a set of identifiers)
    c. Continues execution of program p' in the updated context (now including x)
  9. x <- SELF; p', which:
    a. Stores the identifier of this object in the variable x
    b. Continues execution of program p' in the updated context (now including x)
  10. EVAL x; p', which:
    a. Attempts to interpret the value of x as an AVM program
    b. Executes that program in the current context
    c. Continues execution of program p' in the updated context

    TODO: Somehow we need to pass variables to the program.

  11. REVERT, which:
    a. Reverts all execution. Note that this revert cannot be caught.
  12. RETURN x, which:
    a. Discards the current context
    b. Returns the value associated with the variable x

Note: this program form could be represented as a S-expression.

Contexts are just maps from symbols to values. Values are untyped data. A given variable symbol may be written to only once, but read from any number of times.

TODO: Do we want more “first-class” AVM evaluation, e.g. including the state?

What are AVM outputs?

The AVM can be executed in two modes:

  • In “normal mode”, the output is just whatever is returned by the top-level program.
  • In “trace mode”, the output is whatever is returned by the top-level program, plus a full trace of all calls and responses which took place during program execution.
What is the difference between computation and messaging?

The difference between computation and messaging is simply whether or not there is some need to track any state beyond the message response. Computation could also be modeled as creating an object, sending a message to that object, getting a response, and destroying the object (thereby allowing the object history/state to be garbage collected as it can no longer be referred to), but this seems less elegant.

Functions perform computations. They can be called any number of times and have no state. Functions must be pure functions in the mathematical sense, i.e. (potentially partial) maps from the domain to the codomain. Failure is equivalent to REVERT.

Process objects process messages. They can be created (once), called (any number of times), and destroyed (once). Process objects cannot themselves store any data – they can only create, destroy, look up, and call other objects, and perform computations.

Data objects contain data. They can only be created (once), read (any number of times), and destroyed (once). Data objects cannot themselves execute any computations, perform any calls, etc. – they are “just data”.

TODO: This needs to be reflected in the instruction set.

Ownership

Objects each have an owner. The owner of an object is either:

  • the object which created this object, if this object was created by another object, or
  • the user, if this object was created by a top-level AVM program

In the implementation, the user may be represented by a sentinel “zero-identifier”.

Only the owner of an object can call the object or scry for it. The owner of an object cannot be changed. A similar effect can be achieved by destroying the previous object and creating a new one (through a different intermediary object, which will become the owner of the new object).

This rather strict limitation ensures that call structures always take the form of an acyclic DAG, i.e. child can never call parent.

Note: this ownership structure seems somewhat similar to Unix processes, for which I wasn’t able to find a good formalism in a few minutes of searching, but this might be worth exploring more.

Properties
  • Hierarchical equivalence
    • AVM state can be segmented by object
    • Equivalent to running a little AVM instance w/just that object’s state
      • Other objects cannot be called by non-owner
    • Thus SCRY is equivalent to visibility over the object’s own history
      • Equivalent to AVM ART definition of “object”
  • Behavioral transparency
    • Objects can be replaced by behaviorally equivalent objects
  • Transactional semantics
    • Computation can be reordered up to transactional equivalence
Misc notes
  • This AVM does not feature unification. Unification would involve objects defined relationally instead of functionally, I think. It’s a bit further from the current paper. Worth exploring in the near future though.
  • This AVM also does not feature any kind of typesystem, it is untyped. A typesystem should be possible to build on top.
  • Currently, this AVM does not support reflection. This can probably be added but I haven’t thought too much about it yet and we want to be careful not to break the above properties.
2 Likes
2

Notes to self from work on 30.08.2025:

  • It might be a bit more convenient to use S-expressions (equivalent to Nock nouns) as the basic data type, where an S-expression is either an integer or an ordered pair of S-expressions. Then we can more naturally represent programs as data (as a list of instructions with arguments), more naturally handle multiple arguments to function calls (without encoding/decoding all of the time), and more naturally handle scry returns (which will be a set).
  • Simple reflection (namely, an instruction which inspects whether a given object referenced by name is a data object or a process object, and in the latter case, what the program is) should be easy to add. This plus scry should be sufficient to implement any kind of “higher-level” reflection we might want, as there simply isn’t any other state (other than state kept to compute fresh names, which we explicitly do not want to be readable, as program behaviour should not depend on names). However, this may break the ability to replace objects by behaviorally equivalent objects (at least in a program transformation sense), since the program representations might be different. We might be able to implement reflection at a higher level without this, needs more investigation.
  • This VM structure is designed to be parameterized over the function multiformat not only at the whole VM level but potentially at the individual object level (individual objects may “understand” different subsets of the multiformat), and the multiformat itself can be changed over time while the VM is running without breaking any existing objects as long as the changes are append-only (e.g. new number, newly created objects can start supporting the new function representation). Perhaps the multiformat should simply become part of the state of the AVM. This would then dovetail nicely with and become incorporated into the “hierarchical equivalence” property, and we could add some DEFINE_FUNCTION instruction. Here, though, we need to think about how to represent a function which is a black box to the AVM itself (the host machine just needs to know how to compute it).
3

An Argument against having Functions along with Message Sends

It is much more elegant actually! Let us think of how languages with functions and modules work

(defmodule whatever
  (defun foo (x) (+ x 3)))

(whatever:foo 5) ;;  8

(import whatever)

(foo 5) ;; 8

Here we define a module whatever and a function foo.

We invoke it by saying whatever:foo.

However if we zoom out, we provided the context whatever to foo. Now imagine if whatever is an object not a module… then the semantics are the same. Even in the case of (import whatever), we are implicitly sending foo to it.

This is to say that modules are objects and invoking functions within their space is equivalent to selecting a method on the class side. Let me show this off in Smalltalk

1602×1265 139 KB

Thus if we have any kind of module system it is equivalent to sending a message, and we can simplify our instruction set by doing so, no extra cruft needed for functions.

Reflection

This is very important. One important property of Nock that both @terence and @ray can attest to is that nock can read from itself and reflect, which is a super power.

The base layer should be able to have all of these powers as it’s harder to get it later.

@cdetroye and I have already theorized about how to gain back properties that you may wish and this is namely by having a reflection API at a higher level. I.E. if we are working on the base objects if we don’t see the message send (reflect x) then we know all the meta properties we normally assume is fine. We can enforce this via the MOP, such that even accessing the class side is done through reflect. This means that we can set the MOP up to let us define explicitly what properties we want of objects, sending in reflect does mean that the properties held there are less reliable, but as @cdetroye has shown me you get some good powers by segmenting it by having a single entry point up.

Thus I recommend making this powerful and we restrict it higher, if you need argumentation, let me know and maybe we can discuss it at the hacker house with the other designers of AL in the room.

Ownership

This seems a bit weird to me. You are basically making the argument that the object that everything inherits from (proto object) basically has an identity API that gets constructed.

In particular I find:

This rather strict limitation ensures that call structures always take the form of an acyclic DAG, i.e. child can never call parent.

questionable. As is this illegal?

2861×1682 172 KB

Here I made a doubly linked list, as we can see the cons cell containing 3 also made the cons cell containing 5. However since it’s a doubly linked list the one containing 5 can reference it’s parent and invoke functions on.

We can see it by the arrows in the graphics as it does go both ways. Thus we can compute

self pcdr car

Here I am not mutating the parent but simply invoking a method. I’ve seen this design in other places as well, such as passing yourself to a lower context so that has enough information to operate and to create better visuals in an MVVC like construction.

In a functional world this is a bit harder to do data structure wise (it takes a single mutation), but one gets around this by having another structures which can index into it. I believe I’ve explored this approach in the past here

Representation

This is the right starting point, you work on this structure typically as the meta circular machinery. It depends how much you want to be like smalltalk/self vs how much you want to be like nock/lisp.

I believe you need to do more research on this point

Conditions

For this instruction why can it not be caught? Have you looked into Condition systems? Also Prolog style backtracking may be on interest here.

Linked above is a good book on implementing a condition system.

I mention the condition system as it does let you program different ways of restarting computation or reverting the actions in a programmatic way. It could maybe be built ontop of the revert primitive here depending on how you design it in particular.

Other Notes

There are many other points I’d like to respond to and help ideate on as well, but I am currently out of time.

3 Likes
4

The difference between objects and functions in my model here is that objects have a history and functions do not. Modeling a pure function as an object which has a history doesn’t really make sense. However, the frontend syntax you describe here is totally compatible with a fundamental model which does make a distinction between objects and functions – it is still the case that you can send a message to a function (and get back the result of computing the function), functions just do not have an identity or a history (whereas objects do).

OK, noted.

I’m not familiar with what you’re referencing here (“proto object”, “identity API”), do you have a link?

In general, I’m trying to construct something similar to process isolation, such that multiple users can use the VM, create their own objects, etc. while still guaranteeing that objects will behave as expected. More specifically, this ownership restriction provides for hierarchical transactional objects, where the objects created by an object can always be “folded into” it (or modeled as within it), since they cannot be called from elsewhere. It is probably possible to relax the restriction somewhat while preserving that, e.g. allow children to call parents, but this introduces some complexities in modeling (would the child-parent call be part of the history, or not? if the former, where is it in history, since the triggering call has not been responded to yet? if the latter, what exactly is this? etc.).

However, it would be easy to drop this restriction and leave the rest of the construction the same, we’d just lose these guarantees. I suppose that this ownership check could even be implemented in the object code (program), and perhaps that would be preferable to putting it in the base model.

I suppose that it could be (some sort of handler when you call an object). This instruction is intended to revert any state changes (“as if the transaction never happened”), so we’d need to think about how that works with catch/handle semantics, but I can imagine a basic first pass (it is as if the call in question never happened, and you have to handle the error) would be reasonable enough, and possible to build on top of.

1 Like