New wine in old bottles, or, Adding plugins to procedures in Scheme

[John Cowan]

[-srfi-194]

[+scheme-reports-wg2]

On the SRFI 194 mailing list, on Mon, Aug 24, 2020 at 12:02 PM Marc Nieper-Wißkirchen <ma...@nieper-wisskirchen.de> wrote:

The Householder reflection needs a hermitian scalar product (including
a real scalar product as the general case). Thus, if you want to
generalize it over rings other than , ℂ, or ℍ, you would have to
axiomatize the complex/quaternionic conjugation as well, making the
resulting mathematical structures quite special.

While I generally agree that we should try to enable the use of rings
and modules when no more is needed, in this particular case
restricting to , ℂ, and ℍ has (besides the above argument) the
advantage that, at least,  and ℂ are already built into Scheme. We
could ask for an extension of the numeric tower to ℍ (which would make
perfect sense), in which we just need the usual generic numerical
operations of section 6.2 of the R7RS.

You can ask, but you aren't likely to get, except as an optional extension to R7RS-small.  Most Scheme implementers will almost certainly say that the extension of the numeric tower to complex numbers is quite expensive enough for a rarely used feature of the language (which is why it's in a separate R7RS-small library, so that in principle a program can signal that it does not use non-real numbers), and the further extension to quaternions has an even less favorable cost/benefit ratio.  No Scheme that I know of exposes a way to add new types to the tower.

(Note: In this posting "generic", except in the phrase "generic function", refers to the standard numeric types of Scheme.)

Using the library system is not really satisfactory.  Suppose you want to add quaternions. You can create generic-plus-quaternion procedures like h+, h-, h*, h/ in a library, and then import them under the names of +, -, *, /.  This will work, but you have to carry it through *all* the procedures that accept numbers.  In particular, you have to make sure that all the libraries, whether from the implementation, you, or some third party, have been properly overridden, or a quaternion object will not even be recognized as a number, not to mention handled properly.  (Chicken 4 had this problem: native numbers were just fixnums and flonums, and you had to import the numbers egg to get a full tower, but mixing modules that imported the egg with modules that didn't gave bad results.  Chicken 5 has a built-in tower for that reason.)

To make things worse, suppose you want to add an orthogonal feature to the numeric tower, perhaps SRFI 73 exact infinities.  Now you not only need to override a (possibly different) set of generic math procedures, but you need to have three kinds of overrides: for generic-plus-quaternion, for generic-plus-1/0, and for generic-plus-both.  The geometric explosion will soon kill you.

Now there are two basic ways to make the explosion easier to manage: generic functions and typeclasses.  If we create generic functions ++, --, **, //, then these can be set up with methods to handle standard Scheme numbers, quaternions, exact infinities, octonions, or anything else you could possibly call a number.  There is still a geometric explosion because you need to handle (++ z z), which is just (+ z z); (++ h h); (++ h z); and (++ z h). However, by supporting predicate subsumption and declaring that quaternion? subsumes number?, and providing a function `quaternion` to convert a number to a quaternion, we can reduce this to two cases: (+ z z) and (++ (quaternion <>)  (quaternion <>)).

The disadvantage is that a dispatch framework (although not a very complex one) must be created and standardized.  Chibi has such a framework already, but without subsumption: it assumes that earlier-defined methods subsume later-defined ones.  Some Schemes are class-based and so already have generic functions and subsumption, but the predicates are limited to the form (is-type <> class).  Finally, there are various more or less portable OO frameworks that include generic functions, usually restricted in the same way.  Still, once that is done, you can import ++ as + and get the behavior you want.

The other option is a typeclass object, a record of procedures that specify how to do all the primitive operations of a given type.  This requires no run-time dispatching, but it requires the typeclass to be passed explicitly, and therefore procedures like +++, ---, ***, /// must be called like (+++ numeric-class n n).  This provides complete flexibility: you can have four typeclass objects (one for each combination) or two with internal quaternion vs. generic dispatching, or even just one (in which case typeclasses provide no benefit). In the case of numbers, it's feasible to do dispatching to a registered instance of the typeclass (which will normally include a type predicate as one of its procedures), thus eliminating the need to pass a typeclass object explicitly.

Note that these approaches resolve only the multiple-plugin problem; the problem of needing pervasive import remains if you want to use + to mean ++ or +++.

John Cowan          http://vrici.lojban.org/~cowan        co...@ccil.org
The peculiar excellence of comedy is its excellent fooling, and Aristophanes's
claim to immortality is based upon one title only: he was a master maker
of comedy, he could fool excellently.  Here Gilbert stands side by side
with him.  He, too, could write the most admirable nonsense.  There has
never been better fooling than his, and a comparison with him carries
nothing derogatory to the great Athenian. --Edith Hamilton, The Greek Way

[Lassi Kortela]

> If we create generic functions ++, --, **, //, then these can be set up
> with methods to handle standard Scheme numbers, quaternions, exact
> infinities, octonions, or anything else you could possibly call a
> number.  There is still a geometric explosion because you need to handle
> (++ z z), which is just (+ z z); (++ h h); (++ h z); and (++ z h).
> However, by supporting predicate subsumption and declaring that
> quaternion? subsumes number?, and providing a function `quaternion` to
> convert a number to a quaternion, we can reduce this to two cases: (+ z
> z) and (++ (quaternion <>)  (quaternion <>)).

Probably would be wise to overload the standard numerical operations + -
* etc. Having special numeric operators with a different name is usually
not well-liked (Ocaml dotted float operators, Java bignums).

There should be some way to have a fast path for the common case
(operating on two fixnums or floats). How do we do that? Probably not by
overloading + - * using a generic generic function framework.

One could think of a similar `generic-equal?` extensible to new types
(this was one of the initial motivations for Haskell typeclasses IIRC).

> Chibi has such a
> framework already, but without subsumption: it assumes that
> earlier-defined methods subsume later-defined ones.

First match wins and new methods are added at the end of the list?

[Marc Nieper-Wißkirchen]

My initial comment (on the SRFI 194 mailing list) that led to John's
post here was just about extending the numerical tower of Scheme not
only to include the complex numbers but also the quaternions. As much
as the complex numbers are optional in R7RS, the quaternions would
most likely be an optional feature as well. As the standard numerical
operations have to do type-dispatching anyway (especially when complex
numbers enter the mix), the actual cost to add quaternions does not
seem high, however. Most of the work would probably be to write a SRFI
extending section 6.2 of the R7RS.

Completely generic arithmetic operations (including extending the
number tower by the user) were outside my comment and its a different
kettle of fish:

(1) The current numeric tower (or one including the quaternions) is
mostly linear and there is no much room to extend it anyway (except
for the quaternions). So being able to user-extend the numeric tower
may be a bit pointless.

(2) General rings and fields do not fit into the linear order of the
numeric tower so the extension of the arithmetical operations to such
objects would be orthogonal to questions about the number tower and my
original question. However, for general rings, the usual arithmetical
syntax of the number tower would be too strict. On the same set of
elements, more than one sensible multiplication operation could be
defined, yet we only have one multiplication symbol to overload. In
other words, just looking at the types of the arguments of the
operation is not enough. (That's one reason why the C++ overloading
system is awkward for general computer algebra when operations can be
parameterized through runtime objects.) So, for the more general
applications, the typeclass (or however you want to call it) is the
only sensible way to proceed. I wouldn't overload the standard
arithmetical operations in this context, though. Let their scope be
limited to what numerical tower the implementation provides because
efficiency matters here.

Marc

> --
> You received this message because you are subscribed to the Google Groups "scheme-reports-wg2" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scheme-reports-...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/scheme-reports-wg2/a209b75d-6890-5b73-b7c4-67cae70ecc25%40lassi.io.

[Per Bothner]

On 8/24/20 10:51 PM, Marc Nieper-Wißkirchen wrote:
> My initial comment (on the SRFI 194 mailing list) ...

> was just about extending the numerical tower of Scheme not
> only to include the complex numbers but also the quaternions.

FWIW quaternions are built in to Kawa:

https://www.gnu.org/software/kawa/Quaternions.html

This work was mostly done by Jamison Hope (who I've cc'd but is probably not on this list).
--
--Per Bothner
p...@bothner.com http://per.bothner.com/

[Marc Nieper-Wißkirchen]

Am Di., 25. Aug. 2020 um 08:40 Uhr schrieb Per Bothner <p...@bothner.com>:
>
> On 8/24/20 10:51 PM, Marc Nieper-Wißkirchen wrote:
> > My initial comment (on the SRFI 194 mailing list) ...
> > was just about extending the numerical tower of Scheme not
> > only to include the complex numbers but also the quaternions.
>
> FWIW quaternions are built in to Kawa:
>
> https://www.gnu.org/software/kawa/Quaternions.html

That is exactly what I have had in mind! With this approach, the
numeric tower is extended seamlessly.

Maybe we can turn this into a SRFI for other implementations.

(Quaternions are certainly more useful than the exact complex numbers
that have been voted into R7RS-large.)

[Lassi Kortela]

>> https://www.gnu.org/software/kawa/Quaternions.html
>
> That is exactly what I have had in mind! With this approach, the
> numeric tower is extended seamlessly.
>
> Maybe we can turn this into a SRFI for other implementations.
>
> (Quaternions are certainly more useful than the exact complex numbers
> that have been voted into R7RS-large.)

We should think about how to integrate Scheme numbers and arrays into
the increasingly common machine learning / statistics frameworks.

Here some people are doing quaternions in PyTorch:
<https://github.com/facebookresearch/QuaterNet/blob/master/common/quaternion.py>.
A quaternion is represented as a "tensor of shape (*, 4), where *
denotes any number of dimensions".

Here are all the tensor types supported by PyTorch:
<https://pytorch.org/docs/stable/tensors.html>. Seems like almost the
same set of types as is supported by our homogeneous numeric vector SRFIs.

With machine learning, 16-bit floats are back in vogue and even have
hardware support (I'm not very familiar with GPUs, but apparently Nvidia
Pascal GPUs do half-floats).

[Linas Vepstas]

Repost, first post bounced!

On Tue, Aug 25, 2020 at 10:14 AM Linas Vepstas <linasv...@gmail.com> wrote:

On Tue, Aug 25, 2020 at 7:37 AM Lassi Kortela <la...@lassi.io> wrote:

>> https://www.gnu.org/software/kawa/Quaternions.html
>
> That is exactly what I have had in mind! With this approach, the
> numeric tower is extended seamlessly.
>
> Maybe we can turn this into a SRFI for other implementations.

After a very quick glance, the API there would seem very suitable for a srfi. The only thing missing would be a minor quibble: the ability to rotate a vector on a Bloch sphere, but that's one itty bitty function.

We should think about how to integrate Scheme numbers and arrays into
the increasingly common machine learning / statistics frameworks.

What is this saying?

Here are all the tensor types supported by PyTorch:
<https://pytorch.org/docs/stable/tensors.html>. Seems like almost the
same set of types as is supported by our homogeneous numeric vector SRFIs.

The tensors in pytorch are all "dense"/non-sparse. I'm very interested in having support for extremely sparse tensors, e.g. a matrix that is 1 million by 1 million, of which maybe a few hundred-million entries are non-zero. (A few hundred-million entries of 8 bytes each is a gigabyte, easily fitting into RAM, whereas a 1M by 1M matrix would be 8 terabytes of mostly-zeros blowing out RAM.)

I'm interested in having a statistics framework for such sparse arrays. (Well, actually I already have one, and, although it's partly in scheme, it cannot be srfi-fied due to how it uses unrelated software. Or rather, it cannot be srfi-fied without a sparse-tensor srfi being defined first.)

Utterly unrelated: having arbitrary-precision float arithmetic in the scheme numerical tower would be awesome (or would have been, back in the day when I used such things).

--linas

[Marc Nieper-Wißkirchen]

Am Di., 25. Aug. 2020 um 14:37 Uhr schrieb Lassi Kortela <la...@lassi.io>:
>
> >> https://www.gnu.org/software/kawa/Quaternions.html
> >
> > That is exactly what I have had in mind! With this approach, the
> > numeric tower is extended seamlessly.
> >
> > Maybe we can turn this into a SRFI for other implementations.
> >
> > (Quaternions are certainly more useful than the exact complex numbers
> > that have been voted into R7RS-large.)
>
> We should think about how to integrate Scheme numbers and arrays into
> the increasingly common machine learning / statistics frameworks.

I think we are talking about two really different topics here:

(1) The optional extension of the numeric tower to include the
quaternions as a superset of the complex numbers.

(2) Some fancy machine learning stuff involving matrices and tensors.

I think (1) is well-defined, especially with Kawa's prior work. On the
other hand, (2) is far from having any shape yet. The only connection
I see between (2) and (1) is that the quaternions can be represented
as matrices, but so can the complex numbers. But no one needs any
tensor algebra framework to specify and implement an API for complex
numbers. The same holds true for quaternions, of course.

[Linas Vepstas]

Marc,

On Tue, Aug 25, 2020 at 10:47 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

Am Di., 25. Aug. 2020 um 14:37 Uhr schrieb Lassi Kortela <la...@lassi.io>:
>
> >> https://www.gnu.org/software/kawa/Quaternions.html
> >
> > That is exactly what I have had in mind! With this approach, the
> > numeric tower is extended seamlessly.
> >
> > Maybe we can turn this into a SRFI for other implementations.
> >
> > (Quaternions are certainly more useful than the exact complex numbers
> > that have been voted into R7RS-large.)

(1) The optional extension of the numeric tower to include the
quaternions as a superset of the complex numbers.

The Kawa code appears to be licensed under the X11/MIT license here:  https://www.gnu.org/software/kawa/Software-License.html and so seems suitable for whole-sale conversion to a srfi via cut-n-paste.  The license for the documentation is less clear (https://www.gnu.org/software/kawa/Manual-License.html) and so Jamison would have to clarify.   Notice that there are not one, but two srfi's there: one for quaternions, one for rotations. The point is, you could cook up a srfi for quaternions in no time flat. 

But that's not the problem, is it? The problem seems to be "how can one slot in quaternions into the numeric tower in such a way that it's performant and rapidly-dispatched and etc. without damaging the existing real-number and/or complex number code?"  For that I have no clue whatsoever, as the whole numeric-tower thing in scheme is utterly opaque to me. But that's the question, isn't it? "what do we do about the numeric tower?" or "how do we put new wine in old bottles?"

--linas

[John Cowan]

On Tue, Aug 25, 2020 at 11:47 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

> > (Quaternions are certainly more useful than the exact complex numbers
> > that have been voted into R7RS-large.)

Well, they are interesting enough to mathematicians to have a name, the Gaussian rationals, and they are a field, even if (like the ordinary rationals) not a particularly "useful" field.  To quote math.stackexchange:

For the purposes of algebra, ℚ is not a very nice field to work with: for example, many (most?) polynomials don't even have a root, let alone factor completely, and dealing properly with this deficiency is the subject of the frontiers of mathematical research!

[...]

Similarly, for the purposes of analysis, ℚ is not a very nice ordered set; for example, they form a totally disconnected space, making them nearly useless for capturing even basic familiar geometric notions such as continuity.

(end quote) 

 

(1) The optional extension of the numeric tower to include the
quaternions as a superset of the complex numbers.

But where does one stop? The octonions, for example, are connected with the exceptional Lie groups and have applications in string theory.  And who knows, perhaps the sedecimonions (?) will find an application one day.  It seems like user extensibility of the tower is going to be a must if this is going to go anywhere.

On Tue, Aug 25, 2020 at 2:11 PM Linas Vepstas <linasv...@gmail.com> wrote:

 

For that I have no clue whatsoever, as the whole numeric-tower thing in scheme is utterly opaque to me.

It's pretty straightforward and "mathematical": the integers are a subset of the rationals, which are a subset of the reals, which are a subset of the complex numbers, which are a subset of (typically the same as) the numbers.  By convention, +inf.0, -inf.0, and +nan.0 are real but not rational.

Orthogonal to this is the notion of exactness.  Broadly speaking, a number is inexact if it is specified as an inexact literal or if it is derived from other inexact numbers.  There are exceptions: (* 1.0 0) and (sqrt 4) may be either exact or inexact.  Note that all three arguments are integers in Scheme.

None of this has anything to do with particular representations, which is how most programming languages approach numbers.  A common approach to a full Scheme numeric tower is to have six representations:

o   fixnums (exact integers of small magnitude)

o   bignums (other exact integers)

o   flonums (inexact approximations to the reals)

o   ratnums (pairs of bignums or fixnums representing numerator and denominator)

o   compnums (pairs of flonums representing real and imaginary parts)

o   rectnums (pairs of arbitrary real numbers). 

But of course There's More Than One Way To Do It.

John Cowan          http://vrici.lojban.org/~cowan        co...@ccil.org

So they play that [tune] on their fascist banjos, eh?
        --Great-Souled Sam

[Marc Nieper-Wißkirchen]

Am Di., 25. Aug. 2020 um 21:08 Uhr schrieb John Cowan <co...@ccil.org>:

> On Tue, Aug 25, 2020 at 11:47 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:
>
>> > > (Quaternions are certainly more useful than the exact complex numbers
>> > > that have been voted into R7RS-large.)
>
>
> Well, they are interesting enough to mathematicians to have a name, the Gaussian rationals, and they are a field, even if (like the ordinary rationals) not a particularly "useful" field. To quote math.stackexchange:

The Gaussian rationals are interesting because they form a number
field. But so are the other number fields. (If you have some time try
to understand the relative elementary proof of Fermat's Last Theorem
for p = 3 that uses the Eisenstein numbers.) So it's not really the
exact complex numbers we would like to have but exact algebraic
numbers. Only by chance, the exact complex numbers can be used to
model a single number field.

>> For the purposes of algebra, ℚ is not a very nice field to work with: for example, many (most?) polynomials don't even have a root, let alone factor completely, and dealing properly with this deficiency is the subject of the frontiers of mathematical research!

The latter is true. But I would replace "not a very nice field" by "a
much more interesting field". In the same way, the integers are a more
interesting ring than the rationals: In the integers, the concept of
divisibility is a rich one; in the rationals, it isn't.

>> Similarly, for the purposes of analysis, ℚ is not a very nice ordered set; for example, they form a totally disconnected space, making them nearly useless for capturing even basic familiar geometric notions such as continuity.

There's more than analysis. But even for analysis, Q is more
fundamental than R. The reals are the completion of Q with respect to
the usual absolute value; but there are other completions of Q leading
to the p-adic fields and p-adic analysis.

(These do not fit into the linear Scheme numeric tower, though.)

>> (1) The optional extension of the numeric tower to include the
>> quaternions as a superset of the complex numbers.
>
>
> But where does one stop? The octonions, for example, are connected with the exceptional Lie groups and have applications in string theory. And who knows, perhaps the sedecimonions (?) will find an application one day. It seems like user extensibility of the tower is going to be a must if this is going to go anywhere.

The quaternions still form a field (although a skew field) and linear
algebra is still possible. The octonions, on the other hand, are no
longer associative and fit the concept of a number much less.
Quaternions are very useful in applications driven by computers like
3D graphics and robotics. On the other hand, the applications of
octonions seem more theoretical and unless there is an application
where one has to do actual calculations within sight, I don't see a
reason to add them.

When we have basic linear algebra routines for matrices of Scheme
numbers, allowing quaternions seamlessly would come in very handy and
that's one reason why adding them can be useful.

> On Tue, Aug 25, 2020 at 2:11 PM Linas Vepstas <linasv...@gmail.com> wrote:
>
>>>
>>> For that I have no clue whatsoever, as the whole numeric-tower thing in scheme is utterly opaque to me.
>
>
> It's pretty straightforward and "mathematical": the integers are a subset of the rationals, which are a subset of the reals, which are a subset of the complex numbers, which are a subset of (typically the same as) the numbers. By convention, +inf.0, -inf.0, and +nan.0 are real but not rational.
>
> Orthogonal to this is the notion of exactness. Broadly speaking, a number is inexact if it is specified as an inexact literal or if it is derived from other inexact numbers. There are exceptions: (* 1.0 0) and (sqrt 4) may be either exact or inexact. Note that all three arguments are integers in Scheme.
>
> None of this has anything to do with particular representations, which is how most programming languages approach numbers. A common approach to a full Scheme numeric tower is to have six representations:
>
> o fixnums (exact integers of small magnitude)
> o bignums (other exact integers)
> o flonums (inexact approximations to the reals)
> o ratnums (pairs of bignums or fixnums representing numerator and denominator)
> o compnums (pairs of flonums representing real and imaginary parts)
> o rectnums (pairs of arbitrary real numbers).

Thanks for this table.

As one can see, unless the compiler can prove that a number is of a
certain type, runtime type dispatch is unavoidable (unless the
implementation just has one complex representation, making most
integer and real operations rather slow). Adding one more
representation, quatnum, being a pair of two complex numbers, wouldn't
make the type dispatch noticeably slower. (Especially the common fast
path, the integer path, should stay the same.) But Per can probably
say a bit more as Kawa actually implements this.

Marc

[Arthur A. Gleckler]

If Scheme's numeric tower is extended in R7RS Large, we should definitely consult with Sussman about it.  I am certain that he has thought about this a lot, including at the level of practical extensibility.

[Linas Vepstas]

Hoo boy, I think we are all talking past one-another. ...

On Tue, Aug 25, 2020 at 2:44 PM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

Am Di., 25. Aug. 2020 um 21:08 Uhr schrieb John Cowan <co...@ccil.org>:

> On Tue, Aug 25, 2020 at 11:47 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:
>
>> > > (Quaternions are certainly more useful than the exact complex numbers
>> > > that have been voted into R7RS-large.)
>
>
> Well, they are interesting enough to mathematicians to have a name, the Gaussian rationals, and they are a field, even if (like the ordinary rationals) not a particularly "useful" field.  To quote math.stackexchange:

Bad-mouthing the gaussian rationals is kind-of absurd, it suggests the authors have never looked at diophantine equations or the bazzillion-and-one other interrelated concepts ranging from the riemann hypothesis to p-adic analysis to the (chaotic) motion of geodesics on riemannian manifolds aka "chaos theory" (as it was called in the good old days.)  Foo.

(These do not fit into the linear Scheme numeric tower, though.)

>> (1) The optional extension of the numeric tower to include the
>> quaternions as a superset of the complex numbers.
>
>
> But where does one stop? The octonions, for example, are connected with the exceptional Lie groups and have applications in string theory.  And who knows, perhaps the sedecimonions (?) will find an application one day.  It seems like user extensibility of the tower is going to be a must if this is going to go anywhere.

The quaternions still form a field (although a skew field) and linear
algebra is still possible. The octonions, on the other hand, are no
longer associative and fit the concept of a number much less.

"Where does it stop?" It doesn't. There is a very blurry boundary between "numbers" and "things that aren't quite numbers".  Numbers are made out of "parts", just like atoms are, and that "atomic theory" involves "function fields" and "drinfeld modules" and whatnot. The general heading is called "arithmetic", and David Goss has a nice book on it, "basic structure of function field arithmetic". 

Marc is correct, the "octonians" are an absurd generalization, its going in a wildly-wrong direction.The correct generalizations would be things like p-adic numbers, the cantor set, galois fields or those kinds of directions, followed by polynomial fields. (polynomial fields are used by GPS to determine position. Used by cryptographers the world over to do cryptography... they are a kind of "number", you could say.)

> On Tue, Aug 25, 2020 at 2:11 PM Linas Vepstas <linasv...@gmail.com> wrote:
>
>>>
>>> For that I have no clue whatsoever, as the whole numeric-tower thing in scheme is utterly opaque to me.
>
>
> It's pretty straightforward

 

But dispatch tables are never straightforward, per the below.  I've actually got a patent for dispatch tables (back when I worked for a patent-happy corporation)

> None of this has anything to do with particular representations, which is how most programming languages approach numbers.  A common approach to a full Scheme numeric tower is to have six representations:
>
> o   fixnums (exact integers of small magnitude)
> o   bignums (other exact integers)
> o   flonums (inexact approximations to the reals)
> o   ratnums (pairs of bignums or fixnums representing numerator and denominator)
> o   compnums (pairs of flonums representing real and imaginary parts)
> o   rectnums (pairs of arbitrary real numbers).

Thanks for this table.

As one can see, unless the compiler can prove that a number is of a
certain type, runtime type dispatch is unavoidable (unless the
implementation just has one complex representation, making most
integer and real operations rather slow). Adding one more
representation, quatnum, being a pair of two complex numbers, wouldn't
make the type dispatch noticeably slower. (Especially the common fast
path, the integer path, should stay the same.)

So is this compile-time dispatch or run-time dispatch? Guile, at least, has a compile-time, and so in principle, it can do static analysis (don't know if it actually does).  To pick a hateful example, the  C++ templates enable "generic programming", and one could write a template for plus, minus, times and divide (aka "arithmetic") and have that apply to modules or function fields or quaternions or bit-strings, and not just a "tower" (which is not a tower at all, but a wildly branching tree, except more like a rhizome, because some of the branches grow back together again...).

Heck - it doesn't have to be a "number" -- this is how C++ implements "atomic ints" under the covers - they look like ints but have an atomic test-n-set under the covers.  In scheme, how do I define an "atomic int", guaranteed to increment atomically? Is that in the "number tower"?  Any why aren't bit-strings in the number tower?

If you only had a scheme interpreter, and not a compiler, I suppose you could pack fixnums/bignums/flonums into 3 bits, dispatch on the value of this 3-bit "number tag", and use one of the bits to mean "everything else", where "everything else" could be a much larger (and slower) dispatch table. But you'd do this only if you were creating a SICP-style roll-your-own scheme interpreter as a homework project.  The more serious/ambitious would imagine some kind of static-analysis technique, using something like C++ templates ... which, by the way, C++ implements "dispatch" via the C shared-library linker-loader to do the "dispatching" -- because the linker-loader knows how to walk the symbol table exported from the shared library, and hook things up.   ... actually it just installs trampolines, at first; on the first function call, the trampoline walks the symbol table to do the linkage to the actual function.

Using this as a "hint", the correct way to do generic programming in scheme would then be to write the analog of a linker-loader - something that can bounce off of a trampoline, walk the symbol table to find the correct implementation for the flonum/bignum/whatever, and install that code once and for all.  This avoids run-time dispatch. It's one reason why C is fast. 

So really, my slant on this is "can we do generic programming in scheme?" and "what would it take (a srfi or whatever) so that we can drop a nuclear bomb on the numeric tower, and replace it by something extensible?"

--linas

[Per Bothner]

On 8/25/20 5:15 PM, Jamison Hope wrote:
>> On Aug 25, 2020, at 2:11 PM, Linas Vepstas <linasv...@gmail.com> wrote:

> https://web.archive.org/web/20190918093656/http://www.ccs.neu.edu/home/dorai/squat/squat.html
>
> (Per, when you get a chance, would you mind updating the URL in the
> docs to point to the Wayback Machine?)

I updated the URL in the Kawa git source.
At some point in the unknown future the web-site will be updated ....

[Per Bothner]

On 8/25/20 12:44 PM, Marc Nieper-Wißkirchen wrote:
> As one can see, unless the compiler can prove that a number is of a
> certain type, runtime type dispatch is unavoidable (unless the
> implementation just has one complex representation, making most
> integer and real operations rather slow). Adding one more
> representation, quatnum, being a pair of two complex numbers, wouldn't
> make the type dispatch noticeably slower. (Especially the common fast
> path, the integer path, should stay the same.) But Per can probably
> say a bit more as Kawa actually implements this.

Kawa's compile-time optimization only extends to checking for reals
and various subclasses of real. (Most importantly, the compiler attempts to
use unboxed JVM primitives when it can.) Well, not quite: The compiler
does distinguish numbers from non-numbers, and compiles in a call to
a specific function that does run-time dispatch.

For classes that extend gnu.math.Numeric the run-time dispatch uses
relatively-efficient double-dispatch:
(- X Y)
becomes:
X.sub(Y)
which calls:
X.add(Y, -1)
The run-time class of X has an add method that calls addReversed.
For example in Complex (generic complex numbers):

public Numeric add (Object y, int k) // this + k * y
{
if (y instanceof Complex)
return add (this, (Complex) y, k);
return ((Numeric)y).addReversed(this, k);
}

If both arguments are Complex (and not more specific than Complex) we get to
the following static (no-dispatch) method which calls lower-level static methods

public static Complex add (Complex x, Complex y, int k)
{
return Complex.make (RealNum.add(x.re(), y.re(), k),
RealNum.add(x.im(), y.im(), k));
}

though RealNum.add gets back to dynamic dispatch:

public static RealNum add (RealNum x, RealNum y, int k)
{
return (RealNum)(x.add(y, k));

[Alex Shinn]

On Wed, Aug 26, 2020 at 9:58 AM Per Bothner <p...@bothner.com> wrote:

On 8/25/20 12:44 PM, Marc Nieper-Wißkirchen wrote:
> As one can see, unless the compiler can prove that a number is of a
> certain type, runtime type dispatch is unavoidable (unless the
> implementation just has one complex representation, making most
> integer and real operations rather slow).

This is non-trivial in Scheme where it is assumed the numeric tower is normalized,

such that (+ bignum bignum) may return a fixnum, (sqrt exact-integer) may return

an exact or inexact number, and operations on complex numbers may return real

results, etc.

Without normalized results, static typing (even partially or inferred) can extend

the numeric tower with zero overhead.  Nonetheless, the code size grows

quadratically, which can indirectly slow down the program due to caching effects,

apart from the implementation and maintenance burden.

 

> Adding one more
> representation, quatnum, being a pair of two complex numbers, wouldn't
> make the type dispatch noticeably slower. (Especially the common fast
> path, the integer path, should stay the same.) But Per can probably
> say a bit more as Kawa actually implements this.

Kawa's compile-time optimization only extends to checking for reals
and various subclasses of real.  (Most importantly, the compiler attempts to
use unboxed JVM primitives when it can.)  Well, not quite: The compiler
does distinguish numbers from non-numbers, and compiles in a call to
a specific function that does run-time dispatch.

For classes that extend gnu.math.Numeric the run-time dispatch uses
relatively-efficient double-dispatch:
   (- X Y)
becomes:
   X.sub(Y)
which calls:
   X.add(Y, -1)
The run-time class of X has an add method that calls addReversed.

Thanks for the details Per!

Chibi performs a low-level dispatch directly on the product of the types:

  https://github.com/ashinn/chibi-scheme/blob/master/bignum.c#L1311

This translates to a single jump table instead of the two dispatches in

Kawa.  It's a less modular approach and so perhaps more tedious to

maintain, but does allow adding new numeric types with no additional

dispatch overhead.

--

Alex

[John Cowan]

On Tue, Aug 25, 2020 at 6:10 PM Linas Vepstas <linasv...@gmail.com> wrote:

Hoo boy, I think we are all talking past one-another. ...

Indeed.

 

Bad-mouthing the gaussian rationals is kind-of absurd, [...]  Marc is correct, the "octonians" are an absurd generalization, its going in a wildly-wrong direction.

So one doesn't like the Gaussian rationals, another doesn't like the octonions.  Infinite are the arguments of mages.  This is exactly why we need either user-specifiable extensibility or no extensibility at all.

So really, my slant on this is "can we do generic programming in scheme?" and "what would it take (a srfi or whatever) so that we can drop a nuclear bomb on the numeric tower, and replace it by something extensible?"

As I've discussed elsewhere, we can: either by generic functions, or by explicit typeclasses, or by registered typeclasses.  Each has its strengths and weaknesses.

John Cowan          http://vrici.lojban.org/~cowan        co...@ccil.org

My corporate data's a mess!
It's all semi-structured, no less.
But I'll be carefree / Using XSLT
On an XML DBMS.

[Marc Nieper-Wißkirchen]

Adding quaternions to the numeric tower is a very conservative
addition and fits well into the theme of section 6.2 of the most
recent version of the report.

For everything else (number fields, non-associative algebras like the
octonions, ...), the current numeric tower in its current state is not
a predestined place to put them. Thus, I really would like to leave
these rings out of the discussion for the quaternions. Kawa's
implementation already shows that the quaternions integrate well into
all procedures of the 6.2. Whether it will later be implementable
through some generic numeric tower extension mechanism is a different
thing.

Am So., 30. Aug. 2020 um 04:58 Uhr schrieb John Cowan <co...@ccil.org>:

> As I've discussed elsewhere, we can: either by generic functions, or by explicit typeclasses, or by registered typeclasses. Each has its strengths and weaknesses.

Generic functions are not powerful enough in general because an
operation like "*" cannot usually be deduced from the type of its
arguments, namely when these arguments are elements of different, say,
rings at once.

[Linas Vepstas]

On Sun, Aug 30, 2020 at 3:27 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

Generic functions are not powerful enough in general because an
operation like "*" cannot usually be deduced from the type of its
arguments, namely when these arguments are elements of different, say,
rings at once.

This is already the case for ordinary numbers: e.g. for arbitrary-precision, you have more than one algorithm that will multiply numbers together: did you want the one that is faster and uses more RAM, or the one that is compact? Do you want the one that tightly controls the least-significant bit, or is some rounding error tolerable?

(multiplication may feel like "a simple thing" but its blargingly complicated, under the covers. It burns transistors inside of CPU's ...)

-- Linas

[John Cowan]

On Sun, Aug 30, 2020 at 2:14 PM Linas Vepstas <linasv...@gmail.com> wrote:

 

On Sun, Aug 30, 2020 at 3:27 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

Generic functions are not powerful enough in general because an
operation like "*" cannot usually be deduced from the type of its
arguments, namely when these arguments are elements of different, say,
rings at once.

This is already the case for ordinary numbers: e.g. for arbitrary-precision, you have more than one algorithm that will multiply numbers together: did you want the one that is faster and uses more RAM, or the one that is compact?

True, but that's an implementation issue, not a type issue.  The product of two integers is an integer, at the Scheme level, and at the representation level the product of two bignums is a bignum.  (As someone pointed out upstream, the sum of two bignums may be a fixnum if the bignums have different signs.)

John Cowan          http://vrici.lojban.org/~cowan        co...@ccil.org

No man is an island, entire of itself; every man is a piece of the
continent, a part of the main.  If a clod be washed away by the sea,
Europe is the less, as well as if a promontory were, as well as if a
manor of thy friends or of thine own were: any man's death diminishes me,
because I am involved in mankind, and therefore never send to know for
whom the bell tolls; it tolls for thee.  --John Donne

[Linas Vepstas]

On Sun, Aug 30, 2020 at 1:55 PM John Cowan <co...@ccil.org> wrote:

On Sun, Aug 30, 2020 at 2:14 PM Linas Vepstas <linasv...@gmail.com> wrote:

 

On Sun, Aug 30, 2020 at 3:27 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

Generic functions are not powerful enough in general because an
operation like "*" cannot usually be deduced from the type of its
arguments, namely when these arguments are elements of different, say,
rings at once.

This is already the case for ordinary numbers: e.g. for arbitrary-precision, you have more than one algorithm that will multiply numbers together: did you want the one that is faster and uses more RAM, or the one that is compact?

True, but that's an implementation issue, not a type issue.  The product of two integers is an integer, at the Scheme level, and at the representation level the product of two bignums is a bignum.  (As someone pointed out upstream, the sum of two bignums may be a fixnum if the bignums have different signs.)

How do I tell an implementation to multiply things this way, and not that way? Is there some big parameter, some global configuration table, where I get to specify which algorithms I want to use for multiplication? Can I tune some settings?

This seems absurd, perhaps, for integers, but is an actual, real-life issue for multi-precision floating point, where intermediate calculations may require much higher precision to obtain some given final precision.

... or worse: maybe you want to cache the value of pi to N places, what if some algo needs it to N+120 places for the intermediate results?  Better be ready to recompute pi to a few more places, as needed ...

Even for integers, there can be problems: several different division algos with different performance; many different types of integer functions are costly to compute, so caching is desirable... unless it's not.

For my personal use, I've brute-forced many of these issues by setting global variables and having them apply to all subsequent operations, (because I know what I'm doing) but it hardly seems acceptable for the general public. (There's even threading issues, where different threads might want different global settings...)

I'm sort of aware that what I am writing sounds like irritating quibbling, but I'm trying to point out these are actual, live real issues. Turning them into "implementation issues" is basically a signal of defeat: "we didn't know how to solve the problem in general, so we did this hack."

I don't mean to be irritating. It just comes naturally.  I simply do not know scheme well enough to argue for/against generics, typeclasses of various sorts. I'm trying to reinforce the idea that there are some interesting and hard problems that live  at the boundary between "its an implementation issue" and "we have an API for that".  To be bombastic: that is where the forefront of comp-sci lives, balancing between the obvious and the arcane.

--linas

[Marc Nieper-Wißkirchen]

Am So., 30. Aug. 2020 um 21:33 Uhr schrieb Linas Vepstas
<linasv...@gmail.com>:

> I'm sort of aware that what I am writing sounds like irritating quibbling, but I'm trying to point out these are actual, live real issues. Turning them into "implementation issues" is basically a signal of defeat: "we didn't know how to solve the problem in general, so we did this hack."

I think the right thing to answer here is that the (polymorphic)
number tower is not the right tool for that job.

For that, we have specialized procedures like "fx+" or "fl*". And it
is easy to add new specialized monomorphic procedures through
specialized libraries.

[Lassi Kortela]

>> I'm sort of aware that what I am writing sounds like irritating quibbling,

I don't think there's anything wrong with nitpicking in a programming
context, and indeed it often turns out to make a substantial difference
down the road as you say. I usually wish programmers were more nitpicky,
not less. Scheme is a very detail-oriented community. That's great.

> I think the right thing to answer here is that the (polymorphic)
> number tower is not the right tool for that job.
>
> For that, we have specialized procedures like "fx+" or "fl*". And it
> is easy to add new specialized monomorphic procedures through
> specialized libraries.

+1

However, it's nice if the values resulting from the specialized
procedures can be fed to standard procedures. (When Scheme's standard
procedures can't handle them, but we have more than one set of special
procedures that can, it's nice if the different sets of procedures can
use the same data. That's what I was getting at with representing things
in a way that's easy to copy to/from the popular machine learning
frameworks, though I realize that's not always practical.)

[Linas Vepstas]

So does my API look like this:

 (multiply X Y n-bits-of-final-precision)

or perhaps instead

(define fp (create-fp-arithmetic-system n-bits-of-final-precision nbits-of-intermediate-precision))

(fp 'multiply X Y)

Both approaches have strengths and weaknesses. A srfi for arbitrary-precision math would need to pick one or the other. One needs also sine, cosine, exp, gamma, binomial coeffs, and constants like pi, e ... and the intermediate-precision thing pokes its nose into these, especially anything involving  binomial coefficients, so any kind of newton sums, for example.

Here's a non-trivial example:  you might think `(multiply X Y n-bits-of-final-precision)` is silly, because the product of X,Y should "obviously" have precision (min (precision-of X) (precision-of Y)) -- But what if  X is the constant pi, and the current cached value is good for 100 digits, but (precision-of Y) is 200 ... Clearly (multiply pi Y) should return 200, not 100 bits of precision. But how?

There are also rounding issues: each multiply-add loses sqrt of one bit of precision; after 10000 multiply-adds, you might have lost sqrt(10000)=100 bits of precision. So intermediate results have to be more precise.

-- Linas

[Marc Nieper-Wißkirchen]

Am So., 30. Aug. 2020 um 22:27 Uhr schrieb Linas Vepstas
<linasv...@gmail.com>:

[...]

> So does my API look like this:
> (multiply X Y n-bits-of-final-precision)
>
> or perhaps instead
> (define fp (create-fp-arithmetic-system n-bits-of-final-precision nbits-of-intermediate-precision))
> (fp 'multiply X Y)

The first idea could be a bit inflexible; the second one does runtime
dispatch, which could slow down numeric code too much.

I would prefer syntax here (which could also go hand-in-hand with some
typed version of Scheme).

E.g.:

(define-syntax <fp> (create-fp- ...))

(* <fp> X Y)

As we are syntactically overloading the "*" operator here, the
performance of the number tower is not touched. (To implement this, we
need identifier macros that hopefully come to R7RS exactly for these
use cases.)

[...]

> Here's a non-trivial example: you might think `(multiply X Y n-bits-of-final-precision)` is silly, because the product of X,Y should "obviously" have precision (min (precision-of X) (precision-of Y)) -- But what if X is the constant pi, and the current cached value is good for 100 digits, but (precision-of Y) is 200 ... Clearly (multiply pi Y) should return 200, not 100 bits of precision. But how?
>
> There are also rounding issues: each multiply-add loses sqrt of one bit of precision; after 10000 multiply-adds, you might have lost sqrt(10000)=100 bits of precision. So intermediate results have to be more precise.

For these applications, we could model the type of real number as a
stream of digits. Each operation calculates the digits lazily when
they are requested. And this may force the operands to calculate more
digits. Although SRFI 41 is too inefficient to implement a final
version of this concept, it could be used to create a toy model to
experiment with.