11

Suppose I have these two F# functions:

let sq x = x*x

let tm = DateTime.Now

Clearly sq is pure in that it will always return the same value for a given input while tm is impure because it will return a different value each time it is called.

In general is there a way to determine if a particular function in F# is pure or impure without analyzing what it does, in other words reading it line by line?

Alternatively is there a way to annotate a function to tell the compiler that the function is pure or impure when you write it?

Finally when calling a function that is part of the common language runtime (such as DateTime) how can one tell if it is pure or impure without trying it?

Note: by "pure" I mean the definition from Wikipedia: http://en.wikipedia.org/wiki/Pure_function (permalink)

In computer programming, a function may be described as pure if both these statements about the function hold:

  1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.

  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

abatishchev
  • 98,240
  • 88
  • 296
  • 433
JonnyBoats
  • 5,177
  • 1
  • 36
  • 60
  • 1
    When you say pure, do you really mean idempotent? Or do you mean that it causes no side effects? – Robert Harvey Apr 08 '13 at 17:13
  • 1
    Ah, so Wikipedia says both. Fair enough. FWIW, I don't think Microsoft offers any sort of annotation or attribute that marks functions as "pure..." You just have to know. – Robert Harvey Apr 08 '13 at 17:23
  • You might also find the answers to this question http://stackoverflow.com/questions/4391524/is-returning-a-random-value-from-function-a-side-effect worthwhile reading. – Onorio Catenacci Apr 08 '13 at 21:14

3 Answers3

11

F# does not provide any features and tools for checking that methods are pure, so a simple answer is that you have to check this property yourself.

Outside of F#, it is worth noting that Code Contracts library has a notion of pure methods (and they can be marked with PureAttribute), but I'm not entirely sure what is the checking story there. I think Code Contracts come with static checker that analyses IL (and should work for F# too), but this is quite difficult task, so I would expect it to be quite limited. However, the PureAttribute is used on some BCL methods, so you can tell that some standard .NET methods are pure.

Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • 6
    `PureAttribute` is just a way of telling Code Contracts that the function is pure - no analysis (runtime or static) is performed – Alex Apr 09 '13 at 11:56
  • 3
    Unfortunately, Code Contracts [still](http://social.msdn.microsoft.com/Forums/en-US/11b8c5e3-a25d-4770-a46d-14f24921e0a0/f-and-code-contracts?forum=codecontracts) [doesn't](http://social.msdn.microsoft.com/Forums/en-US/7830b49c-ff45-4105-8609-1e2f8b81263d/when-will-f-be-supported?forum=codecontracts) work with F#. – Jack P. Oct 29 '13 at 18:02
1

Technically speaking your 'tm' value is not a function, but value of type DateTime and it is immutable, so every time you evaluating this value after creating it will always be the same.

Petr
  • 4,280
  • 1
  • 19
  • 15
  • 3
    ...and to clarify even further, if you said let tm() = DateTime.Now (note added brackets) you would force it to be a function which was probably your intent. – Kit Apr 09 '13 at 09:28
-1

Given that it is possible to define both, pure and inpure functions in f#, I would be well surprised if there was an algorithm that can check f# code (function definitions) for purity -- checking program code for semantic properties is generally undecidable by Rice's theorem.

D.F.F
  • 914
  • 1
  • 6
  • 17
  • [Nim](https://nim-lang.org/docs/manual.html#procedures-func) and [Haxe](https://haxe.org/manual/cr-metadata.html) actually do that and both stand knee-deep in both imperative and functional programming, so it's possible. – Matthias Schuster Mar 24 '21 at 21:02
  • Do they do that in some cases or all cases? – D.F.F Mar 27 '21 at 12:54
  • Nim added the last remaining edge case coverage a couple of weeks ago. I dont know about Haxe. – Matthias Schuster Mar 27 '21 at 15:28
  • The thread starter wants to be able "to determine if a particular function in F# is pure or impure". From what I understand, Nim verifies that some pure functions are in fact pure. However, I understand that the threadstarter wants a procedure, that given *any* function decides whether or not the function at hand is pure. In particular, If a function interacts with a global mutable variable *but finally does not change it*, this (depending on your definition of pureness) should be recognized as a pure function - which I still think is not possible. – D.F.F Apr 07 '21 at 11:56
  • Yeah, that could be true. Still, F# can do not one and not the other and the comment, that this is simply not possible in some language that supports imperative design, is incorrect. – Matthias Schuster May 09 '21 at 08:09