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

Mon Feb 20 09:09:19 CST 2017

> On Feb 19, 2017, at 11:19 PM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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.

This looks like it corresponds with my intuition of pure.  It is certainly a minimum requirement anything considered pure should meet (whether compiler verified or “trust me”). 

> 
> 
> On Sun, Feb 19, 2017 at 10:49 PM, Michel Fortin <michel.fortin at michelf.ca <mailto: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 <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 <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 <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 <mailto: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 <mailto: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 <mailto:davesweeris at mac.com>> wrote:
>> 
>>> On Feb 19, 2017, at 11:47, Michel Fortin via swift-evolution <swift-evolution at swift.org <mailto: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 <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
> 
> -- 
> Michel Fortin
> https://michelf.ca <https://michelf.ca/>
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170220/18e59dc3/attachment.html>