Re: [stack] Re: Barebone implementation of concatenative language in c or c++

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

> John Nowak <[email protected]> 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