9d80511470b05582fdb13329de734bda_400x400
June 11th, 2015 by john.warden@gmail.com

In my post on Procedures in a Pure Language – Part 1, I discuss how even pure functional languages can be used to create procedures that have effects, and how that is how things should be.

In Procedures in a Pure Language Part 2, I propose a little language where these impure procedures can coexist with pure functions in a way that makes the line between pure and impure very clear.

In this post, I propose adding a stricture to this language that ensures that, while procedures can have effects, they cannot have side-effects.

Here’s a quick review of a simple program in this language.

main = (console) -> procedure
  let greet = console.println("Hello, Bill")
  greet!

println and main are functions which, given a console argument, return procedures, which can be executed with the ! operator. Let’s call such procedures, which are bound to the object on which they operate, methods.

Containing Effects

Now let’s say add this rule to our language: procedures cannot execute other procedures other than methods on objects passed to them as arguments.

So procedures have no ability to directly reference or execute any other procedure: there are no built-in procedures like println, no global objects like Javascript’s window, and no ability to directly import services or objects like Java’s System.out.

Whoever runs the main procedure above can be certain it will have no effects outside of those that can be achieved by invoking methods on console. Since the caller has complete control over these methods, any effects of main are completely contained.

So these procedures can have effects, but since those affects are contained, they cannot have side-effects.

Contained Inconsistency

Along with not having effects, pure functions must be referentially transparent. In other words, they can’t be inconsistent. Let’s say procedures in our language can only be inconsistent as a result of invoking inconsistent operations on the objects that were passed to them as arguments. Their inconsistency is also contained.

“Impure” Inversion of Control

So a program can’t actually do anything unless it is provided with an object on which it can invoke methods. To OO programmers this sounds like dependency injection or inversion of control.

We can use given/inject preprocessing to achieve inversion of control in this language without the syntactic overhead of manual dependency injection.

given console
main = procedure  
  console.println!("Hello, Bill")

Procedures Inside Functions

There is no reason that a function cannot be pure, and still use procedural code in its implementation. For example:


greet = (name) ->
  mutable output = []
  output.push! "Hello, "
  output.push! name
  output.join("")

greet creates a locally-scoped mutable object, output, and manipulates it — thereby producing effects. But those effects are contained to output, which is not returned and therefore disappears when the function returns.

A functions may be implemented using temporary internal stateful computations like this and still be pure if these states cannot affect the caller or the outside world.

Sandboxing

Since any effects of executing procedures are contained to objects passed to those procedures, we can sandbox their effects.

Presumably, when we run the above program in our hypothetical language, the interpreter will by default pass the a real console object that will actually print to standard output. But let’s say we have the ability to create simple mutable objects that look someting like this:

    mutable mockConsole = object
      output: [] # empty list
      println: (message) -> procedure
        output.push!(message)
    

Now we can pass a mock console to main:

    main = (console) -> procedure
      console.println!("Hello, Bob")
    main!(mockConsole)
    mockConsole.output // ["Hello, Bob"]

Since all services that the main function might use to have effects (Network, Filesystem, etc.) must be passed to it, it makes commandline scripts written our language easy to test.

Conclusion

Requiring inversion of control for all dependencies on services that can be used to have effects, gives the caller of the procedure complete control over its effects: effects without side-effects.

Posted in Programming Language Design Tagged with: , ,

Pure
May 31st, 2015 by john.warden@gmail.com

In my last post on Procedures in a Pure Language, I discussed how even a “purely functional” programming language such as Haskell actually allows you to create procedures that have side effects, and how that is the way things should be.

I also defined the following wish list for a programming language where:

  • I can write pure functions.
  • I can also write procedures.
  • I can treat procedures as values.
  • I clearly see in my code when I am defining a procedure and when I am defining a pure function.
  • I clearly see in my code when a procedure is executed.
  • I can write procedures without the syntactic overhead of the IO Monad required in Haskell.
  • I can contain procedures to only operate on specific objects, so that I can limit their effects to a sandbox.

Proposed Solution

Suppose we start with a simple untyped language with an -> operator for defining anonymous functions, and a ++ operator for concatenating strings.

    f = (name) -> "Hello, " ++ name
    f("Bill")

Since this program has no procedures, it doesn’t do anything other than produce the value “Hello, Bill” when evaluated.

Now let’s add procedures:

    main = (console) -> procedure
      console.println!("Hello, Bill")

I have defined a function, main, which takes an argument named console, and returns a procedure.

The body of a procedure is a sequence of imperatives. In this example there is a single imperative, console.println!("Hello, Bill"). A imperative is to an expression what a function is to a procedure: both return values, but imperatives don’t have to be pure functions.

console.println, like main, is a function that returns a procedure. The ! operator says that this procedure should actually be executed, on not just returned, at this point in the code. Otherwise, the result of evaluating main would be a procedure that, when executed, just returns another procedure.

Methods

console.println looks like what you’d call a method in OO. I’m not thinking we’re defining an OO language here, mind you. We could easily have written this as println console, but I like the . syntax here. Either way, println is a function that is somehow attached to the console value — or more specifically console is polymorphic: console itself supplies the definition of println. We don’t need to go into detail of exactly how this works (types? classes? typeclasses?). I’ll just say that functions like println that are attached to objects are called methods.

The “Apply and Execute” Operator

The ! binary operator could be thought of as “apply and execute”, because it applies a function to its arguments, and then execute the procedure that is returned.

You can also apply a function to it’s arguments without executing it:

    let greet = console.println("Hello, Bill")

The ! operator can also be used as a unary, postfix operator, which simply executes a procedure (instead of calling a function and executing the resulting procedure).

    greet!

Operations

Methods like println, that return procedures are called operations.

The ! binary operator is used to invoke an operation by applying arguments to a function and then executing the procedure.

Summary

main = (console) -> procedure
  let greet = console.println("Hello, Bill")
  greet!
  console.println!("Hello, Bill") // another way of doing the above.

So main is a pure function that returns a procedure. println is an operation — a method that returns a procedure. println, like all methods, is also a pure function, because simply applying it has no side effects.

greet is a procedure, the result of applying println to its arguments in the expression console.println("Hello, Bill").

greet!, because of the presence of the ! operator, is an imperative.

console.println!("Hello, Bill") is likewise an imperative.

Summary of Definitions

  • Function: takes arguments, never has effects.
  • Procedure: takes no arguments, has effects when executed.
  • Method: functions attached to objects (enabling polymorphism).
  • Operation: method that produces a procedure.
  • Expression: has no effects, consistent.
  • Imperative: may have effects or be inconsistent.

Conclusion

We have defined a language that, like Haskell, allows us to define pure functions, which themselves can produce procedures that can be executed. The body of any function containing imperatives that execute procedures must be a procedure, just as in Haskell any function that uses a bind operation or do on an IO something must itself return an IO something. But our language has first-class procedures instead of the IO monad, and the ! operator instead of do or any of the bind operators.

Also just as in Haskell, “evaluating” the program has no side-effects. It just produces a procedure which you can then execute.

Our language doesn’t treat procedures as Monadic value as does Haskell. After a program is evaluated there is no need for something that can be bound, fmaped over, or stuck in a do block, since all that you will ever do with this procedure is execute it.

Also by treating procedures differently from monadic values, it is even easier to see exactly when you are invoking procedures. This will be helpful to a programmer striving to minimize unnecessary use of impure code.

Posted in Programming Language Design Tagged with: , , , ,

Pure
May 28th, 2015 by john.warden@gmail.com

The fact that you can write procedures, which produce side-effects, in Haskell, which is supposed to be a pure language, can be confusing.

I think the key to clearing up the confusion is to understand that most Haskell programs are actually programs that produce programs — like preprocessors in CPP. Conal Elliott’s post The C language is purely functional explores this idea.

The Haskell language itself is pure. When evaluated, Haskell expressions have no side effects, and are referentially transparent.

But the value returned by main in many Haskell programs is an IO something — which is a procedure that can be executed and may have side effects.

If the GHC didn’t have the built-in ability to take an IO something and compile it into an executable procedure, then a Haskell program could evaluate expressions all day long, but the resulting values would just disappear into the ether because the program could never output the results to STDOUT, because that is a side-effect.

Haskell has advantages over impure languages not because it removes the ability to write impure procedures, but because it adds the ability to write pure functions, guaranteed to have no side effects and to be referentially transparent. The majority of many programs can and should be written with pure functions, which are easier to maintain, understand, and debug. Often you only need impure procedures for a small part of the program, perhaps only the parts that actually writes output to STDOUT or a database.

Unfortunately, when you need to write impure-procedures in Haskell, there is a great deal of syntactic overhead that I don’t think has to be necessary.

The benefits of Haskell’s IO to me are are:

  • I can write pure functions.
  • I can also write procedures.
  • I can treat procedures as values.
  • I clearly see in my code when I am defining a procedure and when I am defining a pure function.
  • I clearly see in my code when a procedure is executed.

I’d like to see a language with those benefits, but with additional benefits:

  • I can write procedures without the syntactic overhead of the IO Monad required in Haskell.
  • I can contain procedures to only operate on specific objects, so that I can limit their effects to a sandbox.

I think such a language is possible. Anyone want to help me create it it?

Posted in Programming Language Design Tagged with: , , ,

currypufffold003
May 25th, 2015 by john.warden@gmail.com

Implicit currying and folded application are language feature that render moot the distinction between curried and un-curried functions, allowing functions written in curried style to be called as un-curried functions and vice-versa.

Quick Background: Currying

Currying is the technique of translating a function that takes multiple arguments, or a tuple of arguments (an n-ary function) into a sequence of functions, each with a single argument. For example:

// binary function (uncurried form)
let product = (x,y) -> x*y

// curried form of same function
let product = x -> y -> x*y

The curried form of the function has to be invoked differently than the uncurried form:

(product 2) 4
// which, given left-associativity, is the same as
product 2 4

Instead of

product(2,4)

Partial Application vs Implicit Currying

Partial application is the ability to pass only the first argument to a function taking two or more arguments, and get back a function taking the remainder of the arguments. So you can write your function as an n-ary function, but call it as if it were curried.

Partial application is non-applicable in a language, like Haskell, where n-ary functions are not supported. Functions with multiple arguments have to be defined in curried form.

The advantages to languages like Haskell, where all functions take only a single argument, have been thoroughly explored elsewhere. But these advantages would not be lost in a language that allowed functions to be defined as if they were n-ary. It could be left to the compiler or interpreter to translate them automatically to curried form. So:

let product = (x,y) -> x*y

is syntactically equivalent to:

let product = x -> y -> x*y

This is different from partial application, in that n-ary functions still don’t exist. You still can’t pass multiple arguments to functions.

// won't work
product(x,y)

You have to pass arguments one at a time as you do in Haskell:

product x y

Folded Application

So now we have a language where all functions take a single argument, and multiple-argument functions are either explicitly or implicitly re-written in curried form. Now let’s also say that, as a syntactic convenience, we allowed curried function to be invoked as if they actually allowed multiple arguments. So:

 product(2,4)
 // is the same as
 (product 2) 4

I call this folded application, because it involves implicitly doing a fold (or reduce) operation on the invisible apply operator, applying the function to the first argument, then applying the result to the second argument, and so on. So:

product(2,4)
// is implicitly translated to
reduce apply [product,2,4]

Curried/Uncurried Equivalence

There are languages, like Haskell, where all functions take just one argument (which has advantages), and other languages where functions can take multiple arguments (which also has advantages).

Implicit currying + folded application together allows you to mix paradigms. If you want to think of your functions as always taking single arguments, as in Haskell, you can, regardless of how the function is defined. If you prefer to think of the same functions as taking a list of arguments, you can. The distinction between a curried functions and it’s equivalent n-ary function becomes moot. So if you define:

let product1 = x -> y -> x*y
let product2 = (x,y) -> x*y

Then all of the following are equivalent:

(product1 2) 4
(product2 2) 4
product1(2,4)
product2(2,4)

Difference from Partial Application

A language that allows n-ary functions and partial applications doesn’t quite give you curried/un-curried equivalence. It allows n-ary functions to be invoked as if they were curried. But it does not allow curried functions to be invoked as if they were n-ary. This asymmetry requires programmers to make a choice when defining their functions, and once the choice is made their options for using the function is limited. Curried/un-curried equivalence eliminates this dilemma.

Conclusion

Should languages mix paradigms? I could understand if your instinct is that you should choose a paradigm and stick with it. On the other hand, I think that there are times when both paradigms are useful. The n-ary function paradigm can be a more familiar and intuitive for some software developers, and for certain problems. Indeed I think it is more natural to think of a product as a function that takes two arguments, not as a function that returns a function. On the other hand, there is great power in a language where, at a fundamental mathematical level underneath the syntactic sugar, all functions ultimately take a single argument. A language that allows both paradigms offers the best of both worlds.

Posted in Programming Language Design Tagged with: , , , , , ,

Aristotle
May 16th, 2015 by john.warden@gmail.com

Functional Equality

or

Everything is the Same, Everything is Different

or

When 2+2 is not 4

In this post, I’ll argue the merits of a functional programming language where the equality operator respects the principle of functional equality.

This principles states that, if a and b are equal, then there should exist no function f for which f(a) != f(b).

Many, if not most, FP languages violate this principle.

Same Length, Different Measurement

The international inch is defined as precisely 2.54 centimeters. So 2.54cm = 1in.

Suppose we have a Measurement class in some OO language, with a constructor that takes a magnitude and a unit, like so:

length1 = measurement(2.54, "cm")
length2 = measurement(1, "in")

Does length1 == length2?

You could say that they are equal by the very definition of international centimeters.

But toString(length1) is “2.54 cm”, and toString(length2) is “1 in”. This means toString(length1) != toString(length2), and therefore length1 and length2 are different. So then how can they be equal?

What do You Mean by “Equal?”

My answer is that length1 and length2 are the same, and they are also different.

They are the same in that they represent the same physical distance. But they are different in that they are expressed in different units.

Does 2+2 = 4?

The answer to this quintessentially trivial question really depends on what do you mean by equal!?

Let’s say I define a and b in a Haskell program like so:

let a = 2+2
let b = 4.0

Does a equal b? If the question is whether they are equal points on the number line, then the answer is yes. But in other ways, 2+2 obviously is not the same as 4.0. They even look different. One expression has a little + in it, the other has a decimal point. One is an int, the other is a float.

But do these differences matter?

I propose that, when defining equality, what matters to programmers is whether two values are interchangeable. If a is really equal to b, you should be able to replace a with b anywhere in your code and nothing in your output would change at all. In other words, this statement should never be true:

(a == b) && (f(a) != f(b))

This concept is related to the FP concept of referential transparency: an expression is referentially transparent if it can be replaced with its value without changing the behavior of the program.

But shouldn’t we also expect that any value can be replaced with an equal value without changing the behavior of the program?

For an FP language to really respect the spirit of referential transparency, it should respect functional equality.

It’s Easy to Get Equality Wrong

The strict requirements of functional equality can be easily broken. In the Haskell case, this expression is true:

(a == b) && (show(a) != show(b))

Because show(a) will be “4”, and show(b) will be “4.0”. So the two values are not functionally equal.

Violating Functional Equality Creates Problems

The user of your class my assume that two objects that are equal behave in the same way and are therefore totally interchangeable, when they are in fact not.

Suppose a developer writes a program that plots data on charts, placing labels with the numeric value next to each point.

She may be encounter a situation where the same chart sometimes includes a decimal point in the labels, and sometimes doesn’t. She is perplexed when she discovers that equal inputs produce different outputs, which her intuition says should not be possible in a functional programming lgnguage. Only after spending considerable time debugging does she realize that the inputs, while passing the == test, are actually different, because one contains floats and the other contains integers. She’ll then realize that she needs to rethink her definition of “equality”.

Equality Across Types

So 2+2 == 4.0 should evaluate to false?

That would be a problem as well. It would certainly be non-intuitive for many programmers, and could easily lead to very frustrating debugging sessions.

But I would say that, if you want a language where ints and floats act differently, then they should not even be comparable. The programmer should be required to explicitly convert them into a common type before comparing. The expression 2+2 == 4.0 should produce a compile-time error. You should be required to write something like (float) 2+2 == 4.0, making it very clear what you mean by “equal”.

I would also argue that different types for ints and floats may not be necessary in modern languages — and indeed most dynamic languages these days make no distinction.

Summary

The functional equality principle allows a and b to pass the equality test only if it is never true that f(a) != f(b) for any f.

With a language that enforces functional equality, programmers will still sometimes fail to really think through what they mean by “equality”, and be surprised when two values they expect to be equal are not. But I think this is okay — it will force programers to more concretely understand and define what exactly they mean by equality, and to write more clear and correct code.

Posted in Programming Language Design Tagged with: , ,

functional purity
July 3rd, 2013 by john.warden@gmail.com

In this post, I’ll try to classify the goals of functional purity for the benefit of those who already believe in it, hopefully providing a useful structure for conversations around language design and best practices.

Many coders feel the critical importance of pure functions to the very marrow of our bones. And yet we struggle when trying to construct arguments to convince the “non-believers”. Converts to functional purity tend to come to it through their own experience, not through logic. It is a belief akin to a religious value, or probably more so to a moral value. It is arrived at not so much through a reproducible process of deduction, but through the aggregate subconscious processing of countless experiences (largely debugging sessions) that emerge in an intuitive knowing that is as certain as a logical proof.

We may offer examples where values being modified when the programmer doesn’t expect it will cause bugs and make someone’s life harder. Or we speak in abstractions, about complexity and the the ability to reason about our programs. We might even point to studies. But many coders are so used to mutability and side-effects that complaining about them is like complaining about gravity.

The moral authority of functional purists is weakened in the eyes of non-believers when we make apparent compromises. We use monads and do blocks that appear to let us create side-effects while allowing us to say we aren’t. Our code becomes incomprehensible for the less mathematically inclined. Monads proliferate, IO becomes part of the type signature of every function, do blocks are everywhere, and we further alienate the uninitiated with an attitude that suggests this is all a virtue, as if repeatedly acknowledging their presence were penitence for the sin of using functions that just look like they produce side effects. We spread hundreds of “IO”s throughout our code like hundreds of Hail Mary’s.

Below I’ll try to catalog and articulate the reasons many people do believe in functional purity, not necessarily to convince the “non-believers”, but to help “believers” put a microscope to exactly what we are trying to accomplish, and to question how well we are achieving it.

1. Containment

There’s a big difference between a Haskell function that could possibly perform a problematic IO operation, and a Java method that could do anything.

The “effects” of functions that return IO monads are contained to a limited, well-defined set of IO operations. They can’t modify any values or variables in memory. They can’t launch new threads or terminate the process or modify global variables. Their effects are contained.

A Java method, on the other hand, is totally un-contained. It could do anything. Subtle, insidious little things that create infuriating irreproducible errors. Even if you trust the guy who wrote the Java method, you know that accidents happen. Lack of containment is risky. Containment ensured by the language is better.

2. Control

Very similar to containment, but one step beyond, is control. A function that returns an IO monad doesn’t actually do anything — it just returns some IO operations that will be performed when bound to Main.main.  They won’t be performed at all if you don’t do this binding. You have control.

As another example, if you have a function that does some stateful operation with a State monad, not only are you sure that effects are contained to the output of that function, but you have complete control over the start and end state. You can pass in mock states, say for testing, and you can examine, modify, or reject the end state.

Or, if a function uses Writer for logging, the caller has complete control of what to do with those logs. It can ignore them, modify them, or just pass them on up the call stack.

This is a sort of inversion of control, where a function may perform pseudo-side-effects, but the caller controls exactly if and how these side-effects occur.

3. Clarity

Finally, clarity. This is what we mean when we talk about being able to reason about our code. There’s nothing going on that we can’t see right in the editor. You can point and say “there, all the effects of that function are held in that value there”, there’s no trying to remember if this function modifies that value or writes to some database, or if it depends on when exactly you run it or what environment variables you’ve set. Even pseudo-side effecting code with IO and State and Logging — they are still just functions that return values, and we can see those values being returned and the flow of those state changes. Once you know how to read and write code like this, code is clearer and vast classes of bugs are preempted.

Applying the 3 C’s

These three goals capture all the reasons for pure functions that I can think of at the moment (but please comment if I’ve missed some).  And I think these three ‘C’s can provide a good framework when thinking about language design and best practices.

Sandboxes

It’s interesting to see how these same goals can be met by other means.  For example, containment can be achieved using “sandboxes”.  Sandboxes are why we allow our web browsers to run un-trusted Javascript code.  It produces side effects, but they are contained.

Implicit Parameters

Some see implicit parameters in Scala as dangerous. But where does the danger lie? Containment, Control, or Clarity?

Implicit parameters are contained. They can’t cause side effects, and there is a limited, well-defined mechanism for passing them to functions.

I believe there is no sacrifice to control: as the caller you can override them, control what functions they are passed to or not passed to, and make them explicit when you want to.

The danger lies, I believe, in clarity: it may not be clear that this invisible parameter is being passed around, and this could cause frustrating bugs. An argument can be made that nothing should happen in your code implicitly.

But knowing that the danger lies in clarity, not containment and control, we can focus our discussion on striking a balance between two aspects of clarity: the danger of values getting passed around that are not clearly visible in the code, and the benefits of reduction in code noise.

Posted in Programming Language Design Tagged with: ,