On shadowing vs overloading

[kyouko-taiga]

I'm starting this thread to describe my proposal for the shadowing/overloading rules of Hylo.

Background

From the (still relevant part of) the specification:

General concepts - Preamble

1. An entity is an object, projection, function, subscript, property, trait, type, namespace, or module.
2. A name denotes an entity. A name is composed of a stem identifier, and, optionally argument labels and/or an operator notation and/or a method or subscript implementation introducer. Every name is introduced by a declaration unless it is a reserved keyword bound to a built-in entity.

Here are some example of names:

• foo (a stem without anything else)
• infix+ (an operator notation infix with a stem +)
• bar(ham:viz:).let (a stem bar with labels ham:viz: and an introducer let)

Note that given these definitions, first_index(of:) and first_index(where:) are not the same name!

Next are the definitions of scopes and declarations spaces. We should probably add a notion of depth to the sibling relationship because we don't want the scope of a nested extension to be the same kind of sibling of the original type declaration, so I've stroke through what I think should be overridden.

General concepts - Scopes and declaration spaces

1. A lexical scope is a region of the program text represented by a syntactic element.
2. The lexical scope of a module or namespace declaration is called a global scope. The lexical scope of a type, extension, trait, or conformance declaration is called a type scope. Unless specified otherwise, the lexical scope of any other syntactic element is called a local scope.
3. A lexical scope l1 contains a lexical scope l2 if the region of the program text covered by l1 includes that covered by l2. The innermost lexical scope that contains a lexical scope l1 and that is not l1 is called the parent of l1.
4. A lexical scope l1 is a sibling of a lexical scope l2 if l1 is the lexical scope of a trait, nominal product type, or type alias declaration d and l2 is the lexical scope of an extension or conformance declaration for the entity declared by d, or if l2 is a sibling of l1.
5. The declaration space of a scope is the set of names introduced in that scope and its siblings. The declaration space of a declaration is the declaration space of its lexical scope.

[Note: in the current implementation, files are also scopes. I think we should rather say that a file is implicitly a namespace but that is an ad-hoc discussion.]

I propose we override 4-5 as such:

4. A lexical scope l1 is bridged to a lexical scope l2 if l1 is the lexical scope of a trait, nominal product type, or type alias declaration d and l2 is the lexical scope of an extension or conformance declaration for the entity declared by d, or if l2 is bridged to l1.
5. The declaration space of a scope is the set of names introduced in that scope and its bridged scopes The declaration space of a declaration is the declaration space of its lexical scope.
6. A lexical scope l1 is a sibling of a lexical scope l1 if it is bridged to l2 and has the same parent.
7. A lexical scope l1 is a niece of a lexical scope l1 if it is bridged to l2 and l1 or one of its siblings is a descendant of l2.

[Note: these amended definitions imply that conformances at global scope are bridged but no longer siblings.]

Tentative definitions of shadowing and overloading

• A name is overloaded in a scope if it has more than one declaration introduced in that scope or its siblings.
• Given two lexical scopes l1 and l2, a name n is shadowed in l2 iff there exist declarations introducing n in the respective declaration spaces of l1 and l2 and l1 contains l2.
• A declaration in a lexical scope l1 shall not introduce a name already defined in a scope bridged to l1 unless l1 is a sibling or niece of that scope.

These definitions favor shadowing, only allowing overloading to occur in sibling scopes. Rule 1 describes when overloading occurs. Rule 2 describes when shadowing occurs. Rule 3 prevents overloading across non-sibling scopes [Note: scopes related by a aunt/niece relationship cause shadowing].

For example, it means that this program is legal:

fun negate(_ x: Int) -> Int { -x }
fun negate(_ x: Float64) -> Float64 { -x }

public fun main() {  
  print(negate(1 as Int))
}

But this program isn't:

fun negate(_ x: Int) -> Int { -x }

public fun main() {  
  fun negate(_ x: Float64) -> Float64 { -x }
  print(negate(1 as Int)) // error: cannot pass `Int` to parameter `Float64`
}

Extensions

Overloading is allowed to occur in sibling scopes, meaning that this program is legal:

public type A: Deinitializable {
  public fun foo(_ x: Int) {}
}

public extension A {
  public fun foo(_ x: Bool) {}
}

public fun main() {
  A().foo(1) // OK
}

However, the same program would be illegal if A's primary declaration came from another module.

There are a few of potential issues with this setup. First, because source files are their own scope, it means extensions of a type in different source files of the same module can't add overloads, which might be too restrictive. I see two ways to relax this rule:

1. We say that files no longer represent a scope.
2. We make an exception to the rule above so that:

• A lexical scope l1 is a sibling of a lexical scope l1 if it is bridged to l2 and:
  • l1 has the same parent as l2, or
  • both l1 and l2 children of the same module scope.

Second, this setup doesn't let you export overloads of an imported type, which may be an issue. For example, you can't write this program:

public type MyInteger { ... }

public extension Int {
  public fun infix+(_ other: MyInteger) -> Int { ... }
}

Lastly, this setup doesn't let you add specialization points in nested scopes:

type A<T: Deinitializable>: Deinitializable {
  public var x: T
  public memberwise init
  public fun foo() -> U { ... }
}

public fun main() {
  extension A where T: Comparable {
    public fun foo() -> U { ... }
  }
  A<Bool>().foo() // error: 'Bool' does not conform to 'Comparable'
}

The error occured because foo got shadowed but its new defintion is conditional. We may be able to fix this issue by saying that shadowing is conditional in this case.

Conformances

I think that shadowing should not apply to implementations participating in a conformance when methods of that conformance is used, even in monomorphizable contexts. My goal is to avoid introducing differences between the semantics of monomorphized and existentialized code.

trait P {
  fun foo()
  fun bar() { foo() }
}

type A: Deinitializable {
  public memberwize init
}

conformance A: P {
  public fun foo() { print(true) }
}

public fun main() {
  extension A {
    public fun foo() { print(false) }
  }
  
  let s = A()
  s.foo() // Prints "false"
  s.bar() // Prints "true"
  type(of: s)::P.foo(self: s) // Prints "true"
}

[dabrahams]

I find that, given the definition of “parent scope,” this is rather surprising, because two siblings need not have the same parent.

A lexical scope l1 is a sibling of a lexical scope l2 if l1 is the lexical scope of a trait, nominal product type, or type alias declaration d and l2 is the lexical scope of an extension or conformance declaration for the entity declared by d, or if l2 is a sibling of l1.

For now, though, I'll work with it.

Oh, you change the definitions further down. That's confusing. If you think you have an improved set, please just replace the old ones.

[dabrahams]

For example, you can't write this program:

public type MyInteger { ... }

public extension Int {
  public fun infix+(_ other: MyInteger) -> Int { ... }
}

What, exactly, in your scheme, makes that code illegal?

[dabrahams]

Lastly, this setup doesn't let you add specialization points in nested scopes:
(note: I fixed a typo in your example).

OK, that is an example of qualified name lookup. I expect that lookup to be through the namespace of A<Bool>, which doesn't include that supposedly-shadowing foo because A<Bool> doesn't meet the conditions of the extension.

[dabrahams]

My goal is to avoid introducing differences between the semantics of monomorphized and existentialized code.
Of course monomorphization should not affect semantics! To do otherwise would be… very C++-ish.
Your example has the effects I'd expect.

[kyouko-taiga]

What, exactly, in your scheme, makes that code illegal?

The extension is not sibling of Int because it doesn't have the same parent. Overloading is only allowed in sibling scopes.

[dabrahams]

I have a problem with the phrasing "overloading is only allowed…" because in our language there is currently no user-stated intention to overload. I can't tell whether you intend to forbid something that you are interpreting as an attempt to overload, or whether you are intending to say that overloading does not occur in these cases because something is shadowed. I could accept the latter, but without a way for the user to explicitly-state an intention to overload, I don't want to interpret anything as an illegal attempt to overload. And with a way to state that, I don't think I'd want to forbid any explicit use of that intention.

[dabrahams]

I think there's a simpler way to describe the semantics that I, at least, want.

A scope is a mapping between names and sets of declarations.

struct Scope {
  /// A mapping from a name to the set of declarations of that name in this scope.
  typealias LookupTable = [UnqualifiedName: [Declaration]]
  /// The declarations in this scope that come from the module currently being compiled
  let currentModule: LookupTable
  /// The other declarations in this scope
  let otherModules: LookupTable
  /// The nominal scope that owns declarations made lexically in this scope, if any.
  indirect let associatedNominalScope: Scope?
}

Here visibility is omitted but in any context, you can imagine that invisible declarations are not stored in the scope's LookupTable's:

There are two kinds of scopes, nominal and lexical. A nominal scope is an entity with a name, like a module or type. Lexical scopes are unnamed, like the body of a while loop. A given nominal scope can be re-opened in multiple lexical contexts, e.g. each file (lexical context) in a module opens the scope of the module, the primary declaration (lexical context) and each extension (lexical context) of a type re-opens the scope of that type. Extensions, files, and namespaces are themselves lexical scopes with an associated nominal scope. The associated nominal scope of an extension is the scope of the type being extended, etc. A method or subscript body has an implicit enclosing lexical scope with an associated nominal scope of self. The outermost lexical scope is an implicit one that merges all the public top-level declarations in any imported modules.

IIUC, this is entirely about unqualified name lookup. That is, a name in an expression not preceded by . or ::. In a.b.c that means a. The question is, how do we find out what declaration(s) a refers to? If a refers to multiple declarations, those declarations are overloaded.

My proposed algorithm:

/// Returns the declarations named by `n` when it is written without qualification in `lexicalContext`,
/// the surrounding lexical scopes from innermost to outermost. 
func lookupUnqualified(_ n: UnqualifiedName, from lexicalContext: [Scope]) -> [Declaration] {
  for s in lexicalContext {
    let r = (s.associatedNominalScope ?? s).localDeclarations(of: n, visibleFrom: lexicalContext)
    if !r.isEmpty { return r }
  }
  return []
}

extension Scope {
  fun localDeclarations(of n: UnqualifiedName, visibleFrom lexicalContext: [Scope]) -> [Declarations] {
    currentModule[n] ?? otherModules[n] ?? []
  }
}

The basic rules upheld are:

• declarations in inner lexical scopes hide declarations of the same name in outer lexical scopes.
• a declaration made in the current module of a name in a nominal scope hides any declaration of that name made in other modules.

Examples:

// Module M                     Declares           Uses
let a = "ayyy"			M.a
let b = a                    	M.b                M.a
let c = 3                       M.c
let d = 4                       M.d

type X {
  let a = 3                     M.X.self.a
  static let a = 4              M.X.a
  let b = a                     M.X.b              M.X.a

  type Y {
    let a = true                M.X.Y.self.a
    let b = a                   M.X.Y.self.b       M.X.a
    fun f() -> any { a }        M.X.Y.self.f()     M.X.Y.self.a
  }
}

extension X {
  let c: any { a }              M.X.self.c         M.X.self.a
  static let d = a              M.X.d              M.X.a
  fun f() -> any { a }          M.f                M.X.self.a
}

extension X.Y {
  let z0: any { d }             M.X.Y.self.z0     M.d
}

extension X {
  extension Y {
    let z1: any { d }           M.X.Y.self.z1      M.X.d
  }
}                      

[kyouko-taiga]

IIUC, your algorithm roughly corresponds to the current implementation, with the difference that we have an exception for overloadable symbols in the loop. We exit if r is not empty and r contains at least one non-overloadable symbol. We can turn off this exception and see where that leaves us, as a first experiment.

However, I don't think unqualified lookup is the only part of the equation that we have to look at. See below.

Further, the whole lookup algorithm is only one side of the problem. Another side is to define when a declaration is considered duplicate in a particular scope. The type checker must be able to make such a decision without any use.

A given nominal scope can be re-opened in multiple lexical contexts [...]

That might also be a little too simplistic. For example, we may want to say that you can extend a nominal scope "in itself" and apply shadowing rules:

type A {
  fun f(_ x: Int) {}
  fun g() {
    extension A { fun f(_ x: Int) {} }
    f()
  }
}

Here re-opening A instead of looking at the extension as a separate scope would leave this program illegal.

Here visibility is omitted but in any context, you can imagine that invisible declarations are not stored in the scope's LookupTable's:

Visibility rules, if possible, should be applied after name resolution. Having diagnostics of the form "foo is not visible because blabla" is incredibly useful. It's another story if the names are invisible because they simply aren't in the AST (e.g., they come from a pre-compiled module).

A given nominal scope can be re-opened in multiple lexical contexts

I suppose namespaces are nominal scopes in your definition. Should we be allowed to extend namespaces?

We can certainly extend uninhabited enums in Swift, which are the moral equivalent of a namespace so I think that is a reasonable feature.

each file (lexical context) in a module opens the scope of the module

IIUC that means that a file isn't its own scope. I'd like to preserve the ability to use a file as a scope at least for now. I find this feature useful in Swift. Namespace partially address the issue but at the cost of nesting.

Extensions, files, and namespaces are themselves lexical scopes with an associated nominal scope

Wait, then why are the files re-opening the module scope?

IIUC, this is entirely about unqualified name lookup.

I don't think that is true. The rule will apply to qualified lookup too.

type A {
  public static fun f(_ x: Int) {}
}

public fun main() {
  extension A { static fun f(_ x: Float64) {} }
  A.f(0) // This is qualified lookup
}

The part of the algorithm that deals with that is what you've named localDeclarations(of:visibleFrom:). In the implementation that is the family of type checker methods that look like lookup(_:in:exposedTo:). One key part of this algorithm is the enumeration of the members found in extensions (lookup(_:inExtensionsOf:exposedTo:)). I strongly suspect that if we visit extensions in the proper order here, we'll implement shadowing as expected.

[dabrahams]

However, I don't think unqualified lookup is the only part of the equation that we have to look at. See below.

True.

Further, the whole lookup algorithm is only one side of the problem. Another side is to define when a declaration is considered duplicate in a particular scope. The type checker must be able to make such a decision without any use.

OK, that's easy to answer in my preferred semantics. Let me take another stab at that in a separate post.

each file (lexical context) in a module opens the scope of the module

IIUC that means that a file isn't its own scope. I'd like to preserve the ability to use a file as a scope at least for now. I find this feature useful in Swift.

I don't think you do… because I don't think Swift has that feature 😉 IIUC, access control like fileprivate is entirely a matter of visibility. I just compiled two simple files into the same module; you can see their contents in the daignostics:

/private/tmp/q/Sources/q/r.swift:1:17: error: invalid redeclaration of 'x'
fileprivate var x = 3
                ^
/private/tmp/q/Sources/q/q.swift:1:14: note: 'x' previously declared here
internal var x = "yes"
             ^

Extensions, files, and namespaces are themselves lexical scopes with an associated nominal scope

Wait, then why are the files re-opening the module scope?

Because a declaration in each file in the module is… in the module's scope? If the module name is M and I define f and g at the top-level of two files, they are fullly-qualified-named M.f and M.g.

[kyouko-taiga]

I don't think you do… because I don't think Swift has that feature 😉 IIUC, access control like fileprivate is entirely a matter of visibility.

Oh, interesting! Thanks for clarifying that for me.
Then I welcome your idea.

We may even consider that files simply are the module scope. Having files being individual scopes has introduced various complexities in the implementation. Of course that means you wouldn't be able to shadow a definition in a new file.

Because a declaration in each file in the module is… in the module's scope? If the module name is M and I define f and g at the top-level of two files, they are fullly-qualified-named M.f and M.g.

👍

[dabrahams]

Attempt no. 2 to describe my rules.

For context, I want to uphold a principle of modularity. That is, an access from module X to a name n declared in X should not change its meaning or become illegal due to importing module Y. I believe this principle may need to be compromised/refined a bit due to the possiblity of Y introducing a conformance P: Q that changes the meaning of some access. However, if X also supplies a P: Q conformance I think the principle can and should be upheld.

This is still mostly about name lookup. I'm going to try to state some rules instead of spelling out an algorithm to implement them. I think this list of rules is probably slightly incomplete, but I hope we can amend it until it covers everything. I believe it should also be extended to cover conformances.

1. Scopes can be nominal (associated with a named entity such as a type, module, or namespace) or purely lexical.

2. The scope associated with an extension of type T is the scope associated with T.

3. For each named entity E with associated scopes, each module declaring a name in E supplies a distinct scope.

4. There is only one scope associated with any module; one module cannot declare names at the top level of another.

5. A name that is defined multiple times in a scope is considered to be overloaded in that scope.

6. A program that overloads an entity other than a function in some scope is ill-formed (illegal overloading).

7. In any scope all declarations of overloaded entities must all have distinct types.

8. Scopes participating in name lookup are partially ordered by priority.

9. If lexical scope A is nested in lexical scope B, A has higher priority than B.

10. If lexical scope A is lexically nested in an entity E, A has higher priority than the scope associated with E.

11. At any lexical position p in module M:

    1. Lexical scopes containing p participate in name lookup.
    2. Some names are visible and some are hidden.
    3. A name can be hidden by access control (e.g. public/private)
    4. A name is hidden by any declarations of the same name in any higher-priority scope (shadowing).
    5. A name that is hidden by shadowing can still be accessed using some form of qualification.
    6. The scope associated with entity E supplied by M has priority over other scopes associated with E.
    7. If a used name without explicit scope qualification is visible in multiple scopes, the program is ill-formed (ambiguity)

Let me know what you think.

[kyouko-taiga]

There is only one scope associated with any module; one module cannot declare names at the top level of another.

Just to confirm my understanding: conditional extensions of an entity E are in the same scope as any other associated scope of E, right?

A name that is hidden by shadowing can still be accessed using some form of qualification.

That might be difficult in cases extensions are nested.

type A {}
public fun main() {
  extension A {
    fun foo() {}
    fun bar() {
      extension A { fun foo() }
      // What is the qualified name of `A.foo()` declared in the outer extension?
    }
  }
}

Let me know what you think.

I think it's a solid start but I wonder if the priority rule is sufficient to cover this case:

type A {}

extension A { public static fun foo() }

type B {
  extension A { public static fun foo() {} }
  public static let x = A.foo()
}

I don't think your definition orders the two extensions, meaning that foo has a duplicate definition. Note that this example is or becomes legal, then it also shows a situation where qualification might be difficult to pull off.

[kyouko-taiga]

I'm starting to wonder if perhaps we'd be better off simply requiring an overloaded modifier on names that the user intends to overload. Part of my rationale is that I think this situation is confusing:

public fun main() {
  extension Int {
    public fun infix+(_ other: String) -> Int { ... }
    static fun two() -> Int { 1 + 1 } // error: value of type `Int` can't be passed to parameter of type `String`
  }
}

The problem here is that because the extension has higher priority (under either Dave or my rules), Hylo.Int.infix+ got shadowed. We can certainly explain why that occurs, but I don't think this is a behavior anyone would actually want.

The overloaded modifier would make it clear that the user's intent is to add a definition to the overload set of an existing name. Without overloaded, it would always be illegal to declare a name multiple times in the same scope (included bridged/associated scopes) unless they have some kind of ordering (that is the purpose of my niece/aunt relationship, which I believe subsumes Dave's priority definition).

Some examples:

public type A {
  public fun foo(_ x: Int) {}
  public fun foo(_ x: Int8) {} // error: illegal overload; did you forget `overloaded`?
}

public type B {
  public fun foo(_ x: Int) {}
  public overloaded fun foo(_ x: Int8) {} // OK
}

public type C {
  public fun foo(_ x: Int) {}
}

public fun main() {
  extension B {
    public fun foo(_ x: Int16) {} // OK, shadowing applies!
  }
  extension C {
    public fun overloaded foo(_ x: Int16) {} // OK
    public fun overloaded foo(_ x: Int) {} // error: cannot overload name with identical type
  }
}

[kyouko-taiga]

Following the meeting discussion on Aug. 7th, here is another attempt at specifying the overloading/shadowing situation. The principle we hope to maintain are:

• We want to support modularity: adding new declarations in distant parts of the code should not have a local impact.
• We want an approach consistent with scoped conformances.
• We are biased toward a simple systematic rule, even if it may negatively impact esoteric corner cases.

With that being said, here are the rules:

Scopes and relationships

1. A lexical scope is a region of the program text represented by a syntactic element.
2. A lexical scope l1 contains a lexical scope l2 if the region of the program text covered by l1 includes that covered by l2. The innermost lexical scope that contains a lexical scope l1 and that is not l1 is called the parent of l1. The lexical scopes that contain l1 are called its ancestors. If l2 is the parent of l1, then l1 is a child of l2. If l2 is an ancestor of l1, then l1 is descendant of l2.
3. Given two lexical scopes l1 and l2, l1 is said deeper than l2, written l1 < l2 iff:
   1. l2 is the scope of a module imported in the module containing l1;
   2. l2 is descendant of a module imported in the module containing l1;
   3. l1 and l2 are in the same module m and l1 has more ancestors than l2.

Example:

// `Foo.hylo` in module Foo
public type A: Deinitializable {
  public memberwise init
}

// `Bar.hylo` in module Bar
import Foo

public extension A {
  public init(_ x: Int) { self = A() }
}

// `Qix.hylo` in module Qix
import Foo

public extension A {
  public init(_ x: Int) { self = A() }
}

// `Ham.hylo` in module Ham
import Foo
import Bar
import Qix

public fun main() {
  _ = A()
}

The following statements hold:

• The scope of the main function is deeper than the scopes of the modules Foo, Bar, Qix, and Ham.
• The scope of the extension in Bar.hylo is deeper than the scope of the type declaration in Foo.hylo.
• The scope of the Ham module is deeper than the scopes of the Foo, Bar, and Qix modules.
• The scope of the Qix module is deeper than the scope of the Foo module.
• The scopes of the Bar and Qix modules are unordered.

Nominal scopes

1. Modules, namespaces, traits, type aliases, and product types have a nominal scope. Declarations introduced in a nominal scope can be qualified by the name of the entity associated with that nominal scope.
   1. The nominal scope of a module consists of all the source files in that module.
   2. The nominal scope of a trait or namespace consists of the lexical scope of that declaration with the lexical scopes of the extensions of that trait or namespace.
   3. The nominal scope of a type alias consists of the scope of its generic clause.
   4. The nominal scope of a product type declaration consists of the lexical scope of that type declaration with the lexical scopes of the extensions and conformances of that type.

Scope exposition

1. A lexical scope l1 is exposed to a lexical scope l2 iff:
   1. l1 is descendant of l2.
   2. l1 is contained in a module imported in the scope containing l2.

Shadowing

1. A declaration introduced in a lexical scope l1 shadows declarations with the same name in all scopes exposed to l1 but not deeper than l1.

Name lookup

Name lookup in a nominal scope n from a lexical scope s is implemented by the following algorithm:

1. Gather all declarations introduced in n.
2. Exclude all declarations introduced in scopes not exposed to s.
3. Exclude all shadowed declarations.