The fundamental tool of a computer scientist and software engineer is the programming language. Programming languages of all shapes and sizes are found under every rock in computing. There are large, mainstream languages that everyone uses regularly. But, there are also small, domain-specific languages that are like feudal lords: well-known to their subjects, but anonymous in the wider world.
Few of us will design a large mainstream language during our careers, but almost all of us will (need to) design and implement at least one small language. Sometimes, this design might even be implicit if we're not educated about what constitutes a language.
This course will prepare you to understand the design of all languages and to design and implement small ones. In contrast to other courses of this nature, we will not treat programming languages like fish and try to make little boxes for them to fit in. Programming languages are not fish. Instead, we will explore the "periodic table" of languages features and concepts. In particular, this course will not teach you to program in many languages. There is too much noise in that approach that distracts from the real differences.
Unless stated otherwise, readings are from the course text (freely available online), Programming Languages: Application and Interpretation (PLAI), by Shriram Krishnamurthi. We will use DrScheme v4.1 for many programming assignments. (Make sure you read the "Get the Software" section on the text book site.) Other language implementations will be provided when necessary. We will look at Paul Wilson's survey of Garbage Collection methods later in the course.
DrScheme v4.1 is available on the department machines in
the /users/groups/cs330/plt. Run
the drscheme binary in the bin
directory.
Note: We will not be using the textbook in the traditional way. Think of the textbook as your lecture notes. Don't read it before a class, but refer to it afterwards. The book is superb, so you won't need to distract yourself from the discussion by taking copious notes. (You may want to take note of your ideas and insights, but the content of the lecture will be in the textbook.)
All assignments are due by 2AM the day after the day listed. Assignments that are a second late will not be graded.
| Assignment | Team | Out | Due | Code |
|---|---|---|---|---|
| Musical Notation (Written) | Solo | 9/3 | 9/8 | music |
| Survey | Solo | 9/3 | 9/10 | N/A |
| Rudimentary Interpreter | Solo | 9/5 | 9/12 | rinterp |
| Extended Interpreter | Solo | 9/12 | 9/19 | xinterp |
| Substitution (Written) | Team 1 | 9/19 | 9/26 | wsubst |
| Laziness (Written) | Team 1 | 9/26 | 10/3 | wlazy |
| Raw Web Programming | Team 1 | 9/26 | 10/3 | N/A |
| Language (Written) | Solo | 9/26 | 10/6 | wlang |
| Continuations (Written) | Team 2 | 10/15 | 10/22 | wcont |
| Web Programming in Scheme | Team 2 | 10/17 | 10/24 | pltweb |
| Garbage Collection (Presented) | Solo | 10/20 | 10/27 | pgc |
| Garbage Collection | Team 2 | 10/24 | 11/7 | gc |
| Garbage Collection (Written) | Team 2 | 10/24 | 11/7 | wgc |
| Type Checker | Team 3 | 11/7 | 11/14 | typec |
| Typed (Written) | Team 3 | 11/7 | 11/21 | wtype |
| Type Inference | Team 3 | 11/14 | 12/1 | typei |
| Implementing Prolog | Team 3 | 11/24 | 12/12 | prolog |
All assignments (with a few exceptions) are to be emailed
to jay@cs.byu.edu. The subject
must be: "BYU - Fall 2008 - CS 330 - Section x - y", where 'x' is your
section (1 or 2) and 'y' is the name of the assignment above. Only one
email should be sent per team. If two are sent, I will grade
the oldest one. The message body should be the names of the
team members one per line. You should attach (or provide a
link to) an archive (zip or tgz is fine) of
your work. The archive should create a folder with the coded name of
the assignment. Even assignments with one file should create a
folder. Each assignment specifies the names of code files, if not,
use the coded name.
Written essays must be submitted as PDFs. Use this as an opportunity to learn LaTeX. (Some written assignments carry files, these should be in the folder.)
Assignments that do not have the correct format on either the code, writing, or submission email will not be graded.
| Date | Lecture Topic | Lecture Notes |
|---|---|---|
| 9/3 | Overview / Modeling languages | PLAI 1 |
| 9/5 | Basic interpreters | PLAI 2 |
| 9/8 | Substitution | PLAI 3 |
| 9/10 | Functions | PLAI 4 |
| 9/12 | Deferring substitution | PLAI 5 |
| 9/15 | Assignment 1 Review | |
| 9/17 | First-class functions | PLAI 6 |
| 9/19 | Implementing laziness | PLAI 8 |
| 9/22 | Recursion | PLAI 9 |
| 9/24 | Implementing recursion | PLAI 10 |
| 9/26 | Interpretation without Representation (Before) | PLAI 11 |
| 9/29 | Mutation (Before) (After) | PLAI 12-13 |
| 10/1 | Mutation, cont (Before) (After) | PLAI 13 |
| 10/3 | Variables (Before) (After) | PLAI 14 |
| 10/6 | Presentations | |
| 10/8 | Presentations, cont. | |
| 10/10 | Web programming (Before) (After) | PLAI 15-16 |
| 10/13 | Web programming, cont. (Before) (After) | PLAI 17 |
| 10/15 | Web programming, cont. and CPS (Before I) (Before II) (After I) (After II) | PLAI 17-18 |
| 10/17 | Continuations (Before) (After) | PLAI 19 |
| 10/20 | Implementing continuations (Before) (After) | PLAI 20 |
| 10/22 | Automatic memory management | PLAI 21, Wilson 1 |
| 10/24 | Garbage collection | Wilson 2.1-2.3 |
| 10/27 | GC Conversation | |
| 10/29 | Garbage collection | Wilson 2.4, 2.6-2.7, 4, 4.1, 4.5 |
| 10/31 | Garbage collection | Wilson 4.6, 6.1-6.2, 7.1-7.2, 9; Regions |
| 11/3 | Types | PLAI 24-25 |
| 11/5 | Typing control | PLAI 26 |
| 11/7 | Typing data | PLAI 27 |
| 11/10 | Type soundness | PLAI 28 |
| 11/12 | Explicit polymorphism | PLAI 29 |
| 11/14 | Type inference | PLAI 30 |
| 11/17 | Implicit polymorphism | PLAI 31 |
| 11/19 | Prolog | PLAI 32-33 |
| 11/21 | Implementing Prolog | PLAI 34 |
| 11/24 | Domain-specific languages | PLAI 35 |
| 12/1 | Macros: Compiler extension (code) | PLAI 36 |
| 12/3 | Macros and language design (code) | PLAI 37 |
| 12/5 | Review: Type Inference | |
| 12/8 | Cool PLT Stuff | |
| 12/10 | Review | |
| 12/15 | 2:30pm to 5:30pm: S1 Final Exam | |
| 12/18 | 11am to 2:00pm: S2 Final Exam | |
There is no midterm. There will be a final in class during the scheduled time. It is one question. Beware.
If you need a Scheme reference, see Chapters 1-6 of Teach yourself Scheme in Fixnum Days or How to Design Programs (the intro text that goes with DrScheme). We will use the following constructs/concepts this term: functions, conditionals, symbols, user-defined datatypes (using define-type, covered in class notes only), lists (including map, filter, etc), functions as arguments, let/local.
DrScheme comes with an extensive manual and guide. This is available via the "Help > Help Desk" menu item. It is also online. Use the search box. Refer to the Tutorial, Guide, and Reference.
PLAI comes with a manual also: It is available here.
Please ask for help.
Most assignments for this class will be done in teams (pairs, with a single triple if enrollment is an odd number). Our assignments tend to be short on code but long on thinking, so this will give you the opportunity to fully discuss a solution with another person. You will work with four different people over the course of the semester.
Programming in teams does not mean each person writes part of the code and the team simply pastes together these contributions. Each person is responsible for every line of code, documentation, etc. turned in. This responsibility extends over written assignments as well. It includes getting or losing points for quality, being able to explain the work, and also incurring penalties in case of plagiarism or other violations. That said, we will sometimes ask you questions individually and, if you are unable to answer them, we may give you less credit than your teammates. In short, working is teams is meant to help you learn material better, not to enable you to do less work than you would have if the assignment had to be done individually.
For team projects, you may not discuss the assignment with a student not on your team.
We recommend that teams develop the software together using pair-programming techniques (of the form preached by Extreme Programming), though this is a suggestion, not a requirement. Pair-programming in a nutshell:
Assignments are broken into groups---approximately three assignments per group. You will work with the same team for every assignment in a single group, and you may not work with anyone you worked with in a previous group. Once you have selected a partner please inform the course staff. If you are having difficulty finding someone to be your partner, please contact us and we will attempt to match you with another student.
20% of your grade for programming assignments will depend on your design, style, and comments. Since we expect that you document and test your code anyway, we think of this as giving you a free 20% for each assignment.
Not already knowing Scheme or having learned Scheme with a different style are not excuses for not following these requirements. We are using the coding style from How To Design Programs for this course.
parse comes to
mind) and in that case recommend that each match case fits on a
screen.define-type to be
self-documenting.first and rest
instead of
car and cdr. Likewise, consider using
local
instead of let (local is much better,
anyway).All functions must have tests that exercise non-trivial cases. We require this to encourage good software development skills, but, more importantly, to force you to show us that you know what your code is supposed to do and that you’re not getting a correct answer by guessing. We will not give full credit to untested functionality, even if it is correct!
Good testing:
We will use codewalks, a common practice at software companies, to evaluate some of your programs. A codewalk is a presentation where you, the programmer, convince us, a jury, of specific properties of your program. You accomplish this by presenting your program and answering questions about it. We are most interested in
Each program will receive about 30 minutes of scrutiny. The code you present must the be the same code you turned in electronically. We will not tell you if we will conduct a codewalk for an assignment until after you have turned in a solutions for it. No excuses or exceptions; you read it here.