Imperative vs. Functional Programs

	imperative

Taxonomy of Programming Models

Imperative Programming

	View of computation is as sequence of commands or assignments
	(vs. functional: as set of function declarations)
	Most basic operation is the assignment statement:
	Variable = Expression; x = x+1;

No Òreferential transparencyÓ

	In a functional language f(X) * f(X) is same value as Y = f(X), Y*Y
	In an imperative language, we cannot make this claim; f(X) may have Òside-effectsÓ apart from the production of a value.  (In some cases, it could even modify X.

Expressive Power

Expressive Power

	Every imperative program can be expressed as an equivalent functional program
	The general idea:
		The ÒstateÓ of an imperative program consists of a set of bindings of values to variables.
		A statement, or sequence of statements, in an imperative program can be regarded as a transformation of one state to another.
		The transformation represented by a statement can be expressed as a function.

Example: Factorial Program

	int fac(int n) { int x, a; x = 1; a = 1; while( x <= n )   {   a = a*x;   x = x+1;   } return a; }

Expressing Imperative Programs Functionally (1 of 4)

	Think of the program as represented by its flowchart.

Expressing Imperative Programs Functionally (2 of 4)

	Label each arc with the name of a function having the state vector as an argument, except for the input arc, which gets the input variables as an argument, and the output arc, which need not be labeled.

Expressing Imperative Programs Functionally (3 of 4)

	Interpretation of the functions thus introduced:
		Given the argument values as the state, the function produces the value that the program would eventually produce if it were started in that state at the indicated arc.

Expressing Imperative Programs Functionally (4 of 4)

	Define the functions according to the state transformations in boxes.

Simplifying Using Substitution

Try this one

Recursion -> Iteration?

	Is McCarthyÕs transformation invertible?
		In some cases, it is possible to go from recursion to iteration, if the program is tail-recursive.
		In general, it is not possible to transform an arbitrary recursive program to iteration, except in a fairly contrived way:
			We can always implement recursion using imperative programming and a stack
		In some sense, this suggests that recursive programming is strictly more expressively-powerful than iterative programming.

John McCarthy

Funky Faktorial?

Tail Recursion (review)

Tail Recursion

Tail Recursion

Tail Recursion

Which should I use?

	DonÕt lose sleep over whether to tail-recurse, unless
		you are processing large data objects and memory is a premium, or
		it is much costlier to compute without it, or
		itÕs stated on the exam that you should.
	The compiler must also optimize tail-recursion for this to be effective (currently rex doesnÕt).
	In development, it might be wise to provide the clearest expression of the function first, then later replace it with a tail-recursive version.

Na•ve Reverse

	The valid rule set: reverse([ ]) => [ ]; reverse([E | L]) => append(reverse(L), [E]);
	is called na•ve reverse:
		ItÕs the first reverse coded by the inexperienced.
		ItÕs not tail recursive.
		ItÕs slow: takes an extra factor of length(L) steps to evaluate.

Accumulators (review)

	Certain arguments of functions, particularly tail-recursive ones, are often designated as ÒaccumulatorsÓ, e.g.
	The idea is that this argument value ÒaccumulatesÓ until the function is ready to return the answer without recursing.

Accumulators for List Processing

	Consider a definition of reverse: reverse(L) = reverse(L, [ ]); reverse([ ], A) => A; reverse([E | L], A) => reverse(L, [E | A]);
	Which argument is an accumulator?
	Is this reverse tail-recursive?

Accumulators for List Processing

	reverse(L) = reverse(L, [ ]); reverse([ ], A) => A; reverse([E | L], A) => reverse(L, [E | A]);

Accumulators and Auxiliaries

	Note that when an accumulator is used, it is often in an auxiliary function, rather than the main interface function for the user.
	It is bad style to burden the user with the need to know added arguments, such as initial accumulations.