Every article about productivity is either crappy or excellent. If it’s excellent, I read it all the way through in order to absorb every detail about how I can get more things done—in doing so, I get nothing done. If, however, the article sucks, then I quit reading it immediately and go work on something I care about.
For me, then, good articles about productivity are usually counter to my productivity, and crappy articles are helpful. I’m so disgusted with them that I can’t help but want to work on something to counteract the time I lost by starting to read them.
Therefore, bloggers, please write more crappy productivity articles, so I can get shit done.
08 October 2011
Regexes Parse XML Just Fine, Actually
Despite what you may believe, or may have heard from a particular famous Lovecraftian answer on Stack Overflow, you can actually use regular expressions to parse arbitrary XML. Of course, they’re not regular expressions in the strict mathematical sense, but rather in the sense with which most of us are familiar—Perl regexen.
This relies on a seemingly little-known but tremendously handy feature of Perl regular expressions:
The only bit you can’t do in the regular expression engine itself is assert that the names of two matching tags are equal, because you can’t match backreferences in recursive submatches. This isn’t a problem if you assume your input is well-formed. I’m talking about parsing XML, not checking whether some input actually is XML. Correctness is a Boolean, after all: invalid XML is not XML.
I wrote a quick Perl script to demonstrate this using a number of test strings, both those well formed and those less than perfect. This was in part because I feel like doing “impossible” things lately, and in part because I wanted to brush up on my Perl. The point of it is not to be a good solution, but rather the opposite: there is a certain joy in getting something to work in completely the wrong way.
Anyway, the body of it goes like this:
This recursively enumerates all tags and their contents in some rough semblance of hierarchical order:
I’m admittedly unsure of whether the rules involving lookahead and lookbehind actually match the spec, but it was what came to mind. The rules in question are
I would call this a good (okay, slow and overspecified, but still kinda neat) practical solution to a problem that’s theoretically unsolvable. That, incidentally, will be the theme of many of my upcoming posts, so stay tuned if you’re into it.
This relies on a seemingly little-known but tremendously handy feature of Perl regular expressions:
(?N) will recursively match an instance at the current position of whatever is in capture group N. This lets you recursively match delimiters, limited to a depth of 50 unless you build yourself a special Perl.The only bit you can’t do in the regular expression engine itself is assert that the names of two matching tags are equal, because you can’t match backreferences in recursive submatches. This isn’t a problem if you assume your input is well-formed. I’m talking about parsing XML, not checking whether some input actually is XML. Correctness is a Boolean, after all: invalid XML is not XML.
I wrote a quick Perl script to demonstrate this using a number of test strings, both those well formed and those less than perfect. This was in part because I feel like doing “impossible” things lately, and in part because I wanted to brush up on my Perl. The point of it is not to be a good solution, but rather the opposite: there is a certain joy in getting something to work in completely the wrong way.
Anyway, the body of it goes like this:
my $element = qr{ ( $STag ( $CharData? (?: $Reference | $CDSect | $PI
| $Comment | (?1) )* $CharData? ) $ETag ) }sx;
# ^
# The morsel that matches $element recursively.
my @stack = '<html><head><title>Title</title></head><body><h1>Lies.</h1>'
. '<p><i>You</em>, my friend, have been told them.</p></body></html>';
$" = "\n\n";
while (@stack) {
my $string = shift @stack // '';
my @groups = $string =~ m/$element/g;
print "@groups\n\n" if @groups;
unshift @stack, map {
s/^<($Name)(?:$S*$Attribute)*$S?>//; my $a = $1;
s/<\/($Name)$S*>$//; my $b = $1;
$a eq $b ? $_ : undef
} @groups;
}
This recursively enumerates all tags and their contents in some rough semblance of hierarchical order:
<html>…</html><head>…</head><body>…</body><head>…</head><title>…</title><body>…</body><h1>…</h1><p>…</p><h1>…</h1>Lies.<p>…</p><i>…</em>, my friend, have been told them.<i>…</em>You<title>…</title>Title
<![CDATA[...]]>, and all that other fun stuff.I’m admittedly unsure of whether the rules involving lookahead and lookbehind actually match the spec, but it was what came to mind. The rules in question are
$CData, $CharData, $PITarget, $PI, and $Comment (but they seem to work okay from what little testing I’ve done).
#!/usr/bin/perl
use warnings;
use strict;
my $S = qr{ \x20 | \x09 | \x0D | \x0A }x;
my $NameStartChar = qr{ : | [A-Z] | _ | [a-z] | [\xC0-\xD6] | [\xD8-\xF6]
| [\xF8-\x{2FF}] | [\x{370}-\x{37D}] | [\x{37F}-\x{1FFF}]
| [\x{200C}-\x{200D}] | [\x{2070}-\x{218F}] | [\x{2C00}-\x{2FEF}]
| [\x{3001}-\x{D7FF}] | [\x{F900}-\x{FDCF}] | [\x{FDF0}-\x{FFFD}]
| [\x{10000}-\x{EFFFF}] }x;
my $NameChar = qr{ $NameStartChar | - | \. | [0-9] | \xB7
| [\x{0300}-\x{036F}] | [\x{203F}-\x{2040}] }x;
my $Char = qr{ \x09 | \x0A | \x0D | [\x20-\x{D7FF}] | [\x{E000}-\x{FFFD}]
| [\x{10000}-\x{10FFFF}] }x;
my $Name = qr{ $NameStartChar $NameChar* }x;
my $EntityRef = qr{ & $Name ; }x;
my $CharRef = qr{ % $Name ; }x;
my $Reference = qr{ $EntityRef | $CharRef }x;
my $AttValue = qr{ " (?: [^<&"] | $Reference )* " }x;
my $Attribute = qr{ $Name $S? = $S? $AttValue }x;
my $STag = qr{ < $Name (?: $S* $Attribute )* $S? > }x;
my $ETag = qr{ </ $Name $S? > }x;
my $CDStart = qr{ <!\[CDATA\[ }x;
my $CDEnd = qr{ \]\]> }x;
my $CData = qr{ (?<! $CDEnd ) $Char* (?! $CDEnd ) }x;
my $CharData = qr{ (?<! $CDEnd ) [^<&]* (?! $CDEnd ) }x;
my $CDSect = qr{ $CDStart $CData $CDEnd }x;
my $PITarget = qr{ (?! [Xx][Mm][Ll] ) $Name }x;
my $PI = qr{ <\? $PITarget (?: $S (?: (?<! \?> ) $Char* (?! \?> )))? \?> }x;
my $Comment = qr{ <!-- (?: (?: (?! - ) $Char ) | (?: - (?! - ) $Char ) )*
--> }x;
my $element = qr{ ( $STag ( $CharData? (?: $Reference | $CDSect | $PI
| $Comment | (?1) )* $CharData? ) $ETag ) }sx;
my @stack = '<html><head><title>Title</title></head><body><h1>Lies.</h1>'
. '<p><i>You</em>, my friend, have been told them.</p></body></html>';
$" = "\n\n";
while (@stack) {
my $string = shift @stack // '';
my @groups = $string =~ m/$element/g;
print "@groups\n\n" if @groups;
unshift @stack, map {
s/^<($Name)(?:$S*$Attribute)*$S?>//; my $a = $1;
s/<\/($Name)$S*>$//; my $b = $1;
$a eq $b ? $_ : undef
} @groups;
}
I would call this a good (okay, slow and overspecified, but still kinda neat) practical solution to a problem that’s theoretically unsolvable. That, incidentally, will be the theme of many of my upcoming posts, so stay tuned if you’re into it.
06 October 2011
Correctness is a Boolean
The most misleading thing about the way programming is taught is how programs are graded. Students are used to receiving a score that represents the sum of the correct parts of an assignment. You can think of it start as starting with a zero and earning points up to a maximum of 100, or as starting with 100 and losing points from there. As for me, I prefer to simply avoid thinking about it.
But when it comes to software, this kind of grading makes almost no sense whatsoever. Especially in the imperative languages that are generally taught to beginning students of programming, the effect of a statement depends crucially on the effects of the statements preceding it, and not just lexically, but temporally.
An error in a single line of a program is not necessarily local to that line, but more likely has effects that propagate forward in time or outward in an expression to cause further errors. By grading programs subjectively according to how many of the statements seem appropriately designed and sequenced, teachers influence students to treat programs as though their objective correctness is dependent on the mere sum of the subjective correctness of their parts.
Beginning programmers often have difficulty thinking above the level of individual statements in order to develop a high-level understanding of program structure and meaning. Professors don’t need to further their confusion by giving them a skewed representation of what makes a program right.
A program ought to be like a proof: a single flaw, and it’s not correct. “Correct” means that it does everything it ought to, and nothing it oughtn’t. That says nothing about the amount of work required to make an incorrect program correct, because that’s entirely subjective; it could be a difference as small as a single character, or as great as the entire program. The changes needed are not necessarily local to individual statements, nor even comprehensible at the statement level.
That’s why, if I ever end up teaching programming, I’ll grade my assignments on the basis of correctness and subjective style separately, and draw a clear distinction between the two. If your program is correct, you’re guaranteed a passing grade. All the points beyond that you gotta earn by writing elegantly. It’s only fair.
But when it comes to software, this kind of grading makes almost no sense whatsoever. Especially in the imperative languages that are generally taught to beginning students of programming, the effect of a statement depends crucially on the effects of the statements preceding it, and not just lexically, but temporally.
An error in a single line of a program is not necessarily local to that line, but more likely has effects that propagate forward in time or outward in an expression to cause further errors. By grading programs subjectively according to how many of the statements seem appropriately designed and sequenced, teachers influence students to treat programs as though their objective correctness is dependent on the mere sum of the subjective correctness of their parts.
Beginning programmers often have difficulty thinking above the level of individual statements in order to develop a high-level understanding of program structure and meaning. Professors don’t need to further their confusion by giving them a skewed representation of what makes a program right.
A program ought to be like a proof: a single flaw, and it’s not correct. “Correct” means that it does everything it ought to, and nothing it oughtn’t. That says nothing about the amount of work required to make an incorrect program correct, because that’s entirely subjective; it could be a difference as small as a single character, or as great as the entire program. The changes needed are not necessarily local to individual statements, nor even comprehensible at the statement level.
That’s why, if I ever end up teaching programming, I’ll grade my assignments on the basis of correctness and subjective style separately, and draw a clear distinction between the two. If your program is correct, you’re guaranteed a passing grade. All the points beyond that you gotta earn by writing elegantly. It’s only fair.
28 September 2011
How to Be Productive
Blindingly Obvious Truths
This is how to be productive. Most of these things are absurdly, staggeringly obvious. That’s kinda my style. Anyway, since not very many of us are the kind that get shit done, we apparently need to be reminded every once in a while. Pin this to your wall—pin it to all of your walls—and look at it to give yourself a mental kick in the ass when you know you should be working.
Get out of bed.
If, like me, you have delayed sleep phase syndrome, then fix it. If it’s hard to get up when the sun comes up, then your sleep schedule is probably not healthy, and it is negatively affecting your productivity. We are a diurnal species. Deal with it.
Be healthy.
It ought to go without saying that you need good diet and exercise habits to be healthy. What you may not realise is that health is happiness, and for many of us, happiness is productivity. (I can’t say all, because surely there are some dark tormented programmers out there whose work is fueled by the darkness and torment in their dark tormented souls of tormentful darkfulness. Or something.)
For instance, when my blood sugar is low, I hate the world—then I eat a sandwich and everything’s fine. If you feel like hell all the time, your body is probably trying to tell you something. Sleep right, eat well, exercise occasionally, spend time with friends, find a mate, and mate with them often.
Work on one thing.
Multitasking is doing many things at once—badly. Innumerable studies have shown that multitaskers are just fooling themselves into believing they’re improving their productivity. You can be a true “jack of all trades” if you work on one thing at a time. Don’t distract yourself from what you’re working on with thoughts of what you’re not working on. It’s an endless cycle of self-subversion that can only be broken with focus.
If I want to write a blarticle, I just do it. If I need to do homework, I just—well, okay, first I complain a lot, but then I just do it. I didn’t post a vlog entry for months, and then I said “no, this will not do” and made something. It was shitty. It doesn’t matter. I did it.
Work till you’re done.
Have a project that needs finishing? Don’t waste your valuable time making small changes. Get your hands dirty and implement that feature you want. No one else is going to do it, and you have the time. It probably won’t even be as hard as you think. If it seems guaranteed to be difficult, you might be fixating on a difficult solution when there is a much simpler one. Reflect.
When you’re done, stop.
You must take time to relax and play. If you work hard, you earn the right to relax hard. You will feel the profound satisfaction that comes from creating something through your own focused efforts, and your sleep will be easy and deep.
Now go, and do.
This is how to be productive. Most of these things are absurdly, staggeringly obvious. That’s kinda my style. Anyway, since not very many of us are the kind that get shit done, we apparently need to be reminded every once in a while. Pin this to your wall—pin it to all of your walls—and look at it to give yourself a mental kick in the ass when you know you should be working.
Get out of bed.
If, like me, you have delayed sleep phase syndrome, then fix it. If it’s hard to get up when the sun comes up, then your sleep schedule is probably not healthy, and it is negatively affecting your productivity. We are a diurnal species. Deal with it.
Be healthy.
It ought to go without saying that you need good diet and exercise habits to be healthy. What you may not realise is that health is happiness, and for many of us, happiness is productivity. (I can’t say all, because surely there are some dark tormented programmers out there whose work is fueled by the darkness and torment in their dark tormented souls of tormentful darkfulness. Or something.)
For instance, when my blood sugar is low, I hate the world—then I eat a sandwich and everything’s fine. If you feel like hell all the time, your body is probably trying to tell you something. Sleep right, eat well, exercise occasionally, spend time with friends, find a mate, and mate with them often.
Work on one thing.
Multitasking is doing many things at once—badly. Innumerable studies have shown that multitaskers are just fooling themselves into believing they’re improving their productivity. You can be a true “jack of all trades” if you work on one thing at a time. Don’t distract yourself from what you’re working on with thoughts of what you’re not working on. It’s an endless cycle of self-subversion that can only be broken with focus.
If I want to write a blarticle, I just do it. If I need to do homework, I just—well, okay, first I complain a lot, but then I just do it. I didn’t post a vlog entry for months, and then I said “no, this will not do” and made something. It was shitty. It doesn’t matter. I did it.
Work till you’re done.
Have a project that needs finishing? Don’t waste your valuable time making small changes. Get your hands dirty and implement that feature you want. No one else is going to do it, and you have the time. It probably won’t even be as hard as you think. If it seems guaranteed to be difficult, you might be fixating on a difficult solution when there is a much simpler one. Reflect.
When you’re done, stop.
You must take time to relax and play. If you work hard, you earn the right to relax hard. You will feel the profound satisfaction that comes from creating something through your own focused efforts, and your sleep will be easy and deep.
Now go, and do.
27 September 2011
Simulation is Abstraction is Power
A more abstract programming language is more powerful. This is one of precious few things that most software developers agree on. C is more powerful than assembly, C++ is more powerful than C, and Lisp is more powerful than most developers realise—or will ever take advantage of. And that’s fine.
But whence cometh abstraction? Sure, you can say that all abstractions are generalisations of some category of operations or structures, but that’s shallow and basically useless. There’s more to it.
Abstraction comes from simulation. Computers run simulations of idealised computation; more abstract languages are better at simulating the ideal. Low-level languages deal with real hardware, while high-level languages simulate ideal hardware. A few examples:
(Depending on how far you want to go with the analogy, recursion simulates a whole bunch of things, including self-reference, fractal structure, and induction.)
Simulation is about removing dependency. A program can depend on manual memory management, but it cannot, by definition, depend on garbage collection. With memory management fully abstracted away, memory management ought to be a nonexistent concept from the perspective of the language.
Your program probably pretends it has infinite memory anyway. Provided your program doesn’t crash, the system does have unbounded memory as far as you know. Most programs that are working properly don’t run out of memory unless they’re deliberately designed to, for lack of a better phrase, fuck shit up.
Similarly, as we all know, threads may actually run on separate cores, and thus truly in parallel—that’s sorta the point. But the thing about a language that offers powerful abstractions for parallelism is that you don’t need to care. It’s taken care of. As far as you need to know, the system can perform an infinite number of computations at once.
Abstractions are (imperfect) simulations of limitlessness. As a language designer, you can (and should) offer pragmatic limitations and safeguards for the benefit of the fallible developer. But to make a more powerful language, you must remove limitations. When you do so, you discover the nature of the underlying simulation—and simulation is abstraction is power.
But whence cometh abstraction? Sure, you can say that all abstractions are generalisations of some category of operations or structures, but that’s shallow and basically useless. There’s more to it.
Abstraction comes from simulation. Computers run simulations of idealised computation; more abstract languages are better at simulating the ideal. Low-level languages deal with real hardware, while high-level languages simulate ideal hardware. A few examples:
- References simulate unstructured memory.
- Garbage collection simulates unbounded memory.
- Dynamic typing simulates lack of typing.
- Threads simulate parallel execution.
- Tail recursion simulates unbounded recursion.
(Depending on how far you want to go with the analogy, recursion simulates a whole bunch of things, including self-reference, fractal structure, and induction.)
Simulation is about removing dependency. A program can depend on manual memory management, but it cannot, by definition, depend on garbage collection. With memory management fully abstracted away, memory management ought to be a nonexistent concept from the perspective of the language.
Your program probably pretends it has infinite memory anyway. Provided your program doesn’t crash, the system does have unbounded memory as far as you know. Most programs that are working properly don’t run out of memory unless they’re deliberately designed to, for lack of a better phrase, fuck shit up.
Similarly, as we all know, threads may actually run on separate cores, and thus truly in parallel—that’s sorta the point. But the thing about a language that offers powerful abstractions for parallelism is that you don’t need to care. It’s taken care of. As far as you need to know, the system can perform an infinite number of computations at once.
Abstractions are (imperfect) simulations of limitlessness. As a language designer, you can (and should) offer pragmatic limitations and safeguards for the benefit of the fallible developer. But to make a more powerful language, you must remove limitations. When you do so, you discover the nature of the underlying simulation—and simulation is abstraction is power.
Subscribe to:
Posts (Atom)