[Prev][Next][Index][Thread]

Re: Why Prolog and CBV?

Date: Fri, 22 Nov 91 23:07:09 -0600
To: jcm@cs.stanford.edu

In writing programs, I would like to think about the values
expressions denote and not so much the precise order in which every
step of evaluation happens.  Trying to do the latter can get quite
mind-boggling.  At those times when I am forced to think about the
precise evaluation order, call-by-value gives me a nice tree
structure: (dn for "reduces to")

	e1 dn \x.e1'    e2 dn v2    e1'[v2/x] dn v
	------------------------------------------
			e1 e2  dn v

The structure of the evaluation does not detract from the focus on
values: e1 is evaluated, e2 is evaluated and e1's value is applied to
e2's value.

In contrast, call-by-name does not have such a structure:

	e1 dn \x.e1'    e1'[e2/x] dn v
	------------------------------
		e1 e2  dn v

The evaluation of e2 is hopelessly intermixed with function
application.  (This is perhaps what Purush referred to as the
"noncompositionality" of the application rule).  As a result, the
evaluation order is highly unpredictable even if it is deterministic.
In a large program, e1' and e2 may appear hundreds of pages apart, in
different modules, at totally different levels of abstraction.  Trying
to track the interferences between the two would be hopeless and
dangerous.  I doubt if anybody who seriously programs in call-by-name
(or call-by-need) languages routinely thinks about the evaluation
order.  Rather, one thinks about e2's value, even if it is infinite,
and checks if e1 uses a finite portion of e2's value.  This would not
be possible if the expressions had side effects.

Bob Harper made the point that Forsythe uses call-by-name and yet is
imperative.  But, the difference between Forsythe and ML is that
Forsythe does not have side effects.  (By side effects, I mean not
having any syntactic/type distinctions between terms which denote
values and terms which change the state).  Forsythe's expressions
denote (state-dependent) values and its commands change the state.
Further, the order of execution of commands is deterministic and
predictable (in fact, sequential).  Hence, Forsythe is usable.  If
what looks like an expression is actually a state-changing term and
the order of evaluation is unpredictable, life would be quite hard
indeed.

Uday Reddy