Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Meta-circular evaluator
Résumé
In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp.
A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.
History of compiler construction
The dissertation of Corrado Böhm
describes the design of a self-hosting compiler.
Due to the difficulty of compiling higher-order functions, many languages were instead defined via interpreters, most prominently Lisp. The term itself was coined by John C. Reynolds, and popularized through its use in the book Structure and Interpretation of Computer Programs.
A self-interpreter is a meta-circular interpreter where the host language is also the language being interpreted. A self-interpreter displays a universal function for the language in question, and can be helpful in learning certain aspects of the language. A self-interpreter will provide a circular, vacuous definition of most language constructs and thus provides little insight into the interpreted language's semantics, for example evaluation strategy. Addressing these issues produces the more general notion of a "definitional interpreter".
This part is based on Section 3.2.4 of Danvy's thesis.
Here is the core of a self-evaluator for the
calculus. The abstract syntax of the calculus is
implemented as follows in OCaml, representing variables with their
de Bruijn index, i.e., with their lexical offset
(starting from 0):
type term = IND of int (* de Bruijn index *)
| ABS of term
| APP of term * term
The evaluator uses an environment:
type value = FUN of (value -> value)
let rec eval (t : term) (e : value list) : value =
match t with
IND n ->
List.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.