# Re: [stack] Digest Number 19

## Mark van Gulik — 2000-05-23 17:56:52

    > From: Mark van Gulik [mailto:ghoul6@...]

    >>From: wtanksley@...

    >

    >>on the stack as its result, I'm fairly confident we can express the

    >>program's evaluation strictly in terms of a finite list of

    >>rewriting rules.

    >

    > Again, I'm going to have to study your comments.  They seem fatally flawed

    > right now, but perhaps my own knowledge of the subject is blocking me from

    > seeing the truth in what you're saying.

    >

    >>On a mostly unrelated topic, I was considering how much

    >>expressive power was

    >>lost by Joy's lack of support for lexical closures.

    >

    > Snicker.  Lexical closures?  You mean, "total lack of variables"?  I'm

    > sorry, but there's ZERO possibility for lexical closures when there are zero

    > variables.

     Not true.  Normally a lexical closure is defined in terms of the variables

    that are in scope when an occurrence of a lambda is encountered.  We can

    trivially modify the concept for Joy by talking about the *values* that are

    available on the stack at the moment you wish a closure to be constructed.

     >>Sure,

    >>locally bound

    >>variables and arguments can be bisimulated by finite stack

    >>manipulations,

    >>but are lexically closed variables also possible (the question

    >>of software

    >>re-use being my motivating concern)?

    >

    > You're unmistakably trapped in the lambda-fallacy: thinking that everything

    > is a variant of the lambda calculus.  Not every good thing in computer

    > science comes from the lambda calculus.  Joy, for example, is COMPLETELY

    > unrelated to lambda; Forth is nearly so.

    >

    > Code reuse is FAR easier when you do _not_ have variables, lexically closed

    > or otherwise.

     Yes, reuse is easier without variables, assuming you can even tell what the

    heck the procedure is doing (and assuming that what you really wanted to

    reuse was a single procedure).  My *end* goal is better code reuse (for the

    purpose of this discussion), and my intermediate goal is to support simple

    features of other languages *without* changing Joy.  I'm interested in

    discovering usage patterns for supporting simple concepts like closures.

    BTW, I believe the operations of (typed) Joy can be expressed in terms of

    the lambda calculus (but I agree it's intrinsically unrelated).  But you've

    misunderstood my goal.  The closures I was talking about have nothing to do

    with lambdas (ironically).  They're just a way of bundling data and code

    together.

     >>A simple scheme (no pun intended) to support closures would be

    >>to simply

    >>implement a closed function as a pair of things -- the function and an

    >>aggregate of lexically closed variables.

    >

    > Think about this, though; you're binding variables to functions.  This

    > completely destroys the concept of "concatenative" and replaces it with

    > "applicative".  _Every_ other language in the world is applicative; it's not

    > a hard problem to solve anymore.  I'm interested in solving the problems of

    > concatenative languages, not in making yet another new applicative one, as

    > though THIS one would suddenly behave differently from all other other ones

    > before it.

     No, I don't want the closures to be named, and I also don't want them to be

    lambda-like (i.e., taking named arguments, etc).  I just want to be able to,

    say, partially evaluate the "power" operation with the constant exponent 2

    to produce a "squared" operation.  Hm, bad example.  How about use the

    "power" operation and a constant exponent that's at a known position on the

    stack to produce a new operation-data pair (a closure) that raises a passed

    number to that exponent.

     >>Every time a closure

    >>is needed,

    >>this pair of things would be used.  To invoke the closure,

    >>simply push the

    >>aggregate of closed variables onto the stack (as an aggregate)

    >>and invoke

    >>the function, which is written to expect this aggregate to be

    >>on the top.

    >

    > Forth's local variables work this way -- take a look at them.  Some people

    > use them; I personally see no use for them.

     Again, I'm not really interested in the variables.  I'm also not the least

    bit interested in Forth.  I wrote a Forth interpreter over the summer of

    1983 (it was for the Commodore-64, I was 16), and I have no intention of

    returning (either to that language, that platform, or that age!).

     >>Closure provides enough power to easily support polymorphism,

    >>which in turn

    >>is strong enough to  host object-oriented programming.  I'm

    >>*not* saying Joy

    >>is object-oriented, I'm just saying an object-oriented

    >>language can be built

    >>fairly easily and efficiently on top of it.

    >

    > You seem to believe that OO requires variables, which is simply wrong.

     No, variables + some other things are sufficient but not necessary for OO.

    You're definitely talking to the wrong guy about this -- see my language

    Avail for a discussion of the role of immutable data in OO:

        http://www.ericsworld.com/Mark/HTML/Avail.html

     > I'm

    > also highly confused by your association of polymorphism with closures; just

    > because the PROBLEM of polymorphism with closures has been solved doesn't

    > mean that closures SUPPORT polymorphism; in fact, polymorphism has to be

    > forced onto closures.

     A closure practically *is* run-time polymorphism.  If you pass me a closure

    and I invoke it, I've executed code in which *you* decided the

    implementation.  What could be clearer?  It's not objects, but it is

    polymorphism (from "multiple forms", in this case multiple possible

    implementations depending on what is actually passed).

     > And you then act as though OOP required a huge stack of things.  There are

    > many OOP packages in Forth which add nothing to the language, but provide

    > full polymorphism.

     Since OOP is a style of programming, at best "assisted" by a language (and

    at worst barely permitted), it's mostly independent of Joy.  I'm not

    proposing any changes to Joy, in case you've misinterpreted me, merely an

    idiomatic usage.

     > Now, I happen to like static typechecking with full polymorphism.  The right

    > way to do this isn't to borrow all of the problems of another language in

    > hopes of being allowed to use their solution; the right way is to develop a

    > way to statically typecheck a concatenative language.  It just so happens

    > that someone's finally worked that out.

    >

    > It turns out to be terrifically simple.  Every type is given an ID number,

    > and every "word" (that is, a function with a name) is given a type signature

    > denoting what its inputs and outputs are (for example, "+" might have one

    > variant which looks like "( int int -- int )", and "swap" would look like

    > "(single single -- 2nd 1st)").  User-defined words are required to begin

    > with a written typesignature.

     Well, I would have avoided those special "variables" (dirty word!) like

    "2nd" and "1st".  Instead, I would provide a type signature that was itself

    applicative.  The allowable operations used in a type signature would be

    typeSwap, typeDup, typePop, typeMatchAndPop, and {any type literal}.  Why

    have the power of an applicative language if you don't even bother building

    the type signature applicatively (just kidding, my syntax wouldn't be as

    clear IMO).  As an example, swap's signature would be ( typeswap ), and "+"

    would have the signature (int typeMatchAndPop int typeMatchAndPop int).

    Note that my system would not only be applicative, but inherently

    polymorphic as well.  You may want to consider allowing type invariants to

    be expressed in the *middle* of a procedure (for added clarity).  These

    simply describe the state of the stack (the type signature has the effect of

    matching and popping the relevant type entries, although this must be done

    on a duplicate of the type stack).

    The type theory isn't exactly the hardest thing in the world to grasp (it's

    the first thing I thought of when I started reading about Joy).

     > At compile-time, we have an extra stack, called the type-stack.  When we

     [snip]

     > So we take that extra step, and use ML-style type inferencing.  Now that

    > we've done this, we can also do things that most other languages can't, such

    > as overloading on the return values as well as the input values.

     Ada supports this.  So does my language Avail, to some degree (via multiple

    operations with the same name, not via polymorphic invocation).

     > (We can

    > even overload on the _number_ of return values, which is something that a

    > non-concatenative language simply can't do).

     More interesting would be overloading on the number of "arguments".  Then

    you could use a strengthened version of the procedure when the oldest

    argument types were known statically, and a weakened version when the oldest

    arguments were not known (i.e., within weakened generic data structures).

     > Taking a closer look at what we've built, we see that we're typechecking not

    > _variables_, but rather _dataflow_.  In other words, even our simplest

    > typecheck is doing a partial dataflow analysis, a problem which causes

    > compiler writers for applicative languages major headaches.  How far are we

    > from a complete dataflow analysis?

     This is kind of the whole reason I was looking at Joy in the first place

    (the simplicity of these kinds of analysis).

## srenner@mail.ru — 2000-05-23 18:11:22

    Mark van Gulik's post was a perfect example of what I was hoping for

    when I induced him to join the list.

    About implementations: I have one. In Oberon. With no scanner. It has

    integers and quotations and only does "dup", "plus", and "i".

    sr

## iepos@tunes.org — 2000-05-23 19:23:32

    > No, I don't want the closures to be named, and I also don't want them to be

    > lambda-like (i.e., taking named arguments, etc).  I just want to be able to,

    > say, partially evaluate the "power" operation with the constant exponent 2

    > to produce a "squared" operation.  Hm, bad example.  How about use the

    > "power" operation and a constant exponent that's at a known position on the

    > stack to produce a new operation-data pair (a closure) that raises a passed

    > number to that exponent.

     Ahhhh ... If that's what you're talking about, then I believe Joy already

    has a "closure" feature; they are called "quoted programs". And in

    particular, the "cons" primitive can be used to construct new programs

    at runtime with parameters hard-wired in. For instance, supposing

    you have a number like "2" or "3" on the stack and you want to accordingly

    generate a squaring or cubing program, then you just do

      [exp] cons

    where "exp" is a mythical raise-to-exponent program (not a primitive

    in Thun's Joy). Doing "[exp] cons" will leave you with a program on

    the stack, which you could execute dynamically using "i", or you

    could directly supply it as a branch to "ifte" or to a looping program

    such as "while", which take quoted programs off the stack ("ifte" and

    "while" usually, but not always, have statically known operands, that

    were just pushed on the stack as literals, using "[]"s).

    Unfortunately, in Joy, "cons" is not currently implemented by

    generating specialized native code at runtime; it would be cool

    if it was :-)

    Joy's ability to deal with programs on the stack at runtime is one

    of its most interesting features to me. By the way, along with "cons",

    there is a "concat" primitive, which takes two programs and merges

    them together into one program that does one and then the other.

    Actually, "concat" could be constructed from "cons" as:

      [[i] dip i] cons cons

    The "[i] dip" would run the first program and then the "i" would run

    the second ...

     > A closure practically *is* run-time polymorphism.  If you pass me a closure

    > and I invoke it, I've executed code in which *you* decided the

    > implementation.  What could be clearer?  It's not objects, but it is

    > polymorphism (from "multiple forms", in this case multiple possible

    > implementations depending on what is actually passed).

     This is an interesting point ... use of quoted programs dynamically

    would be a natural way to do object-oriented programming.

     > > variant which looks like "( int int -- int )", and "swap" would look like

    > > "(single single -- 2nd 1st)").  User-defined words are required to begin

    > > with a written typesignature.

    >

    > Well, I would have avoided those special "variables" (dirty word!) like

    > "2nd" and "1st".  Instead, I would provide a type signature that was itself

    > applicative.  The allowable operations used in a type signature would be

    > typeSwap, typeDup, typePop, typeMatchAndPop, and {any type literal}.  Why

    > have the power of an applicative language if you don't even bother building

    > the type signature applicatively (just kidding, my syntax wouldn't be as

    > clear IMO).

     You say you're kidding, but you bring up a good point. Using things

    like "typeSwap", "typeDup", "typePop", and "typeMatchAndPop" seems

    like a good idea, since it avoids the use of the variable-like primitives

    "2nd" and "1st". However, "swap", "dup", and "pop" by themselves is

    not complete; for, with just those, how could you construct a

    combinator that swaps, not the top two items of the stack, but the

    two items beneath the top one? (in other words, how could you write

    the type of "[swap] dip"?) ... If you add a typeDip and typeCons,

    then you'll have completeness, I believe.

    You'd also need a type "quotation" construct; for, although you

    can write the type of a binary arithmetic operator as

      int typeMatchAndPop int typeMatchAndPop int

    how could you write the type of a program that pushes such an operator

    onto the stack? With a quotation construct, you'd write it as just

      [int typeMatchAndPop int typeMatchAndPop int]

    It is interesting that in this style types are written in the exact

    same syntax as ordinary programs, using concatenation and quotation ...

    - Brent Kerby ("iepos")

## stevan apter — 2000-05-24 00:51:03

    ----- Original Message -----

    From: Mark van Gulik <ghoul6@...>

    To: <concatenative@egroups.com>

    Sent: Tuesday, May 23, 2000 1:56 PM

    Subject: Re: [stack] Digest Number 19

    >

    > No, I don't want the closures to be named, and I also don't want them to be

    > lambda-like (i.e., taking named arguments, etc).  I just want to be able to,

    > say, partially evaluate the "power" operation with the constant exponent 2

    > to produce a "squared" operation.  Hm, bad example.  How about use the

    > "power" operation and a constant exponent that's at a known position on the

    > stack to produce a new operation-data pair (a closure) that raises a passed

    > number to that exponent.

    >

        joy>[2 +] "plus2" is pop

        joy>10 plus2

        12

## wtanksley@bigfoot.com — 2000-05-25 19:21:41

    From: iepos@... [mailto:iepos@...]

     >Unfortunately, in Joy, "cons" is not currently implemented by

    >generating specialized native code at runtime; it would be cool

    >if it was :-)

     In the language I'm designing, the "program building functions" operate on

    arrays, not lists.  However, the principle's the same -- and any way you put

    it, you can't generate _only_ native code, you have to generate something

    that the language's primitives can dissect.

    However, it's _very_ easy to include a function which takes as input a

    quotation and produces as output a "function pointer" -- in other words, it

    emits optimised native code.  Such a function is also very easy to use, so

    much so that there's no reason at all to have "cons" run it automatically.

     >- Brent Kerby ("iepos")

     -Billy