Showing posts with label scheme. Show all posts
Showing posts with label scheme. Show all posts

If Scheme were like Scheme

Scheme's numbers are not like the rest of its library. They're older, and they're mostly borrowed from other languages (Maclisp and Common Lisp), so they follow those languages' style rather than Scheme's. They're designed more for the convenience of users than of theorists; they have a usefully complete feature set; they have a printed representation; their operations are predefined and polymorphic and have very short names.

What would Scheme be like if numbers followed the same style as the rest of the language?

It would be necessary to import a library before using any numbers.

(import (scheme numbers))

Numeric constants would be provided as functions returning the constant, apparently because the section of RNRS they appear in is called “Standard Procedures”. Only the most basic constants would be provided; pi would not be among them.

(define (exact-rational-zero)
  (make-exact-rational (exact-integer-zero) (exact-integer-one)))

Numbers would have no printed representation. Creating them would require explicit constructor calls.

There would be no polymorphism. Most operations would include a type in their name.

(define (factorial n)
  (if (exact-integer<=? n (exact-integer-one))
    (exact-integer-one)
    (exact-integer-multiply! (factorial (exact-integer-subtract n (exact-integer-one))) n)))

The distinction between exact and inexact numbers would still be supposedly “orthogonal to the dimension of type”. But the lack of polymorphism would make it even more obvious that in practice exactness was simply one of the type distinctions: that between floats and everything else.

Floating-point numbers would be called “inexact rationals”. Their constructor would take a numerator and denominator, just like exact rationals; their floating-point representation would be considered an implementation detail. Various details of the specification would be inconsistent with IEEE floating point.

NaN would not be a number, of course. inf.0 and -inf.0 would be exact transfinite numbers, not inexact rationals. There would be no negative zero.

Names would be descriptive, like inexact-rational-square-root and exact-integer-greatest-common-divisor.

There would be exact-integer->list and list->exact-integer operations to convert to and from lists of digits (in arbitrary bases). Converting the lists into strings would be up to you. Converting anything other than exact integers to strings would also be up to you.

Numbers would be portably mutable. Some operations would have destructive versions. (If we did this exercise on Python, some would have only destructive versions.) Racket would omit these, supposedly to make optimization easier, but would have separate mutable numbers for programs that need them.

Operations more obscure than exponent would be left to SRFIs. Users would be able to choose between the widely supported SRFI and the complete SRFI.

exact-integer-divide would not be provided, on the grounds that it's not defined for all integers, and can't be implemented efficiently without special hardware.

There would be a portable way to use exact integers as indexes into lists, but not into vectors or strings. This would be remedied in R7RS.

Some implementations would support surprisingly obscure and practical floating-point operations, while omitting basic operations their authors never needed.

(define (numerically-stable? thunk tolerance)
  "Run a floating-point computation with various rounding modes to see
if this significantly changes the result. This is not a reliable test
of numeric stability, but it's an easy way to find bugs."
  (let ((down (call-with-rounding-mode round-down thunk))
        (up (call-with-rounding-mode round-up thunk))
        (nearest (call-with-rounding-mode round-to-nearest thunk))
        (zero (call-with-rounding-mode round-to-zero thunk))
        (roughly-equal? (lambda (a b)
                         (inexact-rational<=?
                          (inexact-rational-absolute-value
                           (inexact-rational-subtract a b))
                          tolerance)))))
    (and (roughly-equal? down up)
         (roughly-equal? down nearest)
         (roughly-equal? down zero)
         (roughly-equal? up nearest)
         (roughly-equal? up zero)
         (roughly-equal? nearest zero)))

There would be debates about whether eq? should “work” on numbers. This would really be about whether numeric operations should always return fresh numbers, and whether the compiler would be allowed to copy them, but no one would mention these merely implementational issues.

eqv? and equal? would compare numbers, even immutable ones, by identity. Hashtables would — OK, standard Scheme doesn't have hashtables. But if it did, the default hash function would hash numbers by identity, not by value.

Arithmetic overflow would still be “a violation of an implementation restriction”. There would still be no way to find out how large a number could safely be.

There would still be no bitwise operations on integers. Schemers who understood the purpose would advise using an implementation that supports bitvectors instead of abusing numbers. Those who did not would say they're easy to implement.

(define two (exact-integer-add (exact-integer-one) (exact-integer-one)))
(define (exact-integer-bitwise-and a b)
  (list->exact-integer (map exact-integer-minimum
                            (exact-integer->list a two)
                            (exact-integer->list b two))))

Complex numbers would, mercifully, be left to a SRFI. The SRFI number would be real, but in most implementations complex-number support would be purely imaginary.

All the comparison predicates would end in ?.

Edit: Replaced some stray uses of <= and + and min with their counterfactual-Scheme equivalents.

In the HN comments, cousin_it says:

We can see similar examples in other languages, e.g. C++ strings are "like C++" and a pain to use, while Java strings are "not like Java" and a pleasure to use. Maybe language design really isn't about general-purpose elegance, but about finding good special-purpose solutions.

Or about using the good general-purpose solutions you already have.

current-jiffy is not usable portably

In addition to current-second, the R7RS draft adds a timer function, current-jiffy. Obviously the Theoretical Right Thing for a timer is a high-resolution version of the same linear timescale used for dates, which current-second can (in an ideal implementation) provide. But in some applications (especially the rather important one of profiling), the timer can be called very frequently, so it must avoid allocation, which means either returning a fixnum or modifying some sort of mutable timer object. This is the point of current-jiffy.1

The main use case is something like this:

;;; Evaluate the body. Return multiple values: the time taken in
;;; seconds, followed by whatever values the body returned.
;;; This returns the time in seconds, not jiffies, for human
;;; readability. It returns the time as a number, rather than
;;; printing it somewhere, so it can be used programmatically.
(define-syntax time
  (syntax-rules ()
    ((time forms ...)
     (let ((start (current-jiffy)))
       (let-values ((vals (begin forms ...)))
         (apply values (/ (mod (- (current-jiffy) start) jiffy-modulus)
                          (jiffies-per-second))
                       vals))))))
> (time (/ (factorial 100) (factorial 99)))
0.0124525432
100 ;hopefully

Presumably R7RS-large will include such a macro. (time? elapsed-time? profile? bench?) But in the current R7RS-small, users can't portably write it, or do anything else with jiffies reliably, because they can't deal with overflow.

High-precision fixnum timers overflow fast. A 32-bit microsecond clock, for instance, overflows every 71 minutes, and a 30-bit fixnum every 17 minutes. This is too frequent to ignore, so all subtraction and comparison of jiffies needs to be modulo the word size, so all programs using current-jiffy need to know jiffy-modulus. In theory they could determine it by experiment, but that takes a while and is imprecise, so in practice portable code can't use current-jiffy for anything but setting random seeds.

This could be fixed by adding jiffy-modulus (jiffy-limit? max-jiffies?) to the standard. But since current-second already covers timing fairly well, it might be better to leave current-jiffy to R7RS-large. Efficient timers are a useful feature, but not one that belongs in Small Scheme.

By the way, shouldn't jiffies-per-second be a constant, not a function? It's in the section called “Standard Procedures”, which does not describe a numeric constant, but it's better to change the title of the section (Standard Definitions? Standard Procedures and Constants?) than to change the language to fit the title.

1IIUC it originally had another point: to provide a linear timescale even if current-second didn't. But now that current-second is supposed to provide TAI, current-jiffy is no longer needed for this, and even if current-second only provides disguised POSIX time, its nonlinearities are infrequent enough for most applications to ignore.

The Scheme that specifies TAI is not the eternal Scheme

The R7RS draft fixes a longstanding hole by adding the simplest possible time function: current-second, which returns the time since 1970 in seconds.

Unfortunately, it specifies that the timescale used is TAI. This is overspecification. The advantage of TAI over POSIX time is linearity (POSIX time jumps backward at leap seconds, so it's ambiguous, and time arithmetic gives incorrect results), but R7RS acknowledges that most implementations will compute it by simply subtracting a constant from their system clock. In addition to not being correct TAI and being gratuitously incompatible with POSIX, the resulting timescale remains ambiguous and nonlinear, so it has no advantage over POSIX time. Why specify a feature when you know it won't work?

I agree that the POSIX timescale is messed up, but this is not something languages can fix. As long as time is provided by the operating system, the choice of timescale is up to the operating system.

Also, time standards have historically been replaced fairly often, so Scheme risks specifying an obsolete standard which no one else uses. It's safer to simply leave the timescale and epoch unspecified, and let current-second be the system clock, whatever it is.

Oft-omitted features should be optional

Language implementors struggle with specifications. Those writing to a spec generally want to follow it, but unlike the authors of the spec, they face problems of implementability. When a standard specifies a feature that is too difficult to implement, or that interferes with performance or other desiderata, some implementors will simply omit it, whatever the language standard says.

Scheme has two features that are particularly annoying to implementors, because they affect how procedure calls are compiled: call-with-current-continuation and tail call optimization. Many implementations, particularly those that aim to interoperate with another language, don't implement them. In JScheme and Kawa, continuations only work outward: call/cc is call/ec. Kawa optimizes local tail recursion, but not tail calls in general. Their implementors would have preferred to follow R5RS, but they decided it was not practical to do so — they felt performance and compatibility with Java were more important than strict compliance with the standard.

To reduce the burden on implementors, the Scheme Reports have long declared some features optional. Most of the numeric tower is optional, and various standard procedures have been marked as optional in some versions. This has been a great help to implementors, who have been able to implement Scheme without worrying about little-used features like complex arithmetic, and has probably contributed to the large number of implementations.

Full continuations and nonlocal tail-call optimization are also little-used features — despite their general utility, few programs rely on either. Implementors know this, which is why they're willing to omit them, even if the standard does not. Users do not appear to consider this omission a serious flaw; JScheme and Kawa are generally considered serious, full-featured implementations, not incomplete toys. In existing practice, call-with-current-continuation and tail call optimization are optional.

Oleg has already proposed making call/cc officially optional, and I agree. Implementors and users treat it as optional, so the standard should too.

In Oleg's proposal, both call/cc and dynamic-wind are optional, and can be omitted entirely. This is unnecessarily disruptive, as it breaks the many programs that use call/cc only for escape continuations and dynamic-wind only for unwind-protect. I suggest a more conservative change: require call/cc to provide at least escape continuations, but make full reusable continuations optional. (There should be a cond-expand feature for this — full-continuations? full-call/cc? reusable-continuations? indefinite-extent-continuations? Just call-with-current-continuation?) This preserves compatibility for almost all programs, while removing one of the greatest burdens on implementors, so there will continue to be many good implementations of Scheme, even as it standardizes other implementation challenges like define-record-type and parameters and exceptions.

The same goes for other features that are difficult to implement. If neither implementors nor users think a feature is necessary, the language standard should acknowledge this, rather than condemn part of its community as noncompliant.

“Irritants”

I laughed when I first saw the arglist for R6RS's error:

(error who msg irritant1 ...)

There are irritants in the Scheme oyster, and error pearls them away for later reference. Cute!

“Irritant” is not a new term; it's existed in Scheme culture for a long time. The earliest reference I can find is in a Maclisp Scheme info file last modified in 1985, and it has turned up occasionally on the rrrs-authors mailing list. I haven't found it in any non-Scheme manuals (yet). Is it a Scheme-only term? Does anyone know where it originated?

For a while, the cuteness blinded me to a possible confusion: “irritants” suggests that the arguments should be the cause of the error — that they should be in some sense wrong or invalid. But they're only informative, and are often innocent indicators, not the causes of the irritation.

A format string and arguments is probably better, because it makes clearer messages. Or simply a string, in a language with string interpolation. Even though this doesn't call for a cute name.

Square in R7RS

It's one of the most trivial library functions ever:

(define (square x) (* x x))

But I've written it many times, and I'm not alone. So it was a pleasant surprise to see that WG1 recently voted to add it to R7RS.

The request gave the (weak) reason that it could have an optimized method for bignums, but voter comments suggest they were more interested in symmetry with sqrt. They also added make-list for symmetry with make-vector. I don't think symmetry is a good reason in either case, let alone sufficient reason to add features to Small Scheme, but square is attractive as a convenience.

It's not the most important feature (and it probably belongs in Big Scheme, not Small Scheme), but it's a small step forward. Every language that aims to be convenient should have square in its standard library.

Thou art thyself, though not a Scheme

Is there any part of a language so obviously unimportant as its name? PLT Scheme was recently renamed to Racket, but it's just a name change; the language is the same as before (or at least isn't changing faster than usual). I was rather surprised to hear of this (I fleetingly thought it was April) since the old name is so well known, but apparently the PLTers think their language will be better off if it's not associated with other Schemes. Anyway, the change shouldn't affect anyone who knows, right?

But it does affect me. Yesterday I was lamenting how little of Scheme is portable across implementations, and found myself thinking, “wait, that doesn't apply to PLT Scheme any more, because it's Racket now”. Even though I know there's no difference, I tend to see PLT Scheme as a Scheme with nonportable extensions, and Racket as an independent language. The new name is working: it makes me take Racket more seriously as a platform, not just an implementation.

(However, I keep mistaking it for “Rocket”.)

Some things never change

Mike Taylor is having a bad initial experience with Scheme. In particular:

As I continue to work my way through the exercises (using Scheme itself at least for now), I run into a problem: for exercise 2.9.3 I need set-car!, which the purity-fascist maintainers of PLT Scheme removed in release 4.0. No doubt there is a secret incantation to undo this change, but I can’t immediately see what it is.

As he has already figured out, this is because he's using an R5RS book with an R6RS-ish implementation, and R6RS DrScheme's dialect is not a superset of R5RS — not even of the commonly taught parts of R5RS. Such conspicuous backward incompatibilities occasionally strike other languages (Perl, certainly, and hasn't it happened to Python at some point?) but it's more embarrassing in a language like Scheme, which is supposed to be old and elegant and stable.

Correction: as Eli Barzilay points out, it's supposed to be an R6RS book. The use of set-c*r! without the necessary (import (rnrs mutable-pairs)) is probably an oversight, made easy by the fact that it still works in most R6RS implementations. So part of the problem here is that the book is buggy: it uses features that aren't in the language it's teaching. Also, DrScheme's main language isn't R6RS but a different dialect which also happens to lack set-car!.

It's also unfortunate in a language which already has a reputation for being impractical. Mike correctly attributed the problem to “purity-fascist maintainers”, but how many other students, on seeing that Scheme's most popular educational implementation doesn't (by default) support the examples used in popular tutorials, have concluded (or confirmed their prejudice) that Lisp is not useful outside of the ivory tower?

(I don't particularly mind immutable lists, but they're a strange thing to break backward compatibility over.)

Pitfalls for who?

SISC has a test suite for R5RS Pitfalls. Most of these are ordinary compliance tests, that test the implementation's completeness or robustness or up-to-date-ness. But several are tests of perverse implications of the standard, where a reasonable person might say R5RS is overspecified or even wrong. In particular, the first two test the interaction of letrec with call/ccletrec is supposed to evaluate all the init-forms before setting any of the variables, effectively requiring an extra layer of variables. This is not obviously better than the simpler definition which initializes one variable at a time. This is less a test of the implementation's quality than of what lengths it's willing to go to to follow the letter of the standard.

The existence of tests like these — and the number of implementations that fail them — says something about how clean a language is. When expert users are surprised by something in a language, and implementors often get it wrong, this suggests a problem in the spec. In these cases, compliance tests can illuminate what parts of the language are ugliest, and why. For Scheme, it looks like the problems are in details that would ordinarily be invisible, but that are exposed by call/cc or syntax-rules. This is a situation where it's easy for language designers to make mistakes, because they don't even realize what they're specifying.

Sometimes, if a spec is widely agreed to be buggy, everyone will just ignore it. SISC's test suite contains a test for whether let-syntax creates a contour for internal define. The test follows the consensus of implementors in saying that R5RS is wrong, and that a good implementation should ignore it on this point. Scheme culture values formality, but apparently there is a limit to how much inconvenience they are willing to put up with for it. Language designers, take note.