C SC 520

Principles of Programming Languages

• Michael L. Scott, Programming Language Pragmatics, 3rd Edition, Morgan-Kaufmann, 2006.(Editions 1 & 2 are out of print, and differ in organization from the 3rd Edition). ISBN 9780123745149.

Other materials (link available in class)
• David A. Watt, Programming Language Syntax and Semantics, Prentice-Hall, 1997. See instructor for link.

Login Name and Password:
Your C SC login name (userid, username) will match your current UA NetID. This NetID is the name of your UA email account, as in Your_NetID@email.arizona.edu. This login name is used for remote ssh access to lectura.cs.arizona.edu, and for login to workstations in Gould-Simpson 228 or 930, and throughout the building.

Your initial password for C SC Department machines will be sent to your email.arizona.edu address at the beginning of the semester. For this reason, you must have an active email.arizona.edu account in order to receive a C SC account.

When you log in to lectura.cs.arizona.edu for the first time you will be forced to change your initial password to a more secure password. See Rules for Acceptable Passwords for information on choosing strong passwords.

Access to Gould Simpson and Labs:
On the first day of classes all students who have registered for C SC classes, whether in-person or on-line, will be able to use their CatCards for access to the Gould-Simpson Building, and to the C SC computer labs in Gould-Simpson Rooms 228 and 930. Access will continue around the clock until the end of the semester.

Computer Science ID (CSID):
You will need to know your Computer Science ID (CSID), which is different from your Student ID (SID). To find your CSID at any time, go to www.cs.arizona.edu/computing/services/csid.html. Enter your 9-digit Student ID (SID) without any hyphens, and push the submit button. Record your CSID for future reference. Grades will be posted using your CSID.

For any account problems, send email to lab@cs.arizona.edu.

Each graded item, such as a homework or examination, is first awarded a raw score; raw scores vary with the number of questions, their difficulty, and their length. For each graded item, the raw score is normalized to a ``traditional'' scale in which 90 - 100 is an A, 80 - 89 is a B and 70 - 79 is a C. For each graded item, only the normalized score is recorded. The final cumulative course grade is computed as a weighted average of these normalized scores, using the weights described under Course Format above. The resulting weighted average is then converted to a letter grade using the ``traditional'' scale. Decisions on whether borderline scores (such as 89) will be recorded as the next highest letter grade will be made using (a) performance on the final examination and (b) evidence of accomplishment in the subject that is cumulative over the term.

Any appeal to the instructor to review or reconsider a graded item must be made within a week (7 days) of the graded item being handed back in class. After that period, the original grade will stand.

Attendance is not enforced, but you are responsible for all material covered in lecture or assigned as reading.

Without prior arrangements, missed exams result in a grade of zero. Homework is due at the start of class on the due date. In-person students should submit homework in paper form (in labeled envelopes provided). On-line students should submit .pdf files via email. Late homework is not accepted.

It is assumed that: you have the prerequisites for this course, and their prerequisites, etc., recursively.

The instructor reserves the right to fail for the course any student failing the final comprehensive examination.

The content of this syllabus is subject to change at the discretion of the instructor.

When writing an examination in this course, All work is expected to be that of each student alone, without consultation with others, without reference to borrowed solutions and not the product of team efforts or collaboration with other authors. Other provisions are governed by the University's Code of Academic Integrity which applies to all those in this course.

Students with disabilities, who may require academic adjustments or reasonable accommodations in order to participate fully in course activities or to meet course requirements, must first register with the Disability Resource Center, 1540 E 2nd St, 621-3268, email drc@w3.arizona.edu, URL http://drc.arizona.edu. DRC staff will qualify students for services, and provide a letter to be submitted directly to the instructor during the first week of classes.

1. Programming Linguistics
   1. Introduction: Syntax, semantics and pragmatics. Criteria for language design. Imperative vs. Applicative languages. Operational, denotational and axiomatic semantics. History and evolution.
   2. Variables, Expressions and Statements: Binding time spectrum. Variables and expressions. Assignment. l-values and r-values. Environments and stores. Storage allocation. Constants and initialization. Expressions. Statement-level control structures.
   3. Types: Primitive types. Pointers. Structured types. Coercion. Notions of type equivalence. Polymorphism: overloading, inheritance, type parameterization.
   4. Procedure Mechanisms: Declarations and activations. Parameter passing. Exceptions. Coroutines. Concurrency. Generators.
   5. Referencing Environments: Static, semidynamic and dynamic activation records. Local vs. global references. Static chain and display. Central referencing environment. Funargs. Deep vs. shallow binding. Parameter passing. Aliasing. Block structure.
   6. Data Encapsulation: Abstract datatypes. Information hiding and abstraction. Visibility. Procedures. Modules. Classes. Packages. Objects and Object-Oriented Programming: inheritance, subtypes and extensions. Simula 67 classes. Smalltalk-80. C++.
2. Programming Language Semantics
   1. Symbol and Meaning: Metalanguage and object language. Semantic maps. Mathematical background: functions, operators, relations, partial orders.
   2. Syntax: Abstract vs concrete syntax. Syntactic domains. Static and dynamic semantics. Abstract syntax trees.
   3. Semantic Description: denotational semantics; operational semantics; axiomatic semantics. Examples with a simple imperative language.
   4. Lambda Calculus: Abstraction and application. Free/bound variables. Reduction. Normal forms and divergence. Church-Rosser theorem. Typed lambda calculus. Semantics of a simple applicative language.
   5. Recursive Definition: The problem of recursive definition. Semantic domains. Continuous functions. Strictness. Fixpoint theory. Successive approximation. Domain-theoretic semantics of an applicative language. Operational semantics: minimal fixpoints and computation rules.
   6. Denotational Semantics of Imperative Languages: Environment/state semantics. Expressions. Commands. Loops. Environments and blocks; refs and dynamic storage. Product types and arrays. l-values and r-values. Jumps and environment/continuation/state semantics. Semantics of parameter passing modes.

• Lecture01: Introduction
• Lecture02: Criteria
• Lecture03: Theory
• Lecture04: Types
• Lecture05: Denotational Semantics
  • Abstract Syntax 0
  • The Store 1
  • The Environment 2
  • An Imperative Language: IMP 3
  • Function Abstractions 4
  • Recursion 5
  • Procedure Abstractions 6
  • Parameter Denotations 7
  • Copy Parameters 8
  • Expression Side-Effects 9
  • Static Semantics 10
• Lecture06: Parameters
• Lecture07: Implementation
• Lecture10: Variables and Assignment
• Lecture08: Continuations Pt I
• Lecture08: Continuations Pt II

• Reading:
  • Due Tue 31 Jan:
    • Watt, Chapter 1: Introduction -- all, and
      Chapter 2: Syntax -- all
    • Scott, Chapter 1: Introduction -- all, and
      Chapter 2: Syntax -- all.
    • The above material is review of subjects covered in the prerequisite for this course and should be familiar.
    
    
  • Due Tue 14 Feb:
    • Watt, Chapter 3 (Semantics), Sections 3.1-3.2
      Chapter 5 (Theory), Section 5.1
    • Scott, Chapter 3 (Names, Scopes and Bindings)
  • Due Tue 21 Feb:
    • Watt: Section 3.3; Section 5.2
    • Scott, 1st, 2nd & 3rd Ed: Chapter 10, Sections 10.1-10.8
    • Read Lambda Calculus by Lloyd Allison; there is a link in the ``Reference Links'' section. Read the "Intro." and explore this site.
    • Read Robert Harper, Introduction to Standard ML; there is a pdf version in the ``Reference Links'' section above. Another good but optional reference is Programming in Standard ML; see the reference links below.
  • Due Tue 6 Mar:
    • Watt, Chapter 5 (Theory), Section 5.3
      
    • Scott (1st, 2nd 3rd eds.), Chapter 7 (Types), all
  • Due Thu 8 Mar:
    • Watt, Chapter 3, Sections 3.4 - 3.7
      
    • Scott (1st, 2nd, 3rd eds.), Chapter 6 (Control Flow), all
  • Due Wed 6 Apr:
    • Watt text: Chapter 4, 4.1, 4.2 (Applications) ;
    • Watt text: Appendices B,C,D on DELTA language
  • Due Thu 19 Apr:
    • W. A. Wulf, D. B. Russel, and A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, vol. 14, no. 12, pp. 780-790 (December 1971). (pdf)
  
  
• Homework:
  • Homework #1 (due 7 Feb)
  • Homework #1 Solutions
  • Homework #2 (due 21 Feb)
  • Homework #2 Solutions
  • Homework #3 (due 8 Mar)
  • Homework #3 Solutions
  • Homework #4 (due 10 Apr)
  • Homework #4 Solutions
  • Homework #5 (due 24 Apr)
  • Homework #5 Solutions
  • OPTIONAL Homework #6 (due 3 May)

• Examinations: Information about exams is posted here in advance of the test.
  • Midterm Exam: Take-home exam out Tue 20 Mar, due Tue 27 Mar
  • Midterm
  • Midterm Solutions
  • Final Exam: Take-home exam out Tue 1 May, due Tue 8 May
  • Final (due Tue 8 May)

• Office hours for the instructor are given above. These hours are subject to change during the semester. I will update this web page and email class members when changes have to be made. If you can not attend scheduled office hours, mail the instructor to make an appointment outside the regular ``walk-in" office hours--in person, via telephone or via email.
  
• D2L News is accessible on your ``Course Home" D2L splash page. Items of importance involving assignment changes, schedule changes, problem hints, etc. will appear in the D2L News. Review it often.
  
• Email questions sent to the instructor should have an informative subject line, and kept brief. It is usually not necessary to include all prior mail correspondence with your mail. Include only what is relevant from earlier exchanges.

All written work submitted for credit must be prepared using a program that produces typeset output with the appropriate type faces, symbols and notation used in the theory of computation (e.g., TeX, LaTeX, Word + Equation, etc). Figures can be rendered using a drawing tool like xfig, Word, PowerPoint, dia, etc. Do not submit scanned images of handwritten work.

Rules for submitted work:

Start each solution on a new page, repeat the problem statement, and number each page. Write on one side of the paper only. Write concise and clear solutions, since failure to communicate clearly will cost points whether or not the conclusion is correct.

In-person students will submit work at the beginning of class on the due date (labeled envelopes will be provided). Please submit in paper form when at all possible--in-person students should submit .pdf files electronically only in an emergency. On-line students will submit answers electronically, before class time on the due date. Submissions must be in .pdf format only.

All good writing is based upon revision. It is essential to revise your work before submission, and to consider whether your argument will be understandable to the reader. For example, it is never a waste of effort to explain the strategy you intend to use in a proof or construction, before beginning to present the work in technical detail. Think of the reader. Explain as if teaching a colleague in your class. Revise. Revise again.

• Lloyd Allison's Lambda Calculus site
• Introduction to Standard ML by Robert Harper
• Programming in Standard ML by Robert Harper