Re: Add nested-function support in a language the based on a stack-machine

On Mon, 12 Feb 2018 11:25:36 -0800 (PST), dror.openu@gmail.com wrote:


>Suppose I have a simple C-like programming language:
>
> int foo() {
> int x = 10;
> int bar(y int) {
> return y * 2
> }
> return bar() + x
> }
>
>Like you can see, it supports nested functions.
>
>I already implemented the lexing-parsing phases, and now I'm working
>on the code generation and the stack-machine. most of the operations,
>and the simple flow-control already implemented but I need some
>help/ideas how to solve the nested-function task.
>
>The stack-machine has two registers, accumulator, and a temporary register.
>
>Each frame contains: `[arguments, local variables, return address,
>caller frame and stack pointer, temporaries and data operations]`. I
>read about two ways to implement the nested-function. one, using an
>activation-link (also called static-link), and display. Is there any
>better idea to handle this? If I'll choose one of these idea, is it
>compile time calculation or do I need to store something in runtime?
>if it's a runtime thing, what's the time complexity for it? is it O(1)
>operation, or something like O(k) where k is the depth of the
>function.


Using activation pointers in the stack frames, you do end up with an
O(n) list. To get something M lexical levels away, you need to follow
M pointers.


A display is O(1) to use: to get from, e.g., level 4 to level 2, the
level 4 function just looks at the pointer in display[2].


Both are O(1) to maintain at runtime - just a pointer save/restore.




Whether they work for you depends on the language. These methods work
for languages like Pascal, but not for languages like Lisp where
nested functions can be called after their parent has termninated and
the stack environment that created them has disappeared.


And as I mentioned in another post, there is an issue mixing displays
with object oriented languages.




If you prefer to go with more advanced compiler techniques, there is
either closure conversion or lambda lifting. They can get pretty
involved [again depending on the language], so rather than us trying
to explain them here, it is better that you read about them and ask
questions if you don't understand something.






>[This at least used to be a standard topic in compiler texts. You should
>be able to do either in O(1). -John]


I have never actually seen lambda lifting (as such) covered in any
compiler text ... I learned of it perusing research papers.


But certainly the other methods should be in any book since ~1990.


Not that lambda lifting is that hard to grasp: once you understand
closure conversion, it's obvious that lambda lifting is simply a (more
complicated) optimization for situations that don't require closure
persistence. Of course, in such situations, you could just choose to
stack allocate the closure rather than heap allocating it. Once
you're committed to the code rewriting necessary to do conversion, the
extra needed to do lambda lifting may be less of a concern.


YMMV,
George

Return to the comp.compilers page.
Search the comp.compilers archives again.