Random-access machines and pointers

Random-access machines

Introduction

Similar to counter machine but:

+ Allows indirect reference of registers. Where \(r\) previously would have referred to the register itself, (eg \(INC(r)\), we can now refer to the value of a pointer using \([r]\). This allows us to write eg \([3]\rightarrow 4\) which means put the value of register \(3\) into register \(4\).

Increments can be rewritten

INC(r) to \([r]+1\rightarrow r\) DEC(r) to \([r]-1\rightarrow r\)

Also for the changes to the instruction register

normally is \([IR]+1\rightarrow IR\) with jump is before JZ(r,z). now if \([r]=0\) then \(z\rightarrow IR\). if \([r]!=0\) then \([IR]+1\rightarrow IR\)

The register machine introduces additional operations, taking advantage of indirect operations.

Pointers

Sort

pointers? addresses? as variables? in stack?

Pointers

So in first case we have \(x=2\) and \(y=2\), and then we want to change both to \(3\).

In first example, initiate both and store \(2\) in memory twice. update both.

In second example we can have x and y have the same value of a pointer, pointing to a third memory location. we can the update this memory location to change both to \(3\).

Two variable can be the same by value, but additionally by pointer.

eg \(x=2\) and \(y=2\). \(x==y\), but if they have the same pointer, they are the same thing. changing one changes the other.

We can update \(x\) and \(y\) will automatically update

When we say \(x=2\), \(y=x\) we are either making \(y\) mutable or immutable. mutable means same pointer. language specific rules apply.