. CS320 Implementing Subprograms
	http://www.csci.csusb.edu/dick/cs320/sebesta/10

. Thanks to
Deborah Chormicle who corrected the page numbers to match the
5th edition of the text.

. Contents
	10.1 General Semantics of Call & Return
	10.2 FORTRAN I through to 77
	10.3 ALGOL-like Languages
	10.4 Blocks
	10.5 Dynamic Scope
	10.6 Subprogram names as arguments.

. 10.1 General Semantics of Call & Return
Make sure you know what is said about what happens
when a subprogram is called, and what must happen when it
returns.  

. 10.2 FORTRAN I through to 77
Since the variables are static and local or static and common
and because recursion is not handled this is simple.
	(the standard did not stop a compiler from compiling a recursive
	 subprogram. Neither did it require that it handled it correctly.
	 Typically the program compiled and ran for ever.
	)

Note the terms: 
	Activation Record (class),
	Activation Record Instance(ARI) (object),
and the structures structure.

Notice... that the FORTRAN was limited by the technology
of the time.... a linker but no real compilers.

. 10.3 ALGOL-like Languages
Notice the different form of an ARI(Figure 10.3, p404).

These allow subprogram to be declared INSIDE other subprograms
and so finding the correct context for a statement can be quite
complex.  This is one case where C is much simpler than Algol 60,
Algol 68, Pascal, Ada,...   However, C++ allows a function to be
declared in a class, *and* a class to be declared (and hidden)
inside a function.... 

C is simpler.  C functions can be recursive and C blocks
do introduce local variables (unlike the FORTRANS) that are allocated
on the stack or heap.  BUT, unlike ALGOL, Pascal and Ada and related Algol
like languages functions are not defined inside other functions:
	So a variable is
		1. local
		2. declared in an outer block
		3. An argument
		4. Declared as a global in this file
		5. Declared as an 'extern' variable in another file.
It is not difficult to work out a simple algorithm, for the compiler to
associate each variable usage with the correct object.  It lets the
linker (link-loader) bind extern variables to addresses.  It is
still static resolution and binding.
These can not depend on where the function is
called but only on the information that the compiler can gather
as it compiles the definition of the function.

In C (but not C++), an activation record is very like that on
page 404 and 405 (figs 10.3 and 10.4).
However there is no need for a static link.  (IMHO (In My Humble Opinion))

The example on page 405 is roughly like
	void sub( double total, int part)
	{	int list[5]; /* list[0..4] not [1..5] */
		double sum;
		...
	}

Recursion is easily handled by using a stack to hold the links, arguments,
and the other parts of the activation record.  The call puts the
activation record on the stack, and a return replaces the activation record
by the value of the expression in the return.  Blocks
also push local variables  onto the stack and then pop them off
again.

Exercise: Compile and run the code on page 408(factorial)
	as a C++ program and test it.
	Add special outputs at the point marked 1
	that print out the value of n at that point.
	What happens if you do the same at point 2 (THINK!)

Make sure you can show how a simple C function like this uses a stack
to handle recursion.

There won't be any questions on displays in 10.3.4.2
on the final.  However you may need displays when/if you do
a more advanced course like CS470 or CS620.

. 10.4 Blocks
This is pretty much revision of CS202 stuff.
Oddly very few programmers use nested blocks, in my experience. And when
they do, it is because the are writing a 'for' loop.  This may be
why Java doesn't have blocks.

This may be why both C++ and Ada make it easy to have a loop that
both declares and controls a local variable.

. 10.5 Dynamic Scope

In my experience Dynamic scope is associated with languages that are
interpreted.  C/C++ macros are the exception.

Further, most implementations rely on the Deep Access technique
with a single run-time stack and a sequential search down the
activation records for a matching identifier.

LISP was defined by such an interpreter - called EVALQUOTE by the way.
Nowadays LISPs tend to use static scope instead.  (defun ....) in
our LISP does this.  So does Scheme.

When I added 'define' to XLISP to create our laboratory LISP I stayed
close to the original form of LISP binding a Lambda expression to the
symbol.  The result is that our LISP can 'define' with dynamic binding
and 'defun' with static binding.

In Scheme static binding and the '(LET ((var val)...) expr...)'
form lets a group of functions be defined (in expressions) that
share access to a set of variables that nobody else can touch.  The
functions themselves have global scope and can called from outside
the (LET ...).  This very like static functions in C++.  It works
with (defun...) in our LISP.


. Personal Note.
Life would be easier if we just BANNED implicit global variables
and replaced them by explicitly named and imported variables.  Ada
packages make this a natural way to work.  Modula has explicit 
statements of what each module exports and imports.  Object-oriented
programming languages make it easy and safe to have local (class-wide)
variables shared between several functions.

. 10.6 Subprogram names as arguments.
Again C makes it easy.  No problem with static links etc since the
variables in the subprogram are resolved by the compiler.  The 'qsort'
function in the C library is a common example.  So is UNIX signal
handling.  This is also used in the X-windows graphic programming
system.

C has a simple rule:
	A function name *is* an address.
		The address of the start of the code.

Java does not allow function names to be function arguments.  However
you can declare a class that has a function in it and hand an
object in this class into a function as an argument.  It works
but is a little clumsy.

The C rule that the name *is* an address also makes it simple
to compile and run.  It does not make it easy for the programmer
to get it right!

I won't be asking questions on the general rules for subprogram
names in this section.

However this is not unlike the FUNARG problem in LISP (chapter 13)...

. Exercises/Assigned work
The review questions are very helpful with the exception of the
work on displays (8,9,10,11,12,16,17).

. Bonus Exercises/Problems
1. Create, compile, and test C++ programs where a function is
declared inside the body of another function.  Hint.  A local
class declaration...