Re: Which first-course languages? (was: What schools use Eiffel (was: No top schools use Ada)) ?

[dewar@cs.nyu.edu (Robert Dewar)]

Des Kenny in summarizing Miranda misses probably its most important feature,
namely its embracing of lazy evaluation. Full referencetial transparency
is not possible without laze evaluation. Let me try to give a simple
example showing what I mean.

First, lazy evaluation means roughly that all expressions are held as
(if you like) trees, waiting to be evaluated, they are only evaluated when
the program needs the value. For example, in most languages if we write

    func (1 / 0);

we bomb on the call to the function because of trying to divide by zero. In
a LE language, we bomb only if and when the function tries to access the
value of this parameter.

Now consider the following function:

   p2 (a, b) = b

which just references its second argument.

Clearly we can replace p2 (expr1, expr2) by expr2 for any possible
expr1 and expr2, and clearly since these are equivalent, we expect
to be able to replace 

   expr3

by

   p2 (expr4, expr3)

for any expr4, but that simple algebraic approach to understanding what
the function p2 means doesn't work in strict (the opposite of lazy)
languages like Ada, since if expr4 is 1/0, the second call bombs.

The idea in a language with full referencetial transparency is that you can
just do algebra of this type on programs without having to worry about
"premature" evaluation of expressions causing problems.

An extension of this notion allows Miranda to deal with infinite sets in
a convenient form. These are not a happy data structure in strict languages
like Ada, since they would take up rather a lot of room! But in Miranda
you keep the set in symbolic form, generating elements as you need them.

One consequence of the lazy evaluation approach is that you just HAVE to
be fully functional. Since you really don't know exactly when expressions
are evaluated, expressions with wide effects would be impossible to deal
with.

The result is quite an interesting level of semantics. To learn more, take
a look at Haskell which is a more modern expression of these ideas, and
furthermore is non-proprietary. 

The difficulty with any aggressively pure functional language is that,
although you can model anything, you are doing just that in many cases,
modeling, instead of writing things in a direct fashion. I tend to think
that the world comes with state, and that procedural notions with state
(I use the word procedural in a broad meaning, as opposed to functional,
certainly embracing object oriented approaches, including even "pure"
object oriented approaches) are ultimately more natural.

But that's the big argument -- so far functional languages have not lit
a real fire, even though they have been around for a long time. Perhaps
the enthusiasm for object oriented approaches spells their doom, we will
see!

One more point is that it is very hard work to write efficient compilers
for LE semantics. The Miranda compiler uses a combinator based apporoach
for its interpretor, which is neat, but quite slow. The difficulty is that
if you write
     a / b

you would like to generate a divide instruction, but you can't do that
in general, instead you have to construct complex structures