Difference between revisions of "CS522  Programming Language Semantics (Fall 2018)"
(→Lecture Notes, Useful Material) 
(→Lecture Notes, Useful Material) 

(30 intermediate revisions by one user not shown)  
Line 5:  Line 5:  
CS522 is an advanced course on semantics of programming languages. Various semantic approaches and related aspects will be defined and investigated. Executable semantics of various programming languages and paradigms will be discussed, together with major theoretical models.  CS522 is an advanced course on semantics of programming languages. Various semantic approaches and related aspects will be defined and investigated. Executable semantics of various programming languages and paradigms will be discussed, together with major theoretical models.  
−  * ''Meetings'':  +  * ''Meetings'': Tu/Th 9:30  10:45, 1103 Siebel Center 
* ''Professor'': Grigore Rosu (Office: SC 2110, WWW: http://fsl.cs.illinois.edu/grosu, Email: grosu@illinois.edu)  * ''Professor'': Grigore Rosu (Office: SC 2110, WWW: http://fsl.cs.illinois.edu/grosu, Email: grosu@illinois.edu)  
* ''Office hours'': By appointment, very flexible (held by Grigore Rosu in SC 2110)  * ''Office hours'': By appointment, very flexible (held by Grigore Rosu in SC 2110)  
Line 21:  Line 21:  
:* '''''Conventional Semantic Approaches'''''  :* '''''Conventional Semantic Approaches'''''  
::* {{pdfCS522Fall2018ConventionalExecutableSemantics.pdfSlides (PDF)}} {{zipCS522Fall2018ConventionalExecutableSemantics.pptxSlides (PPTX)}} <font color=red>(incomplete)</font>  ::* {{pdfCS522Fall2018ConventionalExecutableSemantics.pdfSlides (PDF)}} {{zipCS522Fall2018ConventionalExecutableSemantics.pptxSlides (PPTX)}} <font color=red>(incomplete)</font>  
+  ::* {{pdfCS522Fall2018basicsemantics.pdfBook material on IMP, BigStep SOS, SmallStep SOS, and Denotational Semantics}}  
::* '''''Rewriting Logic and Maude'''''  ::* '''''Rewriting Logic and Maude'''''  
+  :::* {{pdfCS522Fall2018Maude.pdfslides}}  recommended only for a quick look  
+  :::* {{pdfCS522Fall2018Maudebook.pdfBook material}}  recommended  
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW1 (due Tuesday, September 18)</font>''''' [[Image:downarrow.png]]  
+    
+   The following exercises are from the book material above. Do them only in Maude (that is, ''not'' on paper) by modifying {{zipCS522Fall2018MaudeHW1.zipthe provided Maude code for HW1}}): Exercise 56 (page 137); Exercise 70 (page 155).  
+  In case you are not familiar with Maude, you are encouraged to do the following exercises to warmup (but please do not include them as part of your HW1 submission): Exercise 30; Exercise 32; Exercise 33; Exercise 35; Exercise 36. All at pages 80/81.  
+  }  
+  
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW2 (due Wednesday, October 3  easy HW, so earlier submission possible and appreciated)</font>''''' [[Image:downarrow.png]]  
+    
+   The following exercises related to denotational semantics are from the book material above: Exercises 80, 81, 82 ((page 168; write these up on paper, or in a PDF); Exercise 83 (page 169; do it only in Maude (that is, ''not'' on paper) by modifying {{zipCS522Fall2018MaudeHW2.zipthe provided Maude code for HW2}}).  
+  }  
+  ::* {{pdfCS522Fall2018IMP++.pdfBook material on IMP++: Challenging BigStep SOS, SmallStep SOS, and Denotational Semantics}}  
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW3 (due Monday, October 15)</font>''''' [[Image:downarrow.png]]  
+    
+   Combine all the individual extensions of IMP in {{zipCS522Fall2018MaudeHW2.zipthe provided Maude code for HW3}} into the IMP++ language. Read the book material above for all the technical details. You should create a subfolder of imp called 6imp++, and that should have four subfolders, one for each semantic style. Provide also three IMP++ programs.  
+  }  
+  ::* {{pdfCS522Fall2018MSOSRSECCHAM.pdfBook material on Modular SOS, Evaluation Contexts, and the CHAM}}  
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW4 (due Monday, October 29)</font>''''' [[Image:downarrow.png]]  
+    
+   Same as HW3 but for the three additional semantic approaches discussed in the lecture notes above: MSOS, RSEC, and CHAM. Use {{zipCS522Fall2018MaudeHW4.zipthis provided Maude code for HW4}}. Handle also a short essay discussing the advantages and limitations of each of the semantic approaches discussed so far in class, assigning a (justified) score between 1 and 10 to each of them.  
+  }  
+  
+  :* '''''Category theory: definition, diagrams, cones and limits, exponentials'''''  
+  ::* {{pdfCS522Fall2018CategoryTheoryslides.pdfSlides}}  
+  ::* {{zipCS522Fall2018HandWrittenCategoryTheory.zipHand written notes on category theory properties}}  
:* '''''Lambda Calculus and Combinatory Logic'''''  :* '''''Lambda Calculus and Combinatory Logic'''''  
+  ::* {{pdfCS522Fall2018Lambdaslides.pdfSlides}}  
+  ::* {{pdfCS522Fall2018Lambda.pdfBook material on Lambda Calculus and Combinatory Logic}}  
+  ::* {{zipCS522Fall2018HandWrittenCCCuntypedlambda.zipHand written notes on CCC models of untyped Lambda Calculus}}  
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW5 (due Monday, November 12)</font>''''' [[Image:downarrow.png]]  
+    
+   This is a theoretical HW, requiring you to do three proofs using category theory. You are strongly encouraged to do *all* the exercises in the slides, especially if you did not have prior experience with category theory. However, for his HW, only handle the following three exercises: (1, easy) Exercise 8 on slide 20 in the {{pdfCS522Fall2018CategoryTheoryslides.pdfcategory theory slides}}; (2, easy) Property 1 on `category theory  3.png` in the {{zipCS522Fall2018HandWrittenCategoryTheory.ziphand written notes on category theory properties}}; and (3, harder) Lemma on slide `cccuntypedlambda  3.png` in the {{zipCS522Fall2018HandWrittenCCCuntypedlambda.ziphand written notes on CCC models of untyped lambda calculus}}.  
+  }  
:* '''''SimplyTyped Lambda Calculus'''''  :* '''''SimplyTyped Lambda Calculus'''''  
−  ::*  +  ::* Basic notions: type system, equational semantics, models, completeness. {{pdfCS522Fall2018SimplyTypedLambdaCalculus.pdfSlides}} 
−  ::* Cartesian Closed Categories as models for simplytyped lambdacalculus.  +  ::* Cartesian Closed Categories as models for simplytyped lambdacalculus. {{pdfCS522Fall2018PLCCC.pdfSlides}} 
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>HW6 (due Friday, November 30can also take the weekend if needed)</font>''''' [[Image:downarrow.png]]  
+    
+   Proposition 8 from the slides on simplytyped lambda calculus. Exercises 5 and 6 from the slides on CCCs.  
+  }  
:* '''''Recursion, Types, Polymorphism'''''  :* '''''Recursion, Types, Polymorphism'''''  
−  ::* Recursion and Types.  +  ::* Recursion and Types. {{pdfCS522Fall2018Recursion.pdfSlides}} 
−  ::* Polymorphism.  +  ::* Polymorphism. {{pdfCS522Fall2018Polymorphism.pdfSlides}} 
+  { border="1" cellpadding="5" cellspacing="0" width="100%"  
+  ! style="background:#ccddcc;" align="left"  '''''<font color=red>ExtraCredit (due Monday, Dec 17) </font>''''' [[Image:downarrow.png]]  
+    
+   This can be regarded as "Final exam", but it only counts as HW (and not project) extracredit and has the same weight as any of the previous HWs. If you got perfect score so far for the 6 HWs above, then you do not need to do this extracredit. Choose one, and only one, of the following and do it well (you will get either 10 or 0 for this extracredit problem!):  
+  <br> (1) Complete this {{zipCS522Fall2018LambdaExtra.zipLAMBDA code snippet}}. This covers knowledge about untyped lambdacalculus, fixedpoints, combinatory logic, and de Bruijn nameless representations.  
+  <br> (2) Consider the PCF language with callbyvalue (note that the slides above define the callbyname variant). Give it a smallstep, a bigstep, and a denotational semantics in Maude, using the representations of these semantic approaches discussed in the first part of the class. Provide also 5 (five) PCF programs that can be used to test all three of your semantics. You can use the builtins provided as part of the previous HWs (you should only need the generic substitution from there).  
+  <br> (3) This has two problems. The first is to define a type checker for the parametric polymorphic lambdacalculus (or System F). The second is to define a type checker for the subtype polymorphic lambdacalculus. In both cases, make sure that you also include the conditional and a few examples showing that your definition works. Feel free to pick whatever syntax you want for the various constructs (both for terms and for types).  
+  } 
Latest revision as of 14:41, 6 December 2018
Students enrolled in this class are expected to check this web page regularly. Lecture notes and important other material will be posted here.
[edit] Course Description
CS522 is an advanced course on semantics of programming languages. Various semantic approaches and related aspects will be defined and investigated. Executable semantics of various programming languages and paradigms will be discussed, together with major theoretical models.
 Meetings: Tu/Th 9:30  10:45, 1103 Siebel Center
 Professor: Grigore Rosu (Office: SC 2110, WWW: http://fsl.cs.illinois.edu/grosu, Email: grosu@illinois.edu)
 Office hours: By appointment, very flexible (held by Grigore Rosu in SC 2110)
[edit] Piazza Page
[edit] Lecture Notes, Useful Material
The links below provide you with useful material for this class, including complete lecture notes. These materials will be added by need and more topics will be added.
 Conventional Semantic Approaches
 Slides (PDF) Slides (PPTX) (incomplete)
 Book material on IMP, BigStep SOS, SmallStep SOS, and Denotational Semantics
 Rewriting Logic and Maude
 slides  recommended only for a quick look
 Book material  recommended
HW1 (due Tuesday, September 18) 

The following exercises are from the book material above. Do them only in Maude (that is, not on paper) by modifying the provided Maude code for HW1 ): Exercise 56 (page 137); Exercise 70 (page 155).
In case you are not familiar with Maude, you are encouraged to do the following exercises to warmup (but please do not include them as part of your HW1 submission): Exercise 30; Exercise 32; Exercise 33; Exercise 35; Exercise 36. All at pages 80/81. 
HW2 (due Wednesday, October 3  easy HW, so earlier submission possible and appreciated) 

The following exercises related to denotational semantics are from the book material above: Exercises 80, 81, 82 ((page 168; write these up on paper, or in a PDF); Exercise 83 (page 169; do it only in Maude (that is, not on paper) by modifying the provided Maude code for HW2 ). 
HW3 (due Monday, October 15) 

Combine all the individual extensions of IMP in the provided Maude code for HW3 into the IMP++ language. Read the book material above for all the technical details. You should create a subfolder of imp called 6imp++, and that should have four subfolders, one for each semantic style. Provide also three IMP++ programs. 
HW4 (due Monday, October 29) 

Same as HW3 but for the three additional semantic approaches discussed in the lecture notes above: MSOS, RSEC, and CHAM. Use this provided Maude code for HW4 . Handle also a short essay discussing the advantages and limitations of each of the semantic approaches discussed so far in class, assigning a (justified) score between 1 and 10 to each of them. 
 Category theory: definition, diagrams, cones and limits, exponentials
 Lambda Calculus and Combinatory Logic
HW5 (due Monday, November 12) 

This is a theoretical HW, requiring you to do three proofs using category theory. You are strongly encouraged to do *all* the exercises in the slides, especially if you did not have prior experience with category theory. However, for his HW, only handle the following three exercises: (1, easy) Exercise 8 on slide 20 in the category theory slides ; (2, easy) Property 1 on `category theory  3.png` in the hand written notes on category theory properties ; and (3, harder) Lemma on slide `cccuntypedlambda  3.png` in the hand written notes on CCC models of untyped lambda calculus . 
 SimplyTyped Lambda Calculus
HW6 (due Friday, November 30can also take the weekend if needed) 

Proposition 8 from the slides on simplytyped lambda calculus. Exercises 5 and 6 from the slides on CCCs. 
ExtraCredit (due Monday, Dec 17) 

This can be regarded as "Final exam", but it only counts as HW (and not project) extracredit and has the same weight as any of the previous HWs. If you got perfect score so far for the 6 HWs above, then you do not need to do this extracredit. Choose one, and only one, of the following and do it well (you will get either 10 or 0 for this extracredit problem!):
