CS 3040: Programming Languages and Translators, Fall 2020

Instructor: Rob Hasker (414-277-7326)

Office hours: See my home page: https://faculty-web.msoe.edu/hasker/

Textbooks:

Software Languages: Syntax, Semantics, and Metaprogramming, Ralf Lämmel, Springer, 2018, ISBN 978-3-319-90798-7

Real World Haskell, O'Sullivan, Stewart, and Goerzen, O'Reilly, 2008. This book is available online.

Course Description: This course studies programming languages and their implementations. This includes discussions of data types, storage management, syntax, BNF descriptions, domain-specific languages, semantics, lexical analysis, parsing, and compilation. Traditional and more modern programming languages are used as examples. Students use a functional programming language to contruct interpreters and translators for multiple domain-specific languages.

Prereq: CS 2040

Format: 4 lecture hours, no lab, 4 credits

Course Outcomes: On successful completion of this course, the student will be able to

• Specify regular and context free languages
• Write moderately-sized programs in Haskell
• Apply regular expressions to construct programming language tokenizers
• Use recursive descent and parser generators to build parsers, interpreters, and translators for simple languages
• Give a formal specification of a type system and compare various systems
• Construct an operational semantics for a simple programming language
• Discuss storage and data management, including binding, scope, lifetime, and automated garbage collection
• Build a domain-specific language along with tools to process that language

Grading: 

		Percentage
	Assignments	30%
	Quizzes/homework/participation:	20%
	2 Midterm exams:	30%
	Final Exam:	20%
	Total:	100%

The MSOE grading scale will be used, though I reserve the right to award higher grades to individual students if it increases fairness. In addition, successfully demonstrating mastery of course outcomes is a prerequisite for a passing grade. This includes being successful on the final exam and, in some cases, completing assignments even if worth zero points.

Communication

While the course is convening remotely, I will focus on the following communication methods:

• I will either link to materials or provide materials on Canvas. This includes quizzes, exams, assignments, notes, and other materials.
• Some assignments will be submited on esubmit. I will generally put grading comments there with final scores in Canvas (which is sometimes higher than the score shown on esubmit).
• We will use Teams to discuss online presentations and labs as a group. Attending the call-in meetings is required. Your participation in these is a part of your grade.
• Teams generates a large number of notifications. I will probably use Slack for more general-purpose discussions; we will have to experiment with the different tools to see what works best.
• I may use email to make announcements to the class if I'm concerned that an announcement on Teams will not reach everyone.

Assignments and Quizzes

Unless otherwise announced, late assignment and exercise solutions will be penalized 5% if submitted up to three days late and 15% if submitted between four and seven days late. Solutions submitted more than one week late will be worth zero points unless there is advance arrangement for extenuating circumstances. Other assignments (such as homeworks and online quizzes) are worth zero points if late. Unless you have written permission, all assignments must be submitted before Monday of finals week.

Programs will be graded for both correctness (does it work right?) and presentation (does it look good on the printed page?). I will not be handing out an extensive style sheet for this course, but at a minimum you must do the following:

• Identifiers have meaningful names and are scoped correctly.
• Format your programs consistently and nicely, including judicious use of spaces and blank lines. Keep line lengths to about 80 characters.
• Ensuring your files contain no hard tabs except Python source files.
• Include your name (prominently) in source files.
• Providing enough documentation that another person can understand the modules in your solution, without providing documentation that is blatently obvious from examining the code. For example, the first documentation is useful but the others are not:

  const int MAX_SIZE = 30; // max # of dates
  const int LIMIT = 50;    // limit of 50 – USELESS
  if ( x > 0 )             // check x is positive – USELESS

• Follow standard design principles including small subroutines, minimal repeated code, and tightly scoped identifiers.
• Fix your code so it builds without compilation warnings.

Assignments and quizzes are individual unless explicitly stated otherwise. You are responsible for honestly completing and representing your work, for appropriately citing sources, and for respecting the academic endeavors of others. Electronic tools may be used to identify plagiarism. You will be penalized for violating these standards.

Missed quizzes cannot be made up, but at least one of the lowest quiz or homework scores will be dropped. All assignments must be submitted by the Saturday after week 10. Assignments will not be accepted after that unless there is advance, written approval.

Attendance

Attending Teams-based class meetings and lab sessions is mandatory. I may not always take formal attendance, but attendance and participation will be factored into your grade. It is expected that you will read lab writeups and review lecture material before the appropriate lab or class meeting.

Do not record video or audio of lectures without my permission, and do not redistribute provided videos.

All students must take the final exam to receive a passing grade in the course unless the student has been excused in advance.

For students with documented disabilities, chronic medication conditions and mental health concerns: MSOE provides services to make reasonable accommodations available. If you are a student who requires or anticipates the need for accommodations, please contact Student Accessibility Services Office at 414-277-7281, by email at moureau@msoe.edu, or in person at K250 to discuss appropriate accommodations and eligibility requirements.

All students are expected to follow the procedures specified in the Raider Return Plan.

Course Topics

• Implementing a recognizer for a small domain-specific language (7)
• Regular expressions and their translation to finite state machines (4)
• Constructing an abstract syntax tree (6)
• Interpreting and compiling simple computer programs (4)
• Specifying context-free grammars (3)
• Operational semantics (3)
• Specifying type systems (2)
• Variable binding, scope, lifetime, and storage management (4)
• Functional Programming (5)

Tentative Schedule

By weeks:

• Week 1: Domain-Specific Languages
  • in-class exercise: developing a language for registration or reverse engineer the language used to play Zork 1;
  • Assignment 1: construct a fluent API to implement a calculator
• Week 2: Regular Expressions, Syntax Trees, and Introduction to Haskell
  • Assignment 2: Regular expression tutorial
  • Assignment 3: Haskell programming problem
• Week 3: Interpreters
  • In-class exercise: adding variables to a simple expression language
  • Assignment 4: Haskell implementation of a finite state machine
• Week 4: Grammars, Equivalence of FSMs and REs, Chomsky Hierarchy
  • Midterm
  • In-class exercise: grammars and parse trees
  • In-class exercise: constructing programs from a given grammar
  • Assignment 5: A grammar for a subset of Ruby
• Week 5: Recursive-descent and table-driven parsing
  • In-class exercise: build a recursive descent parser for the grammar developed in assignment 5
  • In-class exercise: extend an DFSM checker to cover additional errors
  • Assignment 6: Build an ANTLR-based checker for the Ruby subset identified in Assignment 5
  • Start Final Project: build a language & grammar, checker, and interpreter
• Week 6: Operational Semantics, types
  • Assignment 7: build a semantics for a robot that patrols the number line
  • In-class exercise: build rules for type checking C++ numeric expressions
• Week 7: Types, Lifetime, Scope
  • Assignment: continue final project
  • Midterm
• Week 8: Memory Management, compilation, optimization
  • Assignment: continue final project
• Week 9: Functional Programming
  • Assignment 8: high-performance Haskell code
• Week 10: Wrapup
  • Complete final project