Square wheels

[pozorvlak]

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 :-)

Comments

not to be a jerk, but...

[ryani.livejournal.com]

(using type families from the soon-to-be-released GHC6.8)

class Num cpx => Cpx cpx where
   type Real cpx
   i :: cpx
   (.+) :: Real cpx -> Real cpx -> cpx -- construct rectangular
   (.@) :: Real cpx -> Real cpx -> cpx -- construct polar
   realPart :: cpx -> Real cpx
   imagPart :: cpx -> Real cpx
   magnitute :: cpx -> Real cpx
   angle :: cpx -> Real cpx
   i = 0 .+ 1

Smith's first law, indeed.

Re: not to be a jerk, but...

[pozorvlak.livejournal.com]

Nice! Though one could make the case that Haskell requires new and experimental features to do things that Scheme has been doing easily since the mid-seventies :-)

Actually, one of the things that annoys me about Haskell, or more precisely about the community, is the way they'll say "It's a standard-defined language, with @benefits!", and in the next breath say "Oh, for that you'll need this new feature in today's VC snapshot of GHC! Isn't it neat?" Now, I have nothing against implementation-defined languages: some of my favourite languages are implementation-defined, in fact. Nor do I have anything against spec-defined languages, provided it's a good spec (and not, say one written by the W3C (http://www.w3.org/TR/xpath20/)). But at least be honest with yourselves, guys! :-)

[I've been thinking of blogging about this and related matters for a while - stay tuned...]

Re: not to be a jerk, but...

[ryani.livejournal.com]

Well, the "new & experimental" features are there for brevity (and coolness, I will admit!), not necessity. You could do this today with multiparameter typeclasses with functional dependencies:
class Num r => Cpx c r | c -> r where ...

By the way, "multiparameter typeclasses with functional dependencies" is probably the worst name for a language feature I've ever heard. Associated types are just a more natural way of expressing what we are trying to do here: specify that each complex type has an associated "component" type which it can be constructed and destructed from.

I freely admit to being a performance whore; I work on games, it kind of comes with the territory. One huge advantage of Haskell's static type system is "type erasure"; the types tend to go away at compile time and you get static function dispatch. This is also true of C and most of C++ aside from virtual function calls. On the other hand, in the SICP implementation of Complex you end up with all these type tags at runtime which are used for dynamic dispatch. Feel free to correct me if I misunderstood that part of the implementation.

Re: not to be a jerk, but...

[pozorvlak.livejournal.com]

Yeah, that's my understanding too. Years of writing data-munging code in Perl have left me somewhat blasé about performance, I'll admit - something that would surely change if I were to start writing games or rendering software or scientific number-crunching code or anything else CPU-intensive. On the other hand, I believe that Common Lisp compilers often produce comparably fast code to C: though the dynamism can slow things down, you often don't actually use it and it can be optimised away. The same may go for Scheme, I'm not sure.