Polymorphic recursion
Encyclopedia
In computer science
, polymorphism recursion refers to a recursive
parametrically polymorph
function where the type parameter changes with each recursive invocation made instead of staying constant. Type inference
for polymorphic recursion is equivalent to semi-unification and thefore undecidable
and requires the use of a semi-algorithm or programmer supplied type annotations.
class Stack extends Object
class ArrayStack extends Stack
class LinkedListStack extends Stack
Consider the above Stack class if Stack has a factory method or constructor capable of dynamically instantiating all of the above three classes the Stack would be called a polymorphic class.
Recursion is code that calls upon itself. Consider the (poor) implementation of fibonacci numbers below:
long fib(long x)
{
if (x < 2)
return x;
else
return fib(x - 1) + fib(x - 2);
}
Finally polymorphic recursion would be a class that recursively defined itself in a polymorphic (changing) manner. This is most easily accomplished through generics, and defining your memory picture to be different because you encapsulate different things.
Example:
class BootstrappingStack {
//Recursive polymorphic datatype
BootstrappingStack> stackOfStacks;
//Anything concrete for holding the E's we are under contract to hold
Stack StackOfElements;
}
In some strongly typed
languages, such as C++
, polymorphic recursion is difficult to implement because all data type
s are determined during compilation. Polymorphic recursion causes data types to be infinitely nested, forcing the compiler to throw an error.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, polymorphism recursion refers to a recursive
Recursion (computer science)
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
parametrically polymorph
Parametric polymorphism
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...
function where the type parameter changes with each recursive invocation made instead of staying constant. Type inference
Type inference
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
for polymorphic recursion is equivalent to semi-unification and thefore undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
and requires the use of a semi-algorithm or programmer supplied type annotations.
Examples
Example:class Stack extends Object
class ArrayStack extends Stack
class LinkedListStack extends Stack
Consider the above Stack class if Stack has a factory method or constructor capable of dynamically instantiating all of the above three classes the Stack would be called a polymorphic class.
Recursion is code that calls upon itself. Consider the (poor) implementation of fibonacci numbers below:
long fib(long x)
{
if (x < 2)
return x;
else
return fib(x - 1) + fib(x - 2);
}
Finally polymorphic recursion would be a class that recursively defined itself in a polymorphic (changing) manner. This is most easily accomplished through generics, and defining your memory picture to be different because you encapsulate different things.
Example:
class BootstrappingStack
//Recursive polymorphic datatype
BootstrappingStack
//Anything concrete for holding the E's we are under contract to hold
Stack
}
In some strongly typed
Strongly-typed programming language
In computer science and computer programming, a type system is said to feature strong typing when it specifies one or more restrictions on how operations involving values of different data types can be intermixed...
languages, such as C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, polymorphic recursion is difficult to implement because all data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s are determined during compilation. Polymorphic recursion causes data types to be infinitely nested, forcing the compiler to throw an error.
Further reading
- C. Vasconcellos, L. Figueiredo, C. Camarao (2003). "Practical Type Inference for Polymorphic Recursion: an Implementation in Haskell". Journal of Universal Computer Science.
- L. Figueiredo, C. Camarao. "Type Inference for Polymorphic Recursive Definitions: a Specification in Haskell".
External links
- Standard ML with polymorphic recursion by Hans Leiß, University of Munich