Implementing fold in simple purely functional language without lazy evaluation

Question

I am trying to implement a simple functional language for automatic program synthesis. The data structure is a graph of functions and values, which compiles down to javascript. The following graph should be a fold function. funcApp nodes are connected to a function node and a number of value nodes, and it applies the function to the values. arg0 is the list, arg1 is an initial value (z) arg2 is the function to be applied.

enter image description here

It is equivalent to the folloiwng scheme definition (although my 'language' is not Scheme, it is the graph)

(define (foldr f z xs)
   (if (null? xs)
       z
       (f (car xs) (foldr f z (cdr xs)))))

The problem is that there are since there are no special operators, everything, in particular if is just a normal function. In this form, the program never terminates and instead reaches the maximum stack depth, since the else clause is always computed.

I presume this problem is solved in some languages by lazy evaluation. So my questions are: is there functional version of fold that will not have this infinite recursion 2) where to begin thinking about applying lazy evaluation to a simple language such as this, if necessary.

if is a special form in Scheme, so the else expression is not always evaluated. What's the question here? — Niklas B.
I know that is the case for Scheme, and I think I stated my questions quite explicitly in the last paragraph — zenna
I don't understand the first question. The answer to 2) would be "handle if specially". — Niklas B.
@zenna: First of all, non-strict is not the same as lazy. Second, Scheme solves this by just handling if differently than other function calls (this is called a special form). You don't need full-blown lazy evaluation for that, like Haskell has (although you could implement if-then-else as a simple function in Haskell). The statement by sepp that you can't write fold if you don't have a lazy if was not quite correct (and he deleted that comment already): You can emulate the behaviour by supplying lambdas to the if and calling the result. — Niklas B.
BTW, my confusion mainly came from the fact that you were presenting a "Scheme" example that is in fact not Scheme :) — Niklas B.

Daniel Wagner Daniel Wagner · Accepted Answer · 2012-04-15T22:49:40

I think it's pretty uncommon to evaluate under binders (and, in particular, to evaluate the body of lambdas), so I think the standard solution to lazifying a strict language is to introduce a lambda. I don't know the scheme syntax, but in Haskell syntax, if you wanted x to be a lazy parameter to a strict function f, you might write something like f (\() -> x) (and modify f appropriately to expect such lambdas, and call them at the moment you want to un-lazy them).

Implementing fold in simple purely functional language without lazy evaluation

2 Answers