Metalinguistic abstraction

The establishment of new languages to describe engineering systems in different and more application-specific ways is a powerful strategy to handle complexity. In computer programming, we can even implement each new language by building evaluators/interpreters, computer programs that translate instructions in the input language into the actions specified by the instructions.

"It is no exaggeration to regard this as the most fundamental idea in programming:

The evaluator, which determines the meaning of expressions in a
programming language, is just another program.

To appreciate this point is to change our images of ourselves as programmers. We come to see ourselves as designers of languages, rather than only users of languages designed by others.”

Excerpt From
Structure and Interpretation of Computer Programs
Harold Abelson and Gerald Jay Sussman with Julie Sussman

Construction

Generally, an evaluator is built as an eval-apply loop, where eval evaluates and simplifies expressions into elementary forms, and apply actually executes the commands. Primitive operations are defined, and kept in memory as part of an environment structure. The elementary forms are always reduced into executable commands in terms of the primitives or of certain special forms such as 'define, 'if, 'begin. These are also typically installed into the syntax as procedures to evaluate such expressions.

Finally, more sophisticated derived expressions can also be added to the syntax as syntactical transformations without directly changing the evaluator. These user-defined transformations are called macros.

Applications

Metacircular evaluation
Lisp can even be implemented in Lisp itself. An evaluator written in the same language it evaluates is called a metacircular evaluator. In other words, a metacircular evaluator is a description (expressed in the language itself) of how expressions in a given language are evaluated. This idea is very powerful.

Language execution strategies
You can, for example, even implement a lazy/normal-order Scheme in the typically applicative-order Scheme, by changing the procedure evaluator to convert its arguments automatically into thunks, that are evaluated later when needed. A normal-order implementation provides, among other neat features, a natural implementation of lazy data structures such as streams with seamless integration with the non-lazy equivalents (lists).

Non-deterministic computing
An even more profound change we could introduce is non-deterministic computing by adding automatic search/backtracking. By introducing automatic search, we can then specify conditions for what we want (declarative statements), and allow the search to find the solution that satisfy the conditions. This is in contrast to the usual imperative programming style of describing precisely the computations that need to be carried out. Nondeterministic programs enable simple programs for solving logic puzzles or for parsing natural language, and provide one or more possible solutions that satisfy certain relational constraints.

Logic programming
Going further with this idea of relational programming, another sophisticated system we could set up is a logic programming language. This can be seen as a constraint-satisfying system combined with pattern-matching mechanisms. The basic idea is similar to the above non-deterministic programs, except now we expect to represent all possible solutions simultaneously rather than picking any one possible solution. Furthermore, it would explicitly support very general computation that can proceed in several directions and not just one forward computation. Such a language is particularly useful for retrieving information from data bases by formulating logical queries.

Compilation
In general, compilers can refer to programs that translate code between any two pair of programming languages, meaning every application described above is, technically speaking, a compiler. However, the term is typically used to refer to programs that translate code from high-level languages to a low-level executable language (eg. machine code). One could, for instance, implement a general low-level register machine that implements computations by moving values around containers (registers).

Optimizations

One could separate the syntax analysis from the actual execution of the code, sort of like compilation. This can help to avoid repeated evaluation of the syntax, and instead just execute one long expression all at once. This is also the easiest approach to extend for non-deterministic evaluation. Backtracking is implemented by passing around (and modifying as needed) success procedures to evaluate on successful propagation and failure procedures that handle alternative branches.

In normal-order implementations, thunks can be memoized, so that repeated evaluations are fast.