... end slide from previous class If we didn't have subrout8ines, we couldn't do recursion, since recursion is a subroutine calling itself. Every recursive call has its own copy of function variables and they don't interfere with one another.
Tail Call Optimization
A function is in tail position if the funciton call is the LAST thing it does. They can be optimized so that recusion doesn't really need to be done. “A function call of some function f is in tail position if it is the last call the caller makes and the return value of f is the caller's return value.”
sum xs = loop 0 xs where loop total [] = total loop total (x:xs) = loop (total + x) xs
when sum calls loop: loop can overwrite sum's stack frame loop can reuse sum's return address loop still needs to initialize its stack frame when loop calls itself recursively: recursive call uses same stack frame as caller no initialization of the stack fram is needed function arguments are updated like loop variables.
Inline Expansion
During compile time, the compiler replaces a subroutine call with the code of the subroutine.
f(){ x=1; x=add1(x); //inline expansion, this line becomes x = x+1 }
add1(x){ return x + 1; //creating a stack frame for this is more expensive than putting it inline }
advantages: avoids overhead associated with subroutine calls; faster code encourages building abstractions in the form of many small subroutines related to but cleaner than macros disadvantages: code bloating cannot be used for recursive subroutines code profiling becomes more difficult.
Parameter Passing
Notation:
f(a, b, c) #C, C++, Java... (f a b c) #lisp, scheme a f: b fcont: c #smalltalk, objective C f a b c # haskell, shel scripts
Def: execute the named subroutine with its formal arguments bound to the provided actual arguments. How exactly? Call by value call by reference call by sharing call by value/return copies the whole value into a separate function, and if the function crashes, the caller still has the original value. If the function succeeds, it replaces the value
Index