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

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

Global environment variables violate a core principle of functional programming. For example, this is not very acceptable in the FP world:

def hello = 
  if(locale == 'en.US') 
    "hello"
  elsif(locale == 'fr.FR')
    "bonjour"

locale shouldn’t just be there as a global. In an pure functional language it should be passed as a parameter, according to the the principle of referential transparency.

def hello(locale) = 
  if(locale == 'en.US') 
    "hello"
  elsif(locale == 'fr.FR')
    "bonjour"

But this means you also have to pass locale to every function that calls hello.

def greet = (name, locale) ->
   hello(locale) ++ ", " ++ name

Which means you have to pass locale to every function that calls greet, and so on. Turtles all the way down.

Given/Inject Preprocessing

In my post on functional dependency injection and inversion of control, I discuss a solution for passing dependencies without this syntactic overhead, using given/inject statements and code pre-processing.

We usually think of “dependencies” as libraries or services. But anything your code depends on can be thought of as a dependency. In any case, we can use given to thread locale through our code without the semantic overhead.

given locale

def greet = (name) ->
   hello ++ ", " ++ name

def hello = 
  if(locale == 'en.US') 
    "hello"
  elsif(locale == 'fr.FR')
    "bonjour"

The given statement causes:

  • greet and hello to be rewritten in the pre-processing stage to accept an invisible locale parameter
  • greet to pass the locale parameter in its call to hello.

Now other functions can inject a value for locale. The inject statement causes locale to be passed as a parameter to every subsequent function call in the code block that needs it.

def main(environment) = 
    inject locale = environment.locale
    greet("Everybody")

Now we have the convenience of what kind of looks like a global variable. But it is implemented in such a way that the core principles of FP — no side-effects and referential transparency — are respected.

Referential Transparency

You might argue that, because you don’t actually see these parameters literally being passed in your code, given/inject violates referential transparency.

But the referential transparency rule simply requires that an expression can be replaced with its value without changing the output of the program. The value of an expression involving a given simply depends on that variable being bound to a value. Once bound, the expression can be evaluated, and it will be interchangeable with its value.

Referential transparency is not about syntax: it’s about having well-defined, reproducible behavior that is determined entirely by inputs. There is nothing non-FP about using macros and pre-processors to save some keystrokes.

Clarity

Some programmers might fear that bugs and confusion may arise when programmers don’t realize that their program behavior depends on an environment variable. But if even indirect dependencies on environment variables must be declared with given statements, it should be just as clear to a programmer reading the code what is going on.

Preprocessing vs Monads

Another purely functional approach to environment variables is the use of the Reader Monad. But this requires a great deal more syntactic overhead than given/inject. The signature of every function must be modified to return a Reader, and every function call involves a bind. Code pre-processing with given/inject does this work for you.

Conclusion

given/inject preprocessing lets you use environment variables in a purely functional way without the work and complexity of threading them as parameters throughout your code.

Posted in Programming Language Design Tagged with: ,

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

The terms Dependency Injection and Inversion of Control tend to be used in OOP circles, though these concepts are applicable to virtually any language.

A good summary of the definitions of these concepts is the first answer by Garret Hall on the stack overflow question Inversion of Control vs Dependency Injection. Adam Warski has another good blog post on dependency injection in a post OO world.

In this post I’ll talk about dependency injection and IoC in functional programming languages, and propose a solution for achieving IoC with given/inject preprocessing.

Dependency Injection for Dummies

Dependency Injection is when instead of doing something this:

import someLibrary.makeRect
def makeSquare(sideLength) = makeRect(sideLength, sideLength)

You do this:

def makeSquare(sideLength, makeRect) = makeRect(sideLength, sideLength)

I’m not using any particular programming language here. Just trying to illustrate concepts.

So makeSquare has a dependency, makeRect. We pass makeRect as a parameter to makeSquare in the second example, instead of hard-coding a reference to a specific implementation as we did in the first.

Instead of calling this little technique passing-of-dependencies-as-arguments, we call it dependency-injection. There you go.

Too Many Arguments

If you are a consistent dependency-injector, you inject all dependencies, deferring all decisions about concrete implementations to the highest level of your program — say the main function. So:

def main =
  import someLibrary.makeRect
  makeSomeSquares(makeRect)

def makeSquare(sideLength, makeRect) = makeRect(sideLength, sideLength)
def makeSomeSquares(makeRect) = [makeSquare(2, makeRect), makeSquare(4, makeRect)]

So your have littered your code with makeRects, passing it from main all the way down the call stack.. This is ugly. Most people don’t actually do this.

Other Means of Inversion of Control

Inversion of Control is the more general principle we are striving for here. IoC just means not hard-coding specific implementations for dependencies, but rather just specifying what is needed (“something that makes a rectangle”), and letting something higher up make a decision about specific implementations

Passing dependencies as parameters like this is just one way of achieving IoC. In the OO world, there are also IoC frameworks, service locators, the Template design pattern, and more. But what about the FP world?

Given and Inject

In a functional programming language where code is data, we don’t need containers or design patterns or anything like that. We can just create something that modifies our code to do the dependency injection for us.

Let’s define the given keyword, which is like import, but where you don’t hard-code a specific implementation.

given makeRect // instead of: import someLibrary.makeRect

def makeSquare(sideLength) = makeRect(sideLength, sideLength)
def makeSomeSquares = [makeSquare(2), makeSquare(4)]

So we no longer pass makeRect explicitly to makeSquare or makeSomeSquares.

No let’s define an inject keyword for binding given dependencies to actual implementations.

def main =
  inject makeRect = someLibrary.makeRect
  makeSomeSquares

Now we have two simple, complementary keywords — given and inject — for achieving inversion of control, without the burden of “manually” injecting dependencies into every function call all the way down the stack.

given and inject Macros

given and inject can be thought of as pre-processor directives or macros, that cause your program to be transformed before it is evaluated. For example in a Lisp-like language, we could define GIVEN and INJECT macros, and write our program like this:

    (GIVEN [makeRect] 
      def makeSomeSquares ..etc...)
    
    (def main
      (INJECT [makeRect someLibrary.makeRect]
        makeSomeSquares))

After the macro evaluation stage, we’d have a program where makeRect is explicitly passed as a parameter to makeSquare and makeSomeSquares, but we’d never have to touch that awkward code.

The given and inject syntax is just an alternative syntax for achieving the same thing.

Conclusion

I don’t need to explain the merits of inversion of control — it’s one of the pillars of good OO design. However, it’s often dismissed as non-applicable in a language with higher-order functions. But as demonstrated above, manually injecting dependencies by passing functions as arguments can be cumbersome.

given/inject preprocessing allows you to inject your dependencies to achieve inversion of control without syntactic overhead or complexity, while respecting the principles of pure FP.

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

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