Procedure

Nested Procedure

A Nested procedure is a procedure declared inside another procedure. With supported languages, nested procedures can to access variables outside of its scope, without having to pass the parameters explicitly.

The C Language does not support nested procedures, but many languages do, including languages as diverse as Scheme/Racket, Pascal, Ada, Modula-3, OCaml, Haskell, Python, Javascript, C#, Scala, and even Fortran 90.

Different languages implement nested procedures in different ways:

• Static Scope / Lexical Scope: The word static refers to the text of the program, as opposed to its execution. A statically scoped language searches the program text, starting from the current nested procedure, and moving outwards through its enclosing procedures until it finds a procedure that declares the variable.
  • In the example below, $h$ accesses the variable $w$ of procedure $f$ with value $5$.
  • If you were to remove the declaration val w = 5 for a statically-typed language, it would give you a "w" Not Found Error, even though you declare it in g()
• Dynamic Scope: The word dynamic refers to run time, the execution of the program. A dynamically scoped language uses a stack-like structure to search for the variable to access. (This is more complicated to implement, because we have to consider all possible stacks that could occur at run time, so every single procedure, until you find one).
  • $h$ accesses the variable $w$ of procedure $g$ with value $7$

def f() = {
	val w = 5
	def g() = {
		val w = 7
		h()
	}
	def h() = {
		val z = 4
		z + w
	}
	g()
}

Most modern programming languages are defined with static scope because it is easier to reason about: to find the variable w that procedure h accesses, just start at h and look outwards through the program text.

in CS241E, we implement statically scoped variables.

Implementing Nested Procedures in CS241E

We could use the idea of trying to follow the dynamicLink variable, but we also don’t know how many frames are in between. We add another pointer called the static link.

Static Link: Holds the address of the most recent frame of its directly enclosing procedure.

Accessing outer variables To generate code to access variable w from inside procedure h, a compiler generates the following accesses:

1. Read the parameter pointer in the frame of h to find the parameters of h
2. Read the static link in the parameters of h to find the frame of the directly enclosing procedure f.
3. Access the variable w in the frame of f

Nesting depth of a procedure: Number of levels of outer procedures that enclose it

def f() = {
	val w = 5
	def g () = { ... }
	def h () = {
		def k () = { ... }
	}
}
 

Computing Static Links

We group the static link with the parameters of a procedure.

We will make it the responsibility of the caller to compute the correct static link address and pass it to the callee in the same way as if it were just another extra argument.

We define depth as the deeper inside {}, the greater the depth.

To reach the frame of a procedure with the depth of enclosing from the caller procedure, we need to read static links $n$ times, where $n=\text{depth(caller)}-\text{depth(enclosing)}$ Since $\text{depth(enclosing)}=\text{depth(callee) - 1}$, we have the following in terms of caller and callee (but I think the above is more intuitive): $n=\text{depth(caller)}-\text{depth(callee)}+1$

Example: Using the functions above, when procedure k calls out to procedure g, $n=2-1+1=2$, so we read two static links to determine the static link for g.