?

Log in

No account? Create an account
Programming notes - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Programming notes [Feb. 4th, 2007|03:33 am]
Arvind Narayanan
[Tags|, ]
[Current Mood |excitedexcited]

Immutable data. Just as average programmers feel smugly superior to bad programmers because they (the former) avoid manual memory management, good programmers feel smugly superior to average programmers because they avoid mutable data, and thus suffer no side effects of any function calls, ever. It's probably been 6 months since I used mutable variables (except for the occasional counter or a small function that's nevertheless referentially transparent), and it's been programming nirvana. I'm very, very lucky I took two programming language classes a year ago.

I hope that some day, beginners will be taught to program this way. Maybe a new pointy haired boss-friendly language will be invented and marketed with a barrage of buzzwords, and will also hold the programmer's hand remove the ability to modify data, just as Java did for manual memory management. However, the lambda calculus is much harder to conceptualize than the Turing machine, and so it's unlikely that anything more than a small percentage of programmers will get on board.

Performance. What about the performance hit? There isn't one. Any half-decent functional programming language should provide you a way to make the "inner loops" of your programs run at essentially the same speed as C (excellent tail recursion elimination in lisp, various "implied loops" in python). I do run into occasional performance problems with python, but they're not serious, plus they're specific to python and wouldn't happen with Lisp.

In fact, I deal with gigabytes of data regularly and the functional style is especially well suited to it, because you can program interactively. With imperative programming, you're forced to test your program by re-running it on the massive dataset every time you make a trivial change. With functional, you can code and test each little function individally, which works because there's no state. If you threw an exception deep in the bowels of some complicated function, no problem -- you fix it and call the function again, with the same arguments, with no need to rerun the computation up until the point where the function was called. It's hard to visualize what I'm talking about; I had an epiphany the first time I tried it. Essentially, you can edit your program while it's running. Also, the concept of a debugger is not very meaningful, because there is no state for it to inspect!

Anyway, I'm quite convinced that the tired old argument that "functional programming is great for academics, but it doesn't deliver in the real world" is 100% BS. It comes from a combination of intellectual laziness, sheer ineptitude, and the emotional inability to accept that 95% of the code you've written so far in your life is crap.

Hughes. I did a class paper last year about the 1984 John Hughes paper on functional programming, which is somewhat relevant to mention here. My last two posts on programming were motivated by it. Note that it is an argument against the Hughes paper, not against functional programming (even though it looks like the latter).

Python. I've been running into some limitations of python. The horrible function call overhead is one. You can't sample an element at random from an object of the set builtin type, or from a dictionary. No lazy evaluation. And no macros.

Python is delightfully concise, however. Here's a single-line quicksort, for instance:

>>> def q(l): return len(l) > 1 and q([x for x in l[1:] if x < l[0]]) + [l[0]] + q([x for x in l[1:] if x >= l[0]]) or l
...
>>> q([2,3,5,1,4])
[1, 2, 3, 4, 5]


Not the way you'd want to write it, but good to know you can.

Taking the plunge. Paul Graham's book On Lisp has an excellent description of why macros are important. Essentially, when you want to solve a problem, you write the solution down in an intuitive language that you invent on-the-spot that you think is a good fit for the problem. This is almost like writing specifications, which can now be dispensed with. Then you switch and work bottom-up, you start from lisp and write macros to extend it until the language grows to become the very-high-level language that you imagined when you wrote your initial code. That's just beautiful. That's how I want to write programs!

This pretty much convinced me that I need to take the plunge and learn a pure functional language. However, this is a very long term commitment and I'm in no hurry to do anything hasty. I basically seem to have the choice between Haskell, the Lisp variants, and the ML variants. Haskell sounds great, but apparently doesn't have macros. It's proabably just called something else instead of macros, I need to look into it more. Aside from that, there are practical issues. Should I switch to Emacs? Doesn't seem to make too much sense to be using an extensible langauge and not taking advantage of its poster-child, the extensible editor. On the other hand, is it worth it reprogramming 10 years of vi muscle memory? It's going to be an interesting challenge.
LinkReply

Comments:
[User Picture]From: hukuma
2007-02-04 04:10 pm (UTC)
If you like concise, you'll love Haskell:

q(x:l)=q[y|y<-l,y
[Error: Irreparable invalid markup ('<x]++x:q[y|y<-l,y>') in entry. Owner must fix manually. Raw contents below.]

If you like concise, you'll love Haskell:

q(x:l)=q[y|y<-l,y<x]++x:q[y|y<-l,y>=x];q[]=[]

Or in two lines:
q []=[]
q (x:l) = q(filter (<x) l) ++ x : q(filter (>=x) l)

which is the way I'd actually write it.

I've heard good things about macros but I've always been turned off enough by the (syntax (of Lisp)))))))) to really look into it.
(Reply) (Thread)
[User Picture]From: arvindn
2007-02-04 06:33 pm (UTC)
Indeed! That was one of the things that really impressed me about Haskell. That and excellent library support. It's even got an actively developed gtk binding!

Re parentheses -- c'mon, if something is advertised as solving the world's problems, you don't want to reject it because it doesn't look good :)

Although I do also see your point -- python indentation became natural to me after the first 15 minutes of use, whereas lisp syntax didn't, even after a semester.
(Reply) (Parent) (Thread)
[User Picture]From: theswede
2007-02-04 06:00 pm (UTC)
Definitely learn LISP. It's a great basis for all other functional languages. Use Vile instead of Emacs if you're hard wired for vi keys. Sure, it has all the visual appeal of a pile of nail clippings in a plate of oatmeal, but it's the base language for so much you find in other languages, and an excellent way to learn how to actually code functionally.
(Reply) (Thread)
[User Picture]From: arvindn
2007-02-04 06:43 pm (UTC)
Good point about vile. I think I kinda understand Lisp at a basic level reasonably well, and I definitely want to learn it more. The question of which language to use for day-to-day programming though, still remains. I guess I'll try both Haskell and Lisp for a while and then decide.
(Reply) (Parent) (Thread)
[User Picture]From: ephermata
2007-02-04 06:34 pm (UTC)
Should I switch to Emacs? Doesn't seem to make too much sense to be using an extensible langauge and not taking advantage of its poster-child, the extensible editor.

Unless you think you'd actually use the extensibility of emacs, I don't see why you need to switch. I guess this is tied up with Paul Graham's discussion of macros and specifications, but in that case you have
a problem at hand to solve, and that's why you're writing the spec. Do you find that you have those kind of problems with your editor?
(Maybe another way of saying this is "is it broke?")

All of this is just reminding me how much of an emacs and vim-luddite I am. I barely even have syntax highlighting turned on most of the time. ;)

By the way, I heard a story once about Steve Jobs' visit to PARC. During one of the demonstrations, he remarked on the scrolling speed of a window in the GUI - it was off by a little bit or something. The guy running the demo said "oh, OK, I'll fix it", opened up the Smalltalk code for the scrollbar widget, changed the scroll setting, and then it just worked.
Talk about debugging while it's running.
(Reply) (Thread)
[User Picture]From: arvindn
2007-02-04 06:50 pm (UTC)
(Maybe another way of saying this is "is it broke?")

That's an excellent question to ask if you're comparing two things in the same category, but I'm not sure if Emacs and the rest of the editors are. If your editor understands the language you're writing in, I feel that's a whole different level of programmability.

I can't be sure, though, or give you an example, as I've never used Emacs. But I can give you an analogy from when I switched to vim instead of a really barebones editor. My old editor could edit programs just fine, but after using vim I couldn't help wondering "how the hell does anyone get any programming done without tags?!" (this was of course with C programs, which tend to be gigantic beasts where if you change one part of the code you also have to change 10 others.)
(Reply) (Parent) (Thread)