Visualizing Math – a Small Example

Studying mathematics means investigating numbers and formulas. Getting an understanding of their abstract nature can be difficult. Computers, and the visualizing power of computer graphics, can help us to glimpse in a concrete way the natures of some of these mathematical beasts.

Lets start with a mathematical artifact that is simple to state, the so-called 3n+1 (or Collatz) sequence. Choose any integer to start the sequence. Calculate successive terms of the sequence like this:

• If the number is even, halve it to get the next number;
• If the number is odd, triple it then add one to get the next number.

For example, start with 10:

• 10 is even, so halve it to get 5.
• 5 is odd, so triple it and add 1 to get 16.
• 16 is even, so halve it to get 8.
• 8 is even, so halve it to get 4.
• 4 is even, so halve it to get 2.
• 2 is even, so halve it to get 1.
• 1 is odd, so triple it and add 1 to get 4,
• And we’ve gone into a loop: 1, 4, 2, 1, 4, 2.

Experiment with a few numbers and you might soon notice a few things. First, sequences seem almost completely erratic. Second, they all seem to end up in the loop 1-4-2-1 sooner or later. Third, calculating many long sequences becomes tedious.

Let’s use the computer to remove the tedium by writing a tiny program. The program is written in Python, a language which, along with its interactive shell, encourages playful, curiosity-driven programming.

>>> def chain( num ) :
    """For a given number, print its 3n+1 sequence."""
    while num > 1 :
        print( num, end=" " )
        num = num//2 if num%2 == 0 else 3*num+1
    print( num, end="\n" )

>>> chain(10)
10 5 16 8 4 2 1 

Now it gets a little easier to explore:

>>> for i in range(10,20) :
    chain(i)
10 5 16 8 4 2 1 
11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
12 6 3 10 5 16 8 4 2 1 
13 40 20 10 5 16 8 4 2 1 
14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
16 8 4 2 1 
17 52 26 13 40 20 10 5 16 8 4 2 1 
18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

You see that the sequences drift up and down but with no real pattern, like a leaf in the wind.

The Three Modes of Programmers at Work

Over the years I have been able to observe how software developers do their jobs in a variety of circumstances, and I have come to the conclusion that developers operate in three distinct modes. These modes I call from principles, from cookbook, and trial and error. An individual developer often has a preferred mode, but will switch between modes depending on the complexity of the software being created, the developer’s own depth of skill, and the perceived pressure of the delivery deadline.

In sequence from most to least desirable, here are the three modes:

From Principles. This is how you were taught at school to do things. You learned the fundamentals of the programming languages and tools, and you learned good processes for turning a design into a software product. Later you sharpened those skills with practical experience. Programming from principles is what we have come to associate with being professional.

A skilled carpenter learns the characteristics of all different kinds of wood, and therefore is able to select the right wood for any project, whether it is a dining-room table or a doghouse. Similarly, a skilled developer knows different design approaches, and understands the capabilities and limitation of various software languages and libraries, and can so choose those that are best suited to a project at hand. During construction, the skilled carpenter uses his knowledge to make decisions along the way that may not seem obvious but which affect the quality and durability of the finished product. For example, what is the best way to join two pieces of wood? Choices range from a simple butt joint to a traditional mortise and tenon, to a sturdy-looking dovetail, to simply nailing. The decision is influenced by the type of wood, how much stress will be on the joint, whether the joint will be visible, and on how much effort he is willing to commit. Similarly, during the course of building a piece of software, the developer must make many small but non-trivial decisions that together determine the quality of the delivered product. The developer uses her professional insights to guide those decisions.

Raymond Chen, a software design engineer at Microsoft, writes an extensive blog in which he often relates problems submitted by clients. Many of these problems seem to stem from incorrect decisions made because of gaps in the knowledge of programming principles. For example, using a global solution to a local problem is a common misstep. If you want to prevent users from printing the contents of a particular window, the thing to do is find a way to flag only that window as unprintable, not disable the PrtSc key which affects all windows. In another recent entry, he shows how an understanding of fundamentals helps you make serious headway in analyzing a program failure. There, understanding the underlying memory model of the system helped Raymond make sense of the application data he saw, and informed his choices of next steps, despite being unfamiliar with the specific application.

Applications that we think are awesome usually come from programmers who have that deep understanding of the software platform, the application domain, and the professional practices. In other awesome apps are made by programming from principles.

Of course, in the real world, programmers often don’t have the time  — or inclination — to get a deep understanding of all the software platforms that they have to work with.

Programming Unleashed – Or should it be Leashed?

Unleashed by the Book

If you browse in the computer-book section of any well-stocked bookstore, you will usually come across two or three books titled “Xxx Unleashed” where xxx is something to do with software. Developers can choose from titles like Java 2 Unleashed, JavaScript Unleashed, or PHP Unleashed. For system administrators there are titles like Windows Server 2012 Unleashed. (If I was a company’s IT manager, I’m not sure if I would want my sys admins, with their digital powers and privileges, to be really unleashed.) And if you want to take a break from screen and keyboard for a few minutes, there’s Doodles Unleashed to help you goof off productively.

I have a bit of a contrarian streak, so I thought to myself that it would be amusing for someone to publish a “leased” book. What might you learn from a book called Java 2 Leashed if it existed? (It turns out there are some “leashed” books but they are found in the romance and fantasy sections and have covers that would discourage anyone from reading them on public transit which may explain why most are available only for e-readers.)

What is an Unleashed Programmer? Two Views

However, having observed software being developed  by professionals, I am starting to think that there might be something serious with this contrarian idea. Perhaps production software could benefit from developers choosing to have a “leashed” mindset. Let me explain.

The term unleashed brings to mind two separate meanings:

1. Able to roam anywhere. This unleashed dog in the park roams to any corner of the park and snuffles around wherever it likes. Similarly, an unleashed programmer can roam to any corner of the documentation, understand it, and figure out how to use any feature that the programming system offers.
2. Able to act without restraint. This unleashed dog does whatever it wants in the park: jumping up on adults, knocking over little kids, and leaving doggy doo surprises. Similarly, an unleashed programmer can use whatever programming tricks, copy-pasted program snippets, or code hacks he can think of until his code passes the documented test cases.

Examples of Recursion: The Good, the Bad, and the Silly

What we need: a really good example

The programming artefact of recursion, also known as “writing a subroutine that calls itself”, is well known to generations of students of computer science. Recursion is a reasonably simple yet a remarkably powerful concept. That is, it’s a reasonably simple concept once you understand it, but unfortunately, it can take some effort to get that understanding.

Teachers of computer science are faced with the challenge of finding good examples of recursive programs to offer to their students. The ideal example will demonstrate the principle of recursion clearly while hinting at its power, and thus show why it’s a compelling concept. Over the years I have come across examples of recursive programs, enough now that I think I can classify them into three broad categories: the good, the bad, and the silly. Here are the categories, each with an example:

The Good: Towers of Hanoi

Towers of Hanoi is a puzzle that consists of three posts, and a set of disks of different sizes with holes in the middle so that the disks can be stacked on the posts. You start with all disks stacked on one post, ranging from smallest to largest, top to bottom. Your job is to transfer the stack from the first post to the third, using the second post for temporary storage. You can only move one disk at a time, and you can never place a larger disk on top of a smaller disk.

The puzzle can be solved easily by breaking down the job into smaller jobs. To move the entire stack of disks from the first to the third post, do these steps:

• Move the (slightly smaller) stack of all but the largest disk from the first to the second post,
• Then move the largest disk from the first post to the third,
• Then move the (slightly smaller) stack from the second to the third post.

The middle task is a simple step – just move one disk – but the first and last steps each require solving again the Towers of Hanoi puzzle but for a smaller stack. In other words, solving the full puzzle requires solving two simpler instances of the puzzle.

Why are C’s Pointers and Arrays Confused?

C Arrays and C Pointers

One thing that always confuses is people learning the C programming language is the duality between arrays and pointers. In your C program you might create an array, which is a block of storage:

Then when you call a subroutine with the array as a parameter, the array magically transforms into a pointer to itself:

You are taught that array definitions are different from pointer definitions:

Except in places where they aren’t:

Now, when you were first learning the C programming language, you probably asked yourself: why do arrays and pointers have this confusing relationship; why can’t arrays just be arrays and a pointers just be pointers? (Or maybe you didn’t ask yourself. While studying programming, perhaps you have come to believe that computer languages are by nature complex and arcane things full of unknowable mysteries, and that true programmers have skills that are a cross between those of tax accountants and Harry Potter. And all this stuff about arrays and pointers merely reinforces your belief.) Well, it turns out there is a reason why arrays and pointers act as they do, and this reason is rooted in the history of the C programming language.

The Language that Came Before C

When Dennis Richie at Bell Labs designed the C programming language in the early 1970s, he based it on another language named B, which had been designed by colleague Ken Thompson.

A program written in B would be reasonably legible to a C programmer because B is essentially a simpler version of C. The most notable difference between B and C is that B is a typeless language, that is, variables do not have explicit data types like character or integer. Or, rather, there is exactly one data type: the machine word, which is equivalent to C’s integer type ‘int’.

Now you might think that working with things like character strings would be difficult when your only data type is int, but B provides some help. For example, characters treated as small integers (e.g., ‘A’ is identical to 65), and a string is an array of words with four characters packed per word. To work with the characters in a string, you use the library functions char( string, index ) and lchar( string, index, replacement ).

Arrays are a problem because you obviously cannot pack an array into a single machine word. B solves this problem by defining an array to be a pointer to a block of storage, and having program code deal with the pointer, which does fit in a word. This means that when you define an array, B sets aside storage for both the array itself and the pointer to it:

When you work with an array in B, you are always working with the pointer. This makes it straightforward to pass an array to a subroutine: you pass the pointer to the block of storage unchanged, and both the caller and callee work with the same thing, namely that pointer. This also keeps B’s calling mechanism simple: parameters are always passed by value with no danger of trying to copy blocks of storage into subroutines.

C Tries to Keep Things Tidy

With C came a full suite of data types including arrays as fully-fledged objects. This has advantages, for example, the program does not create pointers unnecessarily, and multi-dimensional arrays are easy to build. However there is a downside when calling subroutines. Because C passes parameters by value, passing an array to a subroutine theoretically means copying the entire array into the subroutine. Not only is copying a block of storage expensive for all but the tiniest of arrays, it is generally not a useful thing for a program to do.

There are a couple of ways around this call-by-value-with-arrays issue, but both involve additional syntax. One way is to allow both call-by-value and call-by-reference parameters in subroutine calls. C++, for example, supports both modes; programmers can select call-by-reference by adding an “&” to the parameter declaration. Another way is to require the programmer to explicitly generate pointers to arrays and pass them into the subroutine, but this requires the programmer to clutter the subroutine code with dereferencing “*” operators.

With C, Ritchie tried to find a middle ground by designing a mechanism for subroutine calls that normally uses the traditional call-by-value, but automatically switches to call-by-reference for arrays. This solves the call-by-value-with-arrays problem and avoids explicit syntax for call-by-reference parameters. This permitted C to deliver the benefits of arrays as first-class objects, while offering a familiar, uncluttered syntax to B programmers (and to Fortran programmers as well) who were migrating to C.

This design fix, with what might be called “hidden dereferencing”, has proven effective in routine program code. It is when a programmer wanders off the beaten path that hidden dereferences can come out hiding and bite not only students but also professional programmers.

Back to the Future with Java

Other languages like Pascal, which appeared around the same time as C, and C++ support both call-by-reference and call-by-value parameter-passing modes with explicit syntax to distinguish the two (“var” and “&”, respectively). Interestingly, Java, a language of more recent design, goes back to B’s idea of always using references (i.e., pointers) to deal with objects.

Although Java’s object references — whereby you always work with references to objects  rather than directly with the objects themselves — echoes the array pointers of B, Java’s references are more sophisticated than B’s pointers. B programmers had to worry about memory leakage (a block of memory with no pointer to it), dangling pointers (a pointers referring to a block of memory that has been deallocated), and other such horrors. Java has tamed the wild pointers of B through built-in mechanisms such as garbage collection and automatic array-bounds checking.