- Abstract Class
Typically abstract classes are used in Scala (instead of [link]traits[/link) when there is an intent to reuse the class in Java source code. An abstract class is a class which cannot be instantiated and only contains a partial implementation. It is claimed that there are some efficiencies to be gained by using abstract classes in Scala as opposed to traits.
An anamorphism is a generic function that can 'unfold' a given input. It unfolds (i.e. opens up the input) by applying a function to the given input which can then produce a [potentially] unbounded/infinite output. A typical example is the zip operation that can take a pair of lists and return a list of pairs. The opposite application of this is a catamorphism.
A catamorphism is a generalization of folds/reductions/recursively-applied-function-to-return-a-consolidated-value over a generalised set of related data types, (thus extending the concept beyond it’s application over Lists).
A closure is a first class function that is able to bind free variable enclosed within the lexical scope of the functions but not directly contained within the function. In concrete terms, this means that a closure can refer to a variable not (otherwise) named in the body of the function, but will be bound to a variable with the given name (referenced within the function) that is within the closest lexical scope to the closure in place.
A commutative operation is one where the order of the operands does not change the end result. For example, mathematical addition is a commutative operation (e.g. 1 + 2 + 3 = 6 and 3 + 2 + 1 = 6). Conversely mathematical subtraction is a noncommutative operation (e.g. 3 – 2 -1 = 0 whereas doesn’t equal 1 – 2 – 3 = -4)
- companion Object
When a singleton object shares a its name and source file with a class it is called it’s ‘companion object’. A class and its companion can access each others private members. See Standalone Object
Contravariance permits the use of supertypes in parameterized types.
Covariance permits the use of subtypes in parameterized types.
- Curry-Howard Isomorphism
The Curry-Howard isomorphism expresses the relationship between the fomalisms present in computer programs, formal logic and computational calculi. In essence, this states that computer programs and proofs can be seen as interchangeable. The generalization claimed is formally expressed as follows: a proof is a program, the formula it proves is a type for the program (sic). See wikipedia for more details.
- Dependent Types
Dependent types are types where the realization of the type created is actually dependent on the values being provided. A typical example is a Tuple, where the specific tuple type that manifests is determined by the number of tuple elements passed into the constructor. See intuitionistic type theory.
Downcasting is the name given to the casting of a type from the general to the more specific (e.g. casting an Object/AnyVal to a String). Typically this technique is used when casting of objects contained in a collection to iterate over them.
- Duck type
Duck typing enables the dynamic binding of a datatpe [at runtime] based on its’ structural compatability and the context in which it is being used. In brief, if the datatype can be seen to posses the attributes needed during execution, it should be treated as valid element in that scenario… so, if it walks, talks and acts like a duck, might as well call it a duck.. See also structural typing.
- Dynamic typing
Dynamic typing performs [the majority of/typically all of] its’ type checking operations at runtime. Advocates of this approach suggest it is an enabler generative programming as well as better supporting transitional and prototyping code (due to the removal of compiler enforced impediments). Duck typing is a key feature of a dyamically typed language, and is given providing better code reuse and looser coupling between systems. Many languages are predominantly statically or dynamically typed, but tend to actually include features from the both paradigms. See static type, duck type and halting problem.
- eager evaluation
In eager evaluation, an expression is evaluated as soon as it is bound to a variable, as opposed lazy evaluation where the expression is evaluated when the result is required.
When a generic type is instantiated the compiler removes the type information associated with the type parameters and arguments associated with class or method. This is the Java approach to resolving generics and backwards compatibility. See also raw type
- Existential types
Existential types provide a way to refer to ‘contained’ types in an abstract way. This can be seen ‘in action’ with type erasure in Java generics. In this scenario, datatypes are ‘acknowledged’ but are only handled in the abstract, as there is no actual information on the concrete aspects of the type involved. Scala supports existential types for compatibility with Java. If Java had reified types and didn’t have raw types or generic wildcards, it is unlikely they would be natively supported in Scala. See here for why Scala has existential types and here for more detail on existentials in Scala.
- Explicit types
Explicit types are a feature of languages like Java and Ada and they involve the developer having to perform type declarations explcitly (instead of the type of a member being implied from the type declaration ‘on the right’ in Java). This is often the cause of much consternation due to the required source code bloat. See Nominative types, implicit types and local type inference.
An expression is an instruction to execute something that will result in a value. If the expression has side effects it is not thought to have referential transparency.
An extractor allows a pattern to be defined for an object independently from it having to appear as a case classes. This is implemented on Scala objects by the unapply() method which takes a value and takes it apart.
As the name suggests a filter allows a data set to be pruned according to specific criteria (such as based on list element evaluations or classes named in imports)
- flow type inference
See local type inference.
GADT stands for Generalized Algebraic Data Type, and is (as the name suggests) the generic abstraction of datatypes which are constructed from other datatypes via constructor declaration. Furthermore, the constructor data is expected to be unwrapped using pattern matching. The most common algebraic data type is the List. See pattern matching distilled.
- Generalized type constraints
Generalized type constraints are classes which provide type based constraints on methods. This enables those constriained methods to provide compile-time specialisations. These classes were introduced in the Predef.scala class in Scalal 2.8, and the ‘viewable’ constraining class later deprecated in Scala v2.9. The constraints use following syntax: A =:= B to specify that type A should exactly match type B, A <:< B which specifies that A must conform to B and A <%< B (deprecated in Scala 2.9, but included for completeness) which means A must be viewable as B. See here for an excellent blog post on this.
A generator is the mechanism by which a value can be ‘generated’ during an iterative procedure. This can take the form of initialising a value with a list element, or an item from a counter, (as shown in for() comprehensions).
- Girard-Reynolds isomorphism
The Girard-Reynolds isomorphism shows that there is a direct relationship between the second-order lambda calculus and its superset the second-order predicate calculus. For example, according to the simply typed lambda calculus, the identity function for booleans and naturals would be expressed by 2 syntactically different lamdba abstractions, but under System F, this could be represented by a single parametrically polymorphic identity lambda.
- Girard-Reynolds type system
The Girard-Reynolds type system provides a generalized quantification (aka polymorphic second-order calculus) over types (such as forAll and thereExists). In effect this is the actual formalisation of the idea of parametric polymorphism. See here for an excellent video and here for a great post about this.
- Halting Problem
The halting problem states that it is logically impossible to determine whether a program will stop when provided with a given input, or will run forever. Note this is a logical a priori impossiblility (as opposed to emprically proving whether a program will complete with a given input). This was one of the first problems in the realm of undecideability. See here for more.
Hindley-Milner is both a heavily constrained/limited type system and an algorithm for inferring types based on their usage ( aka Damas-Milner). This is enacted by the compiler constructing a constraint set for the variables being referenced based on their global context in the program writ-large and usage in the given scope. See here and here for more details.
- Implicit types
Implicitly typed programs rely on the compiler determining the type assignment of values and variables, (i.e. rather than explicity declaring this ‘on-the-left’), based on inference. In Scala terminology this is called local type inference. See Hindley-Milner and System F.
- Implicit conversion
Implicit conversions make it possible to add to the capabilities of given classes by attaching additional behaviour to them. Typically this is used as part of the ‘pimp my library’ pattern which enables the extension of closed source code. If the client either: a) tries to use a method that takes a different type to the that which we are trying to use or; b) tries to call a method that isn’t declared on the type which we are trying to use; then the compiler searches the classpath for the appropriate implicit conversion to either the required type for a) or for another class which carries the method we desire and for whom an implicit conversion can be found in case b). Methods that are able to perform the desired conversion between types must be marked with the keyword ‘implicit’ and be within scope, (i.e. classpath), of the calling class to be usable in this context. See this post and this post.
- Implicit Parameters
Implicit parameters make it possible for a method to implicitly insert certain parameters that were explicitly declared on the method signature. Hence a client of the method doesn’t need to pass these parameters into the method. Instead, the params are picked up ‘implicitly’ in either of the following scenarios: the parameter is in scope where the method call is declared, and the parameter is marked with the ‘implicit’ keyword; the parameter both labeled as implicit and is a member of a companion module. See here for more details.
The term implicit has different meanings based on its context. See implicit types, implicit parameters and (most commonly) implicit conversion.
- Intuitionistic type theory
Intuitionistic type theory uses dependent types in well-typed programs to express predicate logic. This means (via Curry-Howard isomorphism) that such languages that use this form of typing can be used to represent mathematical proofs. E.g. Coq, Agda.
Invariance does not allow for the use of any types other than that which is explicitly declared for a parameterized type.
Lagom is a Swedish term that roughly translates to ‘just the right amount’ in English. However, the subtlety of the term infers that just the right amount is actually the optimal amount, and any more or less would be less optimal, (as opposed to just enough inferring ‘about adequeate’). Also see the wikipedia entry.
- The Lambda Cube
The Lambda cube provides a feature matrix for type systems, based on different calcili of different axes. For example, one such axes along which a type system can be evaluated is whether it supports polymorphism, another axes whether dependent types are supported. See here.
- lazy evaluation
In lazy evaluation, an expression is evaluated when the result of the evaluation is required, as opposed eager evaluation where evaluation occurs as soon as the expression result is bound to a variable.
- Linear types
Linear types enforce that a single element alone can reference an object at a given point time. Linear typing [therefore] makes object aliasing impossible. This is accomplished by removing the reference to an object (and putting that reference out of scope) once the field holding the object reference is used in an assignment for another element. See
- Loan pattern
The loan pattern (aka ARM in Java) is a way to ensure that a resource is ‘deterministically disposed of once it goes out of scope’ [sic]. See this link on the Scala patterns website.
- Local Type Inference
Local type inference allows the compiler to infer the type of an element without the need for a type annotation or to explicitly reference the type in the declaration. In Scala this inference only applies locally (on an per expression basis) and doesn’t envelope the context of the program writ large (as is the case with Hindley-Milner inference). The pragmatic implication of this form of type inference is that Scala’s has substituted consistency guarantees over the inference available in contextual inference system, (such as HM type inference) with correctness. See here and this post and here too !.
A loop, as opposed to an expression, is a simple iteration over a simple collection, but doesn’t necessitate returning a value. Typically iteration uses loops to support the imperative model of programming and for the side effects that can be emitted during processing.
- Nominal type
Nominal types are only comparable if their types are given the same type label at declaration creation time, (i.e. tthis is the converse to structural typing).
- Nominative Types
See Nominal types
A noncommutative operation is one where the order of the operands has an effect on the end result. For example, mathematical subtraction is a noncommutative operation (e.g. 3 – 2 -1 = 0 whereas doesn’t equal 1 – 2 – 3 = -4). Conversely, mathematical addition is a commutative operation (e.g. 1 + 2 + 3 = 6 and 3 + 2 + 1 = 6).
- Parameterized type
A parameterized type is also known as a generic. It is a type which takes another type in it’s declaration (so it is in effect a flexible type). Typical examples are Collections of ‘things’. E.g. A List of Ints, or an Array of Strings.
- Parametric polymorphism
Parametrice polymorphism allows both datatypes and functions to deal with generic types. See wikipedia for further detail.
- Partitioned Publisher
Partitioned publishers is a pattern whereby the publishers (i.e. those with write access) are partitioned in such a fashion that the data they effect is discretely segregated so that they (effectively) write in a single user mode. Idemoptency of writes may be salient in this scenario but concurrency is not a factor as there is no contention over the mutated or inserted data. e.g. blogging platforms.
- Path-dependent types
Path-dependent types involve types that are nested in other types. In Scala, there is a strong relationship between inner types and their containing type. This relationship can often be the cause of errors and confusion, but it is worth remembering that the inner types of two different concrete instances of the same abstract class or trait are not equivalent, and the actual path to the types creatyed are important. For more detail on this see more detail from O’Reilly here. Also see type projections and this post from stackoverflow.
- Pattern guard
In a matching expression, a pattern guard can act as a further filter to be applied upon finding a match.
- Pattern match
A pattern match allows for the presence of a given sequence of tokens to be detected according to some pattern. Scala supports pattern matching against case classes and extractor objects, and endorses a match-first policy.
- Phantom type
Phantom types are types whose raison d’etre is to act as constraint bounds on other datatypes during compilation. For example, a phantom type may be used to constrain whether a given datatype is usable in the construction of an specific object. Phantom types are used for compile time bookkeeping and constraining and should not be instantiated at runtime.
Polymorphism allows for a datatype to be implemented by a number of other compatible datatypes given adherence to some specific rules such as sharing a common ancestor or interface. It is the underpinning of inheritance in OO languages.
- Raw type
When the compiler erases the type information from a generic type in Java, the type that is left is called the raw type. E.g. Box
is converted to the raw type of Box after erasure. See erasure and existential type.
Recursion entails applying a function as a part of the definition of that same function. This is a frequently used technique in functional programming. See also tail recursion.
- Referential transparency
Referential transparency purports that a program will produce the same side effects and output when presented with the same input. This can readily be seen with pure functions, and such expressions are (by definition) deterministic. The antonym to this term is referential opaqueness.
- Reified types
Reified types are types that are ‘materialized’ or ‘made available’ at runtime. Java and Scala support these types in Arrays, otherwise Java implements type erasure at runtime to remove all actual type information from its’ parametric types. Scala has better support for reifying types via Manifests. See this blog post and this one too !
- Representation independence
Representation independence decouples the link between data representation and patterns that can be applied to an object, thus providing greater flexibility on creating/deconstructing objects.
REPL stands for Read-Eval-Print-Loop and is otherwise called the Scala interactive shell. The Scala REPL is started by typing scala at a command prompt, and files can be loaded into a session with the -i filename switch on startup, (so scala -i filename on the command prompt). As of 2.8 onwards, the shell featured tab autocomplete. See also Scala lang site reference and online REPL .
- Rice’s theorem
Rice’s theorem states that there is no general or effective way of determining whether a non-trivial partial function has universal applicability or not. Effectively, this is non determinism over the generality functions. This can be viewed as an abstraction of the halting problem to apply to programming languages as opposed to Turing machines. For more detail wikipedia has a reasonably concise description with examples.
- Sealed Class
A parent superclass to case classes can be marked as sealed, which means that the case classes that extend this superclass in the same source file are complete. Thus pattern matching can be exhaustive for case classes that extend a sealed base class as the set of concrete classes is finite.
- Self type
A self type allows for a type to be assumed in Scala. Typically a self type is used to direct any ‘this’ declarations in the code to a specific type (specifically a different type to that containing the self type reference). One use of self types is in the Cake Pattern in Scala. Using self type references permits (otherwise private and hidden) variables to be brought into scope in a calling class. Self types are ‘usable’ in cases where a class/object/trait and it’s contained types are closely coupled. The Scala website also features an interesting piece on self types.
- side effect
Side effects occur when an operation modifies some state or has an observable interaction with calling functions or the outside world, (such as performing I/O) in addition to producing a value.
- Sound type
Programs which are both statically and strongly typed are considered to have type soundness. This is beacuse such well-typed programs cannot cause type errors.
- Static typing
Static typing provides an early warning system for program verification via compile time type checking. Various benefits are commonly associated with static typing including: ability for the compiler to optimise for performance, provides a better source for documentation, enables better tooling and more robust static code analysis, helps with program correctness (see Rice’s theorem), enables better abstraction and modularity. Many languages are predominantly statically or dynamically typed, but tend to include features from the both paradigms. Also see dynamic typing and the halting problem.
- standalone Object
A singleton object that doesn’t share a name with a companion class and are used to capture utility methods or as application entry points. See Companion Object
- Strong type
- Structural typing
As the name suggests, structural types enable type compatibility based on the actual structure of the variable as opposed to how the variable had been explicitly declared. Essentially, this provides type safe duck typing, as disparate types can be substituted for one another with the compiler providing compile-time verification. This is the basis for the Loan Pattern, and allows for inreased code reuse and flexibility over closed source libraries. An often mentioned disadvantage is that this reuse is less explicit than with polymorphic, declaration-site, instantiation. See nominal types for an opposing means of providing type compatibility.
- surrogate Object
A surrogate object typically stands in for another object and can funnels and controls access to the underlying object. Typically the surrogate will also offer decoration to methods of the underlying object too.
- System F
See Girard-Reynolds type system.
- System F<:
System F-sub is an extension of System F with subtyping support.
- System Fω
System Fω extends System F to include a formalism of parametric polymorphism with type operator support. For example, a List is a sample type operator that can be applied to a manifest type ‘T’ to return a List of type ‘T’s. This pdf provides some useful background here.
- tail recursion
- Type projection
Type projections are a way to refer to type declarations nested in other types, typically using the ‘#’ delimeter.
- Typesafe Null
A Typesafe Null is a means by which an operation wraps its’ return value so that it will not return null. Hence such a return would not throw an NPE in any calling client, or requiring a client to obfuscate their code with liberal usage of !=null style checks. See Java 7 null handling proposals and the overview from @puredanger here
Tail recursion is when another function is called as the final action and has no further processing to perform. Currently, (due to limitations in the JVM), the Scala compiler will only optimise self tail-recursive calls (i.e. calls back to the same function that is initiating the recursion). Also, only final or private methods will be tail recursion optimised (as they cannot be overridden). Optimisation typically takes the form or inlining the call into an iteration (hence reusing the stack frame).
A trait in Scala occupies the middle ground between a Java abstract class and interface. In effect a trait contains method and variable definitions, but can also contains some implementation. Note a trait cannot be instantiated. The similarity to abstract classes, is that a classes may have multiple traits applied to them (or ‘mixed in’ to use the correct parlance). When mulitple traits are mixed in to a class, (i.e. are stacked up against the class), that have shared operations, then the trait implementations are applied with a rightmost order of precendence. This is according to the compile time process of linearization in Scala. There may be some [link]efficiency penalties in using traits[/link] as opposed to abstract classes in Scala. See abstract class.
- Variance annotation
Scala uses variance annotations to contrain, and provide specifications for, Generic/Parameterized types. The specific constraints that can be placed on types are invariance (default), covariant and contravariant. e.g. The declaration of trait Node[+T] would mean that our node declaration is covariant, and could accept any subclasses of whatever type was used in it’s instantiated type, (so a Node[AnyRef] would allow for the creation of a Node[String]). Note that these constraints are checked at compile time.
- Weak type