Pure functions and promises
delay/  pure/  stateless
delay/  pure/  stateful
promise/  pure/  maybe-stateful?
promise/  pure/  stateless?
pure/  stateless
pure/  stateful
pure-thunk/  stateless
pure-thunk/  stateful
define-pure/  stateless
define-pure/  stateful
built-in-pure-functions-set
built-in-pure-functions-free-id-set
immutable/  stateless/  c
immutable/  stateful/  c
unsafe-pure/  stateless
unsafe-operation/  mutating
unsafe-declare-pure/  stateless
unsafe-declare-allowed-in-pure/  stateful
6.12

Pure functions and promises

Georges Dupéron <[email protected]>

 (require delay-pure) package: delay-pure

syntax

(delay/pure/stateless expression)

syntax

(delay/pure/stateful expression)

Produces a promise for expression which does not cache its result, like delay/name. The delay/pure/stateless form checks that the expression is pure by wrapping it with (pure/stateless expression). The delay/pure/stateful form instead relies on (pure/stateful expression).

procedure

(promise/pure/maybe-stateful? v)  boolean?

  v : any/c
A predicate which recognizes promises created with both delay/pure/stateless and delay/pure/stateful.

procedure

(promise/pure/stateless? v)  boolean?

  v : any/c
A predicate which recognizes promises created with delay/pure/stateless, and rejects those created with delay/pure/stateful.

syntax

(pure/stateless expression)

syntax

(pure/stateful expression)

Checks that the expression is pure. This is done by fully expanding the expression, and checking at run-time that the free variables (including functions) contain only immutable values and pure functions. There is a hard-coded list of built-in functions which are known to be pure. The functions created with define-pure/stateless are also accepted (but not those created with define-pure/stateful), as well as struct accessors and predicates, and struct constructors for immutable structures.

Note that the expressions can refer to variables mutated with set! by other code. Placing the expression in a lambda function and calling that function twice may therefore yield different results, if other code mutates some free variables between the two invocations. In order to produce a pure thunk which caches its inputs (thereby shielding them from any mutation of the external environment), use pure-thunk/stateless and pure-thunk/stateful instead.

The first form, pure/stateless, checks that once fully-expanded, the expression does not contain uses of set!. Since the free variables can never refer to stateful functions, this means that any function present in the result is guaranteed be a stateless function. The results of two calls to a stateless function with the same arguments should be indistinguishable, aside from the fact that they might not be eq?. In other words, a stateless function will always return the “same” (not necessarily eq?) value given the same (eq?) arguments. If the result contains functions, these functions are guaranteed to be stateless too.

With the second form pure/stateful, uses of set! are allowed within the expression (but may not alter free variables). The resulting value will be an immutable value which may contain both stateless and stateful functions. Stateful functions may be closures over a value which is mutated using set!, and therefore calling a stateful function twice with the same (eq?) arguments may produce different results. Since Typed/Racket does not use occurrence typing on function calls, the guarantee that the result is immutable until a function value is reached is enough to safely build non-caching promises that return the “same” value, as far as occurrence typing is concerned.

Promises created with delay/pure/stateless and delay/pure/stateful re-compute their result each time, which yields results that are not necessarily eq?. This means that calling eq? twice on the same pair of expressions may not produce the same result. Fortunately, occurrence typing in Typed/Racket does not rely on this assumption, and does not "cache" the result of calls to eq?. If this behaviour were to change, this library would become unsound.

TODO: add a test in the test suite which checks that Typed/Racket does not "cache" the result of eq? calls, neither at the type level, nor at the value level.

syntax

(pure-thunk/stateless thunk)

(pure-thunk/stateless thunk #:check-result)

syntax

(pure-thunk/stateful thunk)

(pure-thunk/stateful thunk #:check-result)
Like pure/stateless and pure/stateful, but the thunk expression should produce a thunk. When #:check-result is specified, a run-time guard on the function’s result is added. The guard checks that the result is an immutable value. With pure-thunk/stateless, the result guard only accepts immutable values, possibly containing stateless functions. With pure-thunk/stateful, the result guard also accepts immutable values, possibly containing stateful functions.

syntax

(define-pure/stateless (name . args) maybe-result body ...)

(define-pure/stateless
  (: name . type)
  (define (name . args) maybe-result body ...))

syntax

(define-pure/stateful (name . args) maybe-result body ...)

(define-pure/stateful
  (: name . type)
  (define (name . args) maybe-result body ...))
 
maybe-result = 
  | : result-type
Defines name as a pure function. The define-pure/stateful form relies on pure/stateful, and therefore allows the function to return a value containing stateful functions. On the other hand, define-pure/stateless relies on pure/stateless, and therefore only allows the return value to contain stateless functions.

Due to the way the function is defined, a regular separate type annotation of the form (: name type) would not work (the function is first defined using a temporary variable, and name is merely a rename transformer for that temporary variable).

It is therefore possible to express such a type annotation by placing both the type annotation and the definition within a define-pure/stateless or define-pure/stateful form:

(define-pure/stateless
  (: square : ( Number Number))
  (define (square x) (* x x)))

The define identifier can either be define from typed/racket or define from type-expander.

This set contains the built-in functions recognized as pure by this library.

For now only a few built-in functions are recognized as pure:

Patches adding new functions to the set are welcome.

for-syntax value

built-in-pure-functions-free-id-set : immutable-free-id-set?

This value is provided at level 1, and contains the identifiers of the functions present in built-in-pure-functions-set.

procedure

((immutable/stateless/c varref) v)  Boolean

  varref : Variable-Reference
  v : Any
Returns a predicate which accepts only values which are immutable, possibly containing stateless functions, but not stateful functions.

This predicate detects whether the functions contained within the value v are pure or not, based on the built-in-pure-functions-set set and a few special cases:

There seems to be no combination of built-in functions in Racket which would reliably associate a struct constructor (as a value) with its corresponding struct type. Instead, immutable/stateless/c uses a heuristic based on object-name: if struct-constructor-procedure? returns #true for a function, and that function’s object-name is st or make-st, then st is expected to be an identifier with static struct type information.

To achieve this, it is necessary to access the call-site’s namespace, which is done via the varref parameter. Simply supplying the result of (#%variable-reference) should be enough.

procedure

((immutable/stateful/c varref) v)  Boolean

  varref : Variable-Reference
  v : Any
Returns a predicate which accepts only values which are immutable, possibly containing both stateful and stateless functions.

This predicate needs to access the call-site’s namespace, which is done via the varref parameter. Simply supplying the result of (#%variable-reference) should be enough.

See the documentation for immutable/stateless/c for an explanation of the reason for this need.

syntax

(unsafe-pure/stateless expression)

Indicates that the expression should be trusted as allowable within a pure/stateless or pure/stateful block or one of their derivatives. No check is performed on the expression.

The unsafe-pure/stateless form can be used within pure/stateless, pure/stateful and their derivatives, to prevent any check on a portion of code.

The expression should be a pure, stateless expression.

Note that in the current implementation, the expression is lifted (in the sense of syntax-local-lift-expression.

syntax

(unsafe-operation/mutating expression)

Indicates that the expression should be trusted as allowable within a pure/stateful block, or one of its derivatives. No check is performed on the expression.

The expression should not vary its outputs and effects based on external state (i.e. its outputs and effects should depend only on the arguments passed to it).

The expression function may internally use mutation. It may return freshly-created stateful objects (closures over freshly-created mutable variables, closures over mutable arguments, and mutable data structure which are freshly created or extracted from the arguments). It may mutate any mutable data structure passed as an argument.

Note that in the current implementation, the expression is lifted (in the sense of syntax-local-lift-expression.

syntax

(unsafe-declare-pure/stateless identifier)

Declares that the given identifier should be trusted as a stateless pure function. The given function is subsequently treated like the functions present in built-in-pure-functions-set.

Note that this has a global effect. For one-off exceptions, especially when it’s not 100% clear whether the function is always pure and stateless, prefer unsafe-pure/stateless.

Declares that the given identifier should be trusted as a function that can be used within pure/stateful and its derivatives.

The identifier function should not vary its outputs and effects based on external state (i.e. its outputs and effects should depend only on the arguments passed to it).

The identifier function may internally use mutation. It may return freshly-created stateful objects (closures over freshly-created mutable variables, closures over mutable arguments, and mutable data structure which are freshly created or extracted from the arguments). It may mutate any mutable data structure passed as an argument.

Note that this has a global effect. For one-off exceptions, prefer unsafe-operation/mutating.