Subject: Re: MD5 in LISP and abstraction inversions
From: Erik Naggum <>
Date: Sat, 17 Nov 2001 04:14:00 GMT
Newsgroups: comp.lang.lisp
Message-ID: <>

* Bruce Hoult
| I see that CL doesn't define < for complex numbers.  Dylan does but says 
| the results are implementation-dependent.

  Why?  Are there any other parts of mathematics that are implementation-
  dependent?  One of C's really bad implementation-dependent features is
  the return value of some form of integer division by negative numbers.
  It is so obscure that most C programmers are completely unaware of it,
  but it bites hard when it bites.  The same applies to the sign of char,
  which is extremely annoying when it suddenly changes on you just because
  you port to a new machine.  I think a language specification should try
  to limit the freedom of implementations in these areas, not increase it
  just because of some rinkytink hardware that gets it wrong.

| < should be a total ordering.  If you can't make it a total ordering for
| your type then don't define it at all.

  It is not "your type" I am concerned about, but the interaction of all
  types in the system, the complexity of which increases very quickly as
  you add types.  If (< a b) is well-defined, and (< b c) is well-defined,
  is (< a b c) and (< a c) also well-defined?  They may not be.  The key to
  the genericity of < in CL is that it works on _all_ (real) numbers, mixed
  and matched however you want.  I expect this to apply to user-defined
  number types, too, but that is precisely where there be dragons.

| It's the programmer's responsibility to ensure that it holds.  The 
| compiler can't check it, but it is allowed to assume that it holds.

  This is simply a cheap cop-out.  If a language gives programmers tools
  that affect fundamental invariants, it is flat out irresponsible if it
  does not give the programmers tools to ascertain that those invariants
  are not violated.

| There are plenty of parallel situations in any programming language.

  True, but that is not a good reason to create more of them.

| You want to define < on lists to mean "shorter than"?  Well, OK.  At 
| least you'll agree it's a total ordering.

  I think I may have to find some neon-sign-like fonts and have the word
  "EXAMPLE" made out of it and then make it flash.  Please get the point of
  the example, and drop the specifics of the example.  They work just like
  analogies: At some point or another, they become irrelevant to the point
  being communicated.

  In this case, I wanted to point out that there are convenience reasons to
  make certain things _equally_ hard.  Adding a new method on < seems to be
  easy, but it is in fact extremely hard, because the programmer needs to
  keep the fundamental invariants of all the types involved intact, and
  that requires a lot more computer science than you get from example code
  in books on OO.  In my view, real programmers will not _want_ to add a
  method on < for a user-defined types because it causes many more problems
  than it solves, and is actually much harder than writing type-specialized

| Dylan side-steps the issue of generic function dispatch on multiple
| arguments, because < takes only two arguments in the first place.  If
| you want the CL operation then you need to use reduce().

  Huh?  As far as I can see, the return value of the function will be used
  as one of its arguments for the next element in the sequence for reduce
  to work.  (reduce #'< '(1 2 3)) would cause cause reduce to make the call
  equivalent to (< t 3).  This is true for both both Common Lisp and Dylan,
  so I wonder what you had in mind.

| Efficiently checking that a set of lists are ordering from shortest to
| longest strikes me as such a specialized thing that you really can't
| avoid a specially written function to do that.

  You make assumptions at break-neck speed and crash into things.  Please
  be more careful.  The intention of bringing up this *EXAMPLE* was to show
  that multiple types of arguments in the same function call would pose
  problems.  Remember that Common Lisp does not use a binary <, only.  With
  just a little effort, you should have seen (length< 2 foo 4) as an
  application of this function, where foo is some sequence and 2 and 4 are
  the regular integers.  And it is obviously not just < that goes into this
  set of length-comparing functions.  (length= foo bar zot) is a lot more
  useful than you might think if you stare yourself blind at length<.

| You appear to be thinking that the best way to do it is to iterate
| through all the lists in parallel, and return false if the first list to
| be exhausted is not the first one (and then drop the first list and
| repeat...).  That would be true if you're expecting a list somewhere in
| the middle or towards the end to be dramatically shorter than it "should"
| be, but it's not the best if it turns out that there's a problem with an
| early list.

  This is completely beside the point, but a "problem"?  What "problem"?

> I think the notion of adding methods to a generic function for a purely
> mathematical function like < stems from a lack of reasonable builtin
> support for the necessary numeric types.  I mean, how often _should_  you
> need to add a new kind of number class to a system?

| That depends on what type of work you're doing.

  No, that is backwards.  Since we are talking about language design, it
  depends on what the language specification should require of the
  implementation, hence the "should".  The language should not impose on
  the _application_ to make these kinds of type additions _unnecessarily_.
  It should also not impose on every application that does not need this
  infrastructure the cost of having it available.  In a dynamically typed
  language, there are significant costs associated with the mere existence
  of user-defined methods on primitive mathematical function.  Moreover,
  the language does in fact provide you with the means to get a more
  elaborate dynamism, but it would be _much_ harder to get the efficient
  implementation of a non- generic < operator, especially if the problem is
  that all the callers of this function would call the generic version.

> Rather than optimize for this extremely unlikely need, optmizing for the
> most likely need, i.e., using the existing number classes, seems like
> good engineering.

| There is no incompatability between the two.

  So generic dispatch is cost-free?  Sorry, this flies in the face of facts.

  Norway is now run by a priest from the fundamentalist Christian People's
  Party, the fifth largest party representing one eighth of the electorate.
  Carrying a Swiss Army pocket knife in Oslo, Norway, is a criminal offense.