Lecture notes for classes 1-2 are available.
A BNF for Java from the official Java specification.
A BNF for the C programming language appears in Annex A (page 476 forward) of this publicly-available draft of the ANSI C spec.
Warning: the example BNF grammars for Java and C above do not use exactly the same conventions as our class.
Lecture notes: Basics of the C programming language (version 2, uploaded 9/7/15, with a correction at the end of section 4 -- thanks to Georgi for pointing out the error).
C for Java Programmers by Niranjan Nagarajan.
Lecture notes: Data types
Very long but important background reading: Java to C++ Transition Tutorial, maintained by the CS123 TA staff at Brown University. Start reading this in preparation for today's class, and keep reading it over the next few days.
Important note about what programming languages you need to know: The textbook and lecture notes give examples from a wide range of programming languages, including Ada, Python, Pascal, C#, and Perl. You should always read and understand the abstract concepts presented in any example. However, in this course you are not required to understand the details of, or write code in, any languages other than the following: Java, C, C++, Scheme, Prolog. Exam questions and homework questions will refer only to these five languages.
Lecture notes: Abstract data types
Examples for separating code into header and implementation files: Location.cpp, Location.h, CityList.cpp, CityList.h, CityListMain.cpp, combined.cpp .
Lecture notes: Multiple inheritance and polymorphism
There are no lecture notes for today. Please take your own notes in class. You need to understand the basics of references and goto statements in C++, even though none of the programming assignments requires these. You also need to understand what operator overloading means, but you aren't required to learn the syntax. Please see the example code below for references, goto statements, and operator overloading:
In addition, you should be aware of the content of Dijkstra's 1968 discussion of go to statements and structured programming, Go To Statement Considered Harmful (available on Moodle). We will discuss this famous letter to the editor in class. Wikipedia has an excellent article on the goto statement. Interestingly, there is a separate Wikipedia page devoted to the phrase "considered harmful".
We may also use the file callStackDemo.java to demonstrate some of Dijkstra's ideas.
Files for working with scanning: cup.jar, example.lex, sym.java, LexTest.java, input-for-LexTest.txt. These five files are also available as a single zip file: scanning.zip.
In class, a question came up about how JFLex might deal with ambiguous tokenizing rules. One option here is to read the manual, but it's very long and complex. Another option is to conduct some experiments. Some brief experiments suggest that JFLex always chooses the rule that consumes the most characters. If rules are tied on this criterion (i.e. they match the same number of characters), then JFLex uses the rule that appears earlier in the .lex file. An example of this is provided: hex-demo.zip. Here you'll find a specification that deliberately allows ambiguity between hexadecimal numbers and decimal numbers. By swapping lines 29 and 30 in the example.lex file inside hex-demo.zip, you will see different behaviors from the scanner on the given input file hex-demo.txt. Good question, interesting answer!
calculator.zip for running JFlex and CUP on the calculator example. Also available as individual files: cup.jar, example.lex, example.cup, input.txt.
Solutions for the in-class "repeat" functionality exercise are available as: repeat-solution.zip. I strongly recommend completing the "repeat" exercise to the best of your ability before consulting solutions.
Lecture notes will not be provided for most of this topic. We will stick reasonably closely to the textbook (Chapter 15, sections 0-5 and section 11 are the only ones we will cover).
Instructions for editing and running Scheme programs:
Please read textbook sections 15.5.12-14.
For more detailed examples, see the tail recursion handout.
For a practical example demonstrating difference in CPU time and memory usage for tail recursive and non-tail recursive implementations of a given function, see sum-fn.zip.
Please take the class survey.
Lecture notes on the implementation of Scheme.
Do you find Scheme's use of parentheses are little excessive? Check out the contents page of the book Introduction to Scheme, by Jerry Smith.
Most of the class will be a discussion of section 15.11 in the textbook. It may also be useful to browse a few of the hits on a web search for "functional versus imperative".
Example code for using lambda expressions in Java: JavaLambda.zip
This class covers non-examinable topics: assignments in Scheme, object-oriented approaches in Scheme, vectors and hash tables in Scheme, and delegates and lambda expressions in C#. Some example Scheme code is available (note that this uses the Racket language, not the Advanced Student language we used for all our previous work).
This class will also include lab time to work on and ask questions about homework assignment 7. If you have finished the homework, I recommend working on the optional exercises, taken from Dybvig's book, The Scheme Programming Language.
Some inspiration for the tail recursion homework: http://xkcd.com/1270/.
This class covers sections 5.1-5.4 and 6.12-6.14 of the textbook.
Contrast the textbook's definition of strongly typed with the discussion given in the first answer on the following page: http://stackoverflow.com/questions/430182/is-c-strongly-typed.
The example code type-equivalence-examples.c provides some examples of type equivalence and inequivalence in C.
This class covers sections 5.5-5.8 of the textbook, but sections 5.5.6 and 5.5.7 are excluded. (These sections cover dynamic scoping, which we will discuss in class, but which will not be included in any homework or exam questions.)
The brief code examples used in class are available as scope-examples.zip.
Here's an example that will be useful for discussing the non-examinable topic of dynamic scoping: dynamic-scope-example-from-sebesta.pdf.
Exam 2.
For running Prolog programs:
We will follow the textbook closely for this topic. Separate lecture notes will not be provided (mostly). However, the examples used in class today are available as prolog-demo1.pl.
The textbook uses unusual notation for some of the propositional logic operators (and, or, implies). We will use the standard notation as taught in the Dickinson discrete math course.
Some of the in-class examples are taken from http://en.wikibooks.org/wiki/Prolog. In particular, this online book contains a good section on Prolog lists, which will help to amplify the textbook's coverage: http://en.wikibooks.org/wiki/Prolog/Lists.
Lecture notes on prolog and first-order logic.
Some very brief notes on unification.
Some notes on additional topics, including negation---these notes will help with the homework. The accompanying file tree.pl demonstrates a non-trivial Prolog data structure.
We do not study the use of arithmetic in Prolog (so you can skip the book section 16.6.6).
The file course-inference.pl contains the example used to explain inference in Prolog.
Instructions for using tracing facilities with XGP:
teachingStudent(maccormick,gao).
Evaluations. Exam revision and hints. Then continue working on final project.
Work on final project in class.
There was a typo in the summary schedule, which incorrectly specified the deadline for the final project as midnight on 12/12. This typo was fixed on 12/7, specifying the correct deadline as midnight on Friday, December 11. However, due to potential confusion over this deadline, I will be happy to grant a 24-hour extension to anyone who wants it. And, as announced in class, you are welcome to use any remaining late days for this assignment. But I recommend you submit on Friday and spend time studying for your exams instead.
Here's an interesting piece of research from 2013 related to some of our work on C/C++ earlier in the semester: Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior, by Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, Armando Solar-Lezama. Some slides used by the first author when presenting the paper are also available. Note the puzzle on the last page of the slides -- it is highly relevant to this class! A file containing the relevant code from the puzzle is available: puzzle.c.