# RE: [stack] Re: Nonstrict Language in Terms of Strict Language

## Louis Madon — 2001-08-01 01:24:24

    Actually what you wrote made me realize something about what Manfred wrote in his previous post. I do not think it is correct to say that "[non-strictness] only makes sense in languages in which there is (explicit or hidden, implicit) lambda abstraction".  When a language supports non-strictness it opens up a whole style of programming based on infinite data structures, for example:

    nats n = n : nats (n + 1)

    this snippet of haskell represents a list of all natural numbers starting from n (ie. n ... infinite).  We could now type:

    take 10 (nats 1)        =>  1 2 3 4 5 6 7 8 9 10

    or building on this define all even natural numbers:

    evens = map (2 *) (nats 1)

    take 10 evens          => 2 4 6 8 10 12 14 16 18 20

    Now in a strict language, 'nats' and 'evens' are non-terminating functions.  This is indeed the case for Joy, so I must conclude that Joy is strict.

    As far as your non-strictness proposal for Joy is concerned, I'm not sure I really understood it - could you show me how you might define 'nats' and 'evens' using it?

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

    From:	Jack Waugh [SMTP:waugh@...]

    Sent:	Tuesday, July 31, 2001 10:22 PM

    To:	concatenative@yahoogroups.com

    Subject:	[stack] Re: Nonstrict Language in Terms of Strict Language

    We could represent a nonstrict value as a quoted passage of code

    guaranteed to evaluate to the desired value.  A value has been

    evaluated when and only when its size is 1.  Under that convention,

    any attempt to represent an unevaluated value as a one-word program

    would have to submit to having a no-op appended to the program so it

    would no longer have a size of one.

    Constants, such as for example 2, map straightforwardly to singleton

    lists of themselves (e. g., [2]).

    Now what do we do with an operation such as dup?  I think that in

    general we could write a combiniator that given a regular Joy

    function and given the number of arguments it consumes from the stack

    and the number of results it should leave (assuming both these counts

    remain constant regardless of the arguments), would convert that

    function to its lazy equivalent.  But rather than try to formulate

    that combinator right away, I will try for just the translation of

    dup.

    Lazy dup should probably begin by testing whether the argument is

    evaluated, and act differently accordingly.  If the argument is

    evaluated, lazy dup can just duplicate it.  But if the argument is

    unevaluated, and if we assume that the stack elements in the

    interpreter are going to map one-to-one to the stack elements in the

    interpreted lazy Joy, lazy dup should still leave two elements on the

    stack.  For efficiency, they should function as two references to the

    same node, so that if the environment demands the evaluation of both

    results of dup, the evaluation won't have to be repeated.  This means

    that to have efficient lazy evaluation, we need a system of

    reference.  We could implement one by keeping on top of the stack an

    interpreter state that will map from references to the mutable things

    referred to.  Then the stack that models the stack of the lazy

    langauge would have to begin just below the interpreter state.

    Introducing this made things more complex.  We can't translate 2 into

    just [2]; we have to translate 2 into [[2]] dip.  So what's lazy

    dup?  I suppose I could write it, but I just got too lazy.

    But if we're going to implement a system of reference, we have to

    write a garbage collector for it, no?  Something smells wrong here;

    I'm sure that when they do this in applicative languages, they don't

    have to rewrite the collector in the strict language.  They use a

    monad somehow.

    To unsubscribe from this group, send an email to:

    concatenative-unsubscribe@egroups.com

    Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    [Non-text portions of this message have been removed]

## Jack Waugh — 2001-08-01 14:03:41

    In http://groups.yahoo.com/group/concatenative/message/740 , Louis

    Madon presents these examples

     > nats n = n : nats (n + 1)

    > evens = map (2 *) (nats 1)

     and goes on to ask

     > As far as your non-strictness proposal for Joy is concerned,

    > I'm not sure I really understood it.  Could you show me how

    > you might define 'nats' and 'evens' using it?

     Although I didn't make it very clear, the thrust of my original

    question was:

    1.  It is possible to define a lazy Joy-like language.  On the

    surface it would look much like Joy, but we could give it lazy

    (nonstrict) semantics.  This would support the sort of examples that

    Mr. Madon gives above.

    2.  It is possible to convert programs in the language of #1 above

    into programs in Joy.  We know this because Joy is Turing-complete.

    3.  Is Joy a suitable language into which to translate for the

    exercise of #2 above?  Can the conversion be done in an elegant way?

    I thought that if I could trick another reader into answering 3,

    she'd outline 2, and I would then learn something that otherwise I

    shall have to go find one of Wadler's books or some other off-Web

    literature to learn.  So laziness motivated me.

    Your question, Mr. Madon, I could interpret to refer to only #1

    above, or to extend into #2 (what would be the translation into Joy

    of the subject programs).  I'll follow a policy of lazy evaluation

    and just answer the first part, and if you want the answer to the

    rest, you can call for the next element of my answer (which may be

    bottom because I'm not sure of a reasonable way to do #2 (I don't

    consider reimplementing the garbage collector to be reasonable)).

     > nats n = n : nats (n + 1)

     I'll partially propose a langauge, to be called Lazy Joy, in which we

    could write the equivalent of the above as

    nats ==

        dup               (the stack is now n n)

        1 +

        nats

        cons

    .

    I wrote a recursive definition.  I'm sure Dr. von Thun could very

    quickly rewrite it without recursion using one or more combinators,

    equivalent in power to the famous Y combinator.  I would propose that

    the same rewrite as would be suggested by the laws of Joy should

    apply equally to Lazy Joy.

     > evens = map (2 *) (nats 1)

     evens == 1 nats [dup +] map .

    Joy's map takes arguments in the reverse order to Haskell's.  cons

    has the same order of arguments in both languages.

    An interesting way to compare languages is to ask what constants mean

    in them.  In C, 2 is a computer word ending in 0010.  In Smalltalk, 2

    is a reference to an "object" (if we want, we can view it as a

    function from a memory state and a message into another memory state

    and a result).  In Hope, 2 is an infinite sequence, 2, 2, 2,

    2, . . . .  In Joy, 2 is a function that pushes 2 (the same function)

    onto the stack.  In Lazy Joy, 2 can answer as to whether it is

    evaluated that yes it is, and can answer as to its value, Joy's 2.

    If a translation from Lazy Joy to Joy is going to work, 1 nats is

    going to have to result in something like a cons node whose car

    evaluates to 1 and whose cdr denotes that it is not evaluated yet,

    but that if someone insists on the value, it will come from an

    equivalent to the Lazy Joy program "2 nats".  A naive translation

    might look like (in Joy) [1] 2 1 0 [nats] translate i cons , where

    translate takes three arguments, those being the number of inputs to

    a Lazy Joy function, the number of results, and the Lazy Joy program

    quoted, and produces the translation of that Lazy Joy program into

    Joy (as a new quoted program).  The trouble (at least one trouble)

    with this naive concept of the translation, is that there doesn't

    seem to be an efficient way to implement 1 2 [dup] translate.

## Manfred von Thun — 2001-08-03 07:21:11

    On Wed, 1 Aug 2001, Louis Madon wrote:

     > Actually what you wrote made me realize something about what Manfred

      wrote in his previous post. I do not think it is correct to say that

     "[non-strictness] only makes sense in languages in which there is

     (explicit or hidden, implicit) lambda abstraction".  When a language

     supports non-strictness it opens up a whole style of programming based

     on infinite data structures, for example:

     >

    > nats n = n : nats (n + 1)

     Yes, I know about infinite lists in Haskell, but I do not know

    how to handle them in Joy. Some time ago I spent time thinking

    about it, but I did not get very far - so it all got buried on

    the stack of "things to do in the future".

    Consider the equivalent definitions

    (in a fantasy applicative language):

             square(x)  ==  x * x

             square  ==  lambda x : x * x

    and now the call

    	 square(2 + 3)

    which in normal order evaluation becomes

    	 (2 + 3)  *  (2 + 3)

    with the additions having to be done twice.

    In applicative order the actual parameter (2 +3) would be

    evaluated first, and the result, 5 substituted for x only once:

    	5  *  5

    Normal order is non-strict, it has the potential advantage

    that a function may be defined even in some cases where not

    all the evaluations of actual parameters terminate -

    that is in those cases where they are not needed.

    Applicative order is more efficient.

    You get the best of two worlds with "lazy evaluation",

    which evaluates the actual parameter once it is ever needed,

    and then all other occurrences of the parameter are

    automatically evaluated at no further cost.

    That was Turner's insight in using the SK-combinators

    (and some specialised variants) for a graph rewriting

    implementation of first KRC and then Miranda (and now Haskell).

    But, as far as I can see, it is all tied to the lambda calculus

    with lambda abstraction and application.

    This is not to deny that infinite lists would be a great idea

    in Joy, of course. I do hope somebody takes up the idea

    and finds a way of doing it,

      either in Joy as it is

      or in a mild modification of Joy in which some

        equivalent of graph rewriting (that means: internally

        an assignment) has to be implemented (in the C-source)

        Currently such internal assignment would go contrary

        to much of Joy.

     > Now in a strict language, 'nats' and 'evens' are non-terminating

       functions.  This is indeed the case for Joy, so I must conclude

      that Joy is strict.

     > As far as your non-strictness proposal for Joy is concerned,

       I'm not sure I really understood it - could you show me how you might

      define 'nats' and 'evens' using it?

    I do not even know of a way to write 'nats' and 'evens' in Joy at all.

    I cannot really contribute much to this discussion,

    but I would strongly encourage anyone who attempts it.

    I do envy some of Haskell's algorithms for their simplicity.

    One that I remember is for finding e.g. the 42nd prime:

    In a conventional languae one would use two counters,

    n for the number being tested, p for the number of primes so far.

    Increment n, if it is prime increment p. Stop when p = 42,

    the value required is n.

    But how inelegant - two extra variables n and p that have

    nothing to do with the problem !

    In Haskell you do:

    Take the list of all natural numbers, filter out the primes,

    extract the 42nd member of that list.

    (I do not know the exact Haskell notation for that)

    With some modification/extension to Joy it should look like

        [1..]  [isprime]  filter  42 at

    So, to summarise my views:

      1. strict/non-strict only applies to applicative languages

         but not to Joy

      2. infinite lists and operations/combinators for them

         would be marvellous in Joy.

    Comments/refutations/endorsements  most welcome

      - Manfred

## Louis Madon — 2001-08-05 13:41:15

    From: "Manfred von Thun" <phimvt@...>

     > ....

    > Normal order is non-strict, it has the potential advantage

    > that a function may be defined even in some cases where not

    > all the evaluations of actual parameters terminate -

    > that is in those cases where they are not needed.

    > Applicative order is more efficient.

    > You get the best of two worlds with "lazy evaluation",

    > which evaluates the actual parameter once it is ever needed,

    > and then all other occurrences of the parameter are

    > automatically evaluated at no further cost.

    > ....

     Um yes, I see the distinction, I was using "non-strict" and "lazy

    evaluation" as if they were equivalent. But I'm still not sure why these

    terms should be inorexibly tied with lambda abstraction. Sure Joy doesn't

    have formal parameters, but it does have functions and those functions do

    require arguments (ie. the stack locations being consumed by the function).

    It seems reasonable to me to be able to ask when do those arguments actually

    get reduced to value form since there is more than one way a Joy

    implementation could do it.

      However, in thinking about it some more, strictness also carries the

    connotation that the argument(s) will be evaluated _at the time the function

    is applied_, whereas in current Joy, argument evaluation and function

    invocation are decoupled - though you are required to have _all_ arguments

    ready before calling the function.  Therefore there are similarities with

    applicative order (it certainly isn't like normal order).

    Louis.