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