Of what use is 'lambda'???

oleg at pobox.com oleg at pobox.com
Thu Sep 28 00:51:41 CEST 2000


Referential transparency is usually defined as substitutability.
Suppose we have a function foo(x) and we want to compute the value of
an expression

	foo(5) + foo(5)
We can either (i) invoke foo with an argument 5 twice and add the
return values, or (ii) invoke foo with an argument 5 once and double
the return value. If both ways _always_ give the same result -- and
the program behaves the same way (e.g., makes the same modifications
to the file systems, printed pieces of paper, etc) no matter which
strategy (i) or (ii) we choose -- we have referential transparency. If
function foo(x) is defined as

	foo(x): if x == 0 then 1 else sin(x)/x
then indeed both ways, (i) and (ii) of evaluating foo(5)+foo(5), give
the same answer -- and result in the same program behavior. However,
consider foo1(x) defined as
	foo1(x): print x; return x + 1

Now it does matter how we evaluate foo1(5)+foo1(5). If we invoke foo
twice, we'll see two fives printed. If we invoke foo1(5) once and
double its result, we'll see only one '5' printed. The behavior of the
program is obviously different. Thus foo1(x) is _not_ referentially
transparent. Note how lack of transparency inhibits compiler
optimizations.

We can re-write foo1(x) as follows:

	foo2(x,out_port): return (x + 1, print(x,out_port))

foo2() takes two arguments -- a number and an output port -- and
returns two arguments: a new number and a new output
port. Furthermore, the output port argument is assumed "consumed".
Function print() takes a number and a port and returns a new port
"with the number printed". foo2() is now again a referentially
transparent function. We can use it as follows:

	let x1,port1 = foo2(x,port)
	 in let x2,port2 = foo2(x,port1)
	    in (x1+x2, port2)

This example shows how to handle interactions with the real world and
remain referentially transparent. An excellent paper

	Philip Wadler "How to Declare an Imperative" (ACM Computing
	Surveys, 1997, v. 29, N3, pp. 240-263).

shows other ways. Section 4, "Dispelling Myths about Functional
Programming" of another excellent paper
	Paul Hudak "Conception, Evolution, and Application of
	Functional Programming Languages" (ACM Computing
	Surveys, 1989, v. 21, N3, pp. 359-411).

demonstrates how similar imperative and functional programming
actually are. Either lets us express computations that mutate a global
state (including i/o).  The apparent difference is that in imperative
programming, the mutable state is "implicit": stored in global
variables. OTH, in functional programming we pass this state
explicitly to all the functions that need it. However, monadic
programming blurs even that distinction between the two styles.


Sent via Deja.com http://www.deja.com/
Before you buy.



More information about the Python-list mailing list