Bitwise » Forums » ADT for fixed stacks similar to stretchy buffers
dannas
Daniel Näslund
7 posts
#15288 ADT for fixed stacks similar to stretchy buffers
5 days, 21 hours ago Edited by Daniel Näslund on May 15, 2018, 5:23 a.m.

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!
mmozeiko
Mārtiņš Možeiko
1666 posts
1 project
#15291 ADT for fixed stacks similar to stretchy buffers
5 days, 19 hours ago

Not sure about what you are asking. You want to write PUSH(stack_ptr, value); or PUSH(frame_ptr, frame); and expect to work?

What about this?
1
2
#define PUSH(arr, x) *arr++ = x
#define POP(arr, x) x = *arr--

pervognsen
Per Vognsen
43 posts
1 project
#15292 ADT for fixed stacks similar to stretchy buffers
5 days, 19 hours ago Edited by Per Vognsen on May 15, 2018, 7:31 a.m.

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).
dannas
Daniel Näslund
7 posts
#15293 ADT for fixed stacks similar to stretchy buffers
5 days, 18 hours ago Edited by Daniel Näslund on May 15, 2018, 7:55 a.m.

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).