Archive for July 18th, 2005
This paper is hard going, but very rewarding. The author concentrates on two ways of transforming a formal, algebraic specification into an implementation, starting with very simple examples and working up to a pretty-printing library.
The reason this paper is worthwhile is that, by moving very slowly and by demonstrating the same theme over and over, each time using a slightly more complex example, the author allows the reader to develop a clear insight into the connection between the terms and the coterms of an algebra.
The two styles of implementation he explores are taking the terms of an algebra and building a datatype from them more-or-less directly, and taking the coterms (or contexts) of the algebra and using them as the core of the datatype instead. Equational reasoning from these starting points leads to dual implementations of the semantics of the specification.
The programs based on terms seem natural to me — reasoning with coterms is awkward at first — but coterm-based programs reify far more detail of the ongoing computation, in a way reminiscent of the design of a custom interpreter for a domain-specific language. To get access, from a term-based solution, to the information that is explicitly represented in a coterm-based solution, you would need to make use of reflective primitives in the host language.
It’s intriguing, the way reflection unexpectedly appears in the mirror-image of a data structure…
July 18th, 2005
tonyg
I figured it was about time to try out java generics, so I decided to write some list processing primitives, and a Pair class that implements java.util.Collection. I intended to then use these to re-write my C3 implementation for Java more like the original Dylan it was adapted from.
There are a few articles around about implementing enumerators in languages without call/cc:
The reason to create Pair which implements java.util.Collection is that its really convenient to construct collections using cons in functions passed to fold.
My various enumerators all take Collection rather than Pair - since they are just as easy to implement that way. Notice that Collection.iterator() is all I need, so I decided not to require List. Also, its impossible for Pair to implement List efficiently.
The enumerators I have implemented so far are forEach(), foldLeft(), foldRight(), map()
Some other useful functions are all(), any(), and zip(), which were all used in implemented Pair.equals()
Of course java has the added the challenge of not being tail-recursive. foldRight() can’t be implemented recursively, since that is likely to cause a stack overflow. Instead, it uses ListIterator.hasPrevious() and ListIterator.previous(), after the collection is copied into an array list if neccessary. Obviously Java’s limited stack makes it a good idea to use foldRight().
I wanted to make array based variants zip, map, all and any, however problems with generics and arrays have made that impossible so far. Thats a shame, because it makes Pair.equals() fairly in-efficient.
July 18th, 2005
david
We are trialling a new coffee machine. The old one is a percolator with two hotplates. The new one is hermetically sealed, has a fascia that coordinates well with hi-fi componentry, and makes variations on espresso that I haven’t heard of with a single button press.
There is a certain satisfaction in the fantasy that one is ‘making’ coffee by replacing the filter and grinds in the percolator; however, the inescapable truth is that this machine straight from Area 51 makes better coffee, even if we can’t see how it is doing it.
July 18th, 2005
mikeb
Having been helping and tinkering with a functional library for Java, I’ve come across real issues with Java and its arrays. Consider:
public static < T > T[] makeArray() {
T[] array = (T[]) new Object[5];
return array;
}
public static void main(String[] args) {
Integer[] ints = Test.< Integer >makeArray();
}
The assignment in main blows up with a ClassCastException. Using the Eclipse debugger, the JVM thinks that the array is an Object[]. So the cast has basically been ignored. This is correct behaviour for Java’s arrays which you can never cast down anyway: Integer[] ary = (Integer[]) new Object[] {1,2,3,4,5}; blows up with the same exception.
If you look at the ArrayList implementation you’ll see how they get around it. The array backing the list is never actually returned. Instead it is always copied. So now:
public static < T > T[] makeArray(T[] input, T... elems) {
T[] array = (T[]) new Object[elems.length];
System.arraycopy(elems, 0, array, 0, elems.length);
System.arraycopy(array, 0, input, 0,
Math.min(input.length, array.length));
return input;
}
public static void main(String[] args) {
Integer[] ints = Test.< Integer >makeArray(new Integer[0], 5, 4, 3, 2, 1);
}
This now works. However, were you trying to do this in a library, as I was, you may need to pass in a generic array which you can’t create which is the reason for the cast in the first place. Fun
July 18th, 2005
matthew