Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Theory Versus Practice: The Great Divide in Programming Languages

September 06, 2013

Last week, I talked about four major, early programming languages: Cobol, Fortran, Algol, and Lisp, and said that Lisp differed from the other three in a fundamental way. That difference is really comes from a philosophical difference about the relationship between programs and computers.

Here's the key question: Do programs exist in order to tell computers what to do, or do computers exist in order to execute programs? In theory, this is a silly question, because the two "alternatives" amount to the same thing, and they are both obviously true. In practice, however, preferring one or the other has a profound effect on the design of programming languages and, to a lesser extent, of computers.

For example, if programs exist in order to command computers, it follows that programming languages should expose those aspects of computers that their users might wish to command. This viewpoint might well lead to the conclusion that assembly languages are the most important kinds of programming languages, as they offer the most direct way of telling computers what to do that is consistent with humans' being able to write programs in those languages.

In contrast, if computers exist in order to execute programs, then it is less important to design programming languages to fit particular computers well than it is to design computers to fit the best programming languages. Of course, this strategy leads to another hard question: What is the best programming language? Moreover, it offers no guidance as to how to figure out which language is the best.

Designing a programming language in order to command a computer leads to the conclusion that the language should look like the computer. If, on the other hand, the programming language comes first, how does one decide how the language should work? If it's not based on an existing computer, and there are no earlier programming languages to use as a model, where does one start?

One logical starting point is mathematics. Mathematical notations have been around for millennia, and mathematicians continuously refine the notation they use in order to make that notation more effective at expressing their abstractions. Accordingly, it makes sense to use some form of mathematical notation as the basis for a programming language.

Every mathematical notation that I have ever seen uses names to refer to concepts that, once defined, do not change within a single context. Such a concept might refer to other values to be defined later, or tentatively defined, but the concept itself remains the same. For example:

Let z be the length of the hypotenuse of a right triangle with legs of lengths x and y, respectively.

This sentence defines z in terms of x and y. It leaves x and y unspecified, but once they have been defined, z is also defined. As long as we are talking about this particular z, it will never be used to mean anything else. So, for example, although we might write something in Fortran that looks similar:

 
               Z = SQRT(X**2 + Y**2)
 

there is a profound difference between the Fortran statement and the corresponding mathematical statement. In Fortran, there is nothing to stop us from writing

 
               Z = Z * 2.0

after which the variable Z has a different value from the one it had before. This kind of statement is a natural way to expose the fact that a computer has memory, and the contents of that memory can change from time to time.

In contrast, a mathematician would never write

Let z refer to its previous value multiplied by 2.

Instead, a mathematician might write something like

Let z' = 2z

Here, the apostrophe (pronounced prime) indicates that z' is related to z in some way; but aside from this relationship, z and z' are two different names. Accordingly, there is never any confusion about which value is associated with z at which time; one always writes z or z' to make the choice explicit.

How do mathematicians deal with problems that involve iteration? For example, consider the following C++ function:

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;
     
}

This function takes a strictly positive integer and repeats the following:

  • If the integer is even, divide it by 2.
  • Otherwise, multiply it by 3 and add 1.

If this process eventually yields 1, the function returns the number of repetitions required to do so; otherwise, the function never terminates. As the function's name suggests, the Collatz conjecture is that this function always terminates for any value of n. The conjecture has been shown by experiment to be true for all integers up to 5*260, but whether it is always true is still unknown.

Obviously, this C++ function uses the names n and count to refer to quantities that vary during the program's execution. In effect, each of these names refers to different things at different times. This programming style is so natural to programmers who have started by learning programming languages that are based on how computer hardware works, such as C or C++ (or Fortran, Algol, or Cobol), that it may be hard even to imagine how one would express such a computation without using a single name to refer to multiple quantities.

Nevertheless, basing a programming language on mathematics yields a workable, although completely different, way of expressing such computations. I'll continue exploring that way next week. Between now and then, I invite you to try rewriting this function in a way that avoids ever changing the value of a "variable" once it has been initialized.

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:

ubm_techweb_disqus_sso_-e45861e6d5eff9bcfc725427b05bbac6
2013-09-23T19:26:45

I'm a bit confused about how what you are describing is different from the many forms of declarative programming that are common in many domains already. Specifically, by contrast to these two obviously related topics:

1) Your description of the use of mathematical relations, as opposed to imperative instructions, seems to me to be just a good old-fashion symbolic math language is, like Sage, Maple, Mathematica, SymPy, SymbolicC++, and countless others...

Symbolic math languages are nice, that's for sure, but they suffer greatly from the problem having to encode (in the form of math relationships) all possible computations, leaving a heavy trail of intermediary expressions and relations. This greatly limits their application to complex problems. For example, working out a symbolic inversion of a 12x12 matrix is about as much as you can do without running out of system memory. And I don't know that a computer that would be made for that purpose would really be able to break that curse.

2) As for declarative programming in general, I love it, when it makes sense. Many libraries and frameworks in C++ (and others) are essentially declarative DSELs. It's a paradigm that is used far more often than it is recognized as such. How often do you see libraries where the user-code goes something like this: create a bunch of objects, declare some symbolic relationships between them, and call "execute". I see this often, and write such code often too. In some domains, this is clearly a nicer way to organize things, but I wouldn't say it is revolutionary or could really be a viable "replacement" for imperative control flows.


Permalink
ubm_techweb_disqus_sso_-3f93c7557cf656fff40964309589760f
2013-09-22T08:59:21

http://en.wikipedia.org/wiki/L...

Oh well you got me into reading your DDJ postings…

One way that mathematicians deal with time-varying quantities is to model them as functions of time. The Lucid data flow language was based on this idea: replace each imperative language variable mathematically with an infinite sequence of values indexed by time, for practical programming implemented as an infinite data flow. With lazy evaluation it even works! :-)

But, for use of Lucid on ordinary computers it's like using a limited, complex and quite inefficient simulation of X when you have X directly available...

I think that lazily evaluated infinite data flows are probably not exactly what you had in mind, but they are certainly “a workable, although completely different, way of expressing such computations”, and I think it’s a fairly direct (perhaps in practice the most direct?) expression of the most natural mathematical model of ordinary computer programming variables.

That said, in C++11 we can go a long way towards immutability (the benefit of knowing that a variable does not detectably change after initialization) by sprinkling CONST generously all over the code, and extending C++11 move semantics to logically const variables so that behind the scenes, when a variable is logically destroyed its contents can be pilfered and reused, just MOVING data around. We could do that earlier too, but apparently not conveniently enough or standard enough to make it attractive. E.g. Andrei Alexandrescu's Mojo framework for move semantics with C++98, never took off (I was one of the many who helped peer-reviewing the original Mojo work, but I never got myself into actually using the stuff, while now with C++11 I do use C++11 semantics all the time).


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2013-09-12T17:45:23

How a language designer chooses to represent symbols that the hardware cannot produce directly has little to do with the design of the language itself. In the case of APL, for example, the designers simply arranged to manufacture custom parts for printers and typewriters so that they could produce the symbols they desired. In contrast, the FORTRAN designers decided to use unique sequences of symbols to represent characters that were not part of the native character set.


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2013-09-12T17:42:26

My point is that there is more than one way to think about programming-language design, and that choosing one way or the other leads to very different conclusions about design issues. I'm saying nothing about how programming languages *should* be.


Permalink
ubm_techweb_disqus_sso_-bf67b400e08a0cfc81cee3a104be46d0
2013-09-12T00:13:50

I think this series of articles was written to explain that there is a programming alternative to procedural instructions.


Permalink
ubm_techweb_disqus_sso_-bf67b400e08a0cfc81cee3a104be46d0
2013-09-11T16:47:32
As the function's name suggests, the Collatz conjecture is that this function always terminates for any value of n. The conjecture has been shown by experiment to be true for all integers up to 5*2^60, but whether it is always true is still unknown.

This conjecture may be true for mathematics. However, computers are not mathematics. They are physical machies and machines have limits, such as maximum numerical values.


Permalink
ubm_techweb_disqus_sso_-d61ca45a8c7fed1a423c3901aeec682d
2013-09-11T13:37:13

If I understand, it seems that your point is that math notation in programming should be more like math notation in mathematics. I would just suggest that much of programming is procedural instructions on how to do something, not math.


Permalink
ubm_techweb_disqus_sso_-cb8bb56280f959a5465d21027fa57560
2013-09-09T14:02:05

Andrew, you claim 'it makes sense to use some form of mathematical notation as the basis for a programming language.' I would suggest APL as an option, since it is very much based on mathematics.

Also, a lot of the problems that FORTRAN, for example has with the equal sign is that it is not used for what math uses it for, in fact, FORTRAN uses .EQ. Languages like Pascal use := and APL uses ←, a proper arrow.


Permalink
ubm_techweb_disqus_sso_-e6422c70c5a8ec53d0dc39e2056f0a7f
2013-09-09T13:40:44

Recursion with less funny business:

unsigned rcollatz( const 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 );
}

Andrew, if you have a moment, please also look at http://www.drdobbs.com/cpp/som...

I'm still not clear on why you think two overloads are better than one function when it comes to rvalue refs.


Permalink
ubm_techweb_disqus_sso_-4d39347e8879e34b6cdf05d5909cbe13
2013-09-08T14:04:40

Tail recursion will work also in plain ol' C for most modern compilers due to FPO and register calling conventions (not that collatz ever iterates long enough to blow the stack).



unsigned collatz(unsigned n, unsigned c = 0) {
if (1 == n) return c;
collatz(n%2 ? 3*n+1 : n/2, c+1);
}


Permalink
ubm_techweb_disqus_sso_-551be50f3638710d529d9bf6a754cc9b
2013-09-08T01:24:36

I thought I would give a shot at a Haskell solution. The solution is similar to #GSANDERSOX1 in that it uses tail recursion. The Haskell solution demonstrates a mathematical solution with no specific variable storage.

collatz :: Int -> Int
collatz 0 = error "n != 0"
collatz n = collatz_f n 0
where
collatz_f 1 c = c
collatz_f n c | n`mod`2 == 0 = collatz_f (n`div`2) (c+1)
| otherwise = collatz_f (3*n+1) (c+1)


Permalink
ubm_techweb_disqus_sso_-6de6f495af51dbef17da79cf9e7077cd
2013-09-07T14:22:25

One solution to the challenge to never modify a variable once it has been initialized is to use tail recursion instead of iteration.

Using Visual Studio 2012 which requires lambda trailing return types, this is one possible solution.

unsigned collatz(unsigned n)
{
std::function<unsigned(unsigned,unsigned)> f = [&f](unsigned n, unsigned count) -> unsigned
{
if (n == 1)
return count;
return f(n%2 == 0 ? n/2 : 3*n+1, count+1);
};
return f(n, 0);
}

Permalink


Video