# Re[2]: [stack] Ideas slowly growing in my head.

## sz — 2000-12-21 08:56:15

    Hello Phimvt,

    среда, 20 декабря 2000 г., you wrote:

     >> The idea is very cute and simple and I explain it down here in brief.

    >>

    >> There is a set of stack pictures:

    >>         %a <- %A

    >> (%a - is an unknown stack picture, <- - "belongs to", %A - set of

    >> possible stack pictures.)

    >>

    >> There is a set of stack effects:

    >> (%a -- %b)

    >> which forms set S of stack effects.

    >>

    >> For stack effects a multiplication operation is defined:

    >> (%a -- %b %c) (%c -- %d) === (%a -- %b %d)

    >> (%a -- %b) (%c %b -- %d) === (%c %a -- %d)

    >> other combination of stack effects produce 0 - type clash.

     pllea> It would be nice to see some examples - I could not quite

    pllea> see how this would look like in practice

    It is more a matter of language design. For example:

    intToCharString 1 == '1 "Wow! One!!" ;

    intToCharString 2 == '2 "Wow! Two!!!" ;

    intToCharString _ == '? "Unknown number." ;

    or (without variables but with different meaning)

    intToCharString == intToStr '. swap ;

    given intToStr transformes integer into string.

    And imaginary compiler or interpreter would give typing information

    like this:

    intToCharString (Int -- Char [Char List]) ;

    Sequencing two intToCharString will produce type clash, because of

    type mismatch:

    (Int -- Char [Char List]) (Int -- Char [Char List])

    Given putStr, which clearly has stack effect of

    putStr ([Char List] --) ;

    we may produce following prorgam:

    intToCharString putStr

    which has stack effect

    (Int -- Char)

    calculated from concatenation of two stack effects

    (Int -- Char [Char List]) ([Char List] --)

    I think that it would be easier to explain in another way.

    We may define a ordering operator '<=' for stack effect lists like

    this:

    %a <= %b if there is (may be empty) list %c such that concatenating %c

    with %a gives us %b. Otherwise %a is greater than %b or they cannot be

    compared. %a and %b cannot be compared if NOT (%a <= %b) and NOT

    (%b <= %a).

     >> Combinator dequo is the new name for good old i combinator, which

    >> has name which is too short for my purposes. I prefer i to be name

    >> of variable, as it will be referred more often. By the way, dequo

    >> stack effect is

    >>         (%a (%a -- %b) -- %b).

    >>

     pllea> If you want type variables (even multiletter) that will not be

    pllea> mistaken for Joy2 operators, maybe you should use capitals -

    pllea> they are hardly used in Joy except for a tiny number of reserved

    pllea> words that will hardly be confused with the type variables.

    I think that it is simpler to distinguish between language phrases. In

    type definition phrase there should be no Joy combinators, as in stack

    effect declaration. But we still have to distinguish between types and

    polymorphic variables and stack effect lists. And stack effect lists

    will occur very rarely, of course (the places we need them are i or

    deque and ifte combinators). So, from information theory, we can put

    almost arbitrary long prefixes before them. ;)

     >>

    >> I should also note that I think that quotation should have only composition

    >> operation, because decomposition of quotation is meaningless (in my humble

    >> opinion).

     pllea> I agree in a way. Joy currently is an "intensional language", and

    pllea> it is not entirely clear whether that is a good idea. You might

    pllea> want to look at my (relatively new) paper "Rationale for Joy"

    pllea> on the web page. I discuss the problem(?) towards the end.

    pllea> For a compiled version of Joy indeed such a prohibition makes

    pllea> a lot of sense.

    I think I should reread it.

     >> I think that my system should be compiler-oriented rather than

    >> interpreter-oriented. That's where all complication grow from.

    >>

    >> I split identifier into keywords (such as "module", "data", "typesyn" etc),

    >> (de)constructors (like "True" or "List") and definitions ("dup").

    >>

     pllea> Don't be too ambitious. Try small things first. Modules might be

    pllea> a great, useful and perhaps indispensible idea, but not for a

    pllea> first version.

    Well, I need at least one module. ;)

    pllea> . But essential characteristics of type for

     >> compiler to deal with it freely is the presence of dup and drop

    >> operations. One operation produces a copy of item, another - deletes

    >> it. Objects with these operations are non-linear (in the sense of

    >> linear logic). Restricting dup and drop rights we may get desirable

    >> effects - for example, the only way for FILE object to disappear is

    >> to use fclose definition:

    >>         fclose (FILE -- ERRNO) ;

    >>

     pllea> I would like to see more examples of how you think the dup and drop/pop

    pllea> operations should be restricted, and what benefit that would have.

    If we restrict drop operation on file descriptors then the only way to

    get rid of them is through fclose function. Then we will need to get

    rid of returned error code. We may as well restrict drop operation for

    system error codes so programmer will be forced to check it.

    If we do not use reference copying (where copy operation copies only

    reference) then every object could be either in heap or referenced

    only once (although indirectly through container as in List type).

    Object deconstruction (such as pattern matching) destroys object and

    puts it into heap while revealing it's internals. This puts us into

    manual heap management but when compiler/interpreter can tells us

    where something is going wrong. Also there is no need for any garbage

    collection.

    It is explained in better english and in greater detail in Henry Baker

    online papers (at http://linux.rice.edu/~rahul/hbaker/)

    ForthStack.html and LinearLisp.html.

    pllea> In general, if you want more discussion, give us some examples of

    pllea> a) wrongly typed programs (with proposed error message), and

    test == intToString intToString ;

    Error (file.j, line x, def 'test'): concatenation type clash:

    intToString (Int -- [Char List])

    intToString (Int -- [Char List])

    pllea> b) correctly typed programs (with proposed run time behaviour), and

    Variant I.

    Definition 'main' should have effect (--).

    main ==

         "Hello, world!" // (-- [Char List])

         putStr          // ([Char List] --)

    ;

    The knowledge on how to deal with side effects is completely hidden

    inside of Joy system. If it decides to reorder computation - we

    wouldn't know. (Such reordering is good for, for example, file stream

    operations and libraries like OpenGL. It is also work in Variant ][.)

    But we operate with less entities.

    Variant ][.

    Definition 'main' should have effect (World -- World).

    main == "Hello, world!" // World [Char List]

         swap           // [Char List] World

         putStr // [Char List] World -- World

    ;

    Then we may (and have to) specify which part of program should

    interact with outer world.

    pllea> c) programs (if any) which would be OK in Joy but not in your

    pllea>    typed version.

    factorial == 0 swap produce_ni mul_ni ;

    mul_ni == [swap dup 0 =] [drop] [* mul_ni] ifte ;

    produce_ni == [dup 0 =] [drop] [dup 1 -] ifte ;

    First we mark top of stack using zero then produce a variable list of

    n[i] until 1 in stack then consume them using *.

    Second and third quotations in produce_ni has different stack effect.

    Second has (a -- ) and third has (Int -- Int Int). Of course, they

    doesn't match.

    Definition mul_ni has problems too. First quotation tells us that we

    have on input two values of unknown type a and of type Int. Second

    quotation has no problems, it just discards Int (zero) argument. Third

    quotation tells us that type a is actually Int and that we should have

    at least one more Int on input.

    Right now I cannot show how mul_ni will produce type clash. But

    produce_ni certainly will.

    pllea> As to c), you will, I take it, allow lists of lists. But will you

    pllea> allow heterogenous lists, consisting, say, of a name (a string or

    pllea> a list of chars) and a phone number?

    pllea>    [ [ "Mary"  19827364 ]

    pllea>      [ "Jane"  83472364 ] ]

    For me it is better to put them into constructor.

    data NamePhone == [Char List] Int NamePhone ;

    pllea> You might have to go for what in ML and Haskell are called tuples,

    pllea> I think (experts please comment).

    Yes, I know about them. I used them, but they are, in fact, short

    constructors for faster usage.

    pllea> As a final comment, I would urge you not to attempt a compiler, not

    pllea> even one that compiles into C or Oberon or whatever. Try your ideas

    pllea> about typing Joy on an interpreter, it is so much easier.

    pllea> In any case, best wishes for your project.

    pllea> To all in the group, a happy Christmas.

    This is some kind of off-topic but in Russia it is used to celebrate

    catholic Christmas, then New Year, then Russian Orthodox Christmas,

    then Old New Year (in Russian Orthodox Church calendar). Old New Year

    happens at 14 January. The only unhappy thing is that almost all

    celebration are unofficial (we have to go to work), but who cares?

    Buy!

     sz                            mailto:sz@...

## Dirk-Ulrich Heise — 2000-12-21 10:15:21

    -----Ursprungliche Nachricht-----

    Von: "sz" <sz@...>

     > If we restrict drop operation on file descriptors then the only way to

    > get rid of them is through fclose function. Then we will need to get

    > rid of returned error code. We may as well restrict drop operation for

    > system error codes so programmer will be forced to check it.

    >

    > If we do not use reference copying (where copy operation copies only

    > reference) then every object could be either in heap or referenced

    > only once (although indirectly through container as in List type).

    > Object deconstruction (such as pattern matching) destroys object and

    > puts it into heap while revealing it's internals. This puts us into

    > manual heap management but when compiler/interpreter can tells us

    > where something is going wrong. Also there is no need for any garbage

    > collection.

     Hello!

    I'm rather new on this list, i'm interested in Joy because it looks

    so much like Forth, yet has a completely different background.

    Though i skimmed through the joy material on the web, i don't

    have an idea of its object semantics. When does it finalize

    objects? I think it would be a very bad idea to leave management

    to the user, like, having to call an explicit fclose instead of leaving

    it to some automatic destruction.

    I wrote a Forth interpreter in Python; it's available in the files section

    of the egroup www.egroups.com/group/synthetoforth . It's dog slow

    but it's a prototype. I use Python object semantics (i've heard

    people saying that that's about equivalent to Scheme semantics),

    and Python polymorphism; so it's sort of a enhanced Forth.

    What my Forth does is this: a "dup" would duplicate a reference

    to a fileobject (there are no fileobjects, just as an example; it could

    be extended to have them); using underlying Python refcounting.

    As soon as the last ref to the object goes away (say, by dropping),

    the file object would be destroyed automatically, thus, closing the

    file. At the moment i'm in the process of recoding the whole thing in

    C++ to get more speed, but for this i have to rebuild the refcounting

    model of Python. Refcounting is not perfect by itself, as it doesn't

    destroy cyclical object structures, but it's far better than manual

    management of heap structures! I come from a C++ background and

    went to Python, i should know!

    Could someone give me a pointer to info about Joy's object

    semantics?

    BTW, now i was talking about objects.. You might say that Joy

    isn't planned to be OO for the time being, but it suffices completely

    to talk about built-in objects like floats, strings or lists of chars to

    get to the question "When is the object storage freed / the object

    finalized" or "what happens during a dup - copying a reference or

    copying the content?" Even if you say "dup copys a function because

    everything in Joy is a function", i would say: Don't pretend the

    problem isn't there! Or did i miss something important?

    Dipl.Inform. Dirk-Ulrich Heise

    business: hei@...

    private: dheise@...

## phimvt@lurac.latrobe.edu.au — 2000-12-22 02:15:51

    On Thu, 21 Dec 2000, sz wrote:

     > Hello Phimvt,

    >

    > ñðåäà, 20 äåêàáðÿ 2000 ã., you wrote:

    >

    > It is more a matter of language design. For example:

    >

    > intToCharString 1 == '1 "Wow! One!!" ;

    > intToCharString 2 == '2 "Wow! Two!!!" ;

    > intToCharString _ == '? "Unknown number." ;

     So, pattern matching? I have considered this several times,

    but put it into the "maybe-later" basket

    [lots of explanation snipped]

     > I think that it would be easier to explain in another way.

    > We may define a ordering operator '<=' for stack effect lists like

    > this:

    > %a <= %b if there is (may be empty) list %c such that concatenating %c

    > with %a gives us %b. Otherwise %a is greater than %b or they cannot be

    > compared. %a and %b cannot be compared if NOT (%a <= %b) and NOT

    > (%b <= %a).

     Yes, something along these lines seems correct

    [More snips]

     > pllea> I would like to see more examples of how you think the dup and drop/pop

    > pllea> operations should be restricted, and what benefit that would have.

    >

    > If we restrict drop operation on file descriptors then the only way to

    > get rid of them is through fclose function. Then we will need to get

    > rid of returned error code. We may as well restrict drop operation for

    > system error codes so programmer will be forced to check it.

     I _think_ I understand

     > pllea> In general, if you want more discussion, give us some examples of

    > pllea> a) wrongly typed programs (with proposed error message), and

    >

    > test == intToString intToString ;

    >

    > Error (file.j, line x, def 'test'): concatenation type clash:

    > intToString (Int -- [Char List])

    > intToString (Int -- [Char List])

     Yes, this is the sort of thing I meant. Lots more, including the

    really hard ones.

     > pllea> b) correctly typed programs (with proposed run time behaviour), and

    >

    > Variant I.

    > Definition 'main' should have effect (--).

    > main ==

    >      "Hello, world!" // (-- [Char List])

    >      putStr          // ([Char List] --)

    > ;

     Right.

     > Variant ][.

    > Definition 'main' should have effect (World -- World).

    >

    > main == "Hello, world!" // World [Char List]

    >      swap           // [Char List] World

    >      putStr // [Char List] World -- World

    > ;

     I don't get it. What is being swapped in line 2?

     > pllea> c) programs (if any) which would be OK in Joy but not in your

    > pllea>    typed version.

    >

    > factorial == 0 swap produce_ni mul_ni ;

    > mul_ni == [swap dup 0 =] [drop] [* mul_ni] ifte ;

    > produce_ni == [dup 0 =] [drop] [dup 1 -] ifte ;

    >

    > First we mark top of stack using zero then produce a variable list of

    > n[i] until 1 in stack then consume them using *.

    >

    > Second and third quotations in produce_ni has different stack effect.

    > Second has (a -- ) and third has (Int -- Int Int). Of course, they

    > doesn't match.

    >

    > Definition mul_ni has problems too. First quotation tells us that we

    > have on input two values of unknown type a and of type Int. Second

    > quotation has no problems, it just discards Int (zero) argument. Third

    > quotation tells us that type a is actually Int and that we should have

    > at least one more Int on input.

    >

    > Right now I cannot show how mul_ni will produce type clash. But

    > produce_ni certainly will.

     I find the example very difficult. Could you specify some simpler ones,

    please ?

     > pllea> As to c), you will, I take it, allow lists of lists. But will you

    > pllea> allow heterogenous lists, consisting, say, of a name (a string or

    > pllea> a list of chars) and a phone number?

    >

    > pllea>    [ [ "Mary"  19827364 ]

    > pllea>      [ "Jane"  83472364 ] ]

    >

    > For me it is better to put them into constructor.

    > data NamePhone == [Char List] Int NamePhone ;

     I'm beginning to see, but what does that list of phone numbers look like

    in your notation?

    Best wishes to all

    Manfred von Thun

    Philosophy Department, La Trobe University

     http://www.latrobe.edu.au/www/philosophy/phimvt/s00bok.html

      ( SYMBOLIC PROCESSING IN PASCAL - many programs at different levels )

     http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html

      ( JOY - a programming language based on function composition )

     >

    >

    >

    >

## phimvt@lurac.latrobe.edu.au — 2000-12-22 04:17:18

    I'll reply to the questions by Dirk-Ulrich

    Manfred von Thun

    Philosophy Department, La Trobe University

     http://www.latrobe.edu.au/www/philosophy/phimvt/s00bok.html

      ( SYMBOLIC PROCESSING IN PASCAL - many programs at different levels )

     http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html

      ( JOY - a programming language based on function composition )

     On Thu, 21 Dec 2000, Dirk-Ulrich Heise wrote:

    > -----Ursprungliche Nachricht-----

    > Von: "sz" <sz@...>

    > > If we do not use reference copying (where copy operation copies only

    > > reference) then every object could be either in heap or referenced

    > > only once (although indirectly through container as in List type).

    > > Object deconstruction (such as pattern matching) destroys object and

    > > puts it into heap while revealing it's internals. This puts us into

    > > manual heap management but when compiler/interpreter can tells us

    > > where something is going wrong. Also there is no need for any garbage

    > > collection.

    >

    > Hello!

      [snip]

    > have an idea of its object semantics. When does it finalize

    > objects? I think it would be a very bad idea to leave management

    > to the user, like, having to call an explicit fclose instead of leaving

    > it to some automatic destruction.

    Joy is like Lisp/Scheme in many ways: it is purely functional,

    and there is no assignment. Every program denotes a function

    from stacks to stacks. In the default mode, when a program

    has executed, the top of the stack is written to the terminal.

    (There may be other items left on the stack, and they can be

    written out by the empty program. Example

        123  2 3 +  .     .

                          ^  write the 123

                       ^  empty program

                    ^  write the 5

                 ^  two items on the stack

               ^ three items on the stack

             ^ two items on the stack

          ^ one item on the stack

    but there are other ways, too, using "put".)

    > Could someone give me a pointer to info about Joy's object

    > semantics?

    Easy: there are no objects. Like Lisp/Scheme, Joy evaluates

    expressions.

    > BTW, now i was talking about objects.. You might say that Joy

    > isn't planned to be OO for the time being, but it suffices completely

    > to talk about built-in objects like floats, strings or lists of chars to

    > get to the question "When is the object storage freed / the object

    > finalized" or "what happens during a dup - copying a reference or

    > copying the content?" Even if you say "dup copys a function because

    > everything in Joy is a function", i would say: Don't pretend the

    > problem isn't there! Or did i miss something important?

    As in Lisp/Scheme, the user does not have to worry about

    storage management. There is an inbuilt ("very simple", as they say)

    stop/copy garbage collector (not a mark/sweep), but again the

    user does not know that. The dup operator copies the top

    element of the stack (which is a list, too). How it does that

    is invisible to the user, of course. In my prototype dup of a list

    conses a second reference to the stack, and dup of anything else

    (bool,char,int,set - which fit into a word) conses a proper

    copy. There would have been other ways of doing that, I suppose.

    So dup does not really copy a function (which is an abstract entity)

    but a program to compute a function. Remember, each of the

    following is indeed a program (which pushes something on the stack)

       true   'A   123   {2 7 31}   [1 2 3 "hello"]

    I hope this helps.

    Mit freundlichem Gruss (frueher mal aus Hamburg),

        Manfred

## Dirk-Ulrich Heise — 2000-12-22 08:53:20

    > I'll reply to the questions by Dirk-Ulrich

    >

    > Manfred von Thun

    > Philosophy Department, La Trobe University

     [...]

     > is invisible to the user, of course. In my prototype dup of a list

    > conses a second reference to the stack, and dup of anything else

    > (bool,char,int,set - which fit into a word) conses a proper

    > copy. There would have been other ways of doing that, I suppose.

     That is in effect identical to Python semantics (or the

    semantics of my Python-based Forth); Python always

    works with references, and an assignment re-binds

    a name to the given reference. Small objects like

    ints are "immutable objects", so they cannot change

    state - so the reference semantics become sort of

    equivalent to value assignments to the user.

    I don't want to bother further with questions about

    finalization issues, i think i can't offer a proper solution

    either, not knowing how to do that in a purely functional

    style. At least i think i've got my implementation of Forth

    right, seeing that you do it very similarly.

    I hope that i will be able to implement some

    Joy combinators etc. in my Forth soon, that's why i was

    asking. I think it'll be possible. Garbage collection might

    be another thing i will have to implement, though.

    Froehliche Weihnachten aus Braunschweig!

    (-5 degree centigrade)

    Dipl.Inform. Dirk-Ulrich Heise

    business: hei@...

    private: dheise@...