CS164: Programming Languages and Compilers

From CS164-Fa07

(Redirected from Main Page)
Jump to: navigation, search

Contents

Why do I want to take CS164?

  • New languages will keep coming. Be ready. Partly thanks to the web, new languages are adopted surprisingly often (CSS, HTML, JavaScript, JSP, PHP, Python, Ruby, XML). This trend will continue and as a programmer, you will be exposed to new languages every few years, most likely for the rest of your life. In this course you will learn (i) how to pick the right language for your job, (ii) why small language differences make so much difference in practice; and (iii) how to quickly learn a new language when you already know a similar one.
  • Write code that writes code. Whenever you need to write a lot of "mindless" code, it's better to write a code generator, which should be in the tool chest of each good software engineer (see The Pragmatic Programmer). For example, given a database schema, you can generate Java classes that correspond to the schema automatically. This way, you won't have to change the Java code when the schema changes. You are not restricted to generating code; for example, you can generate slide presentations with animations that are too difficult to do by hand.
  • Develop your own language. Many web languages have been created practically in the garage by ordinary hackers like you, not by PhD's in programming languages, or big companies, or by language design committees. Just glance at the origins of PHP, JavaScript, Ruby, perl and you will see that the it is possible for you to create a language and have it adopted, too. We'll talk about some missteps in designs of these languages, so that you can learn from (and avoid) the mistakes of the masters.
  • Learn about compilers and interpreters. A programming language is the most important of all programmer tools. So, you better understand how languages are compiled and executed. For example, you need to know how object-oriented programs are compiled/interpreted, so that you can, as the programmer, influence the performance of your programs. Look at these following job ads. They are pretty typical and what they ask for is exactly what cs164 teaches: exposure to various programming languages, algorithms, and object-oriented design.

Announcements

  • 12/21: Students can examine their final exam with Leo, today at 1pm.
  • 12/16: Some study guides for the final exam have been posted.
  • 12/11: Code walks will be in Ras's office
  • 12/08: The library function calm has been fixed in the online compiler. See the newsgroup for details on how to fix your local copies of the library.
  • 12/06: Homework 7 has been extended to Tuesday night. To sign up for the demo, you need to login into the wiki. See instructions below on how to do it. You will need a password given in Lecture 1 slides.
  • 12/05: Homework 7 has been assigned. Note that there is one coding question at the end.
  • 12/04: Project 5 Part 2 has been assigned.
  • 11/27: Homework 5 has been assigned.
  • 11/27: Ras' office hours on Thursday, Nov, 28, will be moved to 10:30-11am. Apologies for the inconvenience.
  • 11/26: Leo's Mondays hour this week are moved to the usual location before class (4:30-5:30pm)
  • 11/25: Leo's Mondays hours this week are moved to Tuesday at La Val's Pizza (Euclid St) at 7 after class
  • 11/22: Project 5 has been posted.
  • 11/21: We are still making final touches on the Project 5 handout. If you are ready to dive into the project, for now please read the handout from Spring 07.
  • 11/21: Submission information for Part 2, Written added
  • 11/17: Project 4 Part 2 assignment updates (see project page)
  • 11/14: Project 4 Part 1 can be submitted Thursday, instead of Wednesday, night
  • 11/13: Project 4 submission information and provided parser/grammar
  • 11/12: As many do not have card access, hours will be @ 5pm @ Brewed Awakenings on Euclid
  • 11/12: Leo will hold hours today, but at 5pm
  • 11/11: Proj 4 file updated to support types, errors, and warnings
  • 11/11: Proj 4 written portion is due with Part 2
  • 11/10: HW4 submission has been fixed
  • 11/10: Project 4 has been assigned.
  • 11/6: Homework 4 has been assigned.
  • 10/31: By popular demand, Project 3 deadline has been extended to Thursday Nov 1, 11:59pm. Use the extra time for testing your project. The deadline for Google Calculator contest has also been moved to Nov 1 11;59pm.
  • 10/28: Thanks to a relentless effort of one team, I fixed 10 bugs in the reference solution of our google calculator. If you found some suspicious behavior of our calculator (and did not check it against the real Google Calculator), recheck that behavior so that you don't use a wrong speciifcation.
  • 10/27: Instructions for the Google Calculator Contest are here.
  • 10/27: The Project 3 deadline has been extended to Wed 31, 11:59pm.
  • 10/25: The "reference" implementation of the Google Calculator has been posted here. Use is to test your Project 3 solutions. If you find a discrepancy, send us email: you have either found a bug and you get an extra credit or you have implemented a feature that we do not support and you should submit the feature into the contest.
  • 10/22: We added the list of units of measure that you are to implement in your google calculator. Find them at the end of the project handout.
  • 10/22: Leo will hold office hours tomorrow (Tuesday) 4:30-5:30pm in the usual place.
  • 10/21: The deadline for proj3 has been extended to Friday Sunday night, and we extended the assignment to implement two specific test case grammars that should work on your parser.
  • 10/21: If you submitted proj3 part 1 late, please create a tag "proj3-part1" that contains a file "version" whose sole contents are the tag you want us to look at for grading (ex: "version" contains the text "proj3-5"). If you didn't submit late... you don't need to do anything. We'll pick out the last tag before the deadline.
  • 10/16: Given the flux of messages on it, do not worry about handling rules for regular expression symbol "$"
  • 10/15: See the proj3 page for an announcement on upcoming required testing.
  • 10/12: The grammar.py AST did not include ignore etc fields, so some people modified theirs, or you can use this one.
  • 10/11: Homework grades for 1, 2, 3 have been posted for a while. If you are missing a grade, email cs164-ra@imail.eecs.berkeley.edu ASAP.
  • 10/09: Midterm 1 grades have been posted. The exam is here. The solutions are here.
  • 10/04: Project 3, parts I and II, are up.
  • 10/01: Until further notice, you are required to use in your projects and homeworks Python version 2.4.4. The reason is that the instructional machines do not run Python 2.5 and if you use the new 2.5 language features, we cannot grade your projects or homeworks. I know this is unfortunate; I have asked inst to install Python 2.5 but it may take a while... Update: It turns out that Python 2.5 is installed on instructional machines, just the path was set incorrectly. The issue should be fixed soon and so you can go back to using 2.5.
  • 10/01: If you need help with SVN, consider attending this help session. If you don't know what SVN is, you should attend. :-)
  • 10/01: You are allowed 1 hand written cheat sheet for the exam.
  • 09/27: We started a page that may help ypou prepare for the first midterm exam.
  • 09/26: Homework 3 has been assigned. It is a short programming homework, due on Monday.
  • 09/26: Project 2 has been extended until tonight, and some test files are availables
  • 09/22: If you cannot use Eclipse or Subclipse, a quick tutorial on using Subversion from the command line to handle your submission has been posted in the project 2 appendix.
  • 09/22: If your team repo has not been created, email the cs164 account. Additionally, you should not rely on our remote tester for testing your project, because, in part, it is not running.
  • 09/18: A note on Project 2.
  • 09/16: Project 2 has been assigned.
  • 09/14: PPT version of Lecture 6 has been posted. PDF coming soon (some technical issues). I will post remaining past lectures over the weekend.
  • 09/14: Exam dates and grade distributions have been announced in class and posted below.
  • 09/11: The submit scripts on Linux instructional machines are broken. Please use Solaris machines for now. The instructional staff promised to fixed the problem before the next project is due.
  • 09/05: Leo's Monday hours will be from 6-7pm from now on
  • 09/05: Homework 2 has been posted, which is an extension of the first interpreter assignment, and hints at deeper mathematical theories.
  • 08/31: Project 1 has just been posted. The project is fun. It will teach you magic with Greasemonkey and regular expressions. I wish I could take the course. --Ras :-)
  • 08/30: Leo will be holding hours in 511 Soda from now on
  • 08/28: Leo will pair together any students without a partner after Friday's section
  • 08/28: Homework 1 is now available
  • 08/28: Due to travel, Ras will not hold office hours on Thu 8/30. The Thu lecture will be give as scheduled.

Course Info

Staff: We will be trying to answer email questions within 36 hours, so coming office hours is heavily suggested because it may be the case that you are not satisfied with our first answer and might have to wait again. If you cannot make hours, the course email is cs164 [at] imail.eecs.berkeley.edu and the newsgroup is located at ucb.class.cs164 (see [accessing the newsgroup]). Only use our personal emails for personal purposes, such as invitations to barbecues. Generally, you should first try to go to office hours, then post to the discussion group, then send an email to the course email. If the issue directly concerns an individual person (ex: barbecue invitation), then use that contact point.

  • Prof. Ras Bodik, 773 Soda, bodik@cs, Office hours: Mon 1:30-2:00 and Thu 10:00-10:30
  • Leo Meyerovich, 511 Soda, lmeyerov@eecs, office hours: Mon 6-7pm and Fri 10-11am

Lectures

The powerpoint files may not display properly because they use non-standard fonts. PDFs should display and print ok. Let me know if they don't.

Date Topic Slides Reading Homeworks, Projects
Tue Aug 28 Why do I want to take this course? pdf-6up, ppt Homework 1
Thu Aug 30 Where do languages come from?

pdf-6up, ppt

Project 1
Tue Sep 4 Regular expressions in JavaScript, Python; their applications

pdf-6up, ppt

Homework 2
Thu Sep 6 Inventing automata as a programming model; DFA, NFA

pdf-6up, ppt

Tue Sep 11 Compiling Regular Expressions; Two flavors of Regular Expressions

pdf-6up, ppt

Thu Sep 13 Grammars: Abstractions for Parsing; Recursive Descent Parsing

pdf-6up, ppt

Project 2
Tue Sep 18 Syntax-Directed Translation

pdf-6up, ppt

Thu Sep 20 Left Recursion Elimination; CYK Parser

pdf-6up, ppt

Tue Sep 25 Earley Parser; Grammar Disambiguation

same slides

Thu Sep 27 "Google Calculator" (syntax-directed translation)
Tue Oct 2 1st Midterm Exam

Midterm 1 Prep

Thu Oct 4 Browsing Web 3.0 on 3.0 Watts

slides

Tue Oct 9 How to grow a language? Lua tutorial
Thu Oct 11 Implementing object-oriented features
Tue Oct 16 Functions notes by Prof. Hilfinger
Thu Oct 18 continued; disambiguation in project 3
Tue Oct 23 cancelled
Thu Oct 25 Code generation; Project Discussion slides
Tue Oct 30 Compiling OO Programs slides
Thu Nov 1 Multiple Inheritance slides
Tue Nov 6 Semantic Analysis, Types, and Runtime Checks 6-up
Thu Nov 8 Midterm 2 Midterm 2 Prep
Tue Nov 13 static and dynamic checks continued same slides
Thu Nov 15 Static Analysis same slides as in pointer analysis
Tue Nov 20 Max/MSP and SkipJax 6-up
Thu Nov 22 Thanksgiving
Tue Nov 27 Pointer Analysis 6-up
Thu Nov 29 Stack Smashing, Trusting Trust 6-up assigned reading
Tue Dec 4 Software synthesis with Sketching 6-up
Thu Dec 6 How to use cs164 in the real world 6-up

Homeworks

Discussions

  1. 08/31/2007: JS/DOM/AJAX/GM
  2. 09/07/2007: REGEX->NFA, NFA+DFA Simulation, NFA->DFA, DFA->REGEX
  3. 09/14/2007: BNF, Recursive Descent, Left Recursion
  4. 09/21/2007: CYK parsing, ambiguity, and complexity
  5. 09/28/2007: review of discussions 2, 3, 4, and Earley parsing example
  6. 10/05/2007: Lambda Calculus: introduction, booleans, lists, Church numerals
  7. 10/12/2007: Lambda Calculus II: addition/multiplication/subtraction, recursion, Y combinator
  8. 10/19/2007: Function Representation: dynamic vs lexical scope, nested and first class functions, dynamic links, static links vs displays
  9. 10/26/2007: informal discussion on what we can statically vs dynamically (or not at all) do
  10. 11/02/2007: Efficient Visitors in Java, JavaScript
  11. 11/09/2007: Midterm 2 wrap up, source-to-source translation
  12. 11/16/2007: Type systems, type checking
  13. 11/30/2007: Implementing Functional Reactive Programming
  14. 12/06/2007: Points-To Analysis with Prolog Unification and CYK

Projects

Late Submission Policy

Each student is allocated four free late days (per semester) that can be used on any programming assignment (a.k.a. project). For example, you can submit the first programming assignment three days late or you can submit each of the last three programming assignments one date late.

The free late days are designed to help you deal with family emergencies, so we advice that you don't waste them on early programming assignments. Save them for the later, more difficult project assignment. No additional free late days will be awarded.

When a team decides to use a late day, both members lose a late day. It is possible that at some point, members of a team have each a different number of free late days left. For example, one team member has two days left, and the other has zero. In this case, the team has one free day left (computed as average of the two late days quotas, rounded up).

After the free late days are exhausted, there is a 10% penalty for each day, or partial day, that a programming assignment is late.

Late written assignments (homeworks) will receive no credit.


Resources

Textbooks

No textbook is required. The following books are recommended:

Students, are there any other books you would like to recommend? If yes, enter them here.

JavaScript/DOM

Firebug

CSS

Python

SVN

Administrivia

Exams

Makeup exams are allowed only for serious and documented family or medical emergencies.

  • Midterm 1: Tue, Oct 2, 5:30-7pm, 306 Soda
  • Midterm 2: Thu, Nov 8, 5:30-7pm, 306 Soda
  • Final Exam: Tuesday, Dec 18, 12:30-3:30pm, Room TBD

Grading

Grades will be computed as follows. The weights are subject to change in response to project and homework difficulty.

  • homeworks: 10%
  • midterms: 14% each
  • final exam: 22%
  • project: 40%

Miscellaneous

Academic Honesty

It is expected that all students understand University policies on academic honesty. Cheating on assignments or exams is very serious and will not be tolerated. In this course, we will use a variation of the standard policy. In this class, it is permissible to talk to other students about assignments, to discuss particular solutions, and even to receive partial solutions (including code) from others. However, all assistance and cooperation must be cited in the assignment write-up. If you receive any assistance from anyone other than course staff or your partner on an assignment, you must acknowledge in the write-up for that assignment who gave assistance and what assistance was given. Grading will take into account how much help a student received from others (the more help, the lower the grade). Failure to acknowledge sources is plagiarism and will be treated as a serious breach of academic honesty. No assistance may be given or received on exams.

In order to participate in the course, you must read the departmental academic honesty policy: link.

You should know that fairly sophisticated plagiarism detection software will be used on the programming assignments.

Retrieved from "http://play.cs.berkeley.edu/wiki/cs164/fa07/index.php/CS164:_Programming_Languages_and_Compilers"
Personal tools