cdiggins.com

A common design pattern (or at least I thought it was common) is to place objects with expensive allocation and/or deallocation in an object pool when they are no longer needed, and reusing object from the pool instead of allocating when needed.

This was absent from popular design pattern lists such as Wikipedia and Ward’s Wiki, so I added them: http://en.wikipedia.org/wiki/Creational_pattern and http://c2.com/cgi/wiki?ObjectPoolPattern .

The MSIL and JVML bytecode lack higher-order instructions. In other words no instructions allow you to treat instructions as data. It seems many people think that to add such a feature would incur a huge overhead, and force one to use dynamically typed (or untyped if you prefer) techniques. Anyway, this is what some recent posts on Lambda-the-Ultimate.org would seem to indicate.

This is precisely what Cat is about, adding higher-order instructions to stack-based languages in a type-safe manner. That means that the stack configuration can be statically determined in advance, and byte-code verifiers (which are simply type-checkers) can verify that the code is safe. It can also be done efficiently.

It is very eye-opening that after all of my posts on Lambda the Ultimate about Cat, that one rather important fact wasn’t caught by many readers. I also thought it was so was a completely obvious fact that you can add higher order functions to a stack-based language in a type-safe manner. This is the problem of research, you get so wrapped up in something, you forget what other people know, don’t know, or think they know.

Looks like I am going to have to write another paper. :-)

I have never been a big fan of algebraic data type pattern matching in functional langauges like Scala, Haskell, OCaml, and F#. I’ve always felt that because data type pattern matching relied on the structure of a data type it broke encapsulation and increased code coupling. Martin Odersky (designer of Scala) is a pretty strong advocate of data type pattern matching, and wrote this interesting article at Artima.com on the pattern matching debate. Having said that I have also felt that data type pattern matching was an important area of research and offered promise to yield powerful language features for flexible and large scale software development.

Don Syme (designer of F#) recently wrote a draft of a paper where he states “[...] it is well known that [pattern matching of algebraic data types] interacts poorly with abstraction.” which is similar to what I’ve long held. In the paper however he proposes a solution that is more abstract if you will. Perhaps data type pattern matching has hope?

I’ve just made a new release of Cat (version 0.10.4). I’ve fixed several bugs in the standard library, added some new functions, renamed a couple of functions, and added a turtle graphics library (a la Logo). The graphics library is still in its early stages but I was able to generate the following image:

The program for generating this pattern is:

#load graphics.cat
window [blue pc 5 pw [100 square 15 rt] 24 repeat] render
“c:\tmp\tmp.png” save

• window = create graphics window 
• pc = set pen color
• pw = set pen width
• square = draw square
• rt = right turn
• render = tell window to execute the function

To permute (shuffle) a stack in any way possible I only need two operations “dip” and “swap”. Using these functions I can construct a “bury” instruction for placing an item from the top under any number of items. I can also create a “dig” instruction for taking the item under top X items in the stack and placing it on the top.

Here’s how.

As far as I am concerned there are only really two ways to iterate over a list, get an iterator (e.g. IEnumerable) or pass a function to the list (e.g. through a ForEach method). The old way was to use an indexer … thank god that that is going the way of the dodo.

To see the two methods in action take a look at Wes Dyer’s post All About Iterators for an in-depth discussion on IEnumerable and iterators. For an example of the other approach take a look at my C# functional list library: http://functional-lists.googlecode.com/svn/trunk/FunctionalList.cs.

Here are my observations:  

• If I was writing a compiler I would be able to implement a ForEach method extremely efficiently by inlining the call.
• The iterator is essentially a fancy pointer, and naive usage (like squirreling it away for reuse later) can lead to subtle bugs.
• A ForEach method is more encapsulated, the task is passed to the list rather than the list exposing something (i.e. an iterator) about its internals.
• An iterator has to pass each element into the iterator, and then the consumer will take the element out of the iterator: two copies instead of one.

Which method do you prefer, and why?

I’ve finished the final revision of the paper Typing Functional Stack-Based Languages and submitted it to ICFP 2007 today. The abstract was rewritten (for the umpteenth time). Hopefully it now has enough “zing” to capture the reviewer’s interests. Though many theorists have already been quick to dismiss the work, much to my chagrin. I’ve been around the block now enough.

Let me sum up the paper this way: “making stack-based languages functional in a type-safe way is easy, here’s how.”.

If anyone thinks that this isn’t important work should think about why it is that you can’t push instructions onto the stack in MSIL or JVML, and how hard it is to translate a functional language to these targets.

I added articles to the Cat wiki today on several topics including kind systems, type theory, and Russell’s paradox. Hopefully you find them interesting and informative. Please let me know if anything is confusing or erroneous.

We had an interesting and productive meeting of the SeaFunc - Eastside group yesterday. I wrote out the meeting notes, and they can be browsed online at: http://tech.groups.yahoo.com/group/SeaFunc/message/552?threaded=1 

This was a lot of work, and I doubt I’ll be as thorough next time around.

I’ve just completed a new article on the Cat wiki HowTheInterpreterWorks that describes the inner workings of the Cat interpreter. Hopefully it will be helpful to other people who want to write their own interpreters and compilers.

Any questions or suggestions would be most welcome!