search

GrammaticalFramework / gf-core

Grammatical Framework core: compiler, shell & runtimes
https://www.grammaticalframework.org
Other
129 stars 35 forks source link

The semantics of empty disjunction (variants{}) #37

Open heatherleaf opened 5 years ago

heatherleaf commented 5 years ago

@aarneranta @krangelov What is the current semantics of Prelude.nonExist or variants{}? Is it intensional or extensional? (see issue #36 for more details)

I think that both nonExist and variants{} use intensional semantics, but please correct me if I'm wrong. In that case, it's a problem because people will think that nonExist is more useful than it really is.

Here are some suggestions on alternative semantics for the two:

  1. Let nonExist = variants{}, and use the extensional semantics. This can be implemented by letting nonExist refer to a non-existing token which can never occur (such as &#!$ or something similar).

    • Advantage: both nonExist and variants{} become useful.
    • Disadvantage: variants{} will have different semantics than variants{a;b}.

  2. Let nonExist and variants{} denote different semantics (extensional resp. intensional).

    • Advantage: nonExist is useful and variants{} and variants{...} will have the same semantics.
    • Disadvantage: nonExist and variants{} are not interchangeable.

  3. Let nonExist = variants{}, and keep using the intensional semantics.

    • Advantage: nonExists and variants{...} will have the same semantics.
    • Disadvantage: not very useful.

Personally I prefer solution (1), but can live with solution (2). I really don't like solution (3).

If we choose the intensional semantics, I propose we only allow the use of variants{} at the top level of a linearisation. I.e., GF should allow this:

lin f = variants{}

but not this:

lin f = {s = variants{}; ...}
heatherleaf commented 5 years ago

Please voice your opinions here! Just tagging some GF people, but everyone is of course welcome: @aarneranta @krangelov @Thomas-H @johnjcamilleri @inariksit @odanoburu

heatherleaf commented 5 years ago

Thinking a bit more, and came to the following modification to (2):

2b. Keep intensional semantics, but disallow variants{} completely. Further: let the semantics of nonExist be extensional (as in (1)).

This will make it clearer that nonExist is a different beast from variants.

johnjcamilleri commented 5 years ago

I don't have too much to add, but I think it is probably desirable that nonExist is not interchangeable with variants{} and that they mean distinct things. Making such a change will probably break some existing grammars, but if it's for the better then I'm for it.

aarneranta commented 5 years ago

Peter,

Thanks for your summary: you are certainly the world expert on the semantics of variants 😊

And I just have one strong opinion, which is: backward compatibility. This commits us to avoid changes that would break anyone's code.

The only reason ever to do this is if we find a bug that needs to be fixed. We have not promised to be bug-to-bug compatible. But even this requires thought, because it is not always clear what is a bug and what is, or has become, a feature.

So my definite vote is to keep the current behaviour of variants, |, and nonExist, as it is now and has been for many years.

This said, I am not always happy with what variants produce, and would like GF to provide alternatives, but with a different syntax so that old code retains its old semantics.

I have previously suggested something that is analogous to nonExist on the Str level, namely alternatives that are not multiplied across tables but stay on the leaves. My experiment with faking it using the pre construction showed that it would be possible without too much work (since it is the same kind of beast as pre but much simpler). And it would be very useful.

Aarne.

From: Peter Ljunglöf notifications@github.com Sent: Friday, March 8, 2019 5:02:33 PM To: GrammaticalFramework/gf-core Cc: Aarne Ranta; Mention Subject: Re: [GrammaticalFramework/gf-core] The semantics of empty disjunction (variants{}) (#37)

Thinking a bit more, and came to the following modification to (2):

2b. Keep intensional semantics, but disallow variants{} completely. Further: let the semantics of nonExist be extensional (as in (1)).

This will make it clearer that nonExist is a different beast from variants.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/GrammaticalFramework/gf-core/issues/37#issuecomment-470979840, or mute the threadhttps://github.com/notifications/unsubscribe-auth/ACwYXYGUtUlu0Y6IXHa1ZYquvsUU2A6Iks5vUomZgaJpZM4bk6QY.

heatherleaf commented 5 years ago

And I just have one strong opinion, which is: backward compatibility (...) So my definite vote is to keep the current behaviour of variants, |, and nonExist, as it is now and has been for many years

...which brings us back to my initial question: what is the semantics of variants{} and nonExist? I did a simple test, and they do not have the same semantics, in fact their current semantics is rather strange:

abstract TestAbs = {
cat S; A; 
fun s1, s2 : A -> S;
    a1, a2 : A;
}

concrete Test of TestAbs = open Prelude in {
lincat S = {s : Str};
       A = {s1, s2 : Str};
lin s1 x = {s = x.s1};
    s2 x = {s = x.s2};
    a1 = {s1 = "a1"; s2 = variants{}};
    a2 = {s1 = nonExist; s2 = "a2"};
}

Generating trees:

TestAbs> gt
s1 a2
s2 a2

Interesting! Note that a1 is not even generated, which is a bit strange since gt is supposed to work only on the abstract syntax level. (In fact, if I only import the abstract syntax, then a1 is generated...)

@krangelov is this something you implemented on prupose, or is it just a consequence of something else?

Linearisation:

TestAbs> l s1 a1
[a1]

TestAbs> l s1 a2

TestAbs> l s2 a1
[a1]

TestAbs> l s2 a2
a2

hmm... what does this mean? Let's try this instead:

TestAbs> l -table a1

TestAbs> l -table a2
s1 : 
s2 : a2

Conclusion: it seems like the current semantics of nonExist is the "extensional" one, and variants{} is "intensional". Just as my suggestion (2) above. @krangelov can you confirm or reject this?

heatherleaf commented 5 years ago

Just three more things:

  1. I still think we should disallow variants{} anywhere except on the top-level!. This is because the meaning of this:

    lin a1 = {s1 = "a1"; s2 = variants{}}

    is exactly the same as this:

    lin a1 = variants{}

    so there's no point in using variants{} anywhere else than on the top-level. It only creates confusion because grammar-writers will believe that it means something else.

    (if disallowing is not an option, then I strongly argue for deprecation)

  2. Currently nonExist can only be used as a Str, but it shouldn't be difficult to make it possible to use in place of a record or a table. Semantically, the meaning is just this:

    nonExist : {s1,...,sn : X}  ==>  {s1 = nonExist; ...; sn = nonExist}
nonExist : (P => X)  ==>  table{P1 => nonExist; ...; Pn => nonExist}

  3. The meaning of nonExist and variants{} must be documented!

krangelov commented 5 years ago

The meaning of nonExist is documented here:

http://www.aclweb.org/anthology/W15-3305

I think it is also included in the reference manual and it is definitely different from variants {}. I agree that empty variants are only useful on the top level, where they serve as a placeholder to indicate that there is a missing linearization but you don't want to see warnings from the compiler. For backwards compatibility, however, it is better not to restrict the use of empty variants in other places.

It would be better to keep the current semantics of variants except that sometimes variants are expanded too eagerly. If I remember correctly:

let x = a | b in x ++ x

results in {aa, ab, ba, bb} while I would expect only {aa,bb}. Fixing this issue is not easy but would resolve many combinatoric explosions. Currently the way out is to define:

oper dup : Str -> Str = \x -> x++x;

and then to use dup (a | b). There are many other similar examples.

On Mon, 11 Mar 2019 at 15:50, Peter Ljunglöf notifications@github.com wrote:

Just three more things:

1.

I still think we should disallow variants{} anywhere except on the top-level!. This is because the meaning of this:

lin a1 = {s1 = "a1"; s2 = variants{}}

is exactly the same as this:

lin a1 = variants{}

so there's no point in using variants{} anywhere else than on the top-level. It only creates confusion because grammar-writers will believe that it means something else.

(if disallowing is not an option, then I strongly argue for deprecation) 2.

Currently nonExist can only be used as a Str, but it shouldn't be difficult to make it possible to use in place of a record or a table. Semantically, the meaning is just this:

nonExist : {s1,...,sn : X}  ==>  {s1 = nonExist; ...; sn = nonExist}
nonExist : (P => X)  ==>  table{P1 => nonExist; ...; Pn => nonExist}

3.

The meaning of nonExist and variants{} must be documented!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/GrammaticalFramework/gf-core/issues/37#issuecomment-471570818, or mute the thread https://github.com/notifications/unsubscribe-auth/ATBZZOcAELFThZL3a_tfeOWKsaUTfWlBks5vVm06gaJpZM4bk6QY .

heatherleaf commented 5 years ago

Thanks for the clarification, I didn't know about that paper!

For backwards compatibility, however, it is better not to restrict the use of empty variants in other places.

But the compiler can give a warning when there's variants{} in any other place.

It would be better to keep the current semantics of variants except that sometimes variants are expanded too eagerly. If I remember correctly: let x = a | b in x ++ x results in {aa, ab, ba, bb} while I would expect only {aa,bb}. Fixing this issue is not easy but would resolve many combinatoric explosions. Currently the way out is to define: oper dup : Str -> Str = \x -> x++x; and then to use dup (a | b).

I tested and you're correct. I would say that's a bug - the first behavior is what I call "extensional disjunction" in my thesis, and GF otherwise uses intensional disjunction.

There are many other similar examples.

Such as the one in issue #14 ?

krangelov commented 5 years ago

On Mon, 18 Mar 2019 at 15:03, Peter Ljunglöf notifications@github.com wrote:

But the compiler can give a warning when there's variants{} in any other place.

Sure that would make sense.

There are many other similar examples.

Such as?

oper foo : Bool => Str = \x => ("a"|"b") ++ bar x

would generate:

oper foo : Bool => Str = variants {table {True => "a"++bar True; False => "a"++bar False}; table {True => "a"++bar True; False => "b"++bar False}; table {True => "b"++bar True; False => "a"++bar False}; table {True => "b"++bar True; False => "b"++bar False}};

instead of:

oper foo : Bool => Str = variants {table {True => "a"++bar True; False => "a"++bar False}; table {True => "b"++bar True; False => "b"++bar False}};

On top of that you could add some records and other tables to make the example more and more complicated.