0

I'm currently reading through Structure and Interpretation of Computer Programs (SICP). During the course of that book, the lesson of "you can optimize recursive procedures by writing them as tail recursive" is drilled in to the reader again and again. In fact, I'm nearly 100 pages in and have yet to see a single for or while loop - it's all been recursion. This is starting to worry me. To my knowledge, optimizing tail calls in a way that effectively turns tail recursive procedures in to iterative procedures is not a common feature in modern programming languages. This gives me my question: If I'm using a language that does not optimize for tail recursion, how can I apply these lessons that SICP has been teaching? Is the knowledge at all transferable?

2
  • Tail-call optimization depends a lot on the language and on the language's implementation. E.g. Java/OpenJDK and Python/CPython do not offer automatic TCO, but C++/GCC does. Of course you can manually transform a tail-recursive solution into a solution using loops, if necessary. Some programming advice in SICP is specific to their LISP flavour, but the more general advice about problem solving are universal. – amon Nov 15 '20 at 18:48
  • As far as I remember, the first 3 chapters of SICP are about creating functional abstractions, creating data abstractions, and creating abstractions with objects/mutability/state. These topics are pretty independent from examples being implemented using recursion, or being implemented using standard iterations / loops. – Doc Brown Nov 15 '20 at 20:58
4

In fact, I'm nearly 100 pages in and have yet to see a single for or while loop - it's all been recursion.

Spoiler alert: you won't be seeing any loops in the book, for the simple reason that the language used in the book (a subset of Scheme) doesn't have loops.

You don't need loops if you have recursion because you can express everything you can express with a loop also with recursion. So, why make your language unnecessarily complex with two concepts, function calls and loops, when function calls on their own can do everything you need?

This is starting to worry me. To my knowledge, optimizing tail calls in a way that effectively turns tail recursive procedures in to iterative procedures is not a common feature in modern programming languages.

First off, you are conflating optimizations and language features. Secondly, you are conflating tail calls and tail recursion. Thirdly, I think your assumption is wrong.

Optimizations are features of a particular version of a particular implementation of a language. In fact, often, they even depend on the particular invocation, e.g. GCC has a wide variety of optimizations that can be turned on or off via command line flags, or can even be gradually configured via command line parameters. You cannot rely on optimizations when you write your code, because you don't know whether or not they will actually be applied. Maybe some of your users are using an implementation that doesn't have that particular optimization. Or they turn it off. Or they are using a newer version than you that removes that particular optimization.

Language features, on the other hand, are guaranteed by the language specification, so you can always rely on them. If an implementation doesn't implement that particular feature, then it violates the language specification.

A tail call is the "last call" that is evaluated in a subroutine. Recursion is when a subroutine calls itself, either directly (direct recursion) or indirectly by calling some other subroutine which calls the first subroutine (indirect recursion). Tail recursion, then, is when the recursive call is a tail call, and just like with recursion, there is direct tail recursion and indirect tail recursion.

This distinction is important, because direct tail recursion is much easier to optimize than general tail calls.

When we talk about tail call optimization (TCO), we are typically talking about an optimization (duh!), not a language feature. The corresponding language feature, which essentially mandates that every possible implementation must provide tail call optimization under a certain set of strictly defined circumstances, is usually called proper tail calls or proper implementation of tail calls (PITCH).

Similarly, tail recursion elimination is an optimization. The corresponding language feature does not necessarily have a common name, I usually call it proper tail recursion in analogy to the general tail call case.

What you are talking about, are not general proper tail calls. You don't need general proper tail calls to implement looping. You only need direct tail recursion:

def whiley(cond: => Boolean)(body: => Unit): Unit = 
  if (cond) { 
    body
    whiley(cond)(body)
  }

Which brings me to my last point: many modern languages actually do support at least proper direct tail recursion, some even support proper general tail calls.

Just a couple of examples:

This gives me my question: If I'm using a language that does not optimize for tail recursion, how can I apply these lessons that SICP has been teaching? Is the knowledge at all transferable?

Almost none of the lessons are about tail recursion. They are about computational thinking, abstraction, reuse, modeling, principles, concepts, etc. They are universally applicable across programming languages.

2

The SCIP book is about the fundamentals of programming and programming languages. It is not about lessons which you will apply to one specific programming language, rather it is about understanding the principles and choices underlying the different programming languages. For example how the presence or absence of tail-call optimization will lead to different approaches to solve the same problem in different languages.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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