What do "reify" and "reification" mean in the context of (functional?) programming?

Question

I read this term a lot in blogs about haskell and functional programming (specially in sigfpe's blog) but I don't have a clue about what it means. I get away with not knowing it most of the times, but I probably would have understood the texts a lot better if I knew. Google didn't help me. I get lost in the technical stuff.

Also the non-technical meaning of the world ("turning the abstract concrete") doesn't help me understand what it practically means to reify something in code.

I'm kinda slow with computer science concepts, so practical examples with code would be nice. :P

Solution 1

So I read up on this, and it is pretty much what it means: taking an abstract concept and making it concrete. Or, there is a proxy that represents the abstract concept. For example, in Lisp, the concept of procedure abstraction and application is reified when you use lambdas.

Reification by itself is a broad concept and not just applicable to functional programming-languages.

In Java for example, there are types that are available at runtime. These are reifiable types. Meaning, there exists a concrete representation of the abstract concept of the type, during runtime. In contrast, there are non-reifiable types. This is especially evident during the use of generics in Java. In Java, generics are subject to type erasure, and so generic type-information is not available during runtime (unless the parameterized type uses unbounded wildcards).

Another example is when you try to model a concept. For example, assume that you have a Group class and a User class. Now there are certain abstract concepts that describe the relationship between the two. For example, the abstract concept of a User being the member of a Group. To make this relationship concrete, you would write a method called isMemberOf that says whether a User is a member of a Group. So what you've done here is that you have reified (made real/explicit/concrete) the abstract concept of group membership.

Another good example is a database where you have parent-child relationships between objects. You can describe this relationship in the abstract concept of a tree. Now suppose you have a function/method that takes this data from the database and constructs an actual Tree object. What you've now done is reified the abstract concept of the parent-child tree-like relationship into an actual Tree object.

Coming back to functional languages in general, perhaps the best example of reification is the creation of the Lisp programming language itself. Lisp was a completely abstract and theoretical construct (basically just a mathematical notation for computer languages). It remained that way until Lisp's eval function was actually implemented by Steve Russel on an IBM 704:

According to what reported by Paul Graham in Hackers & Painters, p. 185, McCarthy said: "Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the eval in my paper into IBM 704 machine code, fixing bug , and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..."

So Lisp was reified from an abstract concept, into an actual programming language.  

Solution 2

Reification

Reification is a form of instantiation. When you reify a concept, you take something abstract and make it concrete, just like the dictionary definition you provided.

You might choose to reify a type as a term inhabiting some abstract syntax tree of possible types.

You might reify a design pattern by coming up with a general purpose implementation of it for some language. For instance, something like

template<typename T> class Singleton {
    public:
        static T& Instance() {
            static T me;
            return me;
        }

    protected:
       virtual ~Singleton() {};
       Singleton() {};
}

reifies the singleton design pattern as a template in C++.

You can reify Hoare's idea of quicksort into an implementation in the programming language of your choice. In this vein, I spend a lot of time reifying concepts from category theory into Haskell code.

You can reify a language as an interpreter for that language. Larry Wall's idea of Perl the language is reified as the perl interpreter.

The data-reify and vacuum packages reify terms as graphs representing how it is structured in memory with sharing.

Reflection

The flip side of reification is reflection, which takes something concrete, and generates an abstraction, usually by forgetting some details. Perhaps you want to do this because the abstraction is simpler, or somehow captures the essence of what you are talking about.

Type-system reflection in Java, C#, etc. takes a concrete class in a programming language, and provides you with the abstract structure a class, giving you access to the list of what members your classes provide. Here we are taking the concrete notion of a type, and generating an abstract term out of it that describes its structure, while discarding any particular values.

Like how you can reify a programming language into an implementation, you may some times go in the opposite direction. Though this is generally considered a bad idea, you might take an implementation and try to reflect a language specification from the desirable properties of its behavior. TeX was implemented first by Knuth, sans specification. Any specification of TeX has been reflected from Knuth's implementation.

(More formally if you view reflection as a forgetful functor that takes you from a concrete domain to an abstract domain, then reification is, ideally, left adjoint to reflection.)

The reflection package I maintain provides a reify method that takes a term and yields a type that represents it, then a reflect method that lets you generate a new term. Here the 'concrete' domain is the type system, and the abstract domain are terms.

Solution 3

From the Haskell Wiki:

To "reify" something is to take something that is abstract and regard it as material. A classic example is the way that the ancients took abstract concepts (e.g. "victory") and turned them into deities (e.g. Nike, the Greek goddess of victory).

A reified type is a value that represents a type. Using reified types instead of real types means that you can do any manipulations with them that you can do with values.

Solution 4

One use I can think of (I'm sure there are others!) is turning a class into a dictionary. Let's take the Eq class (forgetting about the /= operator for the moment):

class Eq a where
    (==) :: a -> a -> Bool

If we reify this class, it becomes:

data EqDict a = EqDict (a -> a -> Bool)

which can be constructed, inspected and so on. Also noteworthy is that you can have only one Eq instance per type, but multiple EqDict values. But the automatic construction of instances (e.g. getting equality for lists when you have it for elements) doesn't work; you'll have to construct the EqDict [a] value yourself.

The reifying process is as simple as this (for this case):

reify :: Eq a => EqDict a
reify = EqDict (==)

A function using the Eq class could transform something like this:

-- silly example, doesn't really do anything
findMatches :: Eq a => a -> [a] -> [a]
findMatches x ys = [ y | y <- ys, x == y ]

-- version using EqDict
findMatchesDict :: EqDict a -> a -> [a] -> [a]
findMatchesDict (EqDict f) x ys = [ y | y <- ys, f x y ]

If you unwrap the EqDict and just pass an a -> a -> Bool, you're getting the ..By functions, like Data.List.nubBy and friends - a similar trick for Ord leads to Data.List.sortBy.

Solution 5

Even just in the context of Haskell the term is used very broadly. Andy Gill's reify package allows you to take recursive structures and turn them into explicit graphs. Sigpfe's post on continuations describes reifying the notion of "the rest of the computation" into a value you can pass around. Template Haskell has a reify function (executed, along with TH code in general, at compile time) that when given the name of a Haskell value returns available information on it (where declared, type, etc.).

What do all these cases have in common? They're talking about taking something which we can reason about and know, but which we can't directly programmatically manipulate, and turning it into an actual first class value that we can name and pass around just like any other. And that's generally the intent that people want to convey when they use the word.

View more solutions

Comments

[CMCDragonkai]

It seems that reification exists in a continuum depending on the situation. While the abstract lisp was reified into a programming language, a programming language itself is a pretty abstract concept form communicating computation, which has to be further reified into machine code and finally into 1s an 0s and then finally into electrical signals... etc etc. Thus reification is just the opposite (dual) of abstraction.