Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

spec/bytecode.md #2

Open
vendethiel opened this issue Apr 13, 2017 · 6 comments
Open

spec/bytecode.md #2

vendethiel opened this issue Apr 13, 2017 · 6 comments

Comments

@vendethiel
Copy link
Member

vendethiel commented Apr 13, 2017

Instructions:

  • Push(valueType: int | str, value: this.type)
    Pushes a value onto the stack, with the type given by valueType.
{"type": "push", "valueType": "int", "value": 5}
{"type": "push", "valueType": "str", "value": "hey"}
  • Dup
    Duplicates the element at the top of the stack.
    Error: it is an error to use this instruction if the stack is empty.
{"type": "dup"}
  • Jump(mode: "stack" | "fixed", pos: usize)
    Jumps to a position.
    Right now, the VM doesn't have flags, so the stack mode will pop the stack and use the popped value as a boolean.
    Error: it is an error to do a stack-based jump if the stack is empty.
{"type": "jump", "mode": "stack", "pos":15}
{"type": "jump", "mode": "fixed", "pos":15}
  • Call(name: str)
    Generates a callframe and enters it. It is unspecified whether this is implemented recursively in the VM.
    The name must be fully-qualified. Each module JSON will contain offsets for functions.
    To allow for overloading, it is important that function names are mangled. See [mangling.md (TODO)](todo as i said).
    The std module is reserved for the VM's own functions.
    Functions with a void return type do not push anything to the stack – *if a function's result is discarded, it is the frontend's responsability to generate a pop.
    When entering a function, the stack is empty. It is up to the frontend to generate ArgumentLoad instructions when necessary.
    Note: arity isn't necessary for now, so it's not present. However, if/when optional arguments are implemented, it might be necessary. Another option would be to create a more complex call where you give a arguments array (splat-like).
    Error: It is an error to call a function if the stack's size is smaller than the function arity.
/* module/name/argument1;argument2;.../return */
{"type": "call", "name": "std.io/print_at_position/str;std.io.point/void"}
  • Return(returns: bool)
    Returns from the current callframe.
    If returns is true, pops the stack and pushes it in the parent's callframe.
    The rest of the stack is discarded.
    Error: it is an error to return with a return value if the stack is empty.
{"type": "return", "returns": false}
{"type": "return", "returns": true}
  • LocalLoad(name: str)
    Loads a local for the current subroutine and pushes it to the stack. Each subroutine has its own dictionary of locals, which starts off empty.
    Note: "locals" somewhat act like registers, but per-fn. They might turn unnecessary, but they're helpful for simpler compilation of local variables, and in the future, maybe for SSAF as well (?).
    Note: how to implement nested functions is currently an open question.
    Error: it is an error to load a unexisting local.
{"type": "local_load", "name": "a"}
  • LocalStore(name: str)
    Pops the stack and stores it in the current subroutine's locals dictionary at name.
    Error: it is an error to use this instruction when the stack is empty.
{"type": "local_store", "name": "a"}

Removed instructions, compared to smallstack:

  • carry {set|invert}: those only existed to demonstrate Jump, they're vastly unnecessary.
  • math: those can simply be Calls.
  • cmp: those can simply be Calls.

NOTE about Jump:

The VM doesn't (currently) have flags, like ZF/zero, CF/carry, SF/sign. If we want to implement x86-like jumps (see this). I'm not sure we want to do that, however. Bikeshedding welcome!

@hmaurer
Copy link

hmaurer commented Apr 18, 2017

Jump position is based on current bytecode file?

@vendethiel
Copy link
Member Author

Yes. Otherwise it's a call you want.

@vendethiel
Copy link
Member Author

Bikesheds, almost exactly 2 years later:

  • Store/Load should probably be use integers. Parameters should be the first N stores. I don't think variable names should be of any interest at all; plus in the future we'll probably want SSA.
  • Calls should probably take the function on the stack, that allows unifying all call types (a() vs a.b() vs a()() etc)
  • Function names should be in a global strings table

@vendethiel
Copy link
Member Author

I forgot:

  • Jump should take an absolute position in the current function (since there's a bytecode array per function).
    The backend will probably generate labels first.
    Will probably use the same kind of NameStage trick to type the Bytecode (and a type family to map U -> Jump(label: String) R -> Jump(offset: Int)? Need also to forbid Jumps in the code when in 'R. Oh and last but not least... Jumps don't have offsets.)

@vendethiel
Copy link
Member Author

* Jump should take an _absolute_ position _in the current function_ (since there's a bytecode array per function).

The WIP absolutely doesn't do this, it does JumpIfFalse in some sort of 1-indexed way:
JmpIfFalse 1; Print "a"; Print "b"; will print b. Basically the JumpIfFalse doesn't itself advance the IP.
It's maybe not the "best" way, but the current recursive impl. wants that. Other way could be with a State monad, or passing "currently generated instructions" (and length - 1 it).

  The backend will probably generate labels first.

Seems annoying: I need to make sure a label can't be a valid AST element later on (see below), and I need to ensure a label doesn't count in the bytecode pos.

  Will probably use the same kind of `NameStage` trick to type the Bytecode (and a type family to map `U -> Jump(label: String)` `R -> Jump(offset: Int)`? Need also to forbid `Jump`s in the code when in `'R`. Oh and last but not least... Jumps don't have offsets.)

...Sounds annoying...

@vendethiel
Copy link
Member Author

The above comment ^ is completely outdated, and now our VM isn't recursive anymore, and we also have a well-typed and well-behaved AST.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants