1. Frobol, a stack-based Business Oriented Language
After Froth failed in the marketplace due to the unreadability of typical Froth programs, its designers came up with a successor language called Frobol. Like Froth, Frobol is a stack-oriented language: but now there is only one stack, and it only holds C chars. There is also only one built-in operation in Frobol, the function call, indicated by the '!' character. All other characters in Froth code simply push their own ASCII value on the stack.
2. Executing a Frobol program
Frobol programs are text strings that are executed one character at a time from left to right. Except for the '!' character, characters just push their own value on the stack. So the effect of executing the program abcdefg is to push the 7 characters abcdefg on to the stack, a first and g last.
The function call operator is different. It pops characters from the stack until it reaches either a slash character '/' (which is also popped) or the bottom of the stack. In either case, all characters except the slash are composed together in the order they were pushed to form a function name, which is then looked up in a table to find a (user-supplied) function to call. This function is given access to the Frobol stack, so that it can pop arguments and push return values.
For example, the Frobol program
abcdefg/puts!
when executed, will call the function registered as puts (which most likely will not be the C function of the same name) on a stack containing only abcdefg.
If no such function has been registered, the function call is a no-op; it leave the stack in the state abcdefg and goes on to the next character in the program. This means in particular that any text string is a legal Frobol program, a critical property for a Business-Oriented Language where code may be written or edited by managers with limited programming experience.
Nothing requires that the name of a function appear in the Frobol program itself. For example, if the function push has the effect of pushing the characters ts onto the stack, then the program
abcdefg/pu/push!!
will leave the stack in state abcdefg/pu/push before hitting the first '!', abcdefg/puts before hitting the second !, and then call puts (with whatever effect that might have) with the stack containing abcdefg.
However, it is the case that the only time a function call occurs is if a '!' character is processed from the code. Merely pushing a '!' onto the stack using frobol_stack_push does not cause a function call.
3. Where function table entries come from
Function table entries are supplied by the caller of the Frobol interpreter. A Frobol interpreter is an abstract data type with the following interface:
1 /* interface to embedded Frobol interpreter */
2 typedef struct frobol *Frobol;
3
4 /* Create a new Frobol interpreter in the initial state */
5 Frobol frobol_create(void);
6
7 /* Execute Frobol code (a null-terminated string) in interpreter */
8 void frobol_execute(Frobol interpreter, const char *code);
9
10 /* Destroy a Frobol interpreter */
11 /* This will call the cleanup handler for all registered functions
12 * and free the stack and any other internal data. */
13 void frobol_destroy(Frobol interpreter);
14
15 /* Add a new Frobol function with the given name */
16 /* When called, the function will be passed
17 * (a) the current interpreter and
18 * (b) the data pointer supplied at registration. */
19 /* The function cleanup, if non-null, will be called with the data pointer
20 * before the interpreter is destroyed. This may either be
21 * when frobol_destroy is called, or when the function is replaced
22 * by a new function with the same name. */
23 void frobol_register(
24 Frobol interpreter,
25 const char *name,
26 void (*func)(Frobol interpreter, void *data),
27 void *data,
28 void (*cleanup)(void *data));
29
30 /* Manipulate the Frobol interpreter stack. */
31 /* These are mostly useful for registered functions. */
32
33 /* returns 1 if stack is empty, 0 otherwise */
34 int frobol_stack_empty(Frobol interpreter);
35
36 /* removes and returns top of stack or returns '\0' if stack is empty */
37 char frobol_stack_pop(Frobol interpreter);
38
39 /* adds a new character to the top of the stack */
40 void frobol_stack_push(Frobol interpreter, char c);
The function frobol_register registers a new function in the Frobol interpreter, which is available in all subsequent calls to frobol_execute. If two functions are registered with the same name, the second takes precedence.
The arguments to frobol_register include in addition to the name and function handler a void *data parameter that can be used to pass extra information (including storage) to the function handler (this means that Frobol functions are really closures). The Frobol interpreter will not attempt to use this pointer in any way, but will pass it to the registered function when called. In addition, a cleanup function pointer is given to the interpreter to allow it to free any storage associated with the data pointer when the function is freed, either by being overwritten by a new function of the same name or when frobol_destroy is called.
Function handlers in Frobol are given a pointer to the Frobol interpreter as their first argument. This allows them to push and pop values using frobol_stack_push and frobol_stack_pop, test if the stack is empty using frobol_stack_empty, execute Frobol code using frobol_execute, and even register new function handlers using frobol_register. This makes implementing e.g. Froth-style arithmetic a simple matter of supplying the appropriate function handler, and even loops or other control structures can be constructed using sufficient cleverness.
4. Your task
Your task is to implement the interface given in frobol.h. The test script will expect you to submit one or more C files that will be compiled together to produce a library file that will then be linked with various test programs. An example of such a program is given below. You do not need to submit the frobol.h file itself, and if you do submit one it will be ignored---your files must implement exactly the interface described in the standard frobol.h header file. You should also not to submit any C files that contain a main routine; main will be supplied by the test program.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <string.h>
5
6 #include "frobol.h"
7
8 /* gcc -pedantic kills strdup! */
9 static char *
10 my_strdup(const char *s)
11 {
12 char *s2;
13
14 s2 = malloc(strlen(s) + 1);
15 assert(s2);
16
17 strcpy(s2, s);
18 return s2;
19 }
20
21 static char *
22 revdup(const char *s)
23 {
24 char *s2;
25 int i;
26 int j;
27
28 s2 = malloc(strlen(s) + 1);
29 assert(s2);
30
31 for(i = strlen(s) - 1, j = 0; i >= 0; i--, j++) {
32 s2[j] = s[i];
33 }
34
35 s2[j] = '\0';
36
37 return s2;
38 }
39
40 static void
41 echo(Frobol f, void *data)
42 {
43 puts(data);
44 }
45
46 static void
47 consume(Frobol f, void *data)
48 {
49 const char *s;
50 char c;
51
52 for(s = data; *s; s++) {
53 assert(!frobol_stack_empty(f));
54 c = frobol_stack_pop(f);
55 assert(c == *s);
56 }
57
58 assert(frobol_stack_empty(f));
59 }
60
61 int
62 main(int argc, char **argv)
63 {
64 Frobol f;
65 char c;
66 int i;
67 char buf[512];
68 char *s;
69
70 /* check that revdup actually works */
71 s = revdup("abc");
72 assert(!strcmp("cba", s));
73 free(s);
74
75 f = frobol_create();
76
77 frobol_register(f, "hello", echo, my_strdup("hello"), free);
78 assert(frobol_stack_empty(f));
79 frobol_stack_push(f, 'X');
80 assert(!frobol_stack_empty(f));
81 frobol_execute(f, "/hello!");
82 assert(!frobol_stack_empty(f));
83 c = frobol_stack_pop(f);
84 assert(c == 'X');
85 assert(frobol_stack_empty(f));
86 frobol_register(f, "hello", echo, my_strdup("bonjour"), free);
87 frobol_execute(f, "/hello!");
88
89 /* stress test on registrations */
90 for(i = 0; i < 10000; i++) {
91 assert(frobol_stack_empty(f));
92 sprintf(buf, "%d", i);
93 frobol_register(f, buf, consume, revdup(buf), free);
94 frobol_execute(f, buf);
95 assert(!frobol_stack_empty(f));
96 sprintf(buf, "/%d!", i);
97 frobol_execute(f, buf);
98 assert(frobol_stack_empty(f));
99 }
100
101 frobol_destroy(f);
102
103 return 0;
104 }
5. Sample solutions
1 #include <stdlib.h>
2 #include <assert.h>
3 #include <string.h>
4
5 #include "frobol.h"
6
7 /* stack parameters */
8 #define INITIAL_STACK_SIZE (1024)
9 #define STACK_GROWTH_MULTIPLIER (2)
10
11 /* dict parameters */
12 #define INITIAL_DICT_SIZE (1024)
13 #define MAX_DICT_LOAD (0.75)
14 #define DICT_GROWTH_MULTIPLIER (2)
15
16 /* hash function parameters */
17 #define HASH_MULTIPLIER (97)
18
19 /* magic characters for frobol_execute */
20 #define FUNCTION_CALL_START ('/')
21 #define FUNCTION_CALL_END ('!')
22
23 /* gcc -pedantic kills strdup! */
24 static char *
25 my_strdup(const char *s)
26 {
27 char *s2;
28
29 s2 = malloc(strlen(s) + 1);
30 assert(s2);
31
32 strcpy(s2, s);
33 return s2;
34 }
35
36 /* Frobol interpreter state */
37 struct frobol {
38 /* interpreter stack */
39 struct {
40 unsigned long size; /* number of allocated slots */
41 unsigned long top; /* index of first unused slot */
42 char *data; /* malloc'd data array */
43 } stack;
44 /* dictionary of registered functions
45 * implemented as a hash table with open addressing. */
46 struct {
47 unsigned long size; /* number of allocated slots */
48 unsigned long count; /* index of first unused slot */
49 struct registration {
50 char *name; /* registered name */
51 void (*func)(Frobol, void *); /* function handler */
52 void *data; /* uninterpreted data */
53 void (*cleanup)(void *); /* cleanup handler */
54 } *data;
55 } dict;
56 };
57
58 static void
59 frobol_initialize_dictionary(Frobol f)
60 {
61 unsigned long i;
62
63 f->dict.data = malloc(sizeof(*(f->dict.data)) * f->dict.size);
64 assert(f->dict.data);
65
66 /* clear the dictionary */
67 for(i = 0; i < f->dict.size; i++) {
68 f->dict.data[i].name = 0;
69 }
70 }
71
72 Frobol
73 frobol_create(void)
74 {
75 Frobol f;
76
77 /* allocate the interpreter */
78 f = malloc(sizeof(*f));
79 assert(f);
80
81 /* build the stack */
82 f->stack.size = INITIAL_STACK_SIZE;
83 f->stack.top = 0;
84 f->stack.data = malloc(f->stack.size);
85 assert(f->stack.data);
86
87 /* build the dictionary */
88 f->dict.size = INITIAL_DICT_SIZE;
89 f->dict.count = 0;
90 frobol_initialize_dictionary(f);
91
92 return f;
93 }
94
95 /* free name and call cleanup on slot i of dictionary if occupied */
96 static void
97 frobol_cleanup_internal(Frobol f, unsigned long i)
98 {
99 if(f->dict.data[i].name) {
100 free(f->dict.data[i].name);
101 if(f->dict.data[i].cleanup) {
102 f->dict.data[i].cleanup(f->dict.data[i].data);
103 }
104 }
105 }
106
107 void
108 frobol_destroy(Frobol f)
109 {
110 unsigned long i;
111
112 /* call cleanup on all registered functions */
113 for(i = 0; i < f->dict.size; i++) {
114 frobol_cleanup_internal(f, i);
115 }
116
117 /* free dict and stack data blocks */
118 free(f->dict.data);
119 free(f->stack.data);
120
121 /* free interpreter itself */
122 free(f);
123 }
124
125 static unsigned long
126 hash(const char *s)
127 {
128 unsigned long h;
129
130 h = 0;
131
132 while(*s) {
133 h = h * HASH_MULTIPLIER + *s++;
134 }
135
136 return h;
137 }
138
139 /* return index of the registration matching name */
140 /* or the first empty registration reached */
141 static unsigned long
142 frobol_lookup_internal(Frobol f, const char *name)
143 {
144 unsigned long i;
145
146 for(i = hash(name) % f->dict.size;
147 f->dict.data[i].name != 0
148 && strcmp(f->dict.data[i].name, name);
149 i = (i+1) % f->dict.size);
150
151 return i;
152 }
153
154
155 /* internal function for frobol_register */
156 /* this inserts a function into the dict hash table */
157 /* without calling strdup on the name */
158 /* and without checking for overload or updating count */
159 static void
160 frobol_insert_internal(Frobol f,
161 char *name,
162 void (*func)(Frobol, void *),
163 void *data,
164 void (*cleanup)(void *))
165 {
166 unsigned long i;
167
168 i = frobol_lookup_internal(f, name);
169
170 /* cleanup if already occupied */
171 frobol_cleanup_internal(f, i);
172
173 /* fill it in */
174 f->dict.data[i].name = name;
175 f->dict.data[i].func = func;
176 f->dict.data[i].data = data;
177 f->dict.data[i].cleanup = cleanup;
178 }
179
180 void
181 frobol_register(Frobol f,
182 const char *name,
183 void (*func)(Frobol, void *),
184 void *data,
185 void (*cleanup)(void *))
186 {
187 /* for growing the dict */
188 unsigned long old_size;
189 struct registration *old_data;
190 unsigned long i;
191
192 /* Pretty much a standard hash insert. */
193 if(f->dict.count > f->dict.size * MAX_DICT_LOAD) {
194 /* rehash */
195 old_size = f->dict.size;
196 old_data = f->dict.data;
197
198 f->dict.size = f->dict.size * DICT_GROWTH_MULTIPLIER;
199 frobol_initialize_dictionary(f);
200
201 for(i = 0; i < old_size; i++) {
202 if(old_data[i].name) {
203 frobol_insert_internal(f,
204 old_data[i].name,
205 old_data[i].func,
206 old_data[i].data,
207 old_data[i].cleanup);
208 }
209 }
210
211 /* don't need this any more */
212 free(old_data);
213 }
214
215 /* now do the real insert */
216 f->dict.count++;
217 frobol_insert_internal(f,
218 my_strdup(name),
219 func,
220 data,
221 cleanup);
222 }
223
224 int
225 frobol_stack_empty(Frobol f)
226 {
227 return f->stack.top == 0;
228 }
229
230 void
231 frobol_stack_push(Frobol f, char c)
232 {
233 if(f->stack.top >= f->stack.size) {
234 /* grow the stack */
235 f->stack.size = f->stack.size * STACK_GROWTH_MULTIPLIER;
236 f->stack.data = realloc(f->stack.data, f->stack.size);
237 assert(f->stack.data);
238 }
239
240 f->stack.data[f->stack.top++] = c;
241 }
242
243 char
244 frobol_stack_pop(Frobol f)
245 {
246 if(f->stack.top == 0) {
247 return '\0';
248 } else {
249 return f->stack.data[--f->stack.top];
250 }
251 }
252
253 /* fetches name back to FUNCTION_CALL_START */
254 /* returns a null-terminated string */
255 /* name is only good as long as you don't touch the stack */
256 static const char *
257 frobol_pop_name(Frobol f)
258 {
259 /* terminate the name */
260 frobol_stack_push(f, '\0');
261
262 /* pop until we hit delimiter or empty stack */
263 while(!frobol_stack_empty(f) && frobol_stack_pop(f) != FUNCTION_CALL_START);
264
265 /* if we hit delimeter, bump up one */
266 return f->stack.data + f->stack.top
267 + (f->stack.data[f->stack.top] == FUNCTION_CALL_START);
268 }
269
270 void
271 frobol_execute(Frobol f, const char *code)
272 {
273 struct registration *r;
274
275 while(*code) {
276 if(*code == FUNCTION_CALL_END) {
277 /* fetch function and run it */
278 r = &f->dict.data[frobol_lookup_internal(f, frobol_pop_name(f))];
279
280 if(r->name) {
281 r->func(f, r->data);
282 }
283 } else {
284 frobol_stack_push(f, *code);
285 }
286 code++;
287 }
288 }