Overloading in math
A few months ago Joe Marshall did a series of posts about how computer science has affected his view of math, beginning with its surpising lack of rigor: unlike programming languages, math notation is often ambiguous.
Check out these two equations:
By the first equation, Q is obviously some sort of function (the quantile function). H therefore operates on a function. By the second equation, the argument to H, which is called x, is used as the argument to f, which is the probability distribution function. f maps numbers to numbers, so x is a number. The types don't match.
This type error is precisely why this notation works. We can write Q to mean both a function and its result (or, to put it differently, both a quantity and a function relating that quantity to something else) because the types differentiate them. It's just like overloading in programming languages, but it's more pervasive, and it's not declared in advance, and one of the overloaded variables isn't even a function.
Indeed, if both Qs were functions, or even if Q returned another function instead of a number, this overloading wouldn't work. It would be too easy to confuse the two. But since their types are so different, we can safely overload arbitrary variables with the functions that compute them, and only programmers will be confused.
Programmers are paranoid about ambiguous notation, because computers can't be trusted to resolve it right. Mathematicians are much less so, because humans handle it better.
I think we can learn something from the mathematicians here. Language designers sometimes reject new overloadings for fear they'd be confusing, even if they wouldn't pose a problem for compilers. For example, overloading arithmetic operations to work on collections or functions sounds scary — wouldn't it be hard to tell what was being added and what was just being mapped or composed? But similarly wide-ranging overloadings in mathematical notation don't cause much trouble, and indeed these specific overloadings exist and work fine in APL and J. When a new construct looks confusing to humans but not to machines, that may be a sign that it's just unfamiliar.
Languages with one user
I don't usually read the reddit comments on my posts, because the signal-to-noise ratio is not that high, and because the "Arcane totally doesn't get it" comments are discouraging. But this means I miss some good ones. Xach said:
When a language has only one user, who is also the implementor, badly interacting patterns don't always become obvious. The tendency is to automatically avoid problematic things without thinking about it.
Good point. I will remember this next time I start to say "...but it doesn't seem to be a problem in practice."
Mainstream at last!
Functional programming is slowly becoming popular. Yesterday I heard someone refer to Haskell as a "mainstream language". ^_^
Labels: haskell
Eliminate unsightly warnings!
Compiler warnings getting you down? People complaining about all the "weird garbage" printed when they type make? Fear not — there's a solution!
A while ago I had occasion to build a particular (over)complicated project that had recently been ported from Windows to Unix. The Windows version spewed pages of warnings when building, but on Unix there was none of that — just an empty terminal with a helpful success message.
Wait a minute...
At the end of the makefile's default rule, I found this:
clear
echo Done building $(TARGET)!I hope you wouldn't consider doing anything like that. Now, if you'll excuse me, I have so many warnings to look at...
Errors
About signaling conditions in Common Lisp, Nikodemus Siivola writes:
Use #'ERROR to signal conditions inheriting from SERIOUS-CONDITION. This includes all subclasses or ERROR. SERIOUS-CONDITION is a convention that means "this will land you in the debugger if not handled", which is what #'ERROR ensures.
- Inherit from ERROR if unwinding from the error leaves the system in a consistent state. Subclasses of ERROR mean "oops, we have a problem, but it's OK to unwind."
- Inherit from SERIOUS-CONDITION, not ERROR, if the system is messed up somehow, and/or requires either human intervention or special knowledge about the situation to resolve: SERIOUS-CONDITIONs that are not ERRORs mean that "something is deeply wrong and you should know what you are doing if you are going to resolve this."
There are two problems with this interpretation.
First, it gives meaning to a difference type: (and serious-condition (not error)) means something beyond what serious-condition alone means. You could interpret this as "serious-condition means we can't continue; error means we can exit safely" - but non-serious-condition signals also mean we can exit safely. So the conditions that can be handled safely are (and condition (or (not serious-condition) error)). This complex type is at least a warning sign. If you want to distinguish recoverable from unrecoverable conditions, shouldn't one or the other have its own class?
Second, it's not what the Hyperspec says. It defines an error as
a situation in which the semantics of a program are not specified, and in which the consequences are undefined
and a serious condition as
a situation that is generally sufficiently severe that entry into the debugger should be expected if the condition is signaled but not handled.
These aren't the most lucid definitions, but the idea is that serious-condition means the signal can't be ignored, and error means this is because the semantics are undefined. (and serious-condition (not error)), therefore, is a situation where the semantics are defined, but where execution nonetheless cannot continue for some other reason - running out of memory, for instance. The distinction isn't between well-behaved states and messed-up ones, but between semantic nonsense and other failures. C++ has an analogous distinction between logic_error, which is the same as CL's error, and runtime_error, which covers the rest of CL's serious-condition. (C++ has only terminating exceptions, so it doesn't have non-serious conditions.)
I'm tempted to make more such distinctions, giving something like this:
- Nonsense: the program has asked for something undefined, like
(+ '(hello) "world!"). (CLerror, C++logic_error) You can define a reasonable meaning for most nonsense errors; they are errors only because their meaning hasn't been defined yet. - Limitation: the implementation knows what you mean, but can't deliver, e.g. arithmetic overflow or running out of memory. (RNRS calls this a "violation of an implementation restriction".) You could consider "not yet implemented" to be a limitation as well.
- Environmental failure: the operation failed because the outside world did not cooperate, e.g. a file was not found or a connection was refused.
- Forbidden: operations which do have an well-defined meaning, but you're not allowed to do them, usually for security or safety reasons, e.g. you don't have permission to
unlink("/").
In other words, "I don't understand", "I can't", "It's not working", and "I'm sorry, Dave. I'm afraid I can't do that.".
This is a nice taxonomy, but I'm not sure it's actually useful. The problem is that one error often leads to another, and the error that's detected isn't necessarily the original problem. For instance, failure to open a nonexistent file (an environmental failure) may manifest as a nonsensical attempt to read from an invalid stream. (CL actually signals it as an error, even though it's not a semantic error, perhaps for this reason.) Or a fixed-size buffer (a limitation) causes a buffer overflow (nonsense) which is eventually detected as a segfault (a forbidden operation). Why try to distinguish between classes of errors when they're so fluid?
Fortunately, programs don't usually care why they failed, unless it was a certain specific error they were expecting. IME most exception handlers are either quite broad (e.g. catching serious-condition near the root of a large computation), and recover in generic ways such as aborting, or quite specific (e.g. catching file-not-found-error on one particular open), and attempt to deal with the problem. There aren't many handlers that try to generalize at intermediate levels, even in languages that support them.
So maybe it's not so useful to classify exceptions by their cause. Maybe we should instead classify them by the possible responses: things like whether they can be ignored (CL's serious-condition) and whether they can be handled at all. In that case Nikodemus' interpretation of (and serious_condition (not error)) as "unrecoverable error" is right — not for CL, but for some future language.
Labels: common-lisp
Ambivalent about anaphors
I like anaphoric macros like aif and aand, but that a- is rather opaque. If you didn't know what it stood for, would you ever guess "anaphoric", or have a clue what the macros did?
Abstruse naming conventions are nothing new — how long have Lispers been using -p for predicates? — but that's no reason to inflict more of them. Is there a less exotic affix for anaphoric macros? Probably not, because it has to be short to be useful, and anything that short will be pretty opaque.
In any case, I'm not sure separate anaphoric macros are the right idea. It's nice to be able to bind a variable by adding a single character to a name, but it's not general. It won't work with a newly defined macro until someone defines an anaphoric variant, which realistically won't happen very often. Maybe that doesn't matter, since you can always fall back on let.
I wonder if it wouldn't be better to be like Perl, and make everything anaphoric. If the normal versions of if and progn bound a variable (perhaps with a more distinctive name than it?), then new macros based on them would too. This sounds nightmarishly unpredictable, since a newly defined macro might use several anaphoric constructs, and the innermost is not necessarily the one you want. It works for and but not for (the naive definition of) case, for instance.
Rampant anaphora might also pose a maintenance hazard, since simple transformations of code may change their referents. However, I haven't heard that this is a big problem in Perl. I suspect this is because people normally base their changes on a mental model of local dataflow, and in Perl, this model includes $_. Unfortunately I don't have enough Perl experience to check this on myself.
I would like to dismiss anaphora on the grounds that they don't compose well: while one aif can make an expression much simpler, a second will often conflict with the first. But this isn't a very distinctive fault. Many useful constructs are hard to compose — even function composition, ironically — and anaphoric macros are too handy to ignore.
Identity of numbers in Common Lisp and Maclisp
Nick Levine asks:
If anyone knows of a Common Lisp implementation for which (eq 3 3) need not be true, could they get back to me? I know what the Spec says about this but have difficulty believing it.
Commenters duly reply that ABCL and some versions of GCL do sometimes have multiple fixnums with the same value. Basically, this can happen in any implementation that uses boxed fixnums and doesn't intern them.
But this is not the only thing that can happen to fixnum identity. Common Lisp allows much worse:
An implementation is permitted to make "copies" of characters and numbers at any time.
This is an ugly thing to have in a language with otherwise straightforward object semantics. CLtL explains:
In general, numbers in Common Lisp are not true objects;
eqcannot be counted upon to operate on them reliably. In particular, it is possible that the expression(let ((x z) (y z)) (eq x y))may be false rather than true if the value of
zis a number.Rationale: This odd breakdown of
eqin the case of numbers allows the implementor enough design freedom to produce exceptionally efficient numerical code on conventional architectures. MacLisp requires this freedom, for example, in order to produce compiled numerical code equal in speed to Fortran. Common Lisp makes this same restriction, if not for this freedom, then at least for the sake of compatibility.
If I understand correctly, the rationale refers to how PDP-10 Maclisp handled arithmetic. It used boxed numbers, and to reduce allocation it often kept them on temporary stacks. This created a problem when a stack-allocated number had to escape and become a permanent value:
Some operations, such as storing a number in a special variable, or RPLAC'ing it into a cons, clearly require permanent allocation of the number. However, in order to allow allocation-free numeric computation, PDP-10 Lisp allows the passing of "intermediate" numeric results between functions without allocating them. Because of this, a function receiving any argument which cannot be positively verified at compile time as not being a pointer to a "temporary" number ("PDL number") must be extremely circumspect about what it does with that argument, in fact, calling a runtime routine named
PDLNMKwhenever a result of "unknown parentage" is stored into a permanent place. The routine checks to see if the result being stored is in fact a pointer to a PDL number, and allocates it permanently if so.
Steele's Fast Arithmetic in MacLISP provides more detail: NCOMPLR reallocated numbers whenever they escaped and had to become permanent, so it sometimes allocated a single value more than once, producing multiple non-eq copies.
The same problem arises with deboxing optimizations in other compilers. Most deboxing compilers, however, are careful to avoid multiple reboxing, for performance reasons: they don't want to embarrass themselves by accidentally allocating even more numbers than they would with naive boxed arithmetic. This has the convenient side effect of preserving identity of numbers.
So while Common Lisp allows implementations to copy numbers at will, I suspect this is purely a historical relic, "rooted in NCOMPLR" rather than in any practical need. Has there ever been an implementation that exploited it?
Labels: common-lisp
