Miden assembly serialization

[bobbinth]

We have several inter-related updates planned for v0.3 release (#361 ) which aim to improve Miden assembly. I thought it would make sense to describe the goals and challenges in more detail.

First, let's go over the intended use of Miden assembly:

1. We use Miden assembly to write Miden standard library.
2. Private programs (e.g. for note scripts, account code) would be stored by wallets in Miden assembly.
3. Public programs which go on chain (e.g., note scripts, account code) would be provided in Miden assembly.

Currently, Miden assembly is written and stored in plain text. This creates a couple of challenges:

• Parsing text adds overhead (which is probably non negligible).
• We probably don't want to put plain text on chain.

An obvious question would be: why not compile Miden assembly to MAST and then just serialize/deserialize MAST as needed. There are a couple of reasons for this (though we should probably examine if they are still as valid as I originally thought):

1. MAST is much less readable as a lot of the information about procedure names etc. is erased by the time we get to it. So, if we compiled standard library into MAST, debugging code might become more complicated.
2. When building MAST, a lot of procedures get inlined into the code because this inlining could lead to much more efficient code (this is especially true for small procedures with no control flow logic). Thus, Miden assembly should be much more compact than serialized MAST code (though, introduction of code block tables in Add Call block to program MAST #375 changes calculus here a bit).

So, the approach we currently are thinking of implementing is to serialize Miden assembly into binary format. This solves our challenges as follows:

• The binary format would be much more compact than plain text.
• It would also be much easier to parse and convert into MAST.
• We could have different options for compiling into binary format. For example, standard library could be compiled in a way which retains procedure names, doc comments etc., but the code that would need to go on chain, would have all that info stripped to make it as compact as possible.

Overall, serializing/deserializing Miden assembly should work pretty well. However, there are a few challenges. All these challenges are related to handling exec, call, and (in the future) syscall instructions. Specifically, the question is: how should we specify call targets for these instructions.

In the plain-text source, we use strings (fully qualified paths). When a procedure from standard library is invoked in a program (via the exec instruction) we'd look up the module to which this procedure belongs, and then in that module would find the procedure by name. But what should we do in the binary format?

For code which is stored locally (e.g., stdlib), we can probably still use strings. In fact, this would probably be the simplest thing to do. However, for the code which goes on chain, using string-based references is probably not a good idea. So, there are might be a few ways to do better.

First, for local procedures (procedures declared in the same module), we could just use numerical indexes. For example:

proc.foo
    <instructions>
end

proc.bar
    <instructions>
end

Procedure foo would have index 0, and procedure bar would have index 1.

Second, for procedure calls to well-known libraries (e.g., stdlib), we could use something like a 20-byte hash of the fully-qualified path. This would mean that when instantiating a library in memory, we'd need to create a map which would allow us to look up module and procedure names by hash. But I think that shouldn't be difficult to do and there could be interesting ways of optimizing this lookup process.

Third, in some cases, we'll need to make calls by MAST root. For example, this is something that would happen when a note script invokes one of interface methods of an account via call instruction. Thus, to execute such programs we'd need to maintain a map of MAST roots to corresponding procedure definitions (we'd probably need to do this anyway to be able to execute public account methods).

To summarize the above:

We could have different variants of relevant instructions. For example, exec instruction could have 4 different variants:

1. Invoking via fully-qualified path for procedures in well-known libraries.
2. Invoking via local procedure index.
3. Invoking via hash of the fully-qualified path for procedures in well-known libraries.
4. Invoking via MAST root for procedures in on-chain accounts.

Similar could be applied to call and syscall though more thinking is needed to understand whether all of the above options are relevant to these instructions.

Also, we could potentially get rid of the first variant (the fully-qualified path) to reduce the number of variants.

[vlopes11]

As discussed in #298 , it is desirable to decouple the assembler from stdlib.

The following is a variation over a foundational idea proposed by @bobbinth

/// A procedure is a mapping from a name to parseable contents
pub trait Procedure {
    type Name;
    type Contents;
}

/// The index is a pure function that takes a domain & name, and injectively maps to an index
pub trait IndexedProcedure {
    type Domain;
    type Index: Clone;
    type Procedure: Procedure;

    fn index(domain: &Self::Domain, name: &<Self::Procedure as Procedure>::Name) -> Self::Index;
}

/// A source provider will map an index to the source contents. As a regular source file, it might
/// contain multiple procedures, each indexed by its own unique idx.
pub trait SourceProvider {
    type Error;
    type Procedure: IndexedProcedure;

    fn contents(
        &self,
        index: &<Self::Procedure as IndexedProcedure>::Index,
    ) -> Result<
        &<<Self::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
        Self::Error,
    >;
}

/// The assembler will take a procedure contents and parse these into an AST.
///
/// The main restriction imposed by this scheme is that the assembler should behave as a pure
/// function; hence, it should have no state.
pub trait Assembler {
    type Error: From<<Self::SourceProvider as SourceProvider>::Error>;
    type SourceProvider: SourceProvider;
    type Ast;

    fn assemble(
        contents: &<<<Self::SourceProvider as SourceProvider>::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
    ) -> Result<Self::Ast, Self::Error>;

    fn assemble_from_source(
        provider: &Self::SourceProvider,
        index: &<<Self::SourceProvider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<Self::Ast, Self::Error> {
        let contents = provider.contents(index)?;

        Self::assemble(contents)
    }
}

/// This error variant will be returned when an append+fetch returns None.
pub enum ProcedureProviderError {
    InconsistentAppend,
}

/// A procedure provider will be a mapping from an index to a parsed AST.
pub trait ProcedureProvider {
    type Error: From<<Self::Assembler as Assembler>::Error> + From<ProcedureProviderError>;
    type Assembler: Assembler;

    fn append(
        &self,
        index: <<<Self::Assembler as Assembler>:: SourceProvider as SourceProvider>::Procedure as IndexedProcedure>::Index,
        ast: <Self::Assembler as Assembler>::Ast,
    );

    fn fetch(
        &self,
        index: &<<<Self::Assembler as Assembler>:: SourceProvider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Option<<Self::Assembler as Assembler>::Ast>;

    fn fetch_or_assemble(
        &self,
        sources: &<Self::Assembler as Assembler>::SourceProvider,
        index: &<<<Self::Assembler as Assembler>:: SourceProvider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<<Self::Assembler as Assembler>::Ast, Self::Error> {
        match self.fetch(index) {
            Some(ast) => Ok(ast),

            None => {
                let ast = Self::Assembler::assemble_from_source(sources, index)?;

                self.append(index.clone(), ast);
                self.fetch(&index)
                    .ok_or_else(|| ProcedureProviderError::InconsistentAppend.into())
            }
        }
    }
}

/// This is a set of concrete implementations of the traits scheme
pub mod concrete {
    use std::collections::HashMap;
    use std::{mem, sync};

    /// An index is normally a truncated representation of the tokens of some procedure, stripped
    /// of the tokens that will not compose the AST such as comments, style indentation,
    /// linebreaks, etc.
    pub type Index = [u8; 20];

    pub enum Error {
        ProcedureNotFound,
        InconsistentAppend,
    }

    impl From<super::ProcedureProviderError> for Error {
        fn from(value: super::ProcedureProviderError) -> Self {
            match value {
                super::ProcedureProviderError::InconsistentAppend => Self::InconsistentAppend,
            }
        }
    }

    /// The AST in this example is a 1:1 with the source contents.
    #[derive(Debug, Clone)]
    pub struct Ast {
        pub contents: String,
    }

    /// A procedure is just a name+contents tuple
    pub struct Procedure {
        pub name: String,
        pub contents: String,
    }

    impl super::Procedure for Procedure {
        type Name = String;
        type Contents = String;
    }

    /// The indexed procedure will just bind a domain+index to a procedure.
    ///
    /// In this example, we XOR the chunks of the domain+name so we injectively compute its index
    pub struct IndexedProcedure {
        pub domain: String,
        pub index: Index,
        pub procedure: Procedure,
    }

    impl super::IndexedProcedure for IndexedProcedure {
        type Domain = String;
        type Index = Index;
        type Procedure = Procedure;

        fn index(domain: &String, name: &String) -> Index {
            // simple & cheap injective XOR based function
            format!("{}::{}", domain, name)
                .as_bytes()
                .chunks(mem::size_of::<Index>())
                .fold(Index::default(), |mut idx, chunk| {
                    idx.iter_mut().zip(chunk.iter()).for_each(|(i, c)| *i ^= *c);
                    idx
                })
        }
    }

    /// This source provider emulates a disk with a source file and will return procedure contents
    /// based on an index
    pub struct SourceProvider {
        pub contents: HashMap<Index, String>,
    }

    impl super::SourceProvider for SourceProvider {
        type Error = Error;
        type Procedure = IndexedProcedure;

        fn contents(&self, index: &Index) -> Result<&String, Error> {
            self.contents.get(index).ok_or(Error::ProcedureNotFound)
        }
    }

    /// The assembler is a set of pure functions that will construct the AST, provided contents
    pub struct Assembler;

    impl super::Assembler for Assembler {
        type Error = Error;
        type SourceProvider = SourceProvider;
        type Ast = Ast;

        fn assemble(contents: &String) -> Result<Self::Ast, Self::Error> {
            Ok(Ast {
                contents: contents.clone(),
            })
        }
    }

    /// A procedure provider will map indexes to parsed ASTs
    pub struct ProcedureProvider {
        procedures: sync::Arc<sync::Mutex<HashMap<Index, Ast>>>,
    }

    impl super::ProcedureProvider for ProcedureProvider {
        type Error = Error;
        type Assembler = Assembler;

        fn append(&self, index: Index, ast: Ast) {
            // unwrap is used here for the sake of simplicity. alternatively, we can use
            // parking_lot for a robust infallible RwLock implementation
            //
            // https://docs.rs/parking_lot/latest/parking_lot/type.RwLock.html
            self.procedures.lock().unwrap().insert(index, ast);
        }

        fn fetch(&self, index: &Index) -> Option<Ast> {
            self.procedures.lock().unwrap().get(index).cloned()
        }
    }
}

[vlopes11]

Note: the AST is returned as owned there. It can as well be a pointer to a memory arena of parsed contents so it can quickly unlock the procedure provider. This would be one alternative if passing the owned AST proves to be expensive.

[bobbinth]

Thank you! This is very well thought out. I have a few comments - some of which might be the result of me not understanding the intent correctly. If so, please correct me in such cases.

First, I am not sure we need to have a concept of SourceProvider - at least at this level. Specifically, we have two parts of transforming source code to MAST. The first part is to transform source code to an AST (which will be done by the parsers). And the second part is to transform AST into MAST, and this is what the main task of the Assembler would be.

So, the main methods on the Assembler would not output AST but would output a Program struct (which describes the MAST of the program). Specifically, the methods could be something like this:

impl Assembler {
    pub fn assemble(&self, ast: ProgramAst) -> Result<Program, AssemblyError> {
        ...
    }
    
    pub fn assemble_from_source(&self, source: &str) -> Result<Program, AssemblyError> {
        let ast = // convert source into AST using parser
        self.assemble(ast)
    }
}

In this model, all library code (e.g., code in stdlib) would already be in AST form by the time it gets to the assembler - so, the assembler does not need to be aware of the source of this code. Concretely, we will run stdlib source code through the parser, get AST for each module, and then serialize these ASTs. Then, when we need to instantiate the assembler, we'll just deserialize these ASTs, and so, the assembler would not need to work with source files of stdlib.

Second, I am not sure we can make Assembler stateless. The reason being is that one of the heavy parts of the compilation is transforming procedure AST into MAST. This transformation is done by the assembler, and because it is pretty heavy, we want to cache the resulting MAST for future reuse. Specifically, we want to maintain a map in the assembler which maps procedure path hash to procedure's MAST (currently, this is accomplished via module map). Moreover, the assembler needs to know the kernel in the context of which the program is being executed, as well as a few other properties. Overall, I think the shape of the Assembler struct could be something like this:

pub struct Assembler {
    kernel: Kernel,
    /// Stores MASTs for Kernel procedures which are built at assembler construction time.
    kernel_procs: BTreeMap<[u8; 20], Procedure>,
    /// Stores MASTs of procedures invoked from external libraries (this is the MAST cache).
    library_procs: BTreeMap<[u8; 20], Procedure>,
    /// Contains ASTs of all relevant library procedures.
    procedure_provider: ProcedureProvider,
    in_debug_mode: bool,
}

With this structure, whenever we encounter an ExecImported node in the program AST, we would do the following:

1. Look for the already compiled MAST of this procedure in library_procs.
2. If the procedure is not found in library_procs, look for it in procedure_provider. If it is found there, then we need to convert the procedure into MAST (this in term will require converting all procedures invoked by this procedure into MASTs as well).
   a. Once the procedure is converted to MAST, we'd save it to library_procs. This way, next time we need its MAST, we don't need to compile it again.
3. Once we have the procedure's MAST we return it to the caller.

The interface of ProcedureProvider could be something like this:

impl ProcedureProvider {
    pub fn fetch(&self, index: [u8; 20]) -> Option<ProcedureAst> {
        ...
    }
}

We don't need to have an append() method in here because from external standpoint, procedure provider will not change after construction. Also, I'm not sure we need to make index generic - we can probably make it so that it is always a 20-byte value. I think the bulk of the complexity of procedure provider would be to take a list of ModuleAst structs (probably grouped by library), and convert them to a map of [u8; 20] -> ProcedureAst.

[bobbinth]

One other though, because we differentiate between local and imported procedures, it might be difficult to get procedures one by one from the ProcedureProvider. A simpler (though less efficient) method would be to switch to ModuleProvider where we get the and parse the full module and keep track of MASTs only for exported procedures from a given module. It is worth examining whether is approach is easier to take initially.

The interface for ModuleProvider could be something like this:

impl ModuleProvider {
    pub fn fetch(&self, proc_index: [u8; 20]) -> Option<ModuleAst> {
        ...
    }
}

[bobbinth]

Assembler constructor could look something like:

pub fn new(
    kernel_source: &str,
    module_provider: ModuleProvider,
    in_debug_mode: bool,
) -> Result<Self, AssemblyError> {
    ...
}

[vlopes11]

The main confusion is that I named Assembler what should have been Parser. Thanks for all the comments, I'll update the skeleton with your input so we make a second round

[vlopes11]

I redesigned the initial proposal taking the comments into account and came with this new model. While the model is being evaluated, will in parallel build an example over that

/// A procedure is a mapping from a name to parseable contents
pub trait Procedure {
    type Name;
    type Contents;
}

/// The index is a pure function that takes a domain & name, and injectively maps to an index
pub trait IndexedProcedure {
    type Domain;
    type Index: Clone;
    type Procedure: Procedure;

    fn index(domain: &Self::Domain, name: &<Self::Procedure as Procedure>::Name) -> Self::Index;
}

/// A source provider will map an index to the source contents. As a regular source file, it might
/// contain multiple procedures, each indexed by its own unique idx.
pub trait SourceProvider {
    type Error;
    type Procedure: IndexedProcedure;

    fn contents(
        &self,
        index: &<Self::Procedure as IndexedProcedure>::Index,
    ) -> Result<
        &<<Self::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
        Self::Error,
    >;
}

pub trait Ast: Clone + IntoIterator<Item = Self> {
    type Provider: SourceProvider;

    fn indexable(
        &self,
    ) -> Option<(
        &<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Domain,
        &<<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Procedure as Procedure>::Name,
    )>;

    fn index(
        &self,
    ) -> Option<<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index> {
        self.indexable().map(|(domain, name)| {
            <<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::index(domain, name)
        })
    }
}

pub trait Parser {
    type Error: From<<<Self::Ast as Ast>::Provider as SourceProvider>::Error>;
    type Ast: Ast;

    fn parse(
        contents: &<<<<Self::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
    ) -> Result<Self::Ast, Self::Error>;

    fn parse_from_source(
        provider: &<Self::Ast as Ast>::Provider,
        index: &<<<Self::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<Self::Ast, Self::Error> {
        let contents = provider.contents(index)?;

        Self::parse(contents)
    }
}

/// This error variant will be returned when an append+fetch returns None.
pub enum ProcedureProviderError {
    InconsistentAppend,
}

pub trait ProcedureProvider {
    type Error: From<<Self::Parser as Parser>::Error> + From<ProcedureProviderError>;
    type Parser: Parser;

    fn append(
        &self,
        index: <<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
        ast: <Self::Parser as Parser>::Ast,
    );

    fn fetch(
        &self,
        index: &<<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Option<<Self::Parser as Parser>::Ast>;

    fn fetch_or_parse(
        &self,
        sources: &<<Self::Parser as Parser>::Ast as Ast>::Provider,
        index: &<<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<<Self::Parser as Parser>::Ast, Self::Error> {
        match self.fetch(index) {
            Some(ast) => Ok(ast),

            None => {
                let ast = Self::Parser::parse_from_source(sources, index)?;

                self.append(index.clone(), ast);
                self.fetch(&index)
                    .ok_or_else(|| ProcedureProviderError::InconsistentAppend.into())
            }
        }
    }
}

pub trait AssemblerContext {
    type IndexedAst: From<<<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast>
        + FromIterator<Self::IndexedAst>;
    type Provider: ProcedureProvider;
    type Mast;

    fn append(
        &self,
        index: <<<<<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    );

    fn build(&self, ast: Self::IndexedAst) -> Self::Mast;

    /// Traverse the AST in postorder, mutating the call nodes into indexed call
    ///     e   |      e
    ///    / \  |     / \
    ///   c   d |--> i   d, i |-> c
    ///  / \    |                / \
    /// a   b   |               a   b
    fn reduce(
        &self,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    ) -> Self::IndexedAst {
        ast.into_iter()
            .map(|node| {
                if let Some(index) = node.index() {
                    self.append(index, node.clone());
                }

                Self::IndexedAst::from(node)
            })
            .collect()
    }

    fn compile(
        &self,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    ) -> Self::Mast {
        let ast = self.reduce(ast);

        self.build(ast)
    }
}

[vlopes11]

Note: we probably want to make the reduce and build operations async so they can be executed in parallel

[vlopes11]

Update with example. We don't need to follow this structure, but it might be beneficial to diff from the current implementation and extract the points that are advantageous to decouple stdlib from assembly.

/// A procedure is a mapping from a name to parseable contents
pub trait Procedure {
    type Name;
    type Contents;
}

/// The index is a pure function that takes a domain & name, and injectively maps to an index
pub trait IndexedProcedure {
    type Domain;
    type Index: Clone;
    type Procedure: Procedure;

    fn index(domain: &Self::Domain, name: &<Self::Procedure as Procedure>::Name) -> Self::Index;
}

/// A source provider will map an index to the source contents. As a regular source file, it might
/// contain multiple procedures, each indexed by its own unique idx.
pub trait SourceProvider {
    type Error;
    type Procedure: IndexedProcedure;

    fn contents(
        &self,
        index: &<Self::Procedure as IndexedProcedure>::Index,
    ) -> Result<
        &<<Self::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
        Self::Error,
    >;
}

pub trait Ast: Clone + IntoIterator<Item = Self> {
    type Provider: SourceProvider;

    fn indexable(
        &self,
    ) -> Option<(
        &<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Domain,
        &<<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Procedure as Procedure>::Name,
    )>;

    fn index(
        &self,
    ) -> Option<<<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index> {
        self.indexable().map(|(domain, name)| {
            <<Self::Provider as SourceProvider>::Procedure as IndexedProcedure>::index(domain, name)
        })
    }
}

pub trait Parser {
    type Error: From<<<Self::Ast as Ast>::Provider as SourceProvider>::Error>;
    type Ast: Ast;

    fn parse(
        contents: &<<<<Self::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Procedure as Procedure>::Contents,
    ) -> Result<Self::Ast, Self::Error>;

    fn parse_from_source(
        provider: &<Self::Ast as Ast>::Provider,
        index: &<<<Self::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<Self::Ast, Self::Error> {
        let contents = provider.contents(index)?;

        Self::parse(contents)
    }
}

/// This error variant will be returned when an append+fetch returns None.
pub enum ProcedureProviderError {
    InconsistentAppend,
}

pub trait ProcedureProvider {
    type Error: From<<Self::Parser as Parser>::Error> + From<ProcedureProviderError>;
    type Parser: Parser;

    fn append(
        &self,
        index: <<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
        ast: <Self::Parser as Parser>::Ast,
    );

    fn fetch(
        &self,
        index: &<<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Option<<Self::Parser as Parser>::Ast>;

    fn fetch_or_parse(
        &self,
        sources: &<<Self::Parser as Parser>::Ast as Ast>::Provider,
        index: &<<<<Self::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
    ) -> Result<<Self::Parser as Parser>::Ast, Self::Error> {
        match self.fetch(index) {
            Some(ast) => Ok(ast),

            None => {
                let ast = Self::Parser::parse_from_source(sources, index)?;

                self.append(index.clone(), ast);
                self.fetch(&index)
                    .ok_or_else(|| ProcedureProviderError::InconsistentAppend.into())
            }
        }
    }
}

pub trait Assembler {
    type Error: From<<Self::Provider as ProcedureProvider>::Error>;
    type IndexedAst: From<<<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast>
        + FromIterator<Self::IndexedAst>;
    type Provider: ProcedureProvider;
    type Mast;

    fn append(
        &self,
        index: <<<<<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast as Ast>::Provider as SourceProvider>::Procedure as IndexedProcedure>::Index,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    );

    fn build(&self, ast: Self::IndexedAst) -> Result<Self::Mast, Self::Error>;

    /// Traverse the AST in postorder, mutating the call nodes into indexed call
    ///     e   |      e
    ///    / \  |     / \
    ///   c   d |--> i   d, i |-> c
    ///  / \    |                / \
    /// a   b   |               a   b
    fn reduce(
        &self,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    ) -> Self::IndexedAst {
        ast.into_iter()
            .map(|node| {
                if let Some(index) = node.index() {
                    self.append(index, node.clone());
                }

                Self::IndexedAst::from(node)
            })
            .collect()
    }

    fn compile(
        &self,
        ast: <<Self::Provider as ProcedureProvider>::Parser as Parser>::Ast,
    ) -> Result<Self::Mast, Self::Error> {
        let ast = self.reduce(ast);

        self.build(ast)
    }
}

pub mod concrete {
    use std::collections::HashMap;
    use std::sync::{Arc, Mutex};
    use std::{mem, vec};

    use crate::{IndexedProcedure as _, ProcedureProvider as _};

    /// An index is normally a truncated representation of the tokens of some procedure, stripped
    /// of the tokens that will not compose the AST such as comments, style indentation,
    /// linebreaks, etc.
    pub type Index = [u8; 20];

    pub enum Error {
        ProcedureNotFound,
        InconsistentAppend,
    }

    impl From<super::ProcedureProviderError> for Error {
        fn from(value: super::ProcedureProviderError) -> Self {
            match value {
                super::ProcedureProviderError::InconsistentAppend => Self::InconsistentAppend,
            }
        }
    }

    #[derive(Clone)]
    pub enum Ast {
        Noop,
        Call { domain: String, name: String },
        Node(Vec<Self>),
    }

    impl IntoIterator for Ast {
        type Item = Self;
        type IntoIter = vec::IntoIter<Self>;

        fn into_iter(self) -> Self::IntoIter {
            match self {
                Ast::Noop => vec![Ast::Noop],
                Ast::Call { domain, name } => vec![Ast::Call { domain, name }],
                Ast::Node(node) => node,
            }
            .into_iter()
        }
    }

    impl super::Ast for Ast {
        type Provider = SourceProvider;

        fn indexable(&self) -> Option<(&String, &String)> {
            match self {
                Ast::Call { domain, name } => Some((domain, name)),
                _ => None,
            }
        }
    }

    /// A procedure is just a name+contents tuple
    pub struct Procedure {
        pub name: String,
        pub contents: Ast,
    }

    impl super::Procedure for Procedure {
        type Name = String;
        type Contents = Ast;
    }

    /// The indexed procedure will just bind a domain+index to a procedure.
    ///
    /// In this example, we XOR the chunks of the domain+name so we injectively compute its index
    pub struct IndexedProcedure {
        pub domain: String,
        pub index: Index,
        pub procedure: Procedure,
    }

    impl super::IndexedProcedure for IndexedProcedure {
        type Domain = String;
        type Index = Index;
        type Procedure = Procedure;

        fn index(domain: &String, name: &String) -> Index {
            // simple & cheap injective XOR based function
            format!("{}::{}", domain, name)
                .as_bytes()
                .chunks(mem::size_of::<Index>())
                .fold(Index::default(), |mut idx, chunk| {
                    idx.iter_mut().zip(chunk.iter()).for_each(|(i, c)| *i ^= *c);
                    idx
                })
        }
    }

    /// This source provider emulates a disk with a source file and will return procedure contents
    /// based on an index
    pub struct SourceProvider {
        pub contents: HashMap<Index, Ast>,
    }

    impl super::SourceProvider for SourceProvider {
        type Error = Error;
        type Procedure = IndexedProcedure;

        fn contents(&self, index: &Index) -> Result<&Ast, Error> {
            self.contents.get(index).ok_or(Error::ProcedureNotFound)
        }
    }

    pub struct Parser;

    impl super::Parser for Parser {
        type Error = Error;
        type Ast = Ast;

        fn parse(contents: &Ast) -> Result<Ast, Error> {
            // for the sake of simplicity, we just transparently parse here

            Ok(contents.clone())
        }
    }

    pub struct ProcedureProvider {
        pub procedures: Arc<Mutex<HashMap<Index, Ast>>>,
    }

    impl super::ProcedureProvider for ProcedureProvider {
        type Error = Error;
        type Parser = Parser;

        fn append(&self, index: Index, ast: Ast) {
            // unwrap is used here for the sake of simplicity. alternatively, we can use
            // parking_lot for a robust infallible RwLock implementation
            //
            // https://docs.rs/parking_lot/latest/parking_lot/type.RwLock.html
            self.procedures.lock().unwrap().insert(index, ast);
        }

        fn fetch(&self, index: &Index) -> Option<Ast> {
            self.procedures.lock().unwrap().get(index).cloned()
        }
    }

    #[derive(Clone)]
    pub enum IndexedAst {
        Noop,
        Call(Index),
        Node(Vec<Self>),
    }

    impl From<Ast> for IndexedAst {
        fn from(ast: Ast) -> Self {
            match ast {
                Ast::Noop => Self::Noop,
                Ast::Call { domain, name } => Self::Call(IndexedProcedure::index(&domain, &name)),
                Ast::Node(node) => Self::Node(node.into_iter().map(Self::from).collect()),
            }
        }
    }

    impl FromIterator<IndexedAst> for IndexedAst {
        fn from_iter<T: IntoIterator<Item = IndexedAst>>(iter: T) -> Self {
            let nodes: Vec<_> = iter.into_iter().collect();
            let len = nodes.len();

            match len {
                0 => Self::Noop,
                1 => nodes[0].clone(),
                _ => Self::Node(nodes),
            }
        }
    }

    impl IntoIterator for IndexedAst {
        type Item = Self;
        type IntoIter = vec::IntoIter<Self>;

        fn into_iter(self) -> Self::IntoIter {
            match self {
                IndexedAst::Noop => vec![Self::Noop],
                IndexedAst::Call(index) => vec![Self::Call(index)],
                IndexedAst::Node(nodes) => nodes,
            }
            .into_iter()
        }
    }

    pub enum Instruction {
        Noop,
    }

    pub struct Mast {
        pub instructions: Vec<Instruction>,
    }

    impl From<Instruction> for Mast {
        fn from(instruction: Instruction) -> Self {
            Mast {
                instructions: vec![instruction],
            }
        }
    }

    impl FromIterator<Mast> for Mast {
        fn from_iter<T: IntoIterator<Item = Mast>>(iter: T) -> Self {
            let instructions = iter.into_iter().fold(vec![], |mut instructions, mut mast| {
                instructions.append(&mut mast.instructions);
                instructions
            });

            Self { instructions }
        }
    }

    impl FromIterator<Ast> for Mast {
        fn from_iter<T: IntoIterator<Item = Ast>>(iter: T) -> Self {
            Self {
                instructions: iter
                    .into_iter()
                    .map(|ast| match ast {
                        Ast::Noop => vec![Instruction::Noop],

                        // this is probably a bug in the cache since indexed mast should be
                        // filtered out in the build routine
                        Ast::Call { .. } => vec![],

                        Ast::Node(node) => node.into_iter().collect::<Self>().instructions,
                    })
                    .map(Vec::into_iter)
                    .flatten()
                    .collect(),
            }
        }
    }

    pub struct Assembler {
        pub provider: ProcedureProvider,
        pub context: Arc<Mutex<HashMap<Index, IndexedAst>>>,
    }

    impl super::Assembler for Assembler {
        type Error = Error;
        type IndexedAst = IndexedAst;
        type Provider = ProcedureProvider;
        type Mast = Mast;

        fn append(&self, index: Index, ast: Ast) {
            self.provider.append(index, ast);
        }

        fn build(&self, ast: IndexedAst) -> Result<Mast, Error> {
            match ast {
                IndexedAst::Noop => Ok(Instruction::Noop.into()),

                // for simplicity, not supporting recursive calls
                IndexedAst::Call(index) => {
                    let ast = self
                        .context
                        .lock()
                        .unwrap()
                        .get(&index)
                        .cloned()
                        .ok_or(Error::ProcedureNotFound)?;

                    self.build(ast)
                }

                IndexedAst::Node(nodes) => Ok(nodes
                    .into_iter()
                    .map(|a| self.build(a))
                    .collect::<Result<_, _>>()?),
            }
        }
    }
}