Self Types
Christopher Diggins — 2007-06-08 18:24:56
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
Manfred Von Thun — 2007-06-15 05:21:00
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@...> 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]
Manfred Von Thun — 2007-06-15 06:27:41
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]
Manfred Von Thun — 2007-06-15 08:01:16
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]
William Tanksley, Jr — 2007-06-15 13:40:08
Manfred Von Thun <
m.vonthun@...> 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
John Cowan — 2007-06-15 17:11:33
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@...
Christopher Diggins — 2007-06-15 17:18:48
The Y and M combinators can't be typed using a simple type system without
recursive types. They can however be typed using a more sophisticated type
system that includes recursive types, dependent types, or, as I am
proposing, self types.
- Christopher
On 6/15/07, John Cowan <cowan@...> wrote:
>
> 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@... <cowan%40ccil.org>
>
>
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-06-15 22:03:02
Hi Manfred,
What you call "X" I believe corresponds directly to the classical "M"
combinator according to Brent Kerby's concatenative combinator
mapping. The SK and Lambda Calculus definitions of "M" can be found at
http://www.angelfire.com/tx4/cus/combinator/birds.html
On 6/14/07, Manfred Von Thun <m.vonthun@...> wrote:
>
> 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.
Yep.
> 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.
I have to extend the type system to handle them. The current type
system can't handle it yet. I feel I am very close to having them
working.
> Am I
> right in believing that y is not possible in Haskell and ML?
I think that Y and M are possible in Haskell using GADT's, but I am
unsure. I know that Haskell can't infer the types. I can't say
anything about ML.
> If so, then perhaps your dup apply problem would
> disappear simply by prohibiting it.
That is definitely a valid approach. However, I find that they Y and M
useful combinators (for example you can define looping constructs
using M). M can be seen as a classical combinatorial definition of
recursion. Providing a meaningful type for it is desirable for my
purposes.
> Are there any Haskellers or MLers on board?
>
> - Manfred
Christoper
Manfred Von Thun — 2007-06-18 06:11:16
On 16/6/07 3:11 AM, "John Cowan" <
cowan@...> wrote:
> 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.
Exactly. But I have never seen the actual proof. Do you have anything
at your fingertips¹, or perhaps a reference?
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-06-18 06:36:25
On 15/6/07 11:40 PM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
>
> Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.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?
My understanding is that the usual terminology is this:
At level zero there are numbers, chars, truth values, lists...
At level one there are functions successor, +, and ...
At level two there are combinators, functions which take functions
as arguments (or as values): map, fold, and many more.
I was looking for something at level three: functions which
take combinators as arguments, but which are distinct from
combinators themselves. I never found any that are distinct
from the existing bunch of Joy combinators. But there are
plenty of ways in which a combinator D can take a quoted
combinator [C] as argument, as in [C] D. The note I wrote
only examined 8 of the 64 combinations that I hinted at.
There are even more combinations once we allow combinators
that take more than one quotation, or once we allow more
complex constructions. A trivial example is
5 [dup *] [i] [i] [i] [i] [i] i => 25
where all the [i] quotations and the final i are the same i.
The whole area of combining combinators in this way is
a strange new world to me. But it has not led to any combinator
N (for new¹) such that [C] N is meaningful for a combinator [C]
but [Q] N is not meaningful for a non-combinator Q. This
is what I meant by a higher order combinator. But I do not have
a proof that there cannot be such a beast.
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-06-18 06:43:49
On 18/6/07 4:11 PM, "Manfred Von Thun" <
m.vonthun@...> wrote:
> Exactly. But I have never seen the actual proof. Do you have anything
> at your fingertips¹, or perhaps a reference?
>
I typed to my mailer Eudora: single quote, AT YOUR FINGERTIPS, single quote.
It came back to me from yahoogroups as: left paren, EAT YOUR..
I did not mean to suggest that you should nibble on your fingertips, John.
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-06-18 15:05:29
Manfred Von Thun <
m.vonthun@...> wrote:
>"William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > Manfred Von Thun <m.vonthun@...> 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?
> My understanding is that the usual terminology is this:
> At level zero there are numbers, chars, truth values, lists...
> At level one there are functions successor, +, and ...
> At level two there are combinators, functions which take functions
> as arguments (or as values): map, fold, and many more.
> I was looking for something at level three: functions which
> take combinators as arguments, but which are distinct from
> combinators themselves.
How would that distinction be achieved? You hint below that
third-order entities would NOT take a function as a parameter; but I
must point out that every combinator IS a function.
> I never found any that are distinct
> from the existing bunch of Joy combinators.
Those are complete, right?
> a strange new world to me. But it has not led to any combinator
> N (for Œnew¹) such that [C] N is meaningful for a combinator [C]
> but [Q] N is not meaningful for a non-combinator Q. This
> is what I meant by a higher order combinator. But I do not have
> a proof that there cannot be such a beast.
It seems to me that you want a function which takes combinators as
arguments, but does not take functions (right?). But because all
combinators _are_ functions, this can't be possible.
Of course, strong type-checking can make something like this possible,
as can runtime stack checks. But I sense that's not what you mean.
> - Manfred
-Billy
Manfred Von Thun — 2007-06-20 06:49:00
On 19/6/07 1:05 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> Manfred Von Thun <m.vonthun@...> wrote:
> At level zero there are numbers, chars, truth values, lists...
>> At level one there are functions successor, +, and ...
>> At level two there are combinators, functions which take functions
>> as arguments (or as values): map, fold, and many more.
>> I was looking for something at level three: functions which
>> take combinators as arguments, but which are distinct from
>> combinators themselves.
>
> How would that distinction be achieved? You hint below that
> third-order entities would NOT take a function as a parameter; but I
> must point out that every combinator IS a function.
Yes, every combinator is a function. My wording was too cryptic
perhaps. I'll try again:
At level one there are functions which take zero level entities
as arguments. At level two there are combinators which take
level one entities as arguments but cannot take level zero
entities as arguments. Examples: dip, nullary, map, filter, fold.
At level three there would be functions which take level two
entities as arguments but cannot take level one entities as
arguments. If there are such things at all, let foo be one of them.
Then the first below would be meaningful, but the second would not:
2 3 [+] [nullary] foo
2 3 [+] foo
>> I never found any that are distinct
>> from the existing bunch of Joy combinators.
>
> Those are complete, right?
It may or may not have to do with any kind of completeness, I do
not know. The existing bunch seems to be pretty useful. But I was
not looking for new level two entities, I was looking for genuinely
level three entities which are not also level two.
>> a strange new world to me. But it has not led to any combinator
>> N (for Œnew¹) such that [C] N is meaningful for a combinator [C]
>> but [Q] N is not meaningful for a non-combinator Q. This
>> is what I meant by a higher order combinator. But I do not have
>> a proof that there cannot be such a beast.
>
> It seems to me that you want a function which takes combinators as
> arguments, but does not take functions (right?). But because all
> combinators _are_ functions, this can't be possible.
If there are the kind of thing I was looking for, this would open
up enormous possibilities and complications, not necessarily
pleasant ones. So I did not really want them. I was pleased (and
often surprised) when I found ways in which existing combinators
C, D can be combined as in [C] D. So nothing third level. But
it is stillan open question as far as I can see.
- Manfred
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-06-20 08:47:48
On 6/19/07, Manfred Von Thun <
m.vonthun@...> wrote:
> On 19/6/07 1:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
>
> > Manfred Von Thun <m.vonthun@...> wrote:
>
> > At level zero there are numbers, chars, truth values, lists...
> >> At level one there are functions successor, +, and ...
> >> At level two there are combinators, functions which take functions
> >> as arguments (or as values): map, fold, and many more.
> >> I was looking for something at level three: functions which
> >> take combinators as arguments, but which are distinct from
> >> combinators themselves.
> >
> > How would that distinction be achieved? You hint below that
> > third-order entities would NOT take a function as a parameter; but I
> > must point out that every combinator IS a function.
>
> Yes, every combinator is a function. My wording was too cryptic
> perhaps. I'll try again:
>
> At level one there are functions which take zero level entities
> as arguments.
In Cat this would be the set of functions with types matching: ('A 'b -> 'C)
> At level two there are combinators which take
> level one entities as arguments but cannot take level zero
> entities as arguments. Examples: dip, nullary, map, filter, fold.
These have types that match the pattern: ('A ('B -> 'C) -> 'D)
> At level three there would be functions which take level two
> entities as arguments but cannot take level one entities as
> arguments.
These would have types: ('A ('B ('C -> 'D) -> 'E) -> 'F)
In Cat, unlike Joy, level two combinators are never also level one
combinators.
> If there are such things at all, let foo be one of them.
> Then the first below would be meaningful, but the second would not:
>
> 2 3 [+] [nullary] foo
> 2 3 [+] foo
>
> >> I never found any that are distinct
> >> from the existing bunch of Joy combinators.
> >
> > Those are complete, right?
>
> It may or may not have to do with any kind of completeness, I do
> not know. The existing bunch seems to be pretty useful. But I was
> not looking for new level two entities, I was looking for genuinely
> level three entities which are not also level two.
>
> >> a strange new world to me. But it has not led to any combinator
> >> N (for Œnew¹) such that [C] N is meaningful for a combinator [C]
> >> but [Q] N is not meaningful for a non-combinator Q. This
> >> is what I meant by a higher order combinator. But I do not have
> >> a proof that there cannot be such a beast.
> >
> > It seems to me that you want a function which takes combinators as
> > arguments, but does not take functions (right?). But because all
> > combinators _are_ functions, this can't be possible.
>
> If there are the kind of thing I was looking for, this would open
> up enormous possibilities and complications, not necessarily
> pleasant ones. So I did not really want them. I was pleased (and
> often surprised) when I found ways in which existing combinators
> C, D can be combined as in [C] D. So nothing third level. But
> it is stillan open question as far as I can see.
Is:
DEFINE f = [[dip] cons] dip.
A level-3 combinator in Joy? In general I think the secret to creating
a level-3 combinator would be to apply a level-2 combinator to the
result of calling a level-2 combinator.
If you are concerned about eliminating any possibility of level-3
combinators in Joy, can't you rewrite the definitions of the level-2
primitives so that they accept combinators or non-combinators? I don't
see the reason that "dip" can't accept straight values like "5" on the
top of the stack, if "i" can accept them. A definition of "dip" as
"swap unit cons i" should be equivalent shouldn't it? In which case
you wouldn't actually be able to say "dip" is a level-2 combinator. Or
am I missing something here?
I believe it is either good to go all the way one direction or the
other: either non-combinator values can be "evaluated" or they can't.
As far as I can see (and I could be mistaken) Joy is somewhat
ambiguous about what exactly can and can't be evaluated.
Hopefully I am not sticking my foot in my mouth here.
Cheers,
Christopher
William Tanksley, Jr — 2007-06-20 14:09:38
Manfred Von Thun <
m.vonthun@...> wrote:
> At level one there are functions which take zero level entities
> as arguments. At level two there are combinators which take
> level one entities as arguments but cannot take level zero
> entities as arguments. Examples: dip, nullary, map, filter, fold.
> At level three there would be functions which take level two
> entities as arguments but cannot take level one entities as
> arguments. If there are such things at all, let foo be one of them.
> Then the first below would be meaningful, but the second would not:
NOW I get it. Thank you for persevering.
I think Chris' explanation makes sense: Joy's type semantics are just
a bit too vague to allow a clean answer to this question. He gave the
example of 'i' and 'dip' accepting different levels for execution, in
spite of being (allegedly) mutually definable.
> - Manfred
-Billy
Manfred Von Thun — 2007-06-29 06:32:43
On 20/6/07 6:47 PM, "Christopher Diggins" <
cdiggins@...> wrote:
> On 6/19/07, Manfred Von Thun <m.vonthun@...> wrote:
>> On 19/6/07 1:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
>>
>>> Manfred Von Thun <m.vonthun@...> wrote:
[..]
>> At level one there are functions which take zero level entities
>> as arguments.
>
> In Cat this would be the set of functions with types matching: ('A 'b -> 'C)
But also binary operators such as +, <, cons and so on, also ternary
operators such as + +, ..., also operators returning several items:
+ + dup, which consumes three and yields two. I don¹t know the
upper/lower case conventions of your type notation to say whether
these cases are already included in (A b -> C). (I don¹t dare to put
in the single quotes, knowing the mess that incompatible mailers create.)
[..]
> Is:
>
> DEFINE f = [[dip] cons] dip.
>
> A level-3 combinator in Joy?
Let us see. f is of the form [..] dip, with quotation [..] on top.
Because of the dip, what is below the [..] will first be saved away
temporarily, and after [..] has been executed the saved part will
be restored. Suppose the saved part is 999. So the top of the stack
is 999 [..], the 999 will be saved, [..] executed, then 999 restored.
When [..] executes, it will push [dip] and then cons something, X,
which has to be on the stack, in front of the quotation [dip], giving
[X dip]. So we know that for f == [[dip] cons] dip to operate,
the top of the stack has to be 999, and below that X.
X 999 f
X 999 [[dip] cons] dip
X [[dip] cons] i 999
X [dip] cons 999
[X dip] 999
This is all we know so far from the specification of f.
But presumably the intention is that [X dip] is going to be executed
by some unspecified combinator. In that case it will push X and
then call dip. So X will have to be a quotation, say X = [Q].
Redoing the above derivation:
[Q] 999 f
[Q] 999 [[dip] cons] dip
[Q] [[dip] cons] i 999
[Q] [dip] cons 999
[[Q] dip] 999
So f has the effect of changing [Q], the second element of the stack
into [[Q] dip], leaving the top element 999 unchanged. So f changes
one quotation [Q] into another [[Q] dip], but it does not execute the
result. So it is a higher order function in the sense of yielding a
function,
a perfectly respectable and frequently used sense of higher order. Such
things are sometimes called functionals. But they are not the sort I was
concerned with, since the resulting quotation [[Q] dip] is not executed.
I should mention that a simpler function g == [[dip] cons] i == [dip] cons
would serve equally well as an example of a program transformer. The
999 and the outer dip in your f don¹t serve any purpose.
[..]
> If you are concerned about eliminating any possibility of level-3
> combinators in Joy, can't you rewrite the definitions of the level-2
> primitives so that they accept combinators or non-combinators? I don't
> see the reason that "dip" can't accept straight values like "5" on the
> top of the stack, if "i" can accept them.
Correction: Joy does not allow any of the following:
5 i
5 dip
5 map
2 3 + i
2 3 + dip
...
[..]
> I believe it is either good to go all the way one direction or the
> other: either non-combinator values can be "evaluated" or they can't.
> As far as I can see (and I could be mistaken) Joy is somewhat
> ambiguous about what exactly can and can't be evaluated.
can or can¹t where is the ambiguity in Joy?
In Joy the combinators always expect one or more quotations:
[Q] i
[Q] dip
[Q] map
[Q1] [Q2] concat i
[Q1] [Q2] concat dip ...
The older combinators always expect the quotation on top of the
stack. Some of the newer convenience combinators that
I have been toying with expect a numeric parameter above the
quotation:
[Q] 3 dips
would be used like this
2 3 777 888 999 [+] 3 dips ==
2 3 [+] i 777 888 999 ==
2 3 + 777 888 999
5 777 888 999
But old and new all expect a quotation
[..]
- Manfred
[Non-text portions of this message have been removed]
Manfred Von Thun — 2007-06-29 07:08:57
Progress report:
I was intrigued by the possibility of combining the combinators,
restricting myself just to unary combinators those which
expect exactly one quotation parameter in addition to other
parameters that they need. In most programming the quotation
will be something such as [+], [first], [dup *], [10 *], [cons cons],
or even just [42]. But quotations such as [i], [dip], [map], [filter]
and so on seem strange as parameters to other combinators.
Does it even make sense?
So I started to investigate the possibilities, restricting myself
to just the simplest combinations. Let C and D be combinators
such as i, dip, nullary, unary, infra, step, map, filter, fold. Do
a fairly exhaustive survey of the possible combinations of the
simplest form: [C] D.
Results: For almost all quoted combinators [C] and almost all
combinators D, the combination [C] D is legal Joy provided
any additional parameters on top of the stack are correctly chosen.
For many of these combination there seem to be some good
uses, and this area deserves further investigation.
To broaden this investigation, let O be any non-combinator,
such as 42, swap, +, cons and so on, or a concatenation of
these. Investigate combinations [O C O] O D O, were the
various Os may or may not be distinct.
None of this has anything to do with my other question,
whether there are specifically higher order combinators,
These would be ones that can take quoted combinators [i],
[dip], [map] and so on as parameters, but cannot take
quoted non-combinators as parameters, such as [42], [+], [10 *].
I have not made any progress in this area.
- Manfred
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-06-29 07:30:51
On 6/28/07, Manfred Von Thun <
m.vonthun@...> wrote:
> On 20/6/07 6:47 PM, "Christopher Diggins" <cdiggins@...> wrote:
> > On 6/19/07, Manfred Von Thun <m.vonthun@...> wrote:
> >> On 19/6/07 1:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> >>> Manfred Von Thun <m.vonthun@...> wrote:
>
> [..]
>
> >> At level one there are functions which take zero level entities
> >> as arguments.
> >
> > In Cat this would be the set of functions with types matching: ('A 'b -> 'C)
>
> But also binary operators such as +, <, cons and so on, also ternary
> operators such as + +, ..., also operators returning several items:
> + + dup, which consumes three and yields two.
I see. That is indeed not a category that can be represented using a
single Cat type then.
> I don¹t know the
> upper/lower case conventions of your type notation to say whether
> these cases are already included in (A b -> C).
Lowercase letters are types, and uppercase letters are type vectors
(or the type of a stack of values if you prefer).
[snip]
Thanks for the clarification.
> > If you are concerned about eliminating any possibility of level-3
> > combinators in Joy, can't you rewrite the definitions of the level-2
> > primitives so that they accept combinators or non-combinators? I don't
> > see the reason that "dip" can't accept straight values like "5" on the
> > top of the stack, if "i" can accept them.
>
> Correction: Joy does not allow any of the following:
>
> 5 i
> 5 dip
> 5 map
> 2 3 + i
> 2 3 + dip
> ...
> [..]
>
> > I believe it is either good to go all the way one direction or the
> > other: either non-combinator values can be "evaluated" or they can't.
> > As far as I can see (and I could be mistaken) Joy is somewhat
> > ambiguous about what exactly can and can't be evaluated.
>
> can or can¹t ‹ where is the ambiguity in Joy?
My mistake, I thought "5 i" was defined in Joy.
Sorry about the confusion.
Christopher
kuwabatake — 2007-07-04 18:42:07
> At level one there are functions which take zero level entities
> as arguments. At level two there are combinators which take
> level one entities as arguments but cannot take level zero
> entities as arguments. Examples: dip, nullary, map, filter, fold.
> At level three there would be functions which take level two
> entities as arguments but cannot take level one entities as
> arguments.
Interesting.
I propose a function called `compose'. It takes a quoted combinator
[C1] and alters that combinator to expect TWO functions on top of the
stack, compose them, and then execute C1.
For example:
[1 2 3] [2 *] [1 +] [map] compose i
=> [3 5 7]
['a] 123 ['b] [cons] [dip] compose i
=> ['a 'b]
This can be written in Joy as follows:
compose == [concat] swap concat
Note that applying compose to a non-combinator is not `meaningful':
[+] compose
=> [concat +]
it results in the meaningless function [concat +] which will throw an
error no matter what kind of input you give it.
I think we can construct other third- and even higher-level functions
using a similar technique. Of course, they are all really functions
stack->stack at heart; the distinction comes with the fact that
third-level functions only make sense when they modify second-level
functions (combinators).
~Daniel
Manfred Von Thun — 2007-07-10 07:54:10
On 5/7/07 4:42 AM, "kuwabatake" <
kuwabatake@...> wrote:
>
>> > At level one there are functions which take zero level entities
>> > as arguments. At level two there are combinators which take
>> > level one entities as arguments but cannot take level zero
>> > entities as arguments. Examples: dip, nullary, map, filter, fold.
>> > At level three there would be functions which take level two
>> > entities as arguments but cannot take level one entities as
>> > arguments.
The last sentence was supposed to mean: but cannot take ANY level
one entities as arguments. (And I really intended: and cannot take
any level zero entities as arguments.)
> Interesting.
>
> I propose a function called `compose'. It takes a quoted combinator
> [C1] and alters that combinator to expect TWO functions on top of the
> stack, compose them, and then execute C1.
>
> For example:
> [1 2 3] [2 *] [1 +] [map] compose i
> => [3 5 7]
> ['a] 123 ['b] [cons] [dip] compose i
> => ['a 'b]
>
> This can be written in Joy as follows:
> compose == [concat] swap concat
>
Your compose is not a combinator, of course, it is a level one entity. So I
conclude that you really intend as your example combinator the
combination: compose i.
Let us see. Suppose I replace the [map] in your example by [cons]:
[1 2 3] [2 *] [1 +] [cons] compose i ==
[1 2 3] [2 *] [1 +] [cons] [concat] swap concat i ==
[1 2 3] [2 *] [1 +] [concat] [cons] concat i ==
[1 2 3] [2 *] [1 +] [[concat] cons] i ==
[1 2 3] [2 *] [1 +] [concat] cons ==
[1 2 3] [2 *] [[1 +] concat]
This is a perfectly meaningful program. (Incidentally, the first two
arguments, [1 2 3] and [2 *] are not being used here, they just
stay there, but that is OK.) But: here is at least one quoted
level one function, [cons], which can serve as the argument to
your combination: compose i. So this example shows that your
combination is not a level three entity of the kind I was looking for.
> Note that applying compose to a non-combinator is not `meaningful':
> [+] compose
> => [concat +]
> it results in the meaningless function [concat +] which will throw an
> error no matter what kind of input you give it.
>
See my qualification at the top: ANY level one entities..
> I think we can construct other third- and even higher-level functions
> using a similar technique. Of course, they are all really functions
> stack->stack at heart; the distinction comes with the fact that
> third-level functions only make sense when they modify second-level
> functions (combinators).
> ~Daniel
As far as I can see, it is still an open question, although after trying and
failing for a long time one is tempted to conclude that the search must
fail.
But a proof of impossibility is needed, not a failed search.
>
Nice try, Daniel. Welcome to the group, and stay with us.
>
- Manfred
[Non-text portions of this message have been removed]
kuwabatake — 2007-07-10 17:40:54
> Your compose is not a combinator, of course, it is a level one
entity. So I
> conclude that you really intend as your example combinator the
> combination: compose i.
Good catch. That makes what I was saying come closer to making sense :)
> Let us see. Suppose I replace the [map] in your example by [cons]:
...
> But: here is at least one quoted
> level one function, [cons], which can serve as the argument to
> your combination: compose i. So this example shows that your
> combination is not a level three entity of the kind I was looking for.
From here, I see two options:
1. You've convinced me, I'll look around for a proof.
2. `cons' and other list operators are really combinators!
Since (unless I am misunderstanding Joy semantics) lists are also
functions, `cons' can also be thought of as a combinator which expects
a function and composes it with the next token on the stack. The only
sensible definition for combinator I can think of is `a function which
fails if it does not receive a quoted function at the appropriate
position on the stack', which certainly holds true of cons and other
`list' operators.
Of course, all of this semantics is really up to the language
designer. If `cons' cannot be considered a combinator, but only a
first-level list function, you'll have convinced me to start on a
proof of nonexistence.
> Nice try, Daniel. Welcome to the group, and stay with us.
Thanks!
~Daniel
PS
A nit-picky correction of your program run:
[1 2 3] [2 *] [1 +] [cons] compose i ==
[1 2 3] [2 *] [1 +] [cons] [concat] swap concat i ==
[1 2 3] [2 *] [1 +] [concat] [cons] concat i ==
[1 2 3] [2 *] [1 +] [concat cons] i ==
[1 2 3] [2 *] [1 +] concat cons ==
[1 2 3] [2 * 1 +] cons ==
[[1 2 3] 2 * 1 +]
I think this is how it would actually go, and my test run seems to agree.