This chapter describes how a Mica program holds its data: values and the copies an assignment and a call make, the cells a program makes on the heap and the one owner each of them has, borrowed pointers that read a cell another name owns, the kinds of memory a program uses, the two memory classes a build chooses between, and what the checked tier stops at run time. Each construct names its rule in the grammar, says what it means, and quotes what the compiler answers when a source breaks the rule. Value and pointer, heap, end to end, ownership and borrowing and memory classes teach the same ground from the start.
Every example is a complete program the website’s gate compiles with the compiler as it is written here, and the output shown beneath it is the output the program prints.
Values and copies
A variable holds its value, never a reference to another variable. Every assignment copies: a number or a truth value, a record whole, a fixed array whole, and a dynamic array element by element, so a change to the copy leaves the original as it was. A pointer is a value too, an address: copying a pointer copies the address, and both copies then point at the same cell.
A call hands a value parameter a copy of its argument, taken at the call (how a parameter is handed over). The routine reads the value it was given for the whole call, even when it changes the place the argument came from, through a pointer or a variable it reaches. A routine that should see such a change takes the place itself, behind a pointer.
{
Copies - every assignment copies, and a value handed to a routine keeps the value it was given.
'Point' is a record and 'Numbers' a dynamic array of numbers. Assigning either one copies it whole, so a change to
the copy leaves the original as it was. 'Report' receives a list by value and a pointer to the holder the list came
from: it changes the holder's list through the pointer, and still reads the number it was handed at the call.
}
program Copies;
imp
WriteLn : std;
const
PointLine = "first (%lld, %lld), second (%lld, %lld)";
ListLine = "left[0] = %lld, right[0] = %lld";
HandedLine = "handed %lld, the holder's list now %lld";
Capacity = 1;
StartX = 1;
StartY = 2;
MovedX = 10;
StartNumber = 5;
ChangedNumber = 99;
type
{ A point is a record of two coordinates, copied whole by an assignment. }
Point = record
x : int64;
y : int64;
end;
{ A list of plain numbers, whose elements an assignment copies. }
Numbers = array of int64;
{ A holder keeps one list in its slot. }
Holder = record
slot : Numbers;
end;
{ The routine changes the holder's list through the pointer, then reads the list it was handed by value. }
procedure Report(handed : Numbers, place : pointer Holder);
begin
place.slot[0] := ChangedNumber;
WriteLn(HandedLine, handed[0], place.slot[0]);
end;
{ The copies of one routine: a record, a list, and a list handed by value beside a pointer to its holder. }
procedure Work();
var
first, second : Point;
left, right : Numbers;
holder : pointer Holder;
begin
first.x := StartX;
first.y := StartY;
second := first;
second.x := MovedX;
WriteLn(PointLine, first.x, first.y, second.x, second.y);
left := new Numbers reserve Capacity;
left[0] := StartNumber;
right := left;
right[0] := ChangedNumber;
WriteLn(ListLine, left[0], right[0]);
holder := new Holder;
holder.slot := left;
Report(holder.slot, holder);
dispose holder;
end;
begin
Work();
end.It prints:
first (1, 2), second (10, 2)
left[0] = 5, right[0] = 99
handed 5, the holder's list now 99Cells on the heap
new and a type makes a cell of that type on the heap and answers a pointer
to it (allocation), and dispose
and the pointer releases the cell
(dispose-statement). A
program releases every cell it makes, on every path through the routine that
holds it, in one of four ways: a dispose, a defer dispose that runs when
the routine ends (deferred statements),
handing the cell on to a caller or to another routine, or binding it to an
owner at the allocation with until, new Node until program. The compiler
follows each cell from its new to its release and refuses a program that
loses one, releases one twice or reads one after its release.
A dynamic array needs no dispose for its own storage: it belongs to the
activation that made it, or to the owner its until names, and is reclaimed
when that owner ends. An array whose elements own cells is released with
dispose, which releases those cells with it.
| Written | Code | The compiler’s words |
|---|---|---|
a cell made and never released, cell := new Node; and no dispose | 13102 | heap cell is not released on every path: last use at line 33, the path leaving at line 34 releases nothing — dispose it, defer the dispose, return it, or bind it to an owner with 'until' |
a cell released twice, dispose cell; dispose cell; | 13104 | heap cell is disposed again after it was already released on every path reaching here — remove the repeated dispose of the cell allocated at line 32 |
a field read after its cell is released, dispose cell; WriteLn(Line, cell.weight); | 13105 | heap cell is dereferenced after it was already released on every path reaching here — the cell allocated at line 32 is used after its dispose; move the use before the release |
One owner per cell
Every cell has one owner at a time, and the owner is the one place that releases it. The pointer type of a place says what the place does with a cell:
| Declared | The place |
|---|---|
cell : pointer Node, a variable, a field or an element | owns the cell it holds, and releases it or hands it on |
function Made(...) : pointer Node | hands the cell it answers to its caller, who then owns it |
cell : owning pointer Node, a parameter | takes the cell from the caller, and releases it or hands it on |
place : pointer Node, a parameter | is lent the cell for the call, while the caller keeps owning it |
seen : borrowed pointer Node | views a cell another place owns, and never releases it |
Three sentences decide every hand-over:
- A name hands its cell over once. Storing a cell into an owning field or element hands it to the record or the array, whose release then releases it, and handing the same cell on again before the name holds a fresh cell gives the cell two owners, which the compiler refuses.
- A cell read out of a field or an element stays that slot’s.
taken := shelf[0]gives the cell a second name, not a second owner: the slot keeps owning it until a store through the same name and path clears it,shelf[0] := nil, and only then doestakenown the cell. - Two names the compiler cannot prove to be one place are two places. A routine is judged by its own text, so a swap of two elements at indices only the running program knows takes both cells out first, then stores both.
Releasing a record or an array releases every cell its owning slots hold, and
storing a fresh dynamic array over one releases the cells its old value still
holds, as dispose of the old value would.
{
Owners - heap cells with one owner each, handed over once and released by their owner.
'Made' answers a fresh cell, which its caller then owns. 'Shelf' is a list whose elements own the cells they point
at: storing a cell into an element hands it over, and the release of the list releases every cell it holds. A cell
read out of an element stays the element's until a store through the same element clears it, so 'Work' clears the
first element before it owns what it read, and hands that cell to 'Retire', whose owning parameter takes it and
releases it. Replacing the shelf with a fresh list releases the cells the old list still holds, and the release of
the fresh shelf at the end of 'Work' releases the rest.
}
program Owners;
imp
WriteLn, Length : std;
const
WeightLine = "the first cell weighs %lld";
EmptyLine = "the first element is empty";
RetiredLine = "retiring a cell of weight %lld";
LengthLine = "the fresh shelf holds %lld elements";
Capacity = 2;
FreshCapacity = 1;
LightWeight = 3;
HeavyWeight = 8;
type
{ A cell on the heap, made with 'new'. }
Node = record
weight : int64;
end;
{ A list whose elements own the cells they point at. }
Shelf = array of pointer Node;
{ A fresh cell of the given weight, which the caller owns. }
function Made(weight : int64) : pointer Node;
begin
Made := new Node;
Made.weight := weight;
end;
{ The routine owns the cell its parameter takes, and releases it. }
procedure Retire(cell : owning pointer Node);
begin
WriteLn(RetiredLine, cell.weight);
dispose cell;
end;
{ One shelf, each of its cells handed over once and released by the owner that holds it last. }
procedure Work();
var
shelf : Shelf;
taken : pointer Node;
begin
shelf := new Shelf reserve Capacity;
shelf[0] := Made(LightWeight);
shelf[1] := Made(HeavyWeight);
WriteLn(WeightLine, shelf[0].weight);
taken := shelf[0];
shelf[0] := nil;
if shelf[0] = nil then
WriteLn(EmptyLine);
Retire(taken);
shelf := new Shelf reserve FreshCapacity;
WriteLn(LengthLine, Length(shelf));
dispose shelf;
end;
begin
Work();
end.It prints:
the first cell weighs 3
the first element is empty
retiring a cell of weight 3
the fresh shelf holds 1 elements| Written | Code | The compiler’s words |
|---|---|---|
one cell stored into two elements, shelf[0] := cell; shelf[1] := cell; | 13106 | heap cell is handed to a second owner: the store at line 35 put the cell allocated at line 34 into an owning slot of 'shelf', which releases it, and an owning field or element releases everything it holds — so this store gives one cell two owners and its release would happen twice, from code nobody wrote. Store a fresh cell here, mark the destination 'borrowed pointer' to borrow rather than own, or move the cell by clearing the slot that held it |
a cell read out of an element released while the element still holds it, taken := shelf[0]; dispose taken; | 13109 | heap cell is released by hand although the container holding it releases it: the cell allocated at line 34 stands in an owning slot of a container on every path reaching here, and that container's own release walks the slot - so this dispose is the first of two releases and the second comes from code nobody wrote. Remove this dispose and let the container's release make it, clear the slot first if the cell must leave the container, or mark the slot 'borrowed pointer' so the container only views the cell |
Borrowed pointers
A borrowed pointer, declared borrowed pointer Node, views a cell another
place owns: a program reads and writes through it, and never releases the cell
through it. A function may answer one, a view of a cell an argument lends, and
a record may keep one in a field. Four rules keep a view valid, and the
compiler reads each of them off the declarations and the routine’s own text:
- One writer per call. A call hands a place that a parameter can write to that parameter alone, so two arguments of one call never reach one place when the parameter receiving either of them can write it; two elements of one array are two places only when their indices are two different constants (how a parameter is handed over).
- A view rests only where its owner outlives the place. A borrowed pointer may be kept in a variable of the routine that owns the cell, in a place reached through the owner itself, or anywhere when the owner is a global; a store into a place that outlives the owner, such as a global, is refused, and so is an answer that carries the view to a caller.
- Any change of its owner’s place ends its views. A release of the cell, a store over the owner, and a call whose heading lets it change the owner each end every view of the cell; the routine takes the view again after the change before it reads through it. Each call is judged by the callee’s heading and by the scope of the names it reaches.
- What the rule cannot follow is refused by name. Where the declarations cannot tell whether the owner outlives the place, or which of two elements an index selects, the compiler refuses the program and names the way out.
{
Views - borrowed pointers, which read a cell another name owns.
'Heavier' answers a borrowed pointer to the heavier of two cells: both stay their owners', and the caller reads
through the view. 'Window' is a record whose 'seen' field is a borrowed pointer, kept in a variable of the routine
whose variables own the cells, so the owners outlive the place that keeps the view. Releasing the cell the view
points at changes its owner's place and ends the view, so 'Work' takes the view again before it reads. The light
cell's release is deferred to the end of 'Work', and the heavy cell is released by hand.
}
program Views;
imp
WriteLn : std;
const
SeenLine = "the window sees a cell of weight %lld";
LightWeight = 3;
HeavyWeight = 8;
HeaviestWeight = 12;
type
{ A cell on the heap, made with 'new'. }
Node = record
weight : int64;
end;
{ A window keeps a view of a cell, which it never releases. }
Window = record
seen : borrowed pointer Node;
end;
{ A fresh cell of the given weight, which the caller owns. }
function Made(weight : int64) : pointer Node;
begin
Made := new Node;
Made.weight := weight;
end;
{ The heavier of two cells, answered as a view: both cells stay their owners'. }
function Heavier(first : borrowed pointer Node, second : borrowed pointer Node) : borrowed pointer Node;
begin
if first.weight >= second.weight then
Heavier := first
else
Heavier := second;
end;
{ Two owners, a window that views the heavier of their cells, and a view taken again after a release. }
procedure Work();
var
light, heavy : pointer Node;
window : Window;
begin
light := Made(LightWeight);
defer dispose light;
heavy := Made(HeavyWeight);
window.seen := Heavier(light, heavy);
WriteLn(SeenLine, window.seen.weight);
dispose heavy;
heavy := Made(HeaviestWeight);
window.seen := Heavier(light, heavy);
WriteLn(SeenLine, window.seen.weight);
dispose heavy;
end;
begin
Work();
end.It prints:
the window sees a cell of weight 8
the window sees a cell of weight 12| Written | Code | The compiler’s words |
|---|---|---|
one variable handed to two pointer parameters of one call, Move(cell, cell); | 5784 | the call to 'Move' reaches 'cell' through parameter 'source', which can write it, and through parameter 'target', which can write it, and a place one parameter can write reaches the routine through that parameter alone: hand 'cell' to one of the two, and give the other a place of its own |
two elements at indices the compiler cannot tell apart, Swap(address row[index], address row[other]); | 5785 | the call to 'Swap' reaches two elements of 'row' through parameter 'first', which can write one of them, and through parameter 'second', which can write one of them, and their indices are not two different constants, so the compiler cannot tell the two elements apart: hand 'Swap' one 'address row' and the two indices, and let it select both elements |
a view of a local holder’s cell kept in a global, gview := holder.node; | 5788 | 'gview' cannot keep a view of the cell 'holder' holds: 'gview' is a global, which lives as long as the program, while 'holder' is a variable of 'Work', which must release the cell or hand it on before it returns - so the view would outlive what it names, and a read through it afterwards returns whatever the next allocation put there, with nothing to report it. Keep the view in a variable of 'Work', which ends no later than the cell, or keep the owner itself there instead of a view of its cell |
a record holding a view of a local cell answered to the caller, Build := box; | 5791 | 'Build := box' carries the view 'box.view', kept at line 34, out of its owner's reach: the answer goes to the caller of 'Build', which outlives it, while 'made' is a variable of 'Build', which must release the cell or hand it on before it returns - so the view would outlive what it names, and a read through it afterwards returns whatever the next allocation put there, with nothing to report it. Keep what carries the view within 'Build' and release it there, or keep the owner itself there instead of a view of its cell |
a read through a view after a call that can change its owner, seen := holder.node; Replace(address holder); WriteLn(Line, seen.weight); | 5790 | 'seen' is read through after its view ended at the call to 'Replace' at line 45, whose parameter 'h' can change 'holder', since any change of its owner's place ends a borrowed pointer and the cell it pointed at may be released there: read through 'seen' before that change, or take the view again after it |
a nested routine keeping a view of its enclosing routine’s cell in storage its own caller lent, place.view := holder.node; | 5789 | 'place.view' cannot keep the view 'holder.node': 'place.view' lies in the storage the caller lent through 'place', and the cell belongs to 'holder' of an enclosing routine, so the compiler cannot tell from the declarations whether the cell it views outlives 'place.view', and the store is refused rather than left to read a released cell. Keep the view in a variable of this routine, or keep the owner itself there instead of a view of its cell |
a borrowed pointer released, dispose seen; | 5200 | dispose statement cannot release a 'borrowed pointer' value of data type 'borrowed pointer Node': a borrow is owned elsewhere (a container, the program, or another scope), which releases it — dispose the owning pointer instead |
Where a program’s memory lives
A program uses three kinds of memory, and each of its values lives in one of them:
| Memory | What lives there | How long |
|---|---|---|
| the stack | the frame of every activation: a routine’s parameters and variables, and the program body’s variables smaller than 64 KiB | until the activation returns |
| static storage | the program body’s variables of 64 KiB and above, and every variable of a library’s body | from the start of the program to its end, holding its start value when the program starts |
| the heap or the arena | the cells new makes and the elements of dynamic arrays | until the cell’s owner releases it |
The stack a program runs on is the one the system gives it unless the build
states its size with --stack-size, and the compiler warns where one frame
grows above one mebibyte without such a statement. Static storage is part of
the program image, and mica --inspect names how much of it the image maps
(the memory the image needs).
Whether the third kind is the hosted heap or a fixed arena is the build’s
memory class.
The two memory classes
--memory-class chooses where the cells and the dynamic arrays of a program
come from, and the program’s source does not change:
| Class | Written | Where the memory comes from |
|---|---|---|
| hosted heap | --memory-class hosted-heap, the default | the C library’s heap, which grows as the program asks |
| fixed arena | --memory-class fixed-arena=<bytes> | one block of the stated size, claimed when the program starts, 1 MiB where no size is written; the program never asks the system for heap memory |
An arena takes a size from 16 bytes to 1 GiB, and it never grows: an
allocation it cannot serve stops the program with the trap
allocation_failure, naming the line of the allocation
(traps on every tier). A small arena
serves a long run because memory follows the activations: a dynamic array a
routine makes is reclaimed when that routine returns, and a value that must
live longer names its owner with until.
{
Classes - one program, built for the hosted heap and for a fixed arena, printing the same lines under both.
'Work' makes a scratch list of sixty-four numbers every time it runs and releases nothing by hand: the list belongs
to the activation that made it, and its memory is reclaimed when 'Work' returns. Five thousand rounds therefore fit
in an arena of sixteen kibibytes. The kept list is bound to the program with 'until program', so it lives beside
the scratch lists until the program ends.
}
program Classes;
imp
WriteLn, Length : std;
const
Rounds = 5000;
ScratchLength = 64;
KeptLength = 4;
KeptNumber = 41;
DoneLine = "%lld rounds done, checksum %lld";
KeptLine = "the kept list holds %lld numbers, the first %lld";
type
{ A list of plain numbers. }
Numbers = array of int64;
var
kept : Numbers;
checksum, round : int64;
{ The sum of a scratch list that this activation makes and its end reclaims. }
function Work(seed : int64) : int64;
var
scratch : Numbers;
index, sum : int64;
begin
scratch := new Numbers reserve ScratchLength;
sum := 0;
for index := 0 to ScratchLength - 1 do
begin
scratch[index] := seed + index;
sum := sum + scratch[index];
end;
Work := sum;
end;
begin
kept := new Numbers reserve KeptLength until program;
kept[0] := KeptNumber;
checksum := 0;
for round := 1 to Rounds do
checksum := checksum + Work(round);
WriteLn(DoneLine, Rounds as int64, checksum);
WriteLn(KeptLine, Length(kept), kept[0]);
end.Built for each class and run, it prints the same lines under both:
--memory-class hosted-heap
5000 rounds done, checksum 810240000
the kept list holds 4 numbers, the first 41
exit=0
--memory-class fixed-arena=16384
5000 rounds done, checksum 810240000
the kept list holds 4 numbers, the first 41
exit=0| Written | The compiler’s words |
|---|---|
an arena below the smallest size, --memory-class fixed-arena=8 | fixed-arena size budget '8' is below the 16-byte minimum |
What the compiler leaves to the checked tier
Where the compiler stops following a cell, such as a record stored whole
through another pointer, it says so with the remark 13111 when the build
passes --remarks (remarks). It goes on refusing a
second release or a use after the release where the names it still follows
make one, and leaves the rest to the checked tier, --optimize debug,checked
or a set naming checked. A checked build stops a second release with the
trap double_dispose, a read or a write through a released cell’s own pointer
with use_after_dispose, and a run that ends with cells it never released
with leaked_cells, naming each cell and the line of the new that made it
(traps on the checked tier).
{
Checked - a cell the compiler stops following, and the checked build that stops its second release.
'Holder' owns one node. 'Work' stores a holder whole through a pointer, where the compiler stops following the
node and says so in a remark. It then reads the node out of the destination and releases it twice, once through
the destination's field and once through the copy it read. The checked build finds the node no longer live at
the second release and stops the program there, naming the line.
}
program Checked;
imp
WriteLn : std;
const
WeightLine = "the node weighs %lld";
NodeWeight = 8;
type
{ A node is the cell a holder owns. }
Node = record
weight : int64;
end;
{ A holder is a record whose one owning field holds a node. }
Holder = record
node : pointer Node;
end;
{ The routine stores a holder through a pointer, then releases its node twice. }
procedure Work();
var
local : Holder;
target : pointer Holder;
copied : pointer Node;
begin
target := new Holder;
local.node := new Node;
local.node.weight := NodeWeight;
value target := local;
copied := target.node;
WriteLn(WeightLine, copied.weight);
dispose target.node;
dispose copied;
dispose target;
end;
begin
Work();
end.Built with mica --compile --link --optimize debug,checked --remarks --source Checked.mica --build build,
the compiler reports the remark:
Error Report for source 'Checked.mica'
Remarks:
39: value target := local;
^ obligation remark 13111 [39,5]: the analysis follows the cell allocated at line 37 no further: the pointer is stored through another pointer, so the compiler no longer proves that the cell is released, and refuses a second release or a use after the release only where the names it still follows make one; a checked run stops every second release and every use after it except one through an address taken inside the cell, and fails when the cell is never releasedand ./build/Checked prints its line and stops at the second release:
the node weighs 8
Mica runtime failure: reason=double_dispose (10)
Mica runtime context: file=Checked.mica, line=43, column=5
Mica runtime source: dispose copied;Memory in tasks, streams and at the C boundary
A task, a generator and a stream hand cells over by the same one-owner rule, and tasks, generators and processes states what each one may take and keep. Who releases a cell that crosses into C or comes back from it is stated in the C boundary.