Having trouble with 'purity'

I am having trouble wrapping my mind around the semantics of a pure functional programming language. In writing my current programming language I chose to treat the variable assignment expression:

x = 5

as the creation of a function named x.

x = 5 is semantically equivalent to:

x = fn () -> 5

Is this sort of 'variable assignment' considered to be an example of pure in the FP sense?

NOTE: if x (in the above example) were to be redefined, a new closure would be created with the associated value.

Sorry to ask such a trivial question, but I am having trouble finding semantic discussions concerning simple functional programming idioms.

Best regards,

M.J. Stahl

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Deferring the question

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
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.]

Depends on your evaluation model.

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.

Ok, then how.

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.

Correct, it's just a value.

That is correct. The type of the value is "Integer".

Whether or not it's on the heap is an implementation issue. There are some optimizations you can perform so that each and every number doesn't have to be malloc-ed. Semantically, however, it works just like "x" is a pointer to a heap cell with the value "5" in it.

If you're going to need dynamic type information (like Scheme does), then you'll also have to store a little bit of information along with the heap value.

Also, there's the issue of whether you're going to use a runtime symbol table for all your variables or if you're going to resolve all that at compile time. I get the feeling that you're writing an interpreter and so the easiest way for you would be to use a symbol table.

Just look at the lambda calculus

Here's the grammar of lambda terms -- we have variable references (described with an "x"), applications, and functions. Values (marked "v") are just functions.
e ::= x | (e1 e2) | (fun (x) e)

v ::= (fun (x) e)
Here are the one-step-at-a-time evaluation rules:
(e1 e2) --> (e1' e2) IF e1 --> e1'

(v e2)  --> (v e2')  IF e2 --> e2'

(fun (x) e) v --> e[v/x]
The first two rules say that you should first reduce a function and its argument to values, and the last rule defines application. The notation "e[v/x]" means "substitute v for x in e". It's defined as follows:
  CASE: e == y 
      IF y = x THEN v 
               ELSE y
  CASE: e == (e1 e2) 
      (e1[v/x] e2[v/x])
  CASE: e == (fun (y) e)
      IF y = x THEN (fun (y) e)       (* The function argument shadows x here *)
               ELSE (fun (y) e[v/x])

I bet you find all of this straightforward. (If you don't, try implementing it in Scheme or ML.)

You'll notice that the most unrealistic part of this implementation is that to actually apply a function, you have to physically substitute the argument in the function's body. That's a very expensive tree construction operation. All an environment is, is a memo table that lets you do the substitution lazily. You remember what each variable is bound to, so that when you run across a variable reference, you can just look it up in the environment.

'Pure functional' is 'no update'

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.

if you know c...

...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)

RE: Ill-defined?

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.



The essence of pure functional programming

Since you expressed interest in purity, it's worth pointing out that minischeme is impure, e.g. it supports the set! form. That has a big impact on the implementation. Among other things, it means that values can have identities independent of their value - in Scheme, the pair (1 . 2) isn't eq? or eqv? to all other pairs with the value (1 . 2). In Haskell, all such pairs are considered equivalent, and you don't need three different equality operations to keep them all straight.

I saw both [variables and functions] 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.

The pure functional approach is this:

  • Variables are names for values.
  • Functions are values.
  • Functions can take parameters, which are names for values.
  • Therefore, parameters are variables.
  • And by the way, we don't really need any other kind of variables, other than parameters. Everything else can be faked with syntactic sugar (see earlier post).

Pure functional programming allows for implementation techniques that you can't really get away with otherwise, such as graph reduction. The first few sections of Chapter 2 of Implementing functional languages: a tutorial give an overview of this technique with some simple examples.