A little knowledge gets you a long way straight to Hell
or, but what if it were a snoc-list, being functional anti-pattern the third.
A long time ago, when I was a freshman in college, I took a course on functional programming. There was a problem on the first exam involving various list operations and drawing pictures of the resulting structures. I had put no effort into learning the actual underpinnings of the list operations and was quite frustrated by anyone actually having the temerity to test me on such irrelevancies; however, as a direct consequence, I have remembered the exact interaction of conses and set-cdr!'s ever since. At least one of my coworkers never had such an experience, which led to the
following comment:
{- but would this be faster? I'm not sure how init and last are implemented:
removeTrailingSpace s =
if last s == ' ' || last s == '\n'
then removeTrailingSpace (init s)
else s
-}
to answer the question: no, there is no conceivable Haskell implementation of cons lists in which that implementation could be faster than anything.[1]
However, that (commented) code snippet was not my real point. My real point comes later in the same file, when the intrepid programmer sets off to demonstrate that, in fact, he did understand that tail recursion is a good thing:
getOneToken' :: Token -> String -> (Token, String)
getOneToken' partialToken "" = (partialToken, "")
getOneToken' partialToken (c:cs)
= if ((c == '\n') || (c == ' '))
then (partialToken, cs)
else (getOneToken' (partialToken ++ [c]) cn)
So.
My point here is not that he's doing space delimited parsing, which is a stupid way to parse data files and leads to data file that contain lines like
Rectangle ( 1 , 2 ) ( 3 , 4 )
spaces not optional. Nor is my point that if he were committed to doing that, he could have used the words function in the standard library, which breaks a line of text apart on the spaces (and which goes nicely together with the lines function, which splits a block of text apart on newlines). Nor is my point that if he wanted the exact functionality he provided, he could have written
getOneToken' = break isSpace
again, using nothing by functions from the standard library. No, my point is that in an attempt to avoid the linear space that would be used by simply consing each token character onto the token returned by the recursive call, he produced code with repeated appends that take quadratic time. Quadratic time, you say? Why, yes. Cons-list construction is right-biased, which means that append takes time linear in its left argument. In this case, with a token of length n, that works out to be:
0 + 1 + .. + n
which, as we all learned in intro CS, is on the order of n^2.
The point? This is bad code. This is not just bad code because it's unnecessary, it's bad code because it attempts to be monstrously clever and ends up being monstrously unclever. Dealing with such monstrous clevernesses turned out to be a lot of why I don't work at Aetion any more.
[1] One could hypothesize a scenario in which, first of all, one detects that the use of a list is linear (and that thus you can afford to mutate it in place) and that one also keeps a pointer to the tail of the list as well as the head, at which point one would be able to implement init and last in such a way that they took constant time. I am not aware of any language/compiler that can do even half of that.
12 diversions:
The anti-patterns you have been writing about underscore a handful of basic points about the kind and quality of programmers one encounters in the so-called Real World,™ namely:
1. The lessons of school don't generally sink in until you've had some practise, and
2. The programming classes taken in college don't generally provide enough practise for the lessons to sink in; and therefore,
3. The first several jobs a programmer takes after college involve a lot of "learn-as-you-go" programming.
There's no harm in learning as you go, and in fact I think it's an essential skill. But not all approaches to "learn-as-you-go" are created equal. The most common variety--that is both pervasive and pernicious--involves approaching every problem as a tabula rasa, and the apparent belief that reading other people's code, reading documentation, and doing some research into what others have done with problems similar to yours, are irrefutable evidence of weak sauce. The outcome is more like "hack-it-till-it-works," than "learn-as-you-go," and results in exactly the kinds of stupidity you've been pointing out:
1. Reinvented wheels, but this time, they're square,
2. Bad algorithms implemented out of ignorance of good ones,
3. Swamp Drainer's Syndrome (a.k.a., lack of global perspective on the problem).
Maybe you should collaborate with the folks over at the Daily WTF to start up a section specifically for functional languages.
well, a lot of people try to be clever, myself included, when we don't realize, reinventing the wheel badly isn't very good.
this is also true at my current internship, where i keep rewriting statistical algorithms in a WORSE manner, simply because i didn't realize someone better had implemented them already.
In re: Jarvis's comments.
It's worth starting by mentioning that these people are not starting to learn FP in college or even interns. In fact, the only intern I worked with was significantly more competent, even while reinventing wheels. These code samples come from people being paid to set the technical direction of the company.
I think that's important because for me, at least, it implies a different set of expectations. For example, I still remember the story of the guys in CS 18 who were implementing a problem that could be solved in one line of breadth-first search with a rather complex back-tracking scheme. It was more work than they needed to do, and I pointed them in a different direction, but the point of the problem set was for them to learn about graph algorithms, not for them to already know the best way to do things.
On the other hand, once somebody's being paid >$100K/yr as a "Partner" and "Chief Technology Officer" and etc., I think its less acceptable to be blatantly incapable of using the technology you're supposed to be overseeing.
A final point is that the basic goals in school and the work place are different, for the most part. In academia, it's at least a little expected that you'll try at things and fail. On the other hand, when you're collecting millions of dollars of taxpayer money, I think it would at least be nice if people failed because they were trying to do hard things, not failed because they vaguely remember a Scheme class they took once and can't be bothered to ask any of the people in their office who know more about Haskell than said people ever will how to write something.
That was not a run-on sentence.
So, that's why none of these stories have come from things people wrote in CS 18, for instance. Further, none of them are highlighting Aetion's equally titanic failure to develop AI algorithms that actually do interesting things - because, at least from my understanding of AI, that's something at which titanic failure should be assumed. On the other hand, for professionals in the field, I think the behavior of cons-lists ought to be pretty well understood.
</soapbox>
Speaking of snoc-lists, I find it amusing to note that Haskell seems to support an implementation of difference-lists, though I guess perhaps it's not in the standard library.
I've used DLists a couple of times - and I sent Don code for DList.cons after his first release didn't include it. (The code is so simple, though, that I can't really take much credit for it. I strongly suspect it would have been in his next release anyway.) The standard libraries also include an implementation of 2-3 finger trees in Data.Seq. I don't understand finger trees, but their documentation claims to support O(1) cons, snoc, and left and right decomposition.
Fascinating article! But just to play devil's advocate, a question. :-)
You wrote: [A]t least from my understanding of AI, [it's] something at which titanic failure should be assumed.
Certainly that was true 10 years ago, but is AI still such a lost cause?
On the theoretical side, things have improved since the AI boom of the 80s. Problems which we could once solve with 20% accuracy, such as face recognition, are now above 95%. Similar improvements have occurred in robot mapping, in statistical natural language parsing, and in many areas of computer vision. And let's not forget spam filtering, which represents an extraordinary accomplishment in text classification.
And if we turn to the real world, we see plenty of these ideas in practice: Google makes effective use of clustering, natural language parsing, Bayesian inference, and many other techniques. For that matter, Google can even translate the front page of Le Monde comprehensibly.
So, in principle, there's no reason why Aetion shouldn't have been able to get some commercially interesting results. Granted, a program which is right only 80-95% of the time may have trouble competing with humans who are right 99.9+% of the time. But on the other hand, such a program can look at far more data.
I really think you ought to be able to make money by sticking a bunch of smart mathematician/programmer types in a company, and having them attack "AI" problems. How else can we explain Google?
In re: Eric's comments.
There is a principled reason that Aetion hasn't, and won't succeed, but you're correct that it has little to do with software. It has more to do with Conway's law:
Organizations which design systems ... are constrained to produce designs which are copies of the communication structures of these organizations.
Aetion's software will thus always resemble an unorganized collection of tenuously connected ideas with little to no technical underpinning. (-:
However, to address your larger question, I'm not sure that the existance of successful systems necessarily suggests that new projects should necessarily have any expectation of success. For instance, there are plenty of successful languages running about, and plenty more languages that have contributed significantly to the PL mindset, even if they haven't survived. On the other hand, I don't yet expect that each new language will even get as many users as Haskell, let alone Java.
On the other hand, I think the opposite holds for, say, parsers. If someone produced a language with a completely confused, inverted, and generally useless parser that even occasionally caused programmer frustration, I would be quite surprised.
My not-unbiased assessment is that AI is in roughly the same place at the moment. Some problems are definitely well understood, and some simple techniques (search, for instance) can become significantly useless if you apply them in not completely standard ways (i.e., Google's MapReduce). On the other hand, I'm not sure that means that a project setting off to do something outside those solved problems should expect to do well.
Of course, there is a final question: why was Aetion's work so far outside the collection of solved problems, when it seems like there's more solved-problem-space than ever before? That comes back to the human factors: Aetion's founders were convinced that they were doing stuff that was brand new and world changing and like Amazon, not GM, and therefore anything that had been used before, be it indexing structures or AI techniques, was looked at askance.
...and therefore anything that had been used before, be it indexing structures or AI techniques, was looked at askance.
Gotcha. That's a very common failure mode for Lisp companies, too.
And I agree with your assessment that the average AI project will fail for a long time to come. After all, about 45% of all large software projects fail, regardless of problem domain--but the failure rate isn't the same for all organizations. Some companies have a very low failure rate; others botch the majority of their projects.
And since AI is much harder than the typical payroll system, the failure rate for AI projects should be correspondingly higher.
But what if we take a little detour to the Ideal World™, where everybody has a clue and nobody reinvents the wheel in a suspiciously square shape? :-)
Assume that everybody makes intelligent use of statistics. Assume that they try the known techniques first. And assume that they only break new ground when it looks like a big win.
In this fantasy world, are most AI projects still doomed to failure? My intuition says no, based on the last decade's steady string of research wins. But your intuition is more interesting to me, because you've been out on the lacerating edge of this stuff.
To appropriate somewhat unfairly some big words, I like to chart the development of pieces of computer science on an art/science/engineering progression. Arts are basically not understood by their practitioners; while there are likely to be schools of approaches that succeed at particular problems, or with particular definitions of success, or for particular collections of users, and while it may even be possible to chart the evolution of these schools and the exchange of ideas between them, there isn't much way to predict the success or failure of any given school based on that. Programming language design probably fits into this category. While one can certainly point out the various aspects that Ruby shares with Perl, or Smalltalk, and how Python does or does not share those aspects, this doesn't give you much of an idea of whether Ruby will eventually eclipse Python or how long it will take. Sciences have developed the underlying law, but still require a certain amount of experimentation and experience a lower success rate. I think that programming language theory fits into this camp. The properties of programming languages can be proven by resort to various mathematical frameworks - for instance, the pi calculus, or the lambda calculus. On the other hand, it's not necessarily possible to specify a set of goals and generate a programming language that provably meets those goals. Engineering, finally, has achieved the last goal. It's possible, for instance, to plug a language description into a parser generator and get a parser out the other side. It's possible, in advance, to know what kind of parser can be generated for a given language, the performance of the parser, etc.
That makes your question roughly where on the progression do I think AI is? I'm a bit pessimistic, but I think it's still roughly in the stage of a fairly well developed art. There are certainly going to continue to be approaches that are more reliable than others, and I think that as people get a better understand of those approaches (and avoid the tendency to redevelop things that already work), you're going to see more successful AI projects because they're going to be following in successful paths. However, I don't think that we're likely to have a scenario in which AI projects really have assured success, or in which AI can be used as a component in other projects with a necessary guarantee of success.
Of course, I've had more than one negative experience in AI at this point, so this may also be simply pessimism on my part. On the other hand, I thoroughly enjoyed Russell and Norvig's book, and it still felt to me more like a vaguely organized cookbook of particular ideas that had or hadn't worked than a exposition of a structured, understood field.
I was exposed to AI twice. The first time was via the Lisp community in the mid-90s, and it consisted of the stale dregs of the 80's AI boom: logical inference, search, and lots of other mistaken attempts to treat the world as a syllogism.
Apparently, the twin gods of deduction and ontology first seduced the philosophers in the 1800s. The philosophers got over it, eventually. The mania next broke out in the AI community, which soon went blooey, leading to the AI winter. And today, this cult of the syllogism seems to have seized control of the W3C, where it develops ever more elaborate ceremonies to glorify RDF.
(Clay Shirky, whom I linked to above, has chronicled this history in greater detail.)
My second introduction to AI was in a computer vision class taught by Hany Farid. Professor Farid encouraged us to look beyond the hacks, the ad hoc algorithms so common in earlier years, and focus on the mathematical heart of the problem. And this focus paid off: A simple technique like SVD was enough for face recognition (see "eigenfaces"). Better directional derivatives improved motion tracking.
And since then, I've seen many more examples where a little bit of math revolutionized a problem in AI: Paul Graham implemented a "naive" Bayes filter, and could recognize spam with 99% accuracy. Systems based on Latent Semantic Analysis (another SVD hack) started scoring well on the TOEFL analogy sections. Natural Language Processing, a chronic failure, turned into Statistical Natural Language Processing and started succeeding.
These cases have several thing in common. They each involve:
1) More math than earlier AI techniques, most commonly either statistics or linear algebra.
2) Extreme simplicity. A basic face recognizer, for example, fits comfortably in a few pages of Matlab code.
3) A strong pragmatic focus.
In 2007, I'd hypothesize that these three traits are the best predictors of success in the art of AI.
But that's the nice thing about artistic manifestos: There's room for disagreement over the fundamentals. :-)
On the other hand, I think the opposite holds for, say, parsers. If someone produced a language with a completely confused, inverted, and generally useless parser that even occasionally caused programmer frustration, I would be quite surprised.
You know, if I didn't know better, I'd say you were describing the syntax of Perl. But of course I know you really mean C++. Or was it APL? It's so hard to be clear on these things... ;-)
In my admittedly somewhat narrow experience, a culture of strong resistance to "Not Invented Here" is one of the strongest forces impeding the success of large-scale commercial ventures, whether in software, or hardware, or in engineering fields unrelated to computers.
In fact, a similar trend can be found in academic research as well, but the peer review process of the more reputable conferences and journals usually squashes it before it gets too far afield. You at least have to demonstrate that your wheels have a convex profile and at least five non-collinear edges.
Ah, another Schlemiel the Painter's algorithm.
Post a Comment