CS 320: Compiling TechniquesPeopleInformationBooksAssignment 0onward!What is a compiler?Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Compilers are complexCourse projectStandard MLIntroduction to MLIntro to MLSlide 19PreliminariesSlide 21Slide 22Slide 23Slide 24Basic ValuesSlide 26Using SML/NJLarger ProjectsCompilation ManagerWhat is next?An interpreterA little language (LL)LL abstract syntax in MLSlide 34Slide 35Function declarationsWhat is the type of the parameter t? Of the function?Slide 38A type errorSlide 40A very subtle errorSlide 42ExceptionsSlide 44EvaluatorSlide 46Slide 47Finishing the EvaluatorSlide 49Slide 50CS 320: Compiling TechniquesDavid WalkerPeopleDavid Walker (Professor)412 Computer Science Building[email protected]office hours: after each classDan Dantas (TA)417 Computer Science Building[email protected] office hours: Mondays 2-3 PMInformationWeb site:www.cs.princeton.edu/courses/archive/spring04/cos320/index.htmMailing list:BooksModern Compiler Implementation in MLAndrew AppelrequiredElements of ML ProgrammingJeffrey D. Ullmanalso: online references; see Web siteAssignment 0Write your name and other information on the sheet circulatingFind, skim and bookmark the course web pagesSubscribe to course e-mail listBegin assignment 1 Read chapter 1 AppelFigure out how to run & use SMLDue next Thursday 12onward!What is a compiler?A compiler is program that translates a source language into an equivalent target languageWhat is a compiler?while (i > 3) { a[i] = b[i]; i ++}mov eax, ebxadd eax, 1cmp eax, 3jcc eax, edxC programassemblyprogramcompiler does thisWhat is a compiler?class foo { int bar; ...}struct foo { int bar; ...}Java programcompiler does thisC programWhat is a compiler?class foo { int bar; ...}.........................Java programcompiler does thisJava virtual machine programWhat is a compiler?\newcommand{....}\sfd\sf\fadgLatex programcompiler does thisTex programWhat is a compiler?\newcommand{....}\sfd\sf\fadgTex programcompiler does thisPostscript programWhat is a compiler?Other places:Web scripts are compiled into HTMLassembly language is compiled into machine languagehardware description language is compiled into a hardware circuit...Compilers are complextext file to abstract syntaxlexing; parsingabstract syntax to intermediate form (IR)analysis; optimizations; data layoutIR to machine codecode generation; register allocationfront-endmiddle-endback-endCourse projectTiger Source Languagesimple imperative languageInstruction Trees as intermediate form (IR)type checking; data layout on the stackCode Generationinstruction selection algorithms; register allocation via graph coloringfront-endmiddle-endback-endStandard MLStandard ML is a domain-specific language for building compilersSupport forComplex data structures (abstract syntax, compiler intermediate forms)Memory management like JavaLarge projects with many modulesAdvanced type system for error detectionIntroduction to MLYou will be responsible for learning ML on your own.Today I will cover some basicsResources: Jeffrey Ullman “Elements of ML Programming”Robert Harper’s “an introduction to ML”See course webpage for pointers and info about how to get the softwareIntro to MLHighlightsData Structures for compilersData type definitionsPattern matchingStrongly-typed languageEvery expression has a typeCertain errors cannot occurPolymorphic types provide flexibilityFlexible Module SystemAbstract TypesHigher-order modules (functors)Intro to MLInteractive LanguageType in expressionsEvaluate and print type and resultCompiler as wellHigh-level programming featuresData typesPattern matchingExceptionsMutable data discouragedPreliminariesRead – Eval – Print – Loop- 3 + 2;PreliminariesRead – Eval – Print – Loop- 3 + 2;> 5: intPreliminariesRead – Eval – Print – Loop- 3 + 2;> 5: int- it + 7;> 12 : intPreliminariesRead – Eval – Print – Loop- 3 + 2;> 5: int- it + 7;> 12 : int- it – 3;> 9 : int- 4 + true;stdIn:17.1-17.9 Error: operator and operand don't agree [literal] operator domain: int * int operand: int * bool in expression: 4 + truePreliminariesRead – Eval – Print – Loop - 3 div 0;Failure : Div - run-time errorBasic Values- ();> () : unit => like “void” in C (sort of) => the uninteresting value/type- true;> true : bool- false;> false : bool- if it then 3+2 else 7; “else” clause is always necessary> 7 : int- false andalso loop_Forever;> false : bool and also, or else short-circuit evalBasic ValuesIntegers- 3 + 2> 5 : int- 3 + (if not true then 5 else 7);> 10 : int No division between expressionsand statementsStrings- “Dave” ^ “ “ ^ “Walker”;> “Dave Walker” : string- print “foo\n”;foo> 3 : intReals- 3.14;> 3.14 : realUsing SML/NJInteractive mode is a good way to start learning and to debug programs, but…Type in a series of declarations into a “.sml” file- use “foo.sml”[opening foo.sml]…list of declarationswith their typesLarger ProjectsSML has its own built in interactive “make”Pros:It automatically does the dependency analysis for youNo crazy makefile syntax to learnCons:May be more difficult to interact with other languages or toolsCompilation Manager% sml- OS.FileSys.chDir “~/courses/510/a2”;- CM.make(); looks for “sources.cm”, analyzes dependencies [compiling…] compiles files in group [wrote…] saves binaries in ./CM/- CM.make’ “myproj/”(); specify directorysources.cmc.smlb.smla.sigGroup isa.sigb.smlc.smlWhat is next?ML has a rich set of structured valuesTuples: (17, true, “stuff”)Records: {name = “Dave”, ssn = 332177}Lists: 3::4::5::nil or [3,4]@[5]DatatypesFunctionsAnd more!Rather than list all the details, we will write a couple of programsAn interpreterInterpreters are usually implemented as a series of transformers:stream ofcharactersabstractsyntaxlexing/parsingevaluateabstractvalueprintstream ofcharactersA little language (LL) An arithmetic expression e isa boolean valuean if statement (if e1 then e2 else e3)an integeran add operationa test for zero (isZero e)LL abstract syntax in MLdatatype term = Bool of bool| If of term * term * term| Num of int| Add
View Full Document