Home » forums » LtU Forum

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 http://www.cdiggins.com/cat/cat.pdf

By cdiggins at 2006-08-02 02:27 | LtU Forum | previous forum topic | next forum topic | other blogs | 7732 reads

Comment viewing options

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

Typo?

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 }

By Eddie Rucker at Wed, 2006-08-02 15:17 | login or register to post comments

Sorry about that, I get my

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

By cdiggins at Thu, 2006-08-03 04:49 | login or register to post comments

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?

By James McCartney at Wed, 2006-08-02 17:13 | login or register to post comments

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.

By cdiggins at Thu, 2006-08-03 04:48 | login or register to post comments

bounded stack effects

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

From your slides:

"[poploc] 5 repeat"

By James McCartney at Thu, 2006-08-03 06:23 | login or register to post comments

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?

By cdiggins at Thu, 2006-08-03 15:45 | login or register to post comments

I think that you should

I think that you should allow this.

By Jules Jacobs at Tue, 2006-08-08 07:47 | login or register to post comments

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?

By dbremner at Thu, 2006-08-03 02:07 | login or register to post comments

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.

By cdiggins at Thu, 2006-08-03 04:52 | login or register to post comments

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.

By Serguey Zefirov at Sat, 2006-08-05 16:31 | login or register to post comments

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.

By cdiggins at Sat, 2006-08-05 17:18 | login or register to post comments

Memoization

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.

By Serguey Zefirov at Mon, 2006-08-07 13:40 | login or register to post comments