Transformation puzzle
Christopher Diggins
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
John Nowak
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
Christopher Diggins
>
>
> 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
Christopher Diggins
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
John Nowak
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
Christopher Diggins
>
>
> 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
John Nowak
> 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
Christopher Diggins
>
> 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