6 views

Skip to first unread message

Apr 26, 2008, 12:18:14 PM4/26/08

to catla...@googlegroups.com

Here is a Cat puzzle, for anyone interested in helping out:

I have to perform a "simple" transform on Cat code. Given a sequence

of instruction, I need to transform it so that I pass a value on the

top of the stack from instruction to instruction, like so:

define f { inc inc inc }

e.g. 1 f == 3

define fM { [inc] dip [inc] dip [inc] dip }

e.g.

1 42 fM == 3 42

While at first the "dip" approach looks fine, there is a problem:

define g { [inc] apply }

define gM { [[inc] dip] dip [apply] dip }

1 42 gM == *stack underflow error*

So what is needed is a more sophisticated function for transforming

each instruction and perhaps a new composition function.

Perhaps the following observations could be helpful:

f g h == [f] [g] compose apply [h] compose apply

f g h == [f] [g] compose [h] compose apply

For those aware of monad theory, this is very closely related. I

suspect that the answer lies in mapping the problem to monads, but I

haven't yet found a correct transform.

Any help would be really appreciated.

- Christopher

Apr 26, 2008, 10:13:05 PM4/26/08

to catla...@googlegroups.com

On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

> Here is a Cat puzzle, for anyone interested in helping out:

>

> I have to perform a "simple" transform on Cat code. Given a sequence

> of instruction, I need to transform it so that I pass a value on the

> top of the stack from instruction to instruction, like so:

What I was experimenting with in Fifth was having all operations work

below the top of the stack:

dup :: A b c -> A b b c

i :: A (A -> B) c -> B c

pop :: A b c -> A c

If you do this, it's trivial to solve the problem as you can pass any

collection of data along the top of the stack. You then just need

access functions like this:

update-top :: A b c -> A b

read-top :: A b -> A b b

The reason I eventually decided against this for Fifth was that you

need to pass "top" through the *entire program* for the types to be

propagated properly. This breaks abstraction boundaries between

modules and so on. This might be an acceptable solution in Cat.

Before I think about solving this in Cat as it stands now: Do the

translations need to be type safe or type preserving? If so, you'll

run into the issue of not being able to perform the expected

translations in some cases due to the type of '[$a $b] [$c] compose'

not necessarily equaling the type of '[$a] [$b $c] compose' (if it can

even be assigned one). I've been doing some thinking and I believe you

may be right here: A 'compositional' type system that's handles

transformations properly is needed. I may even be going without one

until this problem is solved.

- John

Apr 26, 2008, 10:21:29 PM4/26/08

to catla...@googlegroups.com

On Sat, Apr 26, 2008 at 10:13 PM, John Nowak <jo...@johnnowak.com> wrote:

>

>

> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>

> > Here is a Cat puzzle, for anyone interested in helping out:

> >

> > I have to perform a "simple" transform on Cat code. Given a sequence

> > of instruction, I need to transform it so that I pass a value on the

> > top of the stack from instruction to instruction, like so:

>

> What I was experimenting with in Fifth was having all operations work

> below the top of the stack:

>

> dup :: A b c -> A b b c

> i :: A (A -> B) c -> B c

> pop :: A b c -> A c

>

> If you do this, it's trivial to solve the problem as you can pass any

> collection of data along the top of the stack. You then just need

> access functions like this:

>

> update-top :: A b c -> A b

> read-top :: A b -> A b b

>

> The reason I eventually decided against this for Fifth was that you

> need to pass "top" through the *entire program* for the types to be

> propagated properly. This breaks abstraction boundaries between

> modules and so on. This might be an acceptable solution in Cat.

>

>

> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>

> > Here is a Cat puzzle, for anyone interested in helping out:

> >

> > I have to perform a "simple" transform on Cat code. Given a sequence

> > of instruction, I need to transform it so that I pass a value on the

> > top of the stack from instruction to instruction, like so:

>

> What I was experimenting with in Fifth was having all operations work

> below the top of the stack:

>

> dup :: A b c -> A b b c

> i :: A (A -> B) c -> B c

> pop :: A b c -> A c

>

> If you do this, it's trivial to solve the problem as you can pass any

> collection of data along the top of the stack. You then just need

> access functions like this:

>

> update-top :: A b c -> A b

> read-top :: A b -> A b b

>

> The reason I eventually decided against this for Fifth was that you

> need to pass "top" through the *entire program* for the types to be

> propagated properly. This breaks abstraction boundaries between

> modules and so on. This might be an acceptable solution in Cat.

No, this is not what I want. I want to literally rewrite certain

portions of code to have the new semantics. Simply redefining the

language is unfortunately not acceptable.

> Before I think about solving this in Cat as it stands now: Do the

> translations need to be type safe or type preserving?

No, I just want to preserve the semantics, using an algorithmic translation.

> If so, you'll

> run into the issue of not being able to perform the expected

> translations in some cases due to the type of '[$a $b] [$c] compose'

> not necessarily equaling the type of '[$a] [$b $c] compose' (if it can

> even be assigned one). I've been doing some thinking and I believe you

> may be right here: A 'compositional' type system that's handles

> transformations properly is needed. I may even be going without one

> until this problem is solved.

>

> - John

Do you have any ideas on how to perform the translation?

- Christopher

Apr 26, 2008, 10:51:09 PM4/26/08

to catla...@googlegroups.com

I thought I'd follow up with a more concrete example of what I want:

define x2 { dup add }

1 x2 x2 [x2] apply

== 8

One possible transformation might be something like:

1 0 [x2] unitM [x2] unitM bindM [[x2] unitM] unknownM bindM [apply]

unitM bindM apply

== 8 0

If this is correct then what I need to do here is fill in the

definitions for "unitM", "bindM", and "unknownM".

There is one tricky part though, and that is within: [[x2] unitM] I

may want simply insert a "[dup writeln] returnM" and expect it to

write the top value on the stack.

e.g. [[x2] unitM [dup writeln] returnM]

Unfortunately I don't know what "returnM" should be neither!

I used the term "unitM" to represent the fact that it resembles the

monadic unit function, and the term "bindM" because it resembles a

monadic bind (or compose) function, and "returnM" because it resembles

the monadic return function. At least this is what it appears, I could

be completely wrong in this. I don't really care that much though

about monads, the issue is really on creating the correct algorithmic

translation.

Thanks in advance,

Christopher

Apr 27, 2008, 1:03:57 AM4/27/08

to catla...@googlegroups.com

On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>

> Here is a Cat puzzle, for anyone interested in helping out:

>

> I have to perform a "simple" transform on Cat code. Given a sequence

> of instruction, I need to transform it so that I pass a value on the

> top of the stack from instruction to instruction, like so:

Should the instructions be able to access this value?

> define f { inc inc inc }

> e.g. 1 f == 3

> define fM { [inc] dip [inc] dip [inc] dip }

> e.g.

> 1 42 fM == 3 42

I assume you mean '4 42' for the result.

> While at first the "dip" approach looks fine, there is a problem:

> define g { [inc] apply }

> define gM { [[inc] dip] dip [apply] dip }

> 1 42 gM == *stack underflow error*

Is the correct translation not '[[inc]] dip [apply] dip'?

> 1 42 [[succ]] dip [i] dip stack .

[42 2]

> Perhaps the following observations could be helpful:

> f g h == [f] [g] compose apply [h] compose apply

This is incorrect. Perhaps you mean this:

f g h == [f] [g] compose apply [h] apply

- John

Apr 27, 2008, 1:21:56 AM4/27/08

to catla...@googlegroups.com

On Sun, Apr 27, 2008 at 1:03 AM, John Nowak <jo...@johnnowak.com> wrote:

>

>

> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>

> >

> > Here is a Cat puzzle, for anyone interested in helping out:

> >

> > I have to perform a "simple" transform on Cat code. Given a sequence

> > of instruction, I need to transform it so that I pass a value on the

> > top of the stack from instruction to instruction, like so:

>

> Should the instructions be able to access this value?

>

>

> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>

> >

> > Here is a Cat puzzle, for anyone interested in helping out:

> >

> > I have to perform a "simple" transform on Cat code. Given a sequence

> > of instruction, I need to transform it so that I pass a value on the

> > top of the stack from instruction to instruction, like so:

>

> Should the instructions be able to access this value?

Certain functions would, the idea is that I could insert anywhere a

function which outputs the top of the stack, as long it puts it back

afterwards.

> > define f { inc inc inc }

> > e.g. 1 f == 3

> > define fM { [inc] dip [inc] dip [inc] dip }

> > e.g.

> > 1 42 fM == 3 42

>

> I assume you mean '4 42' for the result.

Yes, thanks for the correction.

> > While at first the "dip" approach looks fine, there is a problem:

> > define g { [inc] apply }

> > define gM { [[inc] dip] dip [apply] dip }

> > 1 42 gM == *stack underflow error*

>

> Is the correct translation not '[[inc]] dip [apply] dip'?

That would be correct if it weren't for the fact that I need to also

be able to access the top of the stack at certain points.

For example I might want to insert "dup writeln" as follows:

[[inc dup writeln]] dip [apply] dip.

This is similar to what Wadler refers to as "getting out of the monad"

(http://citeseer.ist.psu.edu/wadler92essence.html)

Sorry that I didn't clearly state this requirement earlier.

> > 1 42 [[succ]] dip [i] dip stack .

> [42 2]

>

> > Perhaps the following observations could be helpful:

> > f g h == [f] [g] compose apply [h] compose apply

>

> This is incorrect. Perhaps you mean this:

>

> f g h == [f] [g] compose apply [h] apply

Yes, thanks again.

> - John

- Christopher

Apr 27, 2008, 3:43:07 AM4/27/08

to catla...@googlegroups.com

On Apr 27, 2008, at 1:21 AM, Christopher Diggins wrote:

> On Sun, Apr 27, 2008 at 1:03 AM, John Nowak <jo...@johnnowak.com>

> wrote:

>

>> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

>>

>>> Here is a Cat puzzle, for anyone interested in helping out:

>>>

>>> I have to perform a "simple" transform on Cat code. Given a sequence

>>> of instruction, I need to transform it so that I pass a value on the

>>> top of the stack from instruction to instruction, like so:

>>

>> Should the instructions be able to access this value?

>

> Certain functions would, the idea is that I could insert anywhere a

> function which outputs the top of the stack, as long it puts it back

> afterwards.

It sounds like what you're looking for isn't possible to do in a safe

way, but I'd clarification first before I start explaining myself. Can

you provide an example of how you'd like to use it

- John

Apr 27, 2008, 8:47:57 AM4/27/08

to catla...@googlegroups.com

On Sun, Apr 27, 2008 at 3:43 AM, John Nowak <jo...@johnnowak.com> wrote:

>

> On Apr 27, 2008, at 1:21 AM, Christopher Diggins wrote:

>

> > On Sun, Apr 27, 2008 at 1:03 AM, John Nowak <jo...@johnnowak.com>

> > wrote:

> >

> >> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

> >>

> >>> Here is a Cat puzzle, for anyone interested in helping out:

> >>>

> >>> I have to perform a "simple" transform on Cat code. Given a sequence

> >>> of instruction, I need to transform it so that I pass a value on the

> >>> top of the stack from instruction to instruction, like so:

> >>

> >> Should the instructions be able to access this value?

> >

> > Certain functions would, the idea is that I could insert anywhere a

> > function which outputs the top of the stack, as long it puts it back

> > afterwards.

>

> It sounds like what you're looking for isn't possible to do in a safe

> way,

>

> On Apr 27, 2008, at 1:21 AM, Christopher Diggins wrote:

>

> > On Sun, Apr 27, 2008 at 1:03 AM, John Nowak <jo...@johnnowak.com>

> > wrote:

> >

> >> On Apr 26, 2008, at 12:18 PM, Christopher Diggins wrote:

> >>

> >>> Here is a Cat puzzle, for anyone interested in helping out:

> >>>

> >>> I have to perform a "simple" transform on Cat code. Given a sequence

> >>> of instruction, I need to transform it so that I pass a value on the

> >>> top of the stack from instruction to instruction, like so:

> >>

> >> Should the instructions be able to access this value?

> >

> > Certain functions would, the idea is that I could insert anywhere a

> > function which outputs the top of the stack, as long it puts it back

> > afterwards.

>

> It sounds like what you're looking for isn't possible to do in a safe

> way,

I am pretty sure it is, look at the Wadler paper I linked earlier.

> but I'd clarification first before I start explaining myself. Can

> you provide an example of how you'd like to use it

program = stack a b c d e f

The transform allows me to

stack state m(a b c print_state d e f)

Where "m" denotes the rewriting strategy (i.e. monadic transform).

This rewriting is not done at run-time, or as part of the language,

but is done by the compiler.

- Christopher

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu