Programming Languages Semester-Conversion Course Group Report (Draft)

(Note: This report summarizes our deliberations related to the conversion of the programming languages group of courses in the transition to semesters. Among other things, it highlights how our evaluation of results of assessments of the intended outcomes of various existing courses in the group has helped inform the design of the semester versions of these courses. Each course group is expected to prepare a similar report; more details are available here. This report will be presented to the Curriculum Committee in Spring 2010.)

Course no. Title Credit
Reqd (R)/
Elective (E)
CSE 421 Software Development in Java 3 E *
CSE 459.XX Programming Languages
for Programmers
1 R *
CSE 655 Intro. to Principles of
Programming Languages
4 R
CSE 755 Programming Languages 3 E
CSE 756 Compiler Design &
4 E
* : Students are required to take 421 or at least one 459.XX

I. Background

Programming languages is an essential topic of any CSE program. Indeed, many people outside the field have the mistaken impression that learning the syntax of a couple of languages and writing a few simple programs in each is all there is to CSE. Our courses have been designed in such a way that students do become familiar with programming in different languages; but at the same time, they also master the conceptual foundations underlying different languages as well as the problems that arise and solutions to implementation of languages; and are exposed to alternative programming paradigms such as functional programming.

II. Current set of courses in the group

CSE 655 is the main (undergraduate) course in the group. It is required of all CSE majors. It not only brings together ideas from a number of earlier courses in the program such as CSE 321, 560, 625, and Math 366 but also, and unlike courses such as CSE 625 and Math 366, often addresses issues in a way that is directly related to actual practice. The learning outcomes for the course are:
  1. Master using syntax-related concepts including context-free grammars, parse trees, and recursive-descent parsing, printing, execution and code generation.
  2. Master analyzing programming language design issues related to data types, expressions and control structures.
  3. Master analyzing data abstraction-related issues.
  4. Master implementation techniques for imperative languages.
  5. Be familiar with analyzing variable binding and scope rules.
  6. Be familiar with analyzing parameter passing methods.
  7. Be familiar with principles of object-oriented languages.
  8. Be familiar with implementing object-oriented languages.
  9. Be familiar with using functional programming languages.
  10. Be familiar with implementing functional programming languages.
A key activity in the course is the implementation of a recursive-descent interpreter for a simple imperative language. This project contributes to a surprising extent to the achievement of a number of the above outcomes. Another important activity is the implementation of a simple set of functions in Scheme. For most students, this is the first exposure to functional programming and this project, although relatively simple for experienced Scheme/Lisp programmers, provides considerable help to students both in their conceptual understanding of functional languages as well as in developing their skills in thinking in a functional style. Other activities consist of homeworks designed to help students achieve the various outcomes.

CSE 421 is a relatively new course that cuts across the programming languages and the software engineering groups of courses. The course was developed with two considerations in mind. First, there was a consensus among faculty, based on performance of students in CSE 560, that a number of students seem to experience considerable difficulty in moving from the CSE 221-222-321 sequence where their program development activities are, in a sense, carefully orchestrated by the instructors, to CSE 560 where they have to engage in a substantial design and development effort with much less guidance and/or constraints. Thus it was felt that a "bridge course" that helped with the transition would be useful. Second, Java has becoming increasingly important in industry and students would benefit by developing their skills in that language. CSE 421 was designed to meet these needs. (The original intent was that, after it had been developed, we would make it a required course for both BS-CSE and BS-CIS majors; but, in the meantime, OSU decided to switch to semesters. Nevertheless, the experience of developing and teaching 421 has been valuable in developing some of our proposed semester courses.) The learning outcomes for the course are:

  1. Master core Java language features including: objects, classes, interfaces, inheritance, and exceptions;
  2. Master core SDK packages including: collections framework, logging, and IO;
  3. Master core best practices for component-based development including: separation of abstract state and concrete representation and coding to the interface;
  4. Master the use of a modern IDE, such as Eclipse;
  5. Be familiar with advanced language features including: iterators, generics, and assertions;
  6. Be familiar with foundations of an object-oriented paradigm, in particular: encapsulation, inheritance, and polymorphism;
  7. Be familiar with the application of design patterns including: immutable objects, factories, and singleton objects;
  8. Be familiar with best practices with regards to object equality, object cloning, and checked/unchecked exceptions;
  9. Be familiar with CVS, JUnit, and Javadoc;
  10. Be exposed to advanced SDK packages including: Swing for GUIs and network programming;
  11. Be exposed to exotic language features including: nested classes, nested interfaces, and annotations;
One of the key course activities to help achieve these outcomes is a long series of carefully designed programming tasks that, on the one hand enable the students to become familiar with various aspects of Java, its libraries, and other industry-standard tools, and, on the other hand, sharpen their skills in designing and implementing software that meets given specifications.

CSE 459 is a set of one-credit courses, each intended to help students become familiar with a specific programming language. Both BS-CSE and BS-CIS majors are required to take one of these courses as part of their program. The intent is that students will develop some skills in at least one other high level language in addition to Resolve-C++. (Of course, as noted above, students also acquire some facility in Scheme as part of CSE 655.) Here we consider one of the 459 courses, 459.51, the one on Perl; others are similar. The learning outcomes for 459.51 are:

  1. Be familiar with Perl's data types.
  2. Be familiar with text and file manipulations using Perl.
  3. Be familiar with using DBI to access a database.
  4. Be familiar with basic CGI scripts written in Perl.
These outcomes are achieved via a series of relatively small programming assignments.

CSE 755 is a continuation of CSE 655 but with a strong focus on the theoretical foundations. Some of the topics in this course are attribute grammars; approaches to defining operational semantics including the meta-circular approach used in languages such as Lisp; a thorough discussion of the axiomatic semantics, and its application to reasoning about program behavior; some discussion of denotational semantics; and, in some offerings, brief discussion of the use of language semantics to compiler correctness and optimization questions. The course is geared toward graduate students but some undergraduates with a strong interest in foundational questions, especially those considering graduate studies, take it as an elective. The learning outcomes for the course are:

  1. Master using attribute grammars for specifying context-sensitive grammars.
  2. Master using the meta-circular approach to defining operational semantics of Lisp.
  3. Master using the axiomatic approach to reasoning about the behavior of imperative programs.
  4. Be familiar with using structured operational semantics.
  5. Be exposed to using denotational semantics.
A key activity in the course is implementation of a Lisp interpreter; this helps achieve the second outcome. Other activities typically consist of a series of homeworks dealing with attribute grammars, axiomatic semantics, etc.

CSE 756 is also a continuation of CSE 655. Students in this course study, in depth, the various problems in implementing compilers for programming languages and possible solutions. They put these solutions into practice by designing and implementing a compiler for a standard imperative programming language. This is a fairly demanding and extensive programming task and brings together ideas that students have seen in a variety of courses, from CSE 560, CSE 625, and CSE 655. This course usually sees a mixture of undergraduate and graduate students. The learning outcomes for the course are:

  1. Master using lexical analyzer and parser generator tools.
  2. Master building symbol tables and generating intermediate code.
  3. Master generating assembly code for a RISC machine.
  4. Master programming in Java.
  5. Be familiar with compiler architecture.
  6. Be familiar with register allocation.
  7. Be exposed to compiler optimizations.
The main student activities in the course that help achieve these outcomes is a carefully designed series of programming projects.

III. Evaluation of courses

CSE 655: Recent POCATs have included a few questions related to 655. We are in the process of creating a more comprehensive set with one or more questions corresponding to each of the mastery, competence, and familiarity-level outcomes. These will be added to the (password protected) POCAT question bank as they become available.

One of the POCAT questions concerns memory management issues in C++ and Java; the question asks whether C++ programs are more or less likely to have memory-related bugs than Java programs. About 80% of the students answer this question correctly. A second question asks, given two languages one of which has polymorphism and the other doesn't, which will have virtual calls. Again about 80% of the students answer this question correctly. Both of these questions might be considered a bit too easy, especially given the expected levels of achievement of the corresponding outcomes. A third question, included in a recent POCAT, asked how Java manages to flag uninitialized variables at compile time when the problem of uninitialized variables is, in general, a runtime issue. Just under 40% of the students answered this correctly; it is not clear whether this indicates a real problem or students might have been confused by the fact that Java automatically initializes some memory locations (e.g., object fields). We will refine this question in future POCATs to see if the performance improves. A last question, also included in a recent POCAT, related to data abstraction. 50% of the students answered this correctly; this is rather low given that data abstraction is a main topic of the CSE 221-sequence. POCAT also includes a couple of questions on formal grammars, based on the material in CSE 625 (formal language and automata theory). Although students answer those questions satisfactorily, our experience in 655 indicates that they don't seem to apply that knowledge in the programming language domain as effectively as one might wish.

Student performance in the various activities in the course has been reasonably satisfactory. Most students (two-thirds or so) finish the interpreter project satisfactorily; another 10 to 15% or so don't quite finish but get most of it completed. Student performance in the Scheme program is also more or less satisfactory. Other activities in the course (homeworks, midterms, final exams) do not indicate any major problems; but see comment at the end of the para above concerning applying formal grammars to programming languages.

Thus the course outcomes are being achieved. However, based on the above evaluation, the following changes seem indicated:

  1. With respect to the outcome, master using syntax-related concepts including context-free grammars, parse trees, and recursive-descent parsing, printing, execution and code generation: More extensive discussion of grammars in the context of programming languages (instead of in the context of formal languages as in the current CSE 625) would help.
  2. With respect to the outcomes, master implementation techniques for imperative languages; and Be familiar with implementing object-oriented languages: More detailed discussion of implementation issues including, memory management techniques; and, at a higher level, a more detailed discussion of different approaches to object construction, initialization, and destruction; would both help.
  3. With respect to the outcome, master analyzing data abstraction-related issues: More detailed discussion of how data abstraction works from the points of view of the client and the provider would help
We are in the process of implementing the third change. Unfortunately, there is not enough room in a quarter-long course to make the first two changes; the semester version of the course has been designed to account for these changes.

CSE 459.51: Since this (like the other 459's) is a one-credit course focusing mainly on technical details of a particular language, and since different students take different 459's, so far we have not included questions on the POCAT about these courses. However, we are currently exploring the possibility of doing so. Currently, the evaluation of the course is based on the student activities in the course these being, as noted earlier, simple programming tasks in Perl (or other languages in the case of the other 459's).

Student performance in these programming tasks has been generally satisfactory. However, some changes have been implemented based on this performance and the intended course outcomes:

  1. All of the outcomes: Offer students who are interested in more challenging work, an additional programming project that requires them to explore some aspect of Perl on their own.
  2. Beyond the existing outcomes: In some offerings of the course, discuss how OO programming might be implemented in Perl.
The semester-version of the course is planned to be similar to the quarter-version. However, one key additional outcome will be added: Be competent with combining Perl's mechanisms and techniques to solve complex, practical problems. In one sense, this is not a new outcome since an implicit idea of the course has been to help the students become capable in combining the various facilities of Perl to solve practical problems but this outcome will make that explicit.

CSE 421: Talk to Paul about this and get his evaluation as well as a couple of POCAT questions.

CSE 755: Since relatively few undergraduate students take this course, there are no 755-based questions on the POCAT. The performance of students in the various activities in the course varies quite a bit with the activity. Most students not only do very well in the Lisp interpreter project and complete it satisfactorily but also find it both challenging and rewarding. Students also do well in the homeworks and midterm/final exam problems related to attribute grammars and Lisp (both the language and implementation topics). On the other hand, many students have difficulties with axiomatic semantics and formal correctness proofs. This, not surprisingly, varies with students; students with a strong background in math logic or similar topics enjoy this part of the course and do very well; others without such background seem to understand the material at a high level but tend to be confused by the details. At the same time, the approach of abstract interpretation, which is currently not included in the course, as a way to define semantics that enables us to provide less than complete information about programs may be worth exploring. One other item that comes up in class discussions, although it is not currently an explicit part of the course or the outcomes, is type-related topics such as algorithms for type inference used in some languages.

Thus, overall, the current course outcomes are being achieved. Based on the above evaluation, the following changes would seem indicated when we move to semesters:

  1. With respect to the outcome, master using the axiomatic approach to reasoning about the behavior of imperative programs, reduce the level of this outcome.
  2. Consider adding an outcome related to abstract interpretation as a precise approach to providing reliable but incomplete information about program behavior.
  3. Consider adding an outcome related to types, type inferencing etc.

CSE 756: As with 755, 756 is a course primarily taken by graduate students. No 756-related questions are included in POCAT. In general, the performance of students in this course is very good, as evidenced by their results on the sequence of programming projects. Students do not seem to have problems with topics introduced in the early parts of the course (i.e., generation of scanners and parsers with the help of automated tools), because in past courses (e.g., 625) they have already seen regular expressions and context-free grammars. The topics related to generation of intermediate code tend to be harder, but overall performance is still high. For both groups of topics, the course outcomes are achieved. For topics related to compiler optimizations (e.g., control-flow and dataflow analysis), project results and performance on the final exam indicate that the outcomes are also achieved. Due to time limitations imposed by the quarter system, it is not possible to have a project on generating assembly code, and the level of competency is not "mastery" as stated in the current course outcomes. The course was not offered for several years because of lack of faculty resources. The course has been taught regularly since 2009 and the experience of these offerings has informed the design of the semester-level version of the course.

Based on the above evaluation, the following changes would seem indicated when we move to semesters:

  1. The "master programming in Java" outcome is not appropriate for a compiler course and should be removed. Furthermore, several other courses (in particular 421) already achieve this outcome. (After the transition to semesters, this will be achieved by the Software I, II sequence.)
  2. "Master building symbol tables" is of little value in this course, since in realistic applications there will already be a compiler front end that provides this functionality. One such example is the compiler infrastructure used for most course projects (the ROSE front end from the Lawrence Livermore National Lab). This outcome is dated and should be eliminated.
  3. "Be exposed to compiler optimizations" is inadequate, since the most recent intellectual advances and practical applications of compilers are focused on this topic. Competency or at least familiarity-level outcomes are necessary for compiler optimizations (including ones for parallelism) and the underlying static analysis machinery (control-flow and dataflow analysis).
  4. An outcome related to typechecking in compilers must be added because this is an important topic, especially for modern object-oriented languages with rich type systems.

IV. Other considerations in switching to semesters

  1. The software spine group has decided that the beginning courses (Software I, II) should be in Java rather than Resolve-C++. This decision was partly based on the fact that Java (and C# which is rather similar to Java) are very widely used in industry and C++ seems to be losing ground slowly. Given this, there is no reason to have a separate CSE 421. At the same time, many of the lessons learned from CSE 421 have informed the design of Software I and II.
  2. There is not enough credit hours in the semester program to require all students to take a course similar to the current 459's. At the same time, some of these courses seem very valuable; so it will be useful to develop similar 1-credit courses for at least some of the languages and offer them as tech electives.
  3. At other universities, the course that is closest to CSE 655 shows quite a bit of variation from one university to the next. At the same time, each of the topics in the current 655 appears prominently in many of these courses. Hence the semester version of the course should be based primarily on the current content of CSE 655.
  4. At the same time, faculty decided that students should have a choice of taking either this course or the "theory" course, i.e., the course that will take the place of the current CSE 625. This means that the programming languages course cannot assume that students would have a background in formal languages and automata theory as we do currently.
  5. As in the case of CSE 655, there is quite a bit of variation across other universities in the course that is closest to CSE 755. Our 755 seems unique in the stress it plays on axiomatic semantics; moreover, it is also unique with respect to not including discussion of formal type-related topics. The changes proposed above were based in part on comparison with the courses at other universities.
  6. Hands-on projects to implement simple compiler optimizations and subsequent assembly code generation are often part of compiler courses in other universities. The limitations of the quarter system make it impossible to have such projects in the current course. In the semester version of 756, these projects should certainly be included. Time permitting, a project on type checking should also be included in the new course.

V. Proposed courses under semesters

... to be completed; may just contain copies of the proposed syllabii.

VI. Other information

... such as expected future directions in the group, a list of people involved with the group, etc.

May be standard stuff about how programming languages, their design, implementation approaches, formal theories of program behavior, etc., continue to be a central part of CSE. Hence these courses will continue to be as important as ever for the foreseeable future?

People involved in preparing report: Neelam Soundarajan, Atanas Rountev, Paul Sivilotti, Robert Joseph, ...

Neelam Soundarajan
(Draft: Feb. 2011; Final: ??).