Functions and procedures. Parameter passing. Nested procedures. First-class and higher-order functions. Implementation issues. Readings: Scott, ch 6, 8.1 - 8.3
When defining functions, the names of variables we give are called (formal) parameters.
function f(a, b, c) ... // parameters: a, b, c
When calling function, the values or variables we feed are called (actual) arguments.
f(i, 2 / i, g(i, j)); // arguments: i, 2/i, g(i, j)
- by value: formal is bound to value of actual.
- by reference: formal is bound to location of actual.
- by copy-return: formal is bound to value of actual; upon return from routine, actual gets copy of formal.
- by name: formal is bound to expression for actual; expression evaluated whenever needed; writes to parameter are allowed (and can affect other parameters!)
- by need: formal is bound to expression for actual; expression evaluated the first time its value is needed; cannot write to parameters.
- Ada: semantic intent is separated from passing implementation. Parameter modes:
in(default, read-only in subprogram),
out(write in subprogram) and
in out(read-write in subprogram).
- C: parameter passing by value, no semantic checks. Assignment to formal is assignment to local copy.
- C++: default is by-value. Can explicitly pass parameter by reference:
void incr (int& y).
- Java: by value only. Just different semantics for primitive types and objects.
Each subprogram invocation creates an activation record. Recursion imposes stack allocation.
- activation record: hold actuals, linkage information, saved registers, local entities.
- caller: place actuals on stack, return address, linkage information, then transfer control to callee.
- prologue: (before) save registers, allocate space for locals.
- epilogue: (after) place return value in register or stack position, update actuals, restore registers, then transfer control to caller.
- binding of locations: actuals and locals are at fixed offsets from frame pointers.
- complications: variable # of actuals, dynamic objects.
Frame pointer: pointing to the head/base of the stack frame/activation record Stack pointer: pointing to the top of the stack
Consider C function
printf("this is %d a format %d string", x, y);
printfcan have variable length of parameters. Within body of printf, we need to locate as many actuals as placeholders in the format string.
Solution: place parameters on stack in reverse order (actuals at positive offset from the frame pointer, locals at negative offset from the frame pointer)
Subprogram callers and callees must completely agree on who does what, how, and when. These details are encompassed in a protocol known as the calling convention.
- C (
cdecl): Parameters placed on the stack in right-to-left order. Caller required to clear the stack parameters.
- Microsoft Standard (
stdcall): called function required to clear the stack parameters.
- Fast Call (
fastcall): up to two parameters placed in hardware registers. Rest on the stack.
- Microsoft C++ (
thiscall): the "this" pointer passed through the CX register (x86)
Two solutions to handle objects of dynamic size on activation record:
- Solution 1: use indirection: activation record holds pointers simpler implementation, costly dynamic allocation/deallocation.
- Solution 2: local indirection: activation record holds offset into stack faster allocation/deallocation, complex implementation.
Static chain/link is a pointer to activation record of statically enclosing scope. Display is an array of pointers to activation records.
Functional languages, however, do not use global linkage because they allocate activation records on heap.
Set up as part of call prologue. To retrieve entity n scopes out, need n dereference operations.
O(1) display lookup: one entry per scoping level (known at compile time), plus dereference.
Allowing functions as first-class values forces heap allocation of activation records. Also, environment of function definition must be preserved until the point of call: activation record cannot be reclaimed if it creates functions.
As a result, functional languages require more complex run-time management.
Higher-order functions are the functions that take (other) functions as arguments and/or return functions. (A function that takes/returns pointers to functions can also be considered a higher-order function.)
How they are restricted in different languages:
- C: no nested definitions, so environment is always global.
- C++: ditto, except for nested classes.
- Ada: static checks to reject possible dangling references.
- Modula: pointer to function illegal if function not declared at top-level.
- ML, Haskell: no restrictions. For example, compose function:
fun compose f g x = f (g x)