# 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.