Karteikarten
Week 7
Karten in diesem Stapel (83)
- 1What is a variable– Variables are distinct from variable names: many variables may have the
same name
– A variable has a scope in a program: a region where it corresponds to a
particular box
– Variables do not correspond to data statements: they are created and
destroyed dynamically as a program runs
– Initialising a variable is not the same as assigning a value to it - 2lifetimeThe lifetime of a variable: when it is created, when it is destroyed
- 3scopeThe scope of a variable: which parts of the source program are able to access the variable
- 4locationThe location of a variable: what its address in memory is
- 5Static variablesSometimes called global variables
– Visible through the entire program - 6Local variablesSometimes called automatic variables
– Visible only in a local procedure - 7Dynamic variablesSometimes called heap variables
– Visibility can vary for different variables
– Used in object oriented and functional languages - 8Static variables lifetimeThe lifetime of a static variable is the entire execution of a program
– When the program is launched, its static variables are created
– They exist and retain their values until the program ends - 9Static variables ScopeThe scope of a static variable is the entire program
– Every part of the program (e.g. a procedure) can access them - 10Static variables locationThe location of static variables is the global segment of memory
- 11Disadvantages of combining variables and code• The executable code cannot be shared
– Suppose two users want to run the program
– Each needs to have a copy of the entire program, which contains both
the instructions and the data
– This means the instructions are duplicated in memory
– This is inefficient use of memory - 12Modern operating systems organise information into segmentscode segment
data segment - 13data segment– A data segment is read/write, and cannot be shared
- 14code segment– A code segment (instructions) is read-only, and can be shared
- 15Local variables lifetimeThe lifetime of a local variable is the function, procedure, method, begin..end block, or a {...} block where are defined
– They exist while the function, procedure, etc exists - 16Local variables scopeThe scope of a local variable is the function, procedure, etc where is defined
– A local variable has one name, but there may be many instances of it if
the function is recursive - 17Local variables location• The location of local variables is a stack frame
– The variables are accessed using the stack frame register
– The compiler (or assembler) works out the address of each local variable
relative to the address of the stack frame
– Therefore they cannot be stored in the static data segment - 18Accessing local variables• The compiler (or programmer) works out the exact format of the stack frame
• Each local variable has a dedicated location in the stack frame
• Its address (relative to the frame) is used in the load instruction
load R1,7[R14] ; local variable at position 7, R14 points to stack frame - 19Dynamic variables lifetimeThe lifetime of a dynamic variable does not need to follow the order that
stack frames are pushed or popped, it can be irregular
– A dynamic variable is created explicitly, e.g. using new in Java - 20Dynamic variables scopeThe scope of a dynamic variable is not limited to use in just one function
– They can be several functions or the entire program - 21Dynamic variables locationThe location of dynamic variables is the heap
– They can't be kept in the static data segment or the stack - 22Dynamic variables UsesUsed in functional and object-oriented languages
- 23The Heap• Typically contains a very large number of very small objects
• Contains a free space list, a data structure that points to all the free words of
memory
• Maintained by the language “runtime system”, not by the operating system
• When you do a new, a (small) amount of memory is allocated from the heap
and a pointer (address) to the object is returned
• When the object is no longer required, the memory used to hold it is linked
back into the free space list - 24MemoryCode
Global
Heap
Stack - 25Saved registersSave the registers the procedure needs to use on the stack, and restore
them before returning - 26Dynamic linkssince each stack frame can have a different size, how do we pop the top one o the stack?
each stack frame contains a pointer (called dynamic link) to the one below - 27stack frameDynamic link
Local variables
Static links for scoped variables - 28stack pointer(address of the top stack frame)
– Each architecture uses a standard register to keep the stack pointer
– In Sigma16, R14 is the stack pointer
– When you call, you push a new stack frame and increase R14
– As a procedure runs, it access its data via R14
– When you return, you set R14 to the stack frame below - 29Accessing a word in the stack frameWe need a “map” showing the format of a stack frame
Suppose that local variable “x” is kept at position 7 in the stack frame, so to
access the variable
load R1,7[R14] ; R1 := x
store R1,7[R14] ; R1 := x
They are called local variables because every call to a procedure has its own private copy - 30About the factorial program• Comments are used to identify the program, describe the algorithm, and
document the data structures
• Blank lines and full-line comments organise the program into small sections
• The caller just uses jal to call the function
• The function is responsible for building the stack frame, saving and restoring
registers
• The technique of using the stack for functions is general, and can be used
for large scale programs - 31data• Variables defined with data statement are static
– Each static variable must have a unique name
– Static variables exist through entire execution of program - 32procedure• Variables defined in a procedure are local
– Different procedures can use the same name for different variables
– Local variables are kept in the stack frame (accessed using R14)
– Call (push stack frame), return (pop stack frame)
– R14 points to current stack frame - 33A node is a record with two fieldsvalue
next - 34valuevalue is a word containing useful information (e.g. an integer, character)
- 35nextnext is a word containing a pointer to the next node in the list
- 36• The last node in the list has a special valuenil in the next field
- 37Accessing the fields of a node• Suppose p is a pointer to a node
load R1,p[R0] ; R1 := p
load R2,0[R1] ; R2 := (*p).value
load R3,1[R1] ; R3 := (*p).next - 38Representing a linked listLink lists tend to be scattered around in memory
- 39Basic operations on lists– Is a list p empty?
– What's the value in a node?
– What's the next node - 40Is list p empty?• Nil is 0, so the list that p points at is empty iff p=0
– The empty list exists but is not present in memory, it is represented as [ ]
• It is unsafe to perform an action on a list p unless p actually points to a node,
so this test is commonly needed - 41Is list p empty? codeload R1,p[R0] ; R1 := p
cmp R1,R0 ; compare p with 0
jumpeq pIsEmpty[R0] ; if p = 0 then goto pIsEmpty
; No, p is not empty
...
pIsEmpty
; Yes, p is empty
...
p data ‘a pointer’ ; p contains a pointer (ie, an address) that can be 0 - 42Get value in node that p points at: x := *p.value• This is safe to do only if p is not empty
• The value field of a node is at offset 0 in the node record - 43Get value in node that p points at: x := *p.value codeload R1,p[R0] ; R1 := p
load R2,0[R1] ; R2 := *p.value
store R2,x[R0] ; x := *p.value - 44Get pointer to next node in a list: q := *p.next• This is safe to do only if p is not empty
• The next field of a node is at offset 1 in the node record - 45Get pointer to next node in a list: q := *p.next codeload R1,p[R0] ; R1 := p
load R2,1[R1] ; R2 := *p.next
store R2,y[R0] ; y := *p.next - 46Traversing a list p• A while loop is the best looping construct for traversing a list
ListSum (p)
{ sum := 0;
while p /= nil do
{ x := (*p).value;
sum := sum + x;
p := (*p).next;
} - 47Search a list p for a value xAgain, the best looping construct is a while loop
ListSearch (p, x)
{ found := False;
while p /= nil && not found do
{ found := x = (*p).value;
p := (*p).next;
}
return found;
} - 48good example of the proper use of a while loop– The condition checks for end of data, and also for early completion
– The loop works even if the original list p is nil
– There is no break/continue statements or goto - 49cons: constructing a list consing a value to the frontCons is an important function, described in the paper: “Cons the magnificent”
• Suppose p = [23, 81, 62]
• q := cons (56, p)
• After computing q, we have
– q = [56, 23, 81, 62] q is the same as p but with 56 attached to the front
– p = [23, 81, 62] p is unchanged
• A function like cons is called a pure function (produces a new result but does
not modify its arguments) - 50Implementing conscons (x, p)
{ q := newnode ();
(*q).value := x;
(*q).next := p;
return q;
}
• No change is made to p, or to the node p points to
• A new node is allocated and set to point to p
• A pointer to the new node is returned - 51Getting a new node from avail list• Implementation of newnode(), where avail is the heap
• We remove the first node of avail
if avail = nil
then { error "fatal error: out of heap" }
else { newnode := avail;
avail := (*avail).next;
return newnode;
} - 52Inserting a node with x where p pointsr := newnode ();
(*r).value := x;
(*r).next := (*p).next;
(*p).next := r;
• Notice that we can insert x after the node that p points to
• But we cannot insert x before that node
• In list algorithms it is common to have two pointers, one lagging an element
behind the other (trailing pointer), to make insertion posible - 53header node• Problem: we cannot insert x at the front of the list (requires to change p)
• Solution: don't use an ordinary variable for p, make a header node
– The next field points to the list
– The value field is not used - 54Deleting a node• Need a pointer p into the list
• The node after p will be deleted
• Just change (*p).next to skip over the next node, and point to the one after
• Note that the node being deleted should be returned to the avail list, so it
can be reused - 55Code for deleting a node• If p points to a node, delete the node after that, assuming it exists
delete (p)
{ if p /= nil
then { q := (*p).next;
if q /= nil
then { (p*).next := (*q).next;
(*q).next := avail;
avail := q;
}
}
} - 56deleting a nodWe can't delete the node p points to, only the following node q points at
• If you know that p cannot be nil, the first test can be omitted
• We need to check whether q = nil; if it is, there's no node to delete
• It doesn't matter whether (*q).next is nil - 57Space leaksIf you return a deleted node to the avail list, it can be reused
• If you don't, this node becomes inaccessible (called garbage)
– It doesn't hold useful data and can not be allocated
• This is a bug in the program (you can run out of memory)
• Over time, as a program runs, more and more nodes may become inaccessible: a space leak - 58Memory managementIt's a bug if you delete a node that contains useful data
• It's a bug if you don't delete a node that doesn't contain useful data
• With complicated data structures, this can be difficult
• A common solution is garbage collection - 59garbage collection– The program doesn't explicitly return nodes to the avail list
– Periodically, the garbage collector traverses all data structures and marks the nodes it finds
– Then the garbage collector adds all unmarked nodes to the avail list - 60Sharing and side effects• Suppose p = [6, 2, 19, 37, 41]
• Traverse a few elements, and set q to point to the 19 node
• Now q = [19, 37, 41] and p is unchanged
• Then delete the second element of q, the result is
– q = [19, 41]
– p = [6, 2, 19, 41] Modifying q has also modified p
• This is called a side effect
– One of the biggest sources of bugs in large scale programs - 61Cons lists• Cons lists: representation of lists based on pure functions (no headers)
– You don’t modify existing data, but you create new data
– This approach fits with pure functional programming (e.g. Lisp, Scheme)
– Example: given a list x= [a,b,c] you can create a new list y = cons (q,x)
and the value of y is [q,a,b,c], but x is not modified, is still [a,b,c] - 62Header lists• Header lists: a list must have a header
– You can modify existing lists, commonly used in algorithmics, where it is
important to be able to modify a list
– Example: given a list x = [a, b, c] you use the insertion algorithm to
insert q before the first element of x, and this doesn’t create a new list y,
it modifies the existing list x, and now x = [q,a,b,c] - 63Comparing lists and arrays Direct access to an element– Array: gives direct (“random”) access to an element with arbitrary index i
– List: gives direct access only to an element you have a pointer to, so
random access is inefficient - 64Comparing lists and arrays Traversal– Array: initialise i to 0
• repeatedly set i := i+1; terminate when i ≥ n (purpose of a for loop)
– List: initialize p to point to the list
• repeatedly set p := (*p).next; terminate when p = nil - 65Comparing lists and arrays Memory needed per elemen– Array: need just the memory required for the element (typically a word)
– List: need a node for each element, which also requires space for the
next pointer (typically a word)
– So typically, an array with n elements needs n words, while a list
requires 2 × n words - 66Comparing lists and arrays Flexibility– Array: fixed size and needs to be allocated fully
– List: variable size and needs only enough memory to hold its nodes - 67More general data structuresWe can put several pointer fields in each node, and produce an enormous
variety of data structures, tailored for the needs of an application program - 68Doubly linked listeach node contains two pointers, one to the previous
node and one to the next
• Allows traversal both directions - 69Circular listthere is no “last” node where next=nil, instead every node
points to the next node, and the list loops back to itself
• There is no “first” or “last” node - 70A stack is an abstract data type– Idea: define the type by the operations it supports, not by the code that
implements it
– There may be different implementations of an ADT, and which
implementation is best may depend on the application using it - 71• The stack ADT is defined by the operations it supportspush, pop
- 72There are several completely different ways to implement a stack– We have already seen how to implement a stack with an array
– We can also do it with a linked list - 73Linked list implementation of stack• A linked list gives easy access to the front of the list, and a stack gives easy
access to the top of the stack
• Represent Empty stack as nil
• Push x is implemented by stack := cons (x, stack)
• Pop x is implemented by stack := (*stack).next - 74Array representation of stack• We can implement a stack using an array
• A variable stLim which gives the size of the array
– This is the limit on the maximum number of elements that can be pushed
• A variable stTop that gives the current number of elements in the stack - 75Array– A container that holds many elements
– Each element has an index (which is an integer)
– You can access any element x[i]
– You can access the elements in any order - 76Stack– A container that holds many elements
– You can only access the top element, and don't need to know its index
– You can (and must) access the elements in Last In First Out order - 77Pushing x onto a stack; push the x onto the stack
; stack[stTop] := R1 ; stTop := stTop + 1
push load R1,x[R0] ; R1 := x
load R2,stTop[R0] ; R2 := stTop
store R1,stack[R2] ; stack[stTop] := x
lea R3,1[R0] ; R3 := constant 1
add R2,R2,R3 ; R2 := stTop + 1
store R2,stTop[R0] ; stTop := stTop + 1 - 78Pop a stack, returning x; pop the stack, store top element into x
; stTop := stTop – 1 ; x := stack[stTop]
pop load R2,stTop[R0] ; R2 := stTop
lea R3,1[R0] ; R3 := constant 1
sub R2,R1,R3 ; R2 := stTop - 1
load R1,stack[R2] ; R1 := stack[stTop-1]
store R1,x[R0] ; x := stack[stTop-1]
store R2,stTop[R0] ; stTop := stTop - 1 - 79Issues with simplest implementation• It doesn't check for errors!
– If push is called when stack is full, data will be written outside the array
– If pop is called when stack is empty, a garbage result will be returned
• Either of these errors may cause the program to get wrong answers or crash - 80Robust software• Fragile software will respond to a minor problem by going haywire
– Might crash, or produce wrong answers
• Robust software checks for all errors and does something appropriate
– A minor problem doesn't turn into a major one - 81approaches for error handling– Produce a message and terminate the program
– Return an error code to the calling program and let it decide what to do
– Throw an exception, which will interrupt the calling program, and invoke
its error handler
• For simplicity, we will terminate the program if an error occurs - 82Error checking: push• If the stack is full, there is no space to store the new element, so push fails
; push (v)
; if stTop >= stLim
; then
; terminate because the stack is full: cannot push
; else
; stack[stTop] := v
; stTop := stTop + 1
; return () - 83Error checking: pop• If the stack is empty, there is no element to return, so pop fails
; v = pop ()
; if stTop == 0
; then
; terminate because the stack is empty: cannot pop
; else
; stTop := stTop - 1
; v := stack[stTop]
; return (v)
Informationen
- Beschreibung
- Computer Science Karteikarten am Week 7, erstellt von Isaac Gilbert am 22/02/2022.
- Erstellt von
- Isaac Gilbert
- Aufrufe
- 0
- Bewertung