### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Programming Languages CS 3723

UTSA

GPA 3.55

### View Full Document

## 6

## 0

## Popular in Course

## Popular in ComputerScienence

This 168 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 3723 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/231390/cs-3723-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.

## Reviews for Programming Languages

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Continuation and Exceptions Control flow in sequential languages cccc 23 Topics a Control flow ordering of sequential statements I Structured Programming Goto considered harmful El Continuation dynamic re enterable evaluation I Function representing the rest of the expression a In functional programming the rest of program a Include the enclosing environment as part of function closure I Convert expressionsfunctions to statementsloops n Exceptions dynamic jump to exit in unusual situations I Structured goto that may return a value I Dynamic scoping of exception handler a Manual control of evaluation order force and delay I Use function definitions to put off computations I Use function calls to force the evaluation of computations I Details skipped cs3723 Imperative programming Control Flow of Programs El Structured control flow I Sequence of statements 1 abbc I Conditional n if a lt b then c else d 1 switcha I LOOpS 1 for 1 while I Jumping out of a scope 1 break continue return El Non structured control flow I Goto conditional jump I Used to implement structured control flow in assembly cs3723 Fortran Control Structure 10 IF X GT 0000001 GO TO 20 11 X X IF X LT 0000001 GO TO 50 20 IF XY LT 000001 GO TO 30 X XYY 30 X XY 50 CONTINUE XA YBA GOTOll Similar structure may occur in assembly code cs3723 Controlling Jumps El Standard constructs that structure jumps if then else end while do end for case I Modern style I Group code in logical blocks Avoid uncontrolled jumps 1 Eg into the middle of a block without allocating local variables I What ifI need to jump into the mid of a block I Eg interrupted tasks in OS web applications the backforward button checkpointing n The scenario my task was interrupted now I want to resume from where I stopped I Solution save the entire runtime environment as a closure 1 Code pointer where to start evaluating the instructions 1 Environment pointer the entire relevant memory stores cs3723 Con rmations El General programming technique Capture the continuation at some point in a program to be used later a A function closure that takes a sin le parameter the result of the past evaluation and returns the result 0 the entire program I To jump into the mid of a program make a function call to the continuation El Useful in I Implementing functional programming languages Operating system scheduling multiprogramming Web site design El Originated from implementation of functional programming languages In pure functional programming the entire program is a single expressnon 1 Independent sub expressions can be evaluated in parallel I But hardware machines require explicit ordering of statements I What is the control flow within expressions cs3723 Continuation of Expressions El Continuation impose sequential ordering in subexpressions I The continuation of an expression is the remaining work to be done after evaluating the expression l Continuation of e is a function applied to the result of e El Implementing control flow in functional languages Evaluate current expression Save the result into a variable Evaluate the rest of the computation 2X 3y 1X 2y let val r2x 2 X in let r2x 2X in end iet vai r3y 3 y in is equivalent to let val sum1r2x r3y in fn r2xgt 2 X let val rlx 1 X in let val sum2 suml r1x in let val r2y 2 Y in Continuation of 2X sum2 r2y end end cs3723 Continuation and Tail Recursion n A function call from g to f is a tail call I if g returns the result of calling f with no further computation I Example red tail call blue nontail call fun fx if x gt 0 then X else fx12 fun fxy if xgty then x else f2xy El But most function calls are not tail calls I Can we convert all recursive functions to tail recursion I If a program needs to be reenterable function calls shouldn t return to caller I Solution continuation passing a Pass continuation as parameter to callee n Callee does not need to return to caller cs3723 Tail recursive function using contlnuatlon a Standard function Cortivetrtlarbliltrary function calls fun factn ifn0then 1 0 339 ca 5 else factn1 El For each function definition F I Extend the definition with a El Continuation form continuation parameter K fun factn K I At eightfursctlion ctallfinside F if 0 then K1 n comp iatioen Ii toca new else factn1 xx K nX continuation function 39 39 1 Convert f into a tail call factn xxx computes n which takes the new continuation function as an extra argument 393 Example compL39tation At each normal return 1 Instead of return invoke fact3 xx39x continuation function K with factzl xylxlx 3y the original returned value a Another example factl AXY3Y2X AXY3Y2X 1 6 cs3723 Tail Recursive Factorial n Factorial in continuation passing style factn K if n0 then K1 else factn 1 axK nx I Continuation of factn 1 XXK nx 1 Cannot pop caller s activation record before recursion need to save the local variable n n Recursion tail recursion loops fun factn let val r ref 1 val nl ref 0 in while not lnln do nl n 1 r r lnl r end C53723 10 General uses of continuations n Explicit control I Normal termination call continuation I Abnormal termination do something else i Compilation techniques I Call to continuation is functional form of go toquot n Jump to the middle of a block by saving the environment in the function closure and restore the environment before jump El Web applications Web Services MOM and SOA services I Handle long running workflows 2 Workflow may take 1 year to complete I Progress of subtasks is asynchronous u Sequential programming is simpler than asynchronous El Continuations provide I An easy way to suspend workflow execution at a wait state I Thread of control can be resumed when the next messageevent occurs maybe some long time ahead C53723 11 Exception structured exit I When something unusual happens we want a program to I Jump out of one or many levels of nested blocks I Until reaching some program point to continue I Pass information to the continuation point I Activation records may be de allocated during the jump a May need to free heap space other resources I What unusual situations I Division by zero null pointers unexpected inputs I Sometimes used in normal situations as well I What languages have exception support I C Java ML Ada I What do we do in other languages I AbOl39t I Return a value representing ERROR C53723 12 Exception Alternative Way of Return II I I El In C can we tell whether x is in struct IntList int x IntList rest IntList removeIntList l int x if I 0 return 0 if gtx x return gtrest gtrest removel gtrestx return I El In CJava we can make sure only existing things are removed IntList removeIntList l int x if I 0 throw no such elementquot if gtx x return gtrest gtrest removel gtrestx return I IntList removeIfExistIntList l int x try removel x catch const char return I Two main language constructs l Statement or expression to raise or throw exception Declaration to establish exception handler cs3723 Exception A Controlled Dynamic Jump III a A normal jump is a static goto Iabe I Label is defined statically as the destination ofjump I Label is defined in an enclosing scope of the jump I Examples 1 L continue jump to start of current scope n breakL jump to end of current scope in returnL jump to end of current function n An exception is a dynamic jump I Don t know where to resume execution until runtime n Jump out of current block a Look for a matching exception handler in enclosing scopes Use dynamic scoping rule instead of static scoping C53723 14 When Should We Use Exceptions El Separation of concern I first consider normal behavior handle unusual situations later a When exceptions are not handled evaluation aborts on error conditions 1 When exceptions are handled error recovery El For more efficient control flow I Return immediately to where the error can be handled I Jump out multiple blocks at a time C53723 15 De ning Exceptions n Exception declaration I Type of data that can be passed in exception 1 ML exception ltnamegt of lttypegt n CJava any data type I Raising an exception I Abort the rest of current block and jump out 1 ML raise ltnamegt ltargumentsgt a C throw ltvauegt n Handling an exception I Continue normal execution after exception 1 ML ltexp1gt handle ltpatterngtgtltexp2gt a C try catch lttypegt var C53723 16 Exceptions in ML and in C El ML exception X let fun fy raise X 1 fun g f1 handle X gt 2 in g handle X gt 4 end El C class X int fint y throw X return 1 int 90 try return f1 catch X x return 2 int main try g catch X x return 4 C53723 17 How Are Exceptions Handled II ML exception X let fun fy raise X 1 fun g f1 handle X gt 2 in g handle X gt 4 end El What are the events that have occurred Enter the let expression Make function call g Make function call f1 Function call f1 raises exception X Exception X is handled in function call g Function ca g returns with value 2 The let expression exits C53723 18 Dynamic Scope of Handler exception X let fun fy raise X 1 fun g f1 handle X gt 2 in g handle X gt 4 end Dynamic scope find first X handler going up the dynamic call chain f1 control link instead of access link leading to raise X 63723 g Which handler is used El Dynamic scoping of handlers I Multiple functions could handle the same exception n One function handles exception one way in Another function handles exception another way I General dynamic scoping rule Jump to most recently established handler on run time stack Dynamic scoping is not an accident I User knows how to handler error I Author of library function does not C53723 20 Exceptions vs Type System n Exception is not part of a type system I Raising expressions I Expression e has type t if normal termination of e produces value of type t I Raising exception is not normal termination 3 Example 1 raise X is not valid I Handling exceptions gt value I Converts exception to normal termination I Need type agreement 1 raise X handle X gt e Type of e must be int 1 e1 handle X gt e2 Type of e1 e2 must be int C53723 21 Exceptions and Resource Allocation exception X let val x ref 123 in let val y ref 456 in raise X end end handle X gt El cs3723 Resources may be allocated between handler and raise May be garbage after exception Examples I Memory I Lock on database I Threads I General problem Must be handled manually 22 Exception vs Continuation El Continuation I Explicitly represent the rest of computation I Do not need to return to the caller El Can use exception to avoid returning to the caller El Raising exception I Jumping out of multiple blocks at a time I Different continuation for normal and exceptional stuanns i Continuation of exception rest of computation after exception is handled El Raising exceptions may have complications I Resource management opened files garbage collection I Use continuation passing to implement exception El Pass multiple continuations one to handle normal condition the others to handle exceptions C53723 23 Llsp Functions recursion and lists cs3723 1 The Lisp Programming Language El Stems from interest in symbolic computation I Led by John McCarthy in late 19505 I Designed for math logic in artificial intelligence ii Functional programming paradigm I A program is a expression 1 Expresses flow of data map input values to output values El No concept of controlflow or statements El No side effects or modification to variables I Functions are firstclass objects El A function can be used everywhere a regular value is used El Functions can take other functions as parameters and return other functions as results higherorder functions El Adding side effect operations I Different occurrences of expressions have different values El Strength and weakness Simplicity and flexibility Build prototype systems incrementally X Not many tools or libraries Slow in speedefficiency interpreted cs3723 Concepts in Lisp El Supported value types I Atomic values numbers eg 3 77 symbols eg abc booleans I Compound data structures lists car cons cdr functions lambda El Supported operations I Function definition and function call 2 define fname lambda parameters body a fname arguments I Predefined functions cons cond if car cdr eq El Innovations in language design I Functional programming paradigm in A program is composed of expressions in Functions are firstclass objects El Higher order functions Abstract view of memory the Lisp abstract machine I Program as data dynamic interpretation of program cs3723 Interacting with Scheme define pi 314159 bind pi to 314159 lambda X X X anonymous function define sq lambda X X X define sq X X X define sq lambda X X X sq 100 100 100 if P E1 E2 if P then E1 else E2 cond P1 E1 P2 E2 else E3 if P1 E1 if P2 E2 E3 let X1 E1 X2 E2 E3 declare local variables X1 and X2 lambda xl X2 E3 E1 E2 let xl E2 X2 E2 E3 E2 can use X1 as a local variable lambda xl lambda x2 E3 E2 E1 cs3723 Expressions Statements and Declarations Expression x52 I Syntactic entity that has a value I Need not change accessible memory I If it does has a side effect El Statement load 4094 r1 I Imperative command I Alters the contents of previouslyaccessible memory I Declaration integer x I Introduces new identifiers variables a May bind value to identifier specify type etc I Scoping rules for variables which variable declaration does each identifier name refer to cs3723 Function Definitions and Variables II Recursive function definition define find lambda x y cond eq y nil nil eq x car y x else find x cdr y n Recursiver traverse the tail of a list y I what about car y a Is y a flat list or a nested list a tree I What are the results of the following calls find abc 0 find abc abc find abc X y abc find abc x y abc cs3723 Lists in LispScheme El a In LispScheme a list may contain arbitrary types of values I a b c 2 3 5 lambda a b cons a b I A dynamically typed list can be used to implement most pointer based data structures including lists and trees I Can it be used to implement arbitrary graphs can we build cycles in lists LispScheme lists can be used to naturally implement AST a tree data structure used as an internal representation of programs in compilersinterpreters lambda list cons 2 b a b 3 5 cs3723 Exercises Programming in LispScheme n Programming steps I What are the input parameters What values could each parameter take I Enumerate each combination of input parameters give a return value for each case n Exercise problems I Define a function Find which takes two parameters x and y It returns x if x appears in y and returns an empty list 0 otherwise I Define a function substitute which takes three parameters x y and 2 It returns a new list which replaces all occurrences x in y with z I Define a function Max which takes a single parameter x and returns the maximal number that appears in x cs3723 Evaluation Using Expressions vs Statements El Side effect free expressions in LispScheme define insert lambda X y cons X y insert 4 insert 3 0 El Imperative programming in C void insert int X Cel y Cell 2 CellmallocsizeofCell zgtval ygtva zgtnext ygtnext ygtval X ygtnext z int main Cel y CellmallocsizeofCell ygtval1 ygtnext0 insert3 y insert4 y n Evaluation order I Among pure expressions explicit in data flow a Can evaluate each expression as soon as values are ready I Among statements implicit in side effects modifications error I Statement order cannot be changed unless proven otherwise dataflow and dependence analysis cs3723 9 Lisp Adding Side Effects II Pure Lisp I Expressions do not modify observable machine states 1 No side effects I Impure Lisp I Allow modifications to memory a May increase efficiency of programs Eg Modify a single element in a list a set X y Replace the value of x with y 1 rplacea A B y or setcar A B y replace A the address field of A B with y 1 rplaced A B y or setcdr A B y replace B the decrement field of A B with y I Sequence operator 1 progn set X y X or begin set X y X Set the value of x to be y then returns the value of x cs3723 Functional Programming n Functions are first class objects I Functions treated same as primitive values What about CC I Can be used to build anonymous and higherorder functions a Higher order functions are functions that either I Take other functions as arguments or return a function as result I First order functions parameters and results are not functions I Secondorder functions take as input or return firstorder functions I Third order functions take as input or return secondorder functions I Example function composition lambda f gx f g x VS lambda f g lambda x f g x C53723 11 Pass Functions as Parameters I Apply a function to each element in a list define maplist f x cond null x nil else cons f car x maplist f cdr x vs Ce maplistint f Ce X if X NULL return NULL else Ce res Ce malloc sizeofCeI resgtvafxgtva resgtnextmapistfxgtnext return res C53723 12 Return functions as results Function composition define compose lambda f g lambda x f g x vs int composeint f int g int X return fgx n In Scheme I The function compose takes only two parameters I The result of compose is another function El in C I The function compose takes three parameters I The result of compose if a concrete value I C does not allow functions being returned as results why C53723 13 Programming With Higherorder Func ons n Apply a function to each element in a list define maplist lambda f x cond null x nil else cons f car x maplist f cdr x Reduce a list into a single value define reduce lambda f0 f1 f2 x cond null x f0 else f2 f1 car x reduce f0 f1 f2 cdr X Increment each number in a list by 1 define incrementl lambda X maplist lambda e if number e e 1 e x Compute the sum of all numbers in a list define sum lambda X reduce O lambda e if number e e 0 lambda resl resZ resl re52 x El El El Exercise l A mapTree function that treat lists as trees I A mapTreePostOrder function that traverses a tree in post order cs3723 14 The Lisp Abstract machine El Abstract machine I The runtime system software simulated machine based on which a language is interpreted I In short the internal model of the interpreter that implements thelanguage El Lisp Abstract machine I A Lisp expression the current expression to evaluate I A continuation the rest of the computation I Alist variablegtvalue mapping I A set of cons cells dynamic memory an pointed to by pointers in AIist a Each cons cell is a pair car cdr gt linked data structures lists atm a gt a single atom El Garbage collection I Automatic collection of nonaccessible cons cells C53723 15 Implementing Lisp The Memory Model El Cons cells Shanng a a b El Both structures could be printed as ABAB n Which are the results of evaluating I cons cons A B cons A B I lambda x cons x x cons A B n Equality of compound structures I What is the result of eq a a I What is the result of eq a b a b C53723 17 Garbage Collection Memory management at runtime I Maintains a list of available memory cells I Receive and satisfies allocation requests I When available space is below threshold 1 Invoke garbage collector El Garbage collection I Detecting memory cells no longer used a Reclaim memory cells C53723 18 Detecting Garbage n Garbage I Memory locations in the heap that are no longer accessible n Examples car cons e1 e2 I Cells created in evaluation of e2 may be garbage 1 unless shared by e1 or other parts of program lambda x car cons x x 39Big Mess I The car and cdr of this cons cell may point to overlapping structures El Need to keep track of how many active pointers are pointing to each store C53723 19 CS 3723 Arrays of functions and functions inside structs Page 1 of 2 runner cat testsortc include ltstdiohgt include ltstdlibhgt include lttimehgt define M 20 void execsort void int int void bubblesort int void selectsort int int maxindint int void swapint int void printit int void inita int void main void int aM void sortit int bubbl esort selectsort int i for i 0 i lt 2 i printfquotSort dnquot i execsort sortit i a printfquotThat s all folksnquot void execsort void sort int int a initaa sort a printita void bubblesort int a int dummy i for dummy 0 dummy lt M l dummy for i 0 i lt M l i if ai gt ai1 swapampai ampai1 void selectsort int a int maxi n M l while n gt 0 maxi maxindn a swapampamaxi ampan n int maxindint m int a int maxi if m 0 return m maxi maxindm 1 a if am gt amaxi return m return maxi void swapint x int y for i 0 i lt 10 i printfquot 2iquot ai printfquotnquot void inita int a for i 0 i lt M i ai int 10000drand48 runner lint m u testsortc function returns value which is always ignored printf runner cc 0 testsort testsortc runner testsort 15 58 159 159 163 269 318 353 383 390 2 75 212 265 293 298 306 404 462 532 That s all folks Continuation and Exceptions Control flow in sequential languages cccc 23 Topics a Control flow ordering of sequential statements I Structured Programming Goto considered harmful n Exceptions dynamic jump to exit in unusual situations I Structured goto that may return a value I Dynamic scoping of exception handler El Continuation dynamic re enterable evaluation I Function representing the rest of the expression a In functional programming the rest of program 2 Include the enclosing environment as part of function closure I Convert expressionsfunctions to statementsloops a Manual control of evaluation order force and delay I Use function definitions to put off computations I Use function calls to force the evaluation of computations I Details skipped cs3723 Imperative programming Control Flow of Programs El Structured control flow I Sequence of statements 1 abbc I Conditional n if a lt b then c else d 1 switcha I LOOpS 1 for 1 while I Jumping out of a scope 1 break continue return El Non structured control flow I Goto conditional jump I Used to implement structured control flow in assembly cs3723 Fortran Control Structure 10 IF X GT 0000001 GO TO 20 11 X X IF X LT 0000001 GO TO 50 20 IF XY LT 000001 GO TO 30 X XYY 30 X XY 50 CONTINUE XA YBA GOTOll Similar structure may occur in assembly code cs3723 Static and Dynamic Jumps El Structured jumps among logical blocks if then else end while do end for case break continue Function calls and return I Avoid nonstructured jumps I Explicit goto jumps into middle of block or function body El Is the destination always known at compiletime Staticjumps destination known before evaluating code I If then else while for break goto break continue calling a function by its static name I Dynamicjumpsdestination not know until runtime 1 Calling a function pointer function return 1 Need to store the destination address in runtime stack cs3723 5 Exception A Structured Dynamic Jump III a A normal jump is a static goto labe I Label is defined statically as the destination ofjump I Label is defined in an enclosing scope of the jump I Examples 1 L continue jump to start of current scope n breakL jump to end of current scope in returnL jump to end of current function n An exception is a dynamic jump I Don t know where to resume execution until runtime n Jump out of current block a Look for a matching exception handler in enclosing scopes Use dynamic scoping rule instead of static scoping cs3723 Exception Alternative Way of Return El In C can we tell whether X is in I struct IntList int X IntList rest IntList removeIntList I int X if I 0 return 0 if IgtX X return lgtrest Igtrest removeIgtrestx return I I In CJava we can make sure only existing things are removed IntList removeIntList I int X if I 0 throw no such element if IgtX X return lgtrest Igtrest removeIgtrestx return I IntList removeIfEXistIntList I int X try removeI X catch const char return I Two main language constructs l Statement or expression to raise or throw exception Declaration to establish exception handler cs3723 Exception What is it a When something unusual happens we want a program to Jump out of one or many levels of nested blocks Until reaching some program point to continue Pass information to the continuation point Activation records may be deallocated during the jump a May need to free heap space other resources a What unusual situations I Division by zero null pointers unexpected inputs I Sometimes used in normal situations as well i What languages have exception support I C Java ML Ada i What do we do in other languages I Abort I Return a value representing ERROR cs3723 When Should We Use Exceptions El Separation of concern I first consider normal behavior handle unusual situations later a When exceptions are not handled evaluation aborts on error conditions 1 When exceptions are handled error recovery El For more efficient control flow I Return immediately to where the error can be handled I Jump out multiple blocks at a time cs3723 De ning Exceptions n Exception declaration I Type of data that can be passed in exception n ML exception ltnamegt of lttypegt u CJava any data type I Raising an exception I Abort the rest of current block and jump out 2 ML raise ltnamegt ltargumentsgt In C throw ltvauegt n Handling an exception I Continue normal execution after exception n ML ltexp1gt handle ltpatterngtgtltexp2gt a C try catch lttypegt var C53723 10 Exceptions in ML and in C II ML exception X let fun fy raise X 1 fun g f1 handle X gt 2 in g handle X gt 4 end I C class X int fint y throw X return 1 int g try return f1 catch X x return 2 int main try g catch X x return 4 C53723 11 How Are Exceptions Handled II ML exception X of int let fun fy raise Xy 1 fun g f1 handle Xy gt y1 in g handle Xy gt y end El What are the events that have occurred Enter the let expression Make function call g Make function call f1 Function call f1 raises exception X1 Exception X1 is handled in function call g Function ca g returns with value 2 The let expression exits C53723 12 Dynamic Scoping of Handler exception X of int let fun fy raise Xy 1 fun g f1 in g handle Xy gt y end Dynamic scope 30 find first X handler 90mg up the dynamic call chain f1 lei a control link instead of access link leading to raise X 63723 13 Which handler is used El Dynamic scoping of handlers I Multiple functions could handle the same exception n One function handles exception one way in Another function handles exception another way I General dynamic scoping rule Jump to most recently established handler on run time stack Dynamic scoping is not an accident I User knows how to handler error I Author of library function does not C53723 14 Exceptions vs Type System n Exception is not part of a type system I Raising expressions I Expression e has type t if normal termination of e produces value of type t I Raising exception is not normal termination 3 Example 1 raise X is not valid I Handling exceptions gt value I Converts exception to normal termination I Need type agreement 1 raise X handle X gt e Type of e must be int 1 e1 handle X gt e2 Type of e1 e2 must be int C53723 15 Exceptions and Resource Allocation exception X let val x ref 123 in let val y ref 456 in raise X end end handle X gt El cs3723 Resources may be allocated between handler and raise May be garbage after exception Examples I Memory I Lock on database I Threads I General problem Must be handled manually Controlling Jumps I What ifI need to jump into the mid of a block I Eg interrupted tasks in OS web applications the backforward button checkpointing n The scenario my task was interrupted now I want to resume from where I stopped I Solution save the entire runtime environment as a closure n Code pointer where to start evaluating the instructions in Environment pointer the entire relevant memory stores C53723 17 Con rmations El General programming technique Capture the continuation at some point in a program to be used later a A function closure that takes a sin le parameter the result of the past evaluation and returns the result 0 the entire program I To jump into the mid of a program make a function call to the continuation El Useful in I Implementing functional programming languages Operating system scheduling multiprogramming Web site design El Originated from implementation of functional programming languages In pure functional programming the entire program is a single expressnon 1 Independent sub expressions can be evaluated in parallel I But hardware machines require explicit ordering of statements I What is the control flow within expressions C53723 18 Continuation of Expressions El Continuation impose sequential ordering in subexpressions I The continuation of an expression is the remaining work to be done after evaluating the expression l Continuation of e is a function applied to the result of e El Implementing control flow in functional languages Evaluate current expression Save the result into a variable Evaluate the rest of the computation 2X 3y 1X 2y let val r2x 2 X in let r2x 2X in end iet vai r3y 3 y in is equivalent to let val sum1r2x r3y in fn r2xgt 2 X let val rlx 1 X in let val sum2 sum1 r1x in let val r2y 2 Y in Continuation of 2X sum2 r2y end end C53723 19 Continuation Passing El If a program needs to be re enterable function calls shouldn t return to caller I All function calls must be converted to tail calls I A function call from g to f is a tail call I if g returns the result of calling f with no further computation I Example red tail call blue nontail call fun fx if x gt 0 then X else fx12 fun fxy if xgty then x else f2xy El But most function calls are not tail calls I Can we convert all function calls to tail calls I Solution continuation passing a Pass continuation as parameter to callee n Callee does not need to return to caller C53723 20 Tail recursive function using continuation El Standard function fun factn if n0 then 1 else nfactn l El Continuation form fun factn K if n0 then K1 else factn l xxK nx factn xxx computes n n Example computation fact3vxx fact2 kyvxx 3y factl AXY3Y2X AXY3Y2X 1 6 I For each function definition F I Extend the definition with a continuation parameter K I At each function call inside F 1 Abstract the rest of computation into a new continuation function 1 Convert f into a tail call which takes the new continuation function as an extra argument I At each normal return El Return result of invoking continuation K with the original returned value I Another example fun appendnily y appendx1x2y x1 appendx2y C53723 21 Tail Recursive Factorial n Factorial in continuation passing style factn K if n0 then K1 else factn 1 axK nx I Continuation of factn 1 XXK nx 1 Cannot pop caller s activation record before recursion need to save the local variable n n Recursion tail recursion loops fun factn let val r ref 1 val nl ref 0 in while not lnln do nl n 1 r r lnl r end C53723 22 General uses of continuations n Explicit control I Normal termination call continuation I Abnormal termination do something else i Compilation techniques I Call to continuation is functional form of go toquot n Jump to the middle of a block by saving the environment in the function closure and restore the environment before jump El Web applications Web Services MOM and SOA services I Handle long running workflows 2 Workflow may take 1 year to complete I Progress of subtasks is asynchronous u Sequential programming is simpler than asynchronous El Continuations provide I An easy way to suspend workflow execution at a wait state I Thread of control can be resumed when the next messageevent occurs maybe some long time ahead C53723 23 Exception vs Continuation El Continuation I Explicitly represent the rest of computation I Do not need to return to the caller El Can use exception to avoid returning to the caller El Raising exception I Jumping out of multiple blocks at a time I Different continuation for normal and exceptional stuanns i Continuation of exception rest of computation after exception is handled El Raising exceptions may have complications I Resource management opened files garbage collection I Use continuation passing to implement exception El Pass multiple continuations one to handle normal condition the others to handle exceptions C53723 24 Lisp Functions recursion and lists cs3723 The Lisp Programming Language n Stems from interest in symbolic computation I math logic artificial intelligence I Functional programming paradigm I A programfunction is a expression El Expresses flow of data in evaluations gt map input values to output values a No concept of controlflow or statements the ordering of expressions does not matter I Functions are firstclass objects El A function can be used everywhere a regular value eg an integer is used a Functions can take other functions as parameters and return other functions as results higherorder functions a Adding side effect operations I Different occurrences of expressions have different values El Strength and weakness J Simplicity and flexibility Build systems incrementally as the results of experiments X Not many tools or libraries Slow in speedefficiency interpreted cs3723 Concepts in Lisp El Supported value types I Atomic values numbers symbols booleans I Compound data structures lists car cons cdr functions lambda El Supported operations I Function definition abstraction n lambda parameterlist body I Predefined functions cons cond if car cdr eq a Language Syntax exp value variable I expList expList exp expList exp or shorthand exp value variable exp exp n Innovations in the design of Lisp I Functional programming paradigm u A program is an expression based on function abstractions and applications a First class functions and higherorder functions I Abstract view of memory the Lisp abstract machine I Program as data dynamic interpretation of program cs3723 Expressions Statements and Declarations Expression x52 I Syntactic entity that has a value I Need not change accessible memory I If it does has a side effect El Statement load 4094 r1 I Imperative command I Alters the contents of previouslyaccessible memory I Declaration integer x I Introduces new identifiers variables a May bind value to identifier specify type etc I Scoping rules for variables which variable does each name refers to cs3723 Interacting With Scheme define pi 314159 bind pi to 314159 lambda x x X anonymous function define sq X X X define sq lambda x X X sq 100 100 100 if P E1 E2 if P then E1 else E2 cond P1 E1 P2 E2 else E3 if P1 E1 if P2 E2 E3 let X1 E1 X2 E2 E3 lambda xl X2 E3 E1 E2 lambda X1 lambda X2 E3 E1 E2 let X1 E2 X2 E2 E3 lambda X1 lambda X2 E3 E2 E1 El Programming environment DrScheme 1 available on WindowsLinux machines 1 Documents available from class web site cs3723 Function De nitions and Variables II Recursive function definition define find lambda X y cond eq y nil nil eq x car y x else find x cdr y I Recursiver traverse the tail of y what about car y 1 Is y a flat list or a nested list a tree El Static scoping of variables Runtime context can differ from the definition context 1 define y 100 1 define addx lambda x x y 1 What is the results of lambda y addx y 3 n x 3 or x 100 Static scoping determine binding of variables by statically looking at surrounding scopes without running the program cs3723 Lists in Scheme I In SchemeLisp a list may contain arbitrary kinds of values I a b c 2 3 5 lambda a b cons a b l A dynamically typed list can be used to implement most pointerbased data structures in lists trees graphs etc El Scheme lists can be used to naturally implement ASTs abstract syntax trees lambda li t cons aib b 3 5 El What about graphs can we build cycles in lists cs3723 Lisp Adding Side Effects II Pure Lisp I Expressions do not modify observable machine states 1 No side effects a Impure Lisp I Allow modifications to memory a May increase efficiency of programs Eg Modify a single element in a list a set X y Replace the value of x with y 1 rplacea A B y or setcar A B y replace A the address field of A B with y 1 rplaced A B y or setcdr A B y replace B the decrement field of A B with y I Sequence operator 1 progn set X y X or begin set X y X Set the value of x to be y then returns the value of x cs3723 Evaluation Using Expressions vs Statements El No side effect expressions no variable modifications I In Scheme define insert lambda X y cons X y insert 4 insert 3 0 I What is the result El Imperative programming in C void insert int x Cell y Cell 2 CellmallocsizeofCell z gtval y gtval z gtnext y gtnext y gtval x y gtnext z int main Cell y CellmallocsizeofCell ygtva1 ygtnextO insert3 y insert4 y n Evaluation order I Among pure expressions eprICIt In data flow a Can evaluate each expression as soon as values are ready Among statements implicit in side effects modifications error a Control flow among statements cannot be changed unless expressions are independent and no error cases could occur cs3723 Exercises Programming in LispScheme n Programming steps I What are the input parameters What values could each parameter take I Enumerate each combination of input parameters give a return value for each case n Exercise problems I Define a function Find which takes two parameters x and y It returns x if x appears in y and returns an empty list 0 otherwise I Define a function substitute which takes three parameters x y and 2 It returns a new list which replaces all occurrences x in y with z I Define a function Max which takes a single parameter x and returns the maximal number that appears in x C53723 10 Meta programming Programs As Data II Lisp program exp value variable exp exp exp Can be represented using Lisp atoms and lists I Can be built at runtime and then evaluated n An eval function used to evaluate contents of list I in Scheme need to choose a more advanced language level define atom lambda x or symbol x number x boolean x define substitute lambda x y z cond null z 2 atom 2 if eq 2 x y 2 else cons substitute x y car 2 substitute x y cdr Z define substituteandeval lambda x y z eval substitute x y z substituteandeval x 3 39 x 1 C53723 11 Higher Order Functions Function that either I takes a function as an argument or returns a function as a result I Firstorder functions parameters and results are not functions I Secondorder functions take as input or return firstorder functions I Thirdorder functions take as input or return secondorder functions El Examples I function composition lambda f g x f g x vs lambda f g lambda x f g x I maplist define maplist f x cond null x nil t cons f car x maplist f cdr x I Functions as firstclass objects I Functions treated same as primitive values What about CC I Can be used to build anonymous and higherorder functions C53723 12 Functions as Parameters El function composition lambda f g x f g x vs int composeint f int g int x return fgx El Apply a function to each element in a list define maplist f x cond null x nil else cons f car x maplist f cdr x vs Ce maplistint f Ce X if X NULL return NULL else Ce res Ce malloc sizeofCeI res gtvafx gtva res gtnextmapistfX gtnext return res C53723 13 Return functions as results El function composition define compose lambda f g lambda x f g x int composeint f int g int X return fgx VS a In Scheme I The function compose takes only two parameters I The result of compose is another function El in C I The function compose takes three parameters I The result of compose if a concrete value I C does not allow functions being returned as result why cs3723 The Lisp Abstract machine El Abstract machine I The runtime system lowlevel hardware machine or high level software simulated machine based on which a language is interpreted El Lisp Abstract machine I A Lisp expression the current expression to evaluate I A continuation the rest of the computation I A list variable gtvalue mapping I A set of cons cells the list data structure El pointed to by pointers in Alist a Each cons cell is a pair car cdr gt linked data structures lists atm a gt a single atom El Garbage collection I Automatic collection of non accessible cons cells C53723 15 Implementing Lisp The Memory Model El Cons cells Sharing n a b El Both structures could be printed as ABAB n Which are the results of evaluating I cons cons A B cons A B I lambda x cons x x cons A B n Equality of compound structures I What is the result of eq a a I What is the result of eq a b a b C53723 17 Garbage Collection Memory management at runtime I Maintains a list of available memory cells I Receive and satisfies allocation requests I When available space is below threshold 1 Invoke garbage collector El Garbage collection I Detecting memory cells no longer used a Reclaim memory cells C53723 18 CS 3723 SUPPLEMENTAL NOTES ON FORMAL LANGUAGES 2122008 Formal languages are not concerned with what anything means but rather only what is or is not a correctly formed sentence ie well formed formula wffquot in the language The sentences are simply sequences of symbols from some alphabet and do not have any inherent meaning A formal language is simply a possibly infinite set of the sequences that are in the language One way of describing a formal language is to give a grammar that says how to generates them Grammars consist of a set of rewriting production rules each consisting of two sequences of symbols Some of these symbols occur in at least one wff these are called terminals and some never do these are none terminals The general procedure is to start with some designated start symbol and apply one of the rewriting rules to get a sequence of symbols and keep on iteratively applying rewriting rules to a part of the sequence The left hand side of each rule must always contain at least one non terminal and the rewriting stops when one is left with a sequence made up entirely of terminal symbols All of the sequences that can be produced in this manner wff in the language described by the grammar For example we might define a language with Production Rules S gt wABx the start symbol is S wA gt y A the noneterminals are S A and B ABx a z the terminals are w x y and 2 There are exactly two wff in this language wz and yz wz can be produced using the derivation S gt wABX gt wz yz can be produced using the derivation S gt wABX gt yABX gt yz The class of languages that can be described with this type of grammar is known as l recursively enumerable languages If you the kinds of symbols that can ap pear on the left and right side and the relationships between the two sequences you can define other less general classes of formal languages Four of these are types of languages grammars in the Chomsky Hierarchy see Figure The most restricted class is the regular languages and all regular languages are also context free languages All context free languages are also context sensitive lan guages and all context sensitive languages are also recursively enumerable lan guages As an aside these languages can also be defined in terms of the ab stract machine required to look at a sequence of symbols and decide whether the sequence is or is not a wff for a given language To recognize arbitrary recursively enumerable languages requires a Turing machine For our purposes the most interesting class of languages is the context free lan guages The syntax of most programming languages can be and is described Types Classification of Values cs3723 Outline I General discussion of types I What is a type I Compile time vs run time type checking I Conservative program analysis I Type inference I Good example of static analysis algorithm I Will study algorithm and examples El Polymorphism I Polymorphism vs overloading I Uniform vs non uniform imp of polymorphism cs3723 Type A type is a collection of computable values that share some structural property I Examples El Non examples I Integers I 3 true Xxx Strings l Even integers I fint gtintifxgt3 I Int gtbool then fxgtxx 1 int gtint gt bool Distinction between sets that are types and sets that are not types is language dependent cs3723 3 Types in Programming El A type is a collection of computable values I Represent concepts from problem domain I Accounts banks employees students I Represent different implementation of values a Integers strings floating points lists records tuples ii Languages use types to I Support organization of concepts 1 Separate types for separate concepts from problem domain I Identify and prevent errors a Compiletime and runtime type checking a Prevent meaningless computation 3 true Bill I Support efficient translation by compilers a Short integers require fewer bits in Access record component by a known offset I Use integer units for integer operations cs3723 Values and Types El Basic types types of atomic values I int bool character real symbol I Values of different types 1 have different layouts u have different operations I Explicit vs implicit type conversion of values El Compound types types of compound values I List record array tuple struct ref pointer I Built from type constructors 1 int arr100 9 arr arrayint100 1 3 4 abc int int string 1 int x 9 x pointerint 1 int fint x return x 5 9 f int9int cs3723 Type Declaration and equivalence a Type declarations l Provide ways to introduce new types userdefined types I Transparent declarations Introduce a synonym for another type 1 typedef struct int a b mystruct u typedef mystruct yourstruct El Opaque declarations Introduce a new type I struct XYZ int a bc El Type equivalence struct 5 int ab struct t int ab Structural equivalence yes I s and t are the same basic type or n s and t are built using the same compound type constructor with the same components I Name equivalence no u S and t are different names 1 Names uniquely define compound type expressions I In C name equivalence for recordsstructs structural equivalence for all other types cs3723 The Type System El Each language has a type system that includes I A collection of basic types and compound types I Type declaration rules on how to introduce new types I For each basiccompound type rules on 1 How to build values of the type integerseg1233290 floating point numberseg 35 012 Symbols abc chars a b strings abc lists abc 3 Type constructors for arrays structs records etc a How to operate on values of the type Evaluation rules equality introduction and elimination operations Each operation is defined only on specific types of operands and returns only a specific type of values A type error occurs if an operation applied to operands outside its domain cs3723 7 Type Error I When a value is misinterpreted or misused with unintended semantics a type error I May cause hardware error function call x where x is not a function u may cause jump to instruction that does not contain a legal op code I May simply return incorrect value intadd3 45 u not a hardware error 1 bit pattern of 45 can be interpreted as an integer a just as much an error as x above cs3723 8 Type safety of languages n A language is type safe if it never allows any undetected type error to occur at runtime I Eg raise a runtime exception instead of segmentation fault I Which languages are type safe Which are not I BCPL family including C and C a Not typesafe casts pointer arithmetic I Algol family Pascal Ada 2 Almost typesafe n Dangling pointers pointers to locations that have been deallocated a No language with explicit deallocation of memory is fully typesafe I Typesafe languages with garbage collection a Lisp ML Smalltalk Java 1 Dynamically typed Lisp Smalltalk u Statically typed ML JAVA cs3723 9 Type Checking Type checking try to discover and report all type errors Can be done at compiletime or runtime or both Runtime type checking LispScheme perl Example in LispScheme when evaluating each car X 1 Check to make sure x is a non empty list Compiletime type checking ML Java CC In CCJava if a function f is declared int ffoat X n The compiler ensures that f is invoked only with float type expressions El Compiletime static vs Runtime dynamic Type Checking Both prevent type errors Runtime checking slows down execution and does not offer early error detection 1 Types of operands must be checked before each operation Compiletime checking restricts program flexibility and cannot discover all errors a Every variablestorage can hold only a single type of values Combination of compile and runtime checking 2 Example Java array bound check at runtime C53723 10 Flexibility vs Safety El In Lisp we can write function like lambda x if number x x 1 car x x could be a number or a list if x is a symbol a type error will occur cannot apply car to x Some uses will produce type error some will not El Static type checking is always conservative I Must define a different function for each input type int f1 int x return x 1 int f2 Intlist x return firstelemx do we need a different function for floating point lists C53723 11 Polymorphism I A function operator is polymorphic if it can operate on different types of input values Dynamic type checking supports arbitrary polymorphic functions I Can we support polymorphic functions in compiled languages El Parametric polymorphism Operate on types parameterized with type variables a a is syntax for type variable aquot u datatype a list nil cons of a a list nil a list cons a a list a a list I Ad hoc polymorphism operator overloading I Functions can be applied to different types use a different implementation for each type definition int gtint real gtreal El Subtype polymorphism Declare some type B to be the subtype of another type A I All functions that operate on A values can also operate on B values 1 Eg union types in C datatype in ML class inheritance and interface implementation in Java 1 Eg Truck and Car are both subtypes of Vehecle datatype Vehecle Truck of Car of How do you implement it in JavaC cs3723 12 Parametric vs Ad hoc Polymorphism n Parametric polymorphism type variables define first lambda X car X x a list any kind of list first a list 9 a A single implementation algorithm is used for all different types of input I Ad hoc polymorphism operator overloading define Add lambda X y if number y x y cons X y When applied to numbers x number y number Add numbernumber9 number When applied to lists x a y a list Add a a list 9 a list Different implementations x y vs cons x y are used for different types I Dynamically typed languages eg LispScheme supports both parametric and ad hoc polymorphism I What about CJavaC C53723 13 Static Type Checking Find Type Errors Without Running the Program El Program Analysis Tools I Try to derive properties of program without running the program I Try to find errors in programs without debugging I Growing area of commercial activity El Static type checking Declare types of variables a Each variable must have a single type It can hold only values of this type D Symbol table records the type of each variable Naming conflict use nested symbol tables Evaluate types of expressions 2 Every expression must have a single type It maps input values to a return value It can return only values of this type I A static type system 1 Include rules for deciding types of expressions These rules specify the proper usage of each operator 1 Accept only expressions that can be typed according to rules 1 May support explicit vs implicit type conversion C53723 14 Static Type Checking n Given an expression if we know the type of each variable what is the type of the expression define Add exp num cond null exp exp cons exp cons Add car exp num Add cdr exp num number exp exp num else exp Suppose we can get the type of each variable from a table exp int num int What is the type of Add exp num null exp 9 false cons exp 9 false number exp 9 true exp num 9 int C53723 15 More on Static Type Checking n In statically typed languages ML CCJava I Each variable has a single type 9 each expression has a single type I Eg in CC int f int a int b int c return a b c a int b int c int 9 abc int n In dynamically typed languages LispScheme I Each variable may have different types depending on the running context 9 each expression may have different types I Eg in Scheme lambda a b c a b c a int b int c int 9 abc int a float b int c int 9 a b c float a list b int c int 9 a b c typeerror cs3723 Static type checking and type inference El Static type checking int fint x return x1 int gint y return fy12 I Programmer has to declare the types of all variables I Compilers evaluate the types of expressions and check agreement a Type inference extension to static type checking 39 fiM return x1 MG return fy12 I Programmers are not required to declare types for variables I Compilers try to figure out agreeable types of all expressions in Find most general type by solving constraints I Lead to parametric polymorphism C53723 17 Type Inference a Without knowing anything about variables can we guess the type of each variable and the type of each expression define Add exp num cond null exp exp cons exp cons Add car exp num Add cdr exp num number exp exp num else exp Each pre defined operator requires its operands to have specific types Eg car x 9 x must be a list car expcdr exp 9 exp list exp num 9 exp number num number So exp could be a number or a list 9 type error in statically typed languages C53723 18 Type Inference n In CC suppose we don t need to declare variables fabcreturnabc intint9int 9 a int b int c int a b c int floatfloat9float 9 a float b float c float 9 type error I In Scheme expressions could have multiple types lambda a b c a b c numbernumber9number 9 a number b number c number a b number n In statically typed languages ML C C Java I When each operator has a single type definition we can automatically infer types of variables and expressions I When each operator has multiple type definitions evaluation rules type inference can easily fail 1 An operator is overloaded if it has multiple type definitions cs3723 19 Type Inference n Another example in Scheme define f lambda x 2 x gt f int 9 int El How does it work I has two types intint gtint realreal gtreal I 2 int has only one type I This implies intint gt int Therefore need x int Therefore fxint 2x has type int 9 int is overloaded because it has two types Most operators in a static type system have a single type In many cases unique type may be polymorphic C53723 20 Another Type Inference Example El Function Definition I definef lambda g x g g X gt f tettet Assume f t1 t2 gt rf Therefore g t1 X t2 g x requires g t2 gtrg therefore t1 t2gtrg g g x requires rg t2 therefore t1 t2gtt2 f returns g g x requires t2rf therefore f t1t2gtrf inplies that f t2gtt2t2gtt2 cs3723 21 Types Classification of Values cccc 23 Outline I General discussion of types I What is a type What is it used for I Basic vs compound types What is a type constructor I Type systems type errors type safety of languages I Type declarations and type equivalence a Type checking and type inference I Compile time vs run time type checking I Type environment and scopes I Compile time type checking and type inference El Polymorphism I Polymorphism vs overloading I Uniform vs non uniform impl of polymorphism cs3723 Type A type is a collection of computable values that share some structural property I Examples El Non examples I 3 true kxx Integers St n S Even Integers 39 r39 9 fint gtintifxgt3 I Int gtbool then fxgtxx1 int gtint gt bool Distinction between sets that are types and sets that are not types is language dependent cs3723 3 Types in Programming n A type is a collection of computable values I Represent concepts from problem domain a Accounts banks employees students I Represent different implementation of values a Integers strings floating points lists records tuples II Languages use types to I Support organization of concepts 1 Separate types for separate concepts from problem domain I Identify and prevent errors a Compiletime and runtime type checking a Prevent meaningless computation 3 true Bill I Support efficient translation by compilers a Short integers require fewer bits in Access record component by a known offset I Use integer units for integer operations cs3723 Values and Types El Basic types types of atomic values I int bool character real symbol I Values of different types 1 have different layouts u have different operations I Explicit vs implicit type conversion of values El Compound types types of compound values I List record array tuple struct ref pointer I Built from type constructors 1 int arr100 9 arr arrayint100 1 3 4 abc int int string 1 int x 9 x pointerint 1 int fint x return x 5 9 f int9int cs3723 A Deeper View The Type System n A language supports each type by I Providing ways to introduce values of the type I Literal integers 1 23 3290 n Literal floating point numbers 35 012 n Symbols abc chars a b strings abc u Lists abc 3 I Providing ways to operate on values of the type a Evaluation rules equality introduction and elimination operations a Every type comes with a set of operations I Each operation defined on specific types of operands and return a specific type of value a A type error occurs if operation applied to operands outside its domain a Type declarations I Provide ways to introduce new types userdefined types cs3723 Type Error a When a value is misinterpreted or misused with unintended semantics a type error occurs I May cause hardware error function call x where x is not a function u may cause jump to instruction that does not contain a legal op code I May simply return incorrect value intadd3 45 1 not a hardware error a bit pattern of 45 can be interpreted as an integer u just as much an error as x above cs3723 7 Relative typesafety of languages n BCPL family including C and C I Not safe casts pointer arithmetic n Algol family Pascal Ada I Almost safe I Dangling pointers u Pointers to locations that have been deallocated a No language with explicit deallocation of memory is fully type safe I Type safe languages with garbage collection I Lisp ML Smalltalk Java I Dynamically typed Lisp Smalltalk I Statically typed ML JAVA cs3723 Type Declaration and equivalence n Transparent declarations I Introduce a synonym for another type a typedef struct int a b mystruct n typedef mystruct yourstruct n Opaque declarations I Introduce a new type a struct XYZ int a bc a Type equivalence struct 5 int ab struct t int ab I Structural equivalence yes a s and t are the same basic type or u s and t are built using the same compound type constructor with the same components I Name equivalence no u S and t are different names a Names uniquely define compound type expressions I In C name equivalence for recordsstructs structural equivalence for all other types cs3723 Static vs Dynamic Typing El In Lisp we can write function like lambda x if number x x 1 car x x could be a number or a list if x is a symbol a type error will occur cannot apply car to X Some uses will produce type error some will not El Static typing is always conservative I Must define a different function for each input type int f1 int x return x 1 int f2 Intlist x return firstelemx do we need a different function for floating point lists cs3723 Compiletime vs Runtime Type Checking El Run time type checking LispScheme perl Example in LispScheme when evaluating each car X I Check to make sure x is a non empty list El Compile time type checking ML Java CC Example ML has strong type inference fx I In CCJava if a function f is declared int ffloat X a Value x must have type float n Both prevent type errors I Run time checking slows down execution I Compile time checking restricts program flexibility Lisp list elements can have different types ML list all elements must have the same type I Combination of compile and runtime checking 1 Example Java array bound check at runtime C53723 11 Program Analysis Tools a Growing area of commercial activity I Try to derive properties of program without running the program I Try to find errors in programs without debugging a Two kinds of analysis I Conservative Sound a If analysis says program is correct then it is u If analysis does not say correct program may be correct I Non conservative unsound 1 If analysis says correct it might be incorrect u If analysis says incorrect there is an anomaly I Applications 1 Conservative tools are for correctness n Nonconservative tools are for bug finding C53723 12 Type checking and type inference El Type checking int fint x return x1 int gint y return fy12 I Programmer has to declare the types of all variables I Compilers evaluate the types of expressions and check agreement a Type inference fC FE X return x1 mam y return fy12 I Programmers are not required to declare types for variables I Compilers try to figure out agreeable types of all epreSSIOI lS 1 Find most general type by solving constraints a Lead to polymorphism C53723 13 Find Type Errors Without Running the Program El Types of variables I Each variable must have a single type a It can hold only values of this type El Types of expressions I Every expression must have a single type i It maps input values to a return value a It can return only values of this type El Type system I Rules for deciding types of expressions 1 These rules specify the proper usage of each operator I Accept only expressions that can be typed according to rules I Explicit vs implicit type conversion C53723 14 Type environment a Symbol table I Record information about names defined in programs a Types of variables and functions a Additional properties eg scope of variable I Contain information about context of program fragment in Name conflicts I The same name may represent different things in different places a Separate symbol tables for names in different scopes a Multiple layers of symbol definitions for nested scopes n Implementation of symbol tables I Hash table from strings names to properties types C53723 15 Type Checking n Given an expression if we know the type of each variable what is the type of the expression define Add exp num cond null exp exp cons exp cons Add car exp num Add cdr exp num number exp exp num else exp Suppose we know the type of each variable in a symbol table exp int num int What is the type of Add exp num null exp 9 false cons exp 9 false number exp 9 true exp num 9 int C53723 16 Type Checking I In CC int f int a int b int c return a b c a int b int c int 9 abc int n In Scheme lambda a b c a b c a int b int c int 9 abc int a float b int c int 9 a b c float a list b int c int 9 a b c typeerror n In statically typed languages ML CCJava I Each variable has a single type 9 each expression has a single type i In dynamically typed languages LispScheme l Each variable may have different types depending on the running context 9 each expression may have different types cs3723 Type Inference ii Without knowing anything about variables can we guess the type of each variable and the type of each expression define Add exp num cond null exp exp cons exp cons Add car exp num Add cdr exp num number exp exp num else exp Each pre defined operator requires its operands to have specific types Eg car x 9 x must be a list car expcdr exp 9 exp list exp num 9 exp number num number So exp could be a number or a list 9 type error in statically typed languages C53723 18 Type Inference n In CC suppose we don t need to declare variables fabcreturnabc intint9int 9 a int b int c int a b c int floatfloat9float 9 a float b float c float 9 type error i In Scheme expressions could have multiple types lambda a b c a b c numbernumber9number 9 a number b number c number a b number n In statically typed languages ML C C Java I When each operator has a single type definition we can automatically infer types of variables and expressions I When each operator has multiple type definitions evaluation rules type inference can easily fail a An operator is overloaded if it has multiple type definitions C53723 19 Type Inference El Another example in Scheme define f lambda x 2 x gt f int 9 int El How does it work I has two types intint gtint realrea gtrea I 2 int has only one type I This implies intint gt int Therefore need x int Therefore fxint 2x has type int 9 int is overloaded because it has two types Most operators in a static type system have a single type In many cases unique type may be polymorphic cs3723 20 Polymorphism El A function operator is polymorphic if it can operate on different types of input values El Parametric polymorphism I Operate on types parameterized with type variables 1 a is syntax for type variable aquot u datatype a list nil cons of a a list nil a list cons a a list a a list i Ad hoc polymorphism operator overloading I Functions can be applied to different types use a different implementation for each type definition intgtint realgtreal El Subtype polymorphism I Inheritance in object oriented programming Truck is a subclass of Car void IncreaseSpeedCar c int incr cgtspeedincr Truck truck IncreaseSpeCe3c72gamptruck 50 21 Parametric vs Ad hoc Polymorphism El Parametric polymorphism type variables define first lambda X car X x a list any kind of list first a list 9 a A single implementation algorithm is used for all M erent types of Input El Ad hoc polymorphism operator overloading define Add lambda X y if number y x y cons X y When applied to numbers x number y number Add numbernumber9 number When applied to lists x a y a list Add a a list 9 a list Different implementations x y vs cons x y are used for different types El Dynamically typed languages eg LispScheme supports both parametric and ad hoc polymorphism I What about CJavaC C53723 22 Fundamantals Syntax and Semantics of Programming Languages cs3723 1 Syntax and Semantics n Syntax I The symbols and rules to write legal programs a Semantics I The meaning of legal programs a Programming language implementation I Syntax gt semantics I Translate program syntax into machine actions a Example date specification I Syntax a date dddddddd cl O123456789 I Semantics a 01022005 gt Jan 02 2005 or Feb 012005 cs3723 Describing Language Syntax n Lexical syntax I Spelling of words tokensterminals 1 Numbers strings names n Keywordsreserved words if while for else I Formal description regular expressions 1 Describe the composition of words a azAZazAZO9 0 9 while El Grammar syntax I Rules to compose programs from tokens n forStmt for exp exp exp quot stmt I Formal description context free grammar n More powerful than regular expressions 1 BNF Backus Naur Form cs3723 Why Describing Syntax n A translatorcompiler needs to understand programs via syntax analysis I Needs to implement syntax analysis in CCJava etc El Why does the syntax need to be formally de ned a Regular expressions and BNFs are themselves languages for describing language syntax I Supports communications between programmers and translatorscompilers I Supports automated generation and validation of syntax analyzers Every configurable automation requires an interface language cs3723 Describing Semantics n Informal definitions l Tutorials learn by working examples Reference Manuals 1 Natural language explanation for each syntax rule El Formal definitions skip I Attribute grammars El Associate attributes values with each grammar symbol 1 Associate semantics rules with each grammar rule I Operational semantics u Interpret the language on an abstract machine or using another language Denotational semantics 1 Define language constructs as mathematical functions Axiomatic semantics proof rules 1 Define properties invariance of language constructs a Goal communication automation and validation cs3723 Contextfree Grammar n A context free grammar includes I A set of terminalstokens atomic symbols I A set of nonterminals compound constructs I A set of productions 1 Rules identifying components of a construct a Each production has format A B where A is a single non terminal B is a sequence of terminals and non terminals I A start nonterminal the toplevel construct of the language I Example contextfree grammar of expressions eneee eeeee ndnd d0123456789 Non terminals e n d Terminals O123456789 Start symbol e What language does the grammar describe cs3723 What language aspects can be defined by CFG El Can we use CFG to define more than just syntax me num string id ee El Support both alternative and recursion El Cannot incorporate context information I Cannot determine the type of variable names a Declaration of variables is in the context symbol table I Cannot ensure variables are always defined before used int w 0 w forw 1wlt 100w 2w a c 3 II acw cs3723 7 Derivations and Parse Trees Semantics of CFG n Derivation top down replacement of non terminals l Each replacement follows a production rule I One or more derivations for each program I Derivations for 5 15 20 n egteegteeegtneegtdeegt5eegt5negt5nd egt5ddegt51degt515egtgt51520 u Egteegtgt5egt5eegtgt515egtgt51520 Parse trees e e eie te Q e Uq1 Cl L D Q N Q O Q l 033 U39I cs3723 8 Parse Trees El A parse tree of each program satisfies I Each leaf node represents a terminal I Each nonleaf node represents a nonterminal I The children of each nonleaf node A from left to right form the rightside of a production rule for A with A at leftside I The root of the parse tree is the starting nonterminal Can you build a checker that reports whether a parse tree for a particular grammar is correct What are required El A parse tree represents a syntactically correct program I Regenerates a program reading terminals at its leaves from left to right i Parsing checking syntactical correctness I Constructing a parse tree for a program El Topdown and bottomup parsers cs3723 Abstract vs Concrete Syntax in Concrete syntax the syntax that programmers write I Example different notations of expressions in Prefix 5 15 20 u Infix 5 15 20 n Postfix 5 15 20 in Abstract 5 ntax the program structure recognized by compilers interpreters I Identifies only the meaningful components a What is the operation and which are the operands Parse Tree fOF e lAbstract Syntax Tree for 5 15 20 51520 ele ei 5 5 l 2 0 1 2 0 C53723 10 Abstract syntax trees El Condensed form of parse tree for representing language constructs l Operators and keywords do not appear as leaves El They define the meaning of the interior parent node I Chains of single productions may be collapsed IF BTHEN S1 ELSE 2 Air 139 5 3 5 3 C53723 11 Exercises parse trees and syntax trees El Grammar for expressions I e n ee e e eeeee I What are the terminals and nonterminals I Write parse trees and ASTs for 111 and 1231 Grammar e 0 1 0e 1e I What language does the grammar describe I Write parse trees and ASTs for 011100 Steps for building parse trees I Write down the start nonterminal I Pick a nonterminal in the tree pick a production replace the non terminal by expanding the subtree El Which production tofpick the one that describes the structure of the current input or the given nonterminal Parse tree gt AST I Replace each nonterminal with an operator one for each production I Remove useless tokens those that don t have values I Collapse chains of single productions C53723 12 Ambiguous Grammars n A grammar is syntactically ambiguous if I some program has multiple parse trees a Multiple choices of production rules during derivation El Consequence of multiple parse trees I Parse trees are used to interpret programs 1 Multiple ways to interpret a program ejbe fix e e n r nr is ri Mn 3 mi lgi My 3 51 MN 1 2 1 2 cs3723 Rewrite ambiguous Grammars El Solutionl introduce recedence and associativity rules to dictate the choices 0 applying production rules I Original grammar e n ee e e ee ee I Precedence and associativity u gtgt all operators are left associative I Derivation for nnn u egteegtnegtneegtnnegtnnn n Solution2 rewrite production rules by introducing additional non terminals I Alternative grammar E T E T T TFTFF n E T F I Derivation for n n n n EgtETgtTTgtFTgtnTgtnTFgtnFFgtnnFgtnnn I How to modify the grammar if n and has high precedence than and a All operators are right associative cs3723 Writing CFGS El Give a CFG to describe the set of strings over which form balanced parenthesesbrackets For example I O O 00 and are in the language I 0 and are not in the language El Give the parse tree and AST for input 00 I If your grammar ambiguous If yes prove it by giving two different parse trees for a single input Rewrite it to be nonambiguous Here we are practicing programming using BNF El Fundamental concepts variables nonterminals and recursmn I Define a clear meaning in English for each nonterminal I Use recursion to implement the meaning I Need to know how to describe a sequence of items and how to ensure an item appears some number of times I Ambiguity introduce a new nonterminal for each precedence l Recursive on the left if leftassociative recurive on the right otherwise C53723 15 Additional exercises El Give a context free grammar for a small graph description language I Terminals digits 039 139 939 39 39 39 and gt39 I Each node of the graph is represented by an integer number I Each edge is represented by a pair of nodes connected with gt39 in eg 3gt4 is an edge from node 339 to node 439 I Each graph description is a sequence of edges u Eg 1gt22gt5 5gt1 El Write a parse tree and an abstract syntax tree for 1gt2 2gt5 5gt1 C53723 16 Tm lzy m Principles anrngamming Languages xxu Wuh mlxuln 20mm n m Wm WM am M 1 Ammuwmmmgmamm mmmm mm mmmmmmmd WWI sym N ma a AWN 7 WWMW y m xyxymum kw WNW mm mm A n sx9 y x mm 3142 d ffmnyli f39 m mlmmmy Grammar context free A context free grammar CFG is a grammar in which X 1 ie X is a single nonterminal 7 LHS l nonterminal 7 RHS a sequence of terminals and nonterminals E r g s gtab CFG SAgtab nonCFG CFG is suf cient to describe most of the constructs in programming languages Programming languages describable by CFG are recognizable by push down automata analogues toFSA with a stack Grammar backus Naur form Backus N aur Form BNF is a metalanguage for describing programming languages A BNF grammar is a context free grammar Notation 7 Nonterminals are enclosed in angle brackets i e lt and gt 7 Uses 3 instead of 9 in productions 7 Productions having the same le hand side can be grouped together using the alteration symbol eg ltsgt altsgt b ltsgtl 7 Lists are described using recursive rules A rule is recursive if its le hand side appears on the righthand side eg ltident1istgt identi er identi er ltident1istgt Grammar BNF recursive rules Left Recursive BNF Grammar 7 A BNF grammar rule is left recursive if its LHS appears at the left end of the RHS e g ltident1istgt ltident1istgt identi er identi er eg A9Axly yxx A A x A x Right Recursive BN F Grammar 1 7 A BNF grammar rule is right recursive if its LHS appears at the right end of the RHS eg ltident1istgt identi er identi er ltident1istgt eg A9xAlyxxy A The order of remrsion has implications on the order of evaluation and assodativity Grammar extended BNF Notation 7 Anyone ofthe alterations 7 Optionalpart 7 oror 7 39 or39or39 repeat zero or more times repeat one or more times 7 x or x terminal symbol 7 Unquotedwords nonterminal symbol Example 7 Using the above notation lt expression gt lt expression gt ltterm gt lt expression gt lt term gt lt term gt could be written in the form of an iteration as follows lt expression gt lt term gt l lt term gt Grammar de nitions Sentence a finite sequence of terminals constructed according to the rules of the grammar for that PL Sententialform a finite sequence of terminals and nonterminals constructed according to the rules of the grammar for that PL Derivation Parse Grammar derivation 2 ltdigilgt 0ll23145l678 9 quot ltlettergt ltidentiliergt ltlettergt ltidemiliergt ltcligilgt w A a r 4 ltassignstmtgt ltidenlil39iergt 0 Can we generate x2 0 from these rules ltassignstmtgt gt4 ltideutifiergt 0 gt3e ltidentii39iergt ltdigilgt U gt3a ltleltergt ltdigitgt 0 gt1 x ltdigilgt 0 gt2 2 0 YES This is a derivation of a L Ilt ll 39t39 in the language described by the grammar ahm e Each sequence in this deriVation is a wiltwlillimn This is a ellum or eummirnl Ivriruliun At each step the rule imlicaled is used to substilule the rhs ot39lhe rule for the lel39lmost uoutenuinal in the scnlenlial l39urm Grammar parsing 1H t39 2 ltligilgt 0 23H5167l8l9 3 ltidenlifiergt ltlettergt ltidentifiergt ltleltergt ltirlenlifiergt ltligilgt 4 ltassignstmtgt ltidentit39iergt 0 Can we recognize X2 0 as belonging to this PL X2 0 gt ltlettergt 2 0 rule 1 gt ltidentil iergt Z 0 rule 3a gt ltidemit39iergtltligitgt 0 rule 2 r ltidenlitiergt 0 rule 3e gt ltassignstmtgt rule 4 A parse of the sentence x2 0 Grammar building parse trees X2 0 gt ltlettcrgt 2 0 rule 1 ltideutifiergt 2 0 rule 3a ltHssigmstmgt gt ltideutifiergtltdigitgt 0 rule 2 gt ltideutifiergt 0 rule 34 ltidenli ugt 0 a ltassigustmtgt rule 39I ltidentifie1gt ltl Ti In parse tree each internal node ltlettergt is a nonterminal its children i are the rhs of a rule for that x nonterminal A parse tree describes the hierarchical syntactic structure of the sentence based on a given language Grammar grammars are not unique 1 ltlettergt alhlcldlel glllliljlkllImlnIolplqlrlsltluIvlwlxlylz 2 ltdigitgt 0ll2l3l4l56l7l8l9 3 ltidgt ltlettergt ltidgt ltletterordigitgt 4 ltassignstmtgt ltidgt 0 5 ltlettcrordigitgt ltlettergt ltdigitgt This grammar generates the same language ie set of trees whose frontiers are the same but has different parse trees than the previous grammar 2nd grammar tree 15 grammar tree ltassignslmlgt ltidgt 0 ltassignslmlgt ltidunlil39icrgt l ltidgt ltlcttcrordigitgt ltidunlifiergt difib ltIeltcrgt ltdigilgt X 2 ltlcltcrgt 2 X Many grammars can correspond to 1 PL but only 1 PL should correspond to any uxeful grammar Grammar ambiguity i li hig il ill Infra illquot 2 1Fi1 lurm E lllillllll uljllll39i i nl lrmm llEI39 jllli39l39vll lil39li I E purlE rural Hr sillr hauntquot wnbrnw lhrn Ilw grammar in urnmigrator There is no algorithm which can examine an arbitrary contextfree grammar and tell if it is ambiguous or not This is undecidable There is no algorithm which can examine two arbitrary contextfree grammars and tell if they generate the same language This is undecidable guous 39 Sometimes we can remove an ambiguity from a grammar by restructuring the productions but it is not always possible An inherently ambiguous language does not possess an unambiguous grammar EgLaibick ij orj kforijkgtl generated by grammar SLCAD LaLbab C c I CC D ch bc A a aA S parsc recs for 217 b c in L 5K problem is L contains a Iion cmitcxtfrcc L 391 language 21 bquotc n gt 1 grammar 0 com l I y L C C a A b D L y I l L c C a A b D 39 L l b C a a a b b b Grammar sources of ambiguity Associativity and precedence of operators Solution 0 Change the grammar to re ect operator precedence XY Z means XY Z Extent of a substructure E g Dangling else Solution Obscure recursion Eg 0 exp expexp A 9AB Solution Grammar is this ambiguous lt assign gt lt identifier gt lt expression gt lt identi ergt AlBlC lt expression gt lt expressiongt lt expression gt l lt expression gt lt expressiongt l lt expression gt l lt identi ergt Grammar is this ambiguous lt assign gt lt identi ier gt lt expression gt lt identi ergt AlBlC lt expression gt lt expressiongt lt expression gt l lt expression gt lt expressiongt l lt expression gt l lt identi ergt Yes because the sentence A B C A has two different parse trees The grammar does not force quotnormalquot lefttoright evaluation of addition and subtraction lt assign 2 lt I lt izvnii39 for gt lt ex n39vw un gt lt identifier gt lt mprcssioii gt If 1 A 7 L39Y I L39Siril gt lt L3939I 39iuii gt A lt L I FV llil gt e lt expression gt 439 gt 391 H lt identifier gt lt m pi39z ssion gt 7 lt 139739ei39ui1 gt 394 quot 7quot quot gt WWW 1quot quotMWquot 139 9 B lti1Uni39 m39 gt lt menMr gt lt izluni39li ei39 gt lt Icniiiei39 gt A C A B C Grammar is it really a problem The operation of addition is associative in mathematics Hence A B C can be performed as either ABC or ABC The multiply operation is also associative Therefore one might say the previous ambiguous grammar would be satisfactory for addition and multiplication But would it Computer arithmetic is not exact and one might want be able to control the order Grammar an unambiguous version lt assign gt lt identi er gt lt expression gt lt identi er gt AlB lC lt expression gt lt expression gt lt term gt l lt expression gt lt term gt l lt term gt lt term gt lt term gtltfactor gtl ltfactor gt ltfactor gt lt expression gt l lt identi er gt LIN Tree for A B C A lt i39tuiiliiel39 gt lt expression gt A lte pi uui mlgt ltM39m gt lt leim gt x IUII39III gt iilL39IUI gt lt fiiz tm gt lt fili39roi39 lt i39zi illiiei39 gt lt1 i39deiiliiui39 gt2 irlcilli39li39ei39 gt A D f CS 37233721 A List of Rational Numbers This example uses exactly the same classes List and CompList from earlier examples to provide a generic list of items so these classes are not shown again here Listed below are a class Rational to implement the rational numbers themselves a new version of GetData to read rational numbers and a slightly altered class with a main method RationalListMain Rationaljava Represent rational number with numerator and denominator public class Rational implements Comparab e private int numerator private int denominator Rational ensuring a nonzero denominator make only numerator signed public Rationalint numer int denom if deno O denom l Make the numerator quotstorequot the sign if denom lt O numer numer l denom denom l numerator numer denominator denom reduce add add two rational numbers public Rational addRational op2 int commonDenominator denominator op2getDenominator int numeratorl numerator op2getDenominator int numerator2 op2getNumerator denominator int sum numeratorl numerator2 return new Rational sum commonDenominator subtract subtract two rational numbers public Rational subtractRational op2 int commonDenominator denominator op2getDenominator int numeratorl numerator op2getDenominator int numerator2 op2getNumerator denominator int difference numeratorl numerator2 return new Rationaldifference commonDenominator multiply multiply two rational numbers public Rational multiplyRational op2 int numer numerator op2getNumerator int denom denominator op2getDenominator return new Rationalnumer denom divide divide two rational numbers public Rational divideRational op2 return multiplyop2reciprocal reciprocal take reciprocal public Rational reciprocal return new Rationaldenominator numerator getNumerator return the numerator public int getNumerator return numerator getDenominator return the denominator public int getDenominator re urn denominator equals check for equality public boolean equalsRational op2 return numerator op2getNumerator ampamp denominator op2getDenominator toString convert to String public String toString String result if numerator 0 result else if denominator result numerator IIquot e1s result numerator quotquot denominator return result reduce reduce to lowest terms private void reduce 39 numerator 0 int common gcd Mathabsnumerator denominator numerator numerator common denominator denominator common gcd greatest commmon divisor private int gcdint numl int num2 while numl num2 if numl gt num2 numl numl num2 else num2 num2 numl return numl compareTo the method in Comparable interface public int compareToObject obj Rational diff thissubtractRationa1obj if diffnumerator 0 return 0 else if diffnumerator lt 0 return 1 else return 1 Fundamantals 1 Syntax of Programming Languages cccc 23 Syntax and Semantics n Syntax I The symbols and rules to write legal programs a Semantics I The meaning of legal programs a Programming language implementation I Syntax gt semantics I Translate program syntax into machine actions a Example date specification I Syntax a date dddddddd cl O123456789 I Semantics a 01022005 gt Jan 02 2005 or Feb 012005 cs3723 Describing Language Syntax El Lexical grammar I Spelling of words tokensterminals 1 Numbers strings names n Keywordsreserved words if while for else I Formal description regular expressions 1 Describe the composition of words a azAZazAZO9 0 9 while El Context free grammar I Rules to compose programs from tokens n forStmt for exp quot exp quot exp quot stmt I Formal description BNF Backus Naur Form 1 More powerful than regular expressions cs3723 Why Describing Syntax n A translatorcompiler needs to understand programs via syntax analysis I Needs to implement syntax analysis in CCJava etc El Why does the syntax need to be formally de ned I Support communications between programmers and translatorscompilers I Support automated generation and validation of syntax analyzers Every automation requires an interface language I Regular expressions and BNFs are themselves languages for describing language syntax cs3723 4 BNF Expressing Contextfree Grammars a Each BNF includes I A set of terminals the wordstokens of the language I A set of nonterminals variables that could be replaced with different sequences of terminals I A set of productions n Rules identifying the structure of each nonterminal a Each production has format A B where A is a single non terminal B is a sequence of terminals and non terminals I A start nonterminal the toplevel syntax of the language I Example BNF for expressions eneee eeeee ndnd dquot0123456789 I Non terminals e n d start nonterminal e I Terminals O123456789 I What language does the grammar describe cs3723 What language aspects can be defined by CFG El Can we use CFG to define more than just syntax me num string id ee El Support both alternative and recursion El Cannot incorporate context information I Cannot determine the type of variable names a Declaration of variables is in the context symbol table I Cannot ensure variables are always defined before used intw Ow for w 1 w lt 100 w 2w a c 3 a c w cs3723 Derivations and Parse Trees Semantics of CFG Derivation top down replacement of non terminals l Each replacement follows a production rule I One or more derivations for each valid program I Derivations for 5 15 20 n egteegteeegtneegtdeegt5eegt5negt5nd egt5ddegt51degt515egtgt51520 u Egteegtgt5egt5eegtgt515egtgt51520 Parse trees e e eH Ax wk e it i vi cl M at U39I N4 94 34 3x cs3723 7 Parse Trees El A parse tree of each program satisfies Each leaf node represent a terminal I Each nonleaf node represent a nonterminal I The children of each nonleaf node A from left to right form the rightside of a production rule for A with A at leftside I The root of the parse tree is the starting nonterminal I A parse tree represents a syntactically correct program I Regenerates a program reading terminals at its leaves from left to right I Parsing checking syntactical correctness I Constructing a parse tree for a program a Topdown and bottomup parsers cs3723 Exercises Building Parse trees El Grammar for expressions e n ee e e eeeee What are the terminals and nonterminals Write parse trees for 111 and 1231 El Grammar e 0 1 De I 1e What language does the grammar describe I Write parse trees for 011100 El Steps for building parse trees I Write down the start nonterminal l Pick a nonterminal in the tree pick a production replace the nonterminal by expanding the subtree n Which production to pick the one that describes the structure of the current input for the given nonterminal cs3723 Abstract vs Concrete Syntax El Concrete syntax the syntax that programmers write I Example different notations of expressions n Prefix 5 15 20 u Infix 5 15 20 n Postfix 5 15 20 El Abstract syntax the program structure recognized by compilersinterpreters I Identifies only the meaningful components I What is the operation and which are the operands girlsggge for e ie lAbstract Syntax Tree for 5 15 20l i gt i e e 5 l 5 15 20 15 20 C53723 10 Abstract syntax trees El Condensed form of parse tree for representing language constructs l Operators and keywords do not appear as leaves 1 They define the meaning of the interior parent node I Chains of single productions may be collapsed S Ifthenelse A A SZ a 3 SL1 2 IF BTHEN S1 ELSE IE 139 5 lt 3 5 3 C53723 11 Exercises Building AST Grammar for expressions I e n ee e e eeeee I What are the terminals and nonterminals I Write parse trees and ASTs for 111 and 12 31 El Grammar e 0 1 De I 1e I What language does the grammar describe I Write parse trees and ASTs for 011100 a Parse tree gt AST I Replace each nonterminal with an operator one for each production I Remove useless tokens those that don t have values I Collapse chains of single productions C53723 12 Ambiguous Grammars n A grammar is syntactically ambiguous if I some program has multiple parse trees a Multiple choices of production rules during derivation El Consequence of multiple parse trees I Parse trees are used to interpret programs a Multiple ways to interpret a program in e We le W Q4 34 D d E HQ33 N4 Q4 34 3 o o cs3723 Rewrite ambiguous Grammars El Solutionl introduce recedence and associativity rules to dictate the choices 0 applying production rules I Original grammar e n I Precedence and associativity u gtgt all operators are left associative I Derivation for nnn u e gteegtne gtneegtnnegtnnn ee e e eeee n Solution2 rewrite production rules by introducing additional non terminals I Alternative grammar E E T E T T TTFTFF F n I Derivation for n n n n EgtETgtTTgtFTgtnTgtnTFgtnFFgtnnFgtnnn I How to modify the grammar if n and has high precedence than and a All operators are right associative cs3723 Writing CFGS El Give a CFG to describe the set of strings over which form balanced parenthesesbrackets For example I O Oquot 00 and quot are in the language I 0 and are not in the language El Give the parse tree and AST for input 00 El If your grammar ambiguous If yes prove it by giving two different parse trees for a single input Rewrite it to be nonambiguous Here we are practicing programming using BNF El Fundamental concepts variables nonterminals and recursmn I Define a clear meaning in English for each nonterminal Use recursion to implement the meaning i Need to know how to describe a sequence of items and how to ensure an item appears some number of times El Ambiguity introduce a new nonterminal for each precedence l Recursive on the left if leftassociative recurive on the right otherwise C53723 15 Additional exercises El Give a context free grammar for a small graph description language I Terminals digits 039 139 939 39 39 39 and gt39 I Each node of the graph is represented by an integer number I Each edge is represented by a pair of nodes connected with gt39 n eg 3gt4 is an edge from node 339 to node 439 I Each graph description is a sequence of edges u Eg1gt22gt55gt1 El Write a parse tree and an abstract syntax tree for 1gt2 2gt5 5gt1 C53723 16

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.