Language definition by interpreter Routes to defining a languageTypical compiler structure“MiniJava run” structureInterpreter structure: advantagesInterpreter structure: more advantagesInterpreter structure: disadvantagesAn interpreter compromise (e.g. Java VM)IMPORTANT OBSERVATIONInterpreter to TypeChecker / Static Analysis is a small stepHow large is MJ typechecker / semantics ?Interpreter to Compiler is a small stepAST for MJ programStart of the interpreter MJ statementsWhat else is needed? ifLoops: While is very much like Lisp’s whileAlso part of the main interpreter: exp-evalRevisit the statement interpreter(looking at code for simple-interp)Prof. Fateman CS 164 Lecture 14 1Language definition by interpreterLecture 14Prof. Fateman CS 164 Lecture 14 2Routes to defining a language•Formal mathematics– Context free grammar for syntax– Mathematical semantics (axioms, theorems, proofs)– Rarely used alone (the downfall of Algol 68)– Can be used to verify/prove properties (with difficulty)• Informal textual– CFG + natural language (Algol 60, Java Language Spec)– Just natural language (Visual Basic for Dummies) -- examples– Almost universally used•Operational– Here’s a program that does the job– Metacircular evaluator for Scheme, Lisp– Evaluator/ interpreter for MiniJavaProf. Fateman CS 164 Lecture 14 3inputTypical compiler structureSource programASTIntermediate formoutputLex, parseTypecheck, cleanupAssembly langObject codeMachineProf. Fateman CS 164 Lecture 14 4input“MiniJava run” structureSource programASTIntermediate formoutputinterpreterLex, parseTypecheck, cleanupWhat language is interpreter written in? What machine does it run on?Except that MJ has no input…Prof. Fateman CS 164 Lecture 14 5Interpreter structure: advantagesinterpreter•Interpreter is written in a higher level language: source language derives semantics from interpreter program and the semantics of the language of the interpreter (e.g. whatever it is that “+” does in Lisp).•What does EACH STATEMENT MEAN?•Exhaustive case analysis•What are the boundaries of legal semantics?•What exactly is the model of scope, etc..Prof. Fateman CS 164 Lecture 14 6Interpreter structure: more advantagesinterpreter•Prototyping / debugging easier (compare to machine level)•Portable intermediate form; here AST in Lisp as text; could be byte code• intermediate form may be compact•Security may be more easily enforced by restricting the interpreter or machine model [e.g. if Lisp were “safe”, so would the interpreter be safe.]•In modern scripting applications, most time is spent in library subroutines so speed is not usually an issue.Prof. Fateman CS 164 Lecture 14 7Interpreter structure: disadvantagesinterpreter•Typically unable to reach full machine speed. Repeatedly checking stuff•Difficult to transcend the limits of the underlying language implementation (not full access to machine: if interpreter is in Lisp, then “interrupts” are viewed through Lisp’s eyes. If interpreter is in Java, then Java VM presents restrictions.)•Code depends on presence of infrastructure (all of Lisp??) so even a tiny program starts out “big”. [Historically, was more of an issue]•(if meta-circular) bootstrapping… (digression on first PL)Prof. Fateman CS 164 Lecture 14 8An interpreter compromise (e.g. Java VM)interpreter•“Compile” to a hypothetical byte-code stack machine appropriate for Java and maybe some other languages, easily simulated on any real machine.•Implement this virtual byte-code stack machine on every machine of interest.•When speed is an issue, try Just In Time compiling; convert sections of code to machine language for a specific machine. Or translateJava to C or other target.Prof. Fateman CS 164 Lecture 14 9IMPORTANT OBSERVATION• Much of the work that you do interpreting has a corresponding kind of activity that you do in typechecking or compiling.• This is why I prefer teaching CS164 by first showing a detailed interpreter for the target language.Prof. Fateman CS 164 Lecture 14 10Interpreter to TypeChecker / Static Analysis is a small step• Modest modification of an interpreter program can result in a new program which is a typechecker. An interpreter has to figure out VALUES and COMPUTE with them. A typechecker has to figure out TYPES and check their validity. •For example:•Interpreter: To evaluate a sequence {s1, s2}, evaluate s1then evaluate s2, returning the last of these.•Typechecker: To TC a sequence {s1, s2}, TC s1 then TC s2, returning the type for s2. •Interpreter: To evaluate a sum (+ A B) evaluate A, evaluate B and add.•Typechecker: To TC a sum, (+ A B) TC A to an int, TC B to an int, Then, return the type, i.e. Int.•Program structure is a walk over the AST.Prof. Fateman CS 164 Lecture 14 11How large is MJ typechecker / semantics ?• Environment setup code for MJ is about 318 lines of code.• Simple interpreter, including all environment setup, is additional 290 lines of code, including comments.• Add to this file the code needed for type checking and you end up with an extra 326 lines of code.• Environment setup would be smaller if we didn’t anticipate type checking.Prof. Fateman CS 164 Lecture 14 12Interpreter to Compiler is a small step• Modest modification of an interpreter program can result in a new program which is a compiler.•For example:•Interpreter: To evaluate a sequence {s1, s2}, evaluate s1then evaluate s2, returning the last of these.•Compiler: To compile a sequence {s1, s2}, compile s1 then compile s2, returning the concatenation of the code for s1and the code for s2. •Interpreter: To evaluate a sum (+ A B) evaluate A, evaluate B and add.•Compiler: To compile a sum, (+ A B) compile A, compile B, concatenate code-sequences. Then, compile + to “add the results of the two previous sections of code”. And concatenate that.•Program structure is a walk over the intermediate code AST.Prof. Fateman CS 164 Lecture 14 13AST for MJ program• AST is a data structure presenting the Program and all subparts in a big tree reflecting ALL parsed constructs of the system.• Here’s fact.java’s AST with some parts abbreviated with #.(Program(MainClass (id Factorial 1) (id a 2)(Print (Call (NewObject #) (id ComputeFac 3) (ExpList #))))(ClassDecls(ClassDecl (id Fac 7) (extends nil) (VarDecls)(MethodDecls (MethodDecl IntType # # # # #)))))Prof. Fateman CS 164 Lecture 14
View Full Document
Unlocking...