FACTOID # 8: Bookworms: Vermont has the highest number of high school teachers per capita and third highest number of librarians per capita.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > Theory of types

At the broadest level, type theory is the branch of mathematics and logic that concerns itself with classifying entities into sets called types. In this sense, it is related to the metaphysical notion of 'type'. Modern type theory was invented partly in response to Russell's paradox, and features prominently in Russell and Whitehead's Principia Mathematica.

With the rise of powerful programmable computers, and the development of programming languages for the same, type theory has found practical application in the development of programming language type systems. Definitions of "type system" in the context of programming languages vary, but the following definition due to Benjamin C. Pierce roughly corresponds to the current consensus in the type theory community:

[A type system is a] tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.
(Types and Programming Languages, MIT Press, 2002)

In other words, a type system divides program values into sets called types (this is called a "type assignment"), and makes certain program behaviors illegal on the basis of the types that are thus assigned. For example, a type system may classify the value "hello" as a string and the value 5 as a number, and prohibit the programmer from adding "hello" to 5 based on that type assignment. In this type system, the program

 "hello" + 5 

would be illegal. Hence, any program permitted by the type system would be provably free from the erroneous behavior of adding strings and numbers.

The design and implementation of type systems is a topic nearly as broad as the topic of programming languages itself. In fact, type theory proponents commonly proclaim that the design of type systems is the very essence of programming language design: "Design the type system correctly, and the language will design itself."

Note that type theory, as described herein, refers to static typing disciplines. Programming systems and languages that employ dynamic typing do not prove a priori that a program uses values correctly; instead they raise an error at runtime, when the program attempts to perform some behavior that uses values incorrectly. Some claim that "dynamic typing" is a misnomer for this reason. In any case, the two should not be confused.

Further reading

  • Benjamin Pierce, Types and Programming Languages, MIT Press, 2002.
  • Luca Cardelli, "Type Systems," The Computer Science and Engineering Handbook, Allen B. Tucker (Ed.), chapter 103, pp. 2208-2236, CRC Press, Boca Raton, FL, 1997. (online) (http://citeseer.ist.psu.edu/cardelli97type.html)

External links

  • Abstract data type (http://www.nist.gov/dads/HTML/abstractDataType.html)
  • A summary paper on the formal basis of ADTs, relationship to category theory, and list of good references (http://www.cs.ucsd.edu/users/goguen/ps/beatcs-adj.ps.gz). Pages 3-4 appear relevant. Reference number [6] looks good, but it may not be available online.
  • Na´ve Computational Type Theory (http://www.nuprl.org/documents/Constable/NaiveTypeTheoryPreface.html) by Robert L. Constable

  Results from FactBites:
PlanetMath: Russell's theory of types (958 words)
Type theory is based on the idea that impredicative definitions are the root of all evil.
A formula for which there is an assignment of types (degrees) to the variables and constants so that it accords to the restrictions of type theory is said to be stratified.
This is version 7 of Russell's theory of types, born on 2003-08-06, modified 2004-02-16.
Russell's Paradox [Internet Encyclopedia of Philosophy] (2714 words)
This is to insist that properties fall into different types, and that the type of a property is never the same as the entities to which it applies.
To be philosophically adequate, the adoption of the theory of types for properties requires developing an account of the nature of properties such that one would be able to explain why they cannot apply to themselves.
The Theory of Types for Classes: It was mentioned earlier that Russell advocated a more comprehensive theory of types than Frege's distinction of levels, one that divided not only properties or concepts into various types, but classes as well.
  More results at FactBites »



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m