The Artima Developer Community
Sponsored Link

Weblogs Forum
Cat Programming Language

7 replies on 1 page. Most recent reply: May 16, 2006 10:36 AM by Christopher Diggins

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 7 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Cat Programming Language (View in Weblogs)
Posted: May 13, 2006 6:53 PM
Reply to this message Reply
Summary
I'm developing a stack based functional language, inspired by the Joy programming language called Cat. What is particularly interesting about Cat is that it is particularly well-suited to optimization.
Advertisement
Those following my posts, may know that I am recently enamored with stack-based functional languages (like Joy). I have posted the powerpoint slides from a proposed talk about the Cat Programming Language at http://www.cdiggins.com/cat.ppt.

Here is the proposal which accompanies the presentation:

Cat Programming Language: A Functional Optimization Framework for the MSIL

Abstract

Cat is a stack-based pure functional language, inspired by the Joy programming language, which targets the Microsoft Intermediate Language (MSIL). Cat, like Joy, differs from mainstream functional languages in that it is based on the composition of functions rather than the application of functions. This design makes algebraic manipulation of programs trivial, and thus facilitates optimization.

This goal of the presentation (http://www.cdiggins.com/cat.ppt ) is to introduce the semantics and syntax of Cat, demonstrate rewriting rules for high-level functional optimizations, and show preliminary performance results for a simple IL Code generator written in C#.

Summary of Language

The Cat language is a pure functional language, inspired by Joy, which in turn is inspired by Forth and FP. All constructs in Cat (atomic programs, user defined programs, operators, literals, lists) behave as functions which takes a single stack as input and returns a new stack. In Cat the concatenation of two functions (e.g. [f g]) has the effect of composition of both functions (e.g. g(f(x))). All new user defined functions are defined as lists of functions. Cat not only has no variable declaration, there are no argument declarations. Cat also lends itself to the higher order functional programming: the lambda operation in Cat is the list construction operator "[...]" and currying can be achieved used basic operations such as "cons".

Results of Research

The primary result of the work done with Cat is the observation that high-level functional optimizations can be very easily expressed and applied. Consider the examples:

f map g map => [f g] map
[f] map x [g] fold => x [[f' f] g] fold 
[f] filter x [g] fold => x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold => x [f g [h] [pop] if] fold 
These optimizations are very important, but are extremely hard to apply once a langauge has been reduced to an assembly, or pseudo-assembly, form.

The thesis of this work is that by first compiling a language to a stack-based functional language such as Cat, before targeting a lower level target such as MSIL, better performance can be achieved.


Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: Cat Programming Language Posted: May 14, 2006 1:44 PM
Reply to this message Reply
Sounds incredibly exciting, but I can't for the life of me follow what you are doing. Perhaps it is due to my lack of experience with stack based languages? It would be nice if you had a Cat tutorial that went over the most basic of functionalities that Cat makes available, but at a slower and more detailed pace.

BTW, nice logo and paw-prints on the slides :)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Cat Programming Language Posted: May 14, 2006 2:58 PM
Reply to this message Reply
> Sounds incredibly exciting, but I can't for the life of me
> follow what you are doing. Perhaps it is due to my lack of
> experience with stack based languages? It would be nice if
> you had a Cat tutorial that went over the most basic of
> functionalities that Cat makes available, but at a slower
> and more detailed pace.

That is an excellent idea, and I'll put it at high-priority. For the time being you can take a look at the Joy tutorial at http://www.latrobe.edu.au/philosophy/phimvt/joy/j01tut.html . Cat is very close to Joy, but there are a few subtle differences.

> BTW, nice logo and paw-prints on the slides :)

Thanks a lot, I'll pass on the compliment to Melanie. )

(for those who are curious, my wife is a graphic designer who created the Heron logo, and the Cat logo).

Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: Cat Programming Language Posted: May 15, 2006 2:47 AM
Reply to this message Reply
Yes, I did assume it was her. She's really good. :)

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Interesting, yes Posted: May 15, 2006 1:50 PM
Reply to this message Reply
This is very interesting. Is Cat an internal project, or will it be made more availbale, or has that been determined yet?

It does seem like you can't keep away from language design.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Interesting, yes Posted: May 15, 2006 8:29 PM
Reply to this message Reply
> This is very interesting. Is Cat an internal project, or
> will it be made more availbale, or has that been
> determined yet?

It's a moonlighting project. So until Microsoft expresses interest in it, it'll be free and open. The prototype is now working, I just need to run some more tests and I'll post it online.

> It does seem like you can't keep away from language design.

I'm an addict. :-)

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Interesting, yes Posted: May 15, 2006 10:41 PM
Reply to this message Reply
I too thought you'd retired from language design, hence my rather cheeky comment about "replacing Christopher Diggins" in my blog bio. Dunno if Bill allows us to rewrite those :-)

Anyway, this sounds interesting - I came to your blog initially because I too had been studying/snake-victim-like-fascinated-by Forth and Lisp and some of the ideas in concatenative languages as part of the CEDSimply research.

Did you know there's already a dotNet Forth? Maybe you can collaborate.

http://www.codeproject.com/dotnet/dforthnet.asp

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Interesting, yes Posted: May 16, 2006 10:36 AM
Reply to this message Reply
> I too thought you'd retired from language design, hence my
> rather cheeky comment about "replacing Christopher
> Diggins" in my blog bio. Dunno if Bill allows us to
> rewrite those :-)

That is too flattering :-)

For the record you can rewrite bios. I got grief because my old bio was percieved by some as too self-promotional. Mine should also be changed again, now that I work for the dark side.

> Anyway, this sounds interesting - I came to your blog
> initially because I too had been
> studying/snake-victim-like-fascinated-by Forth and Lisp
> and some of the ideas in concatenative languages as part
> of the CEDSimply research.
>
> Did you know there's already a dotNet Forth? Maybe you can
> collaborate.
>
> http://www.codeproject.com/dotnet/dforthnet.asp

I've looked at it, albeit rather briefly. Forth in of itself is of less interest to me. I wanted a language where all of the constructs were functions, no variables or argument declarations were allowed, and side-effects were clearly delineated.

I doubt a language like Cat would be popular to write in directly (unless I come up with a really nice macro system)but it is intended as a backend implementation for other languages.

The big idea is that an arbitrary language can compile to Cat, which can then be retargetted to other formats (like MSIL, C, C--, LLVM, Java byte code, Parrot, NASM, C, etc.).

Hmmm... maybe you could find Cat useful as a backend for CEDSimply?

Flat View: This topic has 7 replies on 1 page
Topic: Cat Programming Language Previous Topic   Next Topic Topic: Thinking in C, Beta 2


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us