Object-Oriented Programming

CSCI-UA.0470-001

NYU, Undergraduate Division, Computer Science Course - Fall 2013

Information

Class MeetingsTue and Thu, 3:30-4:45pm in CIWW 512
First ClassSep 3, 2013
Last ClassDec 10, 2013
Final Individal ExamDec 12, 3:30-4:45pm in CIWW 512
Final Group Project PresentationsDec 19, 4:00-5:50pm in CIWW 512
InstructorThomas Wies, office hours: Thu 5:00-6:00pm in CIWW 407, or by appointment
GraderAnupam Nandan, office hours: Tue 4:45-5:45pm in CIWW 412

Overview

Object-oriented (OO) programming has emerged as a significant software development methodology. The goal of this course is to learn how to build and evolve large-scale programs using object-oriented programming. To this end, the course introduces the important concepts of object-oriented languages and design, and explores how these concepts are implemented.

Prerequisites: Computer Systems Organization (CSCI-UA 201).

Acknowledgments: This course is based on the Object-Oriented Programming course designed by Robert Grimm.

Topics

In exploring object-oriented programming, we investigate three questions:

  • Design: How do we think about a program in terms of objects? To answer this question, we explore CRC cards, UML, and design patterns.
  • Language Primitives: How do we express object orientation? To answer this question, we explore classes, interfaces, inheritance, method dispatch, generics, operator overloading, and reflection.
  • Language Implementation: How do we realize object-oriented primitives? To answer this question, we explore virtual method dispatch and automatic memory management in detail.

Design and primitives matter because they represent the essence of object-oriented programming. Implementation matters because it enables us to debug object-oriented programs and tune their performance.

Project

The focus of our exploration of object-oriented programming is a translator from Java to C++. You design, implement, and evaluate your own translator as a term-long project, working in teams of four to five students. In fact, you build two versions of your translator, taking half a term for each version and presenting your work in class on completion of each version. To make the project manageable, your translator only translates a restricted subset of Java into an even more restricted subset of C++; though the second version covers more functionality than the first version. I also provide you with “helper” code, notably for parsing and pretty printing program source files.

Each group elects a speaker, who coordinates with the members of the group and with me. A new speaker is elected at the middle of the term.

Your group’s midterm and final project presentations address three main issues:

  • What are the design and implementation of your translator?
  • How do you ensure that the translator meets the project requirements? Notably, how do you convince yourself and others that the translator actually works?
  • What was easy, hard, and/or surprising and how did that impact your translator?

You have a 12 minute slot for your presentation, which includes a demo of your translator and time to set up your laptop.

Details

Group Meetings

Every project group meets with the instructor every other week for an informal discussion of issues currently facing the group. Group members will probably need additional meetings amongst themselves to better coordinate their work.

Mailing List

All course-related announcements will be sent to the course mailing list. I encourage you to use this list to ask questions and discuss issues related to the course. If you have enrolled before the start of the term you are automatically subscribed to the list. Otherwise, use the above link to subscribe manually.

Grading

Group projects (50%), individual assignments (25%), final exam (25%).

Academic Integrity

Please review the departmental academic integrity policy. In this course, you may discuss assignments with other students, but the work you turn in must be your own. Do not copy another student's work. You must do the projects as a group but not with other groups and without consulting previous years' students, code, etc. You should help other students and groups on specific technical issues but you must acknowledge such interactions. Copying code or other work without giving appropriate acknowledgment is a serious offense with consequences ranging from no credit to potential expulsion.

Textbooks

Required: Recommended:

Languages

This course relies on three different programming languages:

  • The source language is the language of programs serving as inputs to the translator; it is a restricted version of Java.
  • The target language is the language of outputs of the translator; it is a restricted version of C++.
  • The translator language (for lack of a better term) is the language of the translator itself; it is the full Java 5.0 née JDK 1.5 language.

In more detail, the source language is Java without nested classes, anonymous classes, interfaces, enums, annotations, generics, the enhanced for loop, varargs, and automatic boxing and unboxing. Furthermore, the source language omits support for synchronization, i.e., synchronized methods and statements, and strict arithmetic operations, i.e. the strictfp modifier. It also omits support for transient and volatile fields as well as native methods. Finally, you may omit method overloading but not method overriding for the first version of the translator.

The target language is C++ without virtual methods, inheritance, and, in general, templates. It also omits features new to C++11, notably lambda abstractions and type inference, e.g., auto and decltype. It does, however, include gcc's statement expressions, i.e., ({ … }). When compared to C, the target language does include support for basic classes, exceptions, and name spaces. For the first version of the translator, you can ignore memory management and assume an infinite main memory. For the second version of the translator, you need to automatically reclaim unused memory through a so-called smart pointer. The smart pointer library, as well as any library support for implementing Java arrays, may use templates.

Most Java statements and expressions translate directly into the corresponding C++ statements and expressions (modulo minor language differences). As a result, the main challenges for the course project are figuring out (1) how to translate Java class hierarchies into C++ without inheritance and (2) how to implement Java’s virtual method dispatch in C++ without virtual method dispatch, (3) how to select the right overloaded method, and (4) how to automatically manage memory without an existing garbage collector. Note that we will explore how to approach each challenge in class; we will also leave the latter two challenges for the second version of the translator.

Besides the programming language itself, any version of Java includes a rather extensive set of platform libraries, with the facilities in the java.lang package being tightly integrated with Java’s execution model. For our translator, we only support the hashCode(), equals(), and toString() methods in java.lang.Object and the printing of numbers and strings through out.print() and out.println() in java.lang.System. Furthermore, we do not support the dynamic loading of Java classes, but rather translate all Java classes of the source program into one C++ program.

Please note that the translator need not perform any correctness checks on source programs; in other words, you can assume that source programs are free of compile-time errors. At the same time, when writing your own Java test programs, it seems prudent to test them with a regular Java compiler.

Syllabus

Week Date Topics Materials and Assignments
1 09/03 Introduction Slides
09/05 Our first Java class: a four-dimensional point. Notes; Point.java; Read OODP ch. 1 before class
2 09/10 Our first C++ class: a four-dimensional point. Names, sources, and binaries; Notes;
Point.h; Point.cc; Main.cc; Read CFJP ch. 0, 1, 2, and 4 up to and excluding 4.6 before class.
09/12 Designing our translator: CRC cards and UML at work. Notes;
Read OODP ch. 2 before class
3 09/17 Tools: git, make, and xtc. Notes; Translator.java;
Homework 1
Install xtc and read OODP ch. 3 before class
09/19 Tools: git; unit testing with JUnit; Q & A. Notes; PointTest.java
4 09/24 Inheritance, method overriding, and virtual method dispatch. Notes; Code; Alternative impl. of ColorPoint;
Read OODP ch. 4 and 6 before class
09/26 Implementing inheritance and virtual method dispatch by hand. Notes; Code
5 10/01 Tools: debugging and logging. GDB Debugging tutorial; Boost logging framework
10/03 Object-oriented design revisited: when should I use class inheritance? Notes
6 10/08 All about arrays, incl. how to translate Java arrays into C++ Notes; Code
10/10 Generics: a better translation of Java arrays into C++ Notes; From raw lists to generic lists in Java; and C++; Code for improved array translation; Read OODP chapter 8.3 and CFJP chapter 7 before class.
7 10/15 No class: fall recess
10/17 Design patterns: the visitor design pattern Notes; Code for calculator with easy extensibility of expressions and with easy extensibility of operations; Read OODP chapters 5 and 10 before class.
8 10/22 More on generics: variance and wildcard parameters
10/24 Midterm project presentations
9 10/29 Method overloading in Java Notes; Code; Overloading resolution procedure according to the Java Language Specification
10/31 Method and operator overloading in C++ Notes; Code; Read CFJP chapter 5 before class.
10 11/05 Reflection: dynamically dispatched visitors in xtc Notes; Code; Homework 2
Read OODP chapter 7 before class.
11/07 Scoping: xtc's symbol table class Code
11 11/12 Explicit memory managment in C++ Notes; Code; Read CFJP chapters 3.3, 4.6, and 6.3 before class.
11/14 No class
12 11/19 Smart pointers in C++: a reference-counting garbage collector Notes; Code; Read this article before class.
11/21 The casts of C++ Notes; Code; Read CFJP chapters 1.4.1 and 6.7 before class.
13 11/26 Q & A
11/28 No class: Thanksgiving
14 12/03 Traits and Iterators in C++ Notes; Code; Read part 1 and part 2 of O'Reilly's tutorial on C++ iterators.
Homework 3
12/05 Next Generation OO Languages:
A Glimpse of Scala 		demo.scala
15 12/10 Q & A - the object-oriented programming potpourri.
12/12 In-class Final Exams Study guide
16 12/15 11:59pm EST - project source code submission deadline
12/19 4:00-5:50pm - final project presentations

Tools and Resources

For Java, we use the Java 2 Platform Standard Edition 5.0, née JDK 1.5, or later. Oracle provides an implementation for Linux. Apple provides an implementation with Mac OS X, no installation required. In either case, you need to separately install Java’s API documentation. In the case of Mac OS, the documentation is included with Xcode, Apple’s IDE.

For C++, we use gcc, the GNU Compiler Collection, as our compiler. It is the default compiler for Linux and included with Apple’s Xcode for Mac OS X.

If you are running Windows, please dual-boot into Linux or use a virtual machine monitor such as VirtualBox for running Linux. Trying to make gcc and make work on Windows (i.e., through a Unix emulation layer such as Cygwin) is not recommended.

Like many large-scale software projects, we rely on a version control system such as git to manage program sources and on make to automate the build management. If you are using github or a similar service, please make sure that your repository is not publicly visible.

To simplify the task of reading source files in one language, translating them into another language, and then printing source files for that language, we use the xtc toolkit for source-to-source translators. xtc includes a parser for Java source files, which converts the external, textual representation into an internal tree representation. It also includes support for traversing, modifying, and pretty-printing such trees.

You may also find the following resources useful: