Re: [Scheme-reports] Formal Objection: Memoization is not possible in portable R7RS Mark H Weaver (26 Nov 2012 00:11 UTC)

Re: [Scheme-reports] Formal Objection: Memoization is not possible in portable R7RS Mark H Weaver 26 Nov 2012 00:07 UTC

I was asked to produce a list of differences between the R6RS
definition of 'eqv?' of numbers and my proposal.  I sent a
preliminary list in private email which is now on the wiki, but
that list was not complete.

I now have a complete list of edits needed to change the R6RS
definition into the new proposal.  See below for a summary of
the nontrivial ones.

   Regards,
     Mark

Nontrivial changes in the formulation of 'eqv?' since R6RS:

* Nontrivial change: "rational numbers" to "exact numbers" in
  the clause requiring #f if "Obj_1 and obj_2 are rational
  numbers for which the = procedure returns #f."

  Note: This clause was redundant, but is kept for the case of
  exact numbers, so that we may restrict our definition of the
  predicate /operationally equivalent/ to inexact numbers only.

* Stylistic change: Move the following language into the new
  auxiliary predicate /operationally equivalent/:

    [...] yield {the same,different} results (in the sense of
    eqv?) when passed as arguments to any other procedure
    that can be defined as a finite composition of Scheme's
    standard arithmetic procedures"

* Nontrivial change: Restrict use of the predicate
  /operationally equivalent/ to cases where both arguments are
  inexact.

* Stylistic change: Move the "same results (in the sense
  of eqv?)" language into the new auxiliary predicate
  /substantially different/.

* Significant change: Eliminate the circularity by changing
  the definition of /substantially different/ for two numbers
  to use '=' instead of 'eqv?'.

* Significant change: Fix the NaN problem by making sure that
  two numbers can only be /substantially different/ if at
  least one of them is numerically equal to itself.

* Significant change: Restrict the set of procedures that can
  be used to construct 'f', and use the R7RS terminology:

    "Scheme's standard arithmetic procedures"
  =>
    "the standard numerical operations specified in
     section 6.2.6"

* Significant change: Properly handle the case where (f z_1) or
  (f z_2) raise exception(s).

    "(f z_1) and (f z_2) yield results that are not
     substantially different."
  =>
    "(f z_1) and (f z_2) either both raise exceptions or yield
     results that are not /substantially different/."

* Significant change: Make sure that the case where both
  arguments are NaNs is left unspecified by requiring, in the
  inexact clauses, that at least one argument is numerically
  equal to itself.

* Simplification: Remove the redundant check for numerical
  equality as a prerequisite for 'eqv?' returning #t.

  Rationale: If obj_1 and obj_2 are not numerically equal (and
  not both NaNs), it trivially follows that obj_1 and obj_2 are
  not operationally equivalent, since (+ obj_1) and (+ obj_2)
  are substantially different.

* Significant change: Relax the requirements for returning #t
  for 'eqv?' on inexacts to the cases where "the
  implementation is able to prove" operational equivalence.

  We now require only that the "implementations must be able
  to prove that two inexact numbers with the same internal
  representation are operationally equivalent.

  Rationale: It may be difficult or impossible for the
  implementation to prove that two inexact numbers are
  operationally equivalent.

_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports