delay-pure.scrbl (13548B)
1 #lang scribble/manual 2 @require[racket/require 3 delay-pure 4 @for-syntax[racket/base 5 syntax/id-set] 6 @for-label[delay-pure 7 racket 8 (except-in (subtract-in typed/racket racket) :) 9 racket/promise 10 (only-in type-expander :)]] 11 12 @(module te racket/base 13 (provide te:define) 14 (require scribble/manual 15 (for-label type-expander)) 16 (define te:define (racket define))) 17 @(require 'te) 18 @(module tr racket/base 19 (provide tr:define) 20 (require scribble/manual 21 (for-label (only-meta-in 0 typed/racket))) 22 (define tr:define (racket define))) 23 @(require 'tr) 24 25 @title{Pure functions and promises} 26 @author[@author+email["Suzanne Soy" "racket@suzanne.soy"]] 27 28 @defmodule[delay-pure] 29 30 @deftogether[[@defform[(delay/pure/stateless expression)] 31 @defform[(delay/pure/stateful expression)]]]{ 32 33 Produces a promise for @racket[expression] which does not cache its result, 34 like @racket[delay/name]. The @racket[delay/pure/stateless] form checks that 35 the @racket[expression] is pure by wrapping it with 36 @racket[(pure/stateless expression)]. The @racket[delay/pure/stateful] form 37 instead relies on @racket[(pure/stateful expression)].} 38 39 @defproc[(promise/pure/maybe-stateful? [v any/c]) boolean?]{ 40 41 A predicate which recognizes promises created with both 42 @racket[delay/pure/stateless] and @racket[delay/pure/stateful].} 43 44 @defproc[(promise/pure/stateless? [v any/c]) boolean?]{ 45 A predicate which recognizes promises created with 46 @racket[delay/pure/stateless], and rejects those created with 47 @racket[delay/pure/stateful].} 48 49 50 @deftogether[[@defform[(pure/stateless expression)] 51 @defform[(pure/stateful expression)]]]{ 52 53 Checks that the @racket[expression] is pure. This is done by fully expanding 54 the expression, and checking at run-time that the free variables (including 55 functions) contain only immutable values and pure functions. There is a 56 hard-coded list of built-in functions which are known to be pure. The 57 functions created with @racket[define-pure/stateless] are also accepted (but 58 not those created with @racket[define-pure/stateful]), as well as 59 @racket[struct] accessors and predicates, and @racket[struct] constructors for 60 immutable structures. 61 62 Note that the expressions can refer to variables mutated with @racket[set!] 63 by other code. Placing the expression in a lambda function and calling that 64 function twice may therefore yield different results, if other code mutates 65 some free variables between the two invocations. In order to produce a pure 66 thunk which caches its inputs (thereby shielding them from any mutation of the 67 external environment), use @racket[pure-thunk/stateless] and 68 @racket[pure-thunk/stateful] instead. 69 70 The first form, @racket[pure/stateless], checks that once fully-expanded, the 71 @racket[expression] does not contain uses of @racket[set!]. Since the free 72 variables can never refer to stateful functions, this means that any function 73 present in the result is guaranteed be a @deftech{stateless} function. The 74 results of two calls to a @tech{stateless} function with the same arguments 75 should be indistinguishable, aside from the fact that they might not be 76 @racket[eq?]. In other words, a @tech{stateless} function will always return 77 the ``same'' (not necessarily @racket[eq?]) value given the same 78 (@racket[eq?]) arguments. If the result contains functions, these functions are 79 guaranteed to be @tech{stateless} too. 80 81 With the second form @racket[pure/stateful], uses of @racket[set!] are 82 allowed within the expression (but may not alter free variables). The 83 resulting value will be an immutable value which may contain both 84 @tech{stateless} and @deftech{stateful} functions. Stateful functions may be 85 closures over a value which is mutated using @racket[set!], and therefore 86 calling a @tech{stateful} function twice with the same (@racket[eq?]) 87 arguments may produce different results. Since Typed/Racket does not use 88 occurrence typing on function calls, the guarantee that the result is 89 immutable until a function value is reached is enough to safely build 90 non-caching promises that return the ``same'' value, as far as occurrence 91 typing is concerned. 92 93 Promises created with @racket[delay/pure/stateless] and 94 @racket[delay/pure/stateful] re-compute their result each time, which yields 95 results that are not necessarily @racket[eq?]. This means that calling 96 @racket[eq?] twice on the same pair of expressions may not produce the same 97 result. Fortunately, occurrence typing in Typed/Racket does not rely on this 98 assumption, and does not "cache" the result of calls to @racket[eq?]. If this 99 behaviour were to change, this library would become unsound. 100 101 TODO: add a test in the test suite which checks that Typed/Racket does not 102 "cache" the result of @racket[eq?] calls, neither at the type level, nor at 103 the value level.} 104 105 @deftogether[[@defform*[[(pure-thunk/stateless thunk) 106 (pure-thunk/stateless thunk #:check-result)]] 107 @defform*[[(pure-thunk/stateful thunk) 108 (pure-thunk/stateful thunk #:check-result)]]]]{ 109 110 Like @racket[pure/stateless] and @racket[pure/stateful], but the 111 @racket[_thunk] expression should produce a thunk. When 112 @racket[#:check-result] is specified, a run-time guard on the function's 113 result is added. The guard checks that the result is an immutable value. With 114 @racket[pure-thunk/stateless], the result guard only accepts immutable values, 115 possibly containing @tech{stateless} functions. With 116 @racket[pure-thunk/stateful], the result guard also accepts immutable values, 117 possibly containing @tech{stateful} functions.} 118 119 @deftogether[ 120 [@defform*[#:literals (: define) 121 [(define-pure/stateless (name . args) maybe-result body ...) 122 (define-pure/stateless 123 (: name . type) 124 (define (name . args) maybe-result body ...))]] 125 @defform*[#:literals (: define) 126 [(define-pure/stateful (name . args) maybe-result body ...) 127 (define-pure/stateful 128 (: name . type) 129 (define (name . args) maybe-result body ...))] 130 #:grammar 131 [(maybe-result (code:line) 132 (code:line : result-type))]]]]{ 133 134 Defines @racket[name] as a pure function. The @racket[define-pure/stateful] 135 form relies on @racket[pure/stateful], and therefore allows the function to 136 return a value containing @tech{stateful} functions. On the other hand, 137 @racket[define-pure/stateless] relies on @racket[pure/stateless], and 138 therefore only allows the return value to contain @tech{stateless} functions. 139 140 Due to the way the function is defined, a regular separate type annotation of 141 the form @racket[(: name type)] would not work (the function is first defined 142 using a temporary variable, and @racket[name] is merely a 143 @tech["rename transformer" 144 #:doc '(lib "scribblings/reference/reference.scrbl")] for that temporary 145 variable). 146 147 It is therefore possible to express such a type annotation by placing both 148 the type annotation and the definition within a @racket[define-pure/stateless] 149 or @racket[define-pure/stateful] form: 150 151 @racketblock[ 152 (define-pure/stateless 153 (: square : (→ Number Number)) 154 (define (square x) (* x x)))] 155 156 The @racket[define] identifier can either be @tr:define from 157 @racketmodname[typed/racket] or @te:define from 158 @racketmodname[type-expander].} 159 160 @(define-syntax (show-pure-ids stx) 161 (with-syntax ([(id ...) (map (λ (id) (datum->syntax #'here (syntax-e id))) 162 (sort (free-id-set->list 163 built-in-pure-functions-free-id-set) 164 symbol<? 165 #:key syntax-e))]) 166 #`(itemlist 167 (item (list (racket id))) 168 ...))) 169 170 @defthing[built-in-pure-functions-set (and/c generic-set? set-eq? set?)]{ 171 This set contains the built-in functions recognized as pure by this library. 172 173 For now only a few built-in functions are recognized as pure: 174 175 @(show-pure-ids) 176 177 Patches adding new functions to the set are welcome.} 178 179 @defthing[#:kind "for-syntax value" 180 built-in-pure-functions-free-id-set immutable-free-id-set?]{ 181 This value is provided at level 1, and contains the identifiers of the 182 functions present in @racket[built-in-pure-functions-set].} 183 184 @defproc[((immutable/stateless/c [varref Variable-Reference]) [v Any]) Boolean]{ 185 Returns a predicate which accepts only values which are immutable, possibly 186 containing @tech{stateless} functions, but not @tech{stateful} functions. 187 188 This predicate detects whether the functions contained within the value 189 @racket[v] are pure or not, based on the @racket[built-in-pure-functions-set] 190 set and a few special cases: 191 192 @itemlist[ 193 @item{The low-level functions used to build pure promises are always 194 accepted. Their valid use is guaranteed by the macros wrapping them.} 195 @item{Predicates for @racket[struct] types are always accepted} 196 @item{Field accessors for @racket[struct] types are always accepted} 197 @item{Constructors for @racket[struct] types are accepted only if 198 @racket[immutable/stateless/c] can determine that the struct type is 199 immutable.}] 200 201 There seems to be no combination of built-in functions in Racket which would 202 reliably associate a struct constructor (as a value) with its corresponding 203 struct type. Instead, @racket[immutable/stateless/c] uses a heuristic based on 204 @racket[object-name]: if @racket[struct-constructor-procedure?] returns 205 @racket[#true] for a function, and that function's @racket[object-name] is 206 @racket[st] or @racket[make-st], then @racket[st] is expected to be an 207 identifier with static struct type information. 208 209 To achieve this, it is necessary to access the call-site's namespace, which is 210 done via the @racket[varref] parameter. Simply supplying the result of 211 @racket[(#%variable-reference)] should be enough.} 212 213 @defproc[((immutable/stateful/c [varref Variable-Reference]) [v Any]) Boolean]{ 214 Returns a predicate which accepts only values which are immutable, possibly 215 containing both @tech{stateful} and @tech{stateless} functions. 216 217 This predicate needs to access the call-site's namespace, which is 218 done via the @racket[varref] parameter. Simply supplying the result of 219 @racket[(#%variable-reference)] should be enough. 220 221 See the documentation for @racket[immutable/stateless/c] for an explanation 222 of the reason for this need.} 223 224 @defform[(unsafe-pure/stateless expression)]{ 225 Indicates that the expression should be trusted as allowable within a 226 @racket[pure/stateless] or @racket[pure/stateful] block or one of their 227 derivatives. No check is performed on the expression. 228 229 The @racket[unsafe-pure/stateless] form can be used within 230 @racket[pure/stateless], @racket[pure/stateful] and their derivatives, to 231 prevent any check on a portion of code. 232 233 The expression should be a pure, stateless expression. 234 235 Note that in the current implementation, the @racket[expression] is lifted 236 (in the sense of @racket[syntax-local-lift-expression].} 237 238 @defform[(unsafe-operation/mutating expression)]{ 239 Indicates that the expression should be trusted as allowable within a 240 @racket[pure/stateful] block, or one of its derivatives. No check is performed 241 on the expression. 242 243 The @racket[expression] should not vary its outputs and effects based on 244 external state (i.e. its outputs and effects should depend only on the 245 arguments passed to it). 246 247 The @racket[expression] function may internally use mutation. It may return 248 freshly-created stateful objects (closures over freshly-created mutable 249 variables, closures over mutable arguments, and mutable data structure which 250 are freshly created or extracted from the arguments). It may mutate any 251 mutable data structure passed as an argument. 252 253 Note that in the current implementation, the @racket[expression] is lifted 254 (in the sense of @racket[syntax-local-lift-expression].} 255 256 @defform[(unsafe-declare-pure/stateless identifier)]{ 257 Declares that the given identifier should be trusted as a stateless pure 258 function. The given function is subsequently treated like the functions 259 present in @racket[built-in-pure-functions-set]. 260 261 Note that this has a global effect. For one-off exceptions, especially when 262 it's not 100% clear whether the function is always pure and stateless, prefer 263 @racket[unsafe-pure/stateless].} 264 265 @defform[(unsafe-declare-allowed-in-pure/stateful identifier)]{ 266 Declares that the given identifier should be trusted as a function that can 267 be used within @racket[pure/stateful] and its derivatives. 268 269 The @racket[identifier] function should not vary its outputs and effects 270 based on external state (i.e. its outputs and effects should depend only on 271 the arguments passed to it). 272 273 The @racket[identifier] function may internally use mutation. It may return 274 freshly-created stateful objects (closures over freshly-created mutable 275 variables, closures over mutable arguments, and mutable data structure which 276 are freshly created or extracted from the arguments). It may mutate any 277 mutable data structure passed as an argument. 278 279 Note that this has a global effect. For one-off exceptions, prefer 280 @racket[unsafe-operation/mutating].}