Don Groves <dgroves <at> ccwebster.net> wrote:
>>>> "William Tanksley, Jr" <wtanksleyjr <at> > wrote:
>>>>> Laziness is one of the things that can't easily be imported to a
>>>>> concatenative language.
> It seems to me that laziness can be implemented simply by
> encapsulating all data in functions. If a particular function
> is not called, that data is not evaluated. What am I missing?

Data isn't supposed to be evaluated, of course; I think you meant
encapsulating all functions in data rather than the other way around.
And indeed, that does allow you to control when your parameters are
evaluated (thus making them lazy); but it also makes tracking
parameters part of writing and reading your program -- and a lot of
that winds up being done at runtime.

I guess my basic point is that there's a type of laziness, let's call
it automatic laziness, that just can't be done in a concatenative
language. Syntax sugar won't save you from that problem, I think,
since there's too many operations that need to be done.

This doesn't mean I don't like concatenative languages; I just think
there's some research to be done in this area.

You know, it occurs to me that one place to look for a starting point
in that research might be colorforth. Take a look:
http://rainbowforth.sourceforge.net/blocks.html (see block 36,
'factorial', for a programlike block, most of the earlier stuff is the
source code for the language, including a lot of machine code).
Colorforth allows you to write code that's simply neutrally stored, or
markers that help you access that stored code, or immediately executed
code, or code that generates results that go into a definition...
There's a lot of different things to do. The different operations are
distinguished by color codes.

> don

-Wm

On 16 Jul 2010, at 10:21, William Tanksley, Jr wrote:

> Don Groves <dgroves <at> ccwebster.net> wrote:
>>>>> "William Tanksley, Jr" <wtanksleyjr <at> > wrote:
>>>>>> Laziness is one of the things that can't easily be imported to a
>>>>>> concatenative language.
>> It seems to me that laziness can be implemented simply by
>> encapsulating all data in functions. If a particular function
>> is not called, that data is not evaluated. What am I missing?
>
> Data isn't supposed to be evaluated, of course; I think you meant
> encapsulating all functions in data rather than the other way around.

OK, guess I may need some hand-holding here:

Isn't call-by-reference essentially equivalent to lazy evaluation?
If the called function doesn't need a certain parameter during a
particular call, that parameter will not be evaluated. So, parameters
(data) are only evaluated when needed, i.e., they are lazy.

In a call-by-value environment, It seems to me that incapsulating
all data in functions yields the same effect as call-by-reference. If
a parameter is not needed, its evaluating function will not be called.

If I'm on the wrong track with this, please enlighten me!

don

> And indeed, that does allow you to control when your parameters are
> evaluated (thus making them lazy); but it also makes tracking
> parameters part of writing and reading your program -- and a lot of
> that winds up being done at runtime.
>
> I guess my basic point is that there's a type of laziness, let's call
> it automatic laziness, that just can't be done in a concatenative
> language. Syntax sugar won't save you from that problem, I think,
> since there's too many operations that need to be done.
>
> This doesn't mean I don't like concatenative languages; I just think
> there's some research to be done in this area.
>
> You know, it occurs to me that one place to look for a starting point
> in that research might be colorforth. Take a look:
> http://rainbowforth.sourceforge.net/blocks.html (see block 36,
> 'factorial', for a programlike block, most of the earlier stuff is the
> source code for the language, including a lot of machine code).
> Colorforth allows you to write code that's simply neutrally stored, or
> markers that help you access that stored code, or immediately executed
> code, or code that generates results that go into a definition...
> There's a lot of different things to do. The different operations are
> distinguished by color codes.
>
>> don
>
> -Wm
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>

On 2010.07.20, at 11:18 PM, Don Groves wrote:

> Isn't call-by-reference essentially equivalent to lazy evaluation?

Nope. Call-by-reference is an abomination that shouldn't exist. Lazy evaluation is unrelated.

A quick run through here should help:
http://en.wikipedia.org/wiki/Evaluation_strategy

Caveat: It is possible to have an eager yet non-strict language. Wikipedia conflates eagerness and strictness which is unfortunate, although most existing eager languages are indeed strict. The Id programming language is an example of an eager, non-strict language.

Wikipedia is bad at precision.

> In a call-by-value environment, It seems to me that incapsulating
> all data in functions yields the same effect as call-by-reference.

If you replace "call-by-reference" with "lazy evaluation" (or similar), then you're essentially right if your language has lambda abstractions under which evaluation does not occur until they're applied. Lazy evaluation will share the result of evaluating the parameter though if it is needed in multiple places. You have to manually memoize the function passed in to emulate this in an eager setting.

Concatenative languages do not have lambda abstractions, but you can achieve a similar result by placing a function on the stack and lifting values into it (e.g. via Factor's misnamed 'curry' function; it really should be called 'partial-apply' or similar, although that's not exactly right either).

- jn

Don Groves <dgroves <at> ccwebster.net> wrote:
> William Tanksley, Jr wrote:
>> Don Groves <dgroves <at> ccwebster.net> wrote:
>>>>>> "William Tanksley, Jr" <wtanksleyjr <at> > wrote:
>>>>>>> Laziness is one of the things that can't easily be imported to a
>>>>>>> concatenative language.
>>>  It seems to me that laziness can be implemented simply by
>>> encapsulating all data in functions. If a particular function
>>> is not called, that data is not evaluated. What am I missing?

>> Data isn't supposed to be evaluated, of course; I think you meant
>> encapsulating all functions in data rather than the other way around.

> OK, guess I may need some hand-holding here:

No... It's just unclear presuppositions. Thanks for making them clear
by asking about them.

> Isn't call-by-reference essentially equivalent to lazy evaluation?

No; C++ allows call by reference semantics (explicitly specified, of
course) without being lazy at all. An early Fortran had implicit call
by reference, again not lazy (but, I'm told, very dangerous). I don't
use Perl, but I'm told it's call-by-reference.

Wikipedia just reminded me that you're thinking of "call by name" or
"call by need", but those are simply ways to achieve lazy evaluation.

> If the called function doesn't need a certain parameter during a
> particular call, that parameter will not be evaluated. So, parameters
> (data) are only evaluated when needed, i.e., they are lazy.

That IS what lazy evaluation is, yes.

> In a call-by-value environment, It seems to me that encapsulating
> all data in functions yields the same effect as call-by-reference. If
> a parameter is not needed, its evaluating function will not be called.

This gets confusing to me, so hold on tight...

In order to pass a function to a procedure, the function has to be
available as data. If it's not, you can't pass it.

Now, if your language is lazy (or non-strict) this doesn't matter; you
can avoid executing the function by never mentioning its parameter on
an execution path. This allows languages that don't provide
higher-order functions to still be very expressive.

> don

-Wm

John Nowak <john <at> johnnowak.com> wrote:
> Don Groves wrote:
>> Isn't call-by-reference essentially equivalent to lazy evaluation?
> Nope. Call-by-reference is an abomination that shouldn't exist. Lazy evaluation is unrelated.

Heh. John, is this because CBR hypothetically allows mutation of
arbitrary items? I'm not sure that it shouldn't exist, but it should
certainly be confined to explicitly declared OUT parameters.

> A quick run through here should help:
> http://en.wikipedia.org/wiki/Evaluation_strategy

Yes, that's what I used after I wrote my first draft to make it look
like I knew what I was talking about.

> Caveat: It is possible to have an eager yet non-strict language. Wikipedia conflates eagerness and strictness which is unfortunate, although most existing eager languages are indeed strict. The Id programming language is an example of an eager, non-strict language.

WP's explanation of non-strictness on that page is pathetic. BUT, I'm
puzzled... Their definition is clear, and it matches what the first
pageful Google results seem to be using, and their definition utterly
precludes yours... So I'm curious. How is Id both eager and
non-strict?

> Wikipedia is bad at precision.

If this is true, its accuracy is more to be bemoaned than its precision.

Usually its clarity is worse. Especially in highly technical matters.

> Concatenative languages do not have lambda abstractions, but you can achieve a similar result by placing a function on the stack and lifting values into it (e.g. via Factor's misnamed 'curry' function; it really should be called 'partial-apply' or similar, although that's not exactly right either).

In a more general sense, what you're describing is passing a function
_as_ data -- not data inside a function, but rather a function as
data.

> - jn

-Wm

William Tanksley, Jr scripsit:

> No; C++ allows call by reference semantics (explicitly specified, of
> course) without being lazy at all. An early Fortran had implicit call
> by reference, again not lazy (but, I'm told, very dangerous). I don't
> use Perl, but I'm told it's call-by-reference.

The default calling strategy for Fortran is and always has been call by
reference. The dangerous bit was an implementation, not a specification,
error. Buggy compilers conflated all instances of identical constants
(thus there would be only one cell containing 5 no matter how many literal
5s there were in the code) without realizing that literals passed as
arguments could not be conflated in such a manner.

Perl is technically call-by-reference, but it is usual to provide lexically
scoped variables that are mapped to the values of the call-by-reference
parameters, and to assign them first thing in each procedure. The main
exception is the comparison procedure passed to "sort", which uses
by-reference arguments directly (always named "$a" and "$b") for speed.

--
John Cowan cowan <at> ccil.org http://ccil.org/~cowan
Assent may be registered by a signature, a handshake, or a click of a computer
mouse transmitted across the invisible ether of the Internet. Formality
is not a requisite; any sign, symbol or action, or even willful inaction,
as long as it is unequivocally referable to the promise, may create a contract.
--Specht v. Netscape

On 2010.07.21, at 12:18 AM, William Tanksley, Jr wrote:

> In order to pass a function to a procedure, the function has to be
> available as data. If it's not, you can't pass it.
>
> Now, if your language is lazy (or non-strict) this doesn't matter; you
> can avoid executing the function by never mentioning its parameter on
> an execution path.

In an eager language without first-class functions, the language implementor can offer a special 'delay' form that creates a thunk at runtime. A 'force' function can later force the computation to occur. Since the only real semantic issue with introducing 'delay' is due to strictness (e.g. 'delay (4 / 0)' would not cause an error until forced even though '4 / 0' does immediately), it's a relatively uncomplicated addition from a theoretical perspective.

> This allows languages that don't provide higher-order functions to still be very expressive.

You'd still need some way to parameterize functions by other functions even if functions aren't available as data at runtime. OBJ is an excellent example of how to do parameterized programming without first-class functions.

- jn

On 20 Jul 2010, at 21:18, William Tanksley, Jr wrote:

> Don Groves <dgroves <at> ccwebster.net> wrote:
>> William Tanksley, Jr wrote:
>>> Don Groves <dgroves <at> ccwebster.net> wrote:
>>>>>>> "William Tanksley, Jr" <wtanksleyjr <at> > wrote:
>>>>>>>> Laziness is one of the things that can't easily be imported
>>>>>>>> to a
>>>>>>>> concatenative language.
>>>> It seems to me that laziness can be implemented simply by
>>>> encapsulating all data in functions. If a particular function
>>>> is not called, that data is not evaluated. What am I missing?
>
>>> Data isn't supposed to be evaluated, of course; I think you meant
>>> encapsulating all functions in data rather than the other way
>>> around.
>
>> OK, guess I may need some hand-holding here:
>
> No... It's just unclear presuppositions. Thanks for making them clear
> by asking about them.

You're welcome and this is getting vert interesting

First, I should explain my background. When I was at UCLA in
the early 60s, there was no such field as computer science.
The closest thing to it was a math class on numerical methods
taught by a physics professor.

I was working as a Fortran programmer though and that's how
I came to know this stuff. I learned assembly languages by always
printing what Fortran compilers called the "second file" which had
the assembly code interspersed in the Fortran code. Those were
the good old days for me...

>> Isn't call-by-reference essentially equivalent to lazy evaluation?
>
> No; C++ allows call by reference semantics (explicitly specified, of
> course) without being lazy at all. An early Fortran had implicit call
> by reference, again not lazy (but, I'm told, very dangerous). I don't
> use Perl, but I'm told it's call-by-reference.

The reason Fortran's call by reference was so dangerous was that
numerical constants were also passed by reference and hence their
value could be changed by the called subroutine. This was lazy all
right, a lazy implementation. Passing the address of a function which
would yield the constant would have been far safer but, in those days,
the programmer was expected to do most of the work. Programmer
time was dirt cheap by comparison to machine time on an IBM 7094
that cost $2 million 1960 dollars!

> Wikipedia just reminded me that you're thinking of "call by name" or
> "call by need", but those are simply ways to achieve lazy evaluation.
>
>> If the called function doesn't need a certain parameter during a
>> particular call, that parameter will not be evaluated. So, parameters
>> (data) are only evaluated when needed, i.e., they are lazy.
>
> That IS what lazy evaluation is, yes.

OK, at least I've got a handle on that concept.

>> In a call-by-value environment, It seems to me that encapsulating
>> all data in functions yields the same effect as call-by-reference. If
>> a parameter is not needed, its evaluating function will not be
>> called.
>
> This gets confusing to me, so hold on tight...
>
> In order to pass a function to a procedure, the function has to be
> available as data. If it's not, you can't pass it.

I don't understand this -- I do it all the time in my C code by using
the
address operator, &, and the same is easily done in Forth, et al.

It means, of course that the called function must be more intelligent
than is required in some languages. It must know the type values
of its parameters. As I've read on this list in the past, it seems there
has been a lot of research aimed at automating that very task.

As I said, a most interesting and enlightening discussion. Thanks
for taking part.

don

> Now, if your language is lazy (or non-strict) this doesn't matter; you
> can avoid executing the function by never mentioning its parameter on
> an execution path. This allows languages that don't provide
> higher-order functions to still be very expressive.
>
>> don
>
> -Wm
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>

On 2010.07.21, at 12:32 AM, William Tanksley, Jr wrote:

> John Nowak <john <at> johnnowak.com> wrote:
>
>> Nope. Call-by-reference is an abomination that shouldn't exist. Lazy evaluation is unrelated.
>
> Heh. John, is this because CBR hypothetically allows mutation of arbitrary items? I'm not sure that it shouldn't exist, but it should certainly be confined to explicitly declared OUT parameters.

I overstated my point. Call-by-reference is okay provided that it is not the default and that the language has sufficient support to keep things sane. Ada is a nice example of how to do it properly.

> WP's explanation of non-strictness on that page is pathetic. BUT, I'm puzzled... Their definition is clear, and it matches what the first pageful Google results seem to be using, and their definition utterly precludes yours... So I'm curious. How is Id both eager and non-strict?

A lazy language is prevented from evaluating more than is absolutely necessary. This is fatal to implicit parallelism; you can't kick off a parallel evaluation unless you're sure that the results of both evaluations are needed.

Id is an implicitly parallel language, and hence lazy evaluation was not an option. An eager, strict approach is possible, but it also limits parallelism to some degree. For example, if you have multiple evaluations running in parallel and you discover that one of them is not needed, you're not allowed to abort it. On the contrary, you need to continue running it simply to see if it evaluates to an error or not. In the worst case, one of these unneeded parallel evaluations goes into an infinite loop and the entire program cannot continue as a result.

A language that uses lenient evaluation is optimal for parallelism. It does this by both allowing speculative evaluation and by throwing out the requirement that strictness be respected. For example, the result of 'first (4/2, 4/0)' can be either '2' or an error in a lenient language. As such, it is an example of a non-deteriministic evaluation strategy (which is a downside).

Another nice advantage of lenient languages is that you can optimize without concern for ensuring termination. For example, the rewrite rule 'first (a, b) -> a' is a valid means of optimizing a lazy or lenient language (assuming they're pure), but not a valid means for optimizing an eager language (because the second element of the tuple may be _|_).

Here's a nice paper on lenient evaluation:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.9885

In addition, you may want to look at optimistic evaluation with is also non-strict and (primarily) eager. Like lenient evaluation, it allows speculative evaluation. Unlike lenient evaluation however, it is deterministic. If a speculative evaluation encounters an error, it avoids signaling it until it is determined that the result is needed. If an evaluation takes too long (meaning it may be looping) or is otherwise progressing in an undesirable fashion, it is aborted. For this reason, optimistic evaluation was seen as a way of getting better performance out of Haskell. While optimistic evaluation doesn't have the downside of non-determinstism, it brings with it additional overhead and runtime complexity compared to eager evaluation.

Ennals and SPJ on optimistic evaluation:
http://research.microsoft.com/en-us/um/people/simonpj/Papers/optimistic/index.htm

I think languages of the future may well embrace lenient evaluation, although I'm less sure about optimistic evaluation. By easing the requirements around strictness, additional optimizations are possible and parallelism is easier to attain. The overhead of lenient evaluation can be eliminated by only employing it in ways that do not require additional boxing of values. As such, lenient evaluation allows for strictly better performance (no pun intended) than eager evaluation.

>> Concatenative languages do not have lambda abstractions, but you can achieve a similar result by placing a function on the stack and lifting values into it (e.g. via Factor's misnamed 'curry' function; it really should be called 'partial-apply' or similar, although that's not exactly right either).
>
> In a more general sense, what you're describing is passing a function
> _as_ data -- not data inside a function, but rather a function as
> data.

Correct.

- jn

On 20 Jul 2010, at 21:33, John Cowan wrote:

> William Tanksley, Jr scripsit:
>
>> No; C++ allows call by reference semantics (explicitly specified, of
>> course) without being lazy at all. An early Fortran had implicit call
>> by reference, again not lazy (but, I'm told, very dangerous). I don't
>> use Perl, but I'm told it's call-by-reference.
>
> The default calling strategy for Fortran is and always has been call
> by
> reference. The dangerous bit was an implementation, not a
> specification,
> error. Buggy compilers conflated all instances of identical constants
> (thus there would be only one cell containing 5 no matter how many
> literal
> 5s there were in the code) without realizing that literals passed as
> arguments could not be conflated in such a manner.

And there was also the problem of the called routine's ability to
change the value of a constant so passed. There were some pretty
neat obfuscations around due to this feature though...

don

> Perl is technically call-by-reference, but it is usual to provide
> lexically
> scoped variables that are mapped to the values of the call-by-
> reference
> parameters, and to assign them first thing in each procedure. The
> main
> exception is the comparison procedure passed to "sort", which uses
> by-reference arguments directly (always named "$a" and "$b") for
> speed.
>
> --
> John Cowan cowan <at> ccil.org http://ccil.org/~cowan
> Assent may be registered by a signature, a handshake, or a click of
> a computer
> mouse transmitted across the invisible ether of the Internet.
> Formality
> is not a requisite; any sign, symbol or action, or even willful
> inaction,
> as long as it is unequivocally referable to the promise, may create
> a contract.
> --Specht v. Netscape
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>