r_v_dalen — 2006-09-09 11:30:28

I'm wondering how many concatenative languages are lazily evaluated.

I'm aware that Joy can be lazily evaluated, although I believe that the C implementation is
strict?

Side effects rule out lazy evaluation. That's why I believe Factor is probably strict too
(although some parts of Factor could be lazy). I'm not sure about K, J and APL.

But I do know that a lot of data structures aren't strict in APL. It looks like mixing strict and
lazy evaluation is the most practical approach.

My question: how does one decide when to evaluate and when not to evaluate? What kind of
heuristics can be applied? (memory vs time?)

Hopefully, the members of concatenative can provide me some of the answers.

Thanks,

Robbert.

Chris Double — 2006-09-09 11:57:17

On 9/9/06, r_v_dalen <r_v_dalen@...> wrote:

>
> Side effects rule out lazy evaluation. That's why I believe Factor is
> probably strict too (although some parts of Factor could be lazy).

There is a lazy-lists library in Factor and the parser combinators
code relies on it a lot. A parser combinator returns a 'lazy list of
successes' as the result of a parse.

I believe there is also lazy evaluation code available for Joy and the
following paper as well:

http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-reprod.html

Chris.
--
http://www.bluishcoder.co.nz

stevan apter — 2006-09-09 13:24:26

APL, J, and K are strict. i'm not sure what you mean by
saying that some data structures in APL are lazy.

SLACK is a lazy implementation of K, based on SASL. in
SLACK, an expression involving an infinite list like

head tail one where one is 1:two where two is 2:one

compiles to a functional expression

+------@-------+
| |
+--@---+ +-----@------+
| | | |
+-@-+ tail Y +-----@------+
| | | |
B head +--@---+ +-@-+
| | | |
B +-@-+ cons n:2
| |
cons n:1in which the Y combinator is used to compute mutual recursion
between the lists 'one' and 'two'.

computations "go strict" when an operator like + is reduced.
+ causes its operands to be evaluated in full. so e.g.

one + two where one is 1:two where two is 2:one

will blow memory.

----- Original Message -----
From: "r_v_dalen" <r_v_dalen@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, September 09, 2006 7:30 AM
Subject: [stack] Lazy evaluation

> I'm wondering how many concatenative languages are lazily evaluated.
>
> I'm aware that Joy can be lazily evaluated, although I believe that the C implementation is
> strict?
>
> Side effects rule out lazy evaluation. That's why I believe Factor is probably strict too
> (although some parts of Factor could be lazy). I'm not sure about K, J and APL.
>
> But I do know that a lot of data structures aren't strict in APL. It looks like mixing strict and
> lazy evaluation is the most practical approach.
>
> My question: how does one decide when to evaluate and when not to evaluate? What kind of
> heuristics can be applied? (memory vs time?)
>
> Hopefully, the members of concatenative can provide me some of the answers.
>
> Thanks,
>
> Robbert.
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
>

Robbert van Dalen — 2006-09-09 15:15:42

> APL, J, and K are strict. i'm not sure what you
> mean by
> saying that some data structures in APL are lazy.

Just copied this from wikipedia:

"A widely cited paper "The APL Machine" perpetuated
the myth that APL made pervasive use of lazy
evaluation where calculations would not actually be
performed until the results were needed and then only
those calculations strictly required. Although this
technique was used by just a few implementations, it
embodies the language's best survival mechanism: not
specifying the order of scalar operations. Even as
eventually standardized by X3J10, APL is so highly
data-parallel, it gives language implementers immense
freedom to schedule operations as efficiently as
possible."

> SLACK is a lazy implementation of K, based on SASL.

I really like SLACK as a name and as a language. Don't
know enough K to really understand the implementation
though. I still have to learn a great deal of K and J
terminology (nouns, verbs, abverbs) and concepts
(shape, rank, valence) to really appreciate all the
interesting stuff that's sitting on your www.nsl.nl

> compiles to a functional expression
>
> +------@-------+
> | |
> +--@---+ +-----@------+
> | | | |
> +-@-+ tail Y +-----@------+
> | | | |
> B head +--@---+ +-@-+
> | | | |
> B +-@-+ cons n:2
> | |
> cons n:1in which the Y

That really looked like line noise in propertional
font ;)
To bad you cannot force mono-spaced fonts in the yahoo
mail reader.

> computations "go strict" when an operator like + is
> reduced.
> + causes its operands to be evaluated in full. so
> e.g.
>
> one + two where one is 1:two where two is 2:one
>
> will blow memory.

Similarly, folding an infinite list would also blow
memory.

I suspect you can always make lazy evaluation strict
and build lazy structures (Factor's lazy list) with
stict evaluation.

But that's probably not saying much.

Robbert.

> ----- Original Message -----
> From: "r_v_dalen" <r_v_dalen@...>
> To: <concatenative@yahoogroups.com>
> Sent: Saturday, September 09, 2006 7:30 AM
> Subject: [stack] Lazy evaluation
>
>
> > I'm wondering how many concatenative languages are
> lazily evaluated.
> >
> > I'm aware that Joy can be lazily evaluated,
> although I believe that the C implementation is
> > strict?
> >
> > Side effects rule out lazy evaluation. That's why
> I believe Factor is probably strict too
> > (although some parts of Factor could be lazy). I'm
> not sure about K, J and APL.
> >
> > But I do know that a lot of data structures aren't
> strict in APL. It looks like mixing strict and
> > lazy evaluation is the most practical approach.
> >
> > My question: how does one decide when to evaluate
> and when not to evaluate? What kind of
> > heuristics can be applied? (memory vs time?)
> >
> > Hopefully, the members of concatenative can
> provide me some of the answers.
> >
> > Thanks,
> >
> > Robbert.
> >
> >
> >
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
> >
>

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

William Tanksley, Jr — 2006-09-09 22:13:31

r_v_dalen <r_v_dalen@...> wrote:

> I'm wondering how many concatenative languages are lazily evaluated.

Lazy data structures (that is, data structures that contain code that
generate later values) are easy in any language. Actual lazy
evaluation is /impossible/ in a concatenative language -- lazy
evaluation means that parameters to functions aren't evaluated until
and unless they're actually used. This is impossible because
concatenative semantics doesn't have function parameters.

> Robbert.

-Billy

Christopher Diggins — 2006-09-09 22:36:37

However every term in a concatenative language can be viewed as a
function which takes a single function (a stack) and outputs a single
value (another stack).

For an example of lazy evaluation, consider the following
concatenative program:

define f { [] [1 concat] [true] while pop }

In english: while true concatenate 1 to the list on the top of the
stack. When done pop the value.

If the language semantics do not enforce this as an infinite loop,
then it would make sense to say that the language supports lazy
evaluation.

- Christopher Diggins

On 9/9/06, William Tanksley, Jr <wtanksleyjr@...> wrote:
>
> r_v_dalen <r_v_dalen@...> wrote:
> > I'm wondering how many concatenative languages are lazily evaluated.
>
>
> Lazy data structures (that is, data structures that contain code that
> generate later values) are easy in any language. Actual lazy
> evaluation is /impossible/ in a concatenative language -- lazy
> evaluation means that parameters to functions aren't evaluated until
> and unless they're actually used. This is impossible because
> concatenative semantics doesn't have function parameters.

William Tanksley, Jr — 2006-09-09 23:14:31

Christopher Diggins <cdiggins@...> wrote:

> For an example of lazy evaluation, consider the following
> concatenative program:
> define f { [] [1 concat] [true] while pop }
> In english: while true concatenate 1 to the list on the top of the
> stack. When done pop the value.

> If the language semantics do not enforce this as an infinite loop,
> then it would make sense to say that the language supports lazy
> evaluation.

I can see that being acceptable, yes.

This is one of the things I've been trying to figure out to see if I
can think of a way to control the cartesian product in Enchilada -- if
you could specify that only some of the multiplications are relevant
to the rest of your program, and have only those ones actually get
carried out.

> - Christopher Diggins

-Billy

r_v_dalen — 2006-09-11 14:26:59

> > If the language semantics do not enforce this as an infinite loop,
> > then it would make sense to say that the language supports lazy
> > evaluation.
>
> I can see that being acceptable, yes.

Billy, I also agree with you and Christopher. I always think of lazy
evalutation to be some kind of stream. Every time you get an element
from a stream, that element is forced step to be evaluated.

> This is one of the things I've been trying to figure out to see if I
> can think of a way to control the cartesian product in Enchilada -- if
> you could specify that only some of the multiplications are relevant
> to the rest of your program, and have only those ones actually get
> carried out.

The cartesian product is not so problematic. Actually the zip and
desolve operator are to most interesting ones. For instance, the
cartesian product could also be written as:

[a, b, c] [x, y] * =:= [a, b, c, a, b, c] [x, x, x, y, y, y] % =>
[a x, b x, c x, a y, b y, c y]

And the result can be as lazy as myself. Just imagine the following
tree structure.

(% (<1,3>[a, b, c]) (<3,1>[x, y]) )

We can query the tree structure to return the expression sitting at
index 4:

4(%(<1,3>[a, b, c])(<3,1>[x, y])) =>
{%(4<1,3>[a, b, c])(4<3,1>[x, y])} =>
{%{[a]}{[y]}} =>
{a y}

Hopefully, the latter does make some sense. I've tried to visualize a
reduction tree (like the ones found in functional languages).

Robbert.