How to implement a programming language
Metaprogramming
These slides borrow heavily from Ben Wood's Fall `15 slides.
CS251 Programming Languages
Spring 2019, Lyn Turbak
Department of Computer Science Wellesley College
Metaprogramming: InterpretaAon
Program in language L
Interpreter for language L on machine M
Machine M
Metaprogramming 3
How to implement a programming language
InterpretaAon
An interpreter wriDen in the implementaAon language reads a program wriDen in the source language and evaluates it.
TranslaAon (a.k.a. compilaAon)
An translator (a.k.a. compiler) wriDen in the implementaAon language reads a program wriDen in the source language and translates it to an equivalent program in the target language.
But now we need implementaAons of: implementaAon language target language
Metaprogramming 2
Interpreters
Source Program
Data
Interpreter = virtual machine
Output
Metaprogramming 4
Metaprogramming: TranslaAon
Program in language A
A to B translator
Program in language B
Interpreter for language B on machine M
Machine M
Metaprogramming 5
Compiler
C Source Program
C Compiler
x86 Target Program
if (x == 0) { x = x + 1;
} ...
cmp (1000), $0 bne L add (1000), $1 L: ...
x86 Target Program
Data
x86 computer
Output
Thanks to Ben Wood for these and following pictures
Metaprogramming 6
Interpreters vs Compilers
Interpreters No work ahead of Lme Incremental maybe inefficient
Compilers All work ahead of Lme See whole program (or more of program) Time and resources for analysis and opLmizaLon
Metaprogramming 7
Java Compiler
Source Program
Java Compiler
Target Program
if (x == 0) { x = x + 1;
} ...
load 0 ifne L load 0 inc store 0 L: ...
(compare compiled C to compiled Java)
Metaprogramming 8
Compilers... whose output is interpreted
Source Program
Java Compiler
Target Program
Target Program
Data
Doesn't this look familiar?
Java Virtual Machine
Output
Metaprogramming 9
Interpreters... that use compilers.
Source Program
Compiler
Target Program
Data
Virtual Machine
Output
Metaprogramming 10
JIT Compilers and OpAmizaAon
Source Program
Compiler
Target Program
Data
Just In Time Compiler
Performance Monitor
Virtual Machine
? HotSpot JVM ? Jikes RVM ? SpiderMonkey ? v8 ? Transmeta ? ...
Output
Metaprogramming 11
Virtual Machine Model
High-Level Language Program
Bytecode
compiler
compile Ame
run Ame Virtual machine (interpreter)
Virtual Machine Language
JIT compiler
Ahead-of-Lme compiler
NaLve Machine Language
Metaprogramming 12
Typical Compiler
Source Program
Lexical Analyzer Syntax Analyzer Semantic Analyzer Intermediate Code Generator Code Optimizer Code Generator
Analysis Synthesis
Target Program
Metaprogramming 13
How to implement a programming language
Can describe by deriving a "proof" of the implementaLon using these inference rules:
Interpreter Rule P-in-L program L interpreter machine P machine
Translator Rule P-in-S program S-to-T translator machine P-in-T program
Metaprogramming 14
ImplementaAon DerivaAon Example
Prove how to implement a "251 web page machine" using: ? 251-web-page-in-HTML program (a web page wriDen in HTML) ? HTML-interpreter-in-C program (a web browser wriDen in C) ? C-to-x86-translator-in-x86 program (a C compiler wriDen in x86) ? x86 interpreter machine (an x86 computer)
No peaking ahead!
ImplementaAon DerivaAon Example SoluAon
We can omit some occurrences of "program" and "machine":
Metaprogramming 15
Metaprogramming 16
ImplementaAon DerivaAon Are Trees
And so we can represent them as nested structures, like nested bulleted lists:
q 251-web-page-in-HTML program o HTML-interpreter-in-C program ? C-to-x86 compiler-in-x86 program ? X86 computer
o C-to-x86 compiler machine (I) ? HTML-interpreter-in-x86 program (T) ? x86 computer q HTML interpreter machine (I) 251 web page machine (I)
Version that shows conclusions below bullets. More similar to derivaLons with horizontal lines, but harder to create and read
251 web page machine (I) q 251-web-page-in-HTML program q HTML interpreter machine (I)
? HTML-interpreter-in-x86 program (T)
o HTML-interpreter-in-C program o C-to-x86 compiler machine (I)
? C-to-x86 compiler-in-x86 program ? X86 computer ? x86 computer
Preferred "top-down" version that shows conclusions above bullets.
Metaprogramming 17
DerivaAon Exercise
How to execute the Racket factorial program given these parts?
Warning: cannot start the following way:
o factorial-in-Racket program o Racket-to-Python-translator-in-Python program o Python-interpreter-in-C program o C-to-x86-translator-in-x86 program o x86 computer (i.e., x86 interpreter machine)
factorial machine (I) q factorial-in-Racket program q Racket interpreter machine (I)
....
Why not?
Metaprogramming 18
DerivaAon Exercise: SoluAon
How to execute the Racket factorial program given these parts?
Put your soluAon here:
o factorial-in-Racket program o Racket-to-Python-translator-in-Python program o Python-interpreter-in-C program o C-to-x86-translator-in-x86 program o x86 computer (i.e., x86 interpreter machine)
Metaprogramming: Bootstrapping Puzzles
How can a Racket interpreter be wriDen in Racket? How can a Java compiler be wriDen in Java? How can gcc (a C-to-x86 compiler) be wriDen in C?
Metaprogramming 19
Metaprogramming 20
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- jpt a s imple java python translator
- hands on python tutorial uc homepages
- mobilesigntranslatorforthethailanguage
- python programmer books
- hands on python tutorial loyola university chicago
- how to implement a programming language
- real time american sign language recognition with
- 15 123 systems skills in c and unix
- dna features viewer a sequence annotations formatting and
- data visualization and rendering with blender and vtk