[swift-evolution] [Pitch] Support for pure functions. Part n + 1.

[Xiaodi Wu]

This is very, very interesting. Thank you so much for the text.

If I understand your take correctly, the benefits of `pure` in Swift would
be contingent on how pervasively it can be used (as it's the composability
of pure functions that gives it exponential value). And, based on your
discussion, very few functions in Swift would be compiler-provably pure,
meaning any realistic adoption would have to mean "trust me, compiler, it's
pure even though you can't prove it" as opposed to "go ahead, compiler,
test my assertion that this function is pure." If Swift is to keep its
promise of safety by default (granted, principally memory safety), this is
going to have to prompt some soul-searching as to whether that's a very
safe thing to add. It would also mean that lots of things would have to be
manually annotated "trust me" after careful analysis of whether that trust
is warranted, as opposed to the compiler being able to work that out for
itself for free.

Can I venture an operational definition of semantic purity? Maybe this
would be a basis to talk about what "trust me, it's pure" would mean, if we
wanted it:

Consider two variables `a` and `b`, without regard to whether they are
instances of value types or reference types, and without regard to whether
those types are Equatable.

```
let aa = a
let bb = b
```

Let's define, only for the purposes of this discussion and not as an actual
syntax, a notion of pseudo-equality. We will say that `aa` is pseudo-equal
to `a` and `bb` is pseudo-equal to `b`. (I deliberately choose not to
conflate this notion with Equatable's `==` or with `===`.) Now, consider a
function `f(_:_:)`.

```
let result1 = f(a, b)
// ...
// arbitrary code to be executed here
// ...
let result2 = f(aa, bb)
```

The function `f(_:_:)` is pure if, for any `aa` pseudo-equal to `a` and for
any `bb` pseudo-equal to `b`, and for any arbitrary code in the middle, the
snippet above could be replaced by the snippet below with no observable
change in behavior:

```
let result1 = f(a, b)
// ...
// arbitrary code to be executed here
// ...
let result2 = result1
```

Now, this naive definition would preclude I/O and inout, but it would not
preclude infinite loops, fatal errors, etc.


On Sun, Feb 19, 2017 at 10:49 PM, Michel Fortin <michel.fortin at michelf.ca>
wrote:

> The message about D was from me. I'm actually quite familiar with D so
> I'll try to summarize it's take on purity here.
>
> # Pure in D
>
> D has the keyword `pure`, and the compiler enforces purity constraints.
> There is basically two types of pure functions: strongly pure ones and
> weakly pure one, but in general when writing code you can ignore the
> distinction: they all use the same `pure` attribute. The strongly pure one
> is the kind that can be optimized because it has no side effect and its
> result can be reused. The weakly pure one is the kind that takes pointers
> to non-immutable memory and for which you either cannot guaranty a stable
> result across calls or cannot guaranty it won't mutate the memory behind
> those pointers. (Keep in mind that object references are a kind of pointer
> too.) The compiler examine the type of the parameters of a pure function to
> determine if they contain pointers (including pointers hidden in structs)
> and classify it as weakly or strongly pure.
>
> Pure functions are allowed to throw, to exit the program, to run infinite
> loops, and to allocate memory. They can't access global variables unless
> they are immutable (constant), or they are passed as an argument using a
> pointer.
>
> All pure functions can only call other pure functions. This is the part
> where weakly pure is useful: a strongly pure function can call a weakly
> pure function since the weakly pure one will only be able to mutate the
> local state of the enclosing strongly pure function, always in a
> deterministic way.
>
> In D, `const` and `immutable` are transitive attributes, meaning that any
> memory accessed through such pointer is also `const` or `immutable`. So if
> you pass a `const` or `immutable` value to a function in D, it won't be
> able to mutate anything. This makes many functions strongly pure even in
> the presence of pointers.
>
> `pure` in D can also be used to create guarantied uniquely referenced
> objects and object hierarchies, which then can then become transitively
> immutable once they are returned by the pure function.
>
> `pure` works so well in D that most functions are actually pure. There is
> some pressure in libraries to mark functions as pure because their
> functions then become usable inside other pure functions, which means that
> as time passes more and more functions get the pure attribute. To ease the
> burden of adding these attributes everywhere, pure is inferred for template
> functions (and only template functions, because non templates are allowed
> to be opaque).
>
> Official reference: https://dlang.org/spec/function.html#pure-functions
>
> # Pure in Swift?
>
> Because Swift does not have that concept of transitive immutability, I'm
> under the impression that very few functions would be "strongly pure" in
> Swift, making optimizations impossible except for the trivial value types.
> Or, maybe, when a "trust me" attribute vouch that the implementation of a
> value type is pure-compatible.
>
> But I'd be wary about relying much on a "trust me" attribute, as it
> greatly diminish the value of having `pure` in the first place. Add a
> "trust me" at the wrong place and the compiler will not complain when it
> should. Forget a "trust me" somewhere and the compiler will complain where
> it should not. The ratio of "trust me"/`pure` has to be very small for the
> whole purity system to be valuable.
>
> The way I see it, `pure` is likely to make things more complicated for
> everyone, not just for those who want to use pure. Those who want to use
> pure will be asking for everything they want to use to be labeled correctly
> (either with `pure` or "trust me", whichever works).
>
> # What about constexpr?
>
> That's the name of a C++ feature where the compiler evaluates a function
> at compile time to set the value of a constant. This obviously only works
> for functions with no side effects. `constexpr` is the keyword attached to
> those functions.
> http://en.cppreference.com/w/cpp/language/constexpr
>
> The difference from `pure` is that this happens only at compile time.
> Which means you can implement it like D has done instead: treat all
> functions as evaluatable and only stop and emit an error upon reaching an
> instruction that cannot be evaluated. No special attribute needed. Only
> works for functions where the source code is available.
> https://dlang.org/spec/function.html#interpretation
>
> The D approach won't work for Swift across module boundaries, except
> perhaps for functions that can be inlined. For resilience you might want an
> attribute to make it a contract that the inline version is compile-time
> evaluable.
>
>
> Le 19 févr. 2017 à 20:58, Xiaodi Wu via swift-evolution <
> swift-evolution at swift.org> a écrit :
>
>
> I don't know very much about this topic, so I won't pretend that I have
> strong feelings about Michel's questions, but they are undeniably important
> and undoubtedly only one of many.
>
> Before we get to any syntactic bikeshedding, can the proponents of this
> feature write up a comparative summary to educate us about the current
> state of the art? How have other languages have defined purity? I recall an
> earlier message about D, and some rough comparisons or non-comparisons to
> C++ constexpr. Roughly, it would be very helpful to get some sense of the
> following:
>
> What other C-family languages have a concept of purity?
>
> How is purity defined in those languages?
>
> What use cases are enabled by those definitions of purity, and just as
> important, what use cases are notably excluded by them?
>
> If there is evidence in the public record to this effect: if the designers
> of those languages could do it again, have they expressed any thoughts
> about how they would do it differently with respect to purity?
>
> It has been said that Haskell and other functional languages prioritize
> purity over ergonomics of impure functions like I/O. With that in mind,
> what design choices surrounding purity made by those languages are
> off-limits for Swift?
>
> What use cases or even compiler optimizations are possible in Haskell and
> other non-C family languages with a more expansive or stricter concept of
> pure functions that we don't find in C-family languages?
>
> If Swift were to adopt some of these beyond-C rules, how would that impact
> the user experience with common impure functions (I/O, etc.)?
>
> On Sun, Feb 19, 2017 at 14:45 T.J. Usiyan via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> I'm going to update the draft with points addressed here and the twitter
>> conversation. There have been quite a few implications to consider pointed
>> out.
>>
>> This feature is not 'for' the compiler as much as it is for humans
>> writing code, but I will address that in the update.
>>
>> On Sun, Feb 19, 2017 at 3:34 PM, David Sweeris <davesweeris at mac.com>
>> wrote:
>>
>>
>> On Feb 19, 2017, at 11:47, Michel Fortin via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>>
>> 7. Is it desirable that the optimizer sometime take the pure attribute to
>> heart to combine multiple apparently redundant calls into a single one? Or
>> is pure not intended to be usable for compiler optimizations? The ability
>> to optimize will likely be affected by the answer to these question and the
>> loopholes you are willing to allow.
>>
>>
>> AFAIK, "compiler optimizations" are main point of having a keyword for
>> pure functions. (Well, that and whatever role it might play in supporting
>> constant expressions, but that seems like more of a compiler implementation
>> detail than an actual "feature" of pure functions.)
>>
>> Calling fatalError() is fine IMHO because, at that point, any
>> side-effects become a moot point.
>>
>> I'm inclined to say that passing in reference values is ok, as long as we
>> can prove the function doesn't modify anything. Don't know how we'd do
>> that, though, since classes don't need that `mutating` keyword for
>> functions that mutate `self`.
>>
>> If someone is determined to use pointers to pointers to get global state
>> or something to trick the compiler into accepting *semantically* impure
>> code as *syntactically* pure, I'm not sure there's a way we can really
>> stop them. Not and still have @pure be useful. (Or maybe we can... I'm
>> merely thinking of the saying, "every time someone builds a fool-proof
>> system, the world makes a bigger fool".)
>>
>> I would think that allocating memory is ok, as long as it's either
>> deallocated by the time the function exits or it's part of the return
>> value, but I don't know a lot about low-level implementation details, so
>> maybe there's something I'm missing. If that is a problem, though, I think
>> the answer to your "what subset..." question would, more or less, be
>> whatever subset doesn't rely on the runtime (the usefulness of that subset
>> should expand if/when we extend the syntax around tuples or support
>> fixed-length arrays in some other way).
>>
>> In any case, yeah, IMHO you're correct that we should nail down the
>> semantics before worrying so much about the syntax.
>>
>> - Dave Sweeris
>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> --
> Michel Fortin
> https://michelf.ca
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170219/33464a7d/attachment.html>