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 24Slide 25Basic ValuesSlide 27Using SML/NJLarger ProjectsCompilation ManagerWhat is next?An interpreterA little language (LL)LL abstract syntax in MLSlide 35Slide 36Function declarationsWhat is the type of the parameter t? Of the function?Slide 39A type errorSlide 41A very subtle errorSlide 43ExceptionsSlide 45EvaluatorSlide 47Slide 48Finishing the EvaluatorSlide 50Slide 51Last ThingsCS 320: Compiling TechniquesDavid WalkerPeopleDavid Walker (Professor)412 Computer Science Building[email protected]office hours: after each classGuilherme Ottoni (TA)417 Computer Science Building[email protected] office hours: Mondays 2-2:30 PMFridays 2-3 PMInformationWeb site:www.cs.princeton.edu/courses/archive/spring05/cos320/index.htmMailing list:To subscribe:[email protected] nceton.eduTo post to this list, send your email to:[email protected]Modern Compiler Implementation in ML, Andrew AppelA reference manual for SMLbest choice: Online referencessee course web siteseveral hardcopy booksElements of ML Programming, Jeffrey D. UllmanAssignment 0Write your name and other information on the sheet circulatingFind, skim and bookmark the course web pagesSubscribe to course e-mail listBegin assignment 1 Figure out how to run & use SMLDue next Thursday February 10onward!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 HTMLassembly language is compiled into machine languagehardware description language is compiled into a hardware circuit...Compilers are complextext file to abstract syntaxlexing; parsingabstract syntax to intermediate form (IR)analysis; optimizations; data layoutIR to machine codecode generation; register allocationfront-endmiddle-endback-endCourse projectFun Source Languagesimple imperative languageOnly 1 IR (the initial abstract syntax generated by the parser)type checking; high-level optimizationsCode Generationinstruction selection algorithms; register allocation via graph coloringfront-endmiddle-endback-endStandard MLStandard ML is a domain-specific language for building compilersSupport forComplex data structures (abstract syntax, compiler intermediate forms)Memory management like JavaLarge projects with many modulesAdvanced type system for error detectionIntroduction to MLYou will be responsible for learning ML on your own.Today I will cover some basicsResources: Robert Harper’s Online book “an introduction to ML” is a good place to startSee course webpage for pointers and info about how to get the softwareIntro to MLHighlightsData Structures for compilersData type definitionsPattern matchingStrongly-typed languageEvery expression has a typeCertain errors cannot occurPolymorphic types provide flexibilityFlexible Module SystemAbstract TypesHigher-order modules (functors)Intro to MLInteractive LanguageType in expressionsEvaluate and print type and resultCompiler as wellHigh-level programming featuresData typesPattern matchingExceptionsMutable data discouragedPreliminariesstart sml in Unix by typing sml at a prompt:tux% smlStandard ML of New Jersey, Version 110.0.7, September 28, 2000 [CM; autoload enabled]- (* quit SML by pressing ctrl-D *)(* just so you know, comments can be (* nested *) *)PreliminariesRead – Eval – Print – Loop- 3 + 2;PreliminariesRead – Eval – Print – Loop- 3 + 2;> 5: intPreliminariesRead – Eval – Print – Loop- 3 + 2;> 5: int- it + 7;> 12 : intPreliminariesRead – 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 + truePreliminariesRead – 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/NJInteractive 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 ProjectsSML has its own built in interactive “make”Pros:It automatically does the dependency analysis for youNo crazy makefile syntax to learnCons: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 valuesTuples: (17, true, “stuff”)Records: {name = “Dave”, ssn = 332177}Lists: 3::4::5::nil or [3,4]@[5]DatatypesFunctionsAnd more!Rather than list all the details, we will write a