quickscript

Intro

This post will just serve as me rambling about a project I'm working on, aka, trying to plan it and setting stuff up for when I actually implement it so I can reason through it before I realize I fucked up about 5 hours into writing an interpreter.

I want to start with some base ideas that I'm going to try to keep in mind when designing the internal structure of the language's interpreter.

Link to the interpreter source code: github.com/juliewoolie/quickscript

All data exists on the stack.

That tagline is a bit hyperbolic. I've since discovered that there are some things where its easier for me to pass by reference (arrays, strings, structs) so this mantra exists as a general guideline now.

No memory interaction

You should never be able to interact with raw pointers, random memory or anything like C allows you to. It's a scripting language, not C 2.0.

Type safety and basically compiled

quickscript is a statically typed language and my hope is a type system will allow me to make the most out of what I'm doing. Static typing means that the compiler basically knows where everything will be, how big it will be and how it'll be used.

No garbage collector

Memory handling should be done as it executes, the hope is that with a simple stack-memory-based language data will be freed as scopes are exited and so there's no requirement for automatic garbage collection.

Single threaded

I'm not managing that shit, at least not right now. This is called quickscript because it's intended to be a quickly (ish) made scripting language.

Syntax

I'm not defining the grammar, so here's an example of the source code:

1
2
3
4

int32 main(string[] args) {
  println("Hello, world!")
  return 0
}

Internals

Strings / Arrays

Arrays and Strings are largely handled the same as they are in effect, the same, an array of some data type.

quickscript Strings are UTF-8 encoded arrays of single byte characters.

quickscript Arrays are length-prefixed. Meaning the data of an array consists of 4 bytes to determine the length of the array, with the rest of the bits consisting of the array's data. Arrays, despite the first point in the above section, are heap allocated.

Array data is allocated and freed as required by an internal memory allocator, scripts only ever interact with a pointer to said data. That being said, every other rule still applies in regard to how and when arrays are allocated and freed.

Where arrays and strings differ is that Strings are readonly and cannot be modified with anything other than methods that cause new strings to be allocated.

Concatenating, or swapping out characters in a string causes a new duplicate string to be allocated.

Lookups and stack vs heap usage

While almost all user generated code and the data from it will exist on the stack, there are objects or arrays (strings) that must by necessity exist on the heap.

For example, native functions cannot exist in the same space as user-written functions or variables. So a difference must be established for how local functions and native functions are compiled and interpreted.

Pass by value vs by reference

quickscript will follow Java's lead when it comes to how data is passed. Primitive values such as numbers, booleans and characters is passed by value. But structs, strings, arrays and potentially functions will be passed by pointer reference.

While functions can't be assigned to variables or currently passed to functions as an argument, they do still somehow need to be referenced.

Interpreter

quickscript's internal compiler will compile source files into an internal bytecode that is then executed by the interpreter, that bytecode will be referred to as the IR.

The process of that compilation I will uhh, one day figure out :3 I just wanna figure out how the interpreter itself will function.

The IR data produced by the compiler will be split into multiple parts:

Const String Pool

A buffer of utf-8 strings. The strings here are all the identifiers used for function and potentially variable names as well as all the string literals defined in the code itself. As mentioned before, these are length-prefixed UTF-8 strings.

Function data array

Each function's instructions are defined within this array, so it's a large buffer of OP Codes and instructions.

Data layout of instructions

an Instruction is an opcode and all of its arguments. Each instruction is made up of a 16-bit opcode followed by 72 bits of arguments. Each instruction is fixed length.

Function invocation

To invoke a function in quickscript, it's function pointer must be called with the INVOKE instruction.

Further, the interpreter stores all function arguments in an array along with the return value.

IR OP Codes

A lot of the following opcodes will refer to some arguments as "registers." This means the argument is an unsigned 8bit integer index for one of the interpreter's registers.

Any operation listed here which is based on a certain memory size (suffixed with 8, 16, 32 and 64) is also used for pointer types and floating point types, as for those the numeric type doesn't really matter, they're still just numeric values stored in bits.

OP Codes are generally divided into multiple categories: general, unary, conversion and binary. The following sections specify what OP Codes exist and what they do.

General purpose OP Codes

NOP

A no-operation operation that does nothing. This isn't intended to be used or even appear in the outputted IR, but exists as a placeholder for an opcode with a 0 value.

PUSHLINE

Pushes a line number to the interpreters tracker telling it what line of the source it is currently executing, used for when stuff goes wrong or for inspecting the IR and easily comparing it with the source code.

RET

Each function's data is suffxed with this instruction regardless of if a return statement was actually added in the source. It tells the interpreter when to return to the caller up the call the stack.

If there is no call frame to return to after a RET instruction, the program has reached the end of execution and should exit.

JMP, JMPI0 and JMPN0

Are all jump instructions. The first one simply jumps to a different instruction. The other two are conditional jumps. JMPI0 means jump if zero and JMPN0 means jump if not zero.

All instructions take a 32bit unsigned integer as their first argument, which is the next instruction to jump to. The 2nd and 3rd instructions take in a 2nd argument as well: the register value to evaluate is inside.

LOADCONST (has byte-dependent codes)

These are all instructions which take as arguments a register to store a constant value inside and a 2nd argument which is the constant value itself.

MOV

Copy the value in the first register argument into the second register argument.

Stack Memory OP Codes

Stack read and write operations come in two different flavors: Relative and Global. Global reads and writes read from the global scope of the current script file, while relative instructions read from the stack relative to the current function's scope.

STACKALLOC

Allocates room in the stack for the current function to use. The idea, hopefully is that in most cases you can predict how much space a specific function will use on the stack and from that you can allocate all that space at the beginning of a function's execution.

The amount of room to allocate is specified as an unsigned 64-bit integer argument in the instruction

STACKFREE

The counterpart to STACKALLOC, this one retracts the stack pointer, thus freeing all the memory acquired at the start of a function's execution.

The amount of room to allocate is specified as an unsigned 64-bit integer argument in the instruction

SREAD (has byte-dependent codes)

Relative stack read of a corresponding bit-size from the stack memory. Takes in two arguments:

• The register to store the read value.
• The memory offset to read from. Offsets relative to stack address at the start of the function execution.

SWRITE (has byte-dependent codes)

Relative stack write of a corresponding bit-size to the stack memory. Takes in two arguments:

• The register to read the value from.
• The memory offset to write to.

GREAD (has byte-dependent codes)

Global read of a corresponding bit-size from the stack memory. Takes in two arguments:

• The register to store the read value.
• The memory offset to read from. Offsets relative to stack address in the global scope

GWRITE (has byte-dependent codes)

Global write of a corresponding bit-size to the stack memory. Takes in two arguments:

• The register to read the value from.
• The memory offset to write to.

Heap Memory OP Codes

READOBJ (has byte-dependent codes)

These are all instructions for reading from an object (struct or array or string) The instruction takes in three arguments.

• Register containing the "object" to read from (a pointer)
• Register to store the output of the read value.
• The byte offset of the object's data to read from (uint32)

WRITEOBJ (has byte-dependent codes)

These are all instructions for writing to an object. The instruction takes in three arguments.

• Register containing the "object" to write to.
• Register to read the value from.
• The byte offset of the object's data to write to (uint32)

READIDX (has byte-dependent codes)

These are all instructions for reading from an array or string (struct or array or string) The instruction takes in three arguments.

• Register containing the "object" to read from (a pointer)
• Register to store the output of the read value.
• Register containing the index to read from

WRITEIDX (has byte-dependent codes)

These are all instructions for writing to an array or string. The instruction takes in three arguments.

• Register containing the "object" to write to.
• Register to read the value from.
• Register containing the index to write to

(Note: Strings should never be written to)

HEAPALLOC

Allocate an object on the heap. This should only be used for allocating space for objects, arrays and strings. Takes in the following arguments:

• Register to store the pointer address of the allocated memory in.
• Unsigned 64bit integer indicating how many bytes to allocate.

HEAPFREE

Free an object allocated on the heap. This must only ever be called at the end of the scope that initially allocated the object. That is except when the allocated object is a return value or is part of a returned value.

For example, a struct allocated and then returned should not be freed when the function returns. And a struct allocated and then used as the value in a different struct or array should also not be freed when returned.

Arguments:

• Register the pointer to the object is stored in.

Function Call Instructions

PUSHARG (has byte-dependent codes)

Push a value in a register into the interpreter's function arguments array.

Arguments:

• The register containing the value to push.

SETRV

Set the return value. Arguments:

• Register the return value is in.

INVOKE

Two instructions for invoking functions, the 2nd one is used for invoking functions with a void return type.

Arguments:

• The register containing the function pointer
• The register to store the returned value in (ignored when using the void invoke.)

Conversion Instructions

These are instructions that convert from one number type to another.

• I8TU8
• I8TI16
• I8TU16
• I8TI32
• I8TU32
• I8TI64
• I8TU64
• I8TF32
• I8TF64
• U8TI8
• U8TI16
• U8TU16
• U8TI32
• U8TU32
• U8TI64
• U8TU64
• U8TF32
• U8TF64
• I16TI8
• I16TU8
• I16TU16
• I16TI32
• I16TU32
• I16TI64
• I16TU64
• I16TF32
• I16TF64
• U16TI8
• U16TU8
• U16TI16
• U16TI32
• U16TU32
• U16TI64
• U16TU64
• U16TF32
• U16TF64
• I32TI8
• I32TU8
• I32TI16
• I32TU16
• I32TU32
• I32TI64
• I32TU64
• I32TF32
• I32TF64
• U32TI8
• U32TU8
• U32TI16
• U32TU16
• U32TI32
• U32TI64
• U32TU64
• U32TF32
• U32TF64
• I64TI8
• I64TU8
• I64TI16
• I64TU16
• I64TI32
• I64TU32
• I64TU64
• I64TF32
• I64TF64
• U64TI8
• U64TU8
• U64TI16
• U64TU16
• U64TI32
• U64TU32
• U64TI64
• U64TF32
• U64TF64
• F32TI8
• F32TU8
• F32TI16
• F32TU16
• F32TI32
• F32TU32
• F32TI64
• F32TU64
• F32TF64
• F64TI8
• F64TU8
• F64TI16
• F64TU16
• F64TI32
• F64TU32
• F64TI64
• F64TU64
• F64TF32

Unary instructions

These instructions take in 2 arguments, an input and an output register. Each instruction then performs some operation and places the result in the output register.

BNEGATE

Bitwise negate operation

LNEGATE

Logical negate operation

NEG (has number type dependent operations)

Numeric sign flip operation.

Note that for operations like NEGU8 (Unsigned 8 bit negative op code) the result becomes a signed 8 bit integer.

INC (has number type dependent operations)

Increment a number by 1

DEC (has number type dependent operations)

Decrement a number by 1

Binary Operations

Binary instructions take in 3 arguments, a left-hand-side register argument, a right-hand-side register argument and an output register argument. The instruction then performs an operation on the arguments and places the result in the return register.

I'm not listing all the opcodes in this section as there's many variations of each one. But I will list the types of opcodes.

In the following sections, some instructions are marked as bitwise operations and some as bitwise. The difference is in how the bits are handled. Logical operations are intended for boolean operations, so they function slightly differently. For example, the bitwise OR operation combines the bits in two integers, where as the boolean OR operation outputs a 1 or 0 depending on the value of both operands.

Given the sheer number of binary operations that exist, it would be advisable to use some kind of script to auto generate the C code for each one rather than trying to write that shit by hand.

Integer-only Binary Operations

These are instructions that are only supported for the integer types, signed and unsigned, and mostly includes bitwise operations

• LSHIFT: Left Shift
• RSHIFT: Right Shift
• URSHIFT: Unsigned right shift
• BAND: Bitwise AND operation (&)
• BOR: Bitwise OR operation (|)
• BXOR: Bitwise XOR operation (^)

Boolean-only Binary Operations

Some overlap in this category with the previous, but these operations function slightly differently.

• LAND: Logical AND operation (&&)
• LOR: Logical OR operation (||)
• LXOR: Logical XOR operation (^)

Note: The use of LXOR or BXOR has to be decided by the compiler depending on the type of the operands involved. This is because they use the same operator (^) in the source code.

General Number Binary Operations

This category encompasses mostly mathematical operations for each number type supported by quickscript.

ADD

These operations add two numbers.

SUB

These operations subtract the right argument from the left.

MUL

These operations multiply the left argument with the right.

DIV

These operations divide the left argument by the right.

MOD

Modulo instruction.

POW

These operations raise the left argument to the power of the right

Comparison Operations

These are operations that in some way compare the left and right operands

EQ

Equals operator, compares the byte values

EQARR

Equals operator for arrays

EQSTRUCT

Equals operator for structs

NEQ

Not-Equals operator, compares the byte values

NEQARR

Not-Equals operator for arrays

NEQSTRUCT

Not-Equals operator for structs

GT

Greater-Than operator

GTARR

Greater-Than operator, for arrays

GTE (has number-type-depdendent codes)

Greater-Than-or-Equal-to operator

GTEARR

Greater-Than-or-Equal-to operator, for arrays

LT (has number-type-depdendent codes)

Less-Than operator

LTARR

Less-Than operator, for arrays

LTE (has number-type-depdendent codes)

Less-Than-or-Equal-to operator

LTEARR

Less-Than-or-Equal-to operator, for arrays

String/Array Operations

Special binary operation cases carved out for string and array operations.

STRCONCAT

Concatenate two strings

STRREP

String repeat

Standard Library

This section will just describe all the functions and constants I can think of that should be part of the standard library.

Constants

PI

3.1415, you know, pi

E

Euler's number

LN10

Natural logarithm of 10

LN2

Natural logarithm of 2

LOG10E

Base-10 logarithm of E

LOG2E

Base-2 logarithm of E

SQRT1_2

Square root of 1 / 2

SQRT2

square root of 2

Functions

Some functions are defined multiple types for several number types, in those cases the following placeholders will be used:

float

float32 and float64

num

All numeric types

int

Any integer types

I will also omit descriptions from some functions because of how common they are that you can look up the same function in basically any other language and find its definition.

General functions

void printf(string format, args...);

Prints to the standard output, effectively identical to C's printf, except for the ability of quickscript to automatically discern what the argument types are.

println(string format, args...)

Same as printf, but appends a new line character to the end of the print string.

string sformat(string format, args...);

Formats a string in the same way as printf.

Time and date functions

currentTimeMillis()

Returns the current UNIX timestamp.

Math functions

float sqrt(float x);

Square root function

float cbrt(float x);

Cube root function

num abs(num x);

float acos(float x);

float acosh(float x);

float asin(float x);

float asinh(float x);

float atan(float x);

float atan2(float x, float y);

float atanh(float x);

float ceil(float x);

int clz(int x);

float cos(float x);

float cosh(float x);

float hypot(float... values);

float log(float x);

float log10(float x);

float log1p(float x);

float log2(float x);

num max(num... values);

num min(num... values);

float round(float x);

float round(float x, uint32 precision);

int8 sign(num x);

float sin(float x);

float sinh(float x);

float tan(float x);

Structs

Structure of the Bytecode file

This section details the structure of the bytecode file and bytecode data output by the compiler.

Header

This is a set of uint64 pairs. Each one specifies the starting point of one of the following sections of the file and the section's length in bytes.

Const String Pool

An array of QS Strings (32bit length prefix followed by UTF-8 encoded character data) that make up identifiers, string literals, function names and type names.

Type Table

An array of Type declarations that were declared in the source file. Each entry is preceded by a 32bit unsigned integer, the index of the type, and by an 8bit unsigned integer, the type of the entry. The following types are supported:

ARRAY (0x0)

Array type, the following 32bits after the type byte is the index of the component type in the table.

STRUCT (0x1)

Structure type, the layout of this type's data are specified further down.

NSTRUCT (0x2)

Native Struct, indicates a struct that has been declared by the compiler itself and as such is only referenced by the script, not declared.

FUNCSIGN (0x3)

Function signature type, data layout specified further down

Reserved type indexes

Struct Types

Name offset (uint64)

The offset of the name of the struct in the const string pool.

Constructor location (uint32)

Index of the constructor function of the struct in the function table.

Property Count (uint32)

The number of properties this struct has

Property Array (propertydecl[])

An array of the following values:

Name offset (uint64)

Same as the struct's name offset, address of the name inside the const string pool

Offset (uint32)

Offset of the property's data in memory from the start of the struct's memory

Type Index (uint32)

The type index of the property's type

Function Signatures

Return Type (typeindex)

Return type's type index

Argument Count (uint32)

Number of arguments the signature has

Varargs (bool)

A 1 or 0 byte to indicate if the last argument is a variadic argument.

Arguments (typeindex[])

Array of type indexes, each one indicating the corresponding argument's type.

Function Table

An array of functions, their names and their starting offsets. Each entry in this array uses the following values:

Name Offset

Offset of the function name in the string const pool.

Note that for constructors, the function name will be something like StructName.<init>

Start

The offset of where the function starts in memory

Signature (typeindex)

Index of the function signature type in the type table.

When script execution begins, this table is searched through for a "main" function to use as an entry point. If none is found, script doesn't run.

Foreign Function Table

An array of references to native or "foreign" functions.

Name Offset (uint64)

Offset of the function name in the string const pool.

Signature (typeindex)

Index of the function signature type in the type table.

Instruction Array

An array of uninterrupted IR Instructions.

OP Code table