Logo Questions Linux Laravel Mysql Ubuntu Git Menu

Tail-recursion optimization in Oz

In the chapter about function in the Oz tutorial, it says that:

similar to lazy functional languages Oz allows certain forms of tail-recursion optimizations that are not found in certain strict functional languages including Standard ML, Scheme, and the concurrent functional language Erlang. However, standard function definitions in Oz are not lazy.

It then goes on to show the following function which is tail-recursive in Oz:

fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}

What this does is, it maps the empty list to the empty list and non-empty list, to the result of applying the function F to its head and then prepending that to the result of calling Map on the tail. In other languages this would not be tail recursive, because the last operation is the prepend, not the recursive call to Map.

So my question is: If "standard function definitions in Oz are not lazy", what does Oz do that languages like Scheme or Erlang can't (or won't?) to be able to perform tail-recursion optimization for this function? And exactly when is a function tail-recursive in Oz?

like image 672
sepp2k Avatar asked Oct 03 '09 11:10


People also ask

What is tail recursion Optimisation?

Tail call optimization is the specific use of tail calls in a function or subroutine that eliminate the need for additional stack frames. Tail call optimization can be part of efficient programming and the use of the values that subroutines return to a program to achieve more agile results or use fewer resources.

Why tail recursion is efficient in reducing the stack size?

The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.

What is tail recursion with example?

Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. For example the following C++ function print() is tail recursive.

Is tail recursion optimized in Java?

Java doesn't have tail call optimization for the same reason most imperative languages don't have it. Imperative loops are the preferred style of the language, and the programmer can replace tail recursion with imperative loops.

Is tail recursion more efficient?

In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call. In simple words, in tail recursion, the recursive function is called last. So it is more efficient than non-tail recursion.

2 Answers

This is called Tail Recursion Modulo Cons. Basically, prepending to the list directly after the recursive call is the same as appending to the list directly before the recursive call (and thus building the list as a "side-effect" of the purely functional "loop"). This is a generalization of tail recursion that works not just with cons lists but any data constructor with constant operations.

It was first described (but not named) as a LISP compilation technique in 1974 by Daniel P. Friedman and David S. Wise in Technical Report TR19: Unwinding Structured Recursions into Iterations and it was formally named and introduced by David H. D. Warren in 1980 in the context of writing the first-ever Prolog compiler.

The interesting thing about Oz, though, is that TRMC is neither a language feature nor an explicit compiler optimization, it's just a side-effect of the language's execution semantics. Specifically, the fact that Oz is a declarative concurrent constraint language, which means that every variable is a dataflow variable (or "everything is a promise", including every storage location). Since everything is a promise, we can model returning from a function as first setting up the return value as a promise, and then later on fulfilling it.

Peter van Roy, co-author of the book Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi, also one of the designers of Oz, and one of its implementators, explains how exactly TRMC works in a comment thread on Lambda the Ultimate: Tail-recursive map and declarative agents:

The above example of bad Scheme code turns into good tail-recursive Oz code when translated directly into Oz syntax. This gives:

fun {Map F Xs}
   if Xs==nil then nil
   else {F Xs.1}|{Map F Xs.2} end

This is because Oz has single-assignment variables. To understand the execution, we translate this example into the Oz kernel language (I give just a partial translation for clarity):

proc {Map F Xs Ys}
   if Xs==nil then Ys=nil
   else local Y Yr in
      {F Xs.1 Y}
      {Map F Xs.2 Yr}
   end end

That is, Map is tail-recursive because Yr is initially unbound. This is not just a clever trick; it is profound because it allows declarative concurrency and declarative multi-agent systems.

like image 166
Jörg W Mittag Avatar answered Nov 15 '22 09:11

Jörg W Mittag

I am not too familiar with lazy functional languages, but if you think about the function Map in your question, it is easy to translate to a tail-recursive implementation if temporarily incomplete values in the heap are allowed (muted into more complete values one call at a time).

I have to assume that they are talking about this transformation in Oz. Lispers used to do this optimization by hand -- all values were mutable, in this case a function called setcdr would be used -- but you had to know what you were doing. Computers did not always have gigabytes of memory. It was justified to do this by hand, it arguably no longer is.

Back to your question, others modern languages do not do it automatically probably because it would be possible to observe the incomplete value while it is being built, and this must be what Oz has found a solution to. What other differences are there in Oz as compared to other languages that would explain it?

like image 34
Pascal Cuoq Avatar answered Nov 15 '22 09:11

Pascal Cuoq