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]
In http://groups.yahoo.com/group/concatenative/message/740 , Louis
Madon presents these examples
> nats n = n : nats (n + 1)and goes on to ask
> evens = map (2 *) (nats 1)
> As far as your non-strictness proposal for Joy is concerned,Although I didn't make it very clear, the thrust of my original
> I'm not sure I really understood it. Could you show me how
> you might define 'nats' and 'evens' using it?
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.
On Wed, 1 Aug 2001, Louis Madon wrote:
> Actually what you wrote made me realize something about what Manfredwrote 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:
>Yes, I know about infinite lists in Haskell, but I do not know
> nats n = n : nats (n + 1)
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-terminatingfunctions. 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
From: "Manfred von Thun" <phimvt@...>
> ....Um yes, I see the distinction, I was using "non-strict" and "lazy
> 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.
> ....
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.