Open question: Calling functions defined later in the same file

[jonmeow]

In C++, calling functions defined later in the same file requires a forward declaration. Do we need to support the same for Carbon, or can this instead be addressed by name lookup?

#438 has this as an open question.

For example, can this be legal code:

fn Bar() {
  Foo();
}

fn Foo() {
  Print("Called a later define from Bar");
}

I briefly asked this to @zygoloid and we're okay not ruling this out for now. He did bring up wanting to have a single consistent name lookup rule for things both inside and outside functions. For example, the following lookup of x might work, but could error with "refers to x outside its lifetime":

fn F() {
  x = 0;
  Int x;
}

This does touch on #424 (@jsiek).

[jonmeow]

A couple thoughts --

An advantage of requiring a forward declaration is that it means things (readers) only need to look up when reading a file.

An advantage of using name lookup to solve this is that it means readers/writers only need to deal with the definition. i.e., they may need to look in both directions to find it, but they won't first find a forward declaration then need to keep reading. Similarly, a code maintainer doesn't need to keep a forward declaration in sync.

I think using name lookup to solve this is more consistent with other languages (C/C++ is exceptional for using forward declarations).

[jonmeow]

On #438, @josh11b said regarding keeping a forward declaration in sync:

I think this is more of a problem in C++ than Carbon. In C++ you frequently use forward declarations to refer to functions defined in other libraries. In Carbon we can enforce that every forward declaration has an implementation in the same library.

I believe this accurately reflects the ability of a compiler to detect issues, but requiring forward declarations is still adding developer toil.

[chandlerc]

To briefly state my preference, I would like to take the restrictive approach here of requiring a forward declaration.

I understand that we can relax this with name lookup rules, but currently I'm in favor of avoiding it. I think it makes name lookup and other things simpler. I also think it is nice to have the "only look up" rule.

The other important factor is that I think there will be a strong need to have forward declarations even without relaxing this. So in the cost/benefit analysis of allowing calling functions later in a file, I don't think the benefits include "no more forward declarations in the language". Without that benefit, I think the costs aren't justified.

[jonmeow]

Do you think that the complexity will be to the implementation of Carbon, or complexity as perceived by developers using Carbon?

In Code and Name Organization, it's called out that small libraries could be in a single api file. However, if forward declarations are required, wouldn't that api file naturally split out into API and implementation portions? If the outcome of this question is that forward declarations are required, should Code and Name Organization be updated to more strongly recommend api and impl splits for all libraries?

[josh11b]

My guess is that @chandlerc meant "requiring forward declarations to call a function defined later in the file", but we may have to wait for him to get back from his vacation to get clarification.

[josh11b]

@chandlerc just confirmed my interpretation over chat.

[chandlerc]

FWIW, I also think Jon's question is reasonable. But I think there will be libraries that want to use a single file (even if the have some cyclic reference requiring forward declarations) because that simplifies their build / distribution / whatever. I hope we have package management sufficient to obviate many if not all of these concerns, but it still seems good to allow a single file when desired.

[jonmeow]

I think this is a bit of an aside, but I would anticipate the top reason for a single file to be simplifying development. That is, in multi-file development, it's necessary to have edit both files in tandem, sometimes searching in each for definitions.

--

From @josh11b's comment, I think I'm being misunderstood, so let me try to clarify my comments: I'm trying to suggest how developers would affect in ways that affect the understandability goal.

I believe most developers would prefer to have the API at the top of the file, and internal implementation calls towards the bottom.

I'm following a chain of thought that functions will call other functions, or access data. Typically the functions that call others are higher-level, and would more naturally float to the top of an API description. Forcing "only look up" inverts that ordering unless forward declarations are used for the API functions. C++ effectively does that with .cc files, but I don't think anybody really expects a library to exist in a .h file alone.

In the case of a single api file library, the tension is that either the library is so small that ordering doesn't matter, or the developer puts the API at the top as forward declarations. In the latter case, it's similar in essence to splitting files, but may be preferable to ease maintainability (i.e., that fewer files are better). Maybe they'd also inline shorter functions where possible.

However, I perceive it as a strong push towards api and impl split, if combined with code understandability concerns. Even if the file split isn't required, the organizational split is being pressured, especially for developers already accustomed to these pressures in C++. I tend to assume the main reason we'd do "only look up" is because it can imitate C++, and so these pressures are accepted.

--

In chat, I also brought up structs and whether consistency with the "only look up" rule would also apply there. I think this has stronger understandability implications, as it breaks consistency with C++.

In particular, I assume we'll provide something like "private" and "public" access controls in C++. C++ Core Guidelines and Google C++ Style are examples that place "public" before "private", and functions before data.

When implementing a class, I would typically expect that public functions call private, and private functions may use both public and private variables. As a consequence of an "only look up" rule, Carbon style should invert the C++ ordering to follow "only look up": place "private" before "public", and data before functions.

There would further need to be exceptions where, for example, a private function may reuse a public function. Forward declaring classes would only be a partial solution, as trivial functions (particularly accessors and mutators) would be start to dictate order:

struct Circle {
  private Int radius;

  fn get_radius() -> Int { return radius; }

  fn GetArea() -> Int { return Math.Pi * radius * radius; }
}

I would tend to expect APIs to be at the top of files, which is the opposite of what an "only look up" rule leads to. So while I may not grasp the amount of implementation complexity this adds, I do see this as an ongoing writability and understandability issue for developers. Lacking examples of this limitation in other languages, I also see an "only look up" rule as an undesirable innovation of Carbon.

[zygoloid]

I have a strong desire and a weak desire here. Setting aside, for the moment, scopes in which declaration order has an inherent meaning (such as in a function body where declaration order implies ordinary execution order):

Strong desire: reordering declarations within a scope cannot change one valid program into another valid program with a different meaning.
Weak desire: reordering declarations within a scope cannot change the validity or meaning of the program.

We can accommodate my strong desire alone, by restricting name shadowing and being careful about making negative properties ("has this type not been defined yet?") observable, without making the processing actually be order-independent.

I think these are the costs associated with making declarations within a scope be order-irrelevant:

• Divergence from C++ (although programmers would probably thank us, and C++ already does look down within a class definition)
• Potentially more implementation complexity (although we might actually improve parallelization opportunities?)
• Potentially different behavior in a function versus outside

Regarding implementation complexity, something we need to think hard about is phase ordering. If we allow:

1. A function defined in a source file can be used at compile time in the same source file, and
2. The definition of such a function can reference things that are declared later in the same source file

... then we have a problem that can easily lead to circularities:

fn F() -> Type { return G(0); }
fn G(F() n) -> Type { return Int; }

(though in practice the circularities might be a lot less obvious). Here, we can't type-check F before we can look up G and evaluate a call to it, and we can't type-check G before we can look up F and evaluate a call to it. It's probably feasible to say that any such circularity is an error, but it might be hard to tie down exactly what constitutes a reference that adds an edge to our circularity graph without constraining what amount to implementation details.

Prior art, in languages with some amount of order-independence and also some amount of metaprogramming (more examples would be useful):

• C++ supports order-independence within class definitions, but it's largely underspecified and somewhat broken due to this phase ordering problem. The approach taken by compilers is to define a specific order in which certain processing actions occur, but that order varies between compilers and there is no order that accepts all reasonable cases. The latest thinking is that C++ will attempt a "circularities are invalid" approach.
• GHC's metaprogramming functionality, Template Haskell, deals with this problem by splitting scopes into chunks separated by metaprogramming actions, and only providing order-independence within each chunk. I don't think that would fit well into Carbon's metaprogramming approach.
• Python implicitly has an "only look up" model, but due to the language's dynamism, globals can be referenced in a function body before they are introduced, so long as they're introduced before the function is actually called (or more specifically, before the use is evaluated).

[zygoloid]

If we decide to require function declarations to precede calls in all cases, we will need to revisit #438, which says:

Forward declarations will experimentally only be allowed in api files, and only when the definition is in the library's impl file. The intent is to minimize use, consistent with most other languages that have no forward declaration support at all.

... but this would prevent (for example) mutually recursive functions that are not part of the API of a library from being defined an an impl file.

[chandlerc]

I'd like to suggest we start with a restrictive rule that declarations must precede unqualified names in all cases. Reasons:

1. Extremely simple rule both to teach and to implement.
2. Consistent even within function bodies.
3. No problems with metaprogramming facilities.
4. Relatively easy to relax this rule in the future if we need to.

I think the biggest issue is the ergonomic cost to member functions defined lexically inside the class body. That is the one place where C++ currently works to provide order-independence and regressing that I think would be very costly for users.

However, the design we have for member functions has already solved this problem because we aren't using unqualified name lookup to find instance members, and instead providing an explicit object parameter me. So the things that work in C++ today would largely work in Carbon. Examples including what wouldn't work:

class X {
  fn Method[me: Self]() {
    // This would be an error:
    var y: NestedType = {};

    // But this would be fine:
    var z: i32 = me.OtherMethod().GetNumber();
    assert(z == 42);
  }

  class NestedType {
    fn GetNumber[me: Self]() -> i32 { return 42; }
  }

  fn OtherMethod[me: Self]() -> NestedType {
    return {};
  }
}

But requiring nested types to be forward declared (or the member function defined out-of-line) seems much less burdensome than requiring it for all instance members. The use of me in the member functions should make this almost the same ergonomic quality as C++ but with substantially simpler rules.

What do folks think?

(edited to provide a more complete example)

[jonmeow]

To help me respond, are there options that don't require forward declarations? Considering the particular line, would var y: me.NestedType = {};, var y: X.NestedType = {};, or var y: MyPackage.X.NestedType = {}; legal in the above code, or does this me model only work for instance members? (would code like this work?)

[chandlerc]

To help me respond, are there options that don't require forward declarations? Considering the particular line, would var y: me.NestedType = {};, var y: X.NestedType = {};, or var y: MyPackage.X.NestedType = {}; legal in the above code, or does this me model only work for instance members?

Whether me.NestedType works is somewhat a question of how we define . to work here -- I don't think this decision impacts it either way.

And I'd expect MyPackage.X.NestedType and X.NestedType to work fine. I can't see any reason for it not to work.

We have to defer type checking the body of lexically nested member function definitions -- otherwise they'd be incapable of calling any member functions on me, regardless of where they are declared, because it would have an incomplete type. And type checking is always what determines name lookup of a name after a ..

So the only really interesting question is what to do with unqualified name lookup. Having that not depend on type checking seems valuable -- it lets us determine the relationship between top level declarations without doing (potentially expensive, and potentially impossible for mid-edit files) type checking or loading imports.

(would code like this work?)

With me.value? Yes.

[josh11b]

To clarify the extent of this rule, within a file would you be able to refer to functions defined later as long as you didn't use an unqualified name for them?

[chandlerc]

To clarify the extent of this rule, within a file would you be able to refer to functions defined later as long as you didn't use an unqualified name for them?

I think this is a somewhat separable set of questions.

For qualified names derived from a type, there is a compelling argument that they should be part of type checking, and we're expecting the set of names to be complete when the type is complete. And then, where you can reference a name within a type before it is complete (lexically nested method definitions for example), that needs to wait until complete and be consistent with name lookup when complete.

For qualified names from a namepspace I think we could try to make them work in either way if we want. Personally, I would prefer for namespaces to work very similarly to unqualified name lookup -- we've been trying to articulate them as just a useful way to build structured names. They're never "complete", etc. And so for me, that indicates the model I would prefer. While unqualified is "only look up", I'd suggest the same rule for namespaces.

[chandlerc]

Chatted again with @zygoloid and we're both pretty happy with the direction I suggested above. I think @zygoloid is going to work on a proposal to actually document this design.

---

To more fully answer @josh11b's question around whether qualifying the name would allow use further down in the file, and my prior answer was more complicated than it needs to be. The idea here is to lookup each name in a dotted sequence as early as possible. We should keep doing that lookup until we find a name that we cannot lookup until some form of deferred type checking. We handle the type of a class inside its definition the same way we would handle type template parameters (if we have templates) -- they're "dependent" until the end of the class definition, and then we finish the type checking.

The results of this rule are:

• For unqualified names, this is immediate and it always looks "up".

• For names qualified by the type, it is as soon as that type is complete (or ceases to be dependent for a template if/when we have templates). Inside the body of a class type, that defers Self.Foo until Self is completed by closing the class definition.

• For names qualified by a namespace, this is immediate because there is no point at which the namespace would be "complete".

But the difference between when a name qualified by a namespace and by a type is looked up above doesn't result in anything surprising within class definitions -- the set of namespace names doesn't change between inside the class body and it being completed. The difference is only observable with templates, and even then the original consistent rule is followed in both cases. We always walk as far down the dotted sequence of names as we can, and stop when we find the type of an enclosing class body or a dependent type.

We can even imagine namespace names that are dependent:

fn F(template T:! Type) {
  // `T` is dependent here, and so we don't lookup `M` at definition time.
  T.M.G();
}

namespace N;

fn N.G() {}

class X {
  alias M = N;
}

fn Test() {
  // When we call `F` with `X`, we will instantiate the template,
  // and lookup `X.M`. This finds an alias `M` of namespace `N`.
  // At this point, `N.G` has been declared so we can find `X.M.G`
  // during the deferred type-checking triggered phase of lookup.
  F(X);
}

One observation of this example that I didn't realize when discussing with Richard: it means we have the possibility of ODR violations of templates, because we have allowed dependent lookup into an extensible space -- namespaces. Two different calls to F in two different files can instantiate the same template with a different set of functions in the namespace N here and get different results. It is not as bad as C++ yet. You either need to define N.G twice and differently, which we should be able to diagnose at least at link time, or you need to detect whether N.G exists somehow without causing an error if it does not exist. As long as we preclude this latter step, I don't think this is an especially scary issue, but its one we should be aware of and plan for how we detect and reject reasonably reliably.

It is tempting to ask if doing name lookup globally would remove the potential ODR issue, but globally within the file doesn't help at all. It would need to do lookup across all the files that could define N.G, and I don't see any way to do that helpfully. And if we could, we could also just reject the issue immediately regardless of name lookup rules. I don't think the two different name lookup rules discussed here have a difference.

There is a name lookup strategy that would help with the ODR issue: we could insist that even a dependent namespace lookup only looks "up" lexically, regardless of when it is instantiated. This would define away the ODR issue I think. However, we should be careful that this more restrictive model doesn't break real use cases for aliasing a namespace.

Another change we could make to define away this problem is to disallow aliasing a namespace as a member of a class. This is what I suggest, as it would make things more uniform IMO. Using an alias to create a nesting structure that cannot be created without an alias seems bad to me. But this is an orthogonal change to name lookup rules IMO.

[jonmeow]

I'd like to note a consequence of #665 and #752 if forward declarations in the same file are required, and visibility markers on the separate definition are disallowed.

Consider an api file:

package Foo api;

private fn PrintLeaves(Node node);

fn PrintNode(Node node) {
  Print(node.value);
  PrintLeaves(node);
);

fn PrintLeaves(Node node) {
  for (Node leaf : node.leaves) {
    PrintNode(leaf);
  }
}

In the above example, someone reading the definition of PrintLeaves may incorrectly observe that because (a) there are no keywords and (b) it's in the api file, that the definition of PrintLeaves must be public.

A few approaches that I think would address this:

• Change the decision on private vs public *syntax* strategy, as well as other visibility tools like external/api/etc. #665 to require keywords all the time, so the definition of PrintLeaves would have private.
• Disallow separate definitions in the api file. The definition of PrintLeaves must be in the impl file, which per private vs public *syntax* strategy, as well as other visibility tools like external/api/etc. #665 already requires looking at the api file to determine what's public.
  • Still need to allow forward declarations and separate definitions in impl files, so api files become extra special.
• Allow looking down for names, and disallow forward declarations of names in the same file. This eliminates the forward declaration of PrintLeaves while allowing the definition of PrintLeaves to remain in the api file, just requiring the private keyword to be added.
• Keep up-only name lookup and disallow keywords on separate definitions, keeping the risk of visibility confusion from forward declarations.
• Use some keyword to indicate a separate definition, such as def fn.

[jonmeow]

Noting a comment @chandlerc in meeting made about this applying to forward declarations of member functions, I think that would turn the definition into Tree.PrintLeaves; seeing the mention of the class name there would probably make it more apparent to developers to look at the declaration in the class. I mainly think it's a readability issue for free functions.

[github-actions]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time.
This issue is labeled inactive because the last activity was over 90 days ago.

[chandlerc]

@zygoloid and I have had a series of discussions about this, trying to make progress.

To be clear, we see two primary directions that we could pursue here:

1. Basically, resolve things in dependency order, regardless of the order within the file. Similar to deferring and being lazy about name lookup. Any name lookup within a file that doesn't form a real cycle is allowed.
2. Attempt to have names declared prior to their use, as much as possible.

The approach needed for (1) seems clear and well understood. Similarly, the consequences of that approach. I won't try to spell out that in more detail.

There are some concerns with approach (1) that motivate looking at (2) at all. This isn't intended to be all of the concerns or even a ranked list, but just examples:

• C++ behaves very much like (2), and readers familiar with C++ may expect that.
• Similar to prose, it seems likely to be considered good style to introduce terms prior to referencing them and minimize forward references to improve readability. At least some readers have a fairly strong preference. That then raises the question of whether the language should encourage or enforce this.
• It helps provide more obvious semantics in the presence of metaprogramming. Other languages following (1) have had to add rules specifically around metaprogramming to make things work well.
• Continuing to support physical separation of implementation from interface means we expect to have forward declarations and the core of that language complexity regardless of the decision, removing one significant advantage of (1) in other languages.

There is also a very specific ergonomic use case that motivates not strictly following the direction of (2): inline nested function definitions. We both see a very strong use case for allowing the definition of functions nested within classes, where the class type is complete within the function body. This is pervasively used in C++, and Carbon further relies on it for easy definition of factory functions.

Unfortunately, the original suggested rules for (2) don't work well when considering both inline and out-of-line method definitions in classes with inheritance or parameterized classes. The rules would cause inline and out-of-line definitions to have surprising different rules around name lookup. These would both hurt the ergonomics of inline definitions or create significant confusion (or both).

In our discussions, I think we came up with a simpler alternative semantic model for (2) that doesn't have these problems. It focuses very specifically on nested function definitions as an ergonomic affordance, with rules to make it effective at being ergonomic.

---

We start from an extremely simple set of rules: names must be declared before they are used. It applies consistently to all unqualified names. Further, the information being used should be introduced before it is used. If you want to write A.B for a class type A, it can't just be forward declared, it has to be defined first. If you want to call a function as part of computing a type like var arr: Array(i32, ComputeSize());, you have to define ComputeSize first, not just declare it.

Without function bodies nested within classes, this works well. It largely forces a topological order to the source code, but allowing explicit forward declarations to deviate from that or break cycles when needed. It matches the simple and well understood parts of C++'s rules. It also causes the source to show in an obvious way the inherent acyclic order that must exist. Places where approach (1) would detect a cycle and reject, there would also be no viable source order.

Then we handle nested function definitions specially. For example:

class C {
  // ...

  fn MyMethod[me: Self](i32 x, i32 y) -> Self { return {x, y, me.z}; }

  private var x: i32;
  private var y: i32;
  private var z: i32;
}

The '{}'-ed body of MyMethod would be parsed exactly as if it were written after the closing } of C:

class C {
  // ...

  fn MyMethod[me: Self](i32 x, i32 y) -> Self;

  private var x: i32;
  private var y: i32;
  private var z: i32;
}
fn C.MyMethod[me: Self](i32 x, i32 y) -> Self { return {x, y, me.z}; }

Here, all the nested function definitions are parsed as-if defined out-of-line immediately after we return to the top level of the file, exactly in the order they are written. So with two levels of nesting and some other interesting cases:

class X1 {
  fn Function1() -> Self { ... }

  class X2 {
    fn Function2() -> Self { ... }
  }

  // This is fine, but cannot use `Self.X2` as the type.
  var x2: X2;
}

The result would be as if:

class X1 {
  fn Function1() -> Self;

  class X2 {
    fn Function2() -> Self;
  }

  // This is fine, but cannot use `Self.X2` as the type.
  var x2: X2;
}
fn X1.Function1() -> Self { ... }
fn X1.X2.Function2() -> Self { ... }

Basically, nesting function definitions is just an ergonomic affordance, nothing more.

An advantage of this formulation of (2) is that the rules seem very simple to teach and reason about, and it ensures nested definitions don't behave differently from out-of-line definitions.

There are a number of corner cases that make C++'s version of this much more complex, but I think we can pick simple answers for Carbon by focusing on inline definitions being a convenience ergonomic feature.

• You cannot call any nested functions as part of the definition of the class, any more than you could call a function defined out-of-line immediately after the class as part of its definition.
  • Instead these would need to be defined first. This seems especially easy with a modules system and the definition can be aliased into a class if desired as part of its API.
• The order the nested function definitions occurs in the source is the order in which they are parsed at the top level. That may mean one nested function's definition cannot use at compile time (array size) a later function definition.
  • This can be addressed the same way as the prior case or by defining the function out-of-line, and it seems rare and not motivating any additional complexity.
• Default arguments, member initializers, etc. don't have any special behavior, they are parsed where they are written.

The first point is the really big simplifying thing, and it makes inline and out-of-line definitions much more consistent. Without this, inline/nested definitions can't consistently have the type be complete or declare variables of that type. Whether that would be allowed depends on whether the function is called as part of defining the type (and thus creating a cycle).

All of these together fit with the consistent model of nested definitions being exactly the same as out-of-line definitions at the top level.

---

With this (much improved) idea of how (2) would work, I think both @zygoloid and I were at least convinced that both (1) and (2) would be workable and not have serious problems. They seem like reasonable directions, and the question is now much more -- what direction is best?

It's worth noting that we could treat unqualified name lookup independently from qualified name lookup here if we wanted, but so far that hasn't significantly helped us get closer to consensus.

Another thing worth noting is that as (2) is phrased here, there would be a smooth evolution path towards (1) if desired, and there again qualified and unqualified name lookup could evolve independently towards (1) if desired. Valid programs under (2) would also be valid and have the same meaning as (1).

This feels related to the aesthetics of the language, how critical it is to have code organization follow similar structures to C++, and how worried we are about the interactions with metaprogramming. We didn't reach a conclusion between (1) and (2) here, I just wanted to write up a description of the much more workable model for (2) so we were all comparing more realistic formulations of these directions.

[geoffromer]

The '{}'-ed body of MyMethod would be parsed exactly as if it were written after the closing } of C:

Phrasing this in terms of parsing surprises me. Do you anticipate any situations where performing this transformation after parsing but before name resolution would produce a different result?

[KateGregory]

The leads met today and decided to choose the "top down" approach over the "global within file" approach.

[fowles]

@KateGregory would it be possible to say a few words about what part of the trade offs weighed most heavily in their decision?

[chandlerc]

I think the more full details / rationale and such should be up-coming in #875 which aims to capture this decision in a principle.

That said, here is a summary from my memory of the discussion that I ran past the other leads and so I think it is roughly accurate if somewhat brief:

The leads felt like the tradeoffs ended up borderline. We specifically walked through the Carbon priorities to look for tradeoffs on each one.

Many cases would have a different thing be made easier, but without any clear indication that one was more important than another. For example readability is a priority for Carbon. We know that some readers will prefer a "top-down" structure, but others will prefer to not have to scroll past helper code to find interesting code. It isn't clear that one or the other is significantly more important to optimize for, and neither seemed to be severe problems.

Two somewhat minor points were language evolution and migration from C++. The top-down model is expected to be easier to relax into the other if desired compared to the other direction. And the top-down model may minorly reduce the initial surprise of C++ programmers encountering Carbon code as it will follow a fairly similar structure.

Or the leads could decide these minor differences aren't big enough to really make a decision, and just let the painter pick a bikeshed color. The painter confirmed the color would be "top down" because it would match the paint of C++.

Either way, we end up in the same place.

[chandlerc]

(To be clear, I'm posting mostly because I think Kate went offline after we discussed this.)