4 ms·
My first (and only) serious compiler had such nested functions, though without stack frames. Instead my VM had two stacks: one for function arguments and locals
by loup-vaillant 3y ago
My first (and only) serious compiler had such nested functions, though without stack frames. Instead my VM had two stacks: one for function arguments and locals, and the other for return addresses, same as Forth.
I had no stack frame at all. Instead, the compiler kept track of the stack offset of every accessible local (relative to the top of stack). That way the implementation of my nested function was kind of trivial: there were no difference between true locals like `x` and locals from an outer scope like `s`, except of course for the possibility of shadowing.
One reason this was not special is that internally, it was nested scopes all the way down: there was one scope per local variable, so merely declaring two variables already means dealing with nested scopes. Once that was out of the way adding nesting functions was really easy (I believe it added less than 20 lines to my compiler).
Nowadays I think I would use a single stack instead, but if my language is simple enough I’ll probably skip the frame pointer and just keep track of offsets like I did this first time.
- kragen 3y agoif your outer function f called a function 'quicksort' which called a function 'partition' which called your nested function 'compare', how did 'compare' get access to the variables of f from its statically enclosing scope? how did it know how many locals 'quicksort' and 'partition' had pushed onto the operand stack?
- loup-vaillant 3y agoErr… I think recursive inner functions would just blow up… oops. I guess it’s a good thing I didn’t advertise inner functions and only used them in the standard library…
- kragen 3y agowell, that's the problem the static link solves; it's not such a difficult thing to implement if you let procedure values (function pointers) be two words instead of one. gcc emits trampoline code onto the stack at runtime to support this without breaking abi compatibility, so the pointer to the nested function actually points to the trampoline, which just supplies the static link and calls the real nested function