DIP1041.md

Attributes for Higher-Order Functions

Field	Value
DIP:	1041
Review Count:	1
Author:	Quirin F. Schroll (@Bolpat)
Implementation:	none
Status:	Postponed

Abstract

Functions that have function pointers or delegates as parameters cannot be integrated well in pure, nothrow, @safe, and @nogc code. This DIP proposes to adjust the constraints that the mentioned attributes impose. It will only affect functions which accept function pointers or delegates as const, inout, or immutable parameters. The goal is to recognize more code as valid that factually behaves in accordance with the attributes.

Contents

1. Terms and Definitions
2. Rationale
3. Prior Work
4. Description
   • Attribute Checking inside Higher-Order Functions
   • Attribute Inference for Functional Templates
   • Attribute Checking inside Contexts
   • Overloading, Mangling and Overriding
5. Examples
   • Lockstep Iteration
   • String Representations
   • Functions with Typesafe Variadic Lazy Parameters
   • Mutable Parameters
   • Const and Aliasing
   • Overriding Methods
6. Alternatives
   • The Current State
   • New Attributes
   • Contravariant Overriding
7. Outlook
   • Lazy as a Lowering
   • Default Attributes
8. Breaking Changes and Deprecations
9. References
10. Copyright & License
11. Reviews

Terms and Definitions

The attributes pure, nothrow, @safe, and @nogc will be called warrant attributes in this DIP. Notably absent are throw (cf. DIP 1029), @system, and @trusted as they do not warrant any compiler-side checks. Also absent is @live, because @live functions may call non-@live functions.

In this document, FP/D (type) will be an abbreviation for function pointer (type) or delegate (type). A type is essentially an FP/D type (called eFP/D for short) if it is

• a possibly qualified version of an FP/D type; or
• a possibly qualified pointer to essentially FP/D type; or
• a possibly qualified slice of essentially FP/D type; or
• a possibly qualified static array of essentially FP/D type; or
• a possibly qualified associative array with value type an essentially FP/D type.

Example
The type void function(int) pure is an FP/D type, and
thus, const(immutable(void function(int) pure)*)[] is essentially an FP/D type.

An essential call of an eFP/D (object) is an expression that, depending on the eFP/D type, calls an object of the underlying FP/D type. In case of:

• a possibly qualified FP/D: A call (in the regular sense) to that object.
• a pointer p to an eFP/D: An essential call to *p.
• a slice or a static or associative array arr to an eFP/D: An essential call to arr[i] for a suitable index i.

Example
Let fpps be of the essential FP/D type in the previous example. For i a size_t and arg an int, (*(fpps[i]))(arg) is an essential call to fpps.

Basically, an essential call consists of minimal efforts to obtain and call an underlying FP/D object.

This document makes use of the terms parameter and argument in a very precise manner as the D Language Specification points out:

When talking about function parameters, the parameter is what the function prototype defines, and the argument is the value that will bind to it.

A higher-order function, or functional for short, is anything that can be called with one or more eFP/D objects as arguments.

When a higher-order function is called, there are four notable entities commonly referred to:

• The context function, or context for short, is the function that contains the call expresion. When the document refers to e.g., a @safe context, it is meant that the context function is annotated or could be annotated @safe.
• The functional is the higher-order function that is called.
• The parameter functions are the variables declared by the functional's parameter list.
• The argument functions or callbacks are the values plugged-in in the call expression.

Although not an entity in the above sense, the functional's parameter types will be commonly referred to as such.

Example
An illustration of the last terms is given in this code snippet using telling identifiers.

alias ParameterType = void function();
void functional(ParameterType parameterFunction)
{
    parameterFunction();
}

void context()
{
    alias callback = { };
    functional(callback);
}

A warrant attribute context is a context function that is annotated with or could be annotated with one or more of the warrant attributes.

Rationale

Higher-order functions are cumbersome to use in a warrant attribute context. The execution of a context function may provably satisfy the conditions of a warrant attribute, but is considered invalid because the formal conditions of the warrant attribute are not met.

First note that warrant attributes on a functional (or, in fact, on any function) and on a functional's parameter mean very different things:

• On a functional, they give rise to a guarantee that contexts may rely upon.
• Only on a functional's parameter type, warrant attributes give rise to a requirement that the functional potentially needs to work properly.

As an example, consider a functional taking a pure function pointer parameter. In its internal logic, the functional might make use of memoization, or the fact that the parameter's return values are unique. In the case of uniqueness, omitting the requirement will result in invalid code, since return values of impure functions generally cannot be assumed unique. In the case of memoization, omitting the requirement will result not in a compile error but in unexpected behavior when used improperly. In most cases, however, the requirement is merely there to match the functional's own guarantees.

In the current state of the language, a functional cannot have strong guarantees and weak requirements at the same time. Having strong guarantees means that the functional provably behaves in accordance with warrant attributes so that it can be annotated with them. Having weak requirements means that the functional does not need the guarantees of a warrant attribute on a parameter function for its internal logic to be sound. When pressed, most library authors opt against warrant attributes, i.e., for weak requirements, and therefore needlessly weaken the guarantees. For example, Phobos's lockstep does that.

The DIP solves this problem by always allowing calls to const (or inout or immutable) parameter functions when checking a functional for satisfying the conditions of a warrant attribute, irrespective of those parameter functions' types lacking the warrant attribute. In a context where a functional is called, the type system has all the necessary information available to determine if the execution of it will comply with the warrant attributes of the context. For that it must take the warrant attributes of the arguments' types into account.

Loosening warrant attributes' restrictions in that way allows the annotation of more first-order functions. An illustration of what this DIP enables is this:

interface NogcToString
{
    /// Executes `sink(str)` for every part `str` of the string representation.
    void toString(void delegate(const scope char[]) @nogc sink) @nogc;
}

class Aggregate
    : Object       // provides string toString()
    , NogcToString // provides void toString(sink)
{
    override void toString(const scope void delegate(const scope char[]) sink) const @safe @nogc
    { ... }

    /// Returns the string representation in a GC allocated string.
    final override string toString() const @safe
    {
        string result;
        void append(scope const(char)[] s) { result ~= s; }
        toString(&append); // append is (inferred) @safe, but not @nogc
        return result;
    }
}

The signature of the interface's toString indicates that the class override may require the sink to be @nogc in order to fulfill its guarantee not to allocate.

Notice how, in the override, sink is not annotated @safe or @nogc but is declared const. The key observation of this DIP is that because it is const, any call like sink("bla") is restricted to only executing the delegate passed to it (sink cannot e.g., be reassigned), and thus the parameterless toString function has full control over whether the argument &append binding to sink is @safe and/or @nogc.

Apart from the statement toString(&append), the parameterless toString is @safe. With the proposed changes, the statement will be recognized @safe on the grounds that

• the called toString function is annotated (or inferred) @safe; and
• the type of the argument &append binding to a const parameter is also (annotated or) inferred @safe. (Note that the actual argument is checked, not the type of the parameter to which it binds. That argument must satisfy the conditions posed by the parameter type, but it can have stronger guarantees. In the sense of the proposal, it is these additional guarantees that matter.)

On the other hand, that statement is (still) not recognized @nogc on the grounds that, though the called toString function is annotated (or inferred) @nogc, the type of the argument &append binding to a const parameter is not annotated or inferred @nogc.

Similarly, the statement is not recognized pure because the called toString functional is not annotated or inferred pure, even though the argument &append is inferred pure.

The changes entail that not all calls to a functional annotated with a warrant attribute will result in call expressions that are considered in compliance with that warrant attribute. This is, however, less of a problem than it seems at first glance:

• Consider a @system or @trusted context calling a @safe functional with a @system argument. The context does not expect an execution satisfying the formal @safe constraints, therefore the fact that the call to the @safe annotated function is not @safe can be mostly ignored. The memory safety audit for the context must include the callback anyway.
• Consider a @safe context calling a @safe functional with a @system argument. This becomes invalid, since a @safe functional makes guarantees for its internal logic. What the @system callback does is among the responsibility of the context, and in a @safe context, calling a @system function is invalid. Note that this is only true if the callback binds to a const parameter; if the parameter is mutable, there is no difference with the current state of the language.

Especially in meta-programming, it might not be clear at all whether a callback's type has a warrant attribute or not. For @safe and @nogc, this is mostly unproblematic, since these are only interesting from a safety or resource perspective, but no program's logic depends on the guarantees these attributes make: A memory-unsafe program is broken in itself, and GC allocations may at worst slow down a program unexpectedly due to the GC issuing a collection cycle. When GC allocations are an issue, profiling will be necessary anyway. [Author's note: I'm not completely sure. Please have a think whether these claims are really true.]

However, the attributes pure and nothrow are of interest, even in an impure context, or a context where throwing exceptions is allowed.

• The return value of a pure operation can be unique, allowing for implicit casts that are not possible otherwise. In this case, if the call to the functional is impure due to calling it with an impure callback, the code is invalid. An impure context may expect a pure execution for memoization or thread-safety, too.
• A nothrow operation cannot fail recoverably. It fails irrecoverably or succeeds (or gets stuck); in either case, no rollback operation is necessary. This fact may be used by the context even if it may throw itself.

With the changes proposed by this DIP, except for uniqueness, it is necessary to manually ensure the execution is pure or nothrow if that is expected or required for a sound execution. This is especially true for meta-programming (function templates etc.), but not limited to it. Usually, this can be achieved by properly annotating the callback where it is defined: Instead of x => x + 1 one has to write (x) pure nothrow => x + 1. When the type of the argument bound to x depends on factors outside the control of the context, e.g., if typeof(x) happens to have an impure or possibly throwing opBinary!"+"(int), that will lead to a compilation error where the lambda is formulated.

Even in the current state of the language, a context should not rely on the annotations of the functional to check its requirements implicitly, but instead must make those requirements explicit in its statements: Because functionals can be overloaded on the parameter types' warrant attributes, that implicit check cannot be relied upon in general.

The benefits and drawbacks of making this or another warrant attribute the default are discussed regularly on the forums. Changes akin to the ones proposed by this DIP are in fact necessary to alleviate breakage by any sane way that such a default would be implemented.

For example, consider making @safe the default. Without this change, a suitable unannotated void functional(void function() f) would either become

• void functional(void function() f) @safe; or
• void functional(void function() @safe f) @safe.

(Here, suitable means that functional contains @safe operations only, apart from calls to f. One way to test that is annotating the parameter and the functional.)

In the current state of the language, the first option can be excluded immediately: When functional calls its parameter f, it will no longer compile. This breaking change is obvious and would affect almost all unannotated functionals.

So it would have to be the second option, which entails that most @system annotated contexts can no longer make use of functional because its signature now requires any argument be @safe. That is overly restrictive from the viewpoint of a @system context: There is probably no reason why functional should not be used by a @system context.

With this change, however, the first option is viable: A @safe context must supply a @safe argument for the call to functional to be considered @safe. A @system context may supply a @system argument, rendering the call to functional a @system operation which is not a problem, since this is exactly what was happening before making @safe the default.

One could argue that changing defaults is inherently a breaking change. Still, breakage should be minimized and have a transition path. Higher-order functions are not an obscure fringe case that can be ignored.

With this DIP, the first option together with qualifying the parameter const is a transition path for most functionals. If the functional assigns the parameter, a local variable must be introduced instead. If the parameter is not taken directly, but e.g., in a slice (see Description), assignment cannot be replaced by a local variable. This, however, can be dismissed as being an obscure fringe case that can be ignored.

Prior Work

Regarding Attributes

There is no prior work in other languages known to the author in the sense that a similar solution is implemented or has been proposed, discussed and/or dismissed. However, the problems this DIP proposes a solution for, are not specific to the D Programming Language.

In C++, since C++11, there is a close equivalent to D's nothrow called noexcept that is (often) used very similar to how function attributes are used in D. Since C++17, noexcept is part of the function's type as nothrow is in D. For that reason, functionals written in C++ in principle have the same problem.

However, C++ does not require that noexcept functions only call noexcept functions. It is up to the programmer to ensure that no called function, including function pointer parameters, factually will not throw at runtime. (If they do, std::unexpected is called which usually aborts the program.) In plain terms, C++ follows the route that it is the programmer's responsibility nothing bad happens.

Such a solution is undesirable. It merely documents intent; a C++ compiler might perform some checks to emit a warning. In D, if a programmer wants to document intent, the library function assumeWontThrow would be the preferred choice.

An example where conformity with warrant attributes is checked already in the context and not the functional is the case of the delegate parameter implicitly defined in lazy parameters and delegates created when binding to them.

Among the rationale of DIP 1032 was to make lazy less of a special case in the language.

Excerpt of the rationale of DIP 1032
A further reason is that the lazy function parameter attribute is underspecified and is a constant complication in the language specification. With this DIP, lazy can move towards being defined in terms of an equivalent delegate parameter, thereby simplifying the language by improving consistency.

With this proposal, lazy can easily become a lowering to a delegate as outlined in Lazy as a Lowering.

The proposed changes bear some similarity to the relaxation of pure, allowing pure functions to modify any mutable value reachable through their parameters. Those pure functions are called weakly pure in contrast to strongly pure ones that cannot possibly modify values except their local variables. The same way, letting weakly pure functions be annotated pure allowed more strongly pure functions be annotated, the changes proposed by this DIP allow more functions carrying a warrant attribute: The example in the Rationale shows how the second toString overload can be recognized as @safe when the first overload is @safe depending on its argument.

This proposal is based on an idea explained by H. S. Teoh in great detail. In the discussion, Walter Bright, one of the Language Maintainers, raised strong opposition to this approach:

Walter Bright's answer in the Discussion Thread of DIP 1032
But it still tricks the user into thinking the function is pure, since it says right there it is pure. Pure isn't just an attribute for the compiler, it's for the user as it offers a guarantee about what the interface to a function is.

Silently removing pure can also make the user think that a function is thread-safe when it is not. Adding a feature that silently disables an explicitly placed "pure" attribute is going to become a hated misfeature.

I strongly oppose it.

Note that a pure call can be memoized / is thread-safe / has unique return values only if it is to a non-static member function, or as an object, is a function pointer and not a delegate. A pure delegate or member function may access and mutate its context. Even in the current state of the language, more care must be taken than merely looking at attributes especially in the case for pure.

The author agrees that there is a didactic challenge to this, since attributes are currently absolutes. There is no solution that leaves them that way because the absoluteness is precisely the problem. However, from a didactic standpoint, attributes could be explained as describing the allowed and disallowed operations of a function. A function call in and of itself is in accordance with any attribute. Normally, the called function's operations become the responsibility of the caller. In the case of const eFP/D parameters, it intuitively makes sense that the parameters' operations do not have to be the responsibility of the functional, but can be the responsibility of the context binding the arguments to the parameters. In a way, making the functional responsible for const eFP/D parameters' operations is unfair because the functional has no control whatsoever over the called parameters' actions.

The example of a pure and therefore thread-safe functional called from an impure context is being addressed in the Rationale section. It is true that when an impure callback binds to a parameter of a pure functional, the call will silently be considered impure, and because an impure operation is valid, no error is raised. Relying on locally pure operations in a globally impure context implicitly, asks for trouble. When specific properties of a callback are expected, the programmer should state those expectations:

• If the callback is a lambda or a local function, one way is putting the required attributes behind the parameter list. (An example for a lambda is in the Rationale section.)
• Another is assigning the callback to a const variable typed explicitly that will be optimized away certainly.
• A third is to static assert the required attributes using Phobos' std.traits.isSafe and analogous templates.
• A fourth option is using a function template ensurePureCall!pureFunctional that forwards the call and also supplies the pure context to raise an error if the arguments make the call impure.
• A fifth option is wrapping the part in a pure pseudo-block (i.e., a lambda that is immediately called) the same way @trusted pseudo-blocks are used (however, with the reversed intention to restrict and not to allow operations).

Since in all cases where a general context needs the guarantees provided by a warrant attribute locally, the programmers already have attributes in their mind and need a good understanding on what they mean exactly, the author deems it not far-fetched to know it is a good idea to state their requirements explicitly.

If considered necessary, appropriate additions to the standard library Phobos could be made, that unambiguously state and enforce a warrant attribute with little writing and reading.

Bright's criticism would have more weight if the situation were not present in the current state of the language: When a functional is overloaded on the basis of the parameters' attributes (see the current state alternative for an example), inadvertently using an impure callback as an argument to a functional will silently result in an unexpected overload resolution, but no compile error. Stating one's expectations about the callback, is the only way to solve the problem, no matter whether the proposed changes are implemented.

Description

The changes proposed by this DIP affect

• when warrant attributes are satisfied by functions annotated with them; and
• how warrant attributes are inferred for function templates.

The first bullet point can be split into:

• when warrant attributes are satisfied by functionals themselves; and
• when warrant attributes are satisfied when calling a functional.

These changes require unexpected secondary changes to method overriding consistent with expectations.

These secondary changes are part of the DIP. However, the Language Maintainers may opt to accept the main part of the DIP, but not the proposed secondary changes, in favor of other solutions.

Attribute Checking inside Higher-Order Functions

When a function is annotated with a warrant attribute, each expression must satisfy certain conditions. Among those conditions is, for any warrant attribute, that the function may only call functions (the term function referring to anything callable here) that are annotated with the same attribute or have it inferred. Exceptions to this are statements in debug blocks and that @safe functions may also call @trusted functions.

This DIP proposes that

1. essential calls of const, inout, or immutable eFP/D type parameters are not to be subjected to this condition; as well as
2. essential calls of local const, inout, or immutable eFP/D type variables declared in a functional, that are initialized by copying, dereferencing and/or indexing a const, inout, or immutable eFP/D parameter or another such local variable, become valid, too.

For associative arrays, in expressions returning a pointer to a value count as indexing, as well as binding values in a foreach loop does. However, value access through its methods (e.g., byValue) are not proposed to be special cased.

This DIP author suggests that in the case of checking @safe and nothrow for a functional, if the parameter's underlying FP/D type is explicitly annotated @system and/or throw, an essential call to the eFP/D object is considered invalid. This is to avoid confusion. Removing the @system and/or throw annotation fixes this error. The same should be applied to any negation of a warrant attribute if one happens to be introduced to the language. (The Language Maintainers may opt against this on the basis of an easier compiler implementation.)

The second clause concerning local variables notably allows for iterating over eFP/D type parameters that are slices or static or associative arrays using a foreach loop.

Note that it is necessary that the parameter's or local variable's type is const, immutable, or inout on the uppermost level of indirection. If the uppermost level is mutable, the parameter or local can be reassigned in the functional's body before being called, invalidating the assumption that the context has full control over the eFP/D object and its type. You may want to take a look at the respective example.

Only requiring const as a qualifier in fact does suffice. One could conjecture that pointer aliasing could lead to problems, but it does not. You may want to take a look at the respective example.

However, this document does not contain a formal proof (or a proof sketch) that aliasing really is impossible. If the Language Maintainers find it too dangerous to risk, the author suggests going forth with immutable alone instead of const, inout, or immutable, even though pointer, slice, and array types with more than one level of indirection are hard to use with immutable and applicability of them is greatly reduced.

This change entails that a parameter's const, inout, and immutable on the first level of indirection must be distinguished from a qualifier on the second level of indirection.

Attribute Inference for Functional Templates

By the proposal of this DIP, when inferring attributes for function templates,

1. essential calls of runtime parameters of a const, inout, or immutable eFP/D type; as well as
2. essential calls of local const, inout, or immutable eFP/D type variables declared in the function template, that are initialized by copying, dereferencing and/or indexing a const, inout, or immutable eFP/D runtime parameter or another such local variable

are considered to not invalidate any warrant attribute.

That way, attribute inference follows the rules non-template functions are checked.

Attribute Checking inside Contexts

When calling a functional, the types of the eFP/D arguments are known.

By the proposal of this DIP, in a warrant attribute context, a call to a functional is valid with respect to the warrant attribute if, and only if,

1. the functional is annotated (possibly implicitly or inferred) with that warrant attribute (current state); and
2. the types of all arguments that bind to const, inout, or immutable eFP/D type parameters are annotated (possibly implicitly or inferred) with that warrant attribute.

Overloading, Mangling and Overriding

The difference of const, inout, and immutable on first and second layer of indirection that this DIP introduces if the parameter's type is an eFP/D type, seem to affect overloading (and overload resolution), mangling, and overriding.

Overloading is taken care of by proposing that no change is made. In the current state of the language, overload resolution considers the by-copy binding of a value a conversion if any indirection layer's qualifiers of the argument type and the parameter type disagree (match level 3).

Also, functions differing in parameters' qualifiers are considered different in type and mangling. Therefore, no change in mangling symbols is needed.

When a class overrides a method defined in a base class or an interface, by the current rules of the language, in some circumstances, qualifiers const, inout, and immutable can be moved between the first and the second layer of indirection of the parameter types, but the parameter types cannot be changed otherwise. To the author, it seems this is the case when the parameter type has indirections.

interface I
{
    void f(const(int)[]);
    void g(const(int[]));
}

class C : I
{
    override:
    void f(const(int[])) { } // overrides I.f
    void g(const(int)[]) { } // overrides I.g
}

C c;
static assert(!is(typeof(&c.I.f) == typeof(&c.f)));
static assert(!is(typeof(&c.I.g) == typeof(&c.g)));

To allow for dropping warrant attributes from eFP/D type parameters when overriding methods, contravariant parameter overriding is necessary in a minor form. That it is useful together with adding const, is demonstrated in the respective example.

The DIP proposes that conversions changing warrant attributes be considered qualifier conversions. This not only affects overriding, but also overloading; passing a pure delegate to a parameter of compatible impure delegate type will be considered match level 3 (match with qualifier conversion) instead of level 2 (match with implicit conversions).

The DIP also proposes that, for consistency, contravariant parameter overriding with qualifier conversions be explicitly allowed.

Error Messages

When a functional essentially calls a mutable parameter and that parameter's type lacks warrant attributes that the functional has, the compile error message should hint that qualifying the parameter const can solve this problem.

When a call to a functional in a warrant attribute context violates that attribute because an eFP/D argument without that attribute is passed to it, but the functional itself is annotated or inferred compliant to that attribute, a specific compile error message should be issued. The author suggests a message akin to:

@safe function context cannot call @safe function functional because the argument &callback is @system.

Only stating that the call is a violation of the attribute might confuse the programmer into thinking that the annotation of the functional is defective or attribute inference did not lead to the expected attributes.

Grammar Changes

No language grammar changes are necessary for implementing this proposal.

Examples

Lockstep Iteration

Iterating multiple ranges in lockstep with ref access cannot be achieved (not easily, at least) by the usual range interface (empty, front, popFront); it requires opApply. Here we will observe how the naïve approach fairs with respect to warrant attributes and how to make opApply admit warrant attributes properly.

The naïve approach (less interesting parts hidden):

struct SimpleLockstep(Ranges...)
{
    Ranges ranges;
    alias ElementTypes = ...;

    int opApply(const scope int delegate(ref ElementTypes) foreachBody)
    {
        import std.range.primitives : front; // needed for slices to work as ranges
        for (; !anyEmpty; popFronts)
        {
            if (auto result = mixin("foreachBody(", frontCalls, ")"))
                return result;
        }
        return 0;
    }

    bool anyEmpty() { ... }
    static string frontCalls() in (__ctfe) { ... }
    void popFronts() { ... }
}

In principle, being member of an aggregate template, opApply has its warrant attributes inferred. Using anyEmpty and popFronts is unproblematic as they have their warrant attributes inferred, too. When opApply calls its parameter foreachBody that has a delegate type that is not annotated with any warrant attribute, attribute inference will yield no warrant attribute for opApply, too.

This means that in a warrant attribute context, SimpleLockstep cannot be used. (A SimpleLockstep object can be constructed, but foreach through its lowering to opApply cannot be used.) For example, a @safe context plugging in ranges with @safe (or @trusted) interfaces cannot make use of SimpleLockstep because opApply is not annotated / inferred @safe, even though all operations being performed are @safe – not in some abstract sense, but immediate to the type system.

With this DIP, opApply has warrant attributes inferred based on what the range interfaces of the supplied ranges can guarantee. (This is the best it can theoretically do.) In the aforementioned case, opApply will be inferred @safe. Whether a call to opApply is valid in a @safe context is determined in the context, i.e., the code that contains the foreach loop, depending on whether the argument, the generated delegate, is @safe.

For how to implement SimpleLockstep in a way that properly takes attributes into account using the current state of the language, see the Alternatives section.

String Representations

Many objects have an at least somewhat human-readable string representation. In many standalone programs, a function returning GC-allocated string representations suffices. In libraries, however, one strives for more generality. The usual way to give the context first-class control over how the string representation is handled is replacing the return value by a sink. A sink is an output range that the sub-strings are put into. The context controls the sink.

A typical toString as part of an aggregate type uses a templated toString taking the sink type as a template type parameter akin to this:

void toString(Sink)(const scope Sink sink) const { ... }

This solves the attribute inference problem perfectly.

However, the author of a class or interface usually wants the toString member function to be virtual, but then, it cannot be a template anymore; the sink type usually becomes a delegate.

// For quick and easy usage:
string toString() const @safe pure /*maybe*/nothrow { ... }

// For elaborate uses:
private final void toStringImpl(Char)(const scope void delegate(const scope Char[]) sink) { ... }
static foreach (Char; aliasSeq!(char, wchar, dchar))
    void toString(const scope void delegate(Char) sink) const { toStringImpl!Char(sink); }

In the current state of the language, those toStrings cannot be used in warrant attribute contexts. Authors who want to support warrant attribute contexts have to implement up to 16 overloads like this:

private final void toStringImpl(DG)(const scope DG sink) { ... } // inferes attributes
static foreach (Char; aliasSeq!(char, wchar, dchar))
{
    void toString(const scope void delegate(const scope Char[])       sink) const       { toStringImpl(sink); }
    void toString(const scope void delegate(const scope Char[]) @safe sink) const @safe { toStringImpl(sink); }
    ... // 13 more
    void toString(const scope void delegate(const scope Char[]) pure nothrow @safe @nogc sink) const pure nothrow @safe @nogc
    { toStringImpl(sink); }
}

All instantiations of toStringImpl are different, so there are 3 × 16 = 48 template instances and virtual toString functions per class. If the class is templated, there are 48 per instantiation.

Worse than the template and virtual-table bloat is that users of the class who naïvely override the toString method in a derived class will only override the version without attributes.

override void toString(const scope void delegate(const scope char[]) sink) const { ... }

They get a hint that there were other overloads to override available: An error message pointing out that the derived class' toString hides base class toString functions. The suggestion by the compiler to “introduce base class overload set” is wrong. It makes the code compile, but for any sink that has any warrant attribute, it calls the base class toString.

Nonetheless, correctly overriding toString means implementing the 48 overloads again.

All in all, a library author who publishes a class that uses warrant attributes with maximized flexibility makes it unnecessarily hard and tedious to override functional methods correctly.

With the changes proposed by this DIP, only one toString method is needed per character type. (This is the best one can theoretically do.) Which attributes the toString can be given has to evaluated once by the class author. Class authors may intentionally not annotate a method with a warrant attribute, even if their implementation would satisfy it, to allow overriding it with an implementation that does not satisfy that attribute. The fact that guarantees given by a base class cannot be reduced by a derived class are part of the Liskov substitution principle and cannot be addressed by this DIP. Whether a method (not only a functional) should carry a warrant attribute, is a discretionary decision to be made by the class author.

Functions with Typesafe Variadic Lazy Parameters

A function taking a variable number of lazy parameters has, as its last parameter, a static array or slice type whose underlying type is a possibly qualified delegate type taking no parameters.

The motivation behind the notion of essential FP/D objects, types, and calls is this use-case, generalized accordingly. A standard example of taking a variable number of lazy parameters is coalesce, a function that returns the first value that is not null (or null if none is).

T coalesce(T)(const scope T delegate()[] paramDGs...)
{
    foreach (paramDG; paramDGs)
    {
        static assert(is(typeof(paramDG) == const));
        if (auto result = paramDG()) return result;
    }
    return cast(T) null;
}

Here, the loop variable paramDG is a const qualified local initialized from the const parameter paramDGs. By the second clause, calling paramDG does not invalidate any warrant attribute when attribute inference is performed. As a result, coalesce has warrant attributes inferred based on attributes on T's move construction, its cast to bool, and its construction from null, but not on the calls to the parameters.

Mutable Parameters

Calls to mutable parameters are not subject to the relaxed/altered conditions. This example demonstrates why. Consider coalesce from the example above, but with a differently typed parameter:

T coalesce(T)(scope const(T delegate())[] paramDGs...);

In contrast to the above implementation, the outermost layer of paramDGs type is mutable. Since the context has no control over what coalesce does internally, coalesce could append the slice and call the appended delegate object. For that reason, it will not have any warrant attribute inferred.

paramDGs ~= () => returns!T();
paramDGs[$ - 1]();

Changes to the outermost layer of indirection of a parameter are invisible to the caller, and thus the above code could be rewritten so that paramDGs is not appended allowing for it to be const on the outermost layer, too.

The same applies for mutable local eFP/D type variables. Merely stating the mutable version of the underlying parameter slice's type creates a mutable local variable.

T coalesce(T)(const scope T delegate()[] paramDGs...)
{
    foreach (T delegate() paramDG; paramDGs)
    {
        // static assert(is(typeof(paramDG) == const)); // fails
        paramDG = () => returns!T();
        if (auto result = paramDG()) return result;
    }
    return cast(T) null;
}

In this case, too, coalesce would not have any warrant attribute inferred.

Const and Aliasing

Here, we will look at an example why requiring const does in fact guarantee that the context retains control over the type of parameters in the functional.

First, we will have a look at regular pointer aliasing:

void proneToAliasing(ref int x, const(int)* p)
{
    assert(*p == 0);
    x = 1; // looks innocent, but ...
    assert(*p == 1); // ... can make this pass.
}
void resistsAliasing(ref int x, immutable(int)* p) { ... }
void context()
{
    int x = 0;
    proneToAliasing(x, &x); // okay
    resistsAliasing(x, &x); // error
}

Aliasing can happen in the first function because an int* can be assigned to a const(int)*. It cannot happen in the second because an int* cannot be assigned to an immutable(int)*.

For trying to trick the type-system into considering a call to a @system function a @safe operation, aliases of function pointers will be used the same way as above with ints. This is our setup:

alias sysFunc = function int() @system
    { int* p; int x; p = &x; return *p; };

alias SysFP = int function();
int seeminglyAliasingProneFunctional(ref SysFP fp, const(int function()/*@safe*/)* fpp) @safe
{
    fp = sysFunc; // assign a @system function ptr to a @system fp variable, okay
    return (*fpp)(); // essentially call a parameter
}

Next, we look at a @safe context that tries calling seeminglyAliasingProneFunctional with mutable function pointers.

void context() @safe
{
    int function() @safe mutableSafeFp = () => 1;
    seeminglyAliasingProneFunctional(mutableSafeFp, &mutableSafeFp);
}

The call to seeminglyAliasingProneFunctional does not compile. Regardless of commenting-in the /*@safe*/ above and the implementation of this DIP, that code will not compile, since the second argument is not the problem. It is the first one: A @safe function pointer cannot be bound to a mutable @system function pointer parameter by ref. Assigning a @safe FP/D to a @system variable uses an implicit conversion that is not allowed for binding to ref. It's ref that needs an exact match for mutable types, and the same is true for any form of mutable indirection. Because fpp is a pointer to a const, some implicit conversions may take place, and dropping warrant attributes is among them.

For completeness, if mutableSafeFp were to be replaced by a @system function pointer like this

int function() @system mutableSysFP = () => 1;
aliasingProneFunctional(mutableSysFP, &mutableSysFP);

by the proposal of this DIP, the bindings work fine, but since the @safe functional's const parameter is not bound by a @safe function pointer, the call to seeminglyAliasingProneFunctional is not considered @safe, leading to a compiler error in the @safe context.

Overriding Methods

This example demonstrates what changes when base class or interface methods are overridden and how dropping attributes when overriding is useful.

class Base
{
    void functional(const void function()[] paramFunctions) @safe
    { foreach (fp; paramFunctions) fp(); } // becomes valid
    abstract void gunctional(const void function(int) paramFunction) @safe
    { paramFunction(1); } // becomes valid
    abstract void hunctional(int function(int) pure @safe paramFunction) pure @safe;
}

interface Interface
{
    int junctional(const int function(int) pure @safe paramFunction) @safe;
    int kunctional(const int function(int) pure paramFunction) pure @safe;
    int lunctional(int function(int) pure @safe paramFunction) pure @safe;
}

Both implementations of the methods in Base become valid by the changes this DIP proposes.

In the following code comments, weakening the overload means that the implementation is barred from operations the base class implementation were not. Primarily, this means (essentially) calling a parameter. Overriding together with dropping attributes from a parameter's type becomes valid by the changes proposed by this DIP concerning contravariant parameter overriding; this is not explicitly mentioned in the following code comments.

class Derived : Base, Interface
{
    // Dropping const on the first layer of indirection weakens the override:
    override void functional(const(void function())[] paramFunctions) @safe
    { foreach (fp; paramFunctions) fp(); } // stays invalid: cannot call @system fp
    override void gunctional(void function(int) paramFunction) @safe
    { paramFunction(1); } // stays invalid: cannot call @system paramFunction

    // Dropping attributes on a const parameter type makes sense with this DIP:
    override void hunctional(const void function(int) pure fp) pure @safe
    { paramFunction(1); } // becomes valid

    // Dropping const is fine, as long as the functional's attributes are also on the parameter:
    override int junctional(int function(int) pure @safe paramFunction) @safe
    { return paramFunction(1); } // stays valid
    // (Keeping the pure requriement, a further derived implementation's logic can make use of it.)

    // Dropping const on a parameter with lower attributes weakens the override:
    override int kunctional(int function(int) pure paramFunction) pure @safe
    { return paramFunction(1); } // stays invalid: cannot call @system paramFunction

    // Dropping attributes while adding const on a parameter does not weaken the override:
    override int lunctional(const int function(int) pure paramFunction) pure @safe
    { return paramFunction(1); } // becomes valid
}

The implementation of the overrides of Base's methods are invalid, but, by the proposed changes of this DIP, can be made valid by declaring the parameters const on the first layer of indirection.

The override of hunctional dropping pure on its parameter's type becomes valid by the proposed changes of this DIP. However, by the current state of the language, Derived.hunctional cannot call its parameter, but by the proposed changes of this DIP, it can. Calls to Interface.hunctional with a pure argument stay well-behaved. (With an impure argument, they stay invalid.) Calls to Derived.hunctional with an impure argument become meaningful although impure themselves.

The example of junctional shows that if the parameter's type has the same or more warrant attributes as the functional, const is not necessary on the parameter and can be added or dropped without a difference. However, dropping const on a parameter with a type that has fewer warrant attributes than the functional like kunctional has consequences. (Adding warrant attributes to parameters is not allowed when overriding.) On the other hand, adding const allows the functional to make use of its parameters with lower attributes, as lunctional demonstrates.

(Note that as of the writing of this DIP, there is a difference between delegates and function pointers due to issue 21537.)

Third-order and Even-Higher-Order Functionals

All the functionals presented in illustrations and examples were of second order, i.e., the FP/D types in functionals' parameter lists themselves took no eFP/Ds as parameters.

The easiest example of a non-trivial third-order functional is this:

void doNothing() /*pure*/ { }
void justCall(const void function() f) pure { f(); }

void thirdOrderFunctional(const void function(void function()) secondOrderParameter) pure/*?*/
{
    // Here, secondOrderParameter is assumed to be pure by the rules of this DIP.
    // This does not mean that the following call expression is immediately valid in a pure function.
    // Being a functional, calling secondOrderParameter is pure iff its argument is typed pure.
    secondOrderParameter(&doNothing);
}

void context() pure
{
    thirdOrderFunctional(&justCall);
}

Say we wanted to annotate thirdOrderFunctional with pure for it to be callable from the to-be-pure context. That means that, given a secondOrderParameter that is pure, it will act in accordance to the attribute. For secondOrderParameter to be pure means that it, too, acts in accordance to the attribute when fed with a pure argument. If we annotate doNothing with pure, this is the case. If we forget to annotate doNothing properly, the call expression secondOrderParameter(&doNothing) is considered impure. While the relaxed rules assume that secondOrderParameter is pure, it being a functional means it only acts in accordance to that attribute if its arguments are typed accordingly.

We finish this example with a fourth-order functional.

...

void fourthOrderFunctional(const void function(void function(void function())) thirdOrderParameter) pure
{
    // Due to the rules of this DIP, thirdOrderParameter is assumed to be pure.
    // Because justCall is annotated pure, the call really is pure and the constraints are satisfied.
    thirdOrderParameter(&justCall)
}

void context() pure
{
    // Because fourthOrderFunctional and thirdOrderFunctional are annotated pure,
    // this call is pure.
    fourthOrderFunctional(&thirdOrderFunctional);
}

Functions returning Function Pointers or Delegates

Since attributes do not impose any restrictions on returning FP/Ds, the rules remain completely unchanged.

alias R = int function() nothrow;
R returnsNothrowFP(int x) pure
{
    if (x < 0) throw new Exception("");
    else return { static int counter; return counter++; };
}

Here, returnsNothrowFP is a pure function that may throw, retuning a pointer to an impure nothrow function. This is to demonstrate that attributes on functions do not interact in any way with attributes on their return values if those return values happen to be of FP/D type.

Alternatives

The Current State

As this DIP does not introduce new possibilities, there is a way to mimic the behavior of the changes introduced by this DIP.

We take a look at SimpleLockstep again from the Lockstep Iteration example.

First, we observe that none of the operations in opApply directly violate any warrant attribute. So, in the best case scenario with respect to Ranges, opApply should be able to carry all warrant attributes.

Making opApply a template takes away the possibility to infer the foreach loop variables' types, so this is not an option.

However, one can move the code inside opApply into a template taking the delegate type as a template parameter and creating aliases named opApply to instances of that implementation template:

SimpleLockstep(Ranges...)
{
    Ranges ranges;

    ...
    alias ElementTypes = ...;

    private int opApplyImpl(DG : const int delegate(ref ElementTypes))(const scope DG foreachBody) { ... }

    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure nothrow @safe @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)      nothrow @safe @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure         @safe @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)              @safe @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure nothrow       @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)      nothrow       @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure               @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)                    @nogc);
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure nothrow @safe      );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)      nothrow @safe      );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure         @safe      );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)              @safe      );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure nothrow            );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)      nothrow            );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes) pure                    );
    alias opApply = opApplyImpl!(int delegate(ref ElementTypes)                         );

    bool anyEmpty() { ... }
    static string frontCalls() in (__ctfe) { ... }
    void popFronts() { ... }
}

This solution has some drawbacks:

• DRY violation.
• Unnecessary template bloat.
• The 16 combinations of attributes have to be spelled out; avoiding spelling them out requires string mixins which, from a maintainability standpoint, is worse.

If one of the Ranges happens to have a primitive that fails some attributes, the corresponding opApplys will be identical. As an example, if popFront is impure, all opApply overloads created by instantiating the implementation template with a pure delegate type lead to identical impure opApplys regardless. Depending on what overloads are called, it might lead to binary bloat.

If a warrant attribute is to be added to the language, the number of overloads to spell out increases to 32. In general, this does not scale well. Also, from a maintainability standpoint, templates should have no problems with the addition of another attribute. However, since they need to be spelled out, the code has to be adapted to the new circumstance. From the perspective of working with all attributes, adding a warrant attribute breaks code.

In meta-programming, one tends to care little about attributes, since they are inferred, unless of course the details of one becomes part of the function's logic.

If the functional in question is part of an interface or otherwise part of an inheritance hierarchy, templates cannot (easily) be customized, e.g., by overriding them.

New Attributes

Attribute bloat is already a concern raised in the D Language Forum. Any of these solutions would increase it.

Weak Clones

Breakage could be avoided by introducing weak clones of the current warrant attributes. They would mean the same as the current (strong) warrant attributes for first-order functions. The DIP author considers this option to be less desirable because the weak attributes

• need new syntax,
• have an overly specific use-case, therefore
• fear to have almost no adoption by developers.

One should mention that pure, when it meant strongly pure, did not get a weak counterpart for weak purity, but was redefined because strong and weak function purity can be distinguished by the type system taking parameter types into account.

Because there is a DIP (pre-draft at the time of this writing) called Argument-dependent Attributes (AdA for short) that follows this approach, the following part will use the syntax it proposes. It uses the syntax @safe(parameterFunc) to express that the @safety of the functional depends on parameterFunc's @safety. To be meaningful, parameterFunc must be a @system FP/D type. In its body, the functional cannot assign a @system FP/D object to parameterFunc, since calling it would be unsound. However, since const is not involved, the parameter can be reassigned with a @safe FP/D object. Unless the parameter is ref, a local variable serves the job equally well, since the assignment is internal to the functional and cannot be observed by the context.

When it comes to eFP/D types with at least one layer of indirection, e.g., int delegate()[] – any weak clones alternative would have to address them – mutability affects the context: the functional may assign elements of the slice, affecting the context doing so:

void safeFunc() @safe;
void sysFunc() @system;

void functional(void function()[] sinks) @safe(sinks)
{
    foreach (sink; sinks)
    {
        sink();
        sink = &safeFunc; // allowed
        sink = &sysFunc; // error; note that is(typeof(sink) == typeof(&sysFunc))
    }
}

In the opinion of the author, this is an uncommon thing to do or to ask for; a mitigation therefore has not to be particularly elegant. A way to rewrite this using the changes proposed by this DIP is the following:

void functional(const void function()[] callSinks, void function() @safe[] writeSinks) @safe
{
    foreach (callSink; callSinks) callSink();
    foreach (writeSink; writeSinks) writeSink = &safeFunc;
}

The context can pass the same slice to both parameters, callSinks and writeSinks.

Indicate not Calling a Parameter

Another possibility is breaking code, but at least giving programmers the ability to state explicitly that a parameter is not (essentially) called, probably using an attribute like @nocall. The call of a functional with an argument that is passed to a parameter annotated @nocall will not water down its guarantees. The new attribute could be inferred for parameters of function templates.

This solution is undesirable because a functional not calling its parameter is incredibly rare. Even rarer is the case where attributes of the argument passed to the functional and the attributes of the context are incompatible in the sense that the argument has strictly weaker guarantees than the context. Even then, this situation can be handled with the changes proposed by this DIP: Setting the first layer of indirection mutable, it is handled the way it is in the current state of the language.

Indicate Calling a Parameter

Conversely, an attribute @calls could be introduced that indicates that a functional indeed calls its parameter. Feeding an argument with lower guarantees than the functional then waters down the functional's guarantees only if it is passed to a parameter annotated with @calls. The new attribute would be inferred for function templates.

This solution is undesirable because the attribute would be on almost every functional. Forgetting that leads to compile errors that, depending on the error message, might be confusing.

Analogous to the alternative above, it could be handled by making the parameter const.

Contravariant Overriding

The Language Maintainers may find that changing what qualifier conversions are is too unpredictable. As an alternative, when overriding methods in particular, an exception be made and attribute droppings are treated the same as qualifier conversions.

Outlook

None of the following expositions are being proposed as a change, however, they serve as a demonstration of what future developments of the language are enabled by it.

Lazy as a Lowering

Lazy parameters use a delegate internally, but cannot bind delegates with the return type stated: Any argument expression bound to a lazy parameter is currently rewritten to delegate() => expression. This rewrite is not optional and occurs even if it leads to an error (while omitting the rewrite would compile).

Implementing this DIP, lazy can be changed to mean in, but can be combined with the storage classes ref and auto ref, and storage class type constructors like const. The additional storage classes become part of the delegate type as follows:

• ref becomes part of the delegate type as a member function attribute, meaning that the delegate returns by reference.
• For function templates, auto ref becomes part of the delegate type as ref if the supplied argument returns by ref (and nothing otherwise).
• Type constructors become part of the delegate type by applying them to the delegate's return type.

Other storage classes make no sense in combination with lazy, as the implied in is incompatible with them, or they cannot become part of the delegate type in a meaningful way.

Type constructors and ref are redundant with the in storage class, except shared. Because the implicitly generated delegate is always thread-local, i.e., never a shared object, shared cannot be meaningfully applied to the delegate. Also, there is no way to supply a shared delegate without circumventing the type system because the delegate is always created implicitly.

When lazy is used with ref, the ref is considered part of the delegate type (meaning the delegate returns by reference). (Note that delegate types retuning by reference cannot be expressed directly in a function signature; see issue 21521.) When lazy is used with auto ref in a function template, ref-ness of the delegate type is inferred from the argument.

When binding an L-value expression, delegate ref() => expression is tried first. If that does not succeed, delegate() => expression is used. That way, L-value expressions bind to a delegate returning ref when possible.

On a lazy parameter, the trait isRef should return the ref-ness of the delegate return value. The trait isLazy already tests for that storage class specifically.

A preview switch -preview=lazy might be added to the compiler for the transition. It would imply -preview=in.

Default Attributes

As pointed out further above, changes akin to the ones proposed here are necessary for making a warrant attribute the default.

Breaking Changes and Deprecations

Functionals that do not essentially call one of their const, inout, or immutable qualified eFP/D parameters may suffer from breakage.

An example of an affected functional could be the following. (Note that, depending on the state of the language, in means const or const scope.)

int delegate() toDelegate(in int function() func) nothrow pure @safe
{
    alias toDG(alias f) = delegate() { return f(); };
    return toDG!func;
}

In the current state of the language, a @safe context can call toDelegate with a @system argument.

With the changes proposed by this DIP, the call in the context will become invalid. However, one must wonder what the @safe context would do with that @system return value, since it cannot call it directly. To make use of it, it must find its way to a point where calling a @system delegate is valid. However, this could be in a @trusted pseudo-block (a lambda immediately called) in the context.

Because the proposed change only affects parameters qualified on the highest level of indirection, this problem can be solved by pushing down the const qualifier one level of indirection. In the example above, in has to be removed or replaced by scope.

The amount of breakage is probably very low and has an easy transition path in almost all cases. In the opinion of the author, the gains clearly outweigh the costs.

References

Terms

1. Wikipedia: Higher-order function:

   In mathematics and computer science, a higher-order function is a function that does at least one of the following:

   • takes one or more functions as arguments (i.e. procedural parameters),
   • returns a function as its result.

   This document only refers to higher-order functions as the ones in the first bullet point since this proposal is not concerned about return values.

   Also note that first-order function in this context refers to any function that is not a higher-order function.

2. Wikipedia: Functional:

   In computer science, [the term functional] is synonymous with higher-order functions, i.e. functions that take functions as arguments or return them.

D Language Specification

1. Foreach over aggregates
2. Lazy Parameters
3. Lazy Variadic Functions

General D Forum Discussions

1. opApply with Type Inference and Templates?
2. Parameterized delegate attributes
3. @nogc with opApply

DIP 1032

1. DIP 1032: Function Pointer and Delegate Parameters Inherit Attributes from Function
2. Discussion: H. S. Teoh's comment
3. Discussion: Walter Bright's answer

Mentioned and Related Issues in the Issue Tracker

1. opApply and nothrow don't play along
2. Cannot state ref return for delegates and function pointers
3. Function pointers' attributes not covariant when referencing

Other Links

1. CppReference.com about the noexcept specifier

Copyright & License

Copyright © 2020–2021 Quirin F. Schroll and the D Language Foundation

Licensed under Creative Commons Zero 1.0

Reviews

Community Review Round 1

Reviewed Version

Discussion

Feedback

The following actionable feedback was presented in the Feedback Thread:

• The beginning of the DIP is too verbose. The DIP author asked for clarification but received none.
• The DIP is more complex than it needs to be simply to avoid adding new syntax. The DIP author disagreed and explained his motivations.
• The first example exploits a hole in the type system. The DIP author disagreed and provided an explanation.
• The DIP makes an incorrect assumption that calling delegates is the only reasonable way to manipulate them in higher-order functions. The DIP author clarified that the assumption made is that calling mutable delegate parameters is the most common use case and that returning them is rarer.

Addendum

Subsequent to the first round of Community Review, the DIP author concluded that this DIP is dependent on language semantics that some view as a bug. He has decided to delay progress of the DIP until the language maintainers provide a definitive opinion on that view.