The Artima Developer Community
Sponsored Link

Weblogs Forum
Download the Cat

14 replies on 1 page. Most recent reply: Jun 1, 2006 11:54 AM by Max Lybbert

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 14 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Download the Cat (View in Weblogs)
Posted: May 27, 2006 5:48 PM
Reply to this message Reply
Summary
There is now a downloadable interpreter with source for the Cat programming language written in C#.
Advertisement

Cat is a stack based functional language inspired by the Joy programming language Like Joy, Cat is a cross between Forth and the FP language.

A prototype Cat interpreter, has been released into the public domain, and is available for download with C# source code at http://www.cdiggins.com/cat.zip.

Characteristics of Cat

Cat has no variables, no arguments, no constants, and no side-effects. Every Cat program takes a single stack as input, and returns a single stack as output. A Cat program is made up of a sequence of sub-programs. A sub-program may be user-defined or atomic programs.

A Nip of Cat

In Cat every operation, program, and literal, is a stack transform function. It takes a stack and returns a new stack. The following are examples of Cat programs:

    42; // pushes 42 onto the stack
    1 2; // pushes the value 1 and then the value 2 onto the stack
    1 2 swap; // pushes 2 and then 1 onto the stack.
    1 2 +; // pushes 3 onto the stack
    1 + 2; // increments the top value of the stack, then pushes 2 onto the stack
    pop; // removes the top item of the stack
    dup; // duplicates the top item on the stack
    [1 2 3]; // pushes a list of functions onto the stack
    [1 2 3] $; // pushes a list of values onto the stack
    [] 1 cons; // pushes a list containing the "1" function
  

There is a more detailed introduction to Cat available here.


Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: Download the Cat Posted: May 28, 2006 8:26 PM
Reply to this message Reply
>[1 2 3]; // pushes a list of functions onto the stack
>[1 2 3] $; // pushes a list of values onto the stack

So in the other examples, 1, and 2, are functions? And + creates a function 3? What's the difference between the function 1 and the value 1? What difference does it make when you're optimizing?

>[] 1 cons; // pushes a list containing the "1" function

This seems funny, because the arguments are the other way around from cons in LISP. Would it be better to call it something else?

Shigeru HEMMI

Posts: 2
Nickname: textd
Registered: May, 2006

Re: Download the Cat Posted: May 28, 2006 11:35 PM
Reply to this message Reply
Dear Christopher,

Compilation failed in building Cat.exe with mono 1.1.15.0:

C:\cat>mcs --version
Mono C# compiler version 1.1.15.0

C:\cat>mcs /out:CatMono.exe *.cs
Optimzer.cs(13,13): error CS8025: Parsing error
Parser.cs(30,24): error CS1526: A new expression requires () or [] after type
Compilation failed: 2 error(s), 0 warnings

Regards,

HEMMI, Shigeru

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Download the Cat Posted: May 29, 2006 4:48 AM
Reply to this message Reply
I would be fascinated to see an explanation of why cat is a particularly good intermediate language.

What inherent advantage does it provide over some other representation.

BTW I'm a bit puzzled by the difference between [dup *] being an anonymous function and your comment a bit later that a list of literals (e.g. [1 2 3]) pushes a list of functions onto the stack as opposed to a list of integers.

Why do the two operators in the [dup *] get combined into one anonymous function but the [1 2 3] doesn't?

As I think I've remarked before, this reminds me of Nano-False, which allows similar coding on a mobile phone.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Download the Cat Posted: May 29, 2006 2:06 PM
Reply to this message Reply
> >[1 2 3]; // pushes a list of functions onto the stack
> >[1 2 3] $; // pushes a list of values onto the stack
>
> So in the other examples, 1, and 2, are functions? And +
> creates a function 3?

No "+" pops the top two values of the stack, and pushes their sum. "1" pushes the value 1 onto the stack, and "2" pushes the value "2" onto the stack.

> What's the difference between the
> function 1 and the value 1?

You can add ints, but not functions. You can compose functions, but not ints. So essentially the set of operators available is the same. A list of ints can be summed together, but a list of functions returning integers can't.

> What difference does it make
> when you're optimizing?

It's important for type analysis, but it is true that in many cases the value can be substituted for the function.

> >[] 1 cons; // pushes a list containing the "1" function
>
> This seems funny, because the arguments are the other way
> around from cons in LISP. Would it be better to call it
> something else?

Good point. Perhaps I should call it prepend, or push?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Download the Cat Posted: May 29, 2006 2:19 PM
Reply to this message Reply
> I would be fascinated to see an explanation of why
> cat is a particularly good intermediate language.
>
> What inherent advantage does it provide over some other
> representation.

I'm glad you brought this up. I need to make a better case on the page. There are several reasons:

* No need to worry about registers, variables, arguments, and multiple stacks
* It retains the high level operations like "map","filter", "reduce". This way things like "[f] map [g] map" can be easily rewritten as "[f g] map"
* It is easy to write rewriting rules as simple pattern matching (take a look at Optimizer.cs)
* It is easy to implement

> BTW I'm a bit puzzled by the difference between [dup *]
> being an anonymous function and your comment a bit later
> that a list of literals (e.g. [1 2 3]) pushes a list of
> functions onto the stack as opposed to a list of
> integers.


Sorry I wasn't clear, an anonymous function is just a list of functions.

> Why do the two operators in the [dup *] get combined into
> one anonymous function but the [1 2 3] doesn't?

[1 2 3] is also an anonymous function. It can be passed to another function which requires a function, such as the execution operator "i".

> As I think I've remarked before, this reminds me of
> Nano-False, which allows similar coding on a mobile phone.

Nano-false ( http://goanna.cs.rmit.edu.au/~winikoff/palm/dev.html ) and Cat both have their roots in Forth, so that isn't too surprising.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Download the Cat Posted: May 29, 2006 2:50 PM
Reply to this message Reply
> Dear Christopher,
>
> Compilation failed in building Cat.exe with mono
> 1.1.15.0:
>
> C:\cat>mcs --version
> Mono C# compiler version 1.1.15.0
>
> C:\cat>mcs /out:CatMono.exe *.cs
> Optimzer.cs(13,13): error CS8025: Parsing error
> Parser.cs(30,24): error CS1526: A new expression requires
> () or [] after type
> Compilation failed: 2 error(s), 0 warnings
>
> Regards,
>
> HEMMI, Shigeru

Thank you very much for pointing this out Shigeru. I will try to develop a version which works on Mono. I used C# Express edition from Microsoft (which is also free). Let me know if you manage to make it work.

Shigeru HEMMI

Posts: 2
Nickname: textd
Registered: May, 2006

Re: Download the Cat Posted: May 29, 2006 11:37 PM
Reply to this message Reply
I'm using Mac OS X 10.3 (ppc) at home and am using Windows XP at office. The Cat.exe works on Mono+Windows, not works on Mono+Mac at the moment. IronPython can run for both machines, very useful and cool. If the executable Cat.exe works on Mono+Mac, Mono+LINUX, etc., many UNIX people can particpate the camp.
Thank you for your reply.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Mono, C#, etc. Posted: May 30, 2006 11:21 AM
Reply to this message Reply
Out of curiousity, how do you like programming in C#?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Mono, C#, etc. Posted: May 30, 2006 5:37 PM
Reply to this message Reply
> Out of curiousity, how do you like programming in C#?

Kind of fun. I'm much faster in it than in C++. I just wish performance wasn't so crappy. I do like the tiny executables though. I may be odd but I prefer C++ templates to C# generics. That's it in a nutshell.

What do you think of C#?

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Mono, C#, etc. Posted: May 30, 2006 7:00 PM
Reply to this message Reply
I haven't yet done any work in C#. I really need to give up and take the plunge. I *have* skimmed books on it, and read interviews about the differences between C# and Java. Overall, I started really hating Java just before Microsoft started on .NET (which is why I was interested in Heron, btw).

My problem with Java is that many roads are blocked off because Gosling thought they were dangerous. I understand C# opened some of those roads up, so it sounds like an improvement.

In any event, I've downloaded Cat, and I'll download Mono to work with it. The previous error message (well "Parser.cs(30,24): error CS1526: A new expression requires () or [] after type," as "Parsing Error" just doesn't have enough to go off of) sounds like you wrote the C++-style "my_obj = new my_class;" instead of the Java-style "my_obj = new my_class();", so I'm pretty sure the port will be trivial.

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Download the Cat Posted: May 30, 2006 9:01 PM
Reply to this message Reply
> me> why
> me> cat is a particularly good intermediate language.
>

> It retains the high level operations like "map","filter", "reduce".
>This way things like "[f] map [g] map" can be easily rewritten as "[f g] map"

and why is that such a big deal? Isn't that only useful if your application is coded in such a way as to use such operators?

I confess to having missed large chunks of a traditional CS education in things like language implementation (trying to catch up now) so I may just be ignorant of some typical transformations.

If you don't have an application coded to apply operators to structures, say it's just event-driven OO GUI code with some IFs, LOOPs and SELECTs in methods, would you still make use of map logic?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Download the Cat Posted: May 30, 2006 11:58 PM
Reply to this message Reply
> > me> why
> > me> cat is a particularly good intermediate language.
> >
>
> > It retains the high level operations like
> "map","filter", "reduce".
> >This way things like "[f] map [g] map" can be easily
> rewritten as "[f g] map"
>
> and why is that such a big deal? Isn't that only useful if
> your application is coded in such a way as to use such
> operators?
>
> I confess to having missed large chunks of a traditional
> CS education in things like language implementation
> (trying to catch up now) so I may just be ignorant of some
> typical transformations.
>
> If you don't have an application coded to apply operators
> to structures, say it's just event-driven OO GUI code with
> some IFs, LOOPs and SELECTs in methods, would you still
> make use of map logic?


for (int i=0; i < a.length; ++i)
{
a[i] = DoSomeThing();
}


can be rewritten as:


a.Map(DoSomething);

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Download the Cat Posted: May 31, 2006 7:55 PM
Reply to this message Reply
I understand idioms like being able to transform a looped function call into a map (I do a lot of this in Python especially with generators and list comprehensions).

The domains I am interested in providing programming solutions for would more often involve tiny fragments of code being invoked in response to events, either as a GUI app or in multimedia.

I don't see how Cat particularly helps implement such.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Cat and GCC's RTL? Posted: Jun 1, 2006 11:54 AM
Reply to this message Reply
FWIW, Cat reminds me of *the description* of GCC's Register Type Language (I don't know RTL enough to say if Cat's all that much like it). Even so, I believe Cat's slightly different design makes different optimization opportunities available.

/* The domains I am interested in providing programming solutions for would more often involve tiny fragments of code being invoked in response to events, either as a GUI app or in multimedia.
*/

The only general optimization that comes to mind here is inlining the "tiny fragments of code" so that you don't get the overhead of a function call. Cat supports this, but so does C++. Other than that, you'd have to look at the event handler (how do you register events? how do you signal an event took place?), and see if there's a potential to optmize *that*, and Cat may be able to help you there.

On second thought, if you're willing to leave C-calling conventions behind (and inlining function calles does that), Cat may help you find cases where you can use the message-passing techniques used in the L4 microkernel that are apparently slightly faster than a normal function call.

Flat View: This topic has 14 replies on 1 page
Topic: Download the Cat Previous Topic   Next Topic Topic: Code Generation and Standards Support in NetBeans


Sponsored Links



Google
  Web Artima.com   

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