Category: Programming Language Design

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

return value code graphic
June 19th, 2014 by john.warden@gmail.com

The pass-through list is a programming-language feature intended to makes it easier for programmers to modify functions to return additional values without breaking backwards compatibility, in the same way it is easy to modify functions to take additional parameters without breaking backwards compatibility. This is done by, in a sense, unifying the semantics of passing parameters to functions and returning values from functions.

Problem

Suppose I have an inverse function that takes one number and returns one number, in some hypothetical untyped language:

let inverse(x) = 1/x
2*inverse(4)

I cannot change this function to return a second value, without breaking existing code:

// return a list with a number and a string
let inverse(x) = (1/x, "the inverse of " ++ x) 

// Doesn't work any more!  inverse(4) returns a list, not a number.
2*inverse(4) 

On the other hand, I can easily modify the function to take an optional second parameter:

let inverse(x, verbose=false) = // 'verbose' is an optional parameter
  if(verbose) println("Calculating the inverse of " ++ x)
  1/x // return 1/x

And code that depended on the old version of the function still works with the new:

2*inverse(4) // Still works!

Solution

1. Functions Always Return Lists

In most languages, functions accept lists of arguments, but typically return single values. But if functions always returned lists, we wouldn’t have this problem.

This unfortunately would require a lot of extra code for extracting values from lists. But we could reduce that burden with a little syntactic sugar: allowing calling code to accept the values returned by a function using a deconstructing assignment:

// function that returns a list containing one number
let inverse(x) = (1/x) 

// deconstructing assignment assigns the first element of the return list to y
let (y) = inverse(4)     
2*y

Now we can modify a function to return multiple values, but the caller can choose to ignore extra values:

let inverse(x) = (1/x, "the inverse of " ++ x)

// ignore the second return value
let (y) = inverse(4)  

// or use it if we want
let (z, explanation) = inverse(4) 

2. Implicit Deconstruction

But this doesn’t completely solve the problem: we still have to use a deconstructing assignment to receive the values returned by every function call, so simple code such as 2*inverse(4) needs to be rewritten as:

let (result) = inverse(4)
2*result

But this can be solved with an implicit deconstruction rule: if a list returned by a function is not explicitly deconstructed with a deconstructing assignment, then it is implicitly deconstructed, with all but the first value being ignored.

So inverse can now return a second value, but we can still call it as if it returned just one:

// return a list with a number and a string
let inverse(x) = (1/x, "the inverse of " ++ x) 

2*inverse(4) // implicit deconstruction -- just use the first return value

And now we have a language where it is easy to modify a function to return additional values, without breaking backwards compatibility.

3. Implicit Construction

Now, it’s a little inconvenient for our language to force every function to explicitly return a list.

But we can solve this problem with an implicit construction rule, and say that a list is implicitly created in places where it is expected. So:

let inverse(x) = 1/x

Is syntactically equivalent to:

let inverse(x) = (1/x)

In other words, the parentheses around return lists are implicit. You only need to explicitly include them when returning more than one value.

4. Implicit Construction in Function Calls

Let’s say that, in our language, functions expect lists of arguments. The implicit construction rule says that, if you don’t explicitly construct a list where they are expected, one is implicitly constructed. So:

inverse 4
// must be the same as
inverse(4)

Implicit construction can be looked at just an optional parentheses rule.

5. Implicit Deconstruction in Function Definitions

Functions in our language always accept and return a list of values. Now in many functional languages, functions always accept and return a single value. Let’s say that in our language, both of these are true: functions always accept and return a single value — a list — and in cases where that list only contains 1 item, implicit construction/de-construction simplifies the syntax by allowing you to construct and deconstruct the list implicitly, without parentheses.

Let’s say our language supports the -> operator for defining anonymous functions.

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

Now, we said that functions only take a single argument, but it looks like product is taking two. But let’s say that this is just syntactic sugar for deconstructing the function arguments to a function, that lowers to:

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

6. Pass-Through Lists are Not Regular Lists

Implicit construction/deconstruction means that these lists cannot be referenced, making them into a kind ephemeral type, whose lifespan is mainly limited to passing values to or returning values from functions. I’ll call them Pass-Through Lists — reflecting their use for “passing values through” to/from functions, and the idea that implicit deconstruction allows values to “pass through” the parentheses as if they weren’t there.

Pass-through lists could possibly be used as a convenient notation for assigning a list of variables to a list of values like so:

let(firstName, lastName) = ("Albert", "Einstein");

Nesting pass-through lists would also be pointless, given consistent application of the implicit deconstruction rule:

let a = ((1,2),(3,4)) 
// given implicit deconstruction produces the same result as
let a = (1,2)
// which produces the same result as
let a = 1

Pass-Through Lists and Parentheses

The implicit deconstruction rule makes the use of parentheses to construct pass-through lists consistent with the use of parentheses for grouping to override default operator precedence and associativity rules. For example, in the expression a*(b+c), we use parentheses to override the default arithmetic operator precedence. We can look at this as actually creating a single-item pass-through list containing the value of b+c, which is then extracted with an implicit deconstruction and multiplied by a.

Pass-Through Lists and Regular Lists

Since pass-through lists can’t be referenced, our language probably needs an additional list type, perhaps constructed using the [] operator.

let fruit = ["applies","oranges","cherries"]

Synopsis of Pass-Through List Rules

Pass-through lists are created by placing one or more comma-separated values in parentheses. All functions take a single pass-through list as their argument, and return a single pass-through list.

The values of pass-through lists can be accessed via deconstructing assignments, for example:

let (a,b) = ("a","b")

If a pass-through list contains more values than are listed on the left-hand side of the deconstructing assignment, extra values are ignored.

let (a) = ("a","b")

Implicit Construction

Pass-through lists are implicitly constructed — in other words, parentheses are assumed — in any context where a pass-through list is expected, including…

…when passing arguments to functions, so:

f x
// is the same as
f(x)

…when returning values from functions, so:

let inverse(x) = 1/x
// is the same as
let inverse(x) = (1/x)

…and in any deconstructing assignments, so:

let(x) = 5 
// is the same as
let(x) = (5)

Implicit Deconstruction

Implicit deconstruction happens wherever a pass-through list is accessed without an explicit deconstructing assignment, including…

…when constructing pass-through lists by enclosing values in parentheses for overriding operator precedence associativity rules, so:

a*(b+c)
// is the same as
let(temp) = (b+c)
a*temp

…when accessing function return values, so:

let y = f(x)
// is the same as
let (y) = f(x)

…when pass-through lists of arguments are passed to functions. So:

let inverse = x -> 1/x
// is the same as
let inverse = (x) -> 1/x

Summary

By requiring functions to return lists, we’ve made code more robust with respect to changes to function signatures. The implicit construction and deconstruction rules remove the syntactic overhead from this.

These rules make pass-through lists into a kind of ephemeral type that cannot be referenced, requiring support of a more conventional list type in any language that uses pass-through lists.

Using the same semantics for passing/returning values to/from functions will allows a language designer to implement some useful new language features consistently on both sides of the interface to a function: named parameters (named return values), optional and default values (optional and default return values), type constraints, variable-length argument (and return value) lists, pattern matching, and nested deconstructing assignments. I hope to explore some of these features in future posts.

Finally in another future post, I hope to discuss how adding partial application and a new feature I call folded application to a language, along with the implicit construction and deconstruction rules, result in a language where curried and un-curried versions of functions are functionally identical.

Posted in Programming Language Design Tagged with: ,

duck library 2
July 19th, 2013 by john.warden@gmail.com

Most OO programmers have come across this situation: you have some types that don’t share any common supertype, but you wish they did, so you could write some generalized code that works for both types.

For example, you have a CartoonDuck and a RubberDuck class, they both quack, but you didn’t design them to implement a common Duck interface. So it makes it hard for you to create your duck utility library that works with all kind of Ducks.

Ill-Conceived Duck Library

The obvious solution is just to modify the original library code, and make the two duck classes implement a common Duck trait. But let’s say we can’t or don’t want to (e.g. we don’t have commit privileges for the Duck class library, or it is on a long release cycle).

The ability to extend functionality of a library without modifying its source is known as Retroactive Extension. Doing so without creating wrappers has been called Retroactive Polymorphism. There are a couple of great posts by Casual Miracles and Daniel Westheide that talk about using Type Classes in Scala to achieve retroactive polymorphism.

I would classify the particular kind of retroactive extension required for the Duck library — creating a common supertype for some classes without modifying their original code — as retroactive supertyping

In this post I’ll explore various techniques for achieving retroactive supertyping. But for the impatient, I’ll skip to the end with a comparison of pros/cons for each:

Comparison

Let’s start with our base class library.

class CartoonDuck(saying: String) {
    def quack(): String = saying
}

class RubberDuck {
    def quack(): String = "Squeek!"
}

val donald = new CartoonDuck("What's the big idea?")
val daffy = new CartoonDuck("You're dispicable!")
val rubberDucky = new RubberDuck()

/* Todo, implement describeDuckCollection and use it  */
//def describeDuckCollection(ducks: List[Duck]) { /* implement */ }
//describeDuckCollection(List(donald, daffy, rubberDucky))

But, we can’t implement describeDuckCollection(ducks: List[Duck]), because the Duck class doesn’t exist…

Solution 1: Modify Original Code

Again, often the best solution, but suppose we don’t want to do this.

Solution 2. The Adapter Pattern

Okay, so let’s create a Duck trait and create two adapter classes. This is usually a perfectly acceptable solution, especially if your code will be called from Java code that can’t use implicits, or maintained by Java programmers that don’t like implicits. The main drawback is it requires clients of your duck utility library to write extra code to wrap their ducks.

trait Duck {
    def quack(): String
}

def cartoonDuckAsDuck(d: CartoonDuck): Duck = new Duck { 
  def quack() = d.quack() 
}

def rubberDuckAsDuck(d: RubberDuck): Duck = new Duck {
  def quack() = d.quack()
}

def describeDuckCollectionUsingWrappers(ducks: List[Duck]) {
    print(
        "Here are my ducks: " +
        ducks.map(
          duck => "\tA duck that says '" + duck.quack() + "'"
        ).mkString("\n","\n","\n")
    )
}

val wrappedDonald = cartoonDuckAsDuck(donald)
val wrappedDaffy = cartoonDuckAsDuck(daffy)
val wrappedRubberDucky = rubberDuckAsDuck(rubberDucky)

describeDuckCollectionUsingWrappers(
    List(wrappedDonald, wrappedDaffy, wrappedRubberDucky)
)


Solution 3: The Rich Wrapper Pattern (or Pimp My Library Pattern)

If you don’t like explicitly creating those wrappedDonald, wrappedDaffy, etc. objects, then you can make your code more terse and at the same time more mystifying to newbie Scala developers — so they will respect you for your erudition even if they can’t work with your code ūüėČ — by using the Rich Wrapper pattern and implicit conversions.

/* Create a companion object to the Duck trait with the 
implicit conversion functions.  
Names of the functions don't matter, only signatures. */
object Duck {
    implicit def cartoonDuckAsDuck(d: CartoonDuck): Duck = new Duck {
      def quack() = d.quack() 
    }
    implicit def rubberDuckAsDuck(d: RubberDuck): Duck = new Duck {
       def quack() = d.quack()
    }
}

def describeDuckCollectionUsingWrappersAndImplicitConversions(ducks: List[Duck]) {
    print(
        "Here are my ducks: " +
        ducks.map(
          duck => "\tA duck that says '" + duck.quack() + "'"
        ).mkString("\n","\n","\n")
    )
}

describeDuckCollectionUsingWrappersAndImplicitConversions(
    List(donald, daffy, rubberDucky)
)

Here, the caller doesn’t have explicitly wrap its ducks — Scala wraps them for you automatically! If the types of objects being passed to a function don’t match the required types, Scala will look for implicits, functions that can convert them to the right types. It will look for any methods marked implicit in the current scope, or in any relevant companion objects — in this case, the Duck object — and if it finds one with the right type signature, it will assume you want to use it to convert your object to the right type, and do it for you automatically.

Solution 4: Structural Types

With structural types, I can retroactively create a supertype, and declare that anything that declares the quack() method of the right signature is an instance of that type.

/* If it quacks, it's a duck */
type StructuralDuck = {def quack(): String}

def describeDuckCollectionUsingStructuralType(ducks: List[StructuralDuck]) {
    print(
        "Here are my ducks: " +
        ducks.map(
          duck => "\tA duck that says '" + duck.quack() + "'"
        ).mkString("\n","\n","\n")
    )
}

describeDuckCollectionUsingStructuralType(
List[StructuralDuck](
  donald,
  daffy,
  rubberDucky
))

This one is simple, doesn’t require client code to explicitly wrap objects, and doesn’t use implicits! It seems like a perfect solution!

But, structural types only work if your classes all happen to have a duck method with the right signature.

And although structural types are considered to be type safe, they are not not necessarily semantically type safe. Even though it’s probably safe to say that anything that has a quack method is a duck, in other cases, two classes sharing a method with a common name could be mere coincidence. For example, I can create a structural type {def open(): ()}, and it would automatically be a common supertype for both Files and a Doors, but it would be useless and potentially dangerous. So, just keep that in mind.

Solution 5: Type Class Pattern

Type classes, the go-to solution for retroactive extension in Haskell, are probably overkill for the simple problem we are trying to solve here.

Type classes have many of the same pros/cons as the Rich Wrapper pattern, but are more powerful because they allow for multiple dispatch. Our retroactive duck supertyping challenge doesn’t require multiple dispatch, but I’ll still show how the type class pattern would be used in this example.

trait DuckTypeClass[D] { def quack(d: D): String }

object DuckTypeClass {
    implicit def cartoonDuckService: DuckTypeClass[CartoonDuck] = 
      new DuckTypeClass[CartoonDuck] { def quack(d: CartoonDuck) = d.quack() }
    implicit def rubberDuckService: DuckTypeClass[RubberDuck] = 
      new DuckTypeClass[RubberDuck] { def quack(d: RubberDuck) = d.quack()}
}


def describeDuckCollectionUsingTypeClass[D: DuckTypeClass](ducks: List[D]) {
    print(
        "Here are my ducks: " +
        ducks.map(
          duck => "\tA duck that says '" + 
            implicitly[DuckTypeClass[D]].quack(duck) + "'"
        ).mkString("\n","\n","\n")
    )
}

So understand that here, unlike with the Adapter pattern, we are not creating wrapped Duck objects that implement some kind of Duck trait. Instead we are creating objects that are like services (called type class instances) that provide a static duck function, taking CartoonDucks or RubberDucks as arguments. We create just one instance of each of these services for each type of duck, and pass them implicitly to describeDuckCollectionUsingTypeClass.

Notice the : DuckTypeClass inside the type parameter. This is a context bound, which is syntactic sugar, essentially equivalent to defining the method signature as:

def describeDuckCollectionUsingTypeclass[D]
(ducks: List[D])(implicit duckService: DuckTypeClass[D])

And then

implicitly[DuckTypeClass[D]].quack(...) 

is also syntactic sugar, equivalent to writing

duckService.quack(...)

And to be precise, Scala will choose some unique name for the parameter, not necessarily duckService.

Okay, basically we create services that give us static quack and other duck-like functionality, we pass them implicitly to general purpose duck code, and use the context-bound implicit parameter to make method signature a little more terse.

The Heterogeneous Collection Problem

But there’s a problem. Even though this works:

describeDuckCollectionUsingTypeClass(List(donald, daffy))

The following will give you a horrid little error that will make you wonder if it was all worth it:

describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))

Output

error: could not find implicit value for evidence parameter of type this.DuckTypeClass[ScalaObject]
describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))
^
So what’s going on? Well, the first function call works, because, the List only contains CartoonDucks. So Scala infers the type of the argument to be List[CartoonDuck]. It then looks for a typeclass instance of type DuckTypeClass[CartoonDuck], which it finds in the DuckTypeClass companion object. So all good

In the second function call, since the list contains two different types of Duck objects, Scala infers the type to be List[ScalaObject] — the common supertype of RubberDuck and CartoonDuck. But, we can only implicitly pass one instance of DuckTypeClass[D] — either DuckTypeClass[CartoonDuck] or DuckTypeClass[RubberDuck]. Thus, failure!

Solution 6: Hybrid Type Class with Structural Type

However, ScalaObject isn’t the only common supertype of CartoonDuck and RubberDuck. We already defined the StructuralDuck type previously! So let’s just create a new type class instance for StructuralDucks in the DuckTypeClass companion object!

object DuckTypeClass {
  implicit def structuralDuckService: DuckTypeClass[StructuralDuck] = 
    new DuckTypeClass[StructuralDuck] { 
      def quack(d: StructuralDuck) = d.quack()
    }
}

Then we suddenly can deal with heterogenous collections! Because Scala can deduce the list we are passing to be an instance of List[StructuralDuck], and it can find an implicit instance of DuckTypeClass[StructuralDuck], the call will work:

describeDuckCollectionUsingTypeClass(List(donald, daffy, rubberDucky))

Multiple Dispatch and Type Classes

But why would we want to do this? Aren’t we overcomplicating things? We had a perfectly good solution with structural types alone — why use structural types AND type classes?

The answer is, we wouldn’t. Don’t use a type class in cases like this. It’s overkill.

But let me show you when you would need a typeclass. Suppose we want our ducks to fight.

The trick is, the fight method takes two ducks as parameters, and the outcome of the fight depends on the type of duck. If we add the fight method to the type class instances cartoonDuckService and rubberDuckService, we have a problem. Only ducks of the same type could fight:

trait DuckTypeClass[D] { def quack(d: D): String; def fight(d1: D, d2: D): D }

object DuckTypeClass {
    implicit def cartoonDuckService: DuckTypeClass[CartoonDuck] = 
      new DuckTypeClass[CartoonDuck] { 
        def quack(d: CartoonDuck) = d.quack() 
        def fight(duck1: CartoonDuck, duck2: CartoonDuck)
    }

}

But using a type class and a structural type, any two objects with a quack method can fight.

object DuckTypeClass {
    implicit def structuralDuckService: DuckTypeClass[StructuralDuck] = 
    new DuckTypeClass[StructuralDuck] { 
      def quack(d: StructuralDuck) = d.quack()

      /* Define a fight method that works for any two structural ducks */
      import scala.util.Random
      def fight(blueCorner: StructuralDuck, redCorner: StructuralDuck): 
        StructuralDuck = (blueCorner, redCorner) match {

        /* Cartoon Ducks beat Rubber Ducks */ 
        case (rubberDuck: RubberDuck, cartoonDuck:CartoonDuck) =>
         cartoonDuck

        /* Obviously, order of parameters doesn't matter */
        case (cartoonDuck:CartoonDuck, rubberDuck: RubberDuck) => 
 
          fight(rubberDuck, cartoonDuck)

        /* For other combinations of ducks, let fate decide */
        case (duck1, duck2) => 
          if((new Random()).nextBoolean) duck1 else duck2
      }
    }
}

def describeDuckCollectionUsingTypeClassAndMultipleDispatch
[D: DuckTypeClass](ducks: List[D]) {

    /* Import quack and fight from the typeclass instance */
    val duckService = implicitly[DuckTypeClass[D]];
    import duckService._

    print(
        "Here are my ducks: " +
        ducks.map(
          duck => "\tA duck that says '" 
          + quack(duck) + "'"
        ).mkString("\n","\n","\n")
    )
    print(
        "They are fighting!  The winner says: "
        + quack(ducks.reduce(fight))
    )
}

describeDuckCollectionUsingTypeClassAndMultipleDispatch(
  List[StructuralDuck](
    donald, daffy, rubberDucky
  )
)


Now to be clear, what are the benefits of this solution? It means that now, we can create new Duck types, create a DuckTypeClass instances for them, and include them in our duck collection, and all of our describeDuckCollection* code will still work. And we can do this all without touching either our original library code, or the describeDuckCollection implementations! If you are a fan of the open-closed principle, and like to extend functionality with modifying perfectly good code, that’s nice.

Comparison

So each method has its pros and cons, like everything in life! I hope that this simple comparison will help you decide which solution will work best for your particular needs.

Comparison

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

generic syntax
June 28th, 2013 by john.warden@gmail.com

Is it really necessary to invent a new syntax, complete with a new grammar and parser, for every new programming language? Is there a generic syntax that can conveniently express the semantics of many languages? Since all languages, whatever the syntax, are eventually parsed into an abstract syntax tree, couldn’t we just use a general language for expressing abstract syntax trees?

XML and LISP

XML was designed to be generic enough to express data and concepts from virtually any domain. So the AST of, say, a Java program could be represented in XML:

Java

public Integer sum(Integer x, Integer y) {
    return x+y
}

XML

<method name='sum' returnType='Integer' public='true'>
  <parameters>
    <parameter name='x' type='Integer'/>
    <parameter name='y' type='Integer'/>
  </parameters>
  <body>
    <return><plus arg1='x' arg2='y'/></return>
  </body>
</method>

Obviously, nobody would actually want to write their Java programs in XML — but bear with me. Once you have a data structure representing your Java program, your program is now data that can be manipulated before it is finally converted to bytecode, for example via an XSLT transformation. You can now extend Java semantics with macros — functions that act on your program itself. Macros are one of the Lisp programmer’s secret weapons, and part of the reason Lisp programmers are always pointing and laughing at the rest of us.

You could also represent a Java AST in JSON, but it would be even more unwieldy than XML:

{
  head: "method",
  name: "sum",
  returnType: "Integer",
  public: true,
  parameters: [
    {
      head: "parameter",
      name: "x",
      type: "Integer"
    },
    {
      head: "parameter",
      name: "y",
      type: "Integer"
    }
  ],
  body: [
    {
      head: "return",
      body: {
        head: "+",
        arguments: ["x","y"]
      }
    }
  ]
}


You could also represent your Java AST in Lisp, since Lisp is actually built on a generic syntax for expressing nested data structures, which is what an AST is. This is why there are so many domain-specific languages in the Lisp world. Your Java program, if represented as a Lisp expression, would look something like this:

'(method Integer sum :public true [(Integer arg1) (Integer arg2)] (
  (return (+ arg1 arg2))
))

Since this is quoted data, there are no pre-defined semantics. It can represent anything — in our case a Java program.

Improving on LISP

The above Lisp code is a lot more terse than the XML or JSON. But even so, but I imagine few people will want to write their Java programs in Lisp.

Cleaner, More Generic

But what if we could further simplify the syntax and take Lisp out of the equation? We could:

  • First, eliminate the quote operator, by dropping the assumption that every expression represents a functional program by default. This makes the syntax truly generic, more like XML.
  • Second, eliminate unnecessary parentheses. Use whitespace indent/outdent to indicate open/close parentheses.
  • Third, use infix notation for symbols like +

Our syntax now looks like this:

method Integer sum :public true [Integer x, Integer y]
return (x+y)

This is pretty terse and readable. In fact, I think it compares in brevity and clarity with the original Java:

public Integer sum(Integer x, Integer y) {
  return x+y
}

The Parsed Data Structure

Here’s how a generic syntax expression might be parsed into JSON:

  • Comma-separated lists are converted to arrays.
  • Other sequence are converted to maps containing:
    • a root (the first element)
    • any key-value pairs (public in our example)
    • a body (containing the rest of the list)

So this expression:

method Integer sum :public true [Integer x, Integer y]
  return (x+y)

Would be parsed into this JSON structure:

{
  "head": "method"
  "public": true
  "body": [
    "Integer",
    "sum"
    [
      {
        "head": "String"
        "body": ["x"]
      },
      {
        "head": "String"
        "body": ["y"]
      }
    ],
    [
      {
        "head": "return",
        "body": [
          {
            "head": "+",
            "body": [
              "x",
              "y"
            ]
          }

        ]
      }
    ]
  ]
}

Your compiler/interpreter could take this object and interpret it in a way that makes sense. For example, it would be quite straightforward to write an interpreter that applied some transformations or some macros and then converted this data structure into Java.

Other Language Examples

Before showing examples of using generic syntax to represent the ASTs of programs in other languages, I’ll add one more element to the syntax. Sandwiching a token between colons like :this: makes that token an infix operator. And I’ll say all infix operators are right-associative with equal precedence.

Notice how natural the below programs look using generic syntax.

Generic C

include "iostream"

function int main []
  cout << "Hello, World!"
  return 0

Generic Haskell

quicksort :: (Ord a) => (List a) -> (List a)
(quicksort List) = List
quicksort (p : xs) = 
  (quicksort lesser) ++ (List p) ++ (quicksort greater) 
  :where:
        lesser  = filter (< p) xs
        greater = filter (>= p) xs


Conclusion

And a bit more work needs to be done for this language to be complete and practical of course.

Many generic data interchange languages exist, such as XML, YAML, and JSON. But none have been defined to have the versatile terseness required for a programming language. Such a syntax could have interesting uses:

  • It could make it easy to create a new domain-specific languages or new programming language without defining a parser.
  • You could write code from your favorite language, say Java or PHP, using this new syntax, and then define macros that transform your program before it is finally converted to Java or PHP.

In another post, I hope to develop this generic syntax more thoroughly, show some examples of how you might replace your current syntax with generic syntax, so that you can use Macros to transform your code.

Posted in Programming Language Design

images
June 28th, 2013 by john.warden@gmail.com

The “Box Dilemma” is the name I’ve given to the situation where modifying an interface to provide additional information requires making a non-backwards-compatible change.

Implicit Unboxing” is a possible solution to this problem. The compiler or interpreter would let you work with an object (the “box”) containing some value you are interested in wrapped up with some other stuff you want to ignore, and write code as if the box and the other stuff didn’t exist.

When a Box is a Problem

Imagine you walk into a jewelry store that offers watch polishing services. The sign says “give us a watch, and we will give you back a polished watch.” Fantastic. You hand the man behind the counter your fancy watch, in its original box.

Jeweler: What’s this?

You: A watch.

Jeweler: This isn’t a watch. It’s a box.

You: Uh…the watch is in the box.

Jeweler: I told you I polish watches, not boxes.

You: Are you kidding me?

You expect human beings to have some common sense when dealing with boxes. Just open the box! But, for some reason, we don’t have the same expectations for software. If you are using some sort of interface — a library, a web service, a function, etc. — and it expects a watch, and you pass it a box with a watch inside of it, it won’t work. For example:

/* Polish interace takes a watch */
Watch polish(Watch watch)

/* Try to polish a box with a watch in it */
jeweler.polish(new Box(new Watch))

If it’s a strongly typed language, the compiler will respond like that jeweler did, with a type error, something like:

‘polish’ expects an argument of type Watch. But you passed it an argument of type Box[Watch] (you moron).

If the language is not strongly typed, it will act even less intelligently, and throw a disasterous runtime error only after the polishing wheel has ripped your cardboard box to shreds. ¬†The same problem occurs if the Jeweler returns the watch in a box containing, say, the receipt, but your code wasn’t written to expect a box.

Interface Breaking Changes

As a less allegorical example, suppose I have a function that uses some statistics to guess the language of a natural language string. The fairly unsophisticated function just returns a string with the name of the language, which is all I need. It’s not always 100% confident of its guess, so it also returns a number representing a confidence %. The interface looks like this (in no particular programming language):

Listing 1

  
interface LanguageGuess
    String language 
    Float confidence

/* guessLanguage signature returns a LanguageGuess */
LanguageGuess guessLanguage(String)

But I am not interested in the confidence field now. I wish the interface wasn’t so complicated and I could just treat the return value as a string, and write code like this:

Listing 2

String languageGuess = guessLanguage("oh la la")

println languageGuess + ": " + (if(languageGuess == "French")
"that's what I thought"
else
"what the?!?!")

Instead of like this:

Listing 3

LanguageGuess languageGuess = guessLanguage("oh la la")

println languageGuess + ": " + (if(languageGuess.language == "French")
"that's what I thought"
else
"what the?!?!")

You may be thinking what an incredibly lazy programmer! You only need to add .language after languageGuess to “open the box” and access the string. Is this so much work?

Well, no. But my motivation is not saving keystrokes. Rather, it’s that I don’t want to break existing code. You see the previous version of this function used to return just a string, until I realized some words (e.g. “no”) exist in many languages, and that my previous thinking about this language identification problem was over-simple. So I changed the interface to return an object containing both a language and a confidence %. ¬†But now all the many people who wrote code against my old interface have to change it. This is a real problem.

The “Core Value” and the “Box”

With many data structures, it’s easy to identify the core¬†value. It’s the payload, the meat, the fancy watch, the T type parameter, the thing that the “container” exists to contain.

Changing an interface that used to return a value of type T, to return some sort of object containing a value of type T, is one of the most common and expensive changes coders make, one I beleive accounts for measureless software development costs annually.

But this sort of change is a necessary part of the natural evolution of code. First of all, it’s easier to start thinking about your program logic in terms of these core functions and types, and initially ignore ancilliary stuff like logging, error handling, etc. Second, you like all of us have a limited IQ and simply won’t think of all the aspects that should be worked into your design up front (and gosh darnit I’m sick of languages making my feel like I should). And finally, requirements and designs change!

A Box Monad?

Many of the millions of attempts to explain what a Monad is use a Box as an analogy. Now, Monads go beyond simply a value contained in a box. They can deal with future values, or multiple values, or possible or probable values, and so on.

Rather, the “Box Dilemma” problem is just one problem that Monads may help solve.

One of the things that gets functional programmers excited about Monads, is that they kind of promise to let you write code in terms of core values, and let the Monad handle everything else (in this case, the box) orthogonally. But you have to write your code just a little differently so the compiler or interpreter knows to work the Monad magic. For example if I made the type of objects returned by guessLanguage into Monad instances, I could use ‘do’ syntax (a la Haskell) or for comprehensions (a la Scala), like this:

Listing 4 (Scala-like for comprehension)

for
  language <- guessLanguage("oh la la")
  yield println language + ": " + (if(language == "French")
    "that's what I thought"
  else
    "what the?!?!")

This is, uhh, great. It makes my code more complicted, and it hasn’t helped me achieve my goal of not changing Listing 2.

On the bright side, this code is now more robust, because now its possible to add additional aspects to the objects returned by guessLanguage, such as possible errors, or multiple values, or I could even make it run asynchronously, without changing the code in Listing 4 (although combining all these aspects into one object would be challenging.) Now that is kind of neat, and part of why Monads are all the rage right now.

Implicit Unboxing

But, I’m not satisfied. I don’t want to change Listing 2 one bit. My core logic was expressed perfectly clearly and succinctly in listing 2. I want to completely¬†de-couple my core logic from ancilliary aspects of my program like confidence and possible error and logging.

Why can’t the compiler look at my code in listing 1, and automatically just do the right thing? It could automatically convert listing 1 to listing 2 (if we wanted to use a Monad for the implementation). Or it could simply rewrite the code to extract the core value explicitly.

Now, one reason I might not want this, is that in some cases I do¬†want access to the other stuff in the box. So I’d need a way to indicate these cases to the compiler. One possibly solution may be to use type annotations (assuming a typed language) to indicate either the simpler type or the whole box. If I want to access the whole box, my code might look like this (the declaration LanguageEstimate languageEstimate on line 1 is the key).

Listing 5

/* Treat the return value as a language estimate */
LanguageEstimate languageEstimate = guessLanguage("quiero taco bell")

println "The language is " + languageEstimate.language + " with confidence " + languageEstimate.confidence


Otherwise, I would have declared String languageEstimate and my code would look more like listing 2.

Creating Boxes

Suppose in our language, we could create objects using syntax like this:

(core: "French", confidence: 30)

And to save some keystrokes, lets say that we can indicate the “core” value just by listing it first.

("French", confidence: 30)

The compiler would ignore everything but the core value by default

String language = ("French", confidence: 30)
println language

Output

French

But if I use a type annotation compatible with the box, it would give me access to the box and all the extra stuff in it.

LanguageEstimate estimate = ("French", confidence: 30)
println "Language is " + estimate.language + " with confidence " + estimate.confidence

Structural typing and a syntax for pattern matching / deconstructing assignments could come in handy here.

(language, confidence:) = ("French", confidence: 30)
println "Language is " + language + " with confidence " + confidence

Now, if I originally wrote my function to only return a string:

estimateLanguage = string ->
    String language = /* do some analysis */
    Float confidence = /* do some analysis */
    /* return language */
    language

I could modify it return confidence as well without breaking any existing code, just by returning an object with a core value.

LanguageEstimate = type(String, confidence:Float)
estimateLanguage = s ->
    String language = /* do some analysis */
    Float confidence = /* do some analysis */
    /* return language and confidence*/
    (language, confidence: confidence)

And again, this change wouldn’t break any existing code: listing 2 would work for either version of this function.

Possible Applications

Since clearly defining the “Box Dilemma” in my own mind, and understanding what seems like a plausible solution, I have noticed countless instances where this would be immensely useful.

For example, it would provide an interesting way of supporting macros in a language. In an expression such as f(g(x)), the result of evaluating g(x) would normally be passed to f. What if, instead, f received a box that contained the value of g(x) as the core (evaluated lazily), but also contained a data structure representing the parsed expression g(x) itself? If you are writing a regular function, you would ignore the box and just process the value. If you are writing a macro, you could access the box and manipulate the expression itself.

As another example, implicit unboxing can allow you to sneak in “extra” information in all sorts of places where normally it wouldn’t fit. For example, suppose I have a println function defined for strings, which are just lists of characters. And suppose I have defined constants for text formatting such as color and style. I could create strings that have format annotations, and pass those strings to functions that don’t know anything about format annotations, without breaking anything.

regularString = ['a','b','c']
colorfulString = [
    ('a', color: red)
    ('b')
    ('c', color: blue, bold: true)
]
println regularString
println colorfulString

Output

abc
abc

But other functions that know about text formatting could deal with them.

println colorfulString map c ->
    (char, color:) = c
    if(defined color) "(" + color.name + " " + char + ")" else char

Output

(red a)b(blue c)

Conclusion

A language that supported implicit unboxing would open up all sorts of possibilities, where new information could be added to interfaces were previously we wouldn’t have dreamed of it because of how much complexity it would add to the interface, and how much existing code it would break. It would allow functions to return error, debug, type and contract, annotations, and all sorts of other information that can be ignored by code that doesn’t need it. But most importantly, as you change your interface due to the natural evolution of your understanding of the problem and your requirements, you are much less likely to break existing code.

 

Posted in Programming Language Design