Weblogs Forum

15 replies on 2 pages. Most recent reply: Nov 21, 2006 5:27 PM by Andy Dent

 Previous Topic Next Topic
 Flat View: This topic has 15 replies on 2 pages [ 1 2 | » ]
 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Cat is all about Tuples (View in Weblogs)
Posted: Nov 11, 2006 11:13 AM
Summary
Having spent some more time trying to explain Cat, a stack based functional language, I came to an interesting realization: virtually everything could be explained in terms of tuples.
I had been previously explaining the Cat programming languages as a language where every term is a function which maps a pair of stacks to another pair of stacks. I went on to explain the type inference algorithm in terms of tuples, so that I could relate it to existing type theory. Well I just realized that if I model Cat using only tuples and primitives then everything becomes much easier.

Here's what I mean:

• a stack is a tuple
• a pair of stacks is a tuple (pair) of tuples (stacks)
• a function is a tuple (production and consumption) of tuples (pair) of tuples (stacks)
This is very interesting, because it means that the syntax and semantics of Cat can be generalized to languages very different than Cat. For example, more than two tuples (stacks), or languages where the data strucutre behaves more like a deque.

Anyway, before I bark up that tree I'd probably best keep focus on the paper I am writing about Cat. I want to submit a technical article to a peer reviewed journal, and I am looking for people to review it for me. Anyone interested in helping me out?

 Cleo Saulnier Posts: 77 Nickname: vorlath Registered: Dec, 2005
Re: Cat is all about Tuples Posted: Nov 13, 2006 4:14 AM
I was hoping (WAY WAY back, long ago) that one day you would unfold the stacks that Cat uses. You mention deque's. Have you looked more into this? If you made it so that the input and output were different queues (instead of a stack), you could get rid of the execution point or any notion of control statements. You could also link up different 'functions' although you'd need new systax to split and merge tuples. But you'd have your lego-type software construction model. Plus, it'd be concurrent without the use of threads.

Just a thought.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 13, 2006 12:03 PM
> I was hoping (WAY WAY back, long ago) that one day you
> would unfold the stacks that Cat uses. You mention
> deque's. Have you looked more into this?

Well a deque is just a tuple with specific operations, so with the new tuple model, it should be trivial.

> so that the input and output were different queues
> (instead of a stack), you could get rid of the execution
> point or any notion of control statements.

There is no notion of control statements or execution point, except in impure functions (kind of like sequencing operations).

`true [42] [13] if`

is precisely the same thing as

`42`

How the implementation deals with the scenarios is entirely undefined. There is no concept of doing x then doing y, but of rather constructing functions.

> You could also
> link up different 'functions' although you'd need new
> systax to split and merge tuples.

Yep.

> But you'd have your
> lego-type software construction model.

I',m already part of the way there.

> Plus, it'd be
> concurrent without the use of threads.

Map and fold can already be implemented concurrently, but unfortunately they operate on dynamically typed lists (yuck)

> Just a thought.

Keep them coming!

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 13, 2006 12:26 PM
>Plus, it'd be
> concurrent without the use of threads.

I think you might be interested in the discussion on concurrency in concatenative languages:

http://tech.groups.yahoo.com/group/concatenative/message/3063

On a separate note I should point out, that I do want to make sure that the features that you hope for from Cat will be available (or attainable). Please tell me more about the types of built-in functions you'd like to see, and more about the desired structure of Cat. In other words, what do you mean about unfolding the stacks, and what will you do with it?

Thanks,
Christopher

 Cleo Saulnier Posts: 77 Nickname: vorlath Registered: Dec, 2005
Re: Cat is all about Tuples Posted: Nov 13, 2006 7:53 PM
Well, right now Cat, from what I understand, is based on recursive building of functions which in itself states the order of operations based on nesting rather than data, so there is an execution point, even if a relaxed notion of one. While that is nice and should still be available, I was wondering if it'd be possible to allow flow based constructs as well. I realise that many are dismissive of the term 'flow based', but it does have a great deal of power as unix still uses a flavour of it today. It's what makes map/reduce and all sorts of other such constructs possible. Any map/reduce in other languages are adaptations and not true features of the language. For example, how to you reduce a list that is still being built AS the reduce operation is executing? Without side-effects, this breaks the pureness of the language. Not so if you include queues as well as stacks.

I'm not sure if you know about my project. In any case, I'm keeping an eye on Cat because it is the only language that has the potential to bring something no other language has. In short, I want to see where you will go with this. So I was just wondering if you had any thought on allowing queues instead of stacks. I'm wondering if you see any advantage (or disadvantage) in doing this.

Here's what I mean. Instead of all functions using the same stack, it should instead operate on two separate input and ouput queues. The function definition would stay the same. Only where it gets its input and stores its output would change. That's what I mean by unfolding the stack. This would mean that one function's output queue is another's input queue. So the operations would stay the same, but the inputs and outputs are taken from different places. This would allow the chaining of functions together where all of them can execute at the same time. (This is what I'm particularly interested in!!!) This is also what I meant by needing something that will allow splitting and merging of tuples. This is so you can split an output tuple (queue) to two or more different chained functions. You can also merge tuples together into a single queue.

That's it. Add queues and the ability to merge and split them. These could be built-in functions I suppose. And you need a syntax to specify the chaining of functions rather than (and in addition to) nesting them. This has been the major stumbling block wherever this has been attempted. Just wondering if you see the power or if this not where you want to go.

Note that I don't want to influence you either way. I'm interested in knowing what your personal opinion is on this and if it's a direction you have thought of, whether for or against.

Oh, certain things you may want are phase shifting functions as well as data that isn't in tree format, but in stream format where the lower nested data follows the head data in sequential fashion. You'll see why if you look more into it.

So you see that I'm thinking in much bigger terms than the link you provided as far as concurrency is concerned. I still have doubts that you will go this way, but I'm interested in your opinion either way.

Thanks for you time.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 15, 2006 7:54 PM
> Well, right now Cat, from what I understand, is based on
> recursive building of functions which in itself states the
> order of operations based on nesting rather than data, so
> there is an execution point, even if a relaxed notion of
> one. While that is nice and should still be available, I
> was wondering if it'd be possible to allow flow based
> constructs as well.

What form would flow based primitive constructs take?

> I realise that many are dismissive of
> the term 'flow based', but it does have a great deal of
> power as unix still uses a flavour of it today. It's what
> makes map/reduce and all sorts of other such constructs
> possible. Any map/reduce in other languages are
> adaptations and not true features of the language.

On that note, one of the planned primitive constructs for Cat is "filter_map_reduce". This is a primitive that combines the three operations optimally. Many Cat programs (or at least subprograms) can be automatically rewritten to use this atomic operation.

> For
> example, how to you reduce a list that is still being
> built AS the reduce operation is executing?

Use "filter_map_reduce"! :-)

> Without
> side-effects, this breaks the pureness of the language.
> Not so if you include queues as well as stacks.

I agree that queues have to be allowed.

> I'm not sure if you know about my project.

What is the url?

> In any case,
> I'm keeping an eye on Cat because it is the only language
> that has the potential to bring something no other
> language has.

Thanks!

> In short, I want to see where you will go
> with this. So I was just wondering if you had any thought
> on allowing queues instead of stacks. I'm wondering if
>
> Here's what I mean. Instead of all functions using the
> same stack, it should instead operate on two separate
> input and ouput queues. The function definition would
> stay the same. Only where it gets its input and stores
> its output would change. That's what I mean by unfolding
> the stack. This would mean that one function's output
> queue is another's input queue. So the operations would
> stay the same, but the inputs and outputs are taken from
> different places. This would allow the chaining of
> functions together where all of them can execute at the
> same time. (This is what I'm particularly interested
> in!!!) This is also what I meant by needing something
> that will allow splitting and merging of tuples. This is
> so you can split an output tuple (queue) to two or more
> different chained functions. You can also merge tuples
> together into a single queue.
>
> That's it. Add queues and the ability to merge and split
> them. These could be built-in functions I suppose. And
> you need a syntax to specify the chaining of functions
> rather than (and in addition to) nesting them. This has
> been the major stumbling block wherever this has been
> attempted. Just wondering if you see the power or if this
> not where you want to go.

This sounds very interesting, but also very different from where I want to go. I am interested in an operating environment which maps very closely and efficiently to single processor hardware.

However I do agree that queus are an important data structure, which will be supported by Cat, but not at the most fundamental level as you suggest.

I am not convinced at this point, you can't do what you want using a very clever library.

> Note that I don't want to influence you either way. I'm
> interested in knowing what your personal opinion is on
> this and if it's a direction you have thought of, whether
> for or against.

I'd have to see a more complete description to comment further.

 Eirik Maus Posts: 15 Nickname: eirikma Registered: Oct, 2005
Re: Cat is all about Tuples Posted: Nov 16, 2006 6:13 AM
and, what's more,
- the entire memory of the computer is a tuple (albeit large)
- the disk also
- the running of any program or function to change that memory (or disk) is a tuple (from pre-state to post-state)
- runnning programs takes time, and time is itself a tuple (past, future)

 Achilleas Margaritis Posts: 674 Nickname: achilleas Registered: Feb, 2005
Re: Cat is all about Tuples Posted: Nov 17, 2006 4:26 AM
Chris,

It seems to me that if 'tuple' is replaced with 'list', there is no change in the meaning of your proposal.

Is there a specific need that dictates the use of word 'tuple' instead of 'list'?

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 17, 2006 7:03 AM
> Chris,
>
> It seems to me that if 'tuple' is replaced with 'list',
> there is no change in the meaning of your proposal.
>
> Is there a specific need that dictates the use of word

List refers to collections of like-typed elements or to dynamically typed elements, while tuples are statically typed collections. This is my distinction and I believe that of many others as well. Do you think I am straying from convention?

 Achilleas Margaritis Posts: 674 Nickname: achilleas Registered: Feb, 2005
Re: Cat is all about Tuples Posted: Nov 17, 2006 7:43 AM
> List refers to collections of like-typed elements or to
> dynamically typed elements, while tuples are statically
> typed collections. This is my distinction and I believe
> that of many others as well. Do you think I am straying
> from convention?

Definitely not! indeed, the usual interpretation of the list is that a list contains the same type of elements and it grows dynamically, whereas a tuple contains a static amount of different kind of elements.

But there is something else that got me thinking, maybe not that important. You said that a stack is a tuple. In purely functional programming languages, pushing an element into a stack would duplicate the stack, if the stack is a tuple: a new value would be produced. By representing the elements of Cat as lists, perhaps that little point could be rectified.

Perhaps stack duplication does not it play a role in the semantics of Cat; if so, forget this comment. But if it does, you may want to use another type for abstracting Cat's elements.

I would like to note here that a list could theoretically contain elements of more than one type, if that type is an algebraic one.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 17, 2006 9:38 AM
> But there is something else that got me thinking, maybe
> not that important. You said that a stack is a tuple. In
> purely functional programming languages, pushing an
> element into a stack would duplicate the stack, if the
> stack is a tuple: a new value would be produced. By
> representing the elements of Cat as lists, perhaps that
> little point could be rectified.

Yes conceptually and theoeretically the stacks are duplicated, but there is no reason the implementation can't simply reuse the same stacks and update them. In Cat, there is no way to refer to the old stacks, so they are tossed out. This means that the implementation can be extremely efficient (ala Forth).

> Perhaps stack duplication does not it play a role in the
> semantics of Cat; if so, forget this comment. But if it
> does, you may want to use another type for abstracting
> Cat's elements.
>
> I would like to note here that a list could theoretically
> contain elements of more than one type, if that type is an
> algebraic one.

I see what you mean, but the list would still be homogenous over the algebraic type itself, would it not? I guess the question is, if I have a list of fruits, and I place an orange at the end, when I remove the last item, is it still an orange or is it now a fruit? In languages like Haskell and ML we would lose the information about it being a orange, and only know at this point in the program that it is a fruit. So a list of algebraic types cause the more specific type information to be lost. I could be mistaken however, and I am open to corrections.

 Cameron Purdy Posts: 186 Nickname: cpurdy Registered: Dec, 2004
Re: Cat is all about Tuples Posted: Nov 20, 2006 6:56 PM
> It seems to me that if 'tuple' is replaced with 'list',
> there is no change in the meaning of your proposal.

Hey, what about "array"? We could view the memory (or the disk) as an array of bytes, for example ..

OK, silliness aside, of course good general purpose data structures _can_ represent many different things .. but that doesn't mean that they are the ideal way to do so ;-)

Peace,

Cameron Purdy
<a href="http://tangosol.com/">Tangosol Coherence: The Java Data Grid</a>

 Cleo Saulnier Posts: 77 Nickname: vorlath Registered: Dec, 2005
Re: Cat is all about Tuples Posted: Nov 21, 2006 7:33 AM
> I
> > was wondering if it'd be possible to allow flow based
> > constructs as well.
>
> What form would flow based primitive constructs take?

Four operations come to mind. One is splitting tuples.
I'm using named parameters here.

(int:A, int:B)->(A) (B)

Next is merging:

(int:A) (int:B)->(A B)

Then there is chaining:

{fA -> fB -> {fC, fD}}

Or some sort of syntax to allow chaining of functions.
fA,fB,fC and fD can all execute at once if needed.
It's up to the compiler to determine if it should be done.
There are some basic algorithms for this.
The syntax is always difficult because you can merge
and split chains. So I'm sure something WAY better can
be done.

Also, this entire function would take its parameters from either the stack or yet another chained function. It depends how it's used (nested of not).

Lastly, there are conditional and selective merging and splitting.

(int:S) (int:A) (int:B)->(int:C)

S is the selector and you output either A or B on C.

You can also have selective redirecting.

(int:S) (int:A)->(int:B) (int:C)

Depending on S, A will be output on either B or C. You don't need to use both output.

These are needed for queue based processing.

> > For
> > example, how to you reduce a list that is still being
> > built AS the reduce operation is executing?
>
> Use "filter_map_reduce"! :-)

I'm just saying with queues, you can build this with the available language constructs. It's nothing special. You can use it everywhere, not just in this special case.

>
> > I'm not sure if you know about my project.
>
> What is the url?

I only have a blog (username links to it) right now. Beware if you go there. My alter ego is pretty forceful on certain topics. I'll let you know once I release something if you wish.

It's about a visual IDE that has the above constructs and much more. Basically, it's a way to link up different tools together without the restrictions that comes with an execution point (although the implementations can use it). I'm hoping many tools with come with an editor where you can configure them. This is something that I find lacking in programming languages. A simple example is a sort tool where you can pick which algorithm to use and select what data to sort on.

>
> This sounds very interesting, but also very different from
> where I want to go. I am interested in an operating
> environment which maps very closely and efficiently to
> single processor hardware.

AH! I'm sorry to hear that.
>
> However I do agree that queus are an important data
> structure, which will be supported by Cat, but not at the
> most fundamental level as you suggest.
>
I'm tempted to add it myself if you'd allow me to take a jab at it. All I need are the four constructs above. Even if it was single processor only, I think it would add something very useful.

> I am not convinced at this point, you can't do what you
> want using a very clever library.
>
Normally, I'd agree with you as everything can be written in any Turing complete language. But we both know this stop languages from being built. Even so, what I'm talking about cannot be written with a library.

> > Note that I don't want to influence you either way.
> I'm
> > interested in knowing what your personal opinion is on
> > this and if it's a direction you have thought of,
> whether
> > for or against.
>
> I'd have to see a more complete description to comment
> further.
>
> Thanks for sharing your ideas!

Sure thing.

I usually have difficulty in explaining the virtues of queues. I think I remember you talking about black box connectivity. Well, now you could have them. And you'd finally have lego block style of building software. I think that without seeing it and using it, it'll continue to be difficult to show the real power of this. Streams are at the heart of it all. Once you start using it, I think it'll be hard to use anything else after that.

 Cleo Saulnier Posts: 77 Nickname: vorlath Registered: Dec, 2005
Re: Cat is all about Tuples Posted: Nov 21, 2006 7:44 AM
Sorry for the double post. But I just saw another entry where you say you put Cat in the public domain. Is this correct? If so, then I'm gonna have some fun with it. Too bad it's in C#. I'll convert it to C++. BTW, I forgot a word in "this *doesn't* stop languages from being built".

Thanks!

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Cat is all about Tuples Posted: Nov 21, 2006 9:53 AM
> Sorry for the double post. But I just saw another entry
> where you say you put Cat in the public domain. Is this
> correct?

Yes I released the source code into the public domain. I also wrote an article which would help guide someone through the source code at http://www.codeproject.com/useritems/cat.asp

Have fun!

 Flat View: This topic has 15 replies on 2 pages [ 1  2 | » ]
 Previous Topic Next Topic