Lambda the Ultimate

I think you've just deferred the question of what assignment "is" - you haven't really explained the meaning of the assignment operation -- instead, you've done a transformation on the meaning of the number "5" (or something along those lines). You still have an assignment, but now the value on the right hand side is different. This doesn't tell you anything useful about the meaning of assignment itself.

The usual interpretation in functional languages is that assignment is both conceived of and implemented as the binding of a value to a lexical parameter, i.e.

x = 5
... 
body
...

in functional terms is equivalent to the following Scheme:

((lambda (x) ... body ...) 5)

...or in ML:

(fn x => ... body ...) 5

This interpretation comes directly from lambda calculus. It ignores the idea of mutable variables, but you're talking about purity so that question doesn't arise.

[P.S. Real functional languages provide "let" forms which are syntactic sugar for the above.]

I recently ran into the same issue when planning my own simple language (whose implementation will probably never be finished :). In the functional languages I am familiar with, when you do "x = 5" you'll get a symbol 'x' that is bound to the value 5. It's type would be 'Integer'. What you are suggesting would be making 'x' of type '() -> Integer'.

This brings up an interesting issue. It is useful to have a function that takes only '()' as a parameter? In languages with mutable values, the function could modify the global state. In a purely functional language (where the result depends solely on the parameters to a function) this construction seems useless.

One possible reason to use a '()' function would be to delay the execution of a piece of code until it is really needed. On the other hand, if you're using an ahead-of-time compiler, you'd probably want it to be evaluated right away so that there's no run-time hit. However, if the result is an extremely large data structure, you might prefer that it is only constructed at runtime as needed.

Another reason would be to create an infinite sequence (implemented through infinite recursion). With a '()' function, the caller can unroll the sequence bit by bit.

In a lazy language like Haskell, you can create infinite sequences without resorting to using a '()' function. Even if you use infinite recursion to create a sequence, the actual evaluation will only occur as you use the elements in the sequence. I can't think of a reason to use '()' functions in a lazy language.

I think it would be a good decision to make "x = 5" *not* create a function. Like Haskell and ML, you could force the user to say "x () = 5" when he wants to create a function because the extra typing should be reserved for the rare cases. This would also visually match up with the idea that all functions should take exactly one parameter.

Then in a purely (no side-effects) what is the semantics (generally) of something like x = 5?

I know Scheme creates a value of 5 in the heap, and depending on the scope of x, attaches x to the environment with a pointer to the value of 5 in memory.

Maybe I am not getting the entire picture which is why I am having such trouble with this.

When I was trying to understand 'pure functional languages', I had some trouble grokking the statement that 'there is no such thing as assignment,' when clearly, there is some kind of assignment, as with for example (let ((x 5)) ...) in Scheme.

The possibly subtle difference is that in pure functional languages, there is no update. Whereas in imperative languages, it is common to initialize a variable and update it later based on some further logic, in pure functional languages you are forced to find other ways of accomplishing that. Where in C you might write:

  int x = 5;

  if (its_raining) {
    x = 100;
  }

  return 5;

in a pure functional language, you'd have to do the equivalent of:

   int x = its_raining ? 5 : 100;

This "transformation" is straightforward if your variables have just a handful of modifications that don't depend much on each other, but it can be trickier when some complicated logic leads to the successive assignments. A good case is a loop. If you have (assume some variable y):

  int x = 5;
  while (y > 0) {
    x++; y--;
  }
  return x;

There's no cascade of ? : operators that would produce the same result by making a single conditional assignment. Consequently, pure functional languages force you to conceive of this computation in a different way. Recursion is the usual 'way' that people approach a problem like this in a pure functional language, though maybe there are others (higher-order functions might be considered a distinct possibility)

One of the advantages of not being able to make updates is that it's easier to reason about the value of a variable at a certain point in the computation. Without updates, there's only one place in the code where x could get its value (namely the place where it was "let" or as an argument to a function call), so you don't have to consider the combinatorial explosion of different ways that x might have been updated between its first initialization and the spot where you're debugging.

Appealing to the nature of the lambda calculus can be insightful, but I think that a lot can be gained from the experience of programming in a purely-functional style, and searching for purely-functional ways of solving problems.

I don't know if that answers your question, M. J., but I hope it sheds some light on the issue.

The first thing that occurs to me when looking at your example is:

if "x = 5" is equivalent to "x = fn () -> 5", then presumably "x = fn () -> 5" equiv "x = fn () -> (fn () -> 5)", which is equiv to "x = fn () -> (fn () -> (fn -> 5))"... so it's ill-defined.

I'm not being obtuse; presumably you only do the transformation once. If so, then you don't mean "equivalence", since that implies transitivity. But there is a bigger problem. Do you do this for every assignment?

If so, then "x = fn y -> 5" is transformed to "x = fn () -> fn y -> 5", which presumably you don't want.

Or maybe you only do it for RHS expressions which "aren't functions". But if your language is higher-order, you can't detect this in general without doing static type-checking. For example, in "x = f" the f may be bound to a function value or not.

If you are doing static type checking, then something funny is going on because you need to use slightly different type systems to check the program before and after your transformation, that is, you transformation doesn't preserve types "on the nose". Such a thing is possible (indeed, I find it interesting) but I doubt it is what you intend.

...assignment in a functional language is a little like a macro definition.

try thinking of x=5 as
#define x 5

(people will wince at this, but it may help :o)

You are correct Frank, I did not want that. I was merely trying to take some of the complexity out of the language, and decreasing the difference between a variable and a function. I saw both as returning a value, so I though that it would be easier to reason about variables and their implementation if they were created in the same a function would be.

I am modifying minischeme (because its small and readable) to implement this language (not because I care completely about efficiency but I want a lower level understanding of how the internals of some of this stuff works), so I will look at the scheme standard for define, as well as the minischeme code and code from there.

There is a lot of stuff I have to work out in my head, but I am starting to feel that is only going to come once I get a small amount of constructs implemented and start seeing problems.

Regards,

mjs