-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME
181 lines (123 loc) · 7.78 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
Group #9 Assignment #2
Jon Boone
Joshua Datko
Paul DeMicco
Joseph Heenan
________________
This package contains all of the files for Assignment #2.
=======
interpreterext.py ** Contains the grammar for the original mini language along with
** support for the following functions: cons, car, cdr, nullp, intp
** and listp. These are described in detail below. Support for
** list concatination using '||' is also included.
interpreterext.py ** Contains the grammar for the original mini language along with
** support for the following functions: cons, car, cdr, nullp, intp
** and listp. These are described in detail below. Support for
** list concatination using '||' is also included. This version supports
** Dynamic memory managment (Garbage Collection, Mark/Sweep Algorithm).
programext.py ** Contains the implementation for the grammar.
programextgc.py ** Contains the implementation for the grammar. This version supports
** Dynamic memory managment (Garbage Collection, Mark/Sweep Algorithm).
makefile ** Contains targets to run (run-part1 and run-part2) and test (test-part1
** and test-part2) the interpreter (both parts), as well as targets for
** viewing (view-part1 and view-part2) and the mini-language length
** functions (view-func1 / view-func2).
*** GC Notes ***
The internals of the program were refactored such that the fundamental unit
is the ConsCell. A ConsCell has two pointers, car and cdr and can contain
Numbers, None (nil), or other ConsCells.
There is a global heap in the Heap class which allocated a fixed number of
HeapCells. A HeapCell is just a wrapper around a ConsCell with some extra
info for tracking if it is allocated.
Tracking allocations is by setting an allocation flag on the HeapCell.
Finding an available cell works by scanning the list and finding the first
cell that is unallocated. This is of course not as efficient, but it
handles fragmentation well.
Heap.collect implements mark and sweep. It can be called manually or if
alloc fails (if there are no free cells).
*** CHANGING THE HEAP SIZE ***
Search for GLOBAL_HEAP and set the heap value to the desired number. It's
defaulted to 20, which seems reasonable to actually test most things
without getting in the way.
TEST FILES - Will be explained in detail below:
________________
add1.p ** Used to test user defined function using while statement.
assignlist1.p ** Used to test assignment of result of plus operator
assignlist2.p ** Used to test various assignments, including lists and car
assignlist3.p ** Used to test assignment of nested lists
carTest1.p ** Used to test car function.
carTest2.p ** Used to test car function with nested list.
cdrTest1.p ** Used to test cdr function.
cdrTest2.p ** Used to test cdr function with nested list.
concatTest0.p ** Used to test concat function with list constants.
concatTest1.p ** Used to test concat function using Idents.
concatTest2.p ** Used to test concat function using Idents and nested lists.
concatTest3.p ** Used to test concat function using Idents and function call (cons) on rhs.
concatTest4.p ** Used to test concat function with function calls on both rhs and lhs.
concatTest5.p ** Used to test concat function using Idents and function call on lhs.
concatTest6.p ** Used to test concat function using Idents and function call (cdr) on rhs.
consTest0.p ** Used to test cons function used in user defined function.
consTest1.p ** Used to test cons function with a null list.
consTest2.p ** Used to test cons function used in a nested call.
consTest3.p ** Used to test cons function used in a nested call.
consTest4.p ** Used to test cons function used in a nested call with Idents.
consTest5.p ** Used to test cons function the result of which is used in a concat (||) operatation.
embeddedFunCall0.p ** Used to test embedded function calls.
embeddedFunCall1.p ** Used to test embedded function calls.
identTest1.p ** Used to ensure the Ident object parses correctly
iterListFromProf.p ** Used to test the iterative length function from the Professor.
listLenRec.p ** Used to test the recurive length function from the Professor.
memoryAlloc1.p ** Used to test memory allocation using cons.
memoryAlloc2.p ** Used to test memory allocation using cons, car and cdr.
memoryAlloc3.p ** Used to test memory allocation using cons and ints.
memoryAlloc4.p ** Used to test memory allocation using cons and ints.
memoryAlloc5.p ** Used to test memory allocation using cons on the result of prior invocations of cons.
memoryAlloc6.p ** Used to test memory allocation using literals.
predicateTest1.p ** Used to test nullp, listp, and intp.
recListFromProf.p ** Used to test the recurive length function from the Professor.
simpleGcTest.p ** Used to test a few simple assignments and functions calls to ensure
** Garbage collection runs properly.
whileTest1.p ** Used to test the while statement.
README ** This file. Contains details out how to run files, build, test, etc.
whileTest1.p ** Used to test the while statement.
README ** This file. Contains details out how to run files, build, test, etc.
DESCRIPTION: Assignment #2, Part #1
___________
This project extends the mini language and the interpreter by adding support for Lists.
List Grammar:
<list> -> [<sequence>]|[]
<sequence> -> <listelement>,<sequence>|<listelement>
<listelement> -> <list>|NUMBER
Take note that lists are enclosed in '[' and ']' instead of '(' and ')'.
The following functions have been added:
cons( e, L ) - returns a new list, with element e prepended to the front of list L
car( L ) - returns the first element in the list
cdr( L ) - returns the rest of the list (minus the first element)
nullp( L ) - returns 1 if L is null, 0 otherwise
intp( e ) - returns 1 if e is an integer, 0 otherwise
listp( e ) - returns 1 if e is a list, 0 otherwise
List concatenation is also supported by using the following operator '||'
RUNNING: Assignment #2, Part #1
___________
Can be run via make run-part1 < myinputfile (where you substitute myinputfile for an appropriate mini language input file)
TESTING: Assignment #2, Part #1
___________
All test case files (*.p) have been run through the interpreters to ensure proper operation.
VIEWING FUNCTIONS: Assignment #2, Part #3, Length Functions
__________
The following makefile targets are supported:
view-func1: This will show the iterative length function in the mini language. This function was built using the sample code posted by instructor on the Discussion board, with modified test data
view-func2: This will show the recursive length function in the mini language. This function was build using the sample code posted by instructor on the Discussion board, with modified test data
DESCRIPTION: Assignment #2, Part #2
___________
Part 2 of the project implements the same extensions to the mini languange however it implements dynamic memory allocation and
garbage collection using the following:
All memory allocation is done using the cons function call. This provides a heap of cons cells and organizes them in a list. Cons, car, cdr and nullp
have been reimplemented to access cells located in the heap.
Gabage collection is implemented using a mark and sweep algorithm.
RUNNING: Assignment #2, Part #2
___________
Can be run via make run-part2 < myinputfile (where you substitute myinputfile for an appropriate mini language input file)
TESTING: Assignment #2, Part #2
___________
All test case files (*.p) have been run through the interpreters to ensure proper operation.