Languages, meta-languages, and program processors

Goal

This lecture note presents the ground notions of languages, meta-languages, and program processors.

Programming languages, programs, and data

As introduced in a previous chapter,

• a programming language is a notation to express computations;
• a program is something written according to this notation; it can be executed to perform a computation;
• a computation is some kind of processing operation over some data; and
• data are representations of information.

Here is an analogy. A natural language (Danish, for example) is a collection of words assembled into sentences. Words are composed of letters, and sentences are composed of words and punctuation marks. There is a common agreement about correct Danish words (spelling) and about correct Danish sentences (grammar). Spelling and grammar pertain to the syntax of Danish. Sentences are then communicated, either orally or in writing, from someone to someone else, to convey a meaning. Meaning pertains to the semantics of Danish. To stay within the analogy, let us only consider written communication in the rest of this paragraph. Improperly spelled words and improperly constructed sentences are misunderstood or not understood at all. Understandable sentences carry information.

T.T.T.

—Piet Hein

Cooking recipes are written in a natural language, and are examples of programs. A cook follows a recipe to make a dish by operating on ingredients using kitchen tools.

Notion of meta-language

Typically, a foreigner learns Danish using a textbook. Say that the foreigner is French. The textbook is likely to be written in French. The foreigner then discovers the Danish language through explanations written in French. For this foreigner, French is the meta-language of Danish: the language to talk about another language.

At school, a native Dane will learn the proper spelling of Danish words and the correct grammar of Danish with a textbook. This textbook is naturally written in Danish. For this Dane, Danish is the meta-language of Danish: they talk about Danish in Danish. This Dane will also learn English at school, also using a textbook. This textbook is of course written in Danish, and therefore, for this Dane, Danish will be the meta-language of English: they will talk about English in Danish.

Programs and the programming language they are written in

For short, a program that is written in, e.g., OCaml, is said to be “an OCaml program”.

Interpreters

An interpreter is a program for executing another program, i.e., a program processor.

Exercise 09

Write down the four causes of an interpreter:

• what is an interpreter used for?
• which data does it operate on?
• which operations does it carry on these data?
• which methods does it use to carry these operations?

I-diagrams

An interpreter is written in a meta-language (also known as: an implementation language). It is often depicted with an “I-diagram” (“I” for “interpreter”), where

• S-L stands for the source language (of the interpreted programs) and
• M-L stands for the meta-language:

For short,

• an interpreter for S-L programs is said to be “an S-L interpreter” (and so yes, an interpreter for S-L programs written in M-L is both an S-L interpreter and an M-L program), and also
• an interpreter for S-L programs written in M-L is occasionally said to be “an interpreter for S-L written in M-L” even though an interpreter processes programs, not the language in which these programs are written.

Terminology: When interpreters for programs written in assembly language / byte code (i.e., two forms of language more suited for machines than for humans) are implemented in hardware, they are called microprocessors. When they are implemented in software, they are called virtual machines.

Virtual machines are a topic of study in themselves.

• For example, here are two artifacts (i.e., man-made constructs):

  1. an x86 microprocessor (i.e., an interpreter for x86 programs implemented in hardware), depicted as follows:

     

  2. a program written in x86 (i.e., an x86 program), depicted as follows:

     

  We depict the execution of the x86 program by putting the two pictures on top of each other:

  

  The x86 microprocessor executes the program written in x86.

  • Note how x86 is both the source language of the x86 microprocessor and the language in which the program is written.

• For example, here are three artifacts:

  1. the same x86 microprocessor as above:

     

  2. an interpreter for OCaml programs written in x86, depicted as follows:

     

  3. a program written in OCaml, depicted as follows:

     

  We depict the execution of the OCaml program by putting the three pictures on top of each other:

  

  The x86 microprocessor executes the interpreter for OCaml programs written in x86, and this interpreter executes the OCaml program.

  • Note how OCaml is both the source language of the interpreter and the language in which the OCaml program is written.
  • Note how x86 is both the source language of the x86 microprocessor and the implementation language of the interpreter.

• For another example, here are four artifacts:

  1. the same x86 microprocessor as above:

     

  2. the same interpreter for OCaml programs written in x86 as above:

     

  3. an interpreter for PHP programs written in OCaml, depicted as follows:

     

  4. a program written in PHP, depicted as follows:

     

  We depict the execution of the PHP program by putting the four pictures on top of each other:

  

  The x86 microprocessor executes the interpreter for OCaml programs written in x86, this interpreter executes the interpreter for PHP programs written in OCaml, and this interpreter executes the PHP program.

  • Note how PHP is both the source language of the interpreter and the language in which the PHP program is written.
  • Note how OCaml is both the source language of the interpreter for OCaml programs written in x86 and the implementation language of the interpreter for PHP programs written in OCaml.
  • Note how x86 is both the source language of the x86 microprocessor and the implementation language of the interpreter for OCaml programs written in x86.

  You are now in position to appreciate the concept of tower of interpreters, i.e., of interpreters interpreting each other. A tower such as the one just above is constructed bottom up:

  1. The x86 microprocessor executes the interpreter for OCaml programs written in x86:

     

     The result is an OCaml processor with which we can execute OCaml programs. Pictorially:

     

  2. The OCaml processor executes the interpreter for PHP programs written in OCaml:

     

     The result is a PHP processor with which we can execute PHP programs. Pictorially:

     

  3. The PHP processor executes the PHP program:

     

• For one last example, imagine a hardware company that is developing a new microprocessor. Since hardware is more expensive than software, this new microprocessor (call it y86) is first implemented as a virtual machine, i.e., as an interpreter. For example:

  

  This virtual machine simulates the microprocessor.

Interlude

Alfrothul: This stacking of interpreters works also outside Computer Science.

Anton: Pray elaborate.

Alfrothul: Remember Wentworth Miller and Michael Scofield?

Anton: Yes. And yes, I see.

Alfrothul: Right. Wentworth Miller is an actor and Michael Scofield is a character that this actor plays.

Anton: This stacking could go one more level if the movie was about making a movie.

Dana: In The Matrix, the level and the meta-level communicate.

Anton: Aha, right. Neo starts in a simulation, takes a pill, and moves on into the simulator.

Alfrothul: And in Blazing Saddles, a brawl on screen moves into the recording stage and then spreads into the studios of Warner Bros. Pictures.

Halcyon: And then the main characters run away from the movie set, it’s so surreal.

The fourth wall: Yes.

Dana: You have to admire Mel Brooks there, the way two of these characters then go to a movie theater to see how their movie ends.

Mimer: Good times. Should we move on and talk about compilers?

Alfrothul: Let’s.

Compilers

A compiler is a program for translating another program from one language (the “source language”) to another (the “target language”), i.e., another program processor. Given a source program (i.e., a program written in the source language), a compiler produces a target program (i.e., a program written in the target language). Compilers preserve the meaning of the programs they translate: the source program (i.e., the input of the compiler) and the target program (i.e., the output of the compiler) mean the same in the sense that executing either does the same as executing the other.

Exercise 10

Write down the four causes of a compiler.

(Hint: check out the statement of Exercise 09.)

T-diagrams

A compiler is written in an implementation language. It is often depicted with a “T-diagram” (“T” for “translator”), where

• S-L stands for the source language,
• T-L stands for the target language (of the compiled programs), and
• I-L stands for the implementation language:

For short, a compiler from S-L to T-L written in I-L is said to be “an S-L compiler”.

Compilers are a traditional topic of study in themselves.

• For example, given (1) an x86 microprocessor, (2) a compiler from OCaml to x86 written in x86, and (3) a OCaml program, one can execute the OCaml program by (a) compiling it from OCaml to x86, resulting in a x86 program, and (b) executing this compiled program with the x86 microprocessor.

  • Here is a picture of Step (a):

    

    The x86 microprocessor executes the compiler from OCaml to x86, and this compiler translates the OCaml program to an x86 program. Note how x86 is both the source language of the x86 microprocessor and the implementation language of the compiler.

  • And here is a picture of Step (b):

    

  Executing the OCaml program and executing the x86 program do the same. For example, if the OCaml program, when given an integer, computes whether this given integer is prime, then the x86 program, when given an integer, also computes whether this given integer is prime.

• For another example, given (1) an x86 microprocessor, (2) a compiler from OCaml to x86 written in x86, (3) a compiler from PHP to OCaml written in x86 and (4) a PHP program, one can execute the PHP program by (a) compiling it from PHP to OCaml, resulting in a compiled OCaml program, (b) compiling the resulting OCaml program from OCaml to x86, resulting in a compiled x86 program, and (c) executing the resulting x86 program with the x86 microprocessor.

  • Here is a picture of Step (a):

    

  • Here is a picture of Step (b):

    

  • And here is a picture of Step (c):

    

  Executing the PHP program, executing the OCaml program, and executing the x86 program do the same.

  Note how OCaml is both the target language of the first compiler and the source language of the second compiler: the point of this example is that the output program of the first compiler is the input program of the second compiler.

  For brevity, Steps (a) and (b) are often combined as follows, pictorially:

  

Exercise 11

One is given:

• an x86 microprocessor,
• an interpreter for Python programs written in x86,
• a compiler from Python to x86 written in x86, and
• a program written in Python.

Questions:

1. Can one execute the Python program? If yes, describe how to do that.
2. Can one execute the Python program in more than one way? If yes, describe how to do that.
3. In how many ways can one execute the Python program?

Practical suggestion: draw your solution with a pencil, take a low-resolution snapshot of it, and include this snapshot in your report.

Combining interpreters and compilers

Interpreters and compilers are often combined to obtain new interpreters and new compilers.

• For example, given an interpreter for a source language L2 written in a meta-language L1, and an interpreter for the source language L3 written in the meta-language L2, one obtains an interpreter for L3 programs by interpreting the second interpreter with the first, given a L1 processor. Pictorially:

  

  The L1 processor executes the interpreter for L2 programs written in L1, and the interpreter for L2 programs written in L1 executes the interpreter for L3 programs written in L2. (Note how L2 is both the source language of the first interpreter and the meta-language of the second interpreter.)

  Externally – or again macroscopically, the resulting interpreter for L3 programs looks like it is written in L1:

  

  Internally – or again microscopically, this I-diagram contains the two I-diagrams above:

  

  This macroscopic view is a view from outside: it characterizes the extension of this interpreter, i.e., what this interpreter is doing. The microscopic view is a view from inside: it characterizes the intension of this interpreter, i.e., how this interpreter is working (namely by interpreting another interpreter).

• For example, given an interpreter for an implementation language I-L written in a meta-language M-L, and a compiler from a source language S-L to a target language T-L written in the implementation language I-L, one obtains a compiler from S-L to T-L by executing the compiler with the interpreter. Pictorially:

  

  Externally – or again macroscopically, the resulting compiler from S-L to T-L looks like it is written in M-L. Pictorially:

  

  Internally – or again microscopically, this T-diagram contains the T-diagram and the I-diagram above:

  

  This macroscopic view is a view from outside: it characterizes the extension of this compiler, i.e., what this compiler is doing. The microscopic view is a view from inside: it characterizes the intension of this compiler, i.e., how this compiler is working (namely by interpreting another compiler).

• For example, given an interpreter for Scheme programs written in C and a compiler from C to, say a language A (e.g., byte code or assembly language), one obtains an interpreter for Scheme programs written in A by compiling it. Pictorially:

  

  The input of the compiler is a program written in C, and therefore the output is a program written in A since the compiler translates programs from C to A. The input of the compiler is an interpreter for Scheme programs, and therefore the output is also an interpreter for Scheme programs since a compiler preserves the meaning of the programs it translates. Therefore since the input is an interpreter for Scheme programs written in C, the output is an interpreter for Scheme programs written in A.

Food for thought:

• How would one compile a compiler?
• What would be the result?

(Hint: see Phase 1 in Bootstrapping an ML compiler later on.)

Some vocabulary

• In practice, the terms “executing a program” and “running a program” are used interchangeably. Therefore an interpreter is often also said to be a program for running another program.

• Executing a program with an interpreter proceeds in one step, but executing a program with a compiler proceeds in two steps:

  • during the first step, the program is compiled, i.e., is translated into a compiled program;
  • during the second step, the compiled program is executed.

  What happens during the first step is said to happen at compile time, and what happens during the second step is said to happen at run time.

• To put it simplistically,

  • if a compiler is efficient, compile time is short; and
  • if a compiler generates efficient code, the subsequent run time is short.

Binding times

Mimer: So there are two “binding times” when using a compiler: compile time and run time.

Pablito: And only one when using an interpreter?

Neil Jones: Yes.

Mimer: Prof. Jones, thanks for coming by!

Dana: Could there be more than two binding times?

Neil Jones: Oh yes.

Dana: For example?

Neil Jones: Consider a program that generates another program.

Dana: A compiler, for example?

Neil Jones: Yes. Now what are the binding times when we compile this program and then run the resulting compiled program?

Dana: Well, there is compile time and there is run time.

Neil Jones: And what happens when we run the compiled program?

Dana: Ah. I see. Since this program generates another program, there is one subsequent binding time, namely when this generated program is executed.

Neil Jones: Yup.

Alfrothul: And what about a program that generates another program that generates yet another program?

Neil Jones: More binding times.

Self-interpreters and self-compilers

When an interpreter is written in (a subset of) its source language, it can interpret (a copy of) itself. Pictorially:

An interpreter that can interpret (a copy of) itself is called a self-interpreter. Self-interpreters are interesting because they provide a simple way to test the expressiveness of a programming language: how complicated is it to define this language in terms of itself? Implementing such an interpreter is no more absurd than H. L. Mencken writing The American Language in American English. In fact, getting back to the native Dane learning English at school, it is considered a progress to move from a textbook about English written in Danish to a textbook about English written in English.

When a compiler is written in (a subset of) its source language, it can compile (a copy of) itself. Pictorially:

The input of the compiler is a program written in L, and the output is a program written in A since the compiler translates programs from L to A. The input of the compiler is a compiler from L to A, and therefore the output is also a compiler from L to A since a compiler preserves the meaning of the programs it translates. Therefore since the input is a compiler from L to A written in L, the output is a compiler from L to A written in A.

A compiler that can compile (a copy of) itself is called a self-compiler. (See Bootstrapping an ML compiler later on.)

Exercise 12

One is given:

• an x86 microprocessor,
• an interpreter for Scheme programs written in C,
• a compiler from C to x86 written in x86, and
• a compiler from ML to C written in Scheme.

Can one execute a program written in ML, and if so how?

Hint: draw I- and T-diagrams, and then play with them as you would with LEGO bricks.

Solution for Exercise 12, Version 1: top down, depth first

Can we execute a program written in ML, and if so how?

Rhetorical question: Which program processor do we have for ML?

Answer: We only have one, namely

• a compiler from ML to C written in Scheme.

If we can’t execute this compiler, the overall answer is negative, so let’s look at that now.

Rhetorical question: Which program processors do we have for Scheme?

Answer: We only have one, namely

• an interpreter for Scheme programs written in C.

If we can’t execute this interpreter, the overall answer is negative, so let’s look at that now.

Rhetorical question: Which program processor do we have for C?

Answer: We only have one, namely

• a compiler from C to x86 written in x86.

If we can’t execute this compiler, the overall answer is negative, so let’s look at that now.

Rhetorical question: Which program processor do we have for x86?

Answer: We only have one, namely

• an x86 microprocessor.

So we can execute the compiler from C to x86 written in x86, using the x86 microprocessor.

So we can compile the interpreter for Scheme programs written in C, obtaining an interpreter for Scheme programs written in x86. Pictorially:

The result is an interpreter for Scheme programs written in x86.

Rhetorical question, revisited: Which program processors do we have for Scheme?

Answer: We now have two, namely

• an interpreter for Scheme programs written in C, and
• an interpreter for Scheme programs written in x86.

So we can compile a program written in ML into a program written in C, using the interpreter for Scheme programs written in x86 and the x86 microprocessor. We can then compile the resulting C program into a program written in x86, using the x86 microprocessor, and we can execute the resulting x86 program, again using the x86 microprocessor.

Pictorially:

So overall the answer is yes: we can compile a program written in ML, as depicted just above.

Solution for Exercise 12, Version 2: top down, breadth first

Can we execute a program written in ML, and if so how?

Rhetorical question: Which program processors do we have for ML?

Answer: We only have one, namely

• a compiler from ML to C written in Scheme.

Assuming we can somehow execute this compiler, the question would then reduce to the following one:

Can we execute a program written in C, and if so how?

Rhetorical question: Which program processors do we have for C?

Answer: We only have one, namely

• a compiler from C to x86 written in x86.

Assuming we can somehow execute this compiler, the question would then reduce to the following one:

Can we execute a program written in x86, and if so how?

Rhetorical question: Which program processors do we have for x86?

Answer: We only have one, namely

• an x86 microprocessor.

Therefore we can execute a program written in x86, using the x86 microprocessor.

Therefore we can execute a program written in C, using the compiler from C to x86 and then the x86 microprocessor, provided we can execute the compiler from C to x86 written in x86.

Therefore we can execute a program written in ML, provided we can execute the compiler from C to x86 written in x86 and the compiler from ML to C written in Scheme.

We can execute the compiler from C to x86 written in x86 since we have an x86 microprocessor. Pictorially:

So the problem reduces to executing the compiler from ML to C written in Scheme.

Rhetorical question: Which program processors do we have for Scheme?

Answer: We only have one, namely

• an interpreter for Scheme programs written in C.

Assuming we can somehow execute this interpreter, the question would reduce to the following one:

Can we execute a program written in C, and if so how?

We have already answered this question above: using the compiler from C to x86 written in x86 (and the x86 microprocessor to execute it).

So let us use this compiler from C to x86 to compile the interpreter written in C. Pictorially:

The result is an interpreter for Scheme programs written in x86.

We can now execute the program in ML by:

1. interpreting the compiler from ML to C written in Scheme (using the interpreter for Scheme programs written in x86 and the x86 microprocessor) and using it to compile the program written in ML to a program written in C;
2. executing the compiler from C to x86 (using the x86 microprocessor) and using it to compile the resulting program written in C to a program written in x86; and
3. executing the resulting program written in x86 (using the x86 microprocessor).

Pictorially:

Solution for Exercise 12, Version 3: bottom up

1. Since we

   • have a compiler from C to x86 written in x86 (given) and
   • have an x86 microprocessor (given),

   we can compile C programs to x86.

2. Since we

   • can compile C programs to x86 (Point a) and
   • have an x86 microprocessor (given),

   we can execute C programs.

3. Since we

   • have an interpreter for Scheme programs written in C (given) and
   • can execute C programs (Point b),

   we can execute Scheme programs.

4. Since we

   • have a compiler from ML to C written in Scheme (given) and
   • can execute Scheme programs (Point c),

   we can compile ML programs to C.

5. Since we

   • can compile ML programs to C (Point d) and
   • can execute C programs (Point b),

   we can execute ML programs.

So the answer to the question is yes: we can execute a program written in ML (Point e).

Exercise 13

One is given:

• an x86 microprocessor,
• a compiler from Java Byte Code to x86 written in Java Byte Code,
• an interpreter for Scheme programs written in Scheme,
• a compiler from Scheme to Java Byte Code written in x86, and
• a compiler from Schelog to Scheme written in x86.

Can one execute a program written in Schelog, and if so how?

Solution for Exercise 13, top down

Rhetorical question: Which program processor do we have for Schelog?

Answer: We have

• a compiler from Schelog to Scheme written in x86.

This compiler can be used because to run it, we need a program processor for x86, and we have one: the x86 microprocessor.

So let us use this compiler from Schelog to Scheme to compile the program written in Schelog. Pictorially:

So the problem reduces to processing the resulting Scheme program.

Rhetorical question: Which program processor do we have for Scheme?

Answer: We have

• an interpreter for Scheme programs written in Scheme, and
• a compiler from Scheme to Java Byte Code written in x86.

Murph: Each iteration becomes an attempt to prove its own proof.

It’s recursive. Nonsensical.

Professor Brand: Are you calling my life’s work “nonsense”?

—Interstellar

The interpreter cannot be used because to run it, we need a program processor for Scheme, and we do not have one. (This Scheme interpreter is useless because to run it, we need a Scheme interpreter. But to run this Scheme interpreter, we need a Scheme interpreter. And to run this Scheme interpreter, we need a Scheme interpreter – a circular argument. So all in all, we cannot interpret any Scheme program.)

The compiler can be used because to run it, we need a program processor for x86, and we have one: the x86 microprocessor.

So let us use this compiler from Scheme to Java Byte Code to compile the resulting program written in Scheme. Pictorially:

So the problem reduces to processing the resulting byte-code program.

Rhetorical question: Which program processor do we have for Java Byte Code?

Answer: we have

• a compiler from Java Byte Code to x86 written in Java Byte Code.

Loki the Mischievous: But we do have one:

the compiler from Java Byte Code to x86 written in Java Byte Code.

(Boy, I love those circular arguments.)

Murph: Why? They are nonsensical.

This compiler cannot be used because to run it, we need a program processor for Java Byte Code, and we do not have one.

Therefore, we cannot process the resulting byte-code program.

So all in all, we cannot execute a program written in Schelog.

Solution for Exercise 13, bottom up

1. Since we

   • have a compiler from Schelog to Scheme written in x86 (given) and
   • have an x86 microprocessor (given),

   we can compile Schelog programs to Scheme. Furthermore that is the only thing we can do with Schelog programs.

2. Since we

   • have a compiler from Scheme to Java Byte Code written in x86 (given) and
   • have an x86 microprocessor (given),

   we can compile Scheme programs to Java Byte Code. Furthermore that is the only thing we can do with Scheme programs: the Scheme self-interpreter is useless to process programs written in Scheme.

3. Since we

   • can compile Schelog programs to Scheme (Point a) and
   • can compile Scheme programs to Java Byte Code (Point b)

   we can compile Schelog programs to Java Byte Code.

4. However, since we

   • cannot interpret Java Byte Code programs and
   • cannot compile Java Byte Code programs either,

   we cannot process the Java Byte Code programs.

So the answer to the question is no: we cannot execute a program written in Schelog (Point d).

Exercise 14

This exercise is a followup to Exercise 13. Under the same conditions:

1. Can one execute a program written in Scheme?
2. Can one execute a program written in Java Byte Code?
3. Can one execute a program written in Java?
4. Can one execute a program written in JavaScript?

Motivate your answers.

Partial solution for Exercise 14

1. No.
2. No.
3. No.
4. No.

Exercise 15

One is given:

• an ARM microprocessor,
• an interpreter for x86 programs written in ARM,
• an interpreter for Perl programs written in x86,
• a compiler from ML to C written in Perl,
• a compiler from C to x86 written in ARM, and
• a compiler from Prolog to ARM written in ML.

Can one execute a program written in Prolog, and if so how?

Practical suggestion: draw your solution with a pencil, take a low-resolution snapshot of it, and include this snapshot in your report.

Exercise 16

This exercise revisits Exercise 15, replacing the interpreter for x86 programs written in ARM with a compiler from x86 to ARM written in ARM.

Can one execute a program written in Prolog, and if so how?

Exercise 17

This exercise revisits Exercise 15, replacing the interpreter for x86 programs written in ARM with a compiler from x86 to ARM written in x86.

Can one execute a program written in Prolog, and if so how?

After hours

Halcyon (candidly): Does denotational semantics define an interpreter or a compiler?

{David Schmidt && Guy Steele} (simultaneously): A {compiler to lambda terms && lambda interpreter} of course.

A second of eternity passes, and the universe resumes its course.

Version

Added the “After hours” section [25 Mar 2023]

Refined the explanation about interpreting an interpreter and interpreting a compiler, following a question by Ryan Ye Chenhao in class [22 Jan 2023]

Created [10 Jan 2023]