Programming diptych

While trying to do one of the exercises from SICP, I wanted to apply and to a list. Now, I could have used fold, but it seemed a bit of a waste given that Scheme's and is variadic: what I needed was an equivalent of Perl's func(@list_of_args) idiom, or Python and Ruby's func(*list). So, inspired by the syntax for variadic function definitions, I tried

(and . list)

for various values of list, and it worked! Rather elegant, I thought: no special syntax, just an application of Lisp's usual list-construction and argument-passing rules (like the Perl idiom, in fact). But when I tried it with + instead of and, no dice - instead, I get a "Combination must be a proper list" error. Obviously something to do (I realise, belatedly) with the fact that and is a special form and not an ordinary function. Maybe Larry Wall was onto something with his idea that different things should look different :-) But why doesn't it work for ordinary functions? Isn't (func . args) equal to (func arg1 arg2 arg3...)?

[You can get the effect I was originally after by using (apply func list).]


One of the especially nice things about my shiny new Ubuntu installation is that I now have a working Java system, so I can run J in all its graphical glory. So today I worked through one of the J labs: specifically, the one about the Catalan numbers (I can't find the lab online, alas - you'll just have to download J and try it for yourselves :-) ). The standard formula for the Catalan numbers involves factorials, so both the nth Catalan number itself and the time needed to calculate it grows very quickly with n. You can improve the run-time by rearranging the formula to use binomial coefficients (J has a built-in function for calculating ⁿC_r in a non-stupid way), and this makes calculation of Catalan numbers up to the 10,000th or so almost instant. But when I tried to use this code to find the 100,000th Catalan number, my computer locked solid. Response became glacial, the hard drive paged constantly, and I had to kill J and restart the lab.

Fortunately, there was a better way. The rest of the lab showed how you could use the prime decomposition of 2n! and n! to find a much quicker way of calculating Catalan numbers. With this code, the calculation again became instant - a salutory reminder of the power of a good algorithm :-) I'm still finding J a bit hard to read, though: code like

+/ <. n % p ^ >: i. <. p ^. n

or worse,

cat1=: (! +:) % >:

makes my eyes cross :-(

[As any fule can see, the first line calculates the exponent of each prime p in n!, and the second is the naive formula for calculating the Catalan numbers.]

While writing this post, I came across this link, which is rather fun: Culture Shock.