Where Pure Meets Impure

Lazy evaluation within Toyl functions is great, because Toyl will be built to expect it.  However, any time we interact with a library written in a standard imperative language, or with the standard .NET architecture, we will need to know how to correctly cross the gap between the Toyl world and the real world.

There are three sides to this:  First, from a practical perspective, we won't be able to pass ISignature<T> objects into standard .NET methods that expect T objects, so we'll have to evaluate any value before we pass it into a standard method.

Trickier, though, is the question of side-effects.  I will eventually implement some functionality that allows a thunk (a parameterless closure) to remember its evaluated value, which should not change for pure functions.  However, if a method has side-effects in the world, we might need to call it again, rather than remembering the result we obtained from calling it previously.  Likewise, if a method draws information from the world, we might need to call it again to get updated information.

One example of the former type of method is Console.WriteLine, which writes a line to the console.  If we lazily refuse to evaluate it a second time with a particular string, then we will be unable to ever print the same string to the console twice in the same session!

An example of the latter type of method is Console.ReadLine, which reads a line from the console.  This takes no parameters, so our aggressively lazy system would by default assume that anything the user typed at the console was the same thing that the user previously typed.

There are several ways to skin this cat.  The simplest approach would be to treat all external methods as being impure until they have been declared pure within Toyl somewhere.  I would then implement a rule that says: "Any Toyl function that relies on an impure function is itself impure."

Another approach, which would be interesting from a theoretical perspective, would be to treat impure functions the same as pure functions, but pass in something that represents the changing external universe.  No two values of the Universe parameter would be equal, so no two function calls would be considered to operate on the same inputs.  So, we would have Console.ReadLine(Universe) and Console.WriteLine(Universe).  The Universe value would not be globally available--it would have to be passed in to any function that needs it--so any Toyl function that needs it needs to take it as a parameter itself.

That's kind of a tidy solution, because it makes it explicit in the code which functions are pure and which are impure.  However, neither this solution nor the assignment of purity to functions mandates a particular order of evaluation, which can be important when there are side-effects involved.  This is a serious question, since I previously said that I was going to implement aggressive laziness by allowing the system to decide which order to evaluate expressions in.

As an example of the type of issue I am talking about, consider a program that needs to ask a user a question using Console.WriteLine(), then get the user's response using Console.ReadLine().  All things being equal, there is nothing that says the question needs to be evaluated before the response is retrieved, but really it needs to happen in that order.

Continuing the Universe model, what we might want could be something like this:

(Universe, string) PromptUser(Universe U0, string question) {
  Universe U1 = Console.WriteLine(U0, question);
  (Universe U2, string answer) = Console.ReadLine(U1);
  return (U2, answer);
}
Fig. 7.1: Universes in, and universes out

In this case, since we change the universe by asking the question, we want to pass that changed universe into the Console.ReadLine().  There is only one order that this expression can be evaluated in, and that is to ask the question first, then get the answer.

The difficulty here is that our Console.ReadLine() itself should really return two values--it should return the line read from the console, as well as the new universe.  We can handle that in a number of ways, but for now, in pseudo-code, I'll just write two outputs to the left of the assignment operator.

But hopefully we will not need C#-like pseudocode much longer.  In my next post, I'll start talking about what Toyl will look like, and we can start using Toyl code instead.