type.texi 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
  1. @node Static type system
  2. @section Static type system
  3. @cindex type inference
  4. @cindex static type analysis
  5. Scheme48 supports a rudimentary static type system. It is intended
  6. mainly to catch some classes of type and arity mismatch errors early,
  7. at compile-time. By default, there is only @emph{extremely} basic
  8. analysis, which is typically only good enough to catch arity errors and
  9. the really egregious type errors. The full reconstructor, which is
  10. still not very sophisticated, is enabled by specifying an optimizer
  11. pass that invokes the code usage analyzer. The only optimizer pass
  12. built-in to Scheme48, the automatic procedure integrator, named
  13. @code{auto-integrate}, does so.
  14. The type reconstructor attempts to assign the most specific type it can
  15. to program terms, signalling warnings for terms that are certain to be
  16. invalid by Scheme's dynamic semantics. Since the reconstructor is not
  17. very sophisticated, it frequently gives up and assigns very general
  18. types to many terms. Note, however, that it is very lenient in that it
  19. only assigns more general types: it will @emph{never} signal a warning
  20. because it could not reconstruct a very specific type. For example,
  21. the following program will produce no warnings:
  22. @lisp
  23. (define (foo x y) (if x (+ y 1) (car y)))@end lisp
  24. @noindent
  25. Calls to @code{foo} that are clearly invalid, such as @code{(foo #t
  26. 'a)}, could cause the type analyzer to signal warnings, but it is not
  27. sophisticated enough to determine that @code{foo}'s second argument
  28. must be either a number or a pair; it simply assigns a general value
  29. type (see below).
  30. There are some tricky cases that depend on the order by which arguments
  31. are evaluated in a combination, because that order is not specified in
  32. Scheme. In these cases, the relevant types are narrowed to the most
  33. specific ones that could not possibly cause errors at run-time for any
  34. order. For example,
  35. @lisp
  36. (lambda (x) (+ (begin (set! x '(3)) 5) (car x)))@end lisp
  37. @noindent
  38. will be assigned the type @code{(proc (:pair) :number)}, because, if
  39. the arguments are evaluated right-to-left, and @code{x} is not a pair,
  40. there will be a run-time type error.
  41. The type reconstructor presumes that all code is potentially reachable,
  42. so it may signal warnings for code that the most trivial control flow
  43. analyzer could decide unreachable. For example, it would signal a
  44. warning for @code{(if #t 3 (car 7))}. Furthermore, it does not account
  45. for continuation throws; for example, though it is a perfectly valid
  46. Scheme program, the type analyzer might signal a warning for this code:
  47. @lisp
  48. (call-with-current-continuation
  49. (lambda (k) (0 (k))))@end lisp
  50. @cindex type lattice
  51. The type system is based on a type lattice. There are several maximum
  52. or `top' elements, such as @code{:values}, @code{:syntax}, and
  53. @code{:structure}; and one minimum or `bottom' element, @code{:error}.
  54. This description of the type system makes use of the following
  55. notations: @code{@var{E} : @var{T}} means that the term @var{E} has the
  56. type, or some compatible subtype of, @var{T}; and @code{@var{T@suba{a}}
  57. @subtype{} @var{T@suba{b}}} means that @var{T@suba{a}} is a compatible
  58. subtype of @var{T@suba{b}} --- that is, any term whose static type is
  59. @var{T@suba{a}} is valid in any context that expects the type
  60. @var{T@suba{b}} ---.
  61. Note that the previous text has used the word `term,' not `expression,'
  62. because static types are assigned to not only Scheme expressions. For
  63. example, @code{cond} macro has the type @code{:syntax}. Structures in
  64. the configuration language also have static types: their interfaces.
  65. (Actually, they really have the type @code{:structure}, but this is a
  66. deficiency in the current implementation's design.) Types, in fact,
  67. have their own type: @code{:type}. Here are some examples of values,
  68. first-class or otherwise, and their types:
  69. @example
  70. cond : :syntax
  71. (values 1 'foo '(x . y))
  72. : (some-values :exact-integer :symbol :pair)
  73. :syntax : :type
  74. 3 : :exact-integer
  75. (define-structure foo (export a b) ...)
  76. foo : (export a b)@end example
  77. @cindex parametric polymorphism
  78. One notable deficiency of the type system is the absence of any sort of
  79. parametric polymorphism.
  80. @cindex join types
  81. @cindex meet types
  82. @deffn {type constructor} join type @dots{}
  83. @deffnx {type constructor} meet type @dots{}
  84. @code{Join} and @code{meet} construct the supremum and infimum elements
  85. in the type lattice of the given types. That is, for any two disjoint
  86. types @var{T@suba{a}} and @var{T@suba{b}}, let @var{T@suba{j}} be
  87. @code{(join @var{T@suba{a}} @var{T@suba{b}})} and @var{T@suba{m}} be
  88. @code{(meet @var{T@suba{a}} @var{T@suba{b}})}:
  89. @itemize
  90. @item @var{T@suba{j}} @subtype{} @var{T@suba{a}} and @var{T@suba{j}} @subtype{} @var{T@suba{b}}
  91. @item @var{T@suba{a}} @subtype{} @var{T@suba{m}} and @var{T@suba{b}} @subtype{} @var{T@suba{m}}
  92. @end itemize
  93. For example, @code{(join :pair :null)} allows either pairs or nil,
  94. @ie{} lists, and @code{(meet :integer :exact)} accepts only integers
  95. that are also exact.
  96. (More complete definitions of supremum, infimum, and other elements of
  97. lattice theory, may be found elsewhere.)
  98. @end deffn
  99. @deftp type :error
  100. This is the minimal, or `bottom,' element in the type lattice. It is
  101. the type of, for example, calls to @code{error}.
  102. @end deftp
  103. @deftp type :values
  104. @deftpx type :arguments
  105. All Scheme @emph{expressions} have the type @code{:values}. They may
  106. have more specific types as well, but all expressions' types are
  107. compatible subtypes of @code{:values}. @code{:Values} is a maximal
  108. element of the type lattice. @code{:Arguments} is synonymous with
  109. @code{:values}.
  110. @end deftp
  111. @deftp type :value
  112. Scheme expressions that have a single result have the type
  113. @code{:value}, or some compatible subtype thereof; it is itself a
  114. compatible subtype of @code{:values}.
  115. @end deftp
  116. @deffn {type constructor} some-values type @dots{}
  117. @code{Some-values} is used to denote the types of expressions that have
  118. multiple results: if @code{@var{E@sub{1}} @dots{} @var{E@sub{n}}} have
  119. the types @code{@var{T@sub{1}} @dots{} @var{T@sub{n}}}, then the Scheme
  120. expression @code{(values @var{E@sub{1}} @dots{} @var{E@sub{n}})} has
  121. the type @code{(some-values @var{T@sub{1}} @dots{} @var{T@sub{n}})}.
  122. @code{Some-values}-constructed types are compatible subtypes of
  123. @code{:values}.
  124. @code{Some-values} also accepts `optional' and `rest' types, similarly
  125. to Common Lisp's `optional' and `rest' formal parameters. The sequence
  126. of types may contain a @code{&opt} token, followed by which is any
  127. number of further types, which are considered to be optional. For
  128. example, @code{make-vector}'s domain is @code{(some-values
  129. :exact-integer &opt :value)}. There may also be a @code{&rest} token,
  130. which must follow the @code{&opt} token if there is one. Following the
  131. @code{&rest} token is one more type, which the rest of the sequents in
  132. a sequence after the required or optional sequents must satisfy. For
  133. example, @code{map}'s domain is @code{(some-values :procedure (join
  134. :pair :null) &rest (join :pair :null))}: it accepts one procedure and
  135. at least one list (pair or null) argument.
  136. @end deffn
  137. @deffn {type constructor} procedure domain codomain
  138. @deffnx {type constructor} proc (arg-type @dots{}) result-type
  139. Procedure type constructors. Procedure types are always compatible
  140. subtypes of @code{:value}. @code{Procedure} is a simple constructor
  141. from a specific domain and codomain; @var{domain} and @var{codomain}
  142. must be compatible subtypes of @code{:values}. @code{Proc} is a more
  143. convenient constructor. It is equivalent to @code{(procedure
  144. (some-values @var{arg-type} @dots{}) @var{result-type})}.
  145. @end deffn
  146. @deftp type :boolean
  147. @deftpx type :char
  148. @deftpx type :null
  149. @deftpx type :unspecific
  150. @deftpx type :pair
  151. @deftpx type :string
  152. @deftpx type :symbol
  153. @deftpx type :vector
  154. @deftpx type :procedure
  155. @deftpx type :input-port
  156. @deftpx type :output-port
  157. Types that represent standard Scheme data. These are all compatible
  158. subtypes of @code{:value}. @code{:Procedure} is the general type for
  159. all procedures; see @code{proc} and @code{procedure} for procedure
  160. types with specific domains and codomains.
  161. @end deftp
  162. @deftp type :number
  163. @deftpx type :complex
  164. @deftpx type :real
  165. @deftpx type :rational
  166. @deftpx type :integer
  167. Types of the Scheme numeric tower. @code{:integer @subtype{} :rational
  168. @subtype{} :real @subtype{} :complex @subtype{} :number}
  169. @end deftp
  170. @deftp type :exact
  171. @deftpx type :inexact
  172. @deftpx type :exact-integer
  173. @deftpx type :inexact-real
  174. @code{:Exact} and @code{:inexact} are the types of exact and inexact
  175. numbers, respectively. They are typically met with one of the types in
  176. the numeric tower above; @code{:exact-integer} and @code{:inexact-real}
  177. are two conveniences for the most common meets.
  178. @end deftp
  179. @deftp type :other
  180. @code{:Other} is for types that do not fall into any of the previous
  181. value categories. (@code{:other @subtype{} :value}) All new types
  182. introduced, for example by @embedref{Type annotations,@code{loophole}},
  183. are compatible subtypes of @code{:other}.
  184. @end deftp
  185. @deffn {type constructor} variable type
  186. This is the type of all assignable variables, where @code{@var{type}
  187. @subtype{} :value}. Assignment to variables whose types are value
  188. types, not assignable variable types, is invalid.
  189. @end deffn
  190. @deftp type :syntax
  191. @deftpx type :structure
  192. @code{:Syntax} and @code{:structure} are two other maximal elements of
  193. the type lattice, along with @code{:values}. @code{:Syntax} is the
  194. type of macros or syntax transformers. @code{:Structure} is the
  195. general type of all structures.
  196. @end deftp
  197. @subsection Types in the configuration language
  198. Scheme48's configuration language has several places in which to write
  199. types. However, due to the definitions of certain elements of the
  200. configuration language, notably the @code{export} syntax, the allowable
  201. type syntax is far more limited than the above. Only the following are
  202. provided:
  203. @deftp type :values
  204. @deftpx type :value
  205. @deftpx type :arguments
  206. @deftpx type :syntax
  207. @deftpx type :structure
  208. All of the built-in maximal elements of the type lattice are provided,
  209. as well as the simple compatible subtype @code{:values}, @code{:value}.
  210. @end deftp
  211. @deftp type :boolean
  212. @deftpx type :char
  213. @deftpx type :null
  214. @deftpx type :unspecific
  215. @deftpx type :pair
  216. @deftpx type :string
  217. @deftpx type :symbol
  218. @deftpx type :vector
  219. @deftpx type :procedure
  220. @deftpx type :input-port
  221. @deftpx type :output-port
  222. @deftpx type :number
  223. @deftpx type :complex
  224. @deftpx type :real
  225. @deftpx type :rational
  226. @deftpx type :integer
  227. @deftpx type :exact-integer
  228. These are the only value types provided in the configuration language.
  229. Note the conspicuous absence of @code{:exact}, @code{:inexact}, and
  230. @code{:inexact-real}.
  231. @end deftp
  232. @deffn {type constructor} procedure domain codomain
  233. @deffnx {type constructor} proc (arg-type @dots{}) result-type
  234. These two are the only type constructors available. Note here the
  235. conspicuous absence of @code{some-values}, so procedure types that are
  236. constructed by @code{procedure} can accept only one argument (or use
  237. the overly general @code{:values} type) & return only one result (or,
  238. again, use @code{:values} for the codomain), and procedure types that
  239. are constructed by @code{proc} are similar in the result type.
  240. @end deffn