December 27, 2015 8:35 AM

The Instinct To Discard Code Is A Kind Of Faith

I learned this one summer while writing and deleting the same program several times:

The instinct to discard is finally a kind of faith. It tells me there's a better way to do this page even though the evidence is not accessible at the present time.

The engineer in me always whispered that evidence supported the desire to delete the program and start over: a recognition that I understood encapsulation of behavior more clearly, or messages as a means of decoupling subsystems. Yet in the end there is also small bit of faith. "Surely some of the code I'm deleting is good enough to survive to the next generation..." The programmer, like the writer, must be willing to believe in such situations that "nature will restore itself".

(The above passage is a quote of Don DeLillo from The Paris Review, The Art of Fiction No. 135.)

Posted by Eugene Wallingford | Permalink | Categories: Software Development

December 26, 2015 2:12 PM

Moments of Alarm, Written Word Edition

In The Art of Fiction No. 156, George Plimpton asked William Styron, "Are you worried about the future of the written word?" Styron said, "Not really." But he did share the sort of moment that causes him alarm:

Not long ago I received in the mail a doctoral thesis entitled "Sophie's Choice: A Jungian Perspective", which I sat down to read. It was quite a long document. In the first paragraph it said, In this thesis my point of reference throughout will be the Alan J. Pakula movie of Sophie's Choice. There was a footnote, which I swear to you said, Where the movie is obscure I will refer to William Styron's novel for clarification.

Good thing there was an original source to consult.

Posted by Eugene Wallingford | Permalink | Categories: General

December 12, 2015 3:04 PM

Agreement: The Rare and Beautiful Exception

From How to Disagree:

Once disagreement starts to be seen as utterly normal, and agreement the rare and beautiful exception, we can stop being so surprised and therefore so passionately annoyed when we meet with someone who doesn't see eye-to-eye with us.

Sometimes, this attitude comes naturally to me. Other times, though, I have to work hard to make it my default stance. Things usually go better for me when I succeed.

Posted by Eugene Wallingford | Permalink | Categories: General, Personal

December 11, 2015 2:59 PM

Looking Backward and Forward

Jon Udell looks forward to a time when looking backward digitally requires faithful reanimation of born-digital artifacts:

Much of our culture heritage -- our words, our still and moving pictures, our sounds, our data -- is born digital. Soon almost everything will be. It won't be enough to archive our digital artifacts. We'll also need to archive the software that accesses and renders them. And we'll need systems that retrieve and animate that software so it, in turn, can retrieve and animate the data.

We already face this challenge. My hard drive is littered by files I have a hard time opening, if I am able to at all.

Tim Bray reminds us that many of those "born-digital" artifacts will probably live on someone else's computer, including ones owned by his employer, as computing moves to a utility model:

Yeah, computing is moving to a utility model. Yeah, you can do all sorts of things in a public cloud that are too hard or too expensive in your own computer room. Yeah, the public-cloud operators are going to provide way better up-time, security, and distribution than you can build yourself. And yeah, there was a Tuesday in last week.

I still prefer to have original versions of my documents live on my hardware, even when using a cloud service. Maybe one day I'll be less skeptical, when it really is as unremarkable as Tuesday next week. But then, plain text still seems to me to be the safest way to store most data, so what do I know?

Posted by Eugene Wallingford | Permalink | Categories: Computing

December 09, 2015 2:54 PM

What Is The Best Way Promote a Programming Language?

A newcomer to the Racket users mailing list asked which was the better way to promote the language: start a discussion on the mailing list, or ask questions on Stack Overflow. After explaining that neither was likely to promote Racket, Matthew Butterick gave some excellent advice:

Here's one good way to promote the language:
  1. Make something impressive with Racket.
  2. When someone asks "how did you make that?", give Racket all the credit.

Don't cut corners in Step 1.

This technique applies to all programming languages.

Butterick has made something impressive with Racket: Practical Typography, an online book. He wrote the book using a publishing system named Pollen, which he created in Racket. It's a great book and a joy to read, even if typography is only a passing interest. Check it out. And he gives Racket and the Racket team a lot of credit.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

December 08, 2015 3:55 PM

A Programming Digression: Generating Excellent Numbers


Whenever I teach my compiler course, it seems as if I run across a fun problem or two to implement in our source language. I'm not sure if that's because I'm looking or because I'm just lucky to read interesting blogs and Twitter feeds.

Farey sequences as Ford circles

For example, during a previous offering, I read on John Cook's blog about Farey's algorithm for approximating real numbers with rational numbers. This was a perfect fit for the sort of small language that my students were writing a compiler for, so I took a stab at implementing it. Because our source language, Klein, was akin to an integer assembly language, I had to unravel the algorithm's loops and assignment statements into function calls and if statements. The result was a program that computed an interesting result and that tested my students' compilers in a meaningful way. The fact that I had great fun writing it was a bonus.

This Semester's Problem

Early this semester, I came across the concept of excellent numbers. A number m is "excellent" if, when you split the sequence of its digits into two halves, a and b, b² - a² equals n. 48 is the only two-digit excellent number (8² - 4² = 48), and 3468 is the only four-digit excellent number (68² - 34² = 3468). Working with excellent numbers requires only integers and arithmetic operations, which makes them a perfect domain for our programming language.

My first encounter with excellent numbers was Brian Foy's Computing Excellent Numbers, which discusses ways to generate numbers of this form efficiently in Perl. Foy uses some analysis by Mark Jason Dominus, written up in An Ounce of Theory Is Worth a Pound of Search, that drastically reduces the search space for candidate a's and b's. A commenter on the Programming Praxis article uses the same trick to write a short Python program to solve that challenge. Here is an adaptation of that program which prints all of the 10-digit excellent numbers:

    for a in range(10000, 100000):
        b = ((4*a**2+400000*a+1)**0.5+1) / 2.0
        if b == int(b):
           print( int(str(a)+str(int(b))) )

I can't rely on strings or real numbers to implement this in Klein, but I could see some alternatives... Challenge accepted!

My Standard Technique

We do not yet have a working Klein compiler in class yet, so I prefer not to write complex programs directly in the language. It's too hard to get subtle semantic issues correct without being able to execute the code. What I usually do is this:

  • Write a solution in Python.
  • Debug it until it is correct.
  • Slowly refactor the program until it uses only a Klein-like subset of Python.

This produces what I hope is a semantically correct program, using only primitives available in Klein.

Finally, I translate the Python program into Klein and run it through my students' Klein front-ends. This parses the code to ensure that it is syntactically correct and type-checks the code to ensure that it satisfies Klein's type system. (Manifest types is the one feature Klein has that Python does not.)

As mentioned above, Klein is something like integer assembly language, so converting to a Klein-like subset of Python means giving up a lot of features. For example, I have to linearize each loop into a sequence of one or more function calls, recursing at some point back to the function that kicks off the loop. You can see this at play in my Farey's algorithm code from before.

I also have to eliminate all data types other than booleans and integers. For the program to generate excellent numbers, the most glaring hole is a lack of real numbers. The algorithm shown above depends on taking a square root, getting a real-valued result, and then coercing a real to an integer. What can I do instead?

the iterative step in Newton's method

Not to worry. sqrt is not a primitive operator in Klein, but we have a library function. My students and I implement useful utility functions whenever we encounter the need and add them to a file of definitions that we share. We then copy these utilities into our programs as needed.

sqrt was one of the first complex utilities we implemented, years ago. It uses Newton's method to find the roots of an integer. For perfect squares, it returns the argument's true square root. For all other integers, it returns the largest integer less than or equal to the true root.

With this answer in hand, we can change the Python code that checks whether a purported square root b is an integer using type coercion:

    b == int(b)
into Klein code that checks whether the square of a square root equals the original number:
    isSquareRoot(r : integer, n : integer) : boolean
      n = r*r

(Klein is a pure functional language, so the return statement is implicit in the body of every function. Also, without assignment statements, Klein can use = as a boolean operator.)

Generating Excellent Numbers in Klein

I now have all the Klein tools I need to generate excellent numbers of any given length. Next, I needed to generalize the formula at the heart of the Python program to work for lengths other than 10.

For any given desired length, let n = length/2. We can write any excellent number m in two ways:

  • a10n + b (which defines it as the concatenation of its front and back halves)
  • b² - a² (which defines it as excellent)

If we set the two m's equal to one another and solve for b, we get:

    b = -(1 + sqrt[4a2 + 4(10n)a + 1])

Now, as in the algorithm above, we loop through all values for a with n digits and find the corresponding value for b. If b is an integer, we check to see if m = ab is excellent.

The Python loop shown above works plenty fast, but Klein doesn't have loops. So I refactored the program into one that uses recursion. This program is slower, but it works fine for numbers up to length 6:

    > python3.4 6

Unfortunately, this version blows out the Python call stack for length 8. I set the recursion limit to 50,000, which helps for a while...

    > python3.4 8
    Segmentation fault: 11


Next Step: See Spot Run

The port to an equivalent Klein program was straightforward. My first version had a few small bugs, which my students' parsers and type checkers helped me iron out. Now I await their full compilers, due at the end of the week, to see it run. I wonder how far we will be able to go in the Klein run-time system, which sits on top of a simple virtual machine.

If nothing else, this program will repay any effort my students make to implement the proper handling of tail calls! That will be worth a little extra-credit...

This programming digression has taken me several hours spread out over the last few weeks. It's been great fun! The purpose of Klein is to help my students learn to write a compiler. But the programmer in me has fun working at this level, trying to find ways to implement challenging algorithms and then refactoring them to run deeper or faster. I'll let you know the results soon.

I'm either a programmer or crazy. Probably both.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Teaching and Learning

December 01, 2015 4:38 PM

A Non-Linear Truth about Wealth and Happiness

This tweet has been making the rounds again the last few days. It pokes good fun at the modern propensity to overuse the phrase 'exponential growth', especially in situations that aren't exponential at all. This usage has even invaded the everyday speech of many of my scientist friends, and I'm probably guilty more than I'd like to admit.

In The Day I Became a Millionaire, David Heinemeier Hansson avoids this error when commenting on something he's learned about wealth and happiness:

The best things in life are free. The second best things are very, very expensive. -- Coco Chanel
While the quote above rings true, I'd add that the difference between the best things and the second best things is far, far greater than the difference between the second best things and the twentieth best things. It's not a linear scale.

I started to title this post "A Power Law of Wealth and Happiness" before realizing that I was falling into a similar trap common among computer scientists and software developers these days: calling every function with a steep end and a long tail "a power law". DHH does not claim that the relationship between cost and value is exponential, let alone that it follows a power law. I reined in my hyperbole just in time. "A Non-Linear Truth ..." may not have quite the same weight of power law academic-speak, but it sounds just fine.

By the way, I agree with DHH's sentiment. I'm not a millionaire, but most of the things that contribute to my happiness would scarcely be improved by another zero or two in my bank account. A little luck at birth afforded me almost all of what I need in life, as it has many other people. The rest is an expectations game that is hard to win by accumulating more.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Personal