1. A pointer is a variable that identifies a memory location and holds the address of some other entity. It "points" to the other entity.
2. The "^" character is known as the dereferencing operator.
3. A use of point employs the value of a memory location. Using point^ references the actual value. It has been dereferenced.
4. All pointers are assignment compatible with the type ADDRESS and with the type of NIL.
5. Pointers are more easily moved around than actual values. Moving a data value may take significantly more steps than changing the value of a pointer.
6. Some pointers should be guarded, because they could hold the value NIL. Referencing an unguarded pointer when it holds the value NIL causes an error.
7. Procedures that can do pointer arithmetic are (from SYSTEM): ADDADR, SUBADR, DIFADR.
8. A dangling pointer is a pointer that has been left pointing to a memory location that has been deallocated.
9. Passing a pointer as a value parameter makes a copy of the pointer and therefore will be pointing to the same memory location as the original pointer. Since it is pointing to the same memory location, any changes to the value dereferenced will be reflected in the original memory, replicating the effect of a variable procedure.
10. A stack is an area of memory where procedure activation records are placed. Each time a procedure is called, an activation record is placed on top of the last activation record. Every time a procedure calls itself, another copy of its activation record is created, and they have to be removed in reverse order they were placed. The stack's ability to grow is dependent on how much memory is allocated to the stack and how deep the current chain of procedure calls is. A stack pointer is a marker that delimits the top end of the currently allocated stack. It is not available for program manipulation.
11. An activation record is the contents of the memory assigned to a procedure for its parameters and variables when it is invoked.
12. Since a new activation record is created for each procedure call for that specific procedure, each level of activation yields a new set of variables for independent manipulation. Once a recursive call is finished it can give a value back to the previous activation record and the values are passed down the chain to the original procedure. The amount of recursion that can be handled depends on how much memory is allocated to the stack.
13. The use of activation records is automatic, not under programmer control and so not truly dynamic.
14. A heap is the region of memory above the stack and in which program-controlled dynamic allocation and deallocation of memory can take place.
15. NEW and DISPOSE are used in Modula-2 to manage the heap.
16. These two procedures are relatively low level and their implementations may vary by machine, so they call ALLOCATE and DEALLOCATE, which must be visible. Their other magical property is that they have more than one possible syntax.
17. The two library procedures are ALLOCATE and DEALLOCATE from Storage. Any procedures with these names can be used, however, so the programmer can define ones other than those in Storage and make them visible.
18. A function procedure identifier cannot be dereferenced.
19. One can have the record contain another pointer; thus every allocation of such a record generates another pointer.
20. Two applications of dynamic memory include a dynamic database and an open ended queue.
21. A linked list consists of a sequence of dynamically allocated data items; each element of which includes a pointer to the next item on the list. The first item is the head, the last the tail. One needs at least a head pointer pointing to the head of the list.
22. Two extensions to the linked list ADT are append and delete. In append an item is linked to the last item of the linked list. In delete, an item is removed from one of the places in the list.
23.
DEFINITION MODULE LinkListADT; TYPE ItemPointType = POINTER TO ItemData; ItemData = RECORD number : CARDINAL; toPoint : ItemPointType; END; PROCEDURE Create (VAR List : ItemPointType); PROCEDURE Dispose (VAR List : ItemPointType); PROCEDURE AppendFirst (item : ItemData); PROCEDURE Append (item : ItemData); PROCEDURE Delete (index : CARDINAL); END LinkListADT.
24. An opaque data type is a type that is defined in a definition module, but whose details are hidden in the implementation module. They have to be declared as another opaque type or as a pointer type.
25. This limitation was made because it was thought that a compiler could only set aside memory for opaque types if they were all the same size and it was also thought that this implies they must be pointers.
26. When keeping track of variant dynamic records, one must reserve only the amount necessary to store each variant field. More house keeping is needed to ensure that the right amount of space is allotted for each variant.
27. The varying amounts of memory needed for variants of a dynamic record are handled using the alternate syntax of NEW.
28. Static memory allocation is determined when the program starts to run. The maximum amount of memory for the largest possible variant must be set aside.
29. Sub-record tags do affect the memory allocation, whether static or dynamic.
30. One would use handle^^ to point to the integer.
31. The built-in identifier SIZE will return the size of the type point^.
Problems
Note: Not all problems are shown. Most problems are left up to students as labs.
(* Created
June 22 1999
Chapter 12 Question 34 *)
MODULE TestVariantSize;
FROM STextIO IMPORT
WriteString, WriteLn, SkipLine;
FROM SWholeIO IMPORT
WriteCard;
FROM Storage IMPORT
ALLOCATE, DEALLOCATE;
FROM SYSTEM IMPORT
TSIZE;
TYPE
EnumDatType = (red, green, blue);
Item = POINTER TO SomeItem;
SomeItem =
RECORD
int : INTEGER;
card : CARDINAL;
real : REAL;
CASE bool : BOOLEAN OF
TRUE:
colour : EnumDatType; |
FALSE:
char : CHAR;
str : ARRAY [0..19] OF CHAR;
END; (* end CASE *)
CASE color : EnumDatType OF
red:
array1 : ARRAY [0..9] OF CARDINAL; |
green:
array2 : ARRAY [0..9] OF INTEGER; |
blue:
array3 : ARRAY [0..9] OF Item;
END; (* end CASE *)
END; (* end RECORD *)
VAR
test1, test2, test3 : Item;
BEGIN
NEW (test1, blue);
WriteString ("The size of test1^ is :");
WriteCard (SIZE(test1), 0);
WriteLn;
WriteString ("The tsize of test1^ is :");
WriteCard (TSIZE(SomeItem, blue), 0);
WriteLn;
NEW (test2, TRUE);
WriteString ("The size of test2^ is :");
WriteCard (SIZE(test2), 0);
WriteLn;
WriteString ("The tsize of test2^ is :");
WriteCard (TSIZE(SomeItem, TRUE, blue), 0);
WriteLn;
NEW (test3, FALSE);
WriteString ("The size of test3^ is :");
WriteCard (SIZE(test3), 0);
WriteLn;
WriteString ("The tsize of test3^ is :");
WriteCard (TSIZE(SomeItem, FALSE, green), 0);
WriteLn;
SkipLine;
END TestVariantSize.