| Seek and you will find |
[May. 29th, 2008|10:50 am] |
This post is a mea culpa, an admission of failure: if any of you have read my stuff thinking that I know what I'm talking about when it comes to programming, this is your chance to recalibrate. I'm posting in the hopes that by writing this particular ultra-basic technique down in public, I'll never ever ( forget about it )
[The full, working version of PS3 Remuxatron (by Mat Brown, GPLed) is here.] |
|
|
| Lazy lists, impatience and hubris |
[May. 16th, 2008|12:12 pm] |
There was a recent mailing list post by Andrew Coppin (which received some discussion on programming.reddit) in which he bemoans the way that GHC, when presented with reasonable-looking code, can suddenly and mysteriously decide that it needs to allocate gigabytes of memory, slowing your system to a crawl for ages (I've had similar problems myself). Andrew's example was the following: I offer up the following example:mean xs = sum xs / length xs Now try, say, mean [1.. 1e9], and watch GHC eat several GB of RAM. (!!) This is not so mysterious when you remember that Haskell uses linked lists as its native list structure, and so the only way to calculate length xs is to traverse the list a second time: the runtime system "helpfully" keeps around the copy of xs that it generated while calculating sum xs, and you have a space leak. But what to do about it?
( The story so far )
( Doing it in Perl )
( Doing it in Ruby )
( Take-home messages ) |
|
|
| Why I like Perl |
[Apr. 28th, 2008|12:18 am] |
I wrote this in an email to a colleague of totherme's a while back, and have occasionally felt the need to refer to it since. Fortunately, I have a place where I can post my ill-informed ramblings for all the world to see, so here it is :-) It's an attempt to convince a computer scientist, who I believe comes from the Haskell/static typing camp, why Perl is worth learning.
[If you're not a computer scientist, the two chief reasons to learn Perl are (1) it's incredibly useful, (2) it's great fun. But I digress.]
In many ways, Perl occupies the opposite corner of design-space to Haskell. To a first approximation, Haskell proceeds from the question "what if everything we think we know about language design is right?", whereas Perl proceeds from the question ( what if everything we think we know about language design is wrong? ) |
|
|
| Better living through shell scripting |
[Mar. 28th, 2008|03:31 pm] |
As I may have mentioned once or twice before, I'm writing up my thesis. This is an intensely slow and depressing process, and the temptation to slack off is overwhelming. Being a geek, I decided to write some code to help me. Writing code rather than writing thesis is still slacking off, obviously, but it's slacking off to a useful end. Writing blog posts about writing code that's meant to help me write my thesis is another matter...
( Read more... ) |
|
|
| Template Haskell, argument munging and operads, part I |
[Mar. 5th, 2008|10:37 am] |
[The hope was that this post would come in three somewhat independent sections: one pure programming, in which we develop a small utility in Template Haskell; one largely mathematics, at the upper-level high school to beginning undergraduate level, wherein we describe another approach to constructing our utility; and one purely mathematical, more sophisticated but fairly handwavy, wherein I relate all this stuff to my research interests and describe where it leads. The idea was that you could skip the code and jump to the maths, or read the code and skip the maths, or whatever. However, just the first section has now taken far longer than I'd budgeted, both in time and in space, so I'll save the other two for a later post.]
In a recent post, Hitesh Jasani writes about Haskell's flip operator, which takes a function f and returns a function which behaves like f with the order of its first two arguments reversed. So (flip f) x y z w = f y x z w (we write function application without brackets, as is customary in Haskell). I pointed out to Hitesh that actually, we could write such a function in almost any language which supports higher-order functions, and in dynamic languages (like Perl or Lisp) we can go further, and write a function argmunge, which accepts two functions and permutes the arguments of the first one (the "victim") according to the second (the "munger"). So (argmunge f g) x1 x2 x3 x4 ... = f xg 1 xg 2 xg 3 xg 4 ... Here's an implementation of argmunge in Perl, and some code to exercise it:sub argmunge {
my $func = shift;
my $munger = shift; # not necessarily a permutation
return sub { $func->(@_[@$munger]); }
}
sub myprint {
print "Called with args ".join(", ", @_)."\n";
}
argmunge(\&myprint, [2,5,5,6])->(0,1,2,3,4,5,6);
argmunge(\&myprint, [3,2,1])->("fred", "barney", "betty", "wilma"); When run, this displays Called with args 2, 5, 5, 6
Called with args wilma, betty, barney Here we don't pass the munger in as a function, but rather as a list of values [g(0), g(1), ..., g(n)]. I'm prouder of that code than I probably should be, because it relies on some nice Perl features to work as it does; namely, Perl's argument-passing convention (in which all arguments are passed to a function as a single array called @_), list slicing (in which you can index into a list with another list), and list flattening (in which inclusion of one list in another splices the inner list into the outer list, resulting in a flat list). I remarked that it wouldn't be possible to write a general argmunger in Haskell, because the type of the result depends crucially on the actual value of the munging function. It ought to be possible to write one in a dependently-typed language like Cayenne - anyone care to do so?
[Edit: it's possible to write an even nicer version in Arc.]
Anyway, it may not be possible in vanilla Haskell, but ( it is possible using templates. )
The final code can be found here. As always, all suggestions for how I could improve my code or my development practices are gratefully received! |
|
|
| Onageristic speculation |
[Feb. 12th, 2008|10:26 am] |
| [ | Tags | | | apl, beware the geek, computers, haskell, j, language, lisp, maths, perl, programming, smalltalk, type systems | ] |
I'm going to make what should be an uncontroversial statement: if you don't understand and use monads, you are at best a quarter of a Haskell programmer. A corollary of this is that, since using monad transformers is the only (or at least the approved) way to use two or more monads together, if you don't understand and use monad transformers you are at best half a Haskell programmer.
[Another corollary is that I am, at best, about an eighth of a Haskell programmer: though I understand monads well on a theoretical level, I invariably emerge defeated from any attempt to bend them to my will.]
But we'll come back to that later.
Something I've been thinking about for a while is this whole business of ( designing languages to make programs shorter. )
1 There really ought to be a word that means "would never use a twopenny word when a half-crown word would do", but I can't think of one. English grads? Edit: sesquipedalian! Of course! Thanks, fanf! (Originally, I used "prolix") 2 I actually came up with this list by thinking about languages whose users were the most passionate. But they're also extremely concise, which I think is a large part of the reason for the passion. If I were focusing purely on concision, I should probably consider Forth, but I don't know enough about it. 3 J has "boxed arrays" too, which are something like two-dimensional s-expressions, but let's leave those aside for now. 4 You might want to raise this objection against Smalltalk, too: objects are members of classes, which are something like types. Now, I've hardly used Smalltalk, so I'm probably talking out of my elbow, but: since everything is an object, and the language has powerful reflection features and duck typing, we can in fact write generic operators that work for objects of many or all classes. But maybe I'm entirely wrong about Smalltalk programming: in which case, please delete all references to the language from my argument. 5 Do you find yourself wanting to go out and strangle small fluffy animals every time you have to type out an instance declaration that would be entirely unnecessary in a duck-typed language? I do. Particularly when it doesn't work and spits out some ludicrous error message at me, telling me that I've encountered another stupid corner case of the typeclass system. 6 I learned to my surprise the other day that I'm a member of the Geometry and Topology research group, and not the algebra research group as I'd always assumed - apparently universal algebra is now considered a branch of geometry!
|
|
|
| Code-walking in Arc |
[Feb. 5th, 2008|02:35 am] |
totherme kindly drew my attention to this blog post today. The author, Slava Akhmechet, tries to explain away that horrible feeling of unproductivity and frustration that I know so well from my attempts to use Haskell: his claim is that it's just that my expectations are miscalibrated from using imperative languages. A Haskell solution to a given problem, he claims, will take the same amount of thought as a solution in another language, but much less typing: by simple statistics, therefore, you're going to spend a lot of time staring at the screen not doing anything visible, and this can feel very unproductive if you're not used to it.
As an example, he gives the codeextractWidgets :: (Data a) => a -> [String]
extractWidgets = nub . map (\(HsIdent a)->a) . listify isWidget
where isWidget (HsIdent actionName)
| "Widget" `isSuffixOf` actionName = True
isWidget _ = FalseBleh! :-( This function takes a parse tree representing some Haskell code, and extracts all the identifiers ending in "Widget", then removes the duplicates. Slava challenges any Java programmers reading to do the same in five lines or fewer.
( Pointless language pissing match, including some Arc coding )
On language concision in general: I typically find that Haskell requires fewer lines for a given program, but Perl requires fewer characters, and they both use about the same number of tokens. Lisp is longer and messier than Haskell for easy problems, but quickly gains ground as the problems get harder.1 The APL family own on all three axes. This is extremely unscientific, of course, and because I don't know much APL/J I can't be sure how it extends to harder problems. I did once email Paul Graham asking why, if succinctness was power, he didn't switch to a member of the APL family; he has yet to reply, but I don't attach any great significance to this.
And having got all that stuff out of my head, I'm going back to bed. Hopefully I'll be able to sleep this time :-)
1Fun exercise: translate the example code in On Lisp into Haskell (or Perl, Ruby, etc.). It really helps you to get to grips with the material in the book. I found that the Haskell solutions were shorter and cleaner than the Lisp solutions up until about a third of the way through the book, at which point Lisp started to catch up with a vengeance: shortly thereafter, he was doing things in a few lines of Lisp that simply couldn't be done in finitely many lines of Haskell. I'd be very interested to see solutions written by someone who knew what they were doing, though! |
|
|
| Hasskellsses |
[Jan. 23rd, 2008|04:11 pm] |
Bloody Haskell: it's like a scab I can't stop picking at.
Prompted by something on Reddit, I started thinking about libraries to pluralize (English) words, like the table-name generator in Ruby on Rails or Damian Conway's (rather more complete-looking) Lingua::EN::Inflect for Perl. Such things seem to be called "inflectors". My question is, what would be the idiomatic interface for a Haskell inflector? The obvious thing would be something like pluralize :: Inflector -> String -> String where Inflector is some sort of data structure holding configuration data: classical versus modern plurals, any custom cases, etc. But following on from our earlier discussion of high- and low-level type-checking, it occurred to me that there's a constraint here: only singular nouns should be pluralized. So should we then have newtype Singular = String
newtype Plural = String
pluralize :: Inflector -> Singular -> Plural? Or even module Inflect (makeSingular, pluralize)
data Singular = Singular String
data Plural = Plural String
makeSingular :: String -> Singular
-- error-checking code goes here, to check that the string passed
-- is a single word, or something
pluralize :: Inflector -> Singular -> Plural so we don't export the constructors for Singular or Plural, ensuring that one can only construct them using our interface? But wouldn't this make client code far uglier than necessary? Should one then provide both options, tagging one as unsafe? module Inflect (makeSingular, pluralize, unsafePluralize)
data Singular = Singular String
data Plural = Plural String
makeSingular :: String -> Singular
-- error-checking code goes here
unsafePluralize ::Inflector -> String -> String
pluralize :: Inflector -> Singular -> Plural
pluralize i (Singular s) = Plural (unsafePluralize i s)Thoughts? |
|
|
| (no subject) |
[Jan. 17th, 2008|02:54 pm] |
Here's something I've been wondering about for ages. When I'm programming, I find worrying about the types of variables to be generally unhelpful, and being forced to think about such things by the compiler is downright irritating. Yet when I'm doing mathematics, I think type-centrically all the time. The two activities are strongly connected in my mind, so it's surprising to me that there's this difference.
Here are some ( theories I've been kicking around )
By the way, remember a while ago when I was musing on the possibility of static duck-typed languages? Well, it seems that Scala is one :-) |
|
|
| In praise of implementation-defined languages |
[Oct. 1st, 2007|09:18 pm] |
Implementation-defined languages come in for a lot of flak. Users of certain languages will point to their language's standards document as if it were self-evidently proof of greater inherent worth: a language that's defined by its implementation, it is implied, is always going to be a bit non-U. It may train itself out of its dropped H's and tendency to mispronounce the word "scone"1, but it will never have the true breeding that comes from a standards document.
Which is daft, because implementation-defined languages ( have some important advantages )
By the way, I'm not saying that all specifications are bad (a good one is an excellent thing to have) or that specification-defined languages have no advantages - I'm assuming that the advantages of specification-defined languages are so well-rehearsed that I don't need to repeat them. Anyone needing further enlightenment is encouraged to go to comp.lang.scheme and say "I think spec-defined languages suck!" :-)
Now for the second part of my rant: Haskell, as we know it today, is an implementation-defined language, defined by the latest CVS snapshot of GHC. "But what about the Haskell Report, and the Revised Report, and Haskell prime, and Hugs, and, er, those other implementations?" I hear you cry. Well, what about them? Every time I asked some question, it seemed, the answer would begin with "first download the latest version of GHC, then turn on these extensions..." A spec for a language that people don't actually use is - well, not useless, if it's sufficiently close to a language that they do use, but it ain't a specification as I understand the term. Everyone in the Haskell community seems to track the latest version of GHC for its new features. This is not spec-like behaviour. Now, as I said above, I don't think that implementation-defined languages are bad: quite the reverse. I just think it would save everyone a lot of bother and false superiority if the community could admit this to itself and to outsiders.
1 The O is short: "scone" rhymes with "gone", not "groan". Unless you're talking about the town in Scotland, when it rhymes with "boon". People who insist on mispronouncing this word around me will have their scones taken away from them and donated to the Pozorvlak Pedant-Feeding Drive. |
|
|
| Fun combinatorial problem |
[Sep. 20th, 2007|04:09 pm] |
This morning, I got an email from (of all things) a pianist, which had been relayed to the department at large by the Head of Department. He was trying to develop a more rigorous warm-up routine for pianists. Specifically:One of my exercises involves fingers 1-2-3-4. To succeed in playing smoothly at the piano, and to produce equality in the fingers, the following rules must be observed (each 'rule' has a direct technical application at the piano):
each combination must be 6 digits long ; the same number can be used more than once, but never consecutively ; all 4 numbers must be used at least once ; and the combination must not end on 1 or 2.
I have tried my best to work out the possibilities (I have around 30 so far), but I know there must be an equation for this. I just can't see it! You may like to have a go at this yourself: once you've done that, ( here's the email I sent him back )
For maximum points, provide a combinatorial argument establishing the number of such sequences, and an algorithm to enumerate them all. Bonus points if your algorithm traverses the space of warmup sequences in a manner that can be used by the pianist without resort to memorising vast numbers of sequences :-) |
|
|
| The private life of the gerund |
[May. 16th, 2007|09:32 am] |
The relationship between human languages and programming languages is interesting to me. In general, programming languages are a lot simpler (which is great, because it makes it easier to learn lots of them): they also have rather less vocabulary (but that's OK, because you're actively encouraged to make up your own). We talk about programming "idiomatically": while it's often possible to use one language's idioms in another, they can look almost as odd as, say, Japanese idioms used in English. In the evolution of programming languages, you can see a super-compressed version of the evolution of human languages: ideas, grammatical forms, and vocabulary transfer from one language to another where there's contact between the two communities, and languages split into mutually-unintelligible descendants when the communities fracture. There's at least one example of creolization that I'm aware of: the programming language Perl can be considered a creole of C, shell, sed and awk (and has since absorbed features from many other languages). Perl's also been heavily influenced by that other notable creole, English, and incorporates several features from human languages (like topicalization). It's no coincidence that Larry Wall, the original creator of Perl, studied linguistics at graduate school. In the opposite direction, you'll sometimes hear hackers describing human languages in terms derived from programming languages: Japanese is sometimes said to use reverse Polish notation.
But as I said, programming languages tend to be a lot simpler than human languages. In fact, so-called object-oriented languages (like, say, Java) have been described (perhaps "derided" is a better term) as languages in which everything is a noun: dually, so-called functional languages (like Haskell) could be described as languages in which everything is a verb. Actually, verbs and nouns cover pretty much everything in most programming languages. Perl has pronouns and conjunctions, and pronouns can be added to Lisp with sufficient cleverness; a couple of languages have something vaguely resembling adverbs.
So you can imagine my pleasure at learning yesterday that the language called J has gerunds :-)
*downloads J interpreter*
 Fig. 1: The gerund attacks some peaceful pronouns (image courtesy n. molesworth) |
|
|
| (no subject) |
[May. 3rd, 2007|11:30 am] |
The other day I went to the highlands with Michael, a frequent walking partner, and his flatmate Jo. Jo had a shiny new car, which among its other whizzinesses had a "Start" button, rather like the Batmobile: unfortunately, it didn't have a fake "Start" sign that flicked down over the "Ejector Seat" button. What it did have, however, was a clever system that turned the lights off when you switched off the engine. "I don't think I could go back to another car, now," said Jo, "I'd be forever leaving the lights on and running down the battery. My last car used to beep if the lights were left on, but this is much better."
Naturally, this reminded me of Haskell. Haskell is a language that beeps when you leave the lights on; Perl just switches them off. Having got used to the latter, I'm forever leaving the lights on and getting beeped at :-( |
|
|
| Originality considered difficult |
[Apr. 17th, 2007|01:31 pm] |
About a month ago, wormwood_pearl and I went to see the fantastic stand-up comedian Daniel Kitson (who you should all go and see if the slightest opportunity presents itself). One thing that he said really struck me:If you ever think you've had an original thought, put it in quotation marks and type it into Google. Now that's a humbling experience. So I really shouldn't have been surprised when I found out that someone else had already gone ahead with my idea to extend TeX with OCaml. You can get OCamlTeX here. Somewhat to my surprise, it's based on PerlTeX, which allows you to extend TeX using Perl, writing the bodies of your macros in Perl code. For example, \perlnewcommand{\reversewords}[1]{join " ", reverse split " ", $_[0]} defines a macro that reverses the words in its arguments (not at all easy in raw TeX). I'm not entirely sure (the Perl's less than entirely clear, and the TeX is completely beyond me), but it seems to work by setting up intermediate files to communicate between a perl process and a latex process: latex writes out requests to one file, perl reads them, writes the results out to another file, which latex reads and incorporates in the document. Thus there's no need to reimplement the hairy TeX lexer or macro-expander (as there would be with a preprocessor-based approach) or to rewrite the whole of TeX in Perl/OCaml (as I originally envisaged - but come on, it could be fun :-) ).
Another one for the originality-is-hard file is this article, which says a lot of the things I've been thinking about the differences between static typing and unit testing, and how they each influence development methodology. Only the author, mwh, said it back in 2004 :-(. Mwh mentions some things I hadn't thought of, like unit testing tending to make your designs more loosely coupled (because it's such a pain setting up dozens of helper objects for each test). I was particularly struck by this paragraph:As to which "side" is better, well, I'm not going to attempt an answer to that question :-) One thing to consider, though, is the side benefits of a given methodology such as the unit testing driving loose coupling. There are probably side benefits to the powerful static type system approach, too. I will notice that for sub-genius programmers, the unit test approach is probably just plain easier. This resonated with something else that I've been thinking. Kevin Barnes draws a distinction between "freedom languages" and "safety languages" - freedom languages are languages like Lisp or Perl or C, which strive to give you as much freedom as possible. The rationale for this was expressed wonderfully by chromatic: bad programmers will shoot themselves in the foot anyway, and good programmers will use the features to do things that would otherwise be impossible. Safety languages are languages that go to the opposite extreme, and make it very hard to do unsafe things, like Java or Ada. The rationale being roughly a) fewer bugs (even good programmers make mistakes), b) better automated tools. Compare this with the distinction drawn here between Languages for the Masses and Languages for Smart People. At first I thought he was talking about the same thing, but then it struck me: Haskell (and ML, etc), are Languages for Smart People that are also Safety Languages. Which makes them interesting, as most other LFSPs are Freedom Languages. This suggests the question: are there any LFMs that are Freedom Languages? Possibly Python: it's certainly an LFM (it's closely entwined with a project called Computer Programming for Everybody, will be the main programming language used on the One Laptop Per Child laptops, etc - note that I'm not saying that being an LFM is a bad thing!), and yet you can (if you're prepared to ignore the scary DEPRECATED! warnings) do most of the run-time metaprogramming and dark hackery that are more common in Ruby, Perl etc.
Re-reading the LFSP article, I notice that he's mainly concerned with abstractive power: maybe this is the distinction. Safety Languages for Smart People employ powerful abstractions, but restrict dark hackery; Freedom Languages for Smart People allow for both. Maybe the distinction is only visible above a certain level of power, like the weak and electromagnetic forces are only distinct at certain energies...
Of course, if all my "thoughts" are formed by stitching together things I read on the web, it's hardly surprising that they're not original :-) |
|
|
| What I was trying to say |
[Mar. 29th, 2007|03:19 pm] |
chromatic, in a conversation about domain-specific languages in Perl 6, put something I've been trying to say for a while into the correct words that would never quite come for me.
I can decipher and fix bad Ruby code, for example, because I know the underlying language.
You know Ruby's syntax maybe, but who says you know the domain of the business problem the code attempts to solve?
I maintain that that is much more important than syntax--and if you have undisciplined, barely-competent monkeys who cannot or will not write maintainable code, then your biggest risk is not that they might use powerful language features to do bad things that are hard to unravel.
Your biggest risk is that they will do anything. It doesn't matter what they do, if they have access to your source code. They may never know about symbol tables or run-time code evaluation or method aliasing or macros or code generation or monkey patching, but you can be sure that they'll pull a stupid trick such as writing files and reading them in line by line because they don't know how to use arrays.
They're barely competent! They're undisciplined! They're monkeys! Want to fix your coding problems? Start by getting rid of monkeys, not by complaining about powerful tools that competent developers might be able to use productively. From what I've seen, all the safety features in the world will not prevent monkeys from shooting themselves and others in the foot. Paw. Whatever. Whereas good, disciplined programmers will be able to get great mileage out of supposedly dangerous features, by using them correctly (note that "using them correctly" includes not using them in cases where it's not a good idea). I might, of course, be wrong, but this has been my experience thus far, and this is why I'm finding it such a big adjustment to come to a language community that seems to believe the opposite.
[Remember that crack I made a while ago about how, in the limit case, the "guarantees over expressivity" philosophy would lead to preferring guaranteed termination over Turing-completeness? It seems someone actually does believe that. Disclaimer: I've only skimmed the paper.]
By the way, I came across chromatic's post from Piers Cawley's post DSLs, Fluent Interfaces, and how to tell the difference, which says something I've long suspected: that this whole (embedded) DSL business is mostly just a buzzword slapped on a lot of fairly straightforward and common practices. |
|
|
| Stopping cows |
[Mar. 20th, 2007|05:35 pm] |
There's a scene in John Wyndham's marvellous Chocky where the main character asks his father "Why does a cow stop?"
What he means by this is why does a cow's intelligence stop: why are cows smart enough to escape out of an open gate, but not smart enough to see that they could lift up the latch with their noses and escape whenever they want? Why do cows hit a point where their problem-solving ability just stops dead?
I was reminded of this as I read Matthew Huntbach's essay What's Wrong with Ruby this morning. He points out that "Ruby, and the whole scripting language phenomenon is a slap in the face" for the academic language-design community of which he is apparently a part. We have been used to complaining that the programming languages we had developed were so much better than the mainstream programming languages, the only reasons they hadn’t taken off were that they weren’t developed and promoted by big companies, and that the inherent conservatism of industry restricted commercial programming to tried and trusted languages.
Yet a whole stream of new languages: Perl, PHP, Python and now Ruby, each initiated by one person as back-room projects, have been adopted for serious use and achieved many thousands of users. Unlike academically-derived languages, they have given the impression of being thrown together to meet a need without any strong underlying theoretical basis. That's right. Your languages weren't unsuccessful for the reasons you thought they were, and languages that don't meet your standards of elegance have flourished in actual use. Something you thought was necessary for a language to succeed (corporate backing) turns out not to be necessary after all. Now, let's apply your insights to the rest of your essay (which, by the way, is a perfect example of the kind of thing I was talking about in my post Tightrope Walking). Ruby et al don't have static typing, formal semantics, standards documents, or the guarantee that each object will have a class that determines its behaviour - in short, they're not academic languages - and yet thousands of bright users use them and like them. Could it be that perhaps the lack of these things isn't such a problem as you think? Might they, in fact, have advantages that you're too blind to see?
See that bit of metal attaching the gate to the fence? You might like to think about what you can do with that. |
|
|
| navigation |
| [ |
viewing |
| |
most recent entries |
] |
| [ |
go |
| |
earlier |
] |
| |
|
|