CS320 Notes on Subprograms

http://www.csci.csusb.edu/dick/cs320/sebesta/09.html
http://www.csci.csusb.edu/dick/cs320/sebesta/09

Contents

	9.1 Introduction
	9.2 Fundamentals
	9.3 Design Issues
	9.4 Local Referencing Environments
	9.5 Parameter Parsing: theory and practice
	9.6 Subprograms as Parameters
	9.7 Overloading
	9.8 Generic Subprograms
	9.9 Separate vs Independent
	9.10 Functions
	9.11 Nonlocal Environments
	9.12 User defined overloaded operators
	9.13 Coroutines

    Exercises
    Problems

9.1 Introduction.

	Humans can design complicated things that work because we use
	a process of 
		abstraction
	This means abstracting the important features,
	working with these, 
	and then
	take each feature and work out the details.

	Abstraction means replacing a lot of detail by a more
	or less imaginary single item.

	Pretending the Many is actually One.

        One kind of abstraction is
		procedural abstraction
	One command (call) mapped into many commands (body).


	Two ways of getting desired effect:
                    (1) Open subroutine or Macro
                    (2) Closed subroutine, procedure,...
				Procedure: no value returned/void
				Function:  Returns a value.
                
	    Open subroutine or Macro
		 During or before compilation replaces subprogram call 
		   by its expansion.

	    Closed subroutine, procedure, function,...                    
		 One copy is compiled. Each subprogram call transfers
		    control to start of code and this code returns to
		    the instruction after call.

9.2 Fundamentals - Learn the definitions.

	Distinguish:-
	    CALL: A call of the subprogram
	    NAME: The name of the subprogram/function
	    DEFINITION: The Definition  of the subprogram
		Says precisely how it does it, in detail
		as well as how to use it.
	    DESCRIPTION: A description of how to call it.
		Says how to use it.
			Parameter types
			Procedure or function
			If function: what is returned
				(C/C++/Java Prototype)

	parameters = arguments
		data that is given by the caller to the body.

	Procedures are NOT functions!
		A procedure in C is a function that returns no useful value.  

	The book uses the word 'protocol' for a description of
	how a subprogram is to be used:
			Parameter types
			Procedure or function
			If function: what is returned
	In C/C++ this is called a 'prototype'
		(Easily confused with a prototype version of a program.)
	Theorists call it a 'signature'.

9.3 Issues - learn

	This sets the agenda for the rest of the chapter.

9.4 Local Environment

The C code on page 332 has the effect of accumulating all the successive
arrays that it adds up.  What do you change so that it doesn't do this but
gives the sum of each array alone. (easy in C and C++)

How do you modify it so that: adder(array, length) accumulates more and
clear() resets the running sum to zero.(tricky in C, easy in C++)

How do you further make it impossible for a user to accidentally destroy
the current value of sum by assigning a value  other than zero
to it? (Tough in C, Easy in C++)

9.5 Parameter passing

	Why parameters?
	    BASIC and COBOL do without.
	Semantics:  Learn!
	    in
	    out
	    inout
	Implementation models: Learn!
	    value
	    result
	    value-result
	    reference
	    Name  -> now reborn as late binding.
	Examples
		FORTRAN
		ALGOL 60, 68
		Pascal
		Ada
		C
		Note a dirty secret about C macros.
		  They pass parameters by name!

	Try the following macro in a program based on pages 315..316.
	#define SIGMA(s,a,i,n) for(i=1,s=0.0;i<=n;s+=a,i++)

	Here is an example of the code:
	http://www.csci.csusb.edu/dick/cs320/sebesta/09.name.cc
	main()
	{
		int i;
		float sum;

		SIGMA(sum, i, i, 10);
		cout << sum <<endl;

		SIGMA(sum, i*i, i, 10);
		cout << sum <<endl;

		int j;
		double dimsum;
		SIGMA(dimsum, j*j*j, j, 10);
		cout << dimsum <<endl;

		SIGMA(dimsum, (10-i)/(double)i, i, 10);
		cout << dimsum <<endl;

	}

	Find a way to use SIGMA so that it does not compile!

Type-checking

		Which is more expensive: 1000 programmers 
		checking the types of their arguments themselves, or 
		writing type checking into a language?

Implementation Details.

		The Stack.
		Thunks
		Arrays?

Examples

Is it possible to write a perfect SWAP(x,y) macro in C that works for all
possible calls?  Here is the normal code:
#define	SWAP(x,y)	{ double t=x; x=y; y=t; }
Find 3 or 4 ways to make this either not compile, or else compile
and do the wrong thing.  

How does an inline void static function in C++ differ from a
macro in C?   (list 3 answers)

9.6 Subprograms as parameters

Can a function name be used in C without calling it?  If so what
does it mean and what can you do with it.

Notice the complications that arise with determining the referencing
environment:  start from which call/definition?  Pages 351-352.
A language designers headache.

9.7 Overloading

	One identifier + many possible types
	defines a special purpose function.

9.8 Generics

	Year	Has		Hasn't
	1983	Ada		All languages
	1995	Ada		All languages
	1996	Ada,C++ 	The rest
	20??    Ada,C++,Java	?

9.9 Separate Compilation

Look in the source code for our languages
to see how separate compilation is organized in C:
	http://www.csci.csusb.edu/dick/cs320/lisp/src/
	http://www.csci.csusb.edu/dick/cs320/prolog/src/

9.10 Design for functions

	Side effects???
	Type of result

9.11 Access non-local Environments

	COMMON
	Nested
	Export/import

	Again C is a little more sophisticated than the book
	suggests.  A declaration that is external to all
	functions, and is described as static is shared
	only by the functions that are in the same file.

	C++ Classes and Ada Packages provide a useful compromise:
		Set of subprograms share a set of common variables
		That can be made private.

9.12 DIY Operators

User defined overloaded operators

9.13 Coroutines

I find that a variation of the co-routine is the Semi-coroutine 
or restartable subprogram.  They aren't in the book but are
very helpful for making the structures of solutions of some
problems fit the structure of the problem.  They are not in the book
because they have never been implemented in a high-level programming
language.  However they shine a light on how normal co-routines
work and are easier to use and implement than co-routines.

A semicoroutine is a subprogram that hides within it the
'resume' mechanism so that whenever it is called it
restarts at the point that it last returned. A semi-coroutine
can return a value each time it suspends operation and then can
be called a cofunction.

It is a simple kind of pseudo-parallelism.  It is
also easy to simulate using low-level ideas like gotos
and labels.

Semi-co-routines are asymmetrical.  They are called like normal
subprograms (as functions or procedures).  Internally they
restart themselves.  They hide this from the caller.
You call restartable functions/procedures/subprograms in the normal way.  
Invisibly
and automatically they remember their previous state on exit,
and when called, restart
themselves just after the last return.

Semicoroutines are efficient, easy to write, and easy to use... it is a 
pity that they have never been incorporated into any languages.  On the 
other hand they are easy to code in COBOL, FORTRAN, ASSEMBLER, C or C++.


Suppose we had a version of C/C++ with semi-co-routines we can write functions
that are designed to handle whole streams of data correctly -- ones that
mirror the structure of the data being handled.  A very good example of
these are function that recognize and parse streams of data according to
various grammars.  Here is an example.

Suppose we have an incoming stream of characters  and want to classify its
characters according to this XBNF:
	input_stream::= #( (odd_a | non_a )  (even_a | non_a ) ).
(Given input "aaa" this classifies the characters like this:
	a: odd a
	a: even a
	a: odd a
and in string "aba":
	a: odd a
	b: non_a
	a: odd a
)

We could (If C++ had two extra statements) write:

string example(char c){
	restart();
	while(true){
	  if( c == 'a' )
	  	resume("odd a");
	  else resume("not an a");

	  if( c == 'a' )
		resume( "even a" );
	  else resume("not an a");
	}
}
Each time the above resume(...)s it stores information before returning 
control out of example(), that allows the restart() function to jump back 
to the next statement after the last resume statement.


A compiler writer would make the restart() and resume() functions work 
directly handling the stack plus some hidden static storage.  Application 
programmers can instead write a C or C++ that uses static storage, a switch
statement, goto's and labels that simulates the above effect.  Similar code
is used in other languages like COBOL and Pascal.

However we can also do this ourselves by adding static storage for the
state -- the number of the last resume + code to transfer control back
to the correct place.  A convention is to use Q0,Q1,Q2, for the labels
and QS for the variable because theorists use Q for the state of a automaton
or machine.

string example(char c){
    /*restart*/
	static int QS=0;

switch(QS){case 0:goto Q0; case 1:goto Q1; case 2:goto Q2; case 3:goto Q3;
case 4:goto Q4; }

	Q0:
	while(true){
	  if( c == 'a' )
	  	{QS=1; return("odd a"); Q1:; }
	  else {QS=2; return("not an a"); Q2:; }

	  if( c == 'a' )
		{QS=3; return( "even a" ); Q3:; }
	  else { QS=4; resume("not an a"); Q4:; }
	}
}
A complete program is in
	http://www.csci.csusb.edu/dick/cs320/c++/odda.cpp

By the way... it's possible to optimize the above code... but this is
not worth the effort in this and most cases.