Daniel Näslund
10 posts
ADT for fixed stacks similar to stretchy buffers
Edited by Daniel Näslund on
I've been writing an interpreter for The Mouse Programming Language. The code is structured around Pers example from the homework for day 3. My code can be found at https://github.com/dannas/rsc/blob/master/2018/mouse/main.c

I started out with a fixed value stack; then added a fixed call stack; then I needed a "control stack" for keeping track of the loop headers of nested loops. Hey, I might even throw in more stacks in case I decided to do abstract interpretation as suggested by Per and as is done in for instance Firefox Webassembly JIT-compiler.

 1 2 3 4 5 6 7 8 int32_t stack[NUM_STACK]; int32_t *stack_ptr; CallFrame call_stack[NUM_CALLFRAMES]; CallFrame *frame_ptr; char *control_stack[NUM_CONTROLSTACK] char **control_ptr; 

My problem is that I'd like to have one pair of PUSH/POP functions that could operate on all three of these stacks. How would you go about having a fixed stack in C? Just use two variables per each stack and don't "overthink" it? Use a struct that contains the two variables making use of void-pointers? Something else?

I admit that this example is artificial, since having unbounded space for these three stacks is not a problem for this small toy interpreter: I could just use stretchy buffers for the stacks! But I'm wondering if there are more "tricks" similar to stretchy buffers for having succinct ADTs in C?

Thank you once again for the streams so far!
Mārtiņš Možeiko
2236 posts / 1 project
ADT for fixed stacks similar to stretchy buffers
Not sure about what you are asking. You want to write PUSH(stack_ptr, value); or PUSH(frame_ptr, frame); and expect to work?

 1 2 #define PUSH(arr, x) *arr++ = x #define POP(arr, x) x = *arr-- 

Per Vognsen
49 posts / 1 project
ADT for fixed stacks similar to stretchy buffers
Edited by Per Vognsen on
Yes, don't overthink it. Two variables and either hand-coding the push/pop code with standard C idioms like *ptr++ = x and x = *--ptr is the way I'd usually do it, or maybe wrapping it with macros like I did in homework 2 and Martins just demonstrated. Either way, don't overthink it, just do it. "Just do it" is a good rule of thumb when programming in C when you find yourself in decision paralysis (often induced by experience with other languages).
Daniel Näslund
10 posts
ADT for fixed stacks similar to stretchy buffers
Edited by Daniel Näslund on
pervognsen
Yes, don't overthink it. Two variables and either hand-coding the push/pop code with standard C idioms like *ptr++ = x and x = *--ptr is the way I'd usually do it, or maybe wrapping it with macros like I did in homework 2 and Martins just demonstrated. Either way, don't overthink it, just do it. "Just do it" is a good rule of thumb when programming in C when you find yourself in decision paralysis (often induced by experience with other languages).

What I was trying to achieve, was having a way to place asserts inside PUSH/POP for ensuring that the stack pointers were within the limits of allocated memory. But I could just as well use separate POPS(arr, ptr, MAX, n) and PUSHES(arr, ptr, MAX, n) calls.

Thank you Martin and Per. Yeah, I've been somewhat damaged by C++ (who hasn't?) and by reading Peter Norvigs Python solutions (he has written a lot of useful and readable code, but I find myself getting a bit paralyzed by trying to compress my code too much, too early).