Monday 30 April 2012
The expression is a tricky problem in many languages that asks: given a set of functions that operate over a set of types, how do we allow both the set of functions and the set of types that those functions operate over be extending without losing type safety? If you're not familiar with the problem, I recommend reading the explanation by the author of Magpie. For our purposes, we'll use an abstract syntax tree for mathematical expressions as our data type. To start, let's have two sorts of node: addition operators and literals.
interface Node {}
def AddNode class(myLeft: Node, myRight: Node) implements Node => {
public def left fun() => myLeft;
public def right fun() => myRight;
}
def LiteralNode class(myValue: Double) implements Node => {
public def value fun() => myValue;
}
(As an aside: due to the design of the language, we can't give the arguments to a class the same name as it's getter, for instance def value fun() => value, since the body of the function would refer to the function rather than the class argument. Prepending each of the arguments with my is a poor solution, and although I have several ideas on how to rectify this, I'm still pondering on the simplest, cleanest solution.)
Suppose we want to implement a function evaluate that evaluates the expression to a single value. Our first attempt at an implementation might look like this:
def evaluate fun(node: Node) : Double =>
match(node,
case(AddNode, evaluateAdd),
case(LiteralNode, evaluateLiteral)
);
def evaluateAdd fun(add: AddNode) =>
evaluate(add.left()) + evaluate(add.right());
def evaluateLiteral fun(literal: LiteralNode) =>
literal.value();
There's one immediate with this solution: it's not type-safe. If somebody adds another implementation of Node, then evaluate no longer covers all possible cases. The solution to this problem is to define a union type:
type StandardNode = AddNode | LiteralNode
and update evaluate by changing the type of its argument:
def evaluate fun(node: StandardNode) : Double =>
match(node,
case(AddNode, evaluateAdd),
case(LiteralNode, evaluateLiteral)
);
def evaluateAdd fun(add: AddNode) =>
evaluate(add.left()) + evaluate(add.right());
def evaluateLiteral fun(literal: LiteralNode) =>
literal.value();
This makes evaluate type-safe, but has had the unintended consequence of making evaluateAdd unsafe: add.left() and add.right() both have the type Node, yet evaluate only accepts the narrower type StandardNode. We fix this by adding type parameters to AddNode:
def AddNode class[T] => (myLeft: T, myRight: T) implements Node => {
public def left fun() => myLeft;
public def right fun() => myRight;
}
and modifying the type of the argument of evaluateAdd and updating the value of StandardNode:
def evaluateAdd fun(add: AddNode[StandardNode]) =>
evaluate(add.left()) + evaluate(add.right());
type StandardNode = AddNode[StandardNode] | LiteralNode;
(At this point that the interface Node isn't really necessary any more, although there might be other reasons to keep it around.)
Suppose we now add NegateNode and the associated union type ExtendedNode:
def NegateNode class[T] => (myValue: T) => {
public def value fun() => myValue;
}
type ExtendedNode =
AddNode[ExtendedNode] |
NegateNode[ExtendedNode] |
LiteralNode;
ExtendedNode cannot reuse the definition of StandardNode since AddNode[ExtendedNode] is a subtype of ExtendedNode but not a subtype of StandardNode. The solution is to introduce another type parameter, this time on StandardNode and ExtendedNode:
type StandardNode[T] = AddNode[T] | LiteralNode;
type ExtendedNode[T] = StandardNode[T] | NegateNode[T];
We can then add the appropriate type parameters to the argument of evaluate:
def evaluate fun(node: StandardNode[StandardNode]) : Double =>
match(node,
case(AddNode[StandardNode[StandardNode]], evaluateAdd),
case(LiteralNode, evaluateLiteral)
);
But this doesn't work either: we need to specify the type parameter to the second reference to StandardNode, which is StandardNode, which also requires a type parameter... and so on. The solution is to add yet more types that fix the type parameter to themselves::
type StandardNodeF = StandardNode[StandardNodeF];
type ExtendedNodeF = ExtendedNode[ExtendedNodeF];
def evaluate fun(node: StandardNodeF) : Double =>
match(node,
case(AddNode[StandardNodeF], evaluateAdd),
case(LiteralNode, evaluateLiteral)
);
In order to evaluate an instance of ExtendedNode, we'd need to define the following:
def evaluateExtended fun(node: ExtendedNodeF) : Double =>
match(node,
case(AddNode[ExtendedNodeF], evaluateAddExtended),
case(NegateNode[ExtendedNodeF], evaluateNegate),
case(LiteralNode, evaluateLiteral)
);
def evaluateAddExtended fun(add: AddNode[ExtendedNodeF]) =>
evaluateExtended(add.left()) + evaluateExtended(add.right());
def evaluateNegate fun(negate: NegateNode[ExtendedNodeF]) =>
-evaluateExtended(negate.value());
It seems reasonable to write evaluateNegate, but the definition of evaluateAddExtended seems virtually the same as before. The difference is the type parameter for AddNode, and the function we use to evaluate the sub-nodes. So, we introduce a type parameter and argument to abstract both:
def evaluateAdd fun[T] => fun(evaluator: Function[T, Double]) =>
fun(add: AddNode[T]) =>
evaluator(add.left()) + evaluator(add.right());
We can also perform a similar transformation on evaluateNegate and evaluate:
def evaluateNegate fun[T] => fun(evaluator: Function[T, Double]) =>
fun(negate: NegateNode[T]) =>
-evaluator(negate.value());
def evaluate fun[T] => fun(evaluator: Function[T, Double]) =>
fun(node: T) : Double =>
match(node,
case(AddNode[StandardNodeF], evaluateAdd[T](evaluator)),
case(LiteralNode, evaluateLiteral)
);
Now we can rewrite evaluateExtended to use evaluate:
def evaluateExtended fun[T] => (evaluator: Function[T, Double] =>
fun(node: ExtendedNode[T]) : Double =>
match(node,
case(StandardNode[T], evaluate[T](evaluator)),
case(NegateNode[T], evaluateNegate[T](evaluateNegate))
);
If we want to call evaluate or evaluateExtended we
need to use a similar trick as with StandardNode and
ExtendedNode to instantiate the functions:
def evaluateF fun(node: StandardNodeF) =>
evaluate[StandardNodeF](evaluateF)(node);
def evaluateExtendedF fun(node: ExtendedNodeF) =>
evaluateExtended[ExtendedNodeF](evaluateExtendedF)(node);
Hopefully you can now see how you'd extend the solution to include further
node types. Although not covered here, it's also possible to create functions
or classes to help combine evaluators, and functions generally written in
this style with a bit less boilerplate.
If we imagine an ideal solution to the expression problem, we might argue
that this solution is a little verbose, and I'd be inclined to agree.
The question is: is it unnecessarily verbose? There's an argument to be made
that this exposes the essential complexity of solving the expression problem.
Other less verbose solutions hide rather than remove this complexity. On the one
hand, this allows one to express the same ideas more succinctly without being
cluttered with the machinery of how the solution is achieved, compared to the
solution I just described where we have to constantly pass around the type
parameter T and evaluator argument. On the other
hand, if you want to understand what's going on, you don't have to look
very far since everything is explicitly passed around.
On the whole, I think it's simpler than some solutions I've seen to
the expression problem, and the verbosity isn't all-consuming. Pretty good
for a first go, I reckon.
Topics: Language design, Shed
Monday 30 April 2012
Looking around at many of the mainstream languages today, I can't help feeling
as if they've become rather large and unwieldy. I'd say this is true of both
scripting languages such as Python and Ruby, as well as languages common in the
enterprise, such as C# and even Java. I'd argue that features such as
(implementation) inheritance, extension methods, properties, attributes/decorators,
and null act to complicate each language.
A little over a year ago, I thought about the set of features that I actually
used and wondered what a slimmed-down object-orientated programming language
would look like. To that end, I've been working on the Shed programming language. A
non-exhaustive list of features would be:
- Statically-typed
- Functions, including
- Closures
- Functions as values
- Lightweight anonymous function syntax
- Interfaces
- Classes that can implement interfaces
- Object literals, which can also implement interfaces
Intentionally missing are:
- Nulls
- Implementation inheritance
- Extension methods
- Properties
- Function overloading
To give a flavour, here's a naive implementation of the Fibonacci sequence:
def fibonacci fun(n: Double) =>
if n <= 1
then n
else fibonacci(n - 1) + fibonacci(n - 2)
Note that the syntax is still changing. The current implementation of the
compiler doesn't support operators yet, so to get the above compiling, you'd have
to replace the operators with method calls.
The aim of implementing the language
is fun and experimentation, rather than creating a language to write
production code in. I'm pretty sure that for the code I tend to write Shed is a
good fit, at least for my programming style. I don't know if the language
I'm writing applies so well to other domains that I'm less familiar with, but I
intend to enjoy finding out, and possibly extending the feature list as I go.
One of the main principles of the language is to optimise for the reader
rather than the writer. I spend far more time wondering
what some piece of code does that I'd written a few months ago, than typing
new bits of code.
Following on from this, variables in Shed may only be introduced into a scope
via an explicit declaration, excluding variables in default scope. For instance:
import time.*;
since there's no way to tell exactly what variables have been added to scope. In
contrast, the following import adds DateTime to scope:
import time.DateTime;
As I implement various bits of Shed, I'll continue to post interesting
problems and solutions I come across. Until then...
Topics: Language design, Shed
Thursday 23 February 2012
While thinking about what subsets of common languages, such as JavaScript and Java, could be considered pure, it occurred to me that object identity in most languages is an unexpected source of impurity. That is, if you're using object identity, you're not writing purely functional code.
Take, for instance, this piece of JavaScript:
var createEmpty = function () {
return {};
};
var first = createEmpty();
var second = createEmpty();
var isTheSame = first === second
We create two empty objects, and then determine whether they represent the same object using the triple equals operator (using is in Python or == in Java would have much the same effect). Since they were constructed separately, isTheSame holds the value false. Yet in a purely functional language, calling the same function with the same arguments (in this case, no arguments) twice should return the exact same value.
Strictly speaking, it's the construction of the object that is the impure code: calling the identity operator with the same arguments will always return the same value, whereas each time we construct an object, we assign it a different identity. However, code that either contains no use of object identity, or contains no construction of objects can be considered pure. Treating object identity as the impure concept that cannot be used is, in my opinion, the more useful option: it's quite handy being able to construct objects.
Topics: Functional programming, Language design
Sunday 23 October 2011
Over on the 8th Light blog, Steven Degutis discusses the advantages of Go's approach to interfaces. Specifically, Go allows you to have a class implement an interface without explicitly mentioning the interface so long as it has methods with the right names and type signatures. He likes the idea you can write an interface, and have an existing class implement that interface without modification. I find the idea that a class can implement an interface just by the coincidence of having methods with matching names and type signatures to be terrifying.
To re-use Steven's example:
type Predator interface {
chasePrey(Prey) bool
eatPrey(Prey)
}
type Lion struct{}
func (self Lion) chasePrey(p Prey) bool {
// ...
}
func (self Lion) eatPrey(p Prey) {
// ...
}
Since Lion has the methods chasePrey and eatPrey with the correct type signature, it implements the interface Predator, yet the interface Predator is never mentioned in the definition of Lion. This is considered a Good Thing: to quote Steven:
But alas, in Java, the class itself must know ahead of time all the names of the interfaces it wants to conform to. This is an unfortunate form of temporal coupling.
[…]
Go doesn't care that, 5 years ago, Lion never specified which interfaces it implements, it just cares that it has the methods this interface needs, and rightly so.
I think it's a terrifying idea that my class could suddenly start implementing new interfaces that I'd never considered when writing the class. When I define an interface in Java, it has more meaning than just the name and type signature of each method. An interface is also a contract for the behaviour of the implementation of those methods, which can't be verified by names and types alone. I want to explicitly specify the interfaces that a class implements, as a declaration in the code that says "I understand what behaviour sub-types of the interface should have, and I've done my best to make sure that this class implements that behaviour". To me, this is much more useful than knowing the type of a class is compatible with an interface.
Now, I'm not saying that Go has got it wrong. I think Go's interfaces provide weaker contracts in exchange for greater flexibility, but which is better depends on your programming style and preferences.
Topics: Software design
Saturday 22 October 2011
When talking about node.js, I usually hear people give two reasons why they love it. The first is that it uses an event-driven model for concurrency, rather than using threads and blocking function calls. The second is that node.js allows you to use the same language, JavaScript, on both the browser and the server. You can then share logic that might otherwise be duplicated, such as validation of user input. Yet people often dismiss the latter point, saying that when they do web development, the amount of logic that ends up being duplicated is neglible, since the code on the browser and on the server address different concerns.
My question is: have we got this the wrong way round? Does code on the browser and server tend to address separate concerns precisely because sharing logic between them is hard? Once we start using the same language on both sides, we might start to see new ideas that this brings to the table. With modern web applications, we see more and more code that we might have previously expected to see on the server being brought into the browser. If we can easily move code between the browser and server, then we start to have an enourmous amount of flexibility: we can easily change our minds about where some particular code should be executed both when building our application, and at run-time.
Topics: JavaScript, Software design
Tuesday 27 September 2011
I heartily endorse this fine article on writing maintainable code. What do you mean I'm biased because I wrote it?
Topics: Software design, Software development, Testing
Tuesday 7 December 2010
While looking for a templating language for node.js, I came across an article On Design Minimalism, which gels well with my view that reusable code is all about small components that do as little as possible to get the job done, rather than frameworks that do everything you can think of.
Topics: Software design
Thursday 9 September 2010
It was recently pointed out to me (unfortunately, I can't remember where) that a good way to distinguish functional and procedural versions of similar functions is to use adjectives for the functional version and verbs for the procedural version.
For instance, consider functions that sort a list. The functional version would be called sorted, and returns a sorted copy of the list:
some_list = [2, 0, 1]
sorted_list = sorted(some_list)
# some_list == [2, 0, 1], sorted_list == [0, 1, 2]
On the other hand, the procedural function would be called sort, and modifies the list in-place:
some_list = [2, 0, 1]
sort(some_list)
# some_list == [0, 1, 2]
This is probably obvious to everybody else, but I'd never really thought it too much before.
Topics: Software design
Thursday 13 May 2010
Picking names sensibly in code is crucial to readability. For instance, let's say you're storing prices in your database, and they're represented by a Price class. What does a PriceHelper do? Naming something a helper isn't helpful in the least. On the other hand, the class PriceFetcher probably fetches prices from somewhere. Others have written about what names not to use for classes, but I want to talk about a different set of names. I want to talk about how we name our tests. For instance, let's say I'm implementing a join method in Java that will glue together a list of strings. Being a good programmer, I write a test to describe its behaviour:
class JoinTest {
@Test
public void testJoin() {
assertEquals("", join(", ", emptyList()));
assertEquals("Apples", join(", ", asList("Apples")));
assertEquals(
"Apples, Bananas, Coconuts",
join(", ", asList("Apples", "Bananas", "Coconuts"))
);
}
}
So, what's wrong with calling the method testJoin? The answer is that the method tells us nothing about what we expect to happen, just that we're testing the join method. By picking a name that describes what we expect, we can help the next reader of the code to understand what's going on a little better:
class JoinTest {
@Test public void
joiningEmptyListReturnsEmptyString() {
assertEquals("", join(", ", emptyList()));
}
@Test public void
joiningListOfOneStringReturnsThatString() {
assertEquals("Apples", join(", ", asList("Apples")));
}
@Test public void
joiningListOfStringsConcatenatesThoseStringsSeparatedBySeparator() {
assertEquals(
"Apples, Bananas, Coconuts",
join(", ", asList("Apples", "Bananas", "Coconuts"))
);
}
}
Splitting up tests in this fashion also means that it's easier to pin down failures since you can easily work out exactly what test cases are failing.
This works well with Test Driven Development (TDD). Each time you want to add a new behaviour and extend the specification a little further by adding a failing test, the test method describes the new behaviour in both the test code and its name. In fact, having rearranged the code so that the test method names are on their own line without modifiers, we can read a specification of our class simply by folding up the bodies of our test methods:
class JoinTest {
joiningEmptyListReturnsEmptyString() {
joiningListOfOneStringReturnsThatString() {
joiningListOfStringsConcatenatesThoseStringsSeparatedBySeparator() {
}
This reflects the view that test driven development is just as much about specification as testing. In fact, you could as far as saying that regression tests are a happy side-effect of TDD. Either way, the intent of each test is now that much clearer.
Topics: Testing
Sunday 21 February 2010
Improving performance is often a desirable goal. Sometimes you'll have a precise number for just how much performance needs to be improved by, particularly in real-time systems. More often, though, the request for improved performance is far more vague. So, what sort of numbers should we aim for when we want things to go faster? This depends on why you want faster performance -- do you just want to save a bit of time, or do you really want things to change?
Take, for instance, the time it takes to run your entire test suite. This can vary wildly, depending on the application, from seconds to days. Let's say we're working on a small project, and we have a test suite that covers the entire application in one minute. This is fast enough that we can run the entire suite every time before we commit, but we won't be running it every time we make a small change. If we made it go, say, twice as fast, we'd definitely save ourselves some time -- thirty seconds for every commit, if we really do run all the tests before every commit. This is still too slow to be running each time we make a small change, but what if we sped up the suite by an order of magnitude instead, so it takes only a few seconds to run? Now, running the entire suite every minute or two is practical, rather than just before every commit.
Sometimes, we really can get performance improvements of an order of magnitude, by improvements in technology or a clever new algorithm. Otherwise, we might still be able to do what all programmers do -- cheat. If we can get most of the benefit in a much shorter time, then this is often good enough. Going back to our test suite, if we can identify some subset of the tests that run in 10% of the time with 90% of the coverage, then most bugs we might introduce are still picked up, while our tool, the test suite, becomes more flexible.
By improving performance not by small amounts, but by orders of magnitude, we can change the way we use and think about our tools. Performance really does matter.
Topics: Software development