Subject Reduction
   HOME
*





Subject Reduction
In type theory, a type system has the property of subject reduction (also subject evaluation, type preservation or simply preservation) if evaluation of expressions does not cause their type to change. Formally, if Γ ⊢ ''e''1 : ''τ'' and ''e''1 → ''e''2 then Γ ⊢ ''e''2 : ''τ''. Intuitively, this means one would not like to write a expression, in say Haskell, of type Int, and have it evaluate to a value ''v'', only to find out that ''v'' is a string. Together with progress, it is an important meta-theoretical property for establishing type soundness In computer science, type safety and type soundness are the extent to which a programming language discourages or prevents type errors. Type safety is sometimes alternatively considered to be a property of facilities of a computer language; that is ... of a type system. The opposite property, if Γ ⊢ ''e''2 : ''τ'' and ''e''1 → ''e''2 then Γ ⊢ ''e''1 : ''τ'', is called subject expansion. It often does not hold as ev ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Type Theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of mathematics. Two influential type theories that were proposed as foundations are Alonzo Church's typed λ-calculus and Per Martin-Löf's intuitionistic type theory. Most computerized proof-writing systems use a type theory for their foundation. A common one is Thierry Coquand's Calculus of Inductive Constructions. History Type theory was created to avoid a paradox in a mathematical foundation based on naive set theory and formal logic. Russell's paradox, which was discovered by Bertrand Russell, existed because a set could be defined using "all possible sets", which included itself. Between 1902 and 1908, Bertrand Russell proposed various "theories of type" to fix the problem. By 1908 Russell arrived at a "ramified" theory ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Evaluation (computer Science)
In some programming languages, eval , short for the English evaluate, is a function which evaluates a string as though it were an expression in the language, and returns a result; in others, it executes multiple lines of code as though they had been included instead of the line including the eval. The input to eval is not necessarily a string; it may be structured representation of code, such as an abstract syntax tree (like Lisp forms), or of special type such as code (as in Python). The analog for a statement is exec, which executes a string (or code in other format) as if it were a statement; in some languages, such as Python, both are present, while in other languages only one of either eval or exec is. Eval and apply are instances of meta-circular evaluators, interpreters of a language that can be invoked within the language itself. Security risks Using eval with data from an untrusted source may introduce security vulnerabilities. For instance, assuming that the get_data ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Expression (computer Science)
In computer science, an expression is a syntactic entity in a programming language that may be evaluated to determine its value. It is a combination of one or more constants, variables, functions, and operators that the programming language interprets (according to its particular rules of precedence and of association) and computes to produce ("to return", in a stateful environment) another value. This process, for mathematical expressions, is called ''evaluation''. In simple settings, the resulting value is usually one of various primitive types, such as numerical, string, boolean, complex data type or other types. Expression is often contrasted with statement—a syntactic entity that has no value (an instruction). Examples For example, 2 + 3 is both an arithmetic and programming expression, which evaluates to 5. A variable is an expression because it denotes a value in memory, so y + 6 is also an expression. An example of a relational expression is 4 ≠ 4, which eval ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Type (computer Science)
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most programming languages support basic data types of integer numbers (of varying sizes), floating-point numbers (which approximate real numbers), characters and Booleans. A data type constrains the possible values that an expression, such as a variable or a function, might take. This data type defines the operations that can be done on the data, the meaning of the data, and the way values of that type can be stored. Concept A data type is a collection or grouping of data values. Such a grouping may be defined for many reasons: similarity, convenience, or to focus the attention. It is frequently a matter of good organization that aids the understanding of complex definitions. Almost all programming languages explicitly include the notion of data ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Haskell (programming Language)
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming language features such as type classes, which enable type-safe operator overloading, and monadic IO. Haskell's main implementation is the Glasgow Haskell Compiler (GHC). It is named after logician Haskell Curry. Haskell's semantics are historically based on those of the Miranda programming language, which served to focus the efforts of the initial Haskell working group. The last formal specification of the language was made in July 2010, while the development of GHC continues to expand Haskell via language extensions. Haskell is used in academia and industry. , Haskell was the 28th most popular programming language by Google searches for tutorials, and made up less than 1% of active users on the GitHub source code repository. History ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Progress (type Theory)
Progress is the movement towards a refined, improved, or otherwise desired state. In the context of progressivism, it refers to the proposition that advancements in technology, science, and social organization have resulted, and by extension will continue to result, in an improved human condition; the latter may happen as a result of direct human action, as in social enterprise or through activism, or as a natural part of sociocultural evolution. The concept of progress was introduced in the early-19th-century social theories, especially social evolution as described by Auguste Comte and Herbert Spencer. It was present in the Enlightenment's philosophies of history. As a goal, social progress has been advocated by varying realms of political ideologies with different theories on how it is to be achieved. Measuring progress Specific indicators for measuring progress can range from economic data, technical innovations, change in the political or legal system, and questions bear ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Type Soundness
In computer science, type safety and type soundness are the extent to which a programming language discourages or prevents type errors. Type safety is sometimes alternatively considered to be a property of facilities of a computer language; that is, some facilities are type-safe and their usage will not result in type errors, while other facilities in the same language may be type-unsafe and a program using them may encounter type errors. The behaviors classified as type errors by a given programming language are usually those that result from attempts to perform operations on values that are not of the appropriate data type, e.g., adding a string to an integer when there's no definition on how to handle this case. This classification is partly based on opinion. Type enforcement can be static, catching potential errors at compile time, or dynamic, associating type information with values at run-time and consulting them as needed to detect imminent errors, or a combination of both. ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Information And Computation
''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , the current editor-in-chief is David Peleg. The journal publishes 12 issues a year. History ''Information and Computation'' was founded as ''Information and Control'' in 1957 at the initiative of Leon Brillouin and under the editorship of Leon Brillouin, Colin Cherry and Peter Elias. Murray Eden joined as editor in 1962 and became sole editor-in-chief in 1967. He was succeeded by Albert R. Meyer in 1981, under whose editorship the journal was rebranded ''Information and Computation'' in 1987 in response to the shifted focus of the journal towards theory of computation and away from control theory. In 2020, Albert Mayer was succeeded by David Peleg as editor-in-chief of the journal. Indexing All articles from the ''Information and Comput ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]