Cat Programming Language: Slides from Lang. NET 2006

The slides from my presentation on the Cat programming language at Lang. NET 2006 are now online at

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


On page 86 you say that filters are associative but it seems to me like you are showing a commutative transform instead of an associative one.

transform { f filter g filter } { g filter f filter }

Sorry about that, I get my

Sorry about that, I get my commutative and associative mixed up.

bounding stack effects

"A Cat program must consume a constant number of elements of fixed type."

"At any point in a Cat program, the number and type of elements on the stack is knowable at compile time."

so this is not a legal Cat program, then:

{ [pop] swap repeat }

..takes a repeat count from the top of the stack and pops that many items from the stack.
The number of items popped by this function can't be known at compile time. The compiler catches this and reports an error?

Yes the compiler would catch

Yes the compiler would catch this error, if the compiler was finished. ;-)

The repeat function would require a function signature with zero valence (it consume the same number of stack elements that it produces). [pop] has valence of -1 (it consumes one element and produces zero), so it simply won't compile.

I will have to confess though ... I haven't yet decided how to express the fact that a combinator requires a function of valence zero, in the type notation. This isn't a crucial problem to making the compiler work, but it would be nice.

bounded stack effects

"The repeat function would require a function signature with zero valence"

From your slides:

"[poploc] 5 repeat"

Good catch, thank you! So

Good catch, thank you!

So this looks to me like I do need a new operator: repeat#N

Which behaves like a macro.

What do you think?

I think that you should

I think that you should allow this.

Traditional Optimizations

Your presentation mentions Cat's potential for optimization after discarding many approaches that have been used in anger. Have you tried implementing any traditional optimizations like dead code elimination, strength reduction, or common subexpression elimination?

I haven't yet explored the

I haven't yet explored the full limits of the transform system for expressing traditional optimization techniques. So I don't know how many of these are coverable using the transform technique.

Part of the assumption of Cat is that the next target will perform traditional low-level optimizations, such as done by the MSIL.

Notwithstanding presence of lazy generators...

...I hadn't seen any mention of sharing.

So Cat seems to be unsuitable for translation of languages based on lazy reducing of graphs.

No destructive semantics.

It's not explicit, but lists are often shared. This is a side effect of the fact that there are no destructive semantics in the language.


Can we construct something memoizing in Cat?

A computation that computed only once. It seems that we can't.

Anyway, Cat seems to be a good starting point for thinking about intermediate language for graph reduction machines.