Implementing nested scopes

[fnune]

I'm having trouble wrapping my head around how one can represent an AST that's inherently built to represent nested structures (scopes and control flow) into the mostly flat LLVM IR.

This is Christophe's suggestions from an email conversation (which we decided to bring onto GitHub) that should serve as an introduction in this topic:

At first sight, it looks like you need to implement that yourself.

For example, if you have a nested function, you can pass an extra argument that points to an activation record for the calling function. Or you can build a closure (it's very similar, and more general, since it also covers returning anonymous functions).

So far, I have not seen direct support in LLVM IR, but I vaguely recall some discussions about doing it. Is there an Ada compiler that uses LLVM? If so, you could see what code they generate for that.

At the moment, Vampa's variable references are unimplemented and variable declarations essentially just print out the most basic LLVM IR wherever the builder is currently positioned:

vampa/src/libvamc_llvm/src/variable_declaration.rs

Lines 28 to 34 in 78691f0

	let allocation = self
	.builder
	.build_alloca(self.context.i32_type(), name.as_str());
	self.builder.build_store(allocation, value.into_int_value());
	Ok(value)

This means declared variables aren't actually accessible from anywhere. The LLVM tutorial language Kaleidoscope simply includes a hash map that stores variables by name, and this hash map is later on used to access the values those variables point to.

Although Vampa is a toy programming language and a learning project right now, I plan to implement nested scopes. A global hash map storing variables and nested scopes aren't concepts that go so well together, so...

The purpose of this issue is to discuss how one would go about implementing scopes in Vampa to achieve nested scopes. Two things are necessary:

• Whenever the program tries to access a variable, we need to be able to identify what scope it's being accessed in. I've been looking at LLVM's LexicalScope but I'm not sure if this is the right construct.
• Vampa must then be able to access that scope and determine if the accessed variable is in it, or in any of its parents. This means there must be some sort of relationship between scopes, and LexicalScope's getParent method looks promising.

If anyone knowledgeable on this topic happens to stumble upon this, I would gladly welcome some help or being pointed to a good resource.

Useful links:

• Vampa's AST
• LLVM Language Reference Manual
• Inkwell documentation (this is the bindings library that Vampa uses for LLVM)

[fnune]

Halfway through the language reference manual there's mention of the following:

• DILocalVariable: has a scope field that must point to a DILexicalBlock
• DILexicalBlock: also has a scope field that must point to another DILexicalBlock

DILexicalBlocks can be attached to Functions as metadata. These tools seem like the appropriate constructs to implement nested scopes in Vampa, as far as I can tell.

[fnune]

For the MVP, here's a simple implementation with just a hash map: #2

[nikitas-theo]

Hello, also trying to implement nested scoping for my own compiler and looking at this issue has been helpful. Thank you. If I make any progress I can update here, if it is still active.

[fnune]

Awesome! I've not come back to developing Vampa but I'd like to do it at some point. Updates on your progress here would be great, if you have the time.

Also, could you link to your current progress? Just out of curiosity.

[fnune]

Might be helpful: https://craftinginterpreters.com/local-variables.html

[nikitas-theo]

Hello! I actually implemented nested scoping for my compiler project. I used an extra hidden struct argument in the form of an llvm struct that contains any variables the inner function needs from the outer scopres. Essentially you have nested structs of the form: struct_input = {parent_argument_1, parent_argument_2, ..., *grand_parent_struct}. The idea was implemented as shown here Anh Nguyen thesis paragraph 6.2.9, Nested Functions. You can also look at my work here https://github.com/nikitas-theo/pcl. Cheers.