January 2018

S M T W T F S
  123456
78910111213
14151617181920
21222324252627
28293031   

Navigation

Page Summary

Style Credit

Expand Cut Tags

No cut tags

Square wheels

pozorvlak: (kittin)
Sunday, September 30th, 2007 08:26 pm
SICP section 2.4 set off my wheel-reinvention alarms in a big way. It discusses writing code to use complex numbers in a representation-agnostic way; your complex numbers can be either in polar (r, θ) form or rectangular (x + i y) form, and ideally you'd like not to care. Their solution? "Tag" each number with its representation, by passing around pairs whose first element is a symbol: either 'rectangular or 'polar. Your procedures to (say) find the magnitude of your complex numbers first check the symbol and then (in a nice, generic, data-driven, extensible way) dispatch the correct procedure given the representation you're using.

Which is all very well, but isn't this... y'know... a type system? Given that Scheme obviously has some sort of type system in place so it can complain when I try to add 1 to "fred", aren't we reinventing a pretty large wheel? Is this, in fact, final and clinching proof of Smith's (First) Law?

Well, yes and no. Yes, we are implementing a simple type system, but given that the main thrust of the book is how to write interpreters and compilers, that's a pretty useful thing to know. It's also interesting to see how you can whip up your own type system (and module system) atop pairs and lambdas. It's a very simple type system, but it's not too hard to see how, with a slightly more complicated data structure storing your dispatch tables and possibly some macros to take away the busywork, you could implement inheritance, generics... even something like Frink's physical units tracking. And you could mix and match such systems throughout your program. I can't decide if that would be really really cool, or a maintenance and reuse nightmare :-)
Tags:

Programming diptych

pozorvlak: (babylon)
Saturday, September 29th, 2007 12:58 am
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 nCr 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.
Tags:

SICP

pozorvlak: (pozorvlak)
Monday, September 24th, 2007 12:49 pm
I got back from Wales on Tuesday, to find my copy of Structure and Interpretation of Computer Programs (sometimes known as the Wizard book, or SICP, or "sickup", as I've taken to calling it) waiting for me. It's the first-year computer science textbook used at MIT, and early signs are that it's going to be worth its weight in rather good coffee.

( Chapter summary )

I've been working through the exercises, and I'm up to about page 70 (most of the way through Chapter 1). So far, there hasn't been anything really difficult, though a couple of the exercises require you to do Actual Experiments on a computer, and since, what with one thing and another, I don't have a working one at the moment (I'm typing this on [livejournal.com profile] wormwood_pearl's laptop), I haven't been able to do these. Some of the algorithms are new to me, and I've particularly enjoyed doing some programming with loop invariants (but how do you find them in the first place? Presumably there are techniques...), but it's hard to shake off the feeling that a lot of it is old hat; I've been programming computers for nearly twenty years, I'm no longer surprised by the concept of a data structure :-) I've enjoyed the philosophical and historical asides - if an algorithm dates back to ancient Egypt, they'll tell you which papyrus fragment it was found on - and the generally thoughtful and informed tone of the book. The progression from procedural to data-driven to metalinguistic programming reminds me of Eric Raymond's The Art of Unix Programming, but this is surely not coincidence - like many expert Unix hackers, Eric was a Lisper first. [livejournal.com profile] totherme may be amused to learn that his old tutor, Joe Stoy, is a frequently-cited contributor :-)

1Including some probabilistic algorithms - the ease with which one can roll a die in Lisp is not such a trivial matter :-)
2Plus ways of making change from a dollar or pound - I was amused to note that they haven't updated it to reflect the disappearance of the halfpenny :-)
3They're quite fond of the prefix "meta": for instance, they call an interpreter for language X written in language X a "metacircular interpreter", rather than just a circular one, for reasons which I can't quite fathom.
Tags: