Make-promise violates obvious axiom uncontrollably

[Marc Nieper-Wißkirchen]

The "obvious axiom" is the following:

(force (make-promise obj)) => obj

In R7RS, this axiom is violated because make-promise has to return a promise unchanged:

(force (make-promise (make-promise obj))) => obj

While this complicates the semantics (and makes them somewhat ugly), this wouldn't be that much of a problem if the promise type was a disjoint type in R7RS, which it isn't (*).

This means that any object could, in principle, be a promise so the programmer can never know to what (force (make-promise obj)) evaluates because obj can just happen to look like a promise (remember that there are implementations of promises based on non-opaque tagged pairs).

This means that (make-promise <expr>) is mostly useless in portable code and one should always write (let ((tmp <expr>)) (delay tmp)) instead.

This clearly shows that the semantics of make-promise as written in R7RS cannot be the right one. I, therefore, propose to add an erratum to R7RS fixing make-promise (so that it always obeys the above axiom).

Now, errata should only address errors and not design mistakes, but, fortunately, another error comes to our rescue: The definition of make-promise in the chapter on formal syntax and semantics on page 71 actually obeys the above axiom and does not behave as described in chapter 4.

Thus, an erratum should and can resolve this contradiction, and it should do it in a way that favors the definition in chapter 7 over the prose in chapter 4.

Marc

(*) But even if the promise type were disjoint, it would be hard to write generically polymorphic algorithms with make-promise because promises, which are otherwise first-class objects, would ad-hoc be treated non-uniformly and differently than any other type of object.

[Alex Shinn]

I'm trying to recall why we exposed make-promise? It was only used as
an example and not a pre-defined procedure in R5RS.
We modeled the delayed evaluation off of SRFI 45, which also does not
include this procedure.

Note SRFI 155 - Promises shares this same make-promise "feature" with R7RS.

I don't think this is broken, per se, and would not normally be
something to consider as an erratum, although the inconsistency in the
sample implementation offers leverage. Keep in mind that although
promises are not guaranteed to be a disjoint _type_, `promise?` must
be accurate.

So while I think I would prefer your suggestion I'm not sure we can justify it.

--
Alex

> --
> You received this message because you are subscribed to the Google Groups "scheme-reports-wg1" 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-wg1/291ab5c6-7d2c-455c-ade1-2da4342acb91n%40googlegroups.com.

[Marc Nieper-Wißkirchen]

Am Di., 3. Aug. 2021 um 10:46 Uhr schrieb Alex Shinn <alex...@gmail.com>:

I'm trying to recall why we exposed make-promise?  It was only used as
an example and not a pre-defined procedure in R5RS.
We modeled the delayed evaluation off of SRFI 45, which also does not
include this procedure.

Note SRFI 155 - Promises shares this same make-promise "feature" with R7RS.

I know. It doesn't make it better. :)

 

I don't think this is broken, per se, and would not normally be
something to consider as an erratum, although the inconsistency in the
sample implementation offers leverage.  Keep in mind that although
promises are not guaranteed to be a disjoint _type_, `promise?` must
be accurate.

Right, but the latter doesn't help much. For example, an implementation could also declare (some) integers to be promises (interpreting them as indices in a lookup table for already forced promises).  Or, only a slight variation of the sample implementation in SRFI 45 will turn every pair into a promise.

 

So while I think I would prefer your suggestion I'm not sure we can justify it.

The inconsistency should be resolved one way or the other.  And one way is broken (at least insofar as it defines a procedure that is useless in portable code).

I mean, can one write down any meaningful portable test for make-promise as described in chapter 4 of the R7RS?

[Alaric Snell-Pym]

On 03/08/2021 07:37, Marc Nieper-Wißkirchen wrote:
> The "obvious axiom" is the following:
>
> (force (make-promise obj)) => obj
>
> In R7RS, this axiom is violated because make-promise has to return a
> promise unchanged:
>
> (force (make-promise (make-promise obj))) => obj

Is there anything this is *useful* for? I mean, it smacks to me of a bit
of Perl-esque "do what I mean" thing, like making (+ "1" 1) => 2.

I suspect that it's quite important (to the correct functioning of most
code involving promises) that the code "knows" whether a value is a
promise or not, rather than having maybe-promises flying around. In
which case, applying make-promise to a promise would be a deliberate act
done with the intention of creating a two-layer-deep promise, rather
than done deliberately as a no-op. And something that blindly applies
make-promise to unknown things as part of some generic data structure or
algorithm is going to force the promises and expect to get the original
values back, as per the "obvious axiom".

--
Alaric Snell-Pym (M0KTN neé M7KIT)
http://www.snell-pym.org.uk/alaric/

[Marc Nieper-Wißkirchen]

Am Di., 3. Aug. 2021 um 12:30 Uhr schrieb Alaric Snell-Pym <ala...@snell-pym.org.uk>:

On 03/08/2021 07:37, Marc Nieper-Wißkirchen wrote:
> The "obvious axiom" is the following:
>
> (force (make-promise obj)) => obj
>
> In R7RS, this axiom is violated because make-promise has to return a
> promise unchanged:
>
> (force (make-promise (make-promise obj))) => obj

Is there anything this is *useful* for? I mean, it smacks to me of a bit
of Perl-esque "do what I mean" thing, like making (+ "1" 1) => 2.

Yeah, there are two layers to this. One is the Perl-esque thing of the ad-hoc overloading of make-promise.  This is ugly but not an obvious error.  It becomes definitely one - and this is the second layer - because the promise type is not disjoint.

Any sensible use of make-promise with the semantics of chapter 4 would look like (assuming that OBJ is a simple variable reference):

(if (promise? obj)

    (delay obj)

    (make-promise obj))

But, then, one can obviously just write (delay obj)!

-- Marc

 

I suspect that it's quite important (to the correct functioning of most
code involving promises) that the code "knows" whether a value is a
promise or not, rather than having maybe-promises flying around. In
which case, applying make-promise to a promise would be a deliberate act
done with the intention of creating a two-layer-deep promise, rather
than done deliberately as a no-op. And something that blindly applies
make-promise to unknown things as part of some generic data structure or
algorithm is going to force the promises and expect to get the original
values back, as per the "obvious axiom".

--
Alaric Snell-Pym   (M0KTN neé M7KIT)
http://www.snell-pym.org.uk/alaric/

--
You received this message because you are subscribed to a topic in the Google Groups "scheme-reports-wg1" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scheme-reports-wg1/bQcQZK3GBHw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scheme-reports-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/scheme-reports-wg1/90e40646-88cc-6fc5-7561-92010013cc86%40snell-pym.org.uk.

[Alex Shinn]

On Tue, Aug 3, 2021 at 6:03 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> Am Di., 3. Aug. 2021 um 10:46 Uhr schrieb Alex Shinn <alex...@gmail.com>:
>>
>> I don't think this is broken, per se, and would not normally be
>> something to consider as an erratum, although the inconsistency in the
>> sample implementation offers leverage. Keep in mind that although
>> promises are not guaranteed to be a disjoint _type_, `promise?` must
>> be accurate.
>
> Right, but the latter doesn't help much. For example, an implementation could also declare (some) integers to be promises (interpreting them as indices in a lookup table for already forced promises). Or, only a slight variation of the sample implementation in SRFI 45 will turn every pair into a promise.

Integers could not be used because then `promise?` would be broken.
Given a predicate distinguishing elements of a non-disjoint type, one
could consider 3 approaches:

1. Ambiguous with some existing type, such as integers or procedures.
The description of the predicate should indicate this with clear
warnings as for string cursors in SRFI 130, e.g. saying "_can_ be a
string-cursor".

2. A transparent subset of some existing type, such as tagged vectors.
Both `new-type?` and `vector?` will return true for instances, so the
former should take precedence. Instances of this type can be forged,
but otherwise false positives would not normally occur in practice.

3. An opaque subset of some existing type, such as procedures tracked
in a global weak hash table. The same caveats as the above approach
apply, but instances cannot be forged.

As there is no warning or discussion of false positives for `promise?`
I would argue the first approach is not a realistic option. In R5RS,
where there was no `promise?` procedure, the first approach of course
was allowed and widely used.

--
Alex

[Marc Nieper-Wißkirchen]

Am Di., 3. Aug. 2021 um 16:12 Uhr schrieb Alex Shinn <alex...@gmail.com>:

On Tue, Aug 3, 2021 at 6:03 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> Am Di., 3. Aug. 2021 um 10:46 Uhr schrieb Alex Shinn <alex...@gmail.com>:
>>
>> I don't think this is broken, per se, and would not normally be
>> something to consider as an erratum, although the inconsistency in the
>> sample implementation offers leverage.  Keep in mind that although
>> promises are not guaranteed to be a disjoint _type_, `promise?` must
>> be accurate.
>
> Right, but the latter doesn't help much. For example, an implementation could also declare (some) integers to be promises (interpreting them as indices in a lookup table for already forced promises).  Or, only a slight variation of the sample implementation in SRFI 45 will turn every pair into a promise.

Integers could not be used because then `promise?` would be broken.

Broken by what measure? R7RS does allow it. In any case, it is broken together with make-promise's semantics of chapter 4.

 

Given a predicate distinguishing elements of a non-disjoint type, one
could consider 3 approaches:

1. Ambiguous with some existing type, such as integers or procedures.
The description of the predicate should indicate this with clear
warnings as for string cursors in SRFI 130, e.g. saying "_can_ be a
string-cursor".

2. A transparent subset of some existing type, such as tagged vectors.
Both `new-type?` and `vector?` will return true for instances, so the
former should take precedence.  Instances of this type can be forged,
but otherwise false positives would not normally occur in practice.

3. An opaque subset of some existing type, such as procedures tracked
in a global weak hash table.  The same caveats as the above approach
apply, but instances cannot be forged.

As there is no warning or discussion of false positives for `promise?`
I would argue the first approach is not a realistic option.  In R5RS,
where there was no `promise?` procedure, the first approach of course
was allowed and widely used.

In R7RS, all three approaches are allowed.  The implementation in chapter 7 roughly follows approach 2.  I remember that the Google Docs application was crashing on certain inputs several years ago. The root cause was that they had used some kind of approach 2 for some internals. So much for the practice of "would not normally occur in practice".

In any case, we can't change this and can't retroactively make the promise type a disjoint type in R7RS.  All guarantees we get from R7RS's promise? predicate is that it is not an error to apply force to an object satisfying it.

The only leverage we have is to correct make-promise in R7RS.

(And even if promises were of a disjoint type, the chapter 7 semantics of make-promise would still make much more sense than what's in chapter 4.)

-- Marc

PS Note that R7RS also permits that implementations let promise? returns true for every object.  The actual internal promise type wouldn't be exposed in such implementations.  Forcing a non-internal-promise would just return the object.  And make-promise would, in this case, rightfully be the identity.

[John Cowan]

On Tue, Aug 3, 2021 at 10:34 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

 

Given a predicate distinguishing elements of a non-disjoint type, one

could consider 3 approaches:

1. Ambiguous with some existing type, such as integers or procedures.
The description of the predicate should indicate this with clear
warnings as for string cursors in SRFI 130, e.g. saying "_can_ be a
string-cursor".

2. A transparent subset of some existing type, such as tagged vectors.
Both `new-type?` and `vector?` will return true for instances, so the
former should take precedence.  Instances of this type can be forged,
but otherwise false positives would not normally occur in practice.

3. An opaque subset of some existing type, such as procedures tracked
in a global weak hash table.  The same caveats as the above approach
apply, but instances cannot be forged.

As there is no warning or discussion of false positives for `promise?`
I would argue the first approach is not a realistic option.  In R5RS,
where there was no `promise?` procedure, the first approach of course
was allowed and widely used.

In R7RS, all three approaches are allowed.

That turns out not to be the case.

The canons of interpretation provide (among other things), that the text of a provision must be interpreted as a whole, and that the provisions of a text should be interpreted in a way that renders them compatible, not contradictory (see <https://www.law.uh.edu/faculty/adjunct/dstevenson/2018Spring/CANONS%20OF%20CONSTRUCTION.pdf>).

The definition of make-promise is: "The promise? procedure returns #t if its argument is a promise, and #f otherwise. Note that promises are not necessarily disjoint from other Scheme types such as procedures."  Interpreting the second sentence to allow promises to be indistinguishable from some other type, per approach 1, would render the two sentences contradictory.  Therefore, that interpretation is disallowed unless no other interpretation is available.  We do, in fact, have two other interpretations available, namely 2 and 3.

 I agree that approach 2 produces a lower quality of implementation than approach 3, and approach 4 (disjoint types) is better than either.  But QOI has nothing to do with conformance.

PS Note that R7RS also permits that implementations let promise? returns true for every object.

I also deny this.  While it is true that constructs other than delay, delay-force, and make-promise might in principle create a promise, promise? and force are applicable only to promises.  (The three extensions to force listed, including the one that allows forcing a non-promise to return the non-promise are not normative, simply a statement of what some implementations do or have done.)

[Marc Nieper-Wißkirchen]

Am Di., 3. Aug. 2021 um 19:53 Uhr schrieb John Cowan <co...@ccil.org>:

On Tue, Aug 3, 2021 at 10:34 AM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

 

Given a predicate distinguishing elements of a non-disjoint type, one

could consider 3 approaches:

1. Ambiguous with some existing type, such as integers or procedures.
The description of the predicate should indicate this with clear
warnings as for string cursors in SRFI 130, e.g. saying "_can_ be a
string-cursor".

2. A transparent subset of some existing type, such as tagged vectors.
Both `new-type?` and `vector?` will return true for instances, so the
former should take precedence.  Instances of this type can be forged,
but otherwise false positives would not normally occur in practice.

3. An opaque subset of some existing type, such as procedures tracked
in a global weak hash table.  The same caveats as the above approach
apply, but instances cannot be forged.

As there is no warning or discussion of false positives for `promise?`
I would argue the first approach is not a realistic option.  In R5RS,
where there was no `promise?` procedure, the first approach of course
was allowed and widely used.

In R7RS, all three approaches are allowed.

That turns out not to be the case.

The canons of interpretation provide (among other things), that the text of a provision must be interpreted as a whole, and that the provisions of a text should be interpreted in a way that renders them compatible, not contradictory (see <https://www.law.uh.edu/faculty/adjunct/dstevenson/2018Spring/CANONS%20OF%20CONSTRUCTION.pdf>).

The definition of make-promise is: "The promise? procedure returns #t if its argument is a promise, and #f otherwise. Note that promises are not necessarily disjoint from other Scheme types such as procedures."  Interpreting the second sentence to allow promises to be indistinguishable from some other type, per approach 1, would render the two sentences contradictory.  Therefore, that interpretation is disallowed unless no other interpretation is available.  We do, in fact, have two other interpretations available, namely 2 and 3.

Objection, your honor! Why would, if promise? yielded #t for all lists, the two sentences be rendered contradictory?

As long as every list can be interpreted (via force and delay-force) as a promise, there's no contradiction at all.

 I agree that approach 2 produces a lower quality of implementation than approach 3, and approach 4 (disjoint types) is better than either.  But QOI has nothing to do with conformance.

PS Note that R7RS also permits that implementations let promise? returns true for every object.

I also deny this.  While it is true that constructs other than delay, delay-force, and make-promise might in principle create a promise, promise? and force are applicable only to promises.  (The three extensions to force listed, including the one that allows forcing a non-promise to return the non-promise are not normative, simply a statement of what some implementations do or have done.)

I'll come back to this one once we have agreed on the above.

[John Cowan]

On Tue, Aug 3, 2021 at 2:04 PM Marc Nieper-Wißkirchen <marc....@gmail.com> wrote:

 

Objection, your honor! Why would, if promise? yielded #t for all lists, the two sentences be rendered contradictory?

As long as every list can be interpreted (via force and delay-force) as a promise, there's no contradiction at all.

Per the second half of my posting, it is not enough that force accepts random lists: it also has to be the case that every list can be returned from delay.  Under what circumstances would that be the case?

[Marc Nieper-Wißkirchen]

Where do you read that every promise has to be constructible through the delay syntax? For example, the `force' procedure speaks of promises created by delay, delay-force, or make-promise.

But even if that assumption were true, circumstances where every list (bar the empty list) would show up would not be far-fetched: The sample implementation in SRFI 45 uses lists. Now choose a list tagged with a secret object as a representation for a promise that is not yet forced.  After forcing remove the tag or replace it with a random non-secret tag.

 

PS I would like to note that this discussion is rather orthogonal to the original point raised in this thread.

[Alex Shinn]

On Tue, Aug 3, 2021 at 11:34 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> In R7RS, all three approaches are allowed.

You can't take the one statement that "promises are not necessarily
disjoint" as license to do anything. As John says, you have to
consider the full system. I don't see how you could represent
promises as integers and not have a completely broken implementation.

But agreed that this is not a particularly productive debate.

Back on topic, there is also no inconsistency within the standard.
The definition of `make-promise` is as a local utility function used
in the definition of `delay`. It existed before the procedure of the
same name was added to the standard, and has a different signature and
purpose, so can not be confused with that procedure.

We could consider a clarification erratum which states:

The utility procedure `make-promise` used in the derived syntax
definition of `delay` does
not refer to the standard procedure of that name and should be named
`%make-promise`.

There are a number of things I'd like to change about the lazy
evaluation in R7RS, but I think nothing we can change as errata.

--
Alex

[Marc Nieper-Wißkirchen]

The decision not to do anything with make-promise would leave it in a state where it is essentially useless.  In turn, this means that an erratum couldn't do any harm.

PS:

Am Mi., 4. Aug. 2021 um 07:28 Uhr schrieb Alex Shinn <alex...@gmail.com>:

On Tue, Aug 3, 2021 at 11:34 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> In R7RS, all three approaches are allowed.

You can't take the one statement that "promises are not necessarily
disjoint" as license to do anything.  As John says, you have to
consider the full system.  I don't see how you could represent
promises as integers and not have a completely broken implementation.

I never claimed that one could take any (type) predicate.  Admittedly, no one would try to represent promises as integers, and if one did so (with the help of a global integer-indexed table), it would be hard to avoid space leaks because GCing promises would then be very hard.  But I showed that "promise? = list?" is possible in a not-so far-fetched implementation approach.  Even an implementation where the delay form returns quoted datums as literal values (meaning that they also become promises) is possible and sensible as long as the corresponding force implementation returns such values unchanged.

PPS: R7RS even talks about the possibility that "there is no means by which a promise can be operationally distinguished from its forced value" in some implementations of 4.2.5.  In such implementations (which, as per R7RS, extend but do not contradict the R7RS semantics), (promise? 1) has to yield #t because (promise? (delay 1)) does (as otherwise, (delay 1) and 1 would be operationally distinguishable).  (To avoid an argumentum ad logicam: Should this non-normative remark in R7RS actually not hold in the full generality as it was stated, this would not itself refute my assertion above.)

[Alex Shinn]

On Wed, Aug 4, 2021 at 3:15 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> The decision not to do anything with make-promise would leave it in a state where it is essentially useless.

make-promise was always useless - it shouldn't have been added ;)

Don't use it - delay is all you need.

--
Alex

[Marc Nieper-Wißkirchen]

Am Mi., 4. Aug. 2021 um 08:18 Uhr schrieb Alex Shinn <alex...@gmail.com>:

On Wed, Aug 4, 2021 at 3:15 PM Marc Nieper-Wißkirchen
<marc....@gmail.com> wrote:
>
> The decision not to do anything with make-promise would leave it in a state where it is essentially useless.

make-promise was always useless - it shouldn't have been added ;)

:) I have been checking Github and haven't found any use of it yet.

A possible use I can see is in code like the following:

;; Forces a list of promises and returns their values.

(define (force* ls)

  (map force ls))

;; A library procedure

(define (foo ls)

  ... some code that expects a list of promises and may call force* on it ...)

;; A program that would like to use foo on already calculated values

(foo (map make-promise vals))

The (slightly slower) delay alternative would be

(foo (map (lambda (val) (delay val)) vals)

And, in fact, given that the vals may include values that are recognized as promises, only the delay alternative is the correct one with the current definition of make-promise.

[Marc Nieper-Wißkirchen]

Am Di., 3. Aug. 2021 um 10:46 Uhr schrieb Alex Shinn <alex...@gmail.com>:

I'm trying to recall why we exposed make-promise?  It was only used as
an example and not a pre-defined procedure in R5RS.
We modeled the delayed evaluation off of SRFI 45, which also does not
include this procedure.

I may have a partial answer: SRFI 45 includes a procedure named `eager' (that just wraps its value in a promise).  When some of the SRFI 45 names (notably `lazy', which became `delay-force') were renamed, `eager' was apparently renamed to `make-promise'.  It must have been at some later stage where the broken semantics must have crept in.

In this context, the erratum I have been wishing for would restore the semantics of `eager'.