Programming

A web built on LaTeX

Posted on by John

The other day on TeXtip, I threw this out:

Imagine if the web had been built on LaTeX instead of HTML …

Here are some of the responses I got:

  • It would have been more pretty looking.
  • Frightening.
  • Single tear down the cheek.
  • No crap amateurish content because of the steep learning curve, and beautiful rendering … What a dream!
  • Shiny math, crappy picture placement: glad it did not!
  • Overfull hboxes EVERYWHERE.
  • LaTeX would have become bloated, and people would be tweeting about HTML being so much better.
  • Noooo! LaTeX would have been “standardised”, “extended” and would by now be a useless pile of complexity.

Wrapping a function in a burkha

Posted on by John

Terrific quote from Jessica Kerr via Dan North:

In an OO language you can't just pass a function around unless it's dressed in a burkha and accompanied by nouns @jessitron at #scandev

If you feel like you’re missing an inside joke, here’s an explanation.

In object oriented languages, languages that don’t simply support object oriented programming but try to enforce their vision of it, you can’t pass around a simple function. You have to pass around an object that contains the function.

Functions are analogous to verbs and objects are analogous to nouns. In contrast to spoken English where the trend is to turn nouns into verbs, OOP wraps verbs up as nouns.

“Sometimes, the elegant implementation is a function. Not a method. Not a class. Not a framework. Just a function.” — John Carmack

More posts on over-engineered software

Can regular expressions parse HTML or not?

Posted on by John

Can regular expressions parse HTML? There are several answers to that question, both theoretical and practical.

First, let’s look at theoretical answers.

When programmers first learn about regular expressions, they often try to use them on HTML. Then someone wise will tell them “You can’t do that. There’s a computer science theorem that says regular expressions are not powerful enough.” And that’s true, if you stick to the original meaning of “regular expression.”

But if you interpret “regular expression” the way it is commonly used today, then regular expressions can indeed parse HTML. This post [Update: link went away] by Nikita Popov explains that what programmers commonly call regular expressions, such as PCRE (Perl compatible regular expressions), can match context-free languages.

Well-formed HTML is context-free. So you can match it using regular expressions, contrary to popular opinion.

So according to computer science theory, can regular expressions parse HTML? Not by the original meaning of regular expression, but yes, PCRE can.

Now on to the practical answers. The next lines in Nikita Popov’s post say

But don’t forget two things: Firstly, most HTML you see in the wild is not well-formed (usually not even close to it). And secondly, just because you can, doesn’t mean that you should.

HTML in the wild can be rather wild. On the other hand, it can also be simpler than the HTML grammar allows. In practice, you may be able to parse a particular bit of HTML with regular expressions, even old fashioned regular expressions. It depends entirely on context, your particular piece of (possibly malformed) HTML and what you’re trying to do with it. I’m not advocating regular expressions for HTML parsing, just saying that the question of whether they work is complicated.

This opens up an interesting line of inquiry. Instead of asking whether strict regular expressions can parse strict HTML, you could ask what is the probability that a regular expression will succeed at a particular task for an HTML file in the wild. If you define “HTML” as actual web pages rather than files conforming to a particular grammar, every technique will fail with some probability. The question is whether that probability is acceptable in context, whether using regular expressions or any other technique.

Related post: Coming full circle

Randomized studies of productivity

Posted on by John

A couple days ago I wrote a blog post quoting Cal Newport suggesting that four hours of intense concentration a day is as much as anyone can sustain. That post struck a chord and has gotten a lot of buzz on Hacker News and Twitter. Most of the feedback has been agreement, but a few people have complained that this four-hour limit is based only on anecdotes, not scientific data.

Realistic scientific studies of productivity are often not feasible. For example, people often claim that programming language X makes them more productive than language Y. How could you conduct a study where you randomly assign someone a programming language to use for a career? You could do some rinky-dink study where you have 30 CS students do an artificial assignment using language X and 30 using Y. But that’s not the same thing, not by a long shot.

If someone, for example Rich Hickey, says that he’s three times more productive using one language than another, you can’t test that assertion scientifically. But what you can do is ask whether you think you are similar to that person and whether you work on similar problems. If so, maybe you should give their recommended language a try.

Suppose you wanted to test whether people are more productive when they concentrate intensely for two hours in the morning and two hours in the afternoon. You couldn’t just randomize people to such a schedule. That would be like randomizing some people to run a four-minute mile. Many people are not capable of such concentration. They either lack the mental stamina or the opportunity to choose how they work. So you’d have to start with people who have the stamina and opportunity to work the way you want to test. Then you’d randomize some of these people to working longer, fractured work days. Is that even possible? How would you keep people from concentrating? Harrison Bergeron anyone? And if it’s possible, would it be ethical?

Real anecdotal evidence is sometimes more valuable than artificial scientific data. As Tukey said, it’s better to solve the right problem the wrong way than to solve the wrong problem the right way.

Related posts

Teaching an imbecile to play bridge

Posted on by John

From Data and Reality:

The thing that makes computers so hard to deal with is not their complexity, but their utter simplicity. … The real mystique behind computers is how anybody can manage to get such elaborate behavior out of such a limited set of basic capabilities. The art of computer programming is somewhat like the art of getting an imbecile to play bridge or to fill out his tax return by himself. It can be done, provided you know how to exploit the imbecile’s limited talents, and are willing to have enormous patience with his inability to make the most trivial common sense deductions on his own.

Emphasis added.

The quote comes from the 1st edition, published in 1978, because that’s what I ran across. The link is to the 3rd edition, published last year.

Management principle from Dune

Posted on by John

The other day Atamert Ölçgen quoted a passage from Dune in response to something I’d posted on Google+. I haven’t read the Dune books, but the passage puts generalists in a favorable light, and since I’m something of a generalist, I’m inclined to like such quotes. Here’s the part I particularly liked. It says that the mentat must be able to say

There’s no real mystery about this at the moment. This is what we want now. It may prove wrong later, but we’ll correct that when we come to it.

Too often we act as if every decision is weighty and permanent. Of course some decisions are weighty and permanent, but most are not. Wisdom is knowing which decisions are and which are not. Sometimes it pays to not try to look too far ahead, conceding that if you’re wrong “we’ll correct that when we come to it.”

Related posts

Beethoven, The Beatles, and Beyoncé: more on the Lindy effect

Posted on by John

This post is a set of footnotes to my previous post on the Lindy effect. This effect says that creative artifacts have lifetimes that follow a power law distribution, and hence the things that have been around the longest have the longest expected future.

Works of art

The previous post looked at technologies, but the Lindy effect would apply, for example, to books, music, or movies. This suggests the future will be something like a mirror of the present. People have listened to Beethoven for two centuries, the Beatles for about four decades, and Beyoncé for about a decade. So we might expect Beyoncé to fade into obscurity a decade from now, the Beatles four decades from now, and Beethoven a couple centuries from now.

Disclaimer

Lindy effect estimates are crude, only considering current survival time and no other information. And they’re probability statements. They shouldn’t be taken too seriously, but they’re still interesting.

Programming languages

Yesterday was the 25th birthday of the Perl programming language. The Go language was announced three years ago. The Lindy effect suggests there’s a good chance Perl will be around in 2037 and that Go will not. This goes against your intuition if you compare languages to mechanical or living things. If you look at a 25 year-old car and a 3 year-old car, you expect the latter to be around longer. The same is true for a 25 year-old accountant and a 3 year-old toddler.

Life expectancy

Someone commented on the original post that for a British female, life expectancy is 81 years at birth, 82 years at age 20, and 85 years at age 65. Your life expectancy goes up as you age. But your expected additional years of life does not. By contrast, imagine a pop song that has a life expectancy of 1 year when it comes out. If it’s still popular a year later, we could expect it to be popular for another couple years. And if people are still listening to it 30 years after it came out, we might expect it to have another 30 years of popularity.

Mathematical details

In my original post I looked at a simplified version of the Pareto density:

f(t) = c/tc+1

starting at t = 1. The more general Pareto density is

f(t) = cac/tc+1

and starts at t = a. This says that if a random variable X has a Pareto distribution with exponent c and starting time a, then the conditional distribution on X given that X is at least b is another Pareto distribution, now with the same exponent but starting time b. The expected value of X a priori is ac/(c-1), but conditional on having survived to time b, the expected value is now bc/(c-1). That is, the expected value has gone up in proportion to the ratio of starting times, b/a.

The value of typing code

Posted on by John

Tommy Nicholas recently wrote a blog post advocating typing rather than copying-and-pasting code samples. I thought this was the most interesting paragraph from the post:

When Hunter S. Thompson was working as a copy boy at Time Magazine in 1959, he spent his spare time typing out the entire Great Gatsby by F. Scott Fitzgerald and A Farewell to Arms by Ernest Hemingway in order to better understand what it feels like to write a great book. To be able to feel the author’s turns in logic and storytelling weren’t possible from reading the books alone, you had to feel what it feels like to actually create the thing. And so I have found it to be with coding.

Joe Armstrong had similar advice:

Forget about the tools … buy a decent book and type in the programs by hand. One at a time thinking as you go. After 30 years you will get the hang of this and be a good programmer.

Typing code may be like riding a bicycle. I’m surprised how much more detail I see the first time I ride my bicycle over a road I’ve driven on, mostly because I’m moving slower but also because there’s an additional muscular dimension to the experience.

Another advantage to typing example code is that you’ll make mistakes, just as you will in real work. This will give you the opportunity to see what happens and to learn debugging, even though you may not appreciate the opportunity.

Top down, bottom up

Posted on by John

Toward the end of his presentation Don’t fear the Monad, Brian Beckman makes an interesting observation. He says that early in the history of programming, languages split into two categories: those that start from the machine and add layers of abstraction, and those that start from mathematics and work their way down to the machine.

These two branches are roughly the descendants of Fortran and Lisp respectively. Or more theoretically, these are descendants of the Turing machine and the lambda calculus. By this classification, you could call C# a bottom-up language and Haskell a top-down language.

Programmers tend to write software in the opposite direction of their language’s history. That is, people using bottom-up languages tend to write their software top-down. And people using top-down languages tend to write their software bottom-up.

Programmers using bottom-up languages tend to approach software development analytically, breaking problems into smaller and smaller pieces. Programmers using top-down languages tend to build software synthetically. Lisp programmers in particular are fond of saying they grow the language up toward the problem being solved.

You can write software bottom-up in a bottom-up language or top-down in a top-down language. Some people do. Also, the ideas of bottom-up and top-down are not absolutes. Software development (and language design) is some mixture of both approaches. Still, as a sweeping generalization, I’d say that people tend to develop software top-down in bottom-up languages and bottom-up in top-down languages.

The main idea of Brian Beckman’s video is that algebraic structures like monoids and monads inspire programming models designed make composition easier. This could explain why top-down languages enable or even encourage bottom-up development. It’s not as clear to me why bottom-up languages lead to top-down development.

Related post: Functional in the small, OO in the large

Eight fallacies of declarative computing

Posted on by John

Erik Meijer listed eight fallacies of declarative programming in his keynote address at YOW in Melbourne this morning:

  1. Exceptions do not exist.
  2. Statistics are precise.
  3. Memory is infinite.
  4. There are no side-effects.
  5. Schema don’t change.
  6. There is one developer.
  7. Compilation time is free.
  8. The language is homogeneous.

To put these in some context, Erik made several points about declarative programming in his talk. First, “declarative” is relative. For example, if you’re an assembly programmer, C looks declarative, but if you program in some higher level language, C looks procedural. Then he argued that SQL is not as declarative as people say and that in some ways SQL is quite procedural. Finally, the fallacies listed above correspond to things that can cause a declarative abstraction to leak.

(The videos of the YOW presentations should be available in January. I haven’t heard anyone say, but I imagine the slides from the presentations will be available sooner, maybe in a few days.)