Fwd: problem with datum label scopes

17 views
Skip to first unread message

John Cowan

unread,
Jan 9, 2019, 6:02:13 PM1/9/19
to scheme-re...@googlegroups.com, scheme-re...@googlegroups.com
I don't know what to say about this one.  After evaluating the second example, Chibi says that (eq? (car a) (car b)) => #t, so apparently ignores the second definition.


---------- Forwarded message ---------
From: Marc Feeley <fee...@iro.umontreal.ca>
Date: Wed, Jan 9, 2019 at 5:56 PM
Subject: problem with datum label scopes
To: John Cowan <co...@ccil.org>


There seems to be a problem with the R7RS specification of datum label scopes.  Section 2.4 of the R7RS says this:

The scope of a datum label is the portion of the outermost datum in which it appears that is to the right of the label.

This means that the following program conforms to the R7RS:

(define a '#0=(#0#))
(define b '#0=(#0#))

but this program does not conform:

(begin
 (define a '#0=(#0#))
 (define b '#0=(#0#)))

because it contains a duplicate definition of label 0.

This contradicts the specification of toplevel begin (Section 4.2.3):

(begin <expression or definition> ...) syntax

This form of begin can appear as part of a <body>, or at the outermost level of a <program>, or at the REPL, or directly nested in a begin that is itself of this form. It causes the contained expressions and definitions to be evaluated ***exactly as if the enclosing begin construct were not present***.

Moreover, it would appear useful to have a literal in a program referring to another literal, for example:

(define a '#0=(#0#))
(define b '(#0# #0#))

The definition of the datum label scope in R7RS does not allow this, because the references to #0# in the definition of b are not in the scope of the definition #0=.

For these reasons, the scope of datum labels should be the whole program, not just the outermost datum.

Marc

Marc Feeley

unread,
Jan 9, 2019, 9:40:24 PM1/9/19
to scheme-re...@googlegroups.com, John Cowan, scheme-re...@googlegroups.com
I’m not sure what Chibi has to do with this. The issue is with the R7RS spec.

Regarding Chibi, what could explain this is that it is allowed for an implementation to merge literals that are equal? so if those two datums are read independently they will end up being equal? and merged. The following program will probably return #f when run with Chibi:

(begin
(define a '#0=(#0# 1))
(define b '#0=(#0# 2))
(eq? (car a) (car b)))

But this program does not conform to the R7RS spec as I pointed out in my message, so I’m not sure why Chibi did not give an error.

It is important to clarify the scope of datum labels in literals otherwise they are rather useless in programs. Of course, one way to solve this would be to forbid them entirely in programs (in expressions and datums).

Marc
> --
> 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.
> For more options, visit https://groups.google.com/d/optout.

Jim Rees

unread,
Jan 9, 2019, 11:50:37 PM1/9/19
to scheme-re...@googlegroups.com, John Cowan, scheme-re...@googlegroups.com
I disagree with your interpretation, but I admit my main motivation is to try to prevent a major re-write of my reader/writer (and perhaps the same work in other Schemes).    So, I'm going to take a stab and maybe others can find better phrasing from the spec to back me up.

From 1.2:
"...the grammar of Scheme generates a sublanguage of the language used for data."

> but this program does not conform:
>
> (begin
>  (define a '#0=(#0#))
>  (define b '#0=(#0#)))

This is non-sensical because the form is not a valid Scheme datum.

> (begin <expression or definition> ...) syntax
>
> This form of begin can appear as part of a <body>, or at the outermost level of a <program>, or at the REPL, or directly nested in a begin that is itself of this form. It causes the contained expressions and definitions to be evaluated ***exactly as if the enclosing begin construct were not present***.

You cannot proceed into the spec for BEGIN to determine the meaning of a form which is not a valid Scheme datum to begin with.   If, instead you start with a valid datum:

(begin
  (define a '#0=(#0#))
  (define b '#1=(#1#)))

then the program without the encompassing begin still makes sense and has the same meaning as the program with the begin.

The composability offered by BEGIN that you are trying to infer is with respect to programs in the form of data, not their lexical representations.

Marc Feeley

unread,
Jan 10, 2019, 8:13:28 AM1/10/19
to scheme-re...@googlegroups.com, John Cowan, scheme-re...@googlegroups.com, jimr...@gmail.com
The begin form is convenient to package several expressions into one and indeed it is typically used in macros that must expand to a group of expressions or definitions. With R7RS this wrapping of expressions also exists in the define-library’s begin form. So while this is valid:

;; File: foo.sld
(define-library foo
(include "bar.scm"))

;; File: bar.scm
(define a '#0=(#0))
(define b '#0=(#0))

the following is not:

;; File: foo.sld
(define-library foo
(begin
(define a '#0=(#0))
(define b '#0=(#0))))

This is counterintuitive, just like the original example I gave with begin. One expects that wrapping a group of definitions in a begin form should always work. My point of view is that the first case should be an error, just like the second case.

This can be solved by having the scope of datum labels be all of the program’s code (to the right of the label definition). Alternatively datum labels in code could be “errors” (allowing Scheme implementations to not implement them, or implement them with different semantics). Personnaly I would prefer the first option as this is more powerful (allowing one literal to share structure with other literals). It is how datum labels are handled in Gambit.

In terms of implementation it is not a big deal. It simply means that there is a single datum label environment per file parsed (instead of one per toplevel s-expression). This is one motivation for the “read-all” procedure found in certain Schemes, including Gambit, that reads all of the datums until end-of-file and returns a list of those datums. One datum label environment should be created per call to read-all, thus allowing those datums to share structure. My point of view is consistent with the program parser being a call to read-all rather than iterated calls to plain read.

Marc

Alex Shinn

unread,
Jan 10, 2019, 8:02:02 PM1/10/19
to scheme-re...@googlegroups.com, John Cowan, scheme-re...@googlegroups.com
For the record, Chibi allows redefining labels without signaling an error - since this "is an error" that's allowed.
Thus your motivational examples work as expected in Chibi. but are not guaranteed by the standard.

--
Alex

Jim Rees

unread,
Jan 11, 2019, 2:01:49 PM1/11/19
to Marc Feeley, scheme-re...@googlegroups.com, John Cowan, scheme-re...@googlegroups.com
Ok, now I believe what you're proposing is scoping labels to the file / textual-port they are read from.   This is not the same as scoping to the library/program, because the latter would imply that an included file can reference a label defined in the including file/library.

It's an intriguing idea, and I'm fairly sure current R7RS-conforming code would still work on an implementation providing this feature.

Permitting re-definition of labels (within the current textual port) would also be reasonable, especially when the port is the REPL input.

With respect to maximizing sharing of literal data, an implementation is already free to do this automatically (since literals are considered immutable) -- my own compiler produces a single graph of all literals in a library (and other compiler-generated data such as syntax representations) and runs this through an iterative compression algorithm to save space and optimize loading.

Reply all
Reply to author
Forward
0 new messages