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: , ,