Chapter 11 Dynamic Memory: Arrays
11.1 Let’s Add Arrays
We are going to use Scala syntax, but we are not (yet) going to handle objects.
The array will behave more like a C array; the length will need to be remembered.
val arr = new Array[Int](4 + 5);
11.2 Syntax
<type> ::= <ident> | <type> '=>' <type> // '=>' is right associative
| '('[<type>[','<type>]*]')' '=>' <type>
<atom> ::= <number> | <bool> | '()'
| '('<simp>')'
| <ident>
<tight> ::= <atom>['('[<simp>[','<simp>]*]')']*['('<simp>')''=' <simp>]
| '{'<exp>'}'
<uatom> ::= [<op>]<tight> // Previously atom
<simp> ::= ... // same as before
| 'new' 'Array' '[' <type> ']' '('<simp>')'
<exp> ::= ... // same as before
<arg> ::= <ident>':'<type>
<prog> ::=
['def'<ident>'('[<arg>[','<arg>]*]')'[':' <type>] '=' <simp>';']*
<exp>
Scala array read syntax:
arr(1)
Wait a minute! Is this a function application?
Array write syntax:
arr(1) = 5
Here, we can notice one major difference which lets us know this is an array update…
The operations on arrays are primitive operations:
- “block-get”
- “block-set”
11.3 AST
case class Prim(op: String, args: List[Exp]) extends Exp
case class ArrayDec(size: Exp, tp: Type) extends Exp
11.4 Semantic Analysis
case class ArrayType(tp: Type) extends Type
How do we know if an array is well-formed?
If ‘tp’ is well-formed!
An array type ‘tp’ conforms to type ‘pt’ if:
- ‘pt’ is an array type, and
- inner type ‘tp’ conforms to ‘pt’ inner type.
An array type ‘tp’ conforms to a type ‘pt’ if all of the following hold:
- ‘pt’ is a function type with one argument
- the function argument’s type conforms to IntType
- the inner type of ‘tp’ conforms to the return type of ‘pt’
In other words, Array[T] conforms to Int => T!
11.5 Semantic Analysis
Env |- size: Int
-------------------------------------[ArrayDec]
Env |- ArrayDec(size, T): Array[T]
Env |- arr: Array[T] Env |- i: Int
---------------------------------------------[ArrayGet]
Env |- Prim("block-get", List(arr, i)): T
Env |- arr: Array[T] Env |- i: Int Env |- v: T
----------------------------------------------------[ArraySet]
Env |- Prim("block-set", List(arr, i, v)): Unit
11.6 Interpreter
abstract class Val
case class Cst(x: Any) extends Val
def eval(exp: Exp)(env: Env): Val = exp match {
case ArrayDec(size, _) =>
val Cst(s: Int) = eval(size)(env) // Why is this safe?
Cst(new Array[Any](s))
case Prim("block-get", args) => ??? // left as an exercise for the reader
case Prim("block-set", args) => ??? // left as an exercise for the reader
}
11.7 Compiler
Where do we want to store our arrays?
We will use the heap. The heap is permanent, i.e., not erased once a function call is over (unlike the stack and local variables).
Therefore the heap is used as persistent storage.
At (compiled) program launch, the OS maps a memory space for our stack. Thus, we can mov $4 -8(%rsp)
.
To have access to the heap, we call malloc in bootstrap.c and give the pointer to our main function as the first argument
Where is this pointer going to be saved?
A global variable: heap. This address represents the first memory address that we are allowed to use.
So, how do we create an array (ArrayDec)?
Subsequent array creations must not overlap!
We assume %rax contains the address of the array we want to access.
How to write to a memory location:
movq $1 (%rax) // write one in the first element of the array
How to read from a memory location?
movq (%rax), %rax // read the first element of the array
// and store it in %rax
Shortcuts for arrays:
movq %rip(heap), %rax
movq $3, %rcx
movq (%rax, %rcx, 8), %rax // read the 3rd (stored in %rcx)
// element of the array and store
// it in %rax
11.8 Where Are We?
Today, we learned the following:
- Adding arrays
- Heap allocation