Chapter 17

Reflective

17.1 Constraints

• The program has access to information about itself, i.e. introspection.
• The program can modify itself – adding more abstractions, variables, etc. at runtime.

17.2 A Program in this Style

  1 #!/usr/bin/env python
  2 import sys, re, operator, string, os
  3
  4 #
  5 # Two down-to-earth things
  6 #
  7 stops = set(open("../stop_words.txt").read().split(",") + list(
  string.ascii_lowercase))
  8
  9 def frequencies_imp(word_list):
 10 word_freqs = {}
 11 for w in word_list:
 12    if w in word_freqs:
 13        word_freqs[w] += 1
 14    else:
 15        word_freqs[w] = 1
 16 return word_freqs
 17
 18 #
 19 # Let's write our functions as strings.
 20 #
 21 if len(sys.argv)> 1:
 22 extract_words_func = "lambda name : [x.lower() for x in re.
      split('[ˆa-zA-Z]+', open(name).read()) if len(x)> 0 and x
      .lower() not in stops]"
 23 frequencies_func = "lambda wl : frequencies_imp(wl)"
 24 sort_func = "lambda word_freq: sorted(word_freq.iteritems(),
      key=operator.itemgetter(1), reverse=True)"
 25 filename = sys.argv[1]
 26 else:
 27 extract_words_func = "lambda x: []"
 28 frequencies_func = "lambda x: []"
 29 sort_func = "lambda x: []"
 30 filename = os.path.basename(__file__)
 31 #
 32 # So far, this program isn't much about term-frequency. It's about
 33 # a bunch of strings that look like functions.
 34 # Let's add our functions to the "base" program, dynamically.
 35 #
 36 exec('extract_words = ' + extract_words_func)
 37 exec('frequencies = ' + frequencies_func)
 38 exec('sort = ' + sort_func)
 39
 40 #
 41 # The main function. This would work just fine:
 42 # word_freqs = sort(frequencies(extract_words(filename)))
 43 #
 44 word_freqs = locals()['sort'](locals()['frequencies'](locals()['
  extract_words'](filename)))
 45
 46 for (w, c) in word_freqs[0:25]:
 47 print w, ' - ', c

17.3 Commentary

THE SECOND AND FINAL STAGE towards computational reflection requires that the programs be able to modify themselves. The ability for a program to examine and modify itself is called reflection. This is an even more powerful proposition than introspection and, as such, of all the languages that support introspection, only a small subset of them support full reflection. Ruby is an example of a language supporting full reflection; Python and JavaScript support it with restrictions; Java and C# support only a small set of reflective operations.

The example program exercises some of Python's reflection facilities. The program starts by reading the stop words file in the normal way (line #8), followed by the definition of a normal function for counting word occurrences that would be too awkward to implement reflectively in Python (lines #7–16).

Next, the main program functions are defined (lines #21–30). But rather than defining them using normal function definitions, we define them at the meta-level: at that level, we have anonymous functions expressed as strings. These are lazy (unevaluated) pieces of program, as lazy as it gets: unprocessed strings whose contents happens to be Python code.

More importantly, the contents of these stringified functions depend on whether the user has provided an input file as argument to the program or not. If there is an input argument, the functions do something useful (lines #21–24); if there isn't, the functions don't do anything, simply returning the empty list (lines #26–29).

Let's look into the three functions defined in lines #22–24:

• In line #22, we have the meta-level definition of a function that extracts words from a file. The file name is given as its only argument, name.
• In line #23, we have the meta-level definition of a function that counts word occurrences given a list of words. In this case, it simply calls the base-level function that we have defined in lines #10–17.
• In line #24, we have the meta-level definition of a function that sorts a dictionary of word frequencies.

At this point of the program, all that exists in the program is: (1) the stops variable that has been defined in line #7; (2) the frequencies_imp function that has been defined in lines #9–16; (3) the three variables extract_words_func, frequencies_func and sort_func, which hold on to strings – those strings are different depending on whether there was an input argument or not.

The next three lines (#36–38) are the part of the program that effectively makes the program change itself. exec is a Python statement that supports dynamic execution of Python code.1 Whatever is given as argument (a string) is assumed to be Python code. In this case we are giving it assignment statements in the form a = b, where a is a name (extract_words, frequencies and sort), and b is the variable bound to a stringified function defined in lines #21–30. So, for example, the complete statement in line #37 is either

exec('frequencies = lambda wl : frequencies_imp(wl)')

or

exec('frequencies = lambda x : []')

depending on whether there is an input argument given to the program.

exec takes its argument, parses the code, eventually raising exceptions if there are syntax errors, and executes it. After line #38 is executed, the program will contain 3 additional function variables whose values depend on the existence of the input argument.

Finally, line #46 calls those functions. As stated in the comment in lines #41–44, this is a somewhat contrived form of function calling; it is done only to illustrate the lookup of functions via the local symbol table, as explained in the previous chapter.

At this point, the reader should be puzzled about the definition of functions as strings in lines #21–30, followed by their runtime loading via exec in lines #36–38. After all, we could do this instead:

  1 if len(sys.argv)> 1:
  2 extract_words = lambda name : [x.lower() for x in re.split('[ˆ
      a-zA-Z]+', open(name).read()) if len(x)> 0 and x.lower()
      not in stops]
  3 frequencies = lambda word_list : frequencies_imp(word_list)
  4 sort = lambda word_freq: sorted(word_freq.iteritems(), key=
      operator.itemgetter(1), reverse=True)
  5 filename = sys.argv[1]
  6 else:
  7 extract_words = lambda x: []
  8 frequencies = lambda x: []
  9 sort = lambda x: []
 10 filename = os.path.basename(__file__)

Python being a dynamic language with higher-order functions, it supports dynamic definition of functions, as illustrated above. This would achieve the goal of having different function definitions depending on the existence of the input argument, while avoiding reflection (exec and friends) altogether.

17.4 This Style in Systems Design

Indeed, the example program is a bit artificial and begs the question: when is reflection needed?

In general, reflection is needed when the ways by which programs will be modified cannot be predicted at design time. Consider, for example, the case in which the concrete implementation of the extract_words function in the example would be given by an external file provided by the user. In that case, the designer of the example program would not be able to define the function a priori, and the only solution to support such a situation would be to treat the function as string and load it at runtime via reflection. Our example program does not account for that situation, hence the use of reflection here is questionable. In the next two chapters we will see two examples of reflection being used for very good purposes that could not be supported without it.

17.5 Historical Notes

Reflection was studied in philosophy and formalized in logic long before being brought into programming. Computational reflection emerged in the 1970s within the LISP world. Its emergence within the LISP community was a natural consequence of early work in artificial intelligence, which, for the first few years, was coupled with work in LISP. At the time, it was assumed that any system that would become intelligent would need to gain awareness of itself – hence the effort in formalizing what such awareness might look like within programming models. Those ideas influenced the design of Smalltalk in the 1980s, which, from early on, supported reflection. Smalltalk went on to influence all OOP languages, so reflection concepts were brought to OOP languages early on. During the 1990s, as the work in artificial intelligence took new directions away from LISP, the LISP community continued the work on reflection; that work's pinnacle was the MetaObject Protocol (MOP) in the Common LISP Object System (CLOS). The software engineering community took notice, and throughout the 1990s there was considerable amount of work in understanding reflection and its practical benefits. It was clear that the ability to deal with unpredictable changes was quite useful, but dangerous at the same time, and some sort of balance via proper APIs would need to be defined. These ideas found their way to all major programming languages designed since the 1990s.

17.6 Further Reading

Demers, F.-N. and Malenfant, J. (1995). Reflection in logic, functional and object-oriented programming: a short comparative study. IJCAI'95 Workshop on Reflection and Metalevel Architectures and Their Applications in AI.
Synopsis: A nice retrospective overview of computational reflection in various languages.

Kiczales, G., des Riviere, J. and Bobrow, D. (1991). The Art of the Metaobject Protocol. MIT Press. 345 pages.
Synopsis: The Common LISP Object System included powerful reflective and metaprogramming facilities. This book explains how to make objects and their metaobjects work together in CLOS.

Maes, P. (1987). Concepts and Experiments in Computational Reflection. Object-Oriented Programming Systems, Languages and Applications (OOPSLA'87).
Synopsis: Patti Maes brought Brian Smith's ideas to object-oriented languages.

Smith, B. (1984). Reflection and Semantics in LISP. ACM SIGPLAN Symposium on Principles of Programming Languages (POPL'84).
Synopsis: Brian Smith was the first one to formulate computational reflection. He did it in the context of LISP. This is the original paper.

17.7 Glossary

Computational reflection: The ability for programs to access information about themselves and modify themselves.

eval: A function, or statement, provided by several programming languages that evaluates a quoted value (e.g. a string) assumed to be the representation of a program. eval is one of the two foundational pieces of meta-circular interpreters underlying many programming languages, the other one being apply. Any language that exposes eval to programmers is capable of supporting reflection. However, eval is too powerful and often considered harmful. Work on computational reflection focused on how to tame eval.

17.8 Exercises

17.1 Another language. Implement the example program in another language, but preserve the style.

17.2 From a file. Modify the example program so that the implementation of extract_words is given by a file. The command line interface should be:

$ python tf-16-1.py ../pride-and-prejudice.txt ext1.py

Provide at least two alternative implementations of that function (i.e. two files) that make the program work correctly.

17.3 More reflection. The example program doesn't use reflection for reading the stop words (line #7) and counting the word occurrences (lines #9–16). Modify the program so that it also uses reflection to do those tasks. If you can't do it, explain what the obstacles are.

17.4 A different task. Write one of the tasks proposed in the Prologue using this style.

1Other languages (e.g. Scheme, JavaScript) provide a similar facility through eval.