6
$\begingroup$

Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?

I see some problems that I will explain with few examples. I will use a prefix instead of a postfix notation, so evaluation takes place from left to right.

Duplicate an argument seems trivial:

drop A B  ->  B

However, we can not forget that A is unevaluated, so the previous example only work for literals or quotations, but not for unevaluated code:

drop 123 B      ->  B
drop "abc" B    ->  B
drop [+ 1 2] B  ->  B
drop + 1 2 B    ->  1 2 B  -- NON SENSE!

This can be solved in two ways. First, we can impose some structure (unflat) to the code based on the functions arity in the parsing stage:

drop + 1 2 B    ->  drop [+ 1 2] B  // at parse time
drop [+ 1 2] B  ->  B               // at run time

The problem with this approach is that we lose all the benefits of concatenative programming (for example, flatness and multiple return values). In fact, we are converting function composition to function application in prefix notation... In this case:

dup + dup 2 3

Naively translates to:

dup [+ [dup 2] 3]  ->  dup [+ 2 2 3]  // `+` arity mismatch. What to do with the extra value? Which one is it, 2 or 3?

But it result in an strict language is:

4 4 3

The second solution is to instruct the evaluator to reduce the stack just enough to get as many arguments as the current word needs:

drop + 1 2 B  ->  drop 3 B  ->  B

Looks good, but the target of lazy evaluation is to evaluate arguments only when needed. In this case we are evaluating + 1 2 needlessly. It is not a big problem until we found:

drop + bottom 2 B  ->  bottom

What contradicts the expected call-by-need semantics:

drop + bottom 2 B  ->  B
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I'm utterly confused: using prefix notation should result in evaluation from right to left rather than left to right (which is probably why postfix is more common in such languages). Also, a hypothetical lazy concatenative language would probably need a concept of "stack thunks" which represent the unevaluated stack. $\endgroup$
    – cody
    Nov 10, 2016 at 15:31
  • $\begingroup$ @cody Yes, in prefix notation, strict evaluation is from right to left, but not lazy evaluation, that is from left to right. One is the opposite of the other. $\endgroup$
    – user3368561
    Nov 10, 2016 at 15:36
  • 2
    $\begingroup$ I don't think that's true: the meaning of + 1 2 is, from right to left, "create the thunk that, when evaluated, returns a stack with 2 at the top", etc, until the +, which creates the thunk which when evaluated, evaluates the stack until it has 2 elements, then pops them and places the result of their sum on top. It's confusing, because these thunks are (possibly) finally evaluated at the end of the program, that is when reaching the far left. Then each thunk only does the minimum required work, which may require evaluating more thunks to the right of it, etc. $\endgroup$
    – cody
    Nov 10, 2016 at 15:42
  • $\begingroup$ @cody Why transverse the flat spine from right to left to build thunks at run time if it can be done at parse time? At run time you only need to evaluate the left-most thunk to unwind and evaluate the spine. This is what I mean with a left to right evaluation order. $\endgroup$
    – user3368561
    Nov 10, 2016 at 20:21
  • 1
    $\begingroup$ I think it can't be done at parse time, and this is the problem you're running into: in general you can't predict what's going to be left on the stack after evaluating a thunk, which is why you're having an "arity mismatch" in the naive translation of dup + dup 2 3. $\endgroup$
    – cody
    Nov 10, 2016 at 20:51

1 Answer 1

Reset to default
6
$\begingroup$

It can be done. Here's a presentation explaining the language and how the compiler works (so far).

You can play with an asm.js version at http://hackerfoo.com/eval.html

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.