Knew I Couldn't Stay Away

In this post, I said that I was done with language hacking for a while.

Well, I guess I can't stay away from it. Mattia Barbon has been running the Language::P project for a while now, over on github, and I've agreed to give him a hand with the Java backend pieces of that project.

The current state is that he has a Perl5 parser, which covers a reasonable (and improving) subset of P5. The parser is written in Perl5, and currently outputs a packed bytecode format (consisting of P5ish opcodes).

He has a branch containing a .NET backend which uses DLR expression trees, and I've started work on a Java backend.

My initial target is an interpreter, but I have several pieces which I would hope to use in an eventual compiler.

The current aim is to support enough of P5 for the Language::P parser to parse itself, and from there to bootstrap parsers in the target backends. For an interpreted backend, such as my current Java prototype, this will mean shipping a packed bytecode parser for the interpreter to fire up. For compiled backends, other avenues are possible.

Both the .NET and Java parts are currently on private branches, but I hope to make the code available soon, and merge to HEAD.

If anyone wants to help, please leave a comment / email me.

Spring 2.5 and Eclipse 3.5 JUnit Problems

Spring 2.5 test classes (eg those that use @RunWith(SpringJUnit4ClassRunner.class) ) implicitly rely on a class which was removed in JUnit 4.5

See this Jira: http://jira.springframework.org/browse/SPR-5145

Unfortunately, the latest Eclipse (3.5) ships JUnit 4.5 by default, meaning that the newly-production Eclipse version is broken for running tests written for the current production Spring version.

No workaround is currently available (and "use Spring 3.0" as a resolution isn't very helpful for production stuff - it's still in beta) - I will investigate with the Eclipse people as to whether anything (eg a downgrade of the JUnit plugin to 4.4 would be feasible) but don't hold out much hope.

For now, looks like it's back to running Spring tests from the command-line with a local JUnit 4.4 jar on your classpath.

(Btw, if anyone does have a good workaround, please let me know.)

Thanks For All The Fish

One of the major themes of the blog so far has been my attempts to write a version of (perhaps a subset of) Perl 5 that will run on the JVM, and/or find out what makes this a difficult exercise. And, to have fun while doing so.

For reasons which I outline in this post, I think it's time to give up, and I would strongly encourage anyone reading who is tempted to have a go at carrying on where I'm leaving off to think again. The code we wrote is out there, but I would suggest that anyone who's really interested contact me first.

So, here's the lowdown on the problems we faced.

There are really two separate sets of issues - first of all there are issues related to nullability.

Because Perl does not require brackets around function parameters, and has functions which do not need to specify their prototypes, then this line of code:

my $a = dunno + 4;

can be parsed in one of two ways:

• $a gets 4 + the result of calling the function dunno(), which takes no arguments. That is, + is treated as a binary operator
• $a gets the result of calling dunno(4), where dunno takes at least one argument. That is, the + is treated as a unary operator on 4.
  

This line of argument is expanded upon significantly by Jeffrey Kegler at http://www.perlmonks.org/?node_id=663393 - where he links it to Halting. I have not fully satisfied myself of the full implications yet, but the initial points amount to a hugely significant parsing problem, with no real good solution.

The second source of problems is that Perl 5 is old (1994) - and dates from a time when automated language tools were rather more lacking than they are today. When Larry Wall was working on the first versions of p5, lex and yacc were pretty much the state of the art in terms of what was practical for autogeneration, and a skilled practitioner could outperform them by modifying the output, or writing from scratch.

Perl wasn't written with formal parser theory in mind, and has now reached the stage where the implementation is really all we have. It does not fit well into a rigorous model of language, and during its development flexible language features were considered to be more important than linguistic concerns (such as static analysis).

Simply put, there's no grammar, and attempting to write something which matches the only existing implementation is a major undertaking - no existing automated language tools will help much, it's largely a matter of needing to completely reimplement the existing C code in Java (or bytecode). This is a huge amount of work, if it's possible at all, and is not going to be fun - and will be likely to be very frustrating for a large chunk of the time spent on it.

So, here we are. I've had a lot of fun working on this (and particular thanks to James Laver and Shevek, both of whom provided insight, help and encouragement - and to the many other people in the Perl, Java and Ruby worlds with whom I had interesting and sometimes amazing conversations) and I'd like to close with a short summary of what I've learned from this project:

• Too much backwards-compatibility is a huge millstone
• Always ensure that the people you're talking to have the same definitions you do
• If you're going to use formal language, you must have proofs available. Declaring a problem to be in a particular class by fiat does not help anyone.
  
• Perl's block / closure / subroutine definitions are too overlapping and unclear. This is a major problem
• Indirect object syntax in Perl 5 was a misstep

So, that's it for now.

I'll be moving on to other problems on my stack now, so my next posts will be about broader topics than just language design / implementation but I'm sure I'll return to language design in due course - after all, I just can't seem to stay away from it.

My Interview Checklist

Someone asked me recently about what sort of job interview prep I do, and having recently found myself a new job, I thought I'd post a sample here.

This is the bare bones of what I polished before my most recent job hunt. It's skewed towards Java for some of the actual technology bits, but the CS fundamentals should be language-independent.

My attitude is that the working practitioner should have a good command of a lot of this (especially the CS topics) at all times, and should only need to briefly revisit each subject to ensure the polish and the details are 100% there.

The books I used most heavily were "Introduction to Algorithms" (Rivest et al) and Doug Lea's "Concurrent Programming in Java".

Comments and suggestions for things other people have found useful would be most welcome.

Algorithms
Details of order notation (eg Omega etc)
Mergesort
Quicksort
String Matching
NP / NP-completeness

Trees
Basic Trees and Tree Construction
Red / Black Trees
Hashing / Hashtable
HashMap / TreeMap
B-Trees

Graphs
Representations of Graphs in code (object / pointers, matrix, adjacency list)
Graph Traversal (BFS, DFS)
Minimal Spanning Tree
Dijkstra

Discrete Maths / Probability / "Logic Puzzles"
Probability Exercises
Decision Trees Exercises
n-choose-k Problems
Permutation Groups, Cycle, Reprns, etc
"Perfectly Logical Beings" puzzles
Decision / Ply problems (eg Monty Hall)

DB / Hibernate
Normal Form
Having clause
Outer joins
XML Form of Hibernate - Basics
JPA / Hibernate
Indexes and Optimisation

Java Internals and Details
Bitwise operators
Collections / Generics nitty-gritty (ie to bytecode level)
OO nitty-gritty (and nasty edge cases)
Annotations nitty-gritty
Arrays nitty-gritty

OS/Concurrency details
Safety, Liveness, Performance, Reusability
Permanent Fail: Deadlock, Missed Signals, Nested Monitor Locks, LiveLock, Starvation, Resource Exhaustion, Distributed Fail
Immutability
Block-structured Locking, Synchronisation, JMM, Fully Synchronized Objects
Other Constructs: Mutex, Latch, Futures, Callable / Command Adapter
Real-world multithreaded application development

Future Web Tech
HTML 5
ECMAScript 4 hassles
Flex vs Silverlight (ref issues with LCDS and the Adobe approach)
Asynch Messaging for webapps

Last Night's Dynamic Languages Meeting

Yesterday evening, a group of us gathered to talk about dynamic languages, at the British Computer Society in London. The format of the evening was lightning talks - ie 5 minutes per talk - on any subject connected with dynamic languages.

There were a lot of great talks given - from using Ruby for systems programming to improving the test coverage of PHP.

I spoke about the JVM / MLVM as a platform for dynamic languages - my slides are here.

It was really great to meet a lot of people from different parts of the dynamic languages world - especially Rob and Zoe from IBM's sMash / Zero implementation of PHP.

Many thanks to the BCS for hosting, Leon from London.pm for organising it and Billy for being the liason with the BCS. Hopefully there'll be another similar event soon.

Status Update

It's been a while since last update, largely being driven by my not having many cycles.

The grammar rewrite for p5vm is coming on well, but is still being debugged.

If there's anyone reading who is very good with SableCC (or shift-reduce parsers in general) and could spare a few hours helping us debug the new grammar, please get in touch.

I'm giving a lightning talk at the British Computer Society tonight about some of the work being done to put dynamic languages on the JVM - slides will appear here tomorrow.

State of Play for Perlish PoC

First off, the slides from my talk are here.

A tarball of a Mac MLVM (OpenJDK7 with invokedynamic) dating from 2009-04-10 is here.

So, where are we with the code?
The current codebase uses SableCC, an automated parser generator to transform an EBNF grammar into a parser, lexer, etc.

I'm not saying that's the most powerful way to do it, or that it will ultimately suffice for a reasonable stab at getting Perl onto the JVM. It was simply what was to hand that I had a modicum of experience with and with which I could up to speed with some necessary chunks of parser theory in order to get off the ground.

My current grammar has a number of deficiencies, mostly because I cobbled it together by cribbing from some pre-existing grammars which parse Java and PHP.

Longer term we may need either or both of: a more subtle grammar and/or a parser written in Java (basically, a port of the existing C-based parser to Java, but one which tries to stay out of the later phases of compilation).

In terms of code generation, I have two branches - one which uses a homegrown ASM codegen, and one which translates the AST to JRuby's AST, and then uses JRuby's codegen (which is also based on ASM).

Going forward, the semantic differences between Perl and Ruby (notably Everything-Is-An-Object and string handling) probably make AST translation not viable as a long-term strategy.

However, one thing which did occur is if there are parts of the JRuby codegen libs which could be refactored out into a separate package that we could use for Perl / other langs, that would be helpful.

In addition, when designing the AST for use with a homegrown ASM-based codegen, a good hard look at the JRuby AST seems like a good plan - the scoping constructs that they use are directly relevant to Perl, for example (although I'm aware that for performance reasons, they may need to optimise how they handle scope constructs).

Places to get started

• A better grammar. One quick way to improve the current situation is to improve the quality of the EBNF grammar. The current grammar is here. It may not be the long term plan, but making progress with what we've got in advance of a parser port should help to figure out issues and will help momentum


• Design session for how to handle Perlish dispatch in full generality. This is probably the most fundamental design issue which needs to get nailed right now. I have some ideas about how to do it, but they need validating and the input of others. If there's interest, I suggest we get together in the back room of a pub or cafe in London one afternoon and thrash this out.


• Test cases. Having a set of test cases (grouped by complexity - ie low-hanging fruit first) would be very useful. Ultimately, we want to run as much of the test suite as possible, but little acorns are the first step...


• Starting up a wiki or similar to track know issues with syntax and semantic issues (eg the semantic issues around 'new', GC, etc)


• Help from a guru who understands the OP representations. This would be really useful in starting to think about the ultimate form of the parser.

If any of these are appealing, especially the dispatch design task, please get in touch.