Repl, bytecode design, mutually recursive functions

I am working on a simple Lisp -> Bytecode compiler in Rust. I am running into a design issue with bytecode design.

Consider the problem of mutually recursive functions f & g.

f compiles to Vec<Instr>
g compiles to Vec<Instr>

One 'solution' would be double indirection. We have a code: Vec<Rc[Instr]> so what happens is that for f to call g, it looks up code[g_idx] (one indirection to address the Vec, a second to follow the Rc) and runs the code.

A second approach is to hard code the corresponding Rc[Instr] of f/g into each other (avoiding the Vec lookup). But this creates circular references. In AOT systems this would not matter, but with REPL support, I'd prefer unused + unaccessible (due to shadowing) funcs to be dropped over time.

Question: I'm sure others have run into the mutual recursive bytecode problem. What are the typical strategies used to solve this problem ?

I think I have pretty much the identical problem in my SQL implementation, which has Vec<Instruction>.

My functions are represented like this:

pub struct Function {
    pub param_count: usize,
    pub return_type: DataType,
    pub local_typ: Vec<DataType>,
    pub source: Rc<String>,
    pub ilist: RefCell<Vec<Instruction>>,
    pub compiled: Cell<bool>,
}

One of the variants of my Instruction enum is

Call(Rc<Function>),

I have Drop implemented on the database to make sure everything gets freed, it looks like this:

impl Drop for Database
{
  /// Clear function instructions to avoid leaking memory.
  fn drop(&mut self)
  {
    for function in self.functions.borrow().values()
    {
      function.ilist.borrow_mut().clear();
    }
  }
}
1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.