[hcoop/debian/mlton.git] / doc / guide / src / ScopeInference.adoc

ScopeInference
==============

Scope inference is an analysis/rewrite pass for the <:AST:>
<:IntermediateLanguage:>, invoked from <:Elaborate:>.

== Description ==

This pass adds free type variables to the `val` or `fun`
declaration where they are implicitly scoped.

== Implementation ==

<!ViewGitFile(mlton,master,mlton/elaborate/scope.sig)>
<!ViewGitFile(mlton,master,mlton/elaborate/scope.fun)>

== Details and Notes ==

Scope inference determines for each type variable, the declaration
where it is bound.  Scope inference is a direct implementation of the
specification given in section 4.6 of the
<:DefinitionOfStandardML: Definition>.  Recall that a free occurrence
of a type variable `'a` in a declaration `d` is _unguarded_
in `d` if `'a` is not part of a smaller declaration.  A type
variable `'a` is implicitly scoped at `d` if `'a` is
unguarded in `d` and `'a` does not occur unguarded in any
declaration containing `d`.

The first pass of scope inference walks down the tree and renames all
explicitly bound type variables in order to avoid name collisions.  It
then walks up the tree and adds to each declaration the set of
unguarded type variables occurring in that declaration.  At this
point, if declaration `d` contains an unguarded type variable
`'a` and the immediately containing declaration does not contain
`'a`, then `'a` is implicitly scoped at `d`.  The final
pass walks down the tree leaving a `'a` at the a declaration where
it is scoped and removing it from all enclosed declarations.
Commit	Line	Data
7f918cf1 CE	1	ScopeInference
	2	==============
	3
	4	Scope inference is an analysis/rewrite pass for the <:AST:>
	5	<:IntermediateLanguage:>, invoked from <:Elaborate:>.
	6
	7	== Description ==
	8
	9	This pass adds free type variables to the `val` or `fun`
	10	declaration where they are implicitly scoped.
	11
	12	== Implementation ==
	13
	14	<!ViewGitFile(mlton,master,mlton/elaborate/scope.sig)>
	15	<!ViewGitFile(mlton,master,mlton/elaborate/scope.fun)>
	16
	17	== Details and Notes ==
	18
	19	Scope inference determines for each type variable, the declaration
	20	where it is bound. Scope inference is a direct implementation of the
	21	specification given in section 4.6 of the
	22	<:DefinitionOfStandardML: Definition>. Recall that a free occurrence
	23	of a type variable `'a` in a declaration `d` is _unguarded_
	24	in `d` if `'a` is not part of a smaller declaration. A type
	25	variable `'a` is implicitly scoped at `d` if `'a` is
	26	unguarded in `d` and `'a` does not occur unguarded in any
	27	declaration containing `d`.
	28
	29	The first pass of scope inference walks down the tree and renames all
	30	explicitly bound type variables in order to avoid name collisions. It
	31	then walks up the tree and adds to each declaration the set of
	32	unguarded type variables occurring in that declaration. At this
	33	point, if declaration `d` contains an unguarded type variable
	34	`'a` and the immediately containing declaration does not contain
	35	`'a`, then `'a` is implicitly scoped at `d`. The final
	36	pass walks down the tree leaving a `'a` at the a declaration where
	37	it is scoped and removing it from all enclosed declarations.