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

Answer 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.  

Answer 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.