2

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?

3
  • 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, 2020 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, 2020 at 20:58
  • Tail-call recursion can be done in any language. If tail-call optimization is not being done which turns the call into a loop, then this is done at the expense of the stack. Nov 27, 2021 at 12:55

3 Answers 3

5

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.

7
  • "why make your language unnecessarily complex with two concepts..." - indeed, why have function calls when you can write it all in assembly? For me, the problem is that just because everything can be done recursively, does not mean it is usually the easiest possible conception of the task, especially with the typical syntax. There are several common looping constructs in imperative languages - while, for, foreach, etc. They can all be implemented in terms of conditions and jumps, but they exist severally because each one is suited to a different use and makes it easier for the programmer.
    – Steve
    Nov 27, 2021 at 19:39
  • @Steve: If you have proper tail calls, or even just proper tail recursion, you can implement all of those looping constructs you mentioned, and even ones you didn't mention, or ones that haven't been invented yet, or ones that are not general enough to warrant inclusion in the language but might be perfect for your particular situation, as library functions. No need for loops as a language construct, when implementing them as a library function is just a one-liner. Put another way: some problems can be elegantly solved with tail recursion, some with loops. If you only have loops but no proper Nov 27, 2021 at 19:45
  • … tail recursion, then you cannot elegantly solve the ones that require tail recursion. OTOH, if you have proper tail recursion but not loops, you can elegantly solve both, because you can trivially and elegantly implement loops using tail recursion. Nov 27, 2021 at 19:46
  • But have you understood my point that the syntax itself is important for ease of use? Anything you can do with a for-loop you can do with a while-loop, and anything you can do with a while-loop you can do in assembly - and assembly can do at least as much as any higher level construct. Yet the for-loop remains indispensable, for example because of the way it brings into the block header all the control elements which relate to certain kinds of loops. Similarly, it may be possible to do anything with tail recursion alone, but syntactically it leaves a lot to be desired in most cases.
    – Steve
    Nov 27, 2021 at 21:52
  • @Steve: I don't really understand what you are saying. Let's take Scala as an example, because it actually has a while loop built in as a language construct but also supports proper direct tail recursion. Given the definition of a user-defined library function for a while loop I gave in my answer above, this is what a loop using my user-defined whiley loop looks like: whiley (i < 10) { println(i); i += 1 }. And this is what a loop using the language built-in while loop looks like: while (i < 10) { println(i); i += 1 }. How exactly is the second one easier to use than the first one? Nov 28, 2021 at 5:21
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.

0

For example, the sum of integers from n to m is 0 if n > m, and n plus the sum of integers from n+1 to m otherwise. You can write code for this using tail recursion. If tail recursion is part of the language this will work and be efficient.

A C or C++ compiler may optimise this using tail recursion, or it may not. Without tail recursion optimisation, this will likely crash within a millisecond. And even if it works with your compiler, there’s no guarantee that it will work with the next compiler version, and definitely not with a different compiler.

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.