fractions.test

fractions.test

[Kevin Ryde]

Is test-suite/tests/fractions.test meant to be included in the
distribution?

Naturally if so it'll need to be in Makefile.am, and will need a
copyright notice.

The comment about the clisp borrowings being gpl is not really right.
It's not enough to be gpl'ed, the copyright holder needs to be
identified (is it the FSF already?).


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: fractions.test

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> Is test-suite/tests/fractions.test meant to be included in the
> distribution?

Yep, thanks.

> The comment about the clisp borrowings being gpl is not really right.
> It's not enough to be gpl'ed, the copyright holder needs to be
> identified (is it the FSF already?).

I have made fractions.test GPL for that reason.  CLISP is not
copyrighted by the FSF (although it is named GNU CLISP).  However, the
risk is very low that this will turn out to be a problem and then we
only need to remove fractions.test from guile, which is easy to do and
not very harmful.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: fractions.test

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> CLISP is not
> copyrighted by the FSF (although it is named GNU CLISP).

Then I think there needs to be a copyright line in fractions.test
identifying who does hold the portions used.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: fractions.test

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> Marius Vollmer <mvo@zagadka.de> writes:
>>
>> CLISP is not
>> copyrighted by the FSF (although it is named GNU CLISP).
>
> Then I think there needs to be a copyright line in fractions.test
> identifying who does hold the portions used.

Yes, I have done so now.  I had to guess a bit since the original
doesn't contain very explicit copyright notices.  The heritage of the
code isn't crystal clear, but as I said, we can take the risk of
having to remove it.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

ratio implementation

[Bill Schottstaedt]

There is an implementation of ratios for Guile (based on CVS version
of 27-Jul-03) at ccrma-ftp.stanford.edu:/pub/Lisp/gratio.tar.gz.
Rather than send a huge diff, I placed the new versions of the changed
files (all from the libguile directory) in the tarball along with
*.diff showing the changes.  I added numerator, denominator,
rationalize and ratio?, and at the C level scm_make_ratio and
scm_i_ratio2real (should it be scm_ratio2dbl?).  "ratio?" is needed
because "rational?" returns #t if passed a real -- there has to be
some way to distiguish a ratio from a real. An alternative would be to
make "rational?"  rational.

I don't know how the FSF/GPL copyright stuff works, but I did this
work on my own time, did not look at any other implementation, and
hereby donate the code to you.  I'd be happy to "sign the papers".

I use longs for the numerator and denominator, so if bignums are
encountered, I fallback on the old method using scm_divide.  I didn't
try to provide the standard set of C-level type conversions -- not
sure these are needed in this case. I decided to follow Common Lisp
and reduce ratios, and return an integer if the ratio denominator is 1
(or if the numerator is 0).  One ugly change is the SCM_NUMP macro in
numbers.h -- the original of this macro strikes me as a kludge; the
new version is worse.  A questionable change (I followed Dybvig's book
p 126): (/ 17) -> 1/17, (/ 2 3) -> 2/3.  I notice that r5rs seems to
imply that (inexact->exact .3) should return 3/10 (see the rationalize
example which is assuming this) -- should I implement this?  What is
"reasonably close" in this case?  Another gray area involves functions
like round -- in r5rs (round 7/2) returns 4, whereas Guile returns 4.0
(I left it this way because (round 7) currently returns 7.0 rather
than 7) -- I decided to make minimal changes, but handling of
exact/inexact distinctions in Guile could use some work (I am willing
do this, if others approve).  Also, should random accept ratios?
And currently (format #f "~F" 2/3) hangs, but so does
(format #f "~B" 1.5) (in Guile 1.6.4 you get an error, but
in the CVS Guile it hangs in mutex_lock).


The changed files are:

smob.c
hash.c
eq.c
goops.c
gc-card.c
objects.c
numbers.c (nearly all the changes are in this file)
eval.c

numbers.h
tags.h
objects.h

Also in the tarball: ratio-tests.scm.  




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Marius Vollmer]

Bill Schottstaedt <bil@ccrma.Stanford.EDU> writes:

> There is an implementation of ratios for Guile (based on CVS version
> of 27-Jul-03) at ccrma-ftp.stanford.edu:/pub/Lisp/gratio.tar.gz.
> Rather than send a huge diff, I placed the new versions of the changed
> files (all from the libguile directory) in the tarball along with
> *.diff showing the changes.

Good work, thanks!  However, I don't think we should restrict us to
longs as the numerator/denominator, we should use fixnums and bignums.
Your patch is a very good basis for this and it should be quite
straightforward to make it use SCM integers as the
numerator/denominator.

That is, instead of using "long", I'd say we simply use "SCM" and
instead of "+", "==", etc, we use use "scm_sum", "scm_num_eq_p", etc.
Also, instead of mallocing scm_t_ratio, we can use double cells, which
should be more efficient.

Any takers?

(Also I didn't really check whether your rationals behave like R5RS
demands it.  Did you?  We should be sure to follow R5RS.)

> I added numerator, denominator, rationalize and ratio?, and at the C
> level scm_make_ratio and scm_i_ratio2real (should it be
> scm_ratio2dbl?).  "ratio?" is needed because "rational?" returns #t
> if passed a real -- there has to be some way to distiguish a ratio
> from a real.

A ratio is exact, while a real is not.  Thus, I'd say that ratio? is
not really necessary.  There should be no reason to add anything eyond
R5RS for ratios.

> An alternative would be to make "rational?"  rational.

That would violate R5RS, wouldn't it?

> I don't know how the FSF/GPL copyright stuff works, but I did this
> work on my own time, did not look at any other implementation, and
> hereby donate the code to you.  I'd be happy to "sign the papers".

Thanks!  I'll get back to you about the papers when necessary.

> I decided to make minimal changes, but handling of exact/inexact
> distinctions in Guile could use some work (I am willing do this, if
> others approve).

That would be great!

> And currently (format #f "~F" 2/3) hangs, but so does (format #f
> "~B" 1.5) (in Guile 1.6.4 you get an error, but in the CVS Guile it
> hangs in mutex_lock).

This should be fixed in CVS.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Dirk Herrmann]

Marius Vollmer wrote:

 >Bill Schottstaedt <bil@ccrma.Stanford.EDU> writes:
 >
 >>There is an implementation of ratios for Guile (based on CVS version
 >>of 27-Jul-03) at ccrma-ftp.stanford.edu:/pub/Lisp/gratio.tar.gz.
 >>Rather than send a huge diff, I placed the new versions of the changed
 >>files (all from the libguile directory) in the tarball along with
 >>*.diff showing the changes.
 >
 >
 >Good work, thanks!  However, I don't think we should restrict us to
 >longs as the numerator/denominator, we should use fixnums and bignums.
 >Your patch is a very good basis for this and it should be quite
 >straightforward to make it use SCM integers as the
 >numerator/denominator.
 >
 >That is, instead of using "long", I'd say we simply use "SCM" and
 >instead of "+", "==", etc, we use use "scm_sum", "scm_num_eq_p", etc.
 >Also, instead of mallocing scm_t_ratio, we can use double cells, which
 >should be more efficient.
 >
 >Any takers?

Hello together,

the last couple of days I have been looking closely at Guile's 
typecodes, and
I figured that we could improve the treating of numbers in a general way.  I
have to admit that I have not looked into Rob's code, thus my 
observations and
suggestions are based on the current CVS solution only.

Currently, fixnums are realized as immediates, while all other number types
(bignums, reals and complexs) are realized as smobs.  On the other hand, 
there
are at the moment two unused tc7 codes.

My suggestion is to use one of the free tc7 codes to represent a 'number'
type.  First, it would simplify parts of the smob code and free three smob
numbers.  Second, it would make type dispatch for numbers a little faster at
some places.  Third, in contrast to smobs which use 16 type code bits, a
smaller number of typecode bits may be required, making it possible to store
more information in the SCM_CELL_TYPE mask.

In addition to the tc7 bits, additional bits can be used for subtyping the
suggested scm_tc7_number type.  The following subtypes need to be provided:

 - bignums, holding a pointer to a gmp structure
 - doubles, holding a 64 bit double precision number
 - fraction, holding two SCM values for nominator and denominator
 - complex, holding two SCM values for real and imaginary part

The following subtypes can be provided additionally to support certain
features:

 - fixnums, holding an inum SCM value.  This type can be provided to allow
   inexact fixnum values.
 - floats, holding a 32 bit single precision number
 - further floating point representations like mpfr numbers
 - fixed point numbers
 - ...

For example, the four bits above the tc7 bits could be defined as follows
(still using only 11 bits for type information, compared to 16 bits with the
current solution):

 xsss

with x indicating the exactness, and sss indicating the subtype.  The 
subtypes
could, for example, be assigned as follows (certainly, only the mandatory
types listed above would need to be supported):

 000 - Fixnum (inum in cell word #2), optional to allow inexact fixnums
 001 - Bignum (gmp struct ptr in cell word #2), typically exact, optionally
       inexact to allow inexact bignums.
 010 - fraction (all combinations of fixnums and bignums stored as SCM
       values in double cell words #2 #3), typically exact, optionally 
inexact
       if inexact fixnums or inexact bignums are to be supported.
 011 - fixed point number (implementation not clear yet, just listed for
       completeness), exact or inexact
 100 - float (32 bit float in cell word #2), always inexact
 101 - double (64 bit float in double cell words #2 #3), always inexact
 110 - mpfr (gmp struct ptr in cell word #2), always inexact
 111 - complex, stored as SCM values in double cell words #2 #3, possible
       combinations are (double double) - always inexact, (float, float) -
       always inexact, (fixedpoint fixedpoint) - inexact or exact,
       (mpfr mpfr) - always inexact, or all combinations of fixnums, bignums
       and fractions - typically exact, optionally inexact

Since fractions and complex numbers are represented in terms of pairs of 
other
numbers, operations on fractions and complex numbers can be delegated to
operations that work on the remaining, more basic representations.

The limitations on the possible combinations for real and imaginary part of
complex numbers has the background that it does not seem to make sense to me
to represent real and imaginary part with different precision.

Even if no inexact fixnums, bignums and rationals are to be supported it 
does
still make sense to provide the exactness bit for faster operation of the
exact? predicate.


I had been planning, as a first step, to simply allocate that scm_tc7_number
typecode and turn bignums, doubles and complex numbers into subtypes of that
type.  I had not originally intended to add rationals in the same run.  
Maybe
I could help to prepare their addition.  However, there are still a 
number of
changes with respect to separating memoization and execution in the 
evaluator,
so it may take some time until I start to work on it.

Best regards
Dirk Herrmann



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Bill Schottstaedt]

 > That is, instead of using "long", I'd say we simply use "SCM" and
 > instead of "+", "==", etc, we use use "scm_sum", "scm_num_eq_p", etc.
 > Also, instead of mallocing scm_t_ratio, we can use double cells, which
 > should be more efficient.
 >
 > Any takers?

Looks straightforward, but I may not get around to it right away.
Should I wait for Dirk's type-related changes?  Also, I haven't
looked closely at double cells, though I assume (from a glance
at the scm_t_double stuff) that I can include my "reduce" flag
as well as the numerator and denominator.  The point being to
reduce calls on gcd as much as possible (this being Guile's integer
divide, there's some desire to keep it from crawling).  But, it's
an optional optimization.


 > (Also I didn't really check whether your rationals behave like R5RS
 > demands it.  Did you?  We should be sure to follow R5RS.)

Yes, I think it follows R5RS.  See test-ratios.scm for some tests.
I could make these fit into 'make check'.


 > A ratio is exact, while a real is not.  Thus, I'd say that ratio? is
 > not really necessary.  There should be no reason to add anything eyond
 > R5RS for ratios.

Ok -- "exact?" used to return #f for 3/4 -- hence the confusion.


 >> An alternative would be to make "rational?"  rational.
 > That would violate R5RS, wouldn't it?

I don't think so.  You are allowed to make rational? be the same
as real?, but you can also distinguish them.  My druthers would
be for rational? to return #t for a ratio, #f for a float.
Why have it at all if it is just a synonym for "real?"?




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Dirk Herrmann]

Bill Schottstaedt wrote:

> Looks straightforward, but I may not get around to it right away.
> Should I wait for Dirk's type-related changes?

Just for your information: I have submitted a patch which does the first 
part: Introducing scm_tc7_number and turning bignums, reals and complex 
numbers from smobs into subtypes of scm_tc7_number. The patch, however, 
is quite simplistic and does not yet optimize the way the subtypes of 
scm_tc7_number are allocated. It should nevertheless provide the 
type-system infrastructure for easy integration of the fraction type.

> > A ratio is exact, while a real is not.  Thus, I'd say that ratio? is
> > not really necessary.  There should be no reason to add anything eyond
> > R5RS for ratios.
>
> Ok -- "exact?" used to return #f for 3/4 -- hence the confusion.
>
>
> >> An alternative would be to make "rational?"  rational.
> > That would violate R5RS, wouldn't it?
>
> I don't think so.  You are allowed to make rational? be the same
> as real?, but you can also distinguish them.  My druthers would
> be for rational? to return #t for a ratio, #f for a float.
> Why have it at all if it is just a synonym for "real?"? 

Just a side note: We should in guile distinguish between the internal 
representation of values, and their mathematical meaning. For example, 
fixnums and bignums are two representation of integer types. They 
should, however, also report #t when queried about being rational, real 
or complex, since they are elements of all these sets. When introducing 
exact rationals, which are represented internally as a pair of two exact 
integer values, we should not name them rationals, but, for example, 
fractions.

The reason I mention this is that I want to avoid a macro SCM_RATIONAL_P 
to be introduced: The meaning of such a macro would not be clear, since 
it might either be expected to return the equivalent of rational? or 
just return true if an object was detected with an internal 
representation of a fraction.

A nice set of macros to check for numbers of a specific internal 
representation could be (names are just given as examples):

SCM_FIXNUM_P (currently named SCM_INUMP)
SCM_BIGNUM_P (currently named SCM_BIGP)
SCM_FRACTNUM_P
SCM_FLOATNUM_P (currently named SCM_REALP, which is confusing)
SCM_FLOATCPLXNUM_P (currently named SCM_COMPLEXP)

while a nice set of macros for testing for a mathematical meaning could 
be (names are probably acceptable):

SCM_EXACT_P
SCM_NUMBER_P
SCM_INTEGER_P
SCM_RATIONAL_P
SCM_REAL_P
SCM_COMPLEX_P

In the long term, we should rethink our current set of confusing names. 
For the short term, we should at least avoid to introduce more confusing 
terms, especially when introducing the new internal representation of 
fractions.

Best regards
Dirk Herrmann



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Marius Vollmer]

Dirk Herrmann <dirk@dirk-herrmanns-seiten.de> writes:

> When introducing exact rationals, which are represented internally
> as a pair of two exact integer values, we should not name them
> rationals, but, for example, fractions.
>
> The reason I mention this is that I want to avoid a macro
> SCM_RATIONAL_P to be introduced: The meaning of such a macro would not
> be clear, since it might either be expected to return the equivalent
> of rational? or just return true if an object was detected with an
> internal representation of a fraction.

Yes, very good point.  Bill, please name your data type "fraction".

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Bill Schottstaedt]

I made the requested changes (using the Oct-9 CVS Guile):

    ftp://ccrma-ftp.stanford.edu/pub/Lisp/gratio-1.tar.gz

I haven't yet translated the test suite to Guile's form.


I notice that Guile doesn't support "exact complex", but
it appears that some other Schemes do -- is this a desired
extension?

guile> (exact? 2/3+i)
#f



Under scm_ash, the doc string:

	    "Formally, the function returns an integer equivalent to\n"
	    "@code{(inexact->exact (floor (* @var{n} (expt 2 @var{cnt}))))}.\n"

is incorrect:

guile> (ash .1 2)
0.4

but ash is not handling negative shifts correctly:

guile> (ash .1 -2)

Backtrace:
In standard input:
    4: 0* [ash 0.1 -2]

standard input:4:1: In procedure quotient in expression (ash 0.1 -2):
standard input:4:1: Wrong type argument in position 1: 0.1
ABORT: (wrong-type-arg)

The scm_quotient function assumes its arguments are ints/bignums,
so it can't be used directly in ash.


Also: (sqrt 9/49) -> 3/7?  Seems like it should parallel:
guile> (expt 2 -2)
1/4



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: ratio implementation

[Marius Vollmer]

Bill Schottstaedt <bil@ccrma.Stanford.EDU> writes:

> I made the requested changes (using the Oct-9 CVS Guile):
>
>     ftp://ccrma-ftp.stanford.edu/pub/Lisp/gratio-1.tar.gz

Excellent!  I'm going to look it over and apply it once we have the
papers from you.  Thanks a lot!

(More comments later.)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: fractions.test

[Bill Schottstaedt]

Only the bignum cases after the comment about clisp (around
line 346 in my version) are from clisp; I wrote the rest by hand,
although I looked at the plt-scheme test suite for ideas.
I also looked at Dybvig's book and borrowed some of his
examples (they are marked "from Dybvig").  I'm sorry I
haven't translated that file to "the Guile Way" -- no time.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel