design_docs/logo.png

http://www.bardolph.org

Arrays Design

Overview

Support for arrays is accomplished with some new instructions and new handling of certain types of parameters passed into to stack-related instructions.

An Array class contains a Python List object that holds the data. The class also keeps the declared size of the array.

The ArrayCursor class is used to navigate arrays. It contains a reference to the underlying Array object, as well as an index value that designates a specific element within the Array.

A specialized version of ArrayCursor is used to create arrays, as opposed to navigating them.

New VM Instructions

OpCode.OP, Operator.SET

This is a new binary operation for the vm_math module. It does the following:

  1. Pop the rvalue from the top of the stack.

  2. Pop the lvalue from the top of the stack.

  3. Assign the rvalue to the lvalue.

(Consider pushing the lvalue back onto the stack.)

This code sequence does not leave anything on top of the stack. It replaces the previous implementation of the assign command. The implementation of the SET operation will need to handle array cursors differently than simple variables.

Array-Centric Op-Codes

OpCode.ARRAY: Pop the name off the stack and create an array with that name. Push that array object back onto the stack.

OpCode.DEREF: Pop the name of the array off the top of the stack. Create an array cursor using that name and push it onto the stack.

OpCode.INDEX: Pop the index value off of the stack, and then pop the array object off of the stack. If the popped array object is a cursor, apply the index to the cursor and push the resulting array cursor back onto the stack. If the popped object is an array and not a cursor, add a dimension to the array with a length equal to the index value, and push the object back onto the stack.

When the parser reaches the end of the square-bracket pairs, it adds an instruction to pop the stack to clear it of the array under construction.

For example, this script:

array a(10)

can be accomplished with:

OpCode.PUSHQ, "a"
OpCode.ARRAY
OpCode.PUSHQ, 10
OpCode.INDEX
OpCode.POP

In this case, OpCode.INDEX pops the array off the stack, pops 5 off the stack, and adds the dimension to the array, with 5 slots. The final pop instruction leaves the stack in its previous state.

Then, to reference the array, such as a(5):

OpCode.PUSHQ, "a"
OpCode.DEREF
OpCode.PUSHQ, 5
OpCode.INDEX

After this code has been executed, the array cursor will occupy the top of the stack, with the index value of 5.

If it is used as an lvalue, that cursor stores the incoming value in the underlying array, at position 5. If it is used as an rvalue, it provides the value stored in the underlying array, also at position 5.

Therefore, this:

hue a(5)

would produce something like:

OpCode.PUSHQ, "a"
OpCode.DEREF
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.POP, Register.HUE

Note that the stack returns to the same condition it was in prior to this code being executed.

Conversely, assignment to the array, such as:

assign a(5) 10

can be done with:

OpCode.PUSHQ, "a"
OpCode.DEREF
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.PUSHQ, 10
OpCode.OP, Operator.SET

In response to the SET command, the VM pops the array cursor, pops the name of the destination variable (“a”), and assigns the value from the cursor to the variable. The stack will not have anything added to it.

Compare this to the code associated with a scalar:

assign b 20

which might produce:

OpCode.PUSHQ, "b"
OpCode.PUSHQ, 20
OpCode.OP, Operator.SET

In both cases (scalar or array), the SET operation leaves the stack in its previous state.

Multi-Dimensional Arrays

Two kinds of array cursors handle OpCode.INDEX. A cursor used for creation responds to indexing by adding another dimension to the array. For example, to have v(10)(5):

array v(10)(5)

this can be done with:

OpCode.PUSHQ, "v"
OpCode.ARRAY
OpCode.PUSHQ, 10
OpCode.INDEX
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.POP

Note that the first OpCode.INDEX creates the first dimension, creating the equivalent of v(10). The second OpCode.INDEX creates the second dimension. In the underlying array object, each of the first 10 elements is populated with a 5-element sub-array, which amounts to v(10)(5), for a total of 50 slots.

In this context, every INDEX instruction leaves the array object on the stack. No cursors are created here. When construction of the array is complete, the POP at the end clears it off the stack.

Assignment uses an array cursor that acts as a gateway to the underlying array. For example:

assign x v(2)(3)

can be done with:

OpCode.PUSHQ, "x"

OpCode.PUSHQ, "v"
OpCode.DEREF
OpCode.PUSHQ, 2
OpCode.INDEX
OpCode.PUSHQ, 3
OpCode.INDEX

OpCode.SET

Conversely, to assign in the opposite direction:

assign x v(4)(1)

can be done with:

OpCode.PUSHQ, "v"
OpCode.PUSHQ, 4
OpCode.INDEX
OpCode.PUSHQ, 1
OpCode.INDEX

OpCode.PUSHQ, "x"
OpCode.OP, Operator.SET

Partially-Dereferenced Arrays

Only one cursor is needed when iterating over a one-dimensional array. Arrays of more than one dimension require one cursor for each dimension. This is true during creation and access.

Returning to example:

array v (5)(10)

assign x v(3)
assign y x(7)

the cursors work as follows:

# array v (5)(10)
#
OpCode.PUSHQ, "v"
OpCode.ARRAY
OpCode.PUSHQ, 2
OpCode.INDEX
OpCode.PUSHQ, 3
OpCode.INDEX
OpCode.POP

# assign x v(3)
#
OpCode.PUSHQ, "x"
OpCode.PUSHQ, "v"
OpCode.DEREF
OpCode.PUSHQ, 3
OpCode.INDEX
OpCode.OP, Operator.SET

# assign y x(7)
#
OpCode.PUSHQ, "y"
OpCode.PUSHQ, "x"
OpCode.DEREF
OpCode.PUSHQ, 7
OpCode.INDEX
OpCode.OP, Operator.SET

Array as Parameter

The key concept here is that the incoming parameter is a cursor, and there is no DEREF instruction inside the routine.

Script:

define fn with v() begin
    assign v(7) 9
    return v(5)
end

array arr(10)
assign arr(5) 250

hue (fn arr)

VM code:

# define fn with v() begin
#
OpCode.ROUTINE, "fn"

# assign v(7) 9
#
OpCode.PUSHQ, "v"
OpCode.PUSHQ, 7
OpCode.INDEX
OpCode.PUSHQ, 9
OpCode.OP, Operator.SET

# return v(5)
# end
#
OpCode.PUSHQ, "v"
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.RETURN               # Functions leave the return value on the stack.

# array arr(10)
#
OpCode.PUSHQ, "arr"
OpCode.ARRAY
OpCode.PUSHQ, 10
OpCode.INDEX
OpCode.POP

# assign arr(5) 250
#
OpCode.PUSHQ, "arr"
OpCode.DEREF
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.PUSHQ, 250
OpCode.OP, Operator.SET

# hue (fn arr)
#
OpCode.CTX
OpCode.PUSHQ, "arr"
OpCode.DEREF
OpCode.POP, Register.RESULT            # Register.RESULT now holds a cursor.
OpCode.PARAM, "v", Register.RESULT     # Pass that cursor as parameter v.
OpCode.JSR, "fn"
OpCode.END_CTX

OpCode.POP, Register.RESULT
OpCode.MOVE, Register.RESULT, Register.HUE

Partially-Dereferenced Array as a Parameter

As with the previous use case, the incoming parameter is a cursor, and there is no DEREF instruction inside the routine.

Script:

define fn with v() begin
    assign v(6) 7
    return v(5)
end

array arr(10)(20)
assign arr(3)(5) 100

hue (fn arr(3))

VM code:

# define fn with v() begin
#
OpCode.ROUTINE, "fn"

# assign v(6) 7
#
OpCode.PUSHQ, "v"
OpCode.PUSHQ, 6
OpCode.INDEX
OpCode.PUSHQ, 7
OpCode.OP, Operator.SET

# return v(5)
# end
#
OpCode.PUSHQ, "v"
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.RETURN

# array arr(10)(20)
#
OpCode.PUSHQ, "arr"
OpCode.ARRAY
OpCode.PUSHQ, 10
OpCode.INDEX
OpCode.PUSHQ, 20
OpCode.INDEX
OpCode.POP

# assign arr(3)(5) 100
#
OpCode.PUSHQ, "arr"
OpCode.DEREF
OpCode.PUSHQ, 3
OpCode.INDEX
OpCode.PUSHQ, 5
OpCode.INDEX
OpCode.PUSHQ, 100
OpCode.OP, Operator.SET

# hue (fn arr(3))
#
OpCode.CTX
OpCode.PUSHQ, "arr"
OpCode.DEREF
OpCode.PUSHQ, 3
OpCode.INDEX
OpCode.POP, Register.RESULT                 # Cursor associated with arr(3).
OpCode.PARAM, "v", Register.RESULT
OpCode.JSR, "fn"
OpCode.END_CTX

OpCode.POP, Register.RESULT
OpCode.MOVE, Register.RESULT, Register.HUE

Loop over 1-D Array

This kind of loop resembles a standard counted loop.

array v(10)
repeat with i from 0 to 9
    hue v(i)

Note that the above code is functionally equivalent to:

array v(10)
repeat in v as i
    hue v(i)

Therefore the parser, generates code similar to that of a counting loop. Because the size of the array is calculated at run-time, the limit for the loop must also be determined dynamically. The new Operand.SIZE designates this.

For example, to retrieve the size of array v and leave it on top of the stack:

OpCode.PUSHQ, "v"
OpCode.OP, Operator.SIZE

To integrate this into loop code:

# Enter the loop.
OpCode.LOOP

# Initialize the counter
#
OpCode.PUSHQ, "v"
OpCode.Op, Operator.SIZE
OpCode.POP, LoopVar.COUNTER

# This is where the JUMP code points. Check that the number of remaining
# iterations > 0.
#
OpCode.PUSH, LoopVar.COUNTER
OpCode.PUSHQ, 0
OpCode.OP, Operator.GT
OpCode.JUMP, JumpCondition.IF_FALSE, 11

# (Code inside the loop goes here.)

# Decrement the counter.
#
OpCode.PUSH, LoopVar.COUNTER
OpCode.PUSHQ, 1
OpCode.OP, Operator.SUB
OpCode.POP, LoopVar.COUNTER

# Jump to the next potential iteration, where the counter is compared to 0.
#
OpCode.JUMP, JumpCondition.ALWAYS, -5

# Exit the loop.
#
OpCode.END_LOOP

Interpolation works the same as with counted loops as well:

array v(10)
repeat in v as i with x from 10 to 100
    hue v(i) + x

Loop over 2-D Array

Script:

array m(5)(10)

repeat in m as i
    repeat in m(i) as j
        assign m(i)(j) 0

repeat in m as i
    repeat in m(i) as j
        hue m(i)(j)