Posted by Daniel Lyons
Mon, 12 May 2008 15:17:00 GMT
Over the weekend I wrote the same program in three (almost four) languages: Haskell, Common Lisp, Erlang and almost Prolog.
I have an informal result I want to share. The first one I wrote was in Haskell. Of the four, it was definitely the most fun to write. I did, however, avoid monadic computation when it probably would have been amenable, instead I opted to use interact and a small combinator of my own design. In a “real” program in a strict language I’m sure it would have been inefficient. I felt the freedom of Haskell, letting you design the solution in the most abstract, high-level way you can imagine it, and still make it quite small.
Next up was Common Lisp. I was surprised by several things. For one, it was shorter by a handful of lines than the Haskell version. I used essentially the same design as the Haskell and that seemed to work well enough, though Lisp lacks the combinators that Haskell comes with, so I wound up using a do loop for something I was just doing with map in Haskell. And of course I was annoyed by the effort it takes to produce an executable: (sb-ext:save-lisp-and-die "a.out" :toplevel 'main :purify t :executable t).
Then I started on Prolog. Of course, the logical part of the problem was short and sweet. Then I thought about what it would take to do line input/output, got the shivers, and decided to move over to Erlang. The syntax is fairly similar, though the execution strategy is shockingly different, but this application didn’t require any backtracking anyway.
Erlang wound up being shorter than Lisp or Haskell.
This fact stunned me, though I can explain it: Lisp requires a fair amount of schmuzz to do things that are free in Haskell and Erlang (namely, defun steals a line for itself) and Haskell requires a fair amount of schmuzz for human-assisted type checking. Erlang didn’t need either of those and has some of the strongest pattern matching around (though the limited guard support is obnoxious). Erlang did need Rubyesque and despicable list_to_integer and atom_to_list type conversions, but none of those cost me a line. You could omit the type declarations in Haskell, and I did add a line to make the type signatures more readable, but that’s really bad form.
I also found myself wondering how much I was buying myself by using Haskell’s data types for part of the computation. What’s the difference between reading a character or two to create a special instance of some data type and then using that everywhere, versus just using the character? In Haskell I’ll get a read error, whereas in Lisp and Erlang an ecase or a pattern match is going to fail later in the game, but not that much later. Does the anal retentiveness pay off in the end? I’m starting to wonder if, as Jonathan Edwards is proposing, formality is a cure that’s worse than the disease.
- Erlang was the shortest (least syntactic BS as far as writing functions are concerned).
- Erlang was the hardest to debug (the error messages are more machine-readable than human-readable).
- Haskell was the most fun to write (I guess I like function combinators and higher-order programming).
- Haskell took the longest to write (it was the first one I did).
- Lisp was the easiest to write and debug.
- Lisp was the hardest to get to a binary of those that could (I don’t think Erlang can ever give you back a binary directly).
- Lisp’s schmuzz was the most obnoxious to write (especially the hapless
destructuring-bind, which is substantially underpowered compared to Erlang’s or Haskell’s pattern matching facility).
I think I will try using Common Lisp’s bind library later this week to rewrite this and see if I like that better than destructuring-bind.
Tags erlang, haskell, lisp | 2 comments
Posted by Daniel Lyons
Mon, 17 Sep 2007 19:50:00 GMT
Planet Erlang used to be in my list of aggregated sites. It’s not anymore, and because I don’t see a good place on the site to leave feedback, I’m leaving it here.
- Planet Erlang is the only RSS feed that spams me. There’s no excuse. Planet Io doesn’t, Planet Haskell doesn’t, Planet Lisp doesn’t, Planet Erlang had better figure out how that’s happening and make it stop. Killing the item after it gets posted isn’t good enough if it still winds up in my RSS reader, which it does.
- Planet Erlang’s RSS feed is one point shy of completely useless to begin with. The whole point of an RSS feed is to bring me the content without me having to ask. Planet Erlang brings me a one sentence description of the content—in the title and the body. Who thought this was a good idea?
- Finally, when I do click on the title of the story, I wind up not at the story, but at Planet Erlang’s web page with Planet Erlang’s one-sentence summary of the story. Then I have to click again to get to the site.
Here’s a refresher on how RSS is supposed to work:
- I sit on my ass, reading news.
Here’s what actually happens with Planet Erlang:
- I sit on my ass, getting spam.
- Once in a while I see an interesting article’s title.
- I click on it to read it, because it isn’t already there in my news reader where it should be.
- I click on it again to get away from PE’s site and read it.
All this so I can see comments from someone about the site being linked to. Invariably, there are none for me to see. I’m invited to vote on the story. Invariably, the story has one vote.
I don’t know what you guys think running a Planet-style aggregator is all about, but you’re failing it, and you’re being an obstacle to the information I’m there to get.
Tags bitching, erlang | 7 comments
Posted by Daniel Lyons
Thu, 09 Aug 2007 05:59:00 GMT
My wonderful arch nemesis Kirit Sælensminde is up to his dastardly old tricks again. Erlang must be officially in the cool now, or else no one would be trying to demonstrate that their language of choice (or invention, to Kirit’s credit) maps perfectly onto it, or vice-versa.
Let’s talk about the semantic differences:
- Erlang messages are one-way. All OO languages have call-return semantics.
- Erlang’s functions and message passing systems are fully orthogonal.
Erlang is much, much weirder than your run-of-the-mill OO language. But of course we can dig out examples that are different from your run-of-the-mill language—my favorite example is Io. In Io, you can prefix your message with @ to get a transparent future, or @@ to send an asynchronous message altogether. (Of course, let’s forget for a second that Io is implemented with user threads, so it doesn’t scale anything remotely like what Erlang does on huge quantities of processors.) But in Erlang, if you want to return something, you have to send a new message back to the caller. Or two messages. Or none, or whatever.
While we’re thinking of languages with interesting semantics, find me one in which the methods work in a completely different way from the functions. In a decent OO language, you can’t even make a function that isn’t hooked up to a class or an instance.
Also, there are liberties you get with Erlang that you would never get with OO; because the state is just whatever you happen to pass through the listening function. You can call completely different functions when you’re done handling this request, transforming or dropping your state on the floor altogether. This is how you get live code replacement—because there is a boundary between your “behavior” and your “state,” unlike OO where the whole point is to mingle the two ideas.
Then of course we also have implementation differences:
- Starting an Erlang process is cheaper than whatever you’re doing (threads, fork/exec, whatever).
- Sending an Erlang message is cheaper than executing a method.
I think I’m really getting at two ideas simultaneously and I fear I may be muddying the water. The first is that there’s nothing surprising about computational equivalences between Erlang and OO language X. After all, in C++ all those fancy method invocations wind up being function calls inside the compiler, which in turn wind up being jumps or whatever in the binary. What is surprising and obnoxious is the thought that this computational equivalence implies that language X ought to be as great as Erlang (or whatever other language we’re talking about). We’re not ever comparing the totality of language X and Y, just whatever subsets of each that happen to make the discovery of this equivalence easy.
If there’s nothing new about Erlang’s message passing system, then why doesn’t every OO language have the parallelism benefits Erlang has? Joe asserts that the reason is because Erlang is a functional programming language free of destructive assignment, and, by extension, most of what you think of as being state in an imperative language. Isn’t the whole point of OO that your objects have state and behavior and can be carried around as a unit? If Erlang is OO, it somehow wound up there starting from completely different pieces.
Supposing that Erlang is OO but it got there a completely different way, what makes you think Erlang has any ramifications for language X? It seems possible (putting it mildly) that there is more to a programming language than simply what can be proven about it mathematically. That there are aesthetic concerns and pragmatic concerns well outside what can be proven with math. While we were talking about Erlang from an OO perspective, did we mention the utility of its bit syntax? The closest comparison I’ve seen to it is Haskell’s BitSyntax library and even that’s terrible in comparison. And don’t get me started about aesthetics. An anonymous object with a method on it might be “equivalent” to a lambda abstraction, but look at these two things and tell me with a straight face you wouldn’t prefer the OCaml version to the Java version:
// Java
addWindowListener(
new WindowAdapter() {
public void windowClosing( WindowEvent e ) {
System.exit(0);
}
});
(* OCaml *)
addWindowListener (fun e -> System.exit 0)
Erlang is here, now, alive and kicking, gaining in mindshare and popularity every day. It beats the crap out of basically everything else when it comes to concurrency. It has a reasonably large built-in library, it’s been field-tested and really delivered. So what’s with the rush to talk about taking its features to other languages? This is really puzzling to me because Erlang is among my top six languages for implementing damn near anything. I’d vastly prefer it to, say, JavaScript, which is the foundation for Mahlee. JavaScript is a potentially fine language but, as usual from the curly brace contingency, it eschews expressiveness for something like backwards compatibility with menial programmers. Of course semantically I love it, but I love Io so much more I can hardly think about JavaScript. I see it as a web development necessity made tolerable by Prototype, which really is just Ruby for JavaScript when you get down to it.
The rush to pirate the #1 interesting feature from Erlang into various other languages is indicative to me of two things:
- Everyone wants easy concurrency right now, and
- People do not fully appreciate either the mathematical, pragmatic or the artistic value of a programming language.
If people really were interested in a language as a mathematical principle, then they would only program in languages that map directly onto mathematical formalisms, and they’d chafe at the places where the mapping isn’t perfect. Instead, we rely on math when it’s convenient for us, and discard it the rest of the time.
If people really were interested in a language pragmatically, they would see the value of the language as being a holistic experience. I think there are some truly pragmatic programmers in this world using C, C#, C++, Python and Ruby simply because the combination of the language and the library is best for them. It’s extremely contrary to pragmatism, however, to look at other languages solely in terms of collections of ideas which can be stolen. Languages that are assembled this way are rarely beautiful and never mathematical. In general they come out looking like C++.
If people had a taste for languages as an art form, they would certainly find Erlang to be too beautiful in its own right to want to rush out and copy it. And even if they did, for some reason, desire to do that (perhaps because of some great idea which is impossible in Erlang or merits its own language) they would at least have the artistry to not make it another hard to read, hard to parse nightmare like a curly-brace language. I would, in all seriousness, expect it to look more like Haskell. I’d even take a Ruby/Python hybrid, personally, having the keywords and flexibility of Ruby combined with syntactically meaningful indentation/whitespace.
To return to the topic, it’s very easy to look at Erlang’s message passing and attribute the performance and reliability of Erlang to it. This is an error. Erlang’s performance is not a pure math result, but rather a combination of having a very strong theory supported by a very strong implementation and an environment that encourages coding to a certain aesthetic standard that maximizes the utility of the implementation and theory. Threading can be done correctly, beautifully, and so forth but nothing about threading itself or its implementation in threaded languages in any way encourages this—and threading today is considered expert knowledge, practiced very conservatively by most developers if at all, with the vast majority preferring to write unthreaded code or for systems such as web servers backed by relational databases which mitigate the complexity. Ruby, like Io, uses green threads internally yet by the grace of web servers and databases is used to serve millions of concurrently-generated pages daily by everyone using Rails. (And it’s worth pointing out that its user threading is much poorer than Io’s, which is actually quite good for what it is).
Erlang does everything in its power to help you and encourage you to write concurrent programs the right way. Some of this is syntactic—your messages can be of arbitrary complexity and pattern matching makes it quite simple to decide what to do with a given message. Some of this is semantic—you cannot assign to a variable that’s already bound. Some of it is in the standard library, like OTP, which makes it easy to write servers and monitor them. The whole infrastructure is conspiring with the programmer to the same end. It would be a lie to tell someone, “well, you’ve used OO, that’s message passing, that’s basically the same” because they haven’t experienced it in truth. From this perspective saying “Erlang is OO” is completely meaningless because it’s so much less and so much more than OO is. And simultaneously, to say “If you have asynchronous messages, then you have Erlang” would also be a lie, because it’s like pointing to the engine of a car and saying it’s all there is to it.
A language is so much more.
Tags erlang, functional, kirit, mahlee, oop, programming | 2 comments
Posted by Daniel Lyons
Sat, 19 May 2007 03:58:00 GMT
For fun during my meeting with Baird the other day at the Flying Star on Central, I gave him a toy problem I read somewhere on the internet.
Problem: In Prolog, write a predicate len_three/1 which succeeds when its parameter is a list of three items.
A crummy answer looks like this:
len_three(X) :-
length(X, Len),
Len = 3.
Of course there are always many crummy answers. Here’s another crummy one:
len_three(X) :-
length(X, 3).
The best answer is to let the unification algorithm do the work:
len_three([_,_,_]).
Erlang isn’t a far cry from Prolog syntactically, so it’s no surprise that this is valid Erlang:
len_three([_,_,_]) -> true.
To illustrate using the remainder of a list, I showed him how to write head and tail in various languages:
-- Haskell
head (x:_) = x
tail (_:xs) = xs
(* OCaml *)
let head (x::_) = x
let tail (_::xs) = xs
% Prolog
head([X|_], X).
tail([_|T], T).
% Erlang
head([X|_]) -> X.
tail([_|T]) -> T.
So you see these are all pretty analogous to each other, thanks to the pattern matching or unification functionality of the various languages.
So then Baird wanted to see an example of peeling some items off a list but also using the remainder. So I proposed pairs/1, which takes a list as a parameter and returns a list of lists, each sublist containing two items. Implementations:
-- Haskell
two (x:y:xs) = [x,y] : two xs
two [] = []
(* OCaml *)
let rec two = function
| (x::y::xs) -> [x;y] :: two xs
| [] -> []
;;
% Prolog
two([X, Y | Xs], [[X,Y] | Result]) :- two(Xs, Result).
two([], []).
% Erlang
two([X, Y | Xs]) -> [[X, Y] | two(Xs)];
two([]) -> [].
Some observations:
- Notice how much more obfuscation there is going on in the OCaml version than the Haskell version. Taste that sugary sweetness of Haskell’s syntax.
- In theory, the Prolog version should be reversible—in other words, you should be able to unify by calling two(X, [[1,2],[3,4]]) and getting X = [1,2,3,4] back. In practice, I have some trouble writing predicates that have that property, and I’m not sure what I’m doing wrong. I should study Prolog more carefully.
- Notice the Erlang version is shorter than the Prolog version. Shorter and perhaps slightly more readable. I have omitted the module and export declarations, however.
- The Erlang implementation does something funny if you give it 1-10:
2> two:two([1,2,3,4,5,6,7,8,9,10]).
[[1,2],[3,4],[5,6],[7,8],"\t\n"]
Tags erlang, functional, haskell, matching, ocaml, pattern, programming, prolog | 2 comments
Posted by Daniel Lyons
Tue, 10 Apr 2007 07:23:00 GMT
This is a response to Why Misunderstanding OO Sucks.
As systems get larger and more complex then the reductionist view becomes less and less relevant. It continues to have useful inputs into the design, but the development process itself must become more holistic in outlook or it will fail to produce a harmonious whole.
This is an appealing view. It’s of course amusing to throw this at Joe Armstrong, who not only pretty much implemented Erlang but has had his hand in a number of largish systems. If Joe’s perspective were merely reductionist, I’d find it hard to believe that his creation is running the majority of telecom systems in the world. That can’t be a trifling matter.
I think it’s insane to call OO a process and emphasize its effect on software design. If that were the case, how did we have the OO revolution in the 80’s, and not have agile development until the late 90’s? No, if OO had anything to do with process, it had to do with waterfall-model spec, design, then implement thinking. And yet the strongest OO systems today, Smalltalk, Ruby, Python and Io, have nothing to say about the development model, because it had nothing to do with their development or use. If anything, Ruby has a model in agile, thanks to the agile people being overly fond of it.
As for everything being an object, this is only partly true. To make this statement true we have to group together two varieties of object—those with identity and those which are values. Many object oriented languages do in fact conflate these two types of data structure, but of course many do not.
The only OO languages that are a joy to use are those which “conflate” these two things. In Ruby, for example, I can define whatever method I like on integers and call it on a literal, such as the built-in 1.upto(10) { |x| puts x }. Ruby would blow without this feature. In fact, even Python has slowly started to adopt this as a feature. It’s Java and C++, which stupidly maintain a separation between objects and types, that receive the ire of programmers who wish to treat things uniformly.
This difference between object and value semantics is as fundemental to understanding object oriented design and programming as that of function composition is to functional programming. It is unfortunate that it is generally rather badly taught.
I would like to believe that, having been an OO programmer for five years, that statement would have meaning to me, but it doesn’t, for the reasons mentioned above.
If we could build systems that didn’t need to bother with state our jobs would be much easier, but the resulting software would be much less useful and interesting.
That’s interesting, because as mentioned above, Joe Armstrong’s Erlang is now the backbone of the telecom industry, and it doesn’t support modifying your variables. Now, it certainly has state, just like Haskell has state—implicit state, or state managed through a mechanism so alien that OOP isn’t even a concept that can be applied to it.
This shocked me when I started learning functional programming about a year ago. I looked at ML and I snorted. How can this possibly be usable without being able to factor my code into classes? What am I going to do when the client calls me up and I need to have the program do something totally different?
Well, it turns out in functional programming, we have a type system that makes some of OOP unnecessary. Firstly, it’s simple to construct types which enumerate all the different ways of carrying around state you would use in an object. Secondly, we have a pattern-matching system which makes it both possible and cheap to write functions that do different things depending on the nature of their input.
The straw man argument in that is: aha! What about when you add a new alternative to your type, then you have to go through all those functions again and update them! Supposing this is true, consider how hard it is to add a new operation in OO. Say you come up with some new method you need—Aha! You have to go through all those classes and implement that method. And that is the worst case in OO.
OO is, in general, a very good thing when compared to procedural languages. It’s nutty to defend Java and C++ type systems when Ruby and Eiffel exist.
The interesting thing about OO’s lamentable state is quite clear if you look at the history. C++ was made to be as backwards compatible with C as possible. Java was made to be essentially a simplification of C++ with a few improvements. The functional language community wasn’t in a position to have these worries, because these worries come from having a user base, so instead it came up with more and more amazing languages, trying desperately to get people interested.
Actually, this was the second time this had happened. The same thing had basically happened with Lisp in the late 70’s. Everyone was using it and making incompatible variations. Then eventually they decided to have a big standardization process during which the AI winter apparently came and everyone switched to C++. I guess.
What makes the debate bizarre is essentially the Smalltalk factor. While everyone was switching to C++ and lauding the wonder that is OO, how many people were using Smalltalk? It’s not like Smalltalk went away, but it seems to have as many users now as it had after everyone defected for the other. And yet it’s so much more capable and powerful. I find it hard to believe that C bindings could be so difficult or that optimizating compiler technology could be so out of reach when C++ is about the most complex language being used (after FORTRAN or Ada, probably).
In my opinion, I should be spending more of my time worrying about what I’m doing with data rather than worrying about the data itself. OO is definitely interested in helping you worry about the data itself. This is a natural fit for boring business data processing, which is why Java’s being hailed the new COBOL. The crown belongs to the functional languages, but boredom has killed the king.
Tags erlang, oop, rants | 2 comments
Posted by Daniel Lyons
Mon, 09 Apr 2007 08:15:00 GMT
I caught wind of Norvig’s statistical spellchecker essay earlier today and decided to do a reimplementation in Haskell.
Right now, my version blows. It’s 61 lines of code compared to his 25, substantially slower and quite ugly to boot. Yay. :-P
In related news, I bought Programming Erlang. And I know someone who is using Oz which looks ugly and horrible but rather powerful at the same time, so I installed that too.
Tags erlang, functional, haskell, languages, oz, programming | no comments
Posted by Daniel Lyons
Wed, 13 Dec 2006 07:43:44 GMT
So often lately I think about how to make Voltaire functional. A key part of Voltaire is adding code for specific sites, both via plugins and into the regions themselves. This immediately disqualifies OCaml.
The problem of putting code into a template is basically a parsing problem. I already have parsers for VTemplates in OCaml and Haskell. It was a snap. I know of no parsing helper tools for Lisp. Bummer. Erlang has yecc and leex, which I might be learning soon, even though they’re very unorthodox.
OTOH, putting Lisp code into a region and running it later is a snap. eval is part of the REPL, after all. So it takes to dynamically inserted code like a dream. Erlang has a built-in library for evaluating strings, but it’s somewhat less convenient to use than Lisp’s eval. But it’s probably better too, it being Erlang. Haskell, I thought, has no eval. Actually it does, in the form of a library that doesn’t compile against GHC 6.6 (industry standard). It’s sort of wacky to me that you can implement eval as a library, but whatever.
I have in mind a good reason to use Lisp though: keeping data and functions together in the image. After all, the whole “regions table” could be kept in memory as a sort of infinitely nested hash or a-list, carrying around templates which have been compiled into simple functions which are applied to the request args or the requested path or whatever. In fact, it seems clever enough it would be fun to use. One drawback to such an implementation is that the code must then be kept in memory, rather than in a database (I think). So, I would have to supply a mechanism for changing the templates over the wire, and I’d have to keep around the template source, and worry about reading and writing this data structure to disk. Michael’s site is larger than Nina’s somehow and comes to a little under one meg of actual region data, though, so it may not be so bad performance-wise. But code would have to exist which currently doesn’t. On the plus side, if it were simply a nested a-list, the REPL could take care of the disk access, mostly. A hash table would be more trouble.
So, I have bits and pieces of Voltaire implemented in a half-dozen or so languages (several other chunks I haven’t mentioned here). As a family, I’d like to call them The Old Women, after the half-assed woman of Candide. If I eventually distill an implementation in one of them, I may name it Pangloss, since that name befits anything the result of such foolish optimism as I have.
...
I was told earlier today that my functional programming chops, combined with another person’s OO chops, “and Eastern Europe doesn’t stand a chance!” Rock on.
Tags erlang, functional, haskell, lisp, programming, voltaire | no comments
Posted by Daniel Lyons
Mon, 27 Nov 2006 10:15:00 GMT
Lance is fond of merge sort. I think the extra complexity here indicates that merge sort is basically easier on the human brain but doing the same kind of thing as quick sort, which is easier algorithmically. For some reason.
Anyway, here it is in highly convoluted Erlang. I went ahead and re-implemented the core algorithms for pedagogical purposes.
-module(merge).
-export([merge/2, sort/1, map2/2]).
merge([X|Xs], [Y|Ys]) when X < Y ->
[ X | merge(Xs, [Y|Ys]) ];
merge([X|Xs], [Y|Ys]) when X > Y ->
[ Y | merge([X|Xs], Ys) ];
merge(X, []) ->
X;
merge([], Y) ->
Y.
That’s a very pattern-oriented merge function. Very easy though.
map2(Fun, [A,B|T]) ->
[ Fun(A, B) | map2(Fun, T) ];
map2(_, T) ->
T.
The map2 function is basically going to apply some function against every two items in the list. This would suck to do without pattern matching. I go ahead and just concatenate any single item I find without passing it through the function or discarding it, because another part of my algorithm expects that behavior.
unwrap_or_recur(_, [X]) ->
X;
unwrap_or_recur(Fun, X) ->
unwrap_or_recur(Fun, Fun(X)).
OK. This is weird. In particular, this is the kind of thing that just wouldn’t be done in a non-functional language. But it felt natural here.
unwrap_or_recur takes two arguments: a function and a list. If the list only has one thing in it, I return that thing. Otherwise, I recursively invoke
unwrap_or_recur, passing the same function through and the list after having applied the function to it. This is weird but it will begin to make sense in a moment, so hold this thought.
sort(X) ->
unwrap_or_recur(fun(L) -> map2(fun merge/2, L) end,
[ [Item] || Item <- X ]).
How does merge sort work? Well, basically, you consider each item as a queue of itself. Then you merge every two queues into a bigger queue. Repeat until you run out of queues.
Starting with a function that merges two queues, the merge function, I thought, well, I can create a bunch of queues by just making each element a list. That’s the list comprehension in there. Take a look:
18> [ [X] || X <- [7, 3, 1, 5] ].
[[7],[3],[1],[5]]
OK. So then to get the next step, merging those queues, I just need to apply merge on the first and second pairs of queues. It would look like this:
19> merge:merge([7],[3]).
[3,7]
20> merge:merge([1],[5]).
[1,5]
The map2 function basically looks at [[7],[3],[1],[5]] and translates it into this: [Fun([7],[3]), Fun([1],[5])]. That’s going to produce this list: [[3,7], [1,5]]
So the first argument to sort, fun(L) -> map2(fun merge/2, L) end, is a closure that takes a list, and passes every two arguments off to merge. The second argument to sort is the actual list to sort, from the formal parameter.
So what happens in unwrap_or_recur? Well, it just keeps calling the closure above until there’s only one item inside the list. Suppose we do one more recursive application on the list [[3,7], [1,5]], what do we get? This: [[1,3,5,7]]. So then unwrap_or_recur pops the one list item out—the same as dequeuing the entire last queue.
This is all very cool, but I still think I prefer the simplicity of quick sort.
Tags algorithms, erlang, functional, languages, programming | 1 comment
Posted by Daniel Lyons
Sun, 26 Nov 2006 07:59:24 GMT
This last week I got some interesting bad news about my eyes: apparently my pupils over-dilate in darkness or semi-darkness. I have my first old-man disorder at the ripe old age of 25. On long drives at night I will have to turn the dome light on to prevent my eyes from perceiving every light source as a giant luminous splotch with an echo above or below it. This is also why I needed new glasses recently, but why I didn’t notice until I left my job and started working nights. There is no cure for this problem except time; as I age my pupil dilation should get less responsive, which will counteract this problem.
I just finished reading Demian by Hesse. A great book, except for all the cult stuff near the end. There are a number of passages that I really identified with, but the strongest was this:
“Sometimes when I ran through the streets in the evening, unable to return before midnight because I was so restless, I felt that now at this very moment I would have to meet my beloved—as she walked past me at the next street corner, called to me from the nearest window. At other times all of this seemed unbearably painful…”
I was very annoyed that I could identify so thoroughly with a character who goes on to basically endorse Anton LaVey satanism. Tsk-tsk.
I was thinking today about programming in Erlang and how much I enjoy it, but at the same time, though I enjoy my big functional languages, not one of them has a decent Mac library; most of them don’t even have decent Unix GUI libraries or web frameworks. Erlang at least has a promising-sounding web framework but I am tired of web programming for the moment. It’s so very occupational.
I became annoyed thinking about OCaml and how much I had liked it. OCaml is basically the marijuana of functional languages—you start there, and then you get into the heavy stuff like Lisp, Haskell and Erlang. Or else you remain trapped with OCaml, perhaps consuming liters of the Russian vodka of languages—C++—at the same time. “Well, it could be worse.” Yes.
I am disappointed that nobody has anything to say about my quicksort post. I suspect that one is for the ages, and in a couple years, someone will be quite glad it’s there. Nobody pointed out that I am doubling the constant factor in my partition, or that I should use median-of-three for better performance against pre-sorted lists. I expected Lance to show up and demand some merge sorts, which I haven’t coded since my second year of CS.
For myself in response to the Brick Science article, I wrote a small linked list library in C. It turned out to be about 55 lines of code, and it took me about 15 minutes to write, which reassured me after reading that the author expects 155 lines/hour. I would not expect anyone to achieve that in a reasonable language, but with C you can really fluff things up with meaningless brackets and wasted type declarations. Even Lisp, which is the most text-liberal functional language, is a factor of two or three improvement over C. I remember days at Clearwired where I was productively producing about 10 or 20 lines of Python an hour. Of course, HTML is a bit cheaper.
I have become a real dick about movies. Elitism is the opiate of the Dan, but I have tried to be conservative about which things I am an elitist about: heavy metal, programming languages and religion being the primary fields, but also somewhat about politics. I have more-or-less ejected politics as a synonym for theft, graft, stupidity, and waste, no matter the incarnation, so into the open slot I have tossed movies. My brother hasn’t helped, we have been alternating classics I have loved for some time with known-good classics of his interest, and both learning a lot. Plus now we have a lot of pretentious hatred for new movies. It’s a perfect fit with the rest of our hatred set (music and television).
I am now going to attempt to read another classic book, since I usually read about four non-programming books a year and Demian is number one for 2006.
Tags c, demian, erlang, eyes, functional, haskell, hesse, life, lisp, movies, music, ocaml, politics, programming, religion | 2 comments
Posted by Daniel Lyons
Wed, 22 Nov 2006 08:33:00 GMT
If you are interested in implementing quicksort in any reasonable language from scratch, you may not want to read this post.
I had some fun making this post but by all means draw your own conclusions and ignore my commentary.
The OO Languages
Io
List quicksort := method(
(self isEmpty) ifTrue(return List clone) ifFalse(
first := self first
rest := self slice(1)
below := Quicksort quicksort(rest select(i, i < first))
above := Quicksort quicksort(rest select(i, i >= first))
return below appendSeq(list(first) appendSeq(above))
)
)
I’ll be honest: this one took the longest and was the hardest to write. Additionally, it is the not very aesthetically pleasing (though moreso than any of the other OO languages), and I still don’t understand how Io knows when to execute a given piece of code (look at the select portion). It also was pretty unreadable until I separated the above and below variables out. I also didn’t understand why I needed return but it seemed to break the code to not have it there.
That said, it is very whitespacey, which is worth points in my book. This is the implementation I’m the least confident of. Io has changed a lot since I last was using it, and I never became very proficient at it.
Python
def quicksort(l):
if l == []:
return []
else:
x, xs = l[0], l[1:]
return quicksort([ i for i in xs if i < x ]) + \
[x] + quicksort([ i for i in xs if i >= x ])
For some reason, the list comprehensions didn’t do it for me this time. I preferred them in the functional languages where there seems to be less overhead. The parallel assignment helped a bit, but the lack of pattern matching was pretty annoying.
Ruby
def quicksort(l)
if l == [] then
[]
else
x, *xs = l
quicksort(xs.select { |i| i < x }) + [x] +
quicksort(xs.select { |i| i >= x })
end
end
It feels a little tidier than Python. The select was a little tidier than the equivalent list comprehension in Python, and seems to get right to the point a little better whereas with the list comprehension, the meaningful portion is in the if conditional on the far right.
I prefer the x, *xs = l notation, because it reminds me of pattern matching in the functional languages.
The Functional Languages
Haskell
module Quicksort where
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
++ [x] ++
quicksort [ i | i <- xs, i >= x ]
quicksort [] = []
Well, you’d expect a winner, and lo, it is a winner.
Erlang
-module(quicksort).
-export([quicksort/1]).
quicksort([H|T]) ->
quicksort([ X || X <- T, X < H ])
++ [H] ++
quicksort([ X || X <- T, X >= H ]);
quicksort([]) -> [].
Looks just like the Haskell to me, albeit with Prolog-esque syntax. But I like Prolog, so that’s worth a couple points. :) Tie with Haskell.
OCaml
let rec quicksort = function
| (x::xs) ->
(quicksort (List.filter (fun i -> i < x) xs))
@ [x] @
(quicksort (List.filter (fun i -> i >= x) xs))
| [] -> []
;;
Naturally, a bit of OCaml noise enters the picture. No nice list comprehension syntax so we get to use the old-fashioned filter function. However, it’s still quite small. I think it is very readable, I’m just wondering whether OCaml is going to wind up being the functional language I use the least.
Lisp
(defun quicksort (l)
(cond
((null l) nil)
(t (let ((x (car l))
(xs (cdr l)))
(concatenate 'list
(quicksort (remove-if #'(lambda (i) (< x i)) xs))
(cons x nil)
(quicksort (remove-if #'(lambda (i) (> x i)) xs)))))))
Wow. That’s… so ugly. By far the wordiest functional language. I could have done it without the let block though, in which case it looks like this:
(defun quicksort (l)
(cond
((null l) nil)
(t (concatenate 'list
(quicksort (remove-if #'(lambda (i) (< (car l) i)) (cdr l)))
(cons (car l) nil)
(quicksort (remove-if #'(lambda (i) (> (car l) i)) (cdr l)))))))
How unpleasant. I would have expected Lisp to do better. Oh well.
Tags erlang, haskell, io, languages, lisp, ocaml, programming, python, ruby | 12 comments
