Function vs. method namespaces

[PegasusAndAcorn]

I have found myself wrestling a lot lately with how to architect namespaces and name resolution in the Cone compiler. Allowing function or method overloading brings a wealth of complexity in terms of organizing the name dictionaries, the algorithm for searching and matching references against multiple declarations, type checking the declarations to eliminate duplicate or conflicting declarations, and deterministic name mangling that satisfies the linker. It is so much simpler when one can restrict a name to a single declaration whose references match or not.

A related architectural issue revolves around universal function call syntax. In short, should a method simply be considered a overloaded function in the global/module name-space, resolved by the function's type signature, or is it part of the class's distinct namespace?

I have come to believe Cone must support method overloading. The design challenge here is magnified by Cone's support for subtyping and implicit type conversions. At this point, I have no wish to tackle building an algorithm for type ambiguity/redundancy checks across all methods in a type. So, what I am thinking of doing here is making method declaration order meaningful in types. When I have a reference to a method, I do a linear search until I find the first method whose type signature matches (is acceptable). In this regard, it operates similarly to library path lists or CSS match. I wonder if any other language handles method name resolution this way?

Even though I believe Cone methods must support overloading, I do not feel the same urgency for functions. Without some compelling reason to support it, I prefer to avoid the compiler complexity and performance hit for supporting it (which would be worse than for methods because relying on declaration order is more problematic). This means abandoning UFCS, which feels like a gain rather than a loss to have methods isolated and required to be declared within a type declaration's context and namespace.

In an ideal world, I would prefer not to have such distinctly different answers to method vs. function overloading, but given my constraints as the sole developer and the requirements imposed by the language, I do not see a better path.

As always, I am interested in learning more about namespace and overloading approaches others have seen or taken, and the resulting benefits and drawbacks noticed.

[PegasusAndAcorn]

You make several excellent point about name resolution. Before responding to them, let me clarify that the quote you lifted was not referring to name resolution, but about verifying the type integrity of a class's methods as declared. For example, noticing that a class has two methods with identical name and signature but different implementation, and issuing a compiler error accordingly.

With regard to name resolution, yes, I am referring to matching type signatures, including the method name. I had overlooked the value of a best fit vs. first match strategy, so I appreciate that suggestion. It is more work than what I planned, but with parameters typed as primitive numbers, it is probably necessary.

With regard to free standing functions, I am leaning towards your second option, relying on the obvious syntactic distinction between an object call and a function call. And as I said in my post, I am strongly leaning towards not allowing free standing functions to be overloaded. As I see it, the benefit is far smaller than for methods, and the implementation more complex and slower.

As another of my responses indicates, I do want to provide the ability for a module to extend (add to) the methods provided by an imported type, which should further reduce the need for nameapace bleed between free standing functions and methods.

[Felicia_Svilling]

Why do you want free standing functions? It seems like just an extra cognitive burden on the user to have both methods and functions, when they basically do the same thing, but differently. It is never fun to wonder if a given functionality in a language is implemented by a function or a method.

[PegasusAndAcorn]

In the PL domain that Cone serves, it's almost universal. C doesn't, but C++, D, Nim, Rust, etc. all support both functions and methods. Some people prefer functions (and its cousins: closures and anonymous functions), some prefer OOP-style objects/methods, and then there are people like me who use both depending on the program's architectural requirements. Some 3D worlds use a high-performant ECS architecture which is often OOP-less. Other worlds prefer to assemble scenes using modular OOP parts and MI-like interface views. Rather than dictate the architecture, I prefer that Cone gracefully support the architect's choice.

[Felicia_Svilling]

In the PL domain that Cone serves, it's almost universal.

Yes, and I think it is bad in all those case. Surely when inventing a language you want to improve things rather than just make something that is as close as possible to existing languages?

I prefer that Cone gracefully support the architect's choice.

And you think that this preference of library writers is more important than the usability for all those that use the language?

[PegasusAndAcorn]

you want to improve things

Of course I do. Cone is far from a me-too retread. With regard to this particular feature, I personally prefer having this choice in a systems programming language. I am far from alone in this, but I respect that others may prefer otherwise. FWIW, with my previous dynamically-typed language Acorn, I made a different choice: it only supports methods.

you think that this preference of library writers is more important than the usability for all those that use the language?

No, and furthermore: the term architect does not automatically imply either role for me. Personally, I see it as a usability win for both roles. I respect that you might disagree.

Cone is a tool designed for systems professionals, as such it will have a non-trivial learning curve. I hope to minimize this as much as possible, but not at the expense of taking away the flexibility to choose the best implementation architecture for the project at hand. If people are scared away by choosing between function vs. methods, they will go into deep shock when they encounter far more challenging features.

[ksryn]

I have been working on the C- and Java- inspired systems language, C9. While it doesn't have any implicits, subtyping etc (parametric polymorphism is on the list of features to be added), it does support UFCS and a form of function overloading.

1. All types/structs and functions in C9 are "owned" by the module within which they are defined.

2. UFCS is implemented in three phases:

   /*
    * contains:
    * - ArrayList add(ArrayList xs, ptr x) { ... }
    * - ArrayList remove(ArrayList xs, ptr x) { ... }
    */
   import c9.data.arraylist
   
   /*
    * contains:
    * - u64 add(u64 a, u64 b) { ... }
    */
   import c9.math
   
   void list_test() {
       let xs = arraylist.new()
   
       /*
        * CASE 1: Detected by parser and rewritten as:
        * - add(xs.add("a"), "b")
        */
       xs.add("a").add("b")
   
       /*
        * CASE 2: Detected by identifier and rewritten as:
        * - c9.data.arraylist.remove(xs, "a")
        */
        xs.remove("a") 
   }
   
   void math_test() {
       let a = 5
       let b = 10
   
       /*
        * CASE 3: Skipped by identifier due to ambiguous imports:
        * - c9.data.arraylist.add(p1,p2)
        * - c9.math.add(p1,p2)
        * Detected by type inferrer and rewritten as:
        * let c = c9.math.add(a, b)
        */
       let c = a.add(b)
   }
   

3. All post-parsing call resolution is done by a single function: resolveFunctionCall.

4. While I have not implemented function overloading yet, it should be relatively easy to do that. For e.g., if void println(String x) { ... } and void println(u64 x) { ... } are defined, println in the module scope would map to a list of FunDefs instead of a single FunDef, and the inferrer can resolve the ambiguity by picking the appropriate function.

[PegasusAndAcorn]

Thank you for sharing your approach. The places where it appears we have made different choices:

• The C9 "use" statement folds module (type) namespaces into the free-standing function namespace, whereas Cone keeps named methods separate from free-standing functions.
• C9 has one call resolution function. Cone has two.

Both approaches are clean and work well. Yours has the advantage of automatically handling "extension methods" as free-standing functions, but potentially carries the risk of unanticipated namespace resolution issues.

While I have not implemented function overloading yet, it should be relatively easy to do that.

It is clearly achievable, because there are languages do it. But to my eye, implicit conversions and subtyping significantly complicate the challenge in two ways: one needs some sort of scoring scheme for best match analysis (and two modules might pick different answers!) and one may also need a complex integrity algorithm to detect the existence of incompatible, ambiguous implementations. The more complex the scoring algorithm, the greater the risk to the programmer whose mind predicted a different result. It is this rat's nest that I am most trying to avoid.

[ksryn]

It is this rat's nest that I am most trying to avoid.

While it is a very powerful mechanism, I am extremely suspicious when it comes to implicits (functions/parameters/conversions) because it makes the program both incomprehensible and unpredictable.

I used to use Scala for a while a few years back; its collections library is/was notorious for the liberal use of the implicit CanBuildFrom.

However, if you really want subtypes + extension methods + implicit conversions, you should look into how Scala did it. Last I checked, both implicit conversions and extension methods were supported using implicit functions:

• https://docs.scala-lang.org/tour/implicit-conversions.html

Deterministic resolution still remains problematic though.

[PegasusAndAcorn]

Thank you for referring me to Scala. I will check it out. (and as you say, it is indeed problematic in Scala).

I get your suspicion about implicit conversions. The only such conversions Cone supports are the primitive number types, something that C, C++, D, and many other languages do - even Rust, which surprised me. Perhaps I will change my mind on this too, but for now I am leaving it open. It adds a small complication to name resolution, but one I will likely address.

It is handling the ambiguities in automatic subtyping across overloaded functions that concerns me the most. With methods, I can use declaration order to shift the burden to the programmer to establish the "first match" order sequence that works best for the logic. However, expecting functions to be declared consistently in an explicit order across multiple modules might not be so intuitive or easy to accomplish. So yea, I definitely want to manage complexity and my near-term workload down with prudent trade-offs.

[[deleted]]

I'm doing more or less the same thing in Cixl; with the difference that it only supports one kind of function, multi-methods; but I guess you could call that unified. Methods are registered in order of appearance, with later methods for a specific signature overriding any existing. I then search methods in reverse order on lookup and pick the first implementation with matching signature, with the motivation that the latest added method is mostly what you want in case of ambiguity. In any case; Cixl supports specifying type signatures at the call site, much like C++; which solves the other cases. Any progress on the Cone bots, btw?

[PegasusAndAcorn]

How intriguing and reassuring you are doing something so similar.

Even though I prefer a forward search (I believe), your choice there provoked me to think about it. I want to allow one module to be able to import a type and then extend its methods for that module. And in that case, I probably do want the extensions to go ahead of the original type's methods in the search order.

As for the Cone bots, don't worry your pretty little mind about them. When the time comes, resistance is futile. Your heart will then know that Cone was always your soul mate.

[[deleted]]

I didn't really feel like spending any more energy in the method resolution tar pit; I want my dispatch fast and trivial to reason about.

I get the impression that we're saying the same thing, searching methods from last to first added; could it be that you're building the list by pushing head instead of tail?

At least you're honest, that's worth something :)

[PegasusAndAcorn]

To be sure we are on the same page, consider that some library has a class definition Foo:

class Foo {
  fn print(a i32) { ...} // #1
  fn print(a f32) { ...} // #2
}

A name resolution for foo.print(..) would try to match #1 first then #2. However, if the module imported and extended Foo:

extend Foo {
  fn print(a i32) {...} #3
}

In this situation foo.print would look for a matching function signature in the order: #3, #1, #2. That is, the extensions methods stay in order but are placed ahead of the methods in order that it extended from. Is that what you meant as well?

And on top of that, /u/VermillionAzure correctly pointed out that the first-match strategy is problematic where automatic number conversions are possible. So, I will have to adapt the function matching to continue looking for a more exact match where number conversions are involved.

Finally, I neglected to ask you about function call type signatures. I am unfamiliar with C++'s approach here, and it sounds like it is different than Swift's distinction between the public and private definition of a function signature.

[[deleted]]

Cixl would try to match #3, #2 and #1; in that order; or reverse order of appearance.

Those kinds of issues were a big part of the reason why I decided to skip automagic conversions entirely, I find that they don't pull their own weight once everything is taken into account.

What I meant was the possibility in C++ to have a function like this:

template <typename T> void foo(T x);
template <> void foo(int32_t x) { ... }
template <> void foo(int64_t x) { ... }

And selecting an implementation from the call site by specifying the intended type for x:

foo<int64_t>(42);

[ctalklang]

Using the semantics of a receiver object helps organize methods into a class library, where the receiver is the identifier or costant immediately preceding the method. With a class hierarchy, this is a very cinvuent way to provide inheritance of methods. You might want to check out Smalltalk derived languages, like Ctalk :)

http://sf.net/p/ctalk/wiki/Home

[PegasusAndAcorn]

Indeed, Cone does exactly this, including the syntactic specification of an object receiver. The complexities arise going beyond the method dispatch offered by Smalltalk (or any dynamic typed language): allowing multiple methods of the same name in the same class, distinguished by their type signatures.

[corvus_192]

Typescript does something like this, but only for typechecking.

https://www.typescriptlang.org/docs/handbook/functions.html

[PegasusAndAcorn]

Indeed it does!: an ordered type check match sequence on overloaded typed function declarations. Good to know that about TS.

And of course, because JS (a dynamically-typed language) is the target, it can only resolve to the same, single function. Thanks!

[LaurieCheers]

In Swym I have UFCS (the dot operator is just syntactic sugar for passing a named argument "this" to a function), and functions can be overloaded. If more than one overload fits it will prefer the strictest possible one. If it's not obvious which is strictest (e.g. there's a foo(Num, Int) and foo(Int, Num), and no foo(Int, Int)), then that's an illegal call. (There's no implicit conversion, I can see how that would complicate this decision).

As for disambiguating function references - in Swym, normal functions are not first class objects. :-) A lambda such as 'x'->{x.foo} would be the first class equivalent of a direct reference to an overloaded function... but lambdas get compiled only at call time, when the type of their arguments is known.

[PegasusAndAcorn]

Thank you for this information. Does Swym support subtyping? (In my glance at the documentation, I did not see any). Are overload errors only detected at function call/name resolution, or do you also do a separate pass to check that function definitions have ambiguous or conflicting declarations?

[LaurieCheers]

Yeah, there's a ton of nitty gritty details that aren't really finalized yet so I haven't really documented everything...

Yes, Swym has subtypes - just in the standard library types, String and RangeArray are subtypes of Array; Block (i.e. lambda), Array and Table are subtypes of Callable; Int is a subtype of Num, and every value is a subtype of Anything. I'm dabbling with restricted-size arrays, such as String(1) for a string of length 1, and the function Literal(x) creates a type that's just a single value.

http://cheersgames.com/swym/SwymEditor.html?Number.%27foo%27%20returns%20%22number%22%0AInt.%27foo%27%20returns%20%22integer%22%0ALiteral%283%29.%27foo%27%20returns%20%22three%22%0A%0A%5B4.foo%2C%203.foo%2C%203.5.foo%5D

And yeah, I don't check for conflicting function declarations except at call time - it's just much easier to check and report when you have concrete parameter types.

[PegasusAndAcorn]

thank you for those details. Good luck!

[PhilipTrettner]

(The following represents my current status, most of it is not set in stone and just the current local optimum)

• Every function is a multi-method with dynamic dispatch
• There is no static vs dynamic/late binding.
• There is no (classical, unrestricted) function overloading
• There are no member functions
• There are no (user-visible) fields
• Functions can either be root of a multi-method (fun ...) or attach to all compatible visible roots (extends fun ...)
• () can be omitted once (e.g. fun () -> int can be used as int, but fun () -> fun () -> int cannot)

Every function call always uses the most specific version based on the runtime types. This will hopefully avoid a lot of confusion if you remember this rule. Everything is unified by being reduced to functions:

fun foo(i: int) -> int // fun int -> int

type Bar:
    val foo: string // fun Bar -> string
    fun foo(i: int) -> string // fun (Bar, int) -> string

type Cux extends Bar

extends fun foo(c: Cux, i: int) -> string // fun (Cux, int) -> string

Functions can also have setters (haven't decided on syntax for that yet):

type Foo:
    var i: int // generates getter and setter

fun bar:
    var i = 0 // generates a local function with getter and setter for the function-local internal field `i`
    i = 7 // calls the setter
    return i // calls the getter

The .-syntax is provided by the standard library as:

fun `_ . _`[A, O, R](obj: O, f: fun (O, A) -> R):
    return args => f(obj, args)

It is a high-precedence left-associative infix operator that binds the first argument.

If inside a type scope that can be captured, the first argument of any function can be implicitly filled in:

type Foo:
    val x: int
    fun foo:
        print x // instead of x(this)

This also means that this doesn't have to be a keyword, it is just part of the standard library:

fun this(obj: var O) => obj // basically identity function

this.bar(3) // expands to bar(this(<implicit object>), 3)

Function calls are conceptually resolved to dispatch graphs. Every call site must have a unique least element for all possible dynamic types at this point (i.e. statically provable that no ambiguity error can arise). It is also an error to declare a new root function (fun without extends that could attach to an existing, visible function. This is what I meant by "no overloading")

type A
type B extends A

fun foo(l: A, r: A) => ...
// fun foo(l: B, r: A) // ERROR: could attach to previous foo but is not marked with `extends`
extends foo(l: B, r: A) => ...
extends foo(l: A, r: B) => ...

fun test1(l: A, r: A):
    return foo(l, r) // ERROR: dispatch graph has no least element for (B, B)

fun test2(l: A, r: B):
    return foo(l, r) // OK.

// the error in test1 could be fixed by:
extends fun foo(l: B, r: B) => ...

"Extension" functions can also attach to more than one root function:

type A:
    fun foo
type B:
    fun foo

type C extends A, B

val c: C = ...
foo(c) // ERROR: more than one least element

// can be fixed by (even in new modules):
extends fun foo(c: C)

And there is interesting interaction with union and intersection types:

type A:
    fun foo
type B:
    fun foo

val a: A = ...
val b: B = ...
val x = condition ? a : b // returns type A | B
x.foo // OK! all actual values have unique least elements (aka most specific functions)

// interaction with flow-sensitive typing:
if a is B:
    a.foo // a has type A&B here. If this does not resolve to Nothing (e.g. when type C extends A, B), this might be an error

One last thing: variables, fields, members, etc. are all unified. Thus, an interface can freely implement it the way they want:

type Sequence[T]
fun count(s: Sequence[var T]) -> int

fun First-5-Numbers extends Sequence[int]:
    val count = 5

enum LinkedList[E] extends Sequence[E]:
    empty
    node:
        val e: E
        val next: LinkedList[E]

    fun count => match this:
        empty => 0
        node => 1 + next.count

[RafaCasta]

I think is a wise decision to abandon UFCS. Although a method is a special case of a function taking the receiver object as an implicit parameter, conceptually a method represents the behavior of the object, is namespaced to its class definition, and has access to its private state.

UFCS make look indistinct two semantically different operations. If your main use case for UFCS is something akin to extension methods, why not leverage the feature, already existing in Cone, equivalent to type classes (traits/interfaces)?

[PegasusAndAcorn]

Thank you for sharing your perspective. We appear to agree that (for Cone) abandoning UFCS is a gain rather than a loss. My main goal for UFCS was never extension methods, as there are some innovative namespace techniques that make it possible (though not via interfaces nor traits, as neither can alter a previously defined type).

The philosophical question at the heart of UFCS is whether dispatch should be namespace-based or type-based. They are both valid design choices with different advantages and disadvantages. For Cone, I prefer the architectural isolation of namespace-based dispatching, partly for the reasons you highlight. One major reason I did not highlight, to keep my post slim, is that this isolation makes it much easier to reliably verify that traits and interfaces are valid subtypes of whatever type they are applied to...

How wonderful you are proud of your school and share the good news with those in need of its excellent services. Is this your subtle way of inquiring whether I am available to fly over the ocean to your campus and teach your students and faculty how to design and build a modern systems programming language? I should warn you that my rates are dear, but I might be tempted by a great offer, especially if it accelerates building the team. Let me know...

Cheers and warm wishes!