Mike's corner of the web.

Power à la Carte: fine-grained control of power in programming languages

Monday 28 March 2016 11:05

Proposal: general purpose programming languages should provide fine-grained control of the power that a particular module can use. "Power" includes language features, or what modules it is allowed to depend on, whether built into the language, from another package, or within the same codebase.

Suppose I'm writing some code to calculate how much tax someone should pay in a given year. I might want to forbid the use of floating point arithmetic in any of these calculations, but this isn't possible in most languages. In this proposal, I can declare what domain a module belongs to. For each domain, I can then declare what language features it's allowed to use. In this case, I'd be able to declare code as belonging to the "tax calculation" domain, and ensure that that domain cannot use floating point.

Take mutability as another example. I find most code I write is easier to reason about if it doesn't use mutability, but there are a small set of problems that I find are best expressed with mutable code, either for clarity or performance. By choosing exactly when mutability is permitted, I can still use mutability when needed without introducing its complexity into the rest of my codebase. Provided that the code doesn't mutate its arguments nor global state, the rest of the code doesn't need to know that mutability is being used: the contract of the functions can still be pure.

For each domain, I can also declare what other domains that domain is allowed to access. This allows enforcement of separation of concerns i.e. we can ensure that domains aren't intertwined when they shouldn't be. For instance, how tax is calculated shouldn't depend on personal details of an individual, such as their name. This also allows us to see what domains are used without having to read and understand the code of a module.

As another example, suppose I'm writing code to calculate the trajectory of a spacecraft. If I represent values such as distance or speed as integers, then it's possible to do something nonsensical like adding together two distances that use different units, or add together a distance and a speed. Within the domain of the trajectory calculation, I could represent these values with specialised data types preventing the incorrect use of these types. At some point, I may wish to unwrap these values, say to print them, but I can enforce that such unwrapping never happens during calculations. I'll also need to create these wrapped values in the first place, but I can declare and ensure that this value creation only occurs at well-defined boundaries, such as when reading sensors, and never directly within the calculation code.

In other words: the "mechanics" domain uses the "integer arithmetic" domain in its implementation, but that fact is private to the "mechanics" domain. In the "trajectory" domain, I explicitly declare that I can use values from the "mechanics" domain (such as adding together distances or dividing a distance by a time to get a speed), but that doesn't allow me to get their underlying integer representation nor create them from integers. In the "sensor" domain, I explicitly declare that I can create these values, meaning I can read the raw integers from some hardware, and turn them into their appropriate data types.

In the previous example, we saw how we wanted the fact that the "mechanics" domain uses the "integer arithmetic" domain to be private, but there are times when we don't want to allow this hiding. For instance, it's useful to definitively know whether a piece of code might write to disk, even if the write doesn't happen directly in that code.

I might also want to be able to enforce separation of concerns at a much higher level. Being able to enforce this separation is one of the cited benefits of a microservice architecture: it would be nice to be able to get this benefit without having to build a distributed system.

I believe part of the potential benefit of this is from going through the process of declaring what other domains a domain can access. It's often extremely easy to pull in another dependency or to rely on another part of our code without thinking about whether that makes conceptual sense. This is still possible in the system I describe, but by making the programmer be explicit, they are prompted to stop and think. I've made many bad decisions because I didn't even realise I was making a decision.

Some of this separation of domains is already possible: although I can't restrict access to language features, I have some control over what other modules each module can access: for instance, by using separate jars in Java, or assemblies in .NET. However, these are quite coarse and heavyweight: it's hard to use them to express the level of fine-grained control that I've described. The other downside is that by requiring a dependency, you normally end up being able to access its transitive dependencies: again, something that's often undesirable as previously described.

Using something like algebraic effect systems is probably more complex than necessary. The use of a language feature or domain could be modelled as an effect, but tracking this on an expression granularity is probably unhelpful: instead, tracking it by module is both simpler and more appropriate.

In fact, something like Java's annotations, C#'s attributes or Python's decorators are probably sufficient to express what domain each module resides in. You'd then need to separately define what power each domain has, which could be written in a comparatively simple declaration language. I suspect the difficulty comes not in implementing such a checker, but in working out how to use effectively, particularly what granularity is appropriate.

Topics: Software design, Language design

Nope: a statically-typed subset of Python that compiles to JS and C#

Sunday 22 March 2015 15:55

Nope is a statically-typed subset of Python that uses comments as type annotations. For instance, here's the definition of a Fibonacci function:

#:: int -> int
def fib(n):
    seq = [0, 1]
    for i in range(2, n + 1):
        seq.append(seq[i - 1] + seq[i - 2])
    
    return seq[n]

print(fib(10))

And here's a generic identity function:

#:: T => T -> T
def identity(value):
    return value

Since the types are just comments, any Nope program is directly executable as a Python program without any extra dependencies.

Having written your program with type annotations, you can now compile it to some horrible-looking JavaScript or C# and run it:

$ python3 fib.py
55
$ nope compile fib.py --backend=dotnet --output-dir=/tmp/fib
$ /tmp/fib/fib.exe
55
$ nope compile fib.py --backend=node --output-dir=/tmp/fib
$ node /tmp/fib/fib.js
55

Why?

A little while ago, I wrote mammoth.js, a library for converting Word documents to HTML. Since some people found it useful, I ported it to Python. Both implementations are extremely similar, and don't heavily exploit the dynamic features of either language. Therefore, a third port, even to a statically-typed language such as C# or Java, is likely to end up looking extremely similar.

This led to the question: if I annotated the Python implementation with appropriate types, could I use it to generate vaguely sensible C# or Java code? Nope is an experiment to find out the answer.

Should I use it?

This project is primarily an experiment and a bit of fun. Feel free to have a play around, but I'd strongly suggest not using it for anything remotely practical. Not that you'd be able to anyway: many essential features are still missing, while existing features are likely to change. The type-checking is sufficiently advanced to allow partial type-checking of the Python port of Mammoth.

I discuss a few alternatives a little later on, and explain how Nope differs. In particular, there are a number of existing type checkers for Python, the most prominent being mypy.

Examples

Simple functions

Functions must have a preceding comment as a type annotation.

#:: int -> int
def triple(value):
    return value * 3

Functions with optional and named arguments

Optional arguments are indicated with a leading question mark, and must have a default value of None. For instance:

#:: name: str, ?salutation: str -> str
def greeting(name, salutation=None):
    if salutation is None:
        salutation = "Hello"
    
    print(greeting + " " + name)

print(greeting("Alice"))
print(greeting("Bob", salutation="Hi"))

Note that the type of salutation changes as it is reassigned in a branch of the if-else statement. It is initially of type str | none, which is the union of the formal argument type and none (since it's optional). After the if-else statement, it is of the narrower type str, which allows it to be safely used in the string concatenation.

Variables

Most of the time, Nope can infer a suitable type for variables. However, there are occasions where an explicit type is required, such as when inferring the type of empty lists. In these cases, an explicit type can be specified in a similar manner to functions:

#:: list[int]
x = []

Classes

When annotating the self argument of a method, you can use the explicit name of the class:

class Greeter(object):
    #:: Greeter, str -> str
    def hello(self, name):
        return "Hello " + name

For convenience, Nope also introduces Self into the scope of the class, which can be used instead of referring to the containing class directly:

class Greeter(object):
    #:: Self, str -> str
    def hello(self, name):
        return "Hello " + name

As with local variables, instance variables assigned in __init__ can have type annotations, but will often be fine using the inferred type:

class Greeter(object):
    #:: Self, str -> none
    def __init__(self, salutation):
        self._salutation = salutation

    #:: Self, str -> str
    def hello(self, name):
        return self._salutation + " " + name

Generic classes are also supported, although the exact syntax might change:

#:generic T
class Result(object):
    #:: Self, T, list[str] -> none
    def __init__(self, value, messages):
        self.value = value
        self.messages = messages

Code transformations

To preserve some of the advantages of working in a dynamic langauge, Nope supports code transformations: given the AST of a module, a transformation returns an AST that should be used for type-checking and code generation. So long as the transformation and the original runtime behaviour are consistent, this allows you to use code such as collections.namedtuple:

import collections

User = collections.namedtuple("User", [
    #:: str
    "username",
    #:: str
    "password",
])

The current implementation is a bit of a hack, but the ultimate goal is to let a user specify transformations to apply to their code. Ideally, this would allow Python libraries such as SQLAlchemy to be supported in a type-safe manner.

And the rest

Nope also supports while and for loops, try statements, raise statements, destructuring assignment and plenty more. However, I've left them out of this post since they look the same as they do in Python. The only difference is that Nope will detect when inappropriate types are used, such as when trying to raise a value that isn't an exception.

I've started using Nope on a branch of Mammoth. Only some modules are currently being type-checked by Mammoth, such as html_generation.

If you're feeling brave, Nope has a set of execution tests that check and compile sample programs. It's the not the greatest codebase in the world with many unhanded or improperly handled cases, but feel free to read the tests if you want to dive in and see exactly what Nope supports. At the moment, Nope compiles to Python (which means just copying the files verbatim), JavaScript and C# with varying degrees of feature-completeness. The C# implementation in particular has huge scope for optimisation (since it currently relies heavily on (ab)using dynamic), but should already be fast enough for many uses.

Type system

Nope ends up with a few different kinds of type in its type system. It would be nice to be able combine some of these, but for the time being I've preferred to avoid introducing extra complexity into existing types. At the moment, Nope supports:

• Ordinary classes, made by using class in the usual way. Since inheritance is not yet supported, a type T is a subclass of itself and no other ordinary classes.
• Function types, such as:
  • int, str -> str (Requires two positional arguments of type int and str respectively, and returns a str.)
  • int, x: int, ?y: str -> int (Has two required arguments, the second of which can be passed by the name x. Has an optional third argument called y.)
• Structural types. For instance, we might define a structural type HasLength with the attribute __len__ of type -> int (takes no arguments, returns an integer). Any type with an appropriately typed attribute __len__ would be a subtype of HasLength. Currently not definable by users, but should be.
• Generic types. Nope currently supports generic functions, generic classes and generic structural types. For instance, the generic structural type Iterable has a single formal type parameter, T, and an attribute __iter__ of type -> Iterator[T], where Iterator is also a generic structural type.
• Type unions. For instance, a variable of type int | str could hold an int or a str at runtime.

What about IronPython or Jython?

Both IronPython and Jython aim to be Python implementations, rather than implementing a restricted subset. This allows them to run plenty of Python code with little to no modification.

Nope differs in that it aims to allow the generation of code without any additional runtime dependencies. Since the code is statically typed, it should also allow better integration with the platform, such as auto-complete or Intellisense in IDEs such as Visual Studio, Eclipse and IntelliJ.

What about mypy?

mypy is an excellent project that can type check Python code. If you want a project that you can practically use, then mypy is by far more appropriate. There are other type checkers that also use Python annotations to specify types, such as obiwan.

At this point, Nope differs in two main regards. Firstly, Nope's scope is slightly different in that I'm aiming to compile to other languages.

The second main difference is that Nope aims to have zero runtime dependencies. Since mypy uses Python annotations to add type information, programs written using mypy have mypy as a runtime dependency. This also allows some meta-programming with somewhat consistent type annotations, as shown in the collections.namedtuple from earlier:

import collections

User = collections.namedtuple("User", [
    #:: str
    "username",
    #:: str
    "password",
])

What next?

I'm only working on Nope in my spare time, so progress is a little slow. The aim is to get a C# version of Mammoth working by using Nope in the next few months. Although there might not be feature parity to begin with, I'd be delighted if I got far enough to get the core program working.

If, in a surprising turn of events, this turns out to work, I'd be interested to add effects to the type system. Koka is the most notable example I know of such a system, although I'll happily admit to being some unknowledgeable in this area. Thoughts welcome!

Topics: Software design, Language design

Fun with Prolog: write an algorithm, then run it backwards

Sunday 10 November 2013 21:21

Compared to most other languages, Prolog encourages you to write code in a highly declarative style. One of the results is that you can write an algorithm, and then run the same algorithm "backwards" without any additional code.

For instance, suppose you want to find out whether a list is a palindrome or not. We write a predicate like so:

palindrome(L) :- reverse(L, L).

We can read this as: palindrome(L) is true if reverse(L, L) is true. In turn, reverse(L1, L2) is true when L1 is the reverse of L2. We try out the palindrome predicate in the interpreter:

?- palindrome([]).
true.

?- palindrome([1]).
true.

?- palindrome([1, 1]).
true.

?- palindrome([1, 2]).
false.

?- palindrome([1, 2, 1]).
true.

So far, not that different from any other programming language. However, if we set some of the elements of the list to be variables, Prolog tries to fill in the blanks -- that is, it tries to find values for those variables so that the predicate is true. For instance:

?- palindrome([1, A]).
A = 1.

In the above, Prolog tells us that the list [1, A] is a palindrome if A has the value 1. We can do something a bit more fancy if we use a variable for the tail of the list, rather than just one element. [1 | A] means a list with 1 as the first element, with any remaining elements represented by A.

?- palindrome([1 | A]).
A = [1]

Prolog tells us that [1 | A] is a palindrome if A has the value [1]. However, if we hit the semicolon in the interpreter, Prolog gives us another value for A that satisfies the predicate.

?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1]

Now Prolog is telling us that [2, 1] is another value for A that satisfies the predicate. If we hit semicolon again, we get another result:

?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1]

This time, Prolog says A = [_G313, 2, 1] satifies the predicate. The value _G313 means that any value would be valid in that position. Another hit of the semicolon, and another possibility:

?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1] ;
A = [_G313, _G313, 2, 1]

We still have _G313, but this time it appears twice. The first and second element of A can be anything so long as they're the same value. We can keep hitting semicolon, and Prolog will keep giving us possibilities:

?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1] ;
A = [_G313, _G313, 2, 1] ;
A = [_G313, _G319, _G313, 2, 1] ;
A = [_G313, _G319, _G319, _G313, 2, 1] ;
A = [_G20, _G26, _G32, _G26, _G20, 2, 1] ;
A = [_G20, _G26, _G32, _G32, _G26, _G20, 2, 1]

In each of these possibilities, Prolog correctly determines which of the elements in the list must be the same. Now for one last example: what if we don't put any constraints on the list?

?- palindrome(A).
A = [] ;
A = [_G295] ;
A = [_G295, _G295] ;
A = [_G295, _G301, _G295] ;
A = [_G295, _G301, _G301, _G295] ;
A = [_G295, _G301, _G307, _G301, _G295] ;
A = [_G295, _G301, _G307, _G307, _G301, _G295] ;
A = [_G295, _G301, _G307, _G313, _G307, _G301, _G295]

Once again, Prolog generates possibilities for palindromes, telling us which elements need to be the same, but otherwise not putting any restrictions on values.

In summary, we wrote some code to tell us whether lists were palindromes or not, but that same code can be used to generate palindromes. As another example, we might want to implement run-length encoding of lists:

?- encode([a, a, a, b, b, a, c, c], X).
X = [[3, a], [2, b], [1, a], [2, c]] .

Once we've written encode, to work in one direction (turning ordinary lists into run-length-encoded lists), we can use the same predicate to work in the other direction (turning run-length-encoded lists into ordinary lists):

?- encode(X, [[3, a], [2, b], [1, a], [2, c]]).
X = [a, a, a, b, b, a, c, c] .

For the interested, the implementation can be found as a GitHub gist. One caveat is that the implementation of encode has to be written carefully so that it works in both directions. Although this might be harder (and much less efficient) than writing two separate predicates, one for encoding and one for decoding, using a single predicate gives a high degree of confidence that the decode operation is correctly implemented as the inverse of the encode operation. Writing a version of encode that actually works in both directions is an interesting challenge, and also the topic of another blog post.

(Thanks to Ninety-Nine Prolog Problems for inspiration for examples.)

Topics: Prolog, Language design

Functions and corresponding methods with the same name in Shed

Thursday 4 October 2012 20:47

In Shed, we sometimes define functions that usually delegate to a method, but also have some special cases or defaults if that method isn't implemented. For instance, the function represent should produce a string representation of an object. If the argument implements the method represent, it calls that method. Otherwise, it uses the name of the class of the object to generate the string. In code:

def represent fun(value: any) =>
    if isInstance(value, Representable) then
        value.represent()
    else
        defaultRepresent(value)

A problem arises when we want to call the function represent from within an implementation of the represent method. For instance, if we were implementing represent for the Some class:

def Some class(value: any) => {
    // Skipping the rest of the implementation of Some for brevity
    def represent fun() =>
        "Some(" + represent(value) + ")"
}

This code won't compile since we're calling represent with a single argument, value, but within the scope of the class, represent refers to the zero-argument function that implements represent specifically for Some.

There are several possible solutions to this problem, but the simplest one seems to be to use a different name for the method than for the corresponding function. For consistency, we can introduce the convention that the method name should be a simple variation on the function name. For instance, we might choose to use a leading underscore:

def represent fun(value: any) =>
    if isInstance(value, Representable) then
        value._represent()
    else
        defaultRepresent(value)

Although the leading underscore is perhaps a little ugly, that ugliness does help to reinforce the idea that you shouldn't be calling the method _represent directly. Instead, you should be using the represent method. More generally, instead of calling a method _foo, you should be calling foo (unless you're actually implementing foo).

Topics: Functional programming, Language design, Shed

Applicative functors in uncurried languages

Sunday 9 September 2012 20:47

Note: this post assumes you already have some familiarity with applicative functors

In this post, I'll show how to implement applicative functors in JavaScript, specifically for options, and then show an alternative formulation that's arguably better suited to languages that generally have uncurried functions (that is, languages that tend to have functions that accept multiple arguments rather than a single argument).

First of all, let's implement the option type (otherwise known as the maybe type) in JavaScript as a functor:

var none = {
    map: function(func) {
        return none;
    },
    
    bind: function(func) {
        return none;
    },
    
    toString: function() {
        return "none";
    }
};

function some(value) {
    return {
        map: function(func) {
            return some(func(value));
        },
        
        bind: function(func) {
            return func(value);
        },
        
        toString: function() {
            return "some(" + value + ")";
        }
    };
}

var functor = {
    map: function(func, option) {
        return option.map(func)
    },
    unit: some,
    applyFunctor: function(funcOption, argOption) {
        return funcOption.bind(function(func) {
            return argOption.map(func);
        });
    }
};

We can then use option values as applicative functors. Let's try our implementation out to make sure it behaves as we expect:

var four = some(4);
var six = some(6);

function add(first, second) {
    return first + second;
};

function curry(func, numberOfArguments) {
    return function(value) {
        if (numberOfArguments === 1) {
            return func(value);
        } else {
            return curry(func.bind(null, value), numberOfArguments - 1);
        }
    };
}

functor.applyFunctor(functor.map(curry(add, 2), four), six);
// => some(10)
functor.applyFunctor(functor.map(curry(add, 2), none), six);
// => none
functor.applyFunctor(functor.map(curry(add, 2), four), none);
// => none

Note that the use of the functor required us to curry the add function. This isn't a problem in functional languages such as Haskell, since functions tend to be curried by default. However, in languages that usually define functions to have multiple arguments (uncurried languages, for short), such as JavaScript, things get a little untidy.

My understanding of applicative functors is that they allow functors, or rather map, to be generalised to functions that accept more than one argument, such as add. Therefore, in an uncurried language, we might imagine the following cleaner API:

functor.applyFunctorUncurried(add, four, six);
// => some(10)
functor.applyFunctorUncurried(add, none, six);
// => none
functor.applyFunctorUncurried(add, four, none);
// => none

And such an API turns out to be not too hard to implement:

functor.applyFunctorUncurried = function(func) {
    var args = Array.prototype.slice.call(arguments, 1);
    return args.reduce(
        functor.applyFunctor,
        functor.unit(curry(func, args.length))
    );
}

Interestingly, the implementation of applyFunctorUncurried is most easily expressed in terms of the original applyFunctor. I've found cases like this explain why functional languages tend to favour curried functions: it often makes the implementation of higher-order functions such as applyFunctor much more straightforward.

This raises an interesting question: are these two formulations of applyFunctor of equal power? That is, is it possible to implement each in terms of the other? It's straightforward to see that we can implement applyFunctorUncurried in terms of applyFunctor since it's precisely the implementation above. What about implementing applyFunctor in terms of applyFunctorUncurried? This turns out to be pretty straightforward too:

function applyFunctor(funcFunctor, argFunctor) {
    return functor.applyFunctorUncurried(apply, funcFunctor, argFunctor);
}

function apply(func, value) {
    return func(value);
}

Please let me know if you spot mistakes in any of the above -- I've not exactly been rigorous in proof!

I'd be curious to know if there are any languages that include the alternative formulation of applyFunctor, and whether there are common cases where the original formulation is preferable even in uncurried languages.

Topics: Functional programming, Language design, JavaScript

Safer mutation: change the value, change the name

Saturday 16 June 2012 12:33

Many advocates of functional programming suggest that the concept of state, the idea that a value can change and mutate over time, makes reasoning about your program much harder, leading to more bugs. Most languages allow some form of mutability, and can therefore implement both functional and imperative algorithms, even if the preference is strongly towards immutability. In a completely pure functional language, mutability is entirely removed. Since some concepts are arguably easier to understand and implement when using mutable state, this can mean certain problems are harder to solve in a purely functional language. But what if we allowed a limited form of mutability in such a way that we still preserve many of the nicer properties of functional programming, such as referential transparency?

To take a simple example: suppose we want to append an item to the end of a list. In an imperative language, we might write something like this:

list.append("first")

so now list has an extra item, meaning that the original value of list no longer exists. In a functional programming language, we'd create a new value instead of mutating the original list:

val longerList = list.append("first")

We can now use both list and longerList, since list was not modified during the append. This means we never need to reason about what state list is in – its value never changes. The trade-off is that a functional append tends to be more expensive than an imperative append. If we don't actually want to use list again, then this is arguably a bad trade-off. What if we could allow the list to be mutated under the covers, but still be able to present a programming model that appears to preserve immutability? So, we write the same code:

val longerList = list.append("first")

but list is now implemented as a mutable list. The compiler must now ensure that list is never used after the append operation. This means the actual implementation is effectively the same as when written in an imperative style, but we ensure that whenever we change the value of an object, we also change the name used to access it.

This approach does have some severe limitations. For instance, sharing mutable state between many objects is likely to be impossible. If we allowed mutable state to be shared, then mutating that state inside one object would require marking all objects that hold that state to be unusable. In general, having the compiler keep track of this is likely to be unfeasible.

Yet this sharing of mutable state is arguably the worst form of mutablility. It means that changing something in one part of your system could change something in another far away part of the system. This idea of changing the name whenever we change the value is most useful for mutability in the small, when we just want to implement a particular algorithm efficiently.

However, there still might cases where you'd quite reasonably want to share mutable state between, say, just two objects. The more interesting question is: is it possible to handle this case without requiring the user to write an excessive number of hints to the compiler?

Topics: Language design, Functional programming

What is the expression problem?

Sunday 27 May 2012 21:00

View interactive version of this post

datatype node
    = LiteralNode of real
    | AddNode of node * node

datatype node
    = LiteralNode of real
    | AddNode of node * node
                
fun evaluate (LiteralNode value) = value
  | evaluate (AddNode (left, right)) = (evaluate left) + (evaluate right)

datatype node
    = LiteralNode of real
    | AddNode of node * node
    
fun evaluate (LiteralNode value) = value
  | evaluate (AddNode (left, right)) = (evaluate left) + (evaluate right)
  
fun nodeToString (LiteralNode value) = Real.toString value
  | nodeToString (AddNode (left, right)) =
        "(" ^ (nodeToString left) ^ " + " ^ (nodeToString right) ^ ")"
  

datatype node
    = LiteralNode of real
    | AddNode of node * node
    | NegateNode of node
    
fun evaluate (LiteralNode value) = value
  | evaluate (AddNode (left, right)) = (evaluate left) + (evaluate right)
  | evaluate (NegateNode term) = ~(evaluate term)
  
fun nodeToString (LiteralNode value) = Real.toString value
  | nodeToString (AddNode (left, right)) =
        "(" ^ (nodeToString left) ^ " + " ^ (nodeToString right) ^ ")"
  

datatype node
    = LiteralNode of real
    | AddNode of node * node
    | NegateNode of node
    
fun evaluate (LiteralNode value) = value
  | evaluate (AddNode (left, right)) = (evaluate left) + (evaluate right)
  | evaluate (NegateNode term) = ~(evaluate term)
  
fun nodeToString (LiteralNode value) = Real.toString value
  | nodeToString (AddNode (left, right)) =
        "(" ^ (nodeToString left) ^ " + " ^ (nodeToString right) ^ ")"
  | nodeToString (NegateNode term) = "-" ^ (nodeToString term)
      

public interface Node {
}
            
public class LiteralNode implements Node {
    private final double value;

    public LiteralNode(double value) {
        this.value = value;
    }
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;

    public AddNode(Node left, Node right) {
        this.left = left;
        this.right = right;
    }
}
      

public interface Node {
}
            
public class LiteralNode implements Node {
    private final double value;
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;
}
      

public interface Node {
    double evaluate();
}
            
public class LiteralNode implements Node {
    private final double value;
    
    public double evaluate() {
        return value;
    }
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;
    
    public double evaluate() {
        return left.evaluate() + right.evaluate();
    }
}
      

public interface Node {
    double evaluate();
}
            
public class NegateNode implements Node {
    private final Node term;
    
    public double evaluate() {
        return -term.evaluate();
    }
}

public class LiteralNode implements Node {
    private final double value;
    
    public double evaluate() {
        return value;
    }
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;
    
    public double evaluate() {
        return left.evaluate() + right.evaluate();
    }
}
      

public interface Node {
    double evaluate();
    String nodeToString();
}

public class NegateNode implements Node {
    private final Node term;
    
    public double evaluate() {
        return -term.evaluate();
    }
}
            
public class LiteralNode implements Node {
    private final double value;
    
    public double evaluate() {
        return value;
    }
    
    public String nodeToString() {
        return Double.toString(value);
    }
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;
    
    public double evaluate() {
        return left.evaluate() + right.evaluate();
    }
    
    public String nodeToString() {
        return "(" + left.nodeToString() + " + " +
            right.nodeToString() + ")";
    }
}
      

public interface Node {
    double evaluate();
    String nodeToString();
}

public class NegateNode implements Node {
    private final Node term;
    
    public double evaluate() {
        return -term.evaluate();
    }
    
    public String nodeToString() {
        return "-" + term.nodeToString();
    }
}
            
public class LiteralNode implements Node {
    private final double value;
    
    public double evaluate() {
        return value;
    }
    
    public String nodeToString() {
        return Double.toString(value);
    }
}

public class AddNode implements Node {
    private final Node left;
    private final Node right;
    
    public double evaluate() {
        return left.evaluate() + right.evaluate();
    }
    
    public String nodeToString() {
        return "(" + left.nodeToString() + " + " +
            right.nodeToString() + ")";
    }
}
      

Topics: Language design

Solving the expression problem with union types in Shed

Monday 30 April 2012 22:31

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 extended 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

Shed programming language

Monday 30 April 2012 21:52

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

The impurity of object identity

Thursday 23 February 2012 13:22

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