cdiggins.com

I am currently conducting a research survey with Dr. Abdelwahab Hamou-Lhadj at Concordia University in order to understand the role of diagrams in UML and software development. The goal is to find ways to improve the experience of constructing software implementations and models.

I would really appreciate however could take a moment to answer the short 15 question survey at http://www.questionpro.com/akira/TakeSurvey?id=981322

We will be sharing the results in a publicly available technical report.

Thanks!

I have just posted some screen-shots of the upcoming Heron IDE at http://www.heron-language.com along with the first draft of the new Heron specification at http://www.heron-language.com/spec.html.

I use WordPress as my content management system, and it got hacked again. So I had to upgrade again. My old themes got corrupted. Just to make sure I am really irritated the upgrade caused “” to appear everywhere. Boy am I annoyed. I just wish I had the time to roll my own blogging system.

You’ll notice that I abandoned twitter. I am too busy now to spend all my time telling people what I am doing every minute of the day. In short: I am implementing an IDE for Heron. It is shiny and impressive. I’ll tell you about it “real soon now”.

I officially like C# extension methods. They can be used to create traits. That’s it, just thought I’d share this with you.

Here are some of the things I have been up to:

• Looking at using Cat as a replacement for the SECD machine to express operational semantics of Heron (see http://lambda-the-ultimate.org/node/2787)
• Developing the Heron to Cat interpreter (sorry no demos yet). This requires the introduction of local definitions in Cat to emulate labels and gotos.
• Figuring out how a simple transform for Cat code so that a value can be passed from function to function on the top of the stack.
• Trying to figure out how to fix the type system to allow proper handling of nested forall polymorphism without annotations. System-I looks promising for this task,  but it is very complex. There has got to be a better system. I am seriously considering embedding the full Lambda Calculus, or possibly even Cat itself, directly in the type-system and saying sayanora to decidability.
• Wondering why my recent blog post on Composition vs Inheritance received such a lukewarm reception on Reddit. It seems to me that interface forwarding (or delegation as I called it) is an incredibly important feature, but no one cares.

I have been thinking a lot about how to extend the Cat type system so that I can handle objects. The big challenge is to do this in a way that doesn’t add any significant complexity to the language. This is particularly hard to do for a language as small and tight as Cat.

Previously I was thinking about starting with tuples. Not only are tuples nice on their own, but the type of an object is essentially a tuple. There is one simple way to add tuples, which is to represent them as dynamically constructed functions. E.g. ( -> ( -> int string)) which would be a tuple containing an int and a string. The challenge occurs when I try to get values in and out of that function? I want something like: “get0″, “get1″, etc. which gets the value from the appropriate slot. This is trivial to code, but the problem is that I can’t express the type of “getN” in a general enough manner. Consider

get0 : (( -> ‘A ‘b) -> ‘b)
get1 : (( -> ‘A ‘b ‘c) -> ‘b)
get2 : (( -> ‘A ‘b ‘c ‘d) -> ‘b)
…

This works fine, but we can only write so many of these (perhaps a dozen or so) before they start to become unmanageable. The problem then becomes that we would have to limit the number of field accessors, and hence the number of fields to a relatively small and arbitrary number. That is extremely limited, and nearly useless in practice when we can easily imagine objects with hundreds of fields or more. It will also put a horrible strain on the type reconstruction and checking algorithms.

Sidebar: I will probably limit the number of fields to 255 anyway for several reasons:

• there has to be some stated upper limit
• too many fields represents a horrible flaw in the design of OO software
• it is is trivial to extend the 255 limit using aggregation (putting objects in objects)
• Cat is designed to run on small memory systems, so being able to represent the index of a field with a single byte is appealing.

There is another subtle problem (or benefit depending on your point of view) and that is that this approach automatically provides structural subtyping. In other words two types that are structured the same will always be treated as exactly the same type. While this is useful in some circumstances, it is not good to paint ourselves in to such a corner. It is very important for software modularity and correctness to be able to construct two different types with similar structure when needed. 

The following is an entirely different approach that I am now seriously considering using. First I will approach the problem of objects and use those to build tuples.  

object IntString { x : int; y : string; }
6 “the answer is ” IntString.new x.get 7 * x.set
y.get write x.get writeln

So what is the type of the constructors, setters, and getters? Well I propose that the types are:

IntString.new : (int string -> IntString)
x.get : (’o -> ‘o ‘o.x)
x.set : (’o ‘o.x -> ‘o)
y.get : (’o -> ‘o ‘o.y)
y.set : (’o ‘o.y -> ‘o)

So what has happened is that the type of ‘o.x is treated as an unknown variable, that is expanded once ‘o is known. Internally the type reconstruction algorithm simply has to create an object to represent the IntString, and track it.

So far I am very pleased with this approach, because the overall changes to the type system are very minimal, and the everything looks like it will work fine.

The next step is to allow fields to be added incrementally. I am thinking that the syntax may be something like:

30 “answer” IntString.new 
12 z.add
x.get z.get +

So the question is what the type will be off “z.add”? Perhaps something like:

z.add : (’o ‘x -> ‘o+z)

This ‘o+z just indicates that the result is a new type with a field named “z”. The type checker will have to manage the type internally. So to make this a fully compatible duck-typing system, such as the kind found in prototype based object-oriented languages like JavaScript, the requirement is simply that any object can be used where any other object is used, and that if a field is requested whose type is not known at compile-time, we return a value of type “any”, with the special value “undefined” used to indicate failure to find the field. 

Cat version 1.0 beta 4 was just released, download available here. New features inlude:

• static type checking of all primitives
• fixed type inference of “quote” function
• reintroduced “self” types to indicate a function accepting itself as an argument (e.g. define m { dup apply }, m : (’A (’A self -> ‘B) -> ‘B))
• added define symbol (/d:NOGRAPHICS) to remove graphics code in specific builds. This should allow Cat to work properly using Mono on Mac, see “mono_cat_no_graphics.exe” and “cat_mono_no_graphics.bat” for build options

Other recent news includes:

• graphics capabilities added to the online Cat interpreter
• Cat article appears on Doctor Dobbs Journal

About Cat 

Cat is a stack-based programming language that is distinct in that it allows functions to be constructed and pushed on to the stack in a type-safe manner. Cat has potential applications in computer science education, and as an intermediate language for optimization, verificatino, program transformation, and automated translation.

This is to announce that I have released version 1.2 of the online Cat interpreter. There are some bug fixes (e.g. “dup” now properly copies lists) and I have introduced primitive graphics capabilities, along with a new tool-tip help text to the various predefined instructions. Have fun, and feel free to reuse the source code, it is public domain!

I finally just finished integrating type checking back into the Cat compiler. This is only available in the version of Cat most recently checked into the SVN repository so feel free to pull it out: http://code.google.com/p/cat-language/source/checkout.

So Cat supports “self” types again which are references to enclosing functions. They are relatively rare in functions, but one example is the m combinator, defined as “dup apply” which has the type:

m : (’A (’A self -> ‘B) -> ‘B).

Anyway, I can’t sum up how happy I am to have this working with a minimum amount of pain.

This is an announcement of a new release of the Cat programming language. Recent changes include:

• automatic loading of the standard library
• 481 unit-tests (#test_all)
• documentation of over 400 primitive and standard-library instructions
• various minor bug fixes to the standard library
• searching for definitions matching a particular prefix, using “prefix” #defmatch

Cat is a functional stack-based language based on Joy. Cat is designed for several different purposes, but one of my key intentions was for education. Stack based languages can be very interesting for teaching computer science concepts because a student can see each step of a computation, and better understand how a computer operates.

In an effort to make Cat a suitable language for teaching programming I wanted to recapture the spirit of the Logo language in Cat. I found that when learning to program it was not only fun to write drawing programs, but that seeing the results of any mistakes I made helped me to understand what went wrong, and learn faster.

To do this I have included a turtle graphics library. The following screenshot is a demonstration of Cat in action:

The program that generated this is:

>> ow [20 tr pu 40 fd pd 40 draw_triangle] 20 repeat

These instructions are:

• ow - open a window
• tr - turn right
• pu - pen up
• fd - forward
• pd - pen down
• repeat - repeats a function a number of times
• [...] - pushes a function onto the stack

If you are interested in using Cat to teach programming, please let me know if I can help in any way. I’m very interested in trying to make it easier to teach programming to people.