Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Programming Without Variables

September 12, 2013

Last week, I discussed two different philosophies of programming-language design. One philosophy is that programming languages exist in order to grant convenient access to computer hardware; the other is that a programming language should make it easy to write programs, and that the computer's job is then to execute those programs.

I used mathematical notation as an example. In general, mathematicians use a particular name to denote a single value in a particular context. The common notion in programming that a name denotes a "variable," which might have one value at one time and another value at another time, is generally absent from mathematical notation.

As an example, I posed a problem: Rewrite the following C function so that a name denotes only a single value at any given time:

unsigned collatz(unsigned n)
{          
        assert(n != 0);
        unsigned count = 0;
        while (n != 1) {               
                if (n % 2 == 0)                     
                        n /= 2;               
                else                     
                        n = 3 * n + 1;               
                ++count;
        }   
        return count;    
}

Several readers proposed solutions; the most straightforward of which is the one by reader Nons:

 
unsigned rcollatz(unsigned n)

{
    
      assert(n != 0);
    
      if (n == 1)
        
          return 0;
    
      else if (n % 2 == 0)
        
          return 1 + rcollatz(n / 2);
    
      else
        
          return 1 + rcollatz(3 * n + 1);

}

This is an example of replacing an iterative strategy by a divide-and-conquer strategy. The general idea of the latter is that you solve a simple case of the problem, and then you solve the more complicated cases by finding a way to reduce that more complicated case to one or more simpler cases.

Although the idea of replacing iteration by divide-and-conquer is straightforward to explain, it has a pragmatic disadvantage: Programming languages typically have to store in memory the chain of function calls currently being executed, which means that each trip through this "loop" consumes memory to keep track of those calls. In other words, rcollatz needs an amount of memory proportional to its result in order to run.

There is an alternate, somewhat more complicated, technique to translate a function with a loop into a recursive function that does not change any variables. It takes advantage of the fact that it is usually possible for a compiler to translate a tail recursion into a jump instruction. A tail recursion is a recursive call that is used immediately as the function’s result. So, for example, the statement

 
return 1 + rcollatz(n / 2);

does not involve a tail recursion because after rcollatz returns, its result is used as an operand of +. If, on the other hand, we were to write

 
return rcollatz(n / 2);

that call would be a tail recursion.

Here is how to replace a loop by a function that uses only tail recursion:

  1. Identify every variable with a value that changes during the loop.
  2. Define an auxiliary function with one parameter for each of the variables identified in (1).
  3. Replace the loop with a tail-recursive call that uses the new values of the variables.
  4. Replace the original function with a call to the auxiliary function with the appropriate initial values for the variables.

In the case of collatz, step (1) should identify the variables n and count. Steps (2) and (3) yield the following auxiliary function:

 
     unsigned collatz_aux(unsigned n, unsigned count)
     {
           if (n == 1)
                return count;
           else if (n % 2 == 0)
                return collatz_aux(n / 2, count + 1);
           else
                return collatz_aux(3 * n + 1, count + 1);
     }

Step (4) then gives us the following tail-recursive version of collatz:

 
     unsigned trcollatz(unsigned n)
     {
           assert(n != 0);
           return collatz_aux(n, 0);
     }

What we have learned so far is that, at least for this function, it is possible to rewrite it so that its "variables" never actually vary, and with a little effort and a reasonable compiler, it is possible to do so while maintaining the program's speed.

However, there's a problem, which we can see if we change the original program specification: Instead of returning the number of steps needed to reach 1 from a given input, suppose we want to return the entire sequence of values reached during the Collatz process. We can write that program iteratively as follows:

vector<unsigned> collatz_vec(unsigned n)
{
          
     assert(n != 0);
     vector<unsigned> result;
          
     while (n != 1) {
          
               result.push_back(n);
               if (n % 2 == 0)
                     
                      n /= 2;
               
               else
                     
                    n = 3 * n + 1;
               
       }
       return result;
    
}
 

If we try to write this program recursively using the technique we mentioned earlier, we find that each recursive call passes the entire result array as an argument. As a result, the program's runtime will be quadratic in the number of iterations — hardly a happy state of affairs. In effect, the whole idea of an array is built on being able to change part of it, and if we intend to avoid changing memory once we have put values into it, we need another kind of data structure entirely. Next week, we'll look at what such a data structure might be.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

dblake950
2013-10-22T18:30:53

see how psychic you were (are?)


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2013-10-09T16:07:29

Good way to put it.


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2013-10-09T16:05:11

Yep. Well, sort of. More generally, I'm trying to disabuse programmers of the notion that the way they happened to learn to program is the only way.
This attitude leads to new programmers repeating their predecessors' mistakes--mistakes from which they could have learned had they known what those mistakes were.
I call this phenomenon "reinventing the square wheel."


Permalink
ubm_techweb_disqus_sso_-08558a0ab542c72a44ca35ae28de00c3
2013-09-18T16:11:08

Equivalent statement :D


Permalink
ubm_techweb_disqus_sso_-26bc16b45232912ebfa304b63f5eb0ec
2013-09-18T07:51:27

I feel Lisp coming up *grin*


Permalink
ubm_techweb_disqus_sso_-c802d7303e9b34fe631dfb02f0d8d993
2013-09-18T01:23:51

Mathematics has parameters. It does not have mutable variables.


Permalink
ubm_techweb_disqus_sso_-423c3daeb800f393f38c48fd76f73ed4
2013-09-17T20:47:50

The “vector<unsigned> collatz_vec(unsigned n)” example is ugly in that we need to return the
whole array. If using a recursive call,
then place the function in a class and save the array as a class object. Yes, it is easier to focus in at the function
level only. But, this is C++ where we
can use objects. Maintaining the array
as a class item allows us to have a high level (controller) function that
starts the call sequence to the recursive function, then the recursive function
loads the array then calls itself again.
When the When n gets to 1, have the controller function return the
array.


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2013-09-14T19:16:20

Each time you use a "local scope," you are effectively creating a different context. The fact remains that within a given context, each name refers to a specific value.


Permalink
ubm_techweb_disqus_sso_-3f93c7557cf656fff40964309589760f
2013-09-14T10:12:42

I think the description in the article is quite clear: “you solve a simple case of the problem, and then you solve the more complicated cases by finding a way to reduce that more complicated case to one or more simpler cases.”.

In essence a problem is divided into smaller problem, for the programmer. The source code is then a direct expression of the division of the problem, with two or more distinct cases (including at least one base case, something that can be solved directly). The computer may still have to do exactly the same.

In the code you show the first collatz function is tail recursive, but due to the result.push(n); it varies (changes, modifies) the value of at least one variable.


Permalink
ubm_techweb_disqus_sso_-3f93c7557cf656fff40964309589760f
2013-09-14T03:15:15

This is incorrect:

"If we try to write this program recursively using the technique we mentioned earlier, we find that each recursive call passes the entire result array as an argument. As a result, the program's runtime will be quadratic in the number of iterations",

If the arrays had to be physically copied the statement would have been true. But for this example no array copying is needed. Example code using a non-copyable array, demonstrating that the array is not physically copied at all:

http://ideone.com/M2v1EP

For readers not familiar with std::vector behavior: the emplace_back member function has amortized linear complexity, thus this array-based code has linear time.

(I posted a comment about this yesterday in the Facebook group "C++ Enthusiasts", [https://www.facebook.com/group...].)


Permalink
ubm_techweb_disqus_sso_-42fcc713411987355befe844f4dc9bf4
2013-09-13T17:21:56

Would you please elaborate on why do you label the rcollatz function a divide-and-conquer algorithm?, usually an algorithm of this type generates a tree of calls, which I don't see happening.

Also, does this implementation ("trcollatz_vec" function in http://repl.it/KfK) qualify as tail recursive? Anyway, there doesn't seem to be a quadratic number of iterations, unless the 'push' function for the array (or vector in c++) iterates over all the elements in order to put the new one in the last place.

Edit: Layout


Permalink
ubm_techweb_disqus_sso_-fabaf40b9c7fb028af1d39af16bf35f5
2013-09-13T17:08:56

"The common notion in programming that a name denotes a "variable," which might have one value at one time and another value at another time, is generally absent from mathematical notation."

I'm rather confused by this sentence, because in my experience, this concept is extremely common in mathematics. Any time you define a function f(x), you're creating a local scope and explicitly saying that "x" will have different values at different times. "∀" and "∃" (sort of) and "∫" and "Σ" and "Π" also do this. Or consider limits: you're not only declaring that (at least) one variable takes on multiple values, you're declaring that it takes on an infinite number of them!

I think you're getting at something, but it's not quite as clear-cut as "mathematicians don't have variables that change values". It might be more like: "mathematicians don't have variables that change values within one particular scope", or: "mathematicians are careful to distinguish between independent variables (x), dependent variables (y), and constants (x0)".


Permalink
ubm_techweb_disqus_sso_-08558a0ab542c72a44ca35ae28de00c3
2013-09-13T09:18:38

I feel Lists coming up...


Permalink


Video