Var-free programming

[address@hidden]

   Those interested in programming without variables may
   wish to read John Backus' 1977 ACM Turing Award Lecture:

   Backus, John.
   "Can Programming Be Liberated from the von Neumann
   Style?  A Functional Style and Its Algebra of Programs."
   Communications of the ACM 21, 8 (August 1978), 613-641.

This is a very influential and important paper, in my opinion. Really
makes the case for functional programming. Backus, among other things,
is considered the father of Fortran, so it's not like he's an FP partisan.

I will also add that it's a theorem that any generic, with-vars program
can be converted into a variable-free version using a functional representation
called "combinators" (of which Backus's "fp" language has many).

One way to describe why names are nice and so fundamental to so many notations
is that names give you a way to access things multiple times. That is, if you
only wanted to use the value of (x+3) once -- say, you wanted to take the sine
of it -- you could just write it the one place you wanted to use it: sin(x+3).
(I'm going to ignore side-effects for the moment, to keep things simple.) But
if I want to use x+3 a *couple* of places, then I better bind the value to
y, and drop y's in all the places where I want the value.

This is very handy, of course. Note that Alan Bawden wrote a not-widely-known
gem of a dissertation at MIT in which he says that the *problem* with names
is the thing that's good about them -- this multiple-reference property. For
contexts where the cost of reference is very high, names are painful to
manage. There is such a real-world case: distributed network services. If
I have can bind to a name a resource that lives somewhere else on the net,
then, in order to know when that resource is no longer needed, I have to
do distributed garbage collection, a very painful and complicated and
inefficient thing to do. So Alan proposes one of these pointy-headed-theorists
kind of language formalisms, "linear type systems," that gives you a handle
on references by nameing. His thesis, then, is that linear type systems are
not just for effete, weedy type theorists -- they are for network-protocol
designers. It's just that the NPD's don't know it.

So Alan builds distributed systems using a language that back-ends out to
a "linear language" back end. That's his diss (or most of it), from 50,000
feet. The subtitle of his diss is "Confronting the cost of naming."

An interesting read. If you are interested, look here:
    ftp://ftp.ai.mit.edu/people/alan/

    -Olin