How to implement a call stack in JavaScript?

Question

A call stack is composed of stack frames (also called activation records or activation frames).

Let's say I have code (a custom language) which is compiled into an AST (in JavaScript). The language example looks like this:

fun a(z):
  let x = 10
  let y = z * x
  let w = b(y, x)
  return w
fun b(a, b):
  let x = c(a, 10)
  let y = c(b, 20)
  let z = d(x, y)
  return z
fun c(a, b):
  let x = a + 5
  let y = b + 7
  let z = d(x, y)
  return z
fun d(a, b):
  return a * b
main:
  a(argv[0])

Without cheating and saying something about how this can be compiled away statically or something, say you just create an interpreter for this.

How would you go about creating the call stack? What would each activation record look like in particular? (In JS implementation).

Assuming we have a simple AST that you can imagine from the source code:

{
  type: 'fun',
  name: 'a',
  params: ['z'],
  steps: [
    {
      type: 'let',
      name: 'z',
      value: {
        type: 'call',
        name: 'd',
        params: ['x', 'y']
      }
    },
    ...
  ]
}

Then you are going to interpret that AST:

let pointer = 'main'
let callstack = []
let stack = [funs[pointer]]
while (stack.length) {
  let current = stack.shift()
  current.steps.forEach(step => {
    if (step.type == 'call') {
      // PUSH ACTIVATION RECORD SOMEHOW
      step.params.forEach(param => {
        callstack.push(param) // how to reach value from reference?
      })
      stack.push(step)
    }
  })
}

I get completely lost. What would that interpretation function look like?

If I were writing an AST-walking interpreter, I very likely wouldn't implement a call stack, but simply use the stack of the host language. I feel like most scenarios where implementing your own stack makes sense would also require a flat IR (i.e. some form of bytecode, not trees). Beyond that, how you represent the stack depends on the requirements of your language. For example if you have the full power of pointers, you'll probably want a byte array to represent your memory and the stack to just be a part of that. — sepp2k
– sepp2k, Commented Aug 25, 2020 at 13:12
@sepp2k The language implementing the call-stack is JavaScript. Imagine instead of the AST we compile it to 3-address code, then what? — Lance Pollard
– Lance Pollard, Commented Aug 25, 2020 at 14:53
"The language implementing the call-stack is JavaScript" When I said "the requirements of your language", I meant the language that you're implementing, not the host language. Like if you're writing an interpreter for a language that has pointers, you'll want the byte array for memory, so you can implement pointers as indices into that array. "Imagine instead of the AST we compile it to 3-address code, then what?" Then you can implement a call by pushing a new stack frame that contains the index of the current instruction +1 as the return address and implement return as pc = stack.pop().ret; — sepp2k
– sepp2k, Commented Aug 25, 2020 at 15:20
"Then you can implement..." I know what to do, I just don't know how to do it exactly! — Lance Pollard
– Lance Pollard, Commented Aug 25, 2020 at 15:44

intel_chris · Accepted Answer · 2020-08-25 20:59:16Z

Ok, first, let's construct the right AST for your example. Getting the details right are very important in this case. It should look something more like this, and this is far from a perfect AST.

{ type: compilation_unit // this is an object that is an array of functions
  [ 
    { type: fun // this is what you will push on your 'call stack'
      name: 'a'
      params: ['z']
      locals: ['x', 'y', 'w']
      steps: [
        { type: let
          name: 'x'
          value: { type: const
                   value: 10
                 }
         },
         { type: let
           name: 'y'
           value: { type: '*'
                    left: { type: var
                            name: 'z'
                          }
                     right: { type: var
                              name: 'x'
                             }
                   }
           }
    ...
    }
    { type: fun
      name: 'b'
      ...
    }
    ...
    { type: fun
      name: 'main'
      params ...
      locals ...
      steps: [
        { type: call
          name: 'a'
          args: [ 
             { type: '[]'
               name: 'argv'
               subscript: {
                  { type: const
                    value: 0
                  }
             }
           ]
        }
      ]
    } // type fun
  ]
}

So, if you are using your AST as your IR, then when you reach a call "node", what you push on the stack is [a pointer to] the AST for the function you are calling. That's the information you need. The params, the local variables and the steps you need to execute are all there. Your byte code interpreter (in this case an AST walking interpreter) simply needs to look at the type: fun object and see how many params there are, how many locals, etc. and allocate space for them.

But, that is probably not what you want. You talk about 3 address code and that generally means a lower level IR. For that, you need a phase that converts your AST down into that lower level representation. You need to make a pass over your AST to generate a "lower level" IR.

I personally would recommend something like LLVM IR, but that is going to require you to do some study. But to see what a stack frame like that looks like, find a C compiler (or some other compiler that is close(r) to the language you want) that generates LLVM IR and see what it generates both for call instructions and for stack frames. You then turn that type: fun AST object into that sequence of instructions.

Collectives™ on Stack Overflow

How to implement a call stack in JavaScript?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related