System F Structures
System F allows recursive constructions to be embedded in a natural manner, related to that in Martin-Löf's type theory. Abstract structures (S) are created using constructors. These are functions typed as:
- .
Recursivity is manifested when itself appears within one of the types . If you have of these constructors, you can define the type of as:
For instance, the natural numbers can be defined as an inductive datatype with constructors
The System F type corresponding to this structure is . The terms of this type comprise a typed version of the Church numerals, the first few of which are:
- 0 :=
- 1 :=
- 2 :=
- 3 :=
If we reverse the order of the curried arguments (i.e., ), then the Church numeral for is a function that takes a function f as argument and returns the th power of f. That is to say, a Church numeral is a higher-order function – it takes a single-argument function f, and returns another single-argument function.
Read more about this topic: System F
Famous quotes containing the words system f, system and/or structures:
“Predatory capitalism created a complex industrial system and an advanced technology; it permitted a considerable extension of democratic practice and fostered certain liberal values, but within limits that are now being pressed and must be overcome. It is not a fit system for the mid- twentieth century.”
—Noam Chomsky (b. 1928)
“I candidly confess that I have ever looked on Cuba as the most interesting addition which could ever be made to our system of States. The control which, with Florida, this island would give us over the Gulf of Mexico, and the countries and isthmus bordering on it, as well as all those whose waters flow into it, would fill up the measure of our political well-being.”
—Thomas Jefferson (1743–1826)
“It is clear that all verbal structures with meaning are verbal imitations of that elusive psychological and physiological process known as thought, a process stumbling through emotional entanglements, sudden irrational convictions, involuntary gleams of insight, rationalized prejudices, and blocks of panic and inertia, finally to reach a completely incommunicable intuition.”
—Northrop Frye (b. 1912)