Christopher Diggins | 4 Jun 00:53 2007
Picon

[stack] Cat to C++ Translator written in C++

I've just released version 0.1 of a public domain Level-1 Cat to C++
compiler (written in C++) at
http://code.google.com/p/cat-language/downloads/list. This
implementation bootstraps a Level-1 implementation of Cat from a
Level-0 implementation. There are a hundred unit tests and only a
handful of predefined functions so this is a very stable release.

The translation is done without static type-checking instead the
resulting code is implemented using optimized polymorphic variant
types (see http://www.ddj.com/dept/cpp/184402027 and
http://www.codeproject.com/cpp/dynamic_typing.asp ) and stable
fast-growing stacks (see http://www.codeproject.com/cpp/fast-stack.asp
).

For an updated list of primitives that now contains unit tests for all
of the level-0 and level-1 primitives and better definitions see
http://www.cat-language.com/primitives.html.

This release is primarily intended to help people who are interested
in possibly using Cat as a back-end for other programming languages
but who prefer to work with C++ than C#. However, the code base is
should be useful to any language implementer. Using Cat as a back-end
now gets you the following for free:

- an interactive interpreter (written in C#)
- a Cat to MSIL compiler (this is built in to the interpreter)
- a Cat to C++ translator (written in C++)

These are all projects which I have been developing single-handedly.
As more people get involved, you can expect to see the number of
compilers and translators to and from Cat increase quickly.

Other Cat projects by other people that I am aware of are:

- a statically typed Cat to C++ translator
- a Cat to assembly translator
- a Cat to Omega (a dialect of Haskell) translator

Cheers,
Christopher Diggins
http://www.cdiggins.com

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New web site?

Drive traffic now.

Get your business

on Yahoo! search.

Yahoo! Groups

Take a Survey

express your ideas

share your opinion

.

__,_._,___
Christopher Diggins | 5 Jun 22:28 2007
Picon

[stack] Typed Concatenative Continuations

There is an interesting discussion on the type of a
call-with-current-continuation operation in Cat at
lambda-the-ultimate.org ( http://lambda-the-ultimate.org/node/2281 )

Christopher

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New web site?

Drive traffic now.

Get your business

on Yahoo! search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
William Tanksley, Jr | 5 Jun 23:07 2007
Picon

Re: [stack] Typed Concatenative Continuations

Christopher Diggins <cdiggins <at> gmail.com> wrote:
> There is an interesting discussion on the type of a
> call-with-current-continuation operation in Cat at
> lambda-the-ultimate.org ( http://lambda-the-ultimate.org/node/2281 )

Yes, you should definitely read the paper they mention on delimited
continuations. They're phenomenally more generally useful than
conventional continuations. They're also very easy to implement in a
stack language, although typechecking them would present some
interesting challenges (I put some thought into that a while ago --
essentially, you want to make sure that the runtime changes in control
flow will always land on a valid stack state; I didn't come up with
any concrete solutions, but I do suspect it won't be extremely hard).

> Christopher

-Billy

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

Search Ads

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
William Tanksley, Jr | 6 Jun 00:14 2007
Picon

Re: [stack] Typed Concatenative Continuations

I claimed that you should read about delimited continuations. I
continue to assert that, but I have to say that the link they gave you
was pretty hard to use to learn about that (although interesting in
its own right!).

A better link is http://citeseer.ist.psu.edu/139515.html.

-Billy

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New business?

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
Christopher Diggins | 8 Jun 20:24 2007
Picon

[stack] Self Types

My previous plan for dealing with recursive (self-referential) types
was to use labels. I am currently looking at using "self" types, which
are more limited, but I think sufficient.

http://cdiggins.com/2007/06/07/self-types/

Christopher

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

Search Ads

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
Manfred Von Thun | 15 Jun 07:21 2007
Picon
Picon

Re: [stack] Self Types

I can¹t extract the paragraph from your link, so I have to paraphrase:
You mention the difficulty of typing what in Cat is dup apply, or in Joy
dup i. I have occasionally defined a combinator x == dup i, and I chose
that name because it resembles the y combinator. In particular, x can
do whatever y can do: implement recursive execution without a recursive
definition. See the section ³Self-application² in my note:

http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-nestrec.html

My recollection is that there are some difficulties about typing the
y combinator in lambda calculus languages, but don¹t ask me for details.
Presumably the same holds for the y combinator in concatenative
languages, and by extension, for the x combinator in Joy and hence
for dup apply in Cat. Hope this helps.

- Manfred

On 9/6/07 4:24 AM, "Christopher Diggins" <cdiggins <at> gmail.com> wrote:
>
> My previous plan for dealing with recursive (self-referential) types
> was to use labels. I am currently looking at using "self" types, which
> are more limited, but I think sufficient.
>
> http://cdiggins.com/2007/06/07/self-types/
>
> Christopher
>
>

[Non-text portions of this message have been removed]

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New business?

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
Manfred Von Thun | 15 Jun 08:27 2007
Picon
Picon

Re: [stack] Self Types

Further to my previous reply:

Cat seems to be related to Joy in the same way as
Haskell and (the functional subset of) ML are related
to (the functional subset of) Lisp/Scheme: Cat is
strongly typed and Joy is not.

A good question to ask: Even if y and x are possible in Joy
just as y is possible in Lisp/Scheme, it might just be that
y and x (your dup apply) are not possible in Cat. Am I
right in believing that y is not possible in Haskell and ML?
If so, then perhaps your dup apply problem would
disappear ­ simply by prohibiting it.

Are there any Haskellers or MLers on board?

- Manfred

[Non-text portions of this message have been removed]

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

Need traffic?

Drive customers

With search ads

on Yahoo!

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
Manfred Von Thun | 15 Jun 10:01 2007
Picon
Picon

[stack] Combining Combinators


Years ago I sometimes wondered whether there could be
any higher order combinators. Just as ordinary combinators
take a (quoted program to compute a) function as argument
from the stack, so a second order combinator would take
a (quoted program to compute a) combinator as argument
from the stack. I never found anything that is distinctly
second order ­ anything I found also worked first order.

Recently I approached the topic again, this time from a different
angle, restricting myself just to existing unary combinators,
those that take just one quotation as argument.

Let C and D be any from i, dip, nullary, unary, map, step, infra
and filter. C and D could be the same. Now look at all
combinations of the form

[C] D

So the D combinator is to take as its parameter the quotation
[C] from the stack, and below that whatever else is needed.

First, to get the feel for it all, let [C] be the simplest: [i], and
let D range over the list given above.

(1) D = i: (Boring!)
2 3 [+] [i] i => 5

(2) D = dip:
2 3 [+] 999 [i] dip => 5 999

(3) D = nullary:
2 3 [+] [i] nullary => 2 3 [+] 5

(4) D = unary:
2 3 [+] [i] unary => 2 3 5

Comment: 2 3 [+] nullary => 2 3 5,
So we conclude: [i] unary == nullary

(5) D = map. So below the [i] quotation, a list is expected.
and it will have to be a list of quotations for i to execute.
2 3 [[+][*][>][dup *]] [i] map => 2 3 [5 6 false 9]

(6) D = step
Recall that step expects a list below its quotation parameter,
it sequentially puts the members of that list onto the stack
and the executes the quotation for each of them. So if the
quotation is [i], the list will have to be a list of quotations.
2 3 [[+][dup *]] [i] step => 25
So [i] step behaves as if it first concatenates the list of quotations
and then executes it: 2 3 [+ dup *] => 25

(7) D = infra
Recall that infra expects a list below its quotation parameter,
It then treats that list as the stack, and replaces that list by
the result stack.
[[dup *] 3 4 5] [i] infra => [9 4 5]

(8) D = filter
5 [[3 <][10 <][4 <][20 <]] [i] filter => 5 [[10 <][20 <]]

That is quite a collection already, all giving a few surprising
results. These should really be in the toolbox of any
concatenative programmer ­ or perhaps just for the Joy
programmer. But this collection is only the start, because
[C] could be any of the list of 8 combinators. In total
there are 8*8 = 64 combinations to be examined. I have
a few more, but I am far from having a systematic collection.
I shall report on my progress soon.

- Manfred

[Non-text portions of this message have been removed]

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New business?

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
William Tanksley, Jr | 15 Jun 15:40 2007
Picon

Re: [stack] Combining Combinators

Manfred Von Thun <m.vonthun <at> latrobe.edu.au> wrote:
> Years ago I sometimes wondered whether there could be
> any higher order combinators.

I don't see how there couldn't be. Joy functions are higher-order, so
wouldn't Joy's combinators also be higher-order?

Perhaps I'm just confused.

-Billy

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

New business?

Get new customers.

List your web site

in Yahoo! Search.

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___
John Cowan | 15 Jun 19:11 2007

Re: [stack] Self Types

Manfred Von Thun scripsit:

> My recollection is that there are some difficulties about typing the
> y combinator in lambda calculus languages, but don¹t ask me for details.

The difficulty is that it can't be done, on Russell type theory grounds.

--
Don't be so humble. You're not that great. John Cowan
--Golda Meir cowan <at> ccil.org

__._,_.___
SPONSORED LINKS
Yahoo! Finance

It's Now Personal

Guides, news,

advice & more.

Need traffic?

Drive customers

With search ads

on Yahoo!

Yahoo! Groups

Start a group

in 3 easy steps.

Connect with others.

.

__,_._,___

Gmane