The Artima Developer Community
Sponsored Link

Weblogs Forum
New Cat Release and Documentation

9 replies on 1 page. Most recent reply: Jun 24, 2006 6:41 PM 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 9 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

New Cat Release and Documentation (View in Weblogs)
Posted: Jun 17, 2006 5:21 PM
Reply to this message Reply
Summary
I have updated the documentation for Cat and released a new version of the interpreter.
Advertisement
The latest Cat documentation, interpreter, and source code, is now available at http://www.cdiggins.com/cat/.

One of the fun new features is the ability to output an XML representation of any defined command. I use it with an XSLT style sheet to produce pretty HTML output such as the example at http://www.cdiggins.com/cat/all_tests_formatted.xml.

Apart from that there isn't much else to say. The documentation is better, the interpreter has been tested more extensively, the code has been improved somewhat, and there are a few more built-in commands. Oh, and there is a new mailing list I just set up if anyone is interested, at http://groups.google.com/group/catlanguage.

Have fun, and let me know what crazy things you can imagine doing with this kind of language (hint: try imagining all of the domain specific languages you could build).


Marcin Kowalczyk

Posts: 40
Nickname: qrczak
Registered: Oct, 2004

Re: New Cat Release and Documentation Posted: Jun 18, 2006 4:26 AM
Reply to this message Reply
> The Mono compilation problem has been identified as being
> the usage of the .NET Framework 2.0 features, namely
> templates, which are not yet supported by Mono.

Mono does support generics. The compiler of C# 2.0 is called gmcs for the time being.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: New Cat Release and Documentation Posted: Jun 19, 2006 11:08 AM
Reply to this message Reply
> > The Mono compilation problem has been identified as
> being
> > the usage of the .NET Framework 2.0 features, namely
> > templates, which are not yet supported by Mono.
>
> Mono does support generics. The compiler of C# 2.0 is
> called gmcs for the time being.

Thanks for pointing that out. I have removed the statement.

Robbert van Dalen

Posts: 5
Nickname: rapido
Registered: Jun, 2006

Re: New Cat Release and Documentation Posted: Jun 20, 2006 4:50 PM
Reply to this message Reply
Hi Christopher

Like you, I like Joy, Cat, Forth and Postscript for their concatenative features.
And, also like you, I am not very content with the current state-of-the-art programmign languages, and I'm eager to build something better.

However, a programming language is one thing: efficient algorithms to implement the language is another.
I feel that the most important data structure is the sequence. In Cat this would be the List structure.

Now consider the following Cat program that has 1 trillion elements with one single reduction:
[1 2 3 4 ......... 10000000 10000001 add 10000002 ....... 10000000000] dup !

The previous Cat program would copy the sequence (with complexity O(trillion) ?) and reduce the second (opened) sequence and add two big numbers.

My question to you is: how are you going to maintain the pure functional properties of Cat *and* also scale to big sequences?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: New Cat Release and Documentation Posted: Jun 21, 2006 1:00 AM
Reply to this message Reply
> My question to you is: how are you going to maintain the
> pure functional properties of Cat *and* also scale to big
> sequences?

I don't fully understand the problem. Where is the conflict that you are implying?

Robbert van Dalen

Posts: 5
Nickname: rapido
Registered: Jun, 2006

Re: New Cat Release and Documentation Posted: Jun 21, 2006 1:16 AM
Reply to this message Reply
Because everything is purely functional in Cat this means that any list or data structure in Cat has to maintain its referentially transparent/immutable properties during execution.

Now consider a very big (quoted) program with a million entries.
My question is: When this program is executed (reduced) how does Cat make sure it doesn't destroy the previous (unreduced) version?

Copying all elements from the old version into the new one would certainly be an idea. But this would be very inefficient.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: New Cat Release and Documentation Posted: Jun 21, 2006 10:37 AM
Reply to this message Reply
> Because everything is purely functional in Cat this means
> that any list or data structure in Cat has to maintain its
> referentially transparent/immutable properties during
> execution.
>
> Now consider a very big (quoted) program with a million
> entries.
> My question is: When this program is executed (reduced)
> how does Cat make sure it doesn't destroy the previous
> (unreduced) version?
>
> Copying all elements from the old version into the new one
> would certainly be an idea. But this would be very
> inefficient.

I have a few observations:
- In a case like the one you proposed, no part of the program ever uses the unreduced list. A smart compiler could destroty the original list without changing the program semantics
- Copying semantics aren't so bad as all that. e.g. C++ programs often run fine
- A sequence of consecutive numbers would be better represented using:

def myseq = 1 1000000 init;

which can be easily stored as a generator function internally.

As an interesting node: I have a list class in C# under development which switches between different internal representations based on usage. For example, in some circumstances it uses an array representation, in others a linked list, and in others still it uses a generator function.

Finally, I should ask, are there better alternatives I am not aware of? I am definitely open to suggestions.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: New Cat Release and Documentation Posted: Jun 21, 2006 10:54 AM
Reply to this message Reply
/* [Designing] a programming language is one thing: [designing] efficient algorithms to implement the language is another.

Consider a very big (quoted) program with a million entries.
My question is: When this program is executed (reduced) how does Cat make sure it doesn't destroy the previous (unreduced) version?
*/

I didn't have a good answer for this yesterday, and CDiggins has already given a better answer than what I came up with this morning. Even so, I believe if all else failed, Cat can work on chunks of such input. That is, if Cat can determine that certain conditions hold (eg., computations on element 1 do not affect computations on element 2), then the runtime environment can choose an arbitrary number of elements (say 32 or 64) that can be worked on simultaneously. This provides a speedup compared to working on one element at a time.

The answers would have to be stored somewhere other than the original list so that if computation failed halfway through the original list wouldn't be affected. If I understand correctly, Google's MapReduce works like this ( http://labs.google.com/papers/mapreduce.html ).

Robbert van Dalen

Posts: 5
Nickname: rapido
Registered: Jun, 2006

Re: New Cat Release and Documentation Posted: Jun 21, 2006 11:53 AM
Reply to this message Reply
> > Because everything is purely functional in Cat this
> means
> > that any list or data structure in Cat has to maintain
I have a few observations:
> - In a case like the one you proposed, no part of the
> program ever uses the unreduced list. A smart compiler
> could destroty the original list without changing the
> program semantics
OK, how about this ;-)

[bigprogram] dup ! => [bigprogram] [bigprogram] => [bigprogram] bigprogram

Surely the quoted [bigprogram] should not be destroyed by the reduced program.

> - Copying semantics aren't so bad as all that. e.g. C++
> programs often run fine

What about the efficient concatenation of big lists A and B (or programs)?Surely you this operation to be fast to, say O(log(size(A) + size(B)) and not O(size(A + B)).

> - A sequence of consecutive numbers would be better
> represented using:
>
> def myseq = 1 1000000 init;
>
> which can be easily stored as a generator function
> internally.
Yes, it would be a lazy list ;-)

>
> As an interesting node: I have a list class in C# under
> development which switches between different internal
> representations based on usage. For example, in some
> circumstances it uses an array representation, in others a
> linked list, and in others still it uses a generator
> function.
Cool.

>
> Finally, I should ask, are there better alternatives I am
> not aware of? I am definitely open to suggestions.
May be you should look at Chris Okasaki's work on purely functional datastructures. The most recent development is: Finger Trees by Ralf Hinze. I also use Treaps sometimes for fast list implementations.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: New Cat Release and Documentation Posted: Jun 24, 2006 6:41 PM
Reply to this message Reply
> What about the efficient concatenation of big lists A and B (or programs)?Surely you this operation to be fast to, say O(log(size(A) + size(B)) and not O(size(A + B)).

One solution to this problem is a concatenated list structure. This is constructed from a pair of lists. Concatenation is fast, but everything else is just a bit slower.

I will confess that for the current moment the precise choice of data strucutres in my Cat compiler is low on my priority list.

Flat View: This topic has 9 replies on 1 page
Topic: New Cat Release and Documentation Previous Topic   Next Topic Topic: A Brief History of Scala


Sponsored Links



Google
  Web Artima.com   

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