1. Your task
Your task is to write an interpreter for the Froth programming language, defined below. Your program should either be in the single file froth.c or should be accompanied by a Makefile that generates a program froth when make is called with arguments make froth.
The froth program should take the name of a Froth-language file as argv[1] and should execute the program contained in that file. If the named file cannot be opened for reading (e.g., using fopen(file, "r");), the program should exit with exit code 1.
2. The Froth programming language
Programs in Froth are strings of ASCII characters, each of which is a operation in the language. With one exception noted below, execution proceeds left to right across the string, with each character causing another operation to occur. If the end of string is reached, the program exits with exit code 0.
Most of the operations operate on the main stack, which is a stack of values of type int, initially empty. Some operations also operate on a second auxiliary stack, which also holds ints and is also initially empty.
2.1. Froth operations
Each operation below is followed by a picture of the top of the main stack before and after the operation, surrounded by parentheses and separated by --. The top of stack in each case is on the right.
2.1.1. Arithmetic operations
- >
(x y -- x>y): Pop the top two elements from the stack and push 1 if the second-to-top (x) is greater than the top (y), 0 otherwise.
- =
- (x y -- x=y): Pop the top two elements from the stack and push 1 if the second-to-top (x) is equal to the top (y), 0 otherwise.
- +
- (x y -- x+y): Replace the top two elements with their sum.
- -
(x -- -x): Negate the top of stack. Note that there is no built-in subtraction operator in Froth: use -+ instead.
- *
- (x y -- x*y): Replace the top two elements of the stack with their product.
- /
- (x y -- x/y): Integer division as in C.
- %
- (x y -- x%y): Remainder operator as in C.
Note that there is no < operator in Froth.
2.1.2. Numbers
- z
- ( -- 0): Push zero on the stack.
- 0..9
( x -- x*10+d ): Each digit multiplies the top of the stack by 10 and adds its numerical value. So the sequence z12345 effectively pushes the number 12345 onto the stack.
2.1.3. Input and output
- !
( x -- ): Print the character whose ASCII value is x to stdout (like putchar).
- ?
( -- x ): Read a character from stdin and push its ASCII value on the stack, or -1 for end-of-file (like getchar).
- x
- ( x -- ): Terminate the program immediately, returning x as the exit code.
2.1.4. More main stack operations
- c
- ( x -- x x ): Copy the top element of the stack.
- d
- ( x -- ): Drop (throw away) the top element of the stack.
- s
- ( x y -- y x ): Swap the top two elements of the stack.
2.1.5. Auxiliary stack operations
- p
- ( x -- ): Push the top of the main stack onto the auxiliary stack.
- q
- ( -- x ): Pop the top of the auxiliary stack onto the main stack.
2.1.6. Whitespace
Whitespace characters (' ', '\t', '\r', and '\n') are no-ops and are ignored by the Froth language. This allows for nicer formatting.
2.1.7. Other characters
Any other characters are not legal Froth and should cause the program to exit with an exit code of 2. You may wish to print an informative message to stderr if this happens.
Clarification: It is not an error for a Froth program to contain a non-legal character, only to attempt to execute it. So, for example, the program
z[THIS CODE IS NEVER EXECUTED!]
is perfectly legal Froth.
2.2. Control flow
Control flow is done using pairs of matching square bracket operators. Each matching pair acts like a while loop in C; when a left bracket [ is encountered, it pops the top of the main stack and tests if the value is nonzero. If it is nonzero, the body of the loop (up to the next matching right bracket ]) is executed. Control then jumps back to the left bracket, which pops another value off the stack. If a zero value is popped, control skips to the character after the matching right bracket.
If there is no matching bracket in either case, the program terminates with exit code 3.
For example, the following code fragment computes the absolute value of the top of the stack:
c-z>[-z]
Here, the placement of z (push zero) before the ] guarantees that the body is executed at most once. This effectively turns the while into an if.
Here is another loop that prints out the alphabet backwards, followed by a newline:
z96 z26 +
c z96 >
[
c !
c z1- +
c z96 >
]
z10 !
2.3. Errors
It is an error to attempt to attempt to read an empty stack. Any operation that would consume more values than are present in the main or auxiliary stack should cause the program to exit immediately with exit code 4.
3. Storage allocation and premature exits
You should free any space you allocate by the end of your program if the interpreted program exits normally (by reaching the end of the program). Premature exits caused by errors or use of the x command are not required to free all allocated space: for these you can just call exit with an appropriate argument.
4. Submitting your assignment
If you have a single source file froth.c, submit that. Otherwise, submit all of your source and/or header files together with a Makefile that will generate froth when make is called with make froth. In this latter case, you can run the command
/c/cs223/bin/makeit 4 froth
to have make froth executed on your behalf in the submission directory (this is useful to see that you submitted everything you needed to).
You can also do
/c/cs223/bin/testit 4 public
to run the public test script /c/cs223/Hwk4/test.public on your submitted files.
5. More Froth
Here are some more examples of Froth programs. Some of these are taken from the public test inputs.
This program cat.froth copies its input to its output. The method is to keep reading chracters using a while loop as long as they are greater than -1 (or z1- as the number is written in Froth):
?cz1->[!?cz1->]d
Here's a more complicated program tac.froth that writes its input in reverse order to the output. The first loop is similar to the cat.froth program, except that instead of using ! to send the characters to the output, it uses p to push them to the auxiliary stack. The second loop uses q to pop characters from the auxiliary stack until -1 is reached.
z1-p?cz1->[p?cz1->]qcz1->[!qcz1->]d
Many of the longer test inputs were generated with the assistance of m4, a general-purpose macro processor (type info m4 on any Linux machine or see http://www.gnu.org/software/m4/manual/html_node/index.html). For example, to get song.froth, you can run the command m4 froth.m4 song.m4 > song.froth, after downloading froth.m4 (which provides various useful routines like PrintNumber) and song.m4.
6. Solutions
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #include "stack.h"
5
6 /* used internally by getall; initial size of buffer */
7 #define INITIAL_BUFFER_SIZE (4096)
8
9 /* exit codes */
10 #define EXIT_BAD_FILE (1)
11 #define EXIT_BAD_COMMAND (2)
12 #define EXIT_NO_MATCH (3)
13
14 /* reads the entire contents of f and returns them as a freshly-malloc'd string */
15 /* returns 0 on allocation error */
16 char *
17 getall(FILE *f)
18 {
19 int size; /* size of block holding buf */
20 int top; /* number of characters in buffer */
21 char *buf; /* buffer contents */
22 int c; /* input character */
23
24 size = INITIAL_BUFFER_SIZE;
25 buf = malloc(size);
26 if(buf == 0) return 0;
27
28 top = 0;
29
30 for(;;) {
31 /* grow the buffer if full */
32 if(top >= size) {
33 size *= 2;
34 buf = realloc(buf, size);
35 if(buf == 0) {
36 return 0;
37 }
38 }
39
40 /* grab and parse the next character */
41 c = getc(f);
42 if(c == EOF) {
43 /* we are done */
44 buf[top++] = '\0';
45 buf = realloc(buf, top);
46 return buf;
47 } else {
48 /* add it in */
49 buf[top++] = c;
50 }
51 }
52 }
53
54 #define OPEN_BRACKET ('[')
55 #define CLOSE_BRACKET (']')
56
57 /* return index of matching CLOSE_BRACKET */
58 /* calls exit(EXIT_NO_MATCH) if there isn't one */
59 int
60 matchForwards(const char *program, int pc)
61 {
62 int depth; /* number of open brackets encountered */
63
64 depth = 0;
65 for(; program[pc] != '\0'; pc++) {
66 switch(program[pc]) {
67 case OPEN_BRACKET:
68 depth++;
69 break;
70
71 case CLOSE_BRACKET:
72 if(--depth == 0) {
73 /* got it */
74 return pc;
75 }
76 break;
77
78 default:
79 break;
80 }
81 }
82
83 /* didn't find it */
84 exit(EXIT_NO_MATCH);
85 }
86
87 /* return index of matching OPEN_BRACKET */
88 /* calls exit(EXIT_NO_MATCH) if there isn't one */
89 int
90 matchBackwards(const char *program, int pc)
91 {
92 int depth; /* number of open brackets encountered */
93
94 depth = 0;
95 for(; pc >= 0; pc--) {
96 switch(program[pc]) {
97 case CLOSE_BRACKET:
98 depth++;
99 break;
100
101 case OPEN_BRACKET:
102 if(--depth == 0) {
103 /* got it */
104 return pc;
105 }
106 break;
107
108 default:
109 break;
110 }
111 }
112
113 /* didn't find it */
114 exit(EXIT_NO_MATCH);
115 }
116
117 /* horrible non-syntactic macros */
118 #define BINARY(code, op) case code: y = stackPop(s); x = stackPop(s); stackPush(s, x op y); break;
119 #define UNARY(code, op) case code: x = stackPop(s); stackPush(s, op x); break;
120
121 void
122 frothInterpreter(const char *program)
123 {
124 int pc; /* program counter */
125 Stack s;
126 Stack aux;
127 int x;
128 int y;
129
130 s = stackCreate();
131 aux = stackCreate();
132
133 if(s == 0 || aux == 0) abort();
134
135 for(pc = 0; program[pc] != '\0'; pc++) {
136 switch(program[pc]) {
137
138 /* arithmetic operations */
139 BINARY('>',>);
140 BINARY('=',==);
141 BINARY('+',+);
142 UNARY('-',-);
143 BINARY('*',*);
144 BINARY('/',/);
145 BINARY('%',%);
146
147 /* numbers */
148 case 'z': stackPush(s, 0); break;
149
150 case '0':
151 case '1':
152 case '2':
153 case '3':
154 case '4':
155 case '5':
156 case '6':
157 case '7':
158 case '8':
159 case '9':
160 x = stackPop(s);
161 stackPush(s, x*10 + (program[pc] - '0'));
162 break;
163
164 /* input and output */
165 case '!':
166 putchar(stackPop(s));
167 break;
168
169 case '?':
170 stackPush(s, getchar());
171 break;
172
173 case 'x':
174 exit(stackPop(s));
175 break;
176
177 /* more main stack operations */
178 case 'c':
179 x = stackPop(s);
180 stackPush(s, x);
181 stackPush(s, x);
182 break;
183
184 case 'd':
185 x = stackPop(s);
186 break;
187
188 case 's':
189 y = stackPop(s);
190 x = stackPop(s);
191
192 stackPush(s, y);
193 stackPush(s, x);
194
195 break;
196
197 /* auxiliary stack */
198 case 'p':
199 stackPush(aux, stackPop(s));
200 break;
201
202 case 'q':
203 stackPush(s, stackPop(aux));
204 break;
205
206 case ' ':
207 case '\t':
208 case '\r':
209 case '\n':
210 break;
211
212 case OPEN_BRACKET:
213 x = stackPop(s);
214
215 if(!x) {
216 /* skip to matching CLOSE_BRACKET */
217 pc = matchForwards(program, pc);
218 }
219
220 break;
221
222 case CLOSE_BRACKET:
223 /* skip back to matching OPEN_BRACKET */
224 /* subtract 1 so we land on the OPEN_BRACKET after pc++ */
225 pc = matchBackwards(program, pc) - 1;
226 break;
227
228 default:
229 exit(EXIT_BAD_COMMAND);
230 break;
231 }
232 }
233
234 stackDestroy(aux);
235 stackDestroy(s);
236 }
237
238 int
239 main(int argc, char **argv)
240 {
241 FILE *f;
242 char *program;
243
244 if(argc != 2) {
245 fprintf(stderr, "Usage: %s froth-program\n", argv[0]);
246 exit(EXIT_BAD_FILE);
247 } else if((f = fopen(argv[1], "r")) == 0) {
248 fprintf(stderr, "%s: cannot open for reading\n", argv[1]);
249 exit(EXIT_BAD_FILE);
250 } else if((program = getall(f)) == 0) {
251 fprintf(stderr, "%s: allocation error while reading file\n", argv[1]);
252 exit(EXIT_BAD_FILE);
253 } else {
254 fclose(f);
255 frothInterpreter(program);
256 free(program);
257 return 0;
258 }
259 }
1 /* integer stack type for use in Froth interpreter */
2
3 typedef struct stack *Stack;
4
5 /* returns new empty stack or 0 on allocation failure */
6 Stack stackCreate(void);
7
8 void stackDestroy(Stack);
9
10 /* returns true iff stack is empty */
11 int stackEmpty(Stack);
12
13 void stackPush(Stack, int);
14 int stackPop(Stack);
15
16 /* returns number of elements on stack */
17 int stackSize(Stack);
1 #include <stdlib.h>
2 #include <assert.h>
3 #include "stack.h"
4
5 #define INITIAL_SPACE (1024)
6 #define STACK_POP_EMPTY_ACTION() (exit(4))
7
8 struct stack {
9 int top; /* number of elements */
10 int space; /* size of allocated block */
11 int *data; /* contents of stack */
12 };
13
14 Stack
15 stackCreate(void)
16 {
17 Stack s;
18
19 s = malloc(sizeof(*s));
20 if(s == 0) return 0;
21
22 s->top = 0;
23 s->space = INITIAL_SPACE;
24
25 s->data = malloc(sizeof(*(s->data)) * s->space);
26 if(s->data == 0) {
27 free(s);
28 return 0;
29 }
30
31 return s;
32 }
33
34 void
35 stackDestroy(Stack s)
36 {
37 free(s->data);
38 free(s);
39 }
40
41 /* returns true iff stack is empty */
42 int
43 stackEmpty(Stack s)
44 {
45 return s->top == 0;
46 }
47
48 void
49 stackPush(Stack s, int x)
50 {
51 while(s->top >= s->space) {
52 s->space *= 2;
53 s->data = realloc(s->data, sizeof(*(s->data)) * s->space);
54 }
55
56 s->data[s->top++] = x;
57 }
58
59 int
60 stackPop(Stack s)
61 {
62 if(s->top <= 0) {
63 STACK_POP_EMPTY_ACTION();
64 } else {
65 return s->data[--(s->top)];
66 }
67 }
68
69 /* returns number of elements on stack */
70 int
71 stackSize(Stack s)
72 {
73 return s->top;
74 }