I got an email early this morning that my paper has been accepted to SOFSEM, which is fantastic news. I hadn’t expected it to be accepted, really; rather, I was more interested in getting good feedback from the referees, which I did get. And one referee gave some good papers too for more reading.

The paper introduces a restricted functional programming language which disallows recursion, but offers a special syntax for catamorphism. Catamorphisms are a general mechanism for “iterating through” some algebraic data structure. Over the lists, a catamorphism is just a fold—in fact sometimes I just call catamorphisms “generalized folds”. Over the natural numbers, a catamorphism is just a bounded loop, such as a for loop offered in many other languages. Anyway, the language without recursion but with catamorphism is equivalent in power to the primitive recursive functions, and provides a good model for trying to attack programs from a static analysis standpoint.

The paper that was accepted is just an introductory paper, and really I think the most exciting parts of it are in the motivation and in the considerations for future work. The end goal is to come up with algorithms to determine, statically, the running time and memory consumption of a program written in this language. As every program in this language halts, these things are certainly possible, but I think structuring them as catamorphisms mean that we should be able to get some good efficiency, and with reasonably accurate results too. The primitive recursive functions are more than powerful enough to do “useful” things in: they encompass the entire exponential hierarchy.

Anyway what was most exciting, beyond it getting accepted I suppose, is that the referees generally seemed to agree with me that it’s an interesting area of research.