Archive for July, 2005
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
Gnus, the Emacs mail/news/whatever reader, has built-in support for RSS, which, in theory should allow one to read blogs like this or LtU without having to leave the comfortable surroundings of Emacs.
The instructions at MyGnus were good enough to get me going, but the result is quite unsatisfactory. Firstly, gnus throws a fit when trying to retrieve the RSS for this blog, though the LtU blog is fine. TonyG suggests this may be due to namespace prefixes. Secondly, the body of RSS feeds tends to be HTML, which looks hideous when rendered by Emacs.
So for the time being I’ll stick to web browsers for blog reading.
July 15th, 2005
matthias
This is a simple-minded (and slightly weird) Lisp interpreter for Squeak Smalltalk. It doesn’t have a REPL under Morphic, but I’ve hacked on it to provide a minimal Morphic UI.
It got me thinking about Lisp Machines again. What if the existing Squeak infrastructure could be exploited to build a Scheme Machine? The minimal addition required to the Squeak VM would be a tail-call opcode. Once tail calls are possible, a compiler could be written to take Scheme code to Squeak bytecode. A full module system could be implemented fairly easily, thanks to Smalltalk’s non-separation of compile-time and runtime. The mapping between Smalltalk constructs and Scheme Machine constructs might be:
| Scheme Machine | Smalltalk |
|---|
| Module | Class |
| Module instantiations | Instances |
| Global variables | Probably wouldn’t be implemented — you’d use module-local variables instead, just like MzScheme’s module system |
| Module-local functions | Instance methods |
| Module-local variables | Instance variables |
Integration with the debugger might be tricky. Many system utilities expect to be able to decompile bytecode into Smalltalk; a major refactoring might be needed for multi-language integration within Squeak. One would have to tag each method with the decompiler to use, update each UI widget to display these annotations etc.
July 15th, 2005
tonyg
TiddlyWiki is a wiki that runs entirely within a single page, on the client side of the browser. Javascript and CSS are used to control the visibility and layout of the various subpages. Normal WikiLinks provide linkage between subpages. It’s a very elegant piece of work - and since the entire site is contained in a single document (editable directly in your browser) it seems almost ideal for version-controlled project documentation. (Merging and conflict resolution might be a little more manual than is usual for code.)
mikeb and I have been toying with the idea of some kind of hybrid between (Mac OS) Stickies and Wiki ideas — TiddlyWiki might provide a good start for something of the sort.
July 15th, 2005
tonyg
I have been playing with AVISPA recently, a tool to model protocols and check them for security vulnerabilities. Overall this is quite an impressive piece of software. The installation is painless, the documentation is good, and it has some neat features, like the presentation of attack traces as Message Sequence Charts.
It is quite amazing, and scary, how even the most trivial protocols (I tried some with just a handful of messages) are subject to non-obvious attacks. However, I am still not convinced that tools like AVISPA, certainly in their current incarnations, are good enough to find these attacks without the user having thought of them in the first place. In my, admittedly limited, experience, vulnerabilities are usually found in the process of constructing a formal model. Checking the model merely serves as a confirmation. Indeed it is often the case that some effort is required to bend the model into a shape that allows the model checker to detect the attacks.
July 14th, 2005
matthias
Vitaly ran into peer-moderation today by posting a pointer to Jumbo, which supports meta-programming for Java.
Tom said:
[…] it looks lovely, but what i fail to understand is why this is
better as an extension for java, rather than using a lisp-like language,
which is much more suitable for compile-time computation (and of course
for code manipulation)
is there anything java (the language) gives you that one should be so
keen to preserve?
The closing question prompted some wry comments on the state of Java’s standard libraries and support for concurrency. Meanwhile, Vitaly defended using Jumbo:
Sure Lisp-like languages are much better in this field. They have
only one flaw - they’re
not accepted by the majority of the industry. So, sometimes using this
sort of workarounds
is the only way - Java-only programmers will be happy, and Lisp
programmers will be happy
to see this functionality in Java.
Everyone cannily avoided the invitation to meta-discussion about the ‘industry’, and instead digressed into talking about what support there is in LISP for concurrency. Vitaly held up Bigloo, explaining that there were thread primitives to build on and that any ugliness can be hidden in macros — which brought us almost full circle.
July 13th, 2005
mikeb
Next Posts