CSC302 2011S, Class 29: Representing Procedure Calls

Overview:
* Context: Supporting Recursive Functions.
* The Call Stack.
* Making Better Use of the Call Stack.

Admin:
* Late/Missing: AC, JL
* We'll use about fifteen minutes at the start of Friday's class to 
  talk about presentations.
* No homework due this week.
* No homework due next week.
* Readings for Friday: 
  Wikipedia on Evaluation Strategy (http://en.wikipedia.org/wiki/Evaluation_strategy);
  Encyclopedia of CS on Parameter Passing (http://portal.acm.org/citation.cfm?id=1074677).
* EC for Thursday's Convocation [academic]
* EC for Thursday's CS Extra [academic]
* EC for Friday's CS Table - Wolfram TED Talk, http://www.ted.com/talks/stephen_wolfram_computing_a_theory_of_everything.html [academic]
* EC for Bob's Benefit Bash Friday [peer]

Presentations: To be discussed Friday.
* Groups
* Projects
* Dates
  Friday, Week 12
  Monday, Week 13
  Wednesday, Week 13
  Friday, Week 13
  Monday, Week 14

Reminder: You take over 45 minutes of a class, using about 35 minutes
of it (5 for admin, 10 for Q&A).  Choose a topic (relevant).  Choose
a presentation style (lab, lecture, discussion, combination).  You may
(should) ask people to do a reading in advance.

Groups should have multiple topics ready for Friday's class so that 
we can resolve differences.

---

Context: Early design of programming languages.
* Subroutines (functions, procedures, methods) are a good idea.  (Even
  though goto does much of the same thing)
  * Makes it easier to reuse code.  (You can do it with goto, but ...)
    * Can shorten development time
  * Modularizing code makes it easier for multiple programmers to work
    on the same project.  (Good documentation on what a chunk of code
    does helps too.)
  * Clarifies parameterization
    * Also eliminates the problem of identical code for passing "parameters"
      to a labeled block.
  * Helps elminate problems of goto
  * Makes testing easier
  * Makes returning from the block of code easier
  * Clarifies code
  * Adds local variables
* Early implementations (Fortran) allocated a static block of memory
  for local variables and other information
* This technique does not work if you want recursive procedures

To implement recursive procedures, you often want a "call stack"

What information might you store for a procedure call?
* Return address: Where the procedure is supposed to branch when it is
  done.
* Local variables:  Why not just put them in static memory?  (That is,
  in the same area of memory that we put program globals.)
  * Perhaps a space issue
  * Makes recursion difficult
* Parameters: Inputs to the function
* Software state that might need to be restored
  * E.g., registers
    * Before you call a procedure, save all the registers you might care
      about (and restore them afterwards)
    * When a procedure starts, it stores any registers it might change
      (and restores them when it's done)
  * Frame pointer and Stack pointer
* Term for the thing we're storing all this information in: "The Frame"
* Temporary variables
  root = (-b + sqrt(b*b - 4ac)) / 2a
  t1 = b * b;
  t2 = 4 * a;
  t2 = t2 * c;
  t1 = t1 - t2;
* Address of frame pointer of parent function (not caller) in languages
  that allow nested function definitions.
  * Distinguish static and dynamic relationships
* Return value

* Example code that shows why offsets from the stack pointer are not
  constant
void silly(int n)
{
  int stuff[n];
  ...
}