Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: Add nested-function support in a language the based on a stack-machine Date: Tue, 13 Feb 2018 23:27:05 -0500 Organization: A noiseless patient Spider Lines: 76 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-02-022@comp.compilers> References: <18-02-009@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="62876"; mail-complaints-to="abuse@iecc.com" Keywords: code Posted-Date: 14 Feb 2018 13:08:41 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1957 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