32 views

Skip to first unread message

Aug 24, 2020, 3:41:20 PM8/24/20

to Marc Nieper-Wi?kirchen, Linas Vepstas, scheme-re...@googlegroups.com

[-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

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

Aug 24, 2020, 4:15:30 PM8/24/20

to scheme-re...@googlegroups.com, Linas Vepstas

> 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 + -
> 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 <>)).

* 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.

Aug 25, 2020, 1:52:04 AM8/25/20

to scheme-re...@googlegroups.com, Linas Vepstas

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.

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.

Aug 25, 2020, 2:40:08 AM8/25/20

to scheme-re...@googlegroups.com, Marc Nieper-Wißkirchen, Linas Vepstas, Jamison Hope

On 8/24/20 10:51 PM, Marc Nieper-Wißkirchen wrote:

> My initial comment (on the SRFI 194 mailing list) ...

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/

> 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:
> only to include the complex numbers but also the quaternions.

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/

Aug 25, 2020, 8:20:44 AM8/25/20

to Per Bothner, scheme-re...@googlegroups.com, Linas Vepstas, Jamison Hope

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
>

> 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

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

Aug 25, 2020, 8:37:47 AM8/25/20

to scheme-re...@googlegroups.com, Linas Vepstas, Jamison Hope

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

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

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

Aug 25, 2020, 11:30:48 AM8/25/20

to Lassi Kortela, scheme-re...@googlegroups.com, Jamison Hope

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

Aug 25, 2020, 11:47:31 AM8/25/20

to scheme-re...@googlegroups.com, Per Bothner, Linas Vepstas, Jamison Hope

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

> >> 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.

(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.

Aug 25, 2020, 2:11:33 PM8/25/20

to Marc Nieper-Wißkirchen, scheme-re...@googlegroups.com, Per Bothner, Jamison Hope

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

Aug 25, 2020, 3:08:20 PM8/25/20

to scheme-re...@googlegroups.com, Per Bothner, Linas Vepstas, Jamison Hope

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.

So they play that [tune] on their fascist banjos, eh?

--Great-Souled Sam

--Great-Souled Sam

Aug 25, 2020, 3:44:23 PM8/25/20

to scheme-re...@googlegroups.com, Per Bothner, Linas Vepstas, Jamison Hope

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

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!

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.

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.

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

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

Aug 25, 2020, 3:51:40 PM8/25/20

to scheme-re...@googlegroups.com, Per Bothner, Linas Vepstas, Jamison Hope

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.

Aug 25, 2020, 6:10:54 PM8/25/20

to Marc Nieper-Wißkirchen, scheme-re...@googlegroups.com, Per Bothner, Jamison Hope

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

Aug 25, 2020, 8:40:39 PM8/25/20

to Jamison Hope, Marc Nieper-Wißkirchen, linasv...@gmail.com, scheme-re...@googlegroups.com

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 ....

>> 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 ....

Aug 25, 2020, 8:58:01 PM8/25/20

to scheme-re...@googlegroups.com

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
> 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.

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

Aug 26, 2020, 1:51:08 AM8/26/20

to scheme-re...@googlegroups.com

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!

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

Aug 29, 2020, 10:58:26 PM8/29/20

to scheme-re...@googlegroups.com, Marc Nieper-Wißkirchen, Per Bothner, Jamison Hope

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.

My corporate data's a mess!

It's all semi-structured, no less.

But I'll be carefree / Using XSLT

On an XML DBMS.

It's all semi-structured, no less.

But I'll be carefree / Using XSLT

On an XML DBMS.

Aug 30, 2020, 4:27:48 AM8/30/20

to John Cowan, scheme-re...@googlegroups.com, Per Bothner, Jamison Hope

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.

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.

operation like "*" cannot usually be deduced from the type of its

arguments, namely when these arguments are elements of different, say,

rings at once.

Aug 30, 2020, 2:14:41 PM8/30/20

to scheme-re...@googlegroups.com, John Cowan, Per Bothner, Jamison Hope

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

Aug 30, 2020, 2:55:17 PM8/30/20

to Linas Vepstas, scheme-re...@googlegroups.com, Per Bothner, Jamison Hope

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

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

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

Aug 30, 2020, 3:33:24 PM8/30/20

to John Cowan, scheme-re...@googlegroups.com, Per Bothner, Jamison Hope

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

Aug 30, 2020, 3:47:36 PM8/30/20

to scheme-re...@googlegroups.com, John Cowan, Per Bothner, Jamison Hope

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.

<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."

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.

Aug 30, 2020, 4:26:58 PM8/30/20

to scheme-re...@googlegroups.com, Marc Nieper-Wißkirchen, John Cowan, Per Bothner, Jamison Hope

>> 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.

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

Aug 30, 2020, 4:27:30 PM8/30/20

to scheme-re...@googlegroups.com, John Cowan, Per Bothner, Jamison Hope

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

Aug 31, 2020, 3:21:01 PM8/31/20

to scheme-re...@googlegroups.com, John Cowan, Per Bothner, Jamison Hope

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.

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

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.

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu