Course Group Status Report

1. Summary

As explained in detail in Section 2.4, courses in this group contribute to our students' achieving a number of EC 2000 and CSE outcomes. Briefly, the variety of programs that students are required to design and implement to solve problems of varying difficulty, using ideas from discrete mathematics, formal languages, etc., ensures that these courses contribute toward achieving CSE program outcomes I.i, I.ii, I.iii and V.iii as well as EC 2000 outcomes 3.a, 3.c, and 3.e; the documentation that these systems require as well as the active class discussions that are a common feature of especially CSE 655, enables these courses to contribute to CSE outcome IV.ii, as well as EC 2000 3.g; the range of modern languages and tools that the students work with in these courses help these courses contribute toward meeting CSE outcome V.i and V.ii as well as EC 2000 outcomes 3.i and 3.k; and the focus on ensuring that the students' programs are well designed and function correctly as well as discussions about common causes (such as memory leaks) for failures in real systems, help these courses contribute toward meeting CSE outcomes III.ii, V.i and V.ii, as well as EC 2000 outcomes 3.f, 3.i and 3.k.

Students and faculty are generally very satisfied with the courses in this group. Students find CSE 655 a very worthwhile course; it not only brings together ideas from a number of earlier courses in the program such as Math 366, CSE 321, CSE 560, and CSE 625, but often addresses issues in a way that is directly related to actual practice.

2. Detailed Analysis

Section 2.2 was added following recent discussions in the Curriculum Committee on the structure of Course Group Reports and the committee's decision to include such an evaluation in the reports. The proposal that the committee discussion was based on is available.

2.1 Summary of the courses

CSE 655: This is the main course on programming languages. It is not a survey of languages; rather, the course is intended to ensure that the students gain a thorough understanding of the major concepts underlying different languages; use standard ways of describing programming language features; and gain an appreciation of alternate programming paradigms such as functional programming and, to a very limited extent, logic programming. Students also gain a thorough understanding of ways of implementing languages such as compilers and interpreters, as well as run-time questions such as memory management. A common student project in this course is to implement a simple programming language; this allows students to gain a first-hand appreciation for problems ranging from parsing the input program, to detecting errors (both compile-time and run-time) in the program, to managing memory. This project is a natural extension of a similar project that students are assigned in CSE 321; in that project, students are required to implement a compiler (using an artificial target language) for a very simple "bugs world programming language". Seeing the ideas of recursive descent parsing and compilation/interpretation in a second project in 655 that is both more involved and in which they receive less assistance with building the final implementation helps reinforce the lessons on this topic from 321, especially since in the meantime, students have also taken 625 which gives them a thorough grounding in theoretical ideas involving formal grammars.

Another common programming task is to have students design and implement a program in a language like SCHEME to acquire some facility for functional programming.

Students take CSE 655 in their late junior year or early senior year. By that time some of them have had some industrial experience, either as interns or as part-time employees in local software companies. Naturally they bring their experiences with various languages to the classroom, often leading to illuminating discussions relating the CSE 655 topics to actual industrial practice. There are also extended discussions on software engineering related issues, including important ideas from the Software Spine, and how they are reflected (or not) in individual languages.

CSE 755: This is a continuation of CSE 655 but with a strong focus on the theoretical foundations underlying programming languages. Some of the topics in this course are attribute grammars and their use in specifying context sensitive conditions as well as a discussion of how compilers can check these conditions using the attribute grammar specifications; approaches to defining operational semantics including the meta-circular approach used in languages such as Lisp, as well as a thorough discussion of how an implementation of Lisp may be based on such a specification; a thorough discussion of the axiomatic semantics, and its application to reasoning about program behavior; some discussion of the use of language semantics to compiler correctness and optimization questions. CSE 755 is geared toward graduate students but some undergraduates with a strong interest in foundational questions, especially those considering graduate studies, take this course as an elective.

CSE 756: This is also a continuation of CSE 655. Students in this course study, in depth, the various problems in implementing compilers for programming languages and study various 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.

2.2 Evaluation of courses

• be familiar with csh programming;
• be familiar with UNIX regular expressions;
• be familiar with using basic sed commands; and
• be familiar with using awk commands to filter through data files.

CSE 459.22 lists three learning objectives:

• master using the most common C language constructs;
• be familiar with using some techniques for avoiding typical C programming errors;
• be exposed to useful system-level functions provided by the C library.

CSE 459.23 lists four learning objectives:

• master using C++ classes, member functions, constructors, destructors etc.;
• be familiar with using templates and the C++ standard template library (STL);
• be familiar with using inheritance;
• be exposed to using virtual functions, dynamic dispatch.

CSE 459.31 lists four learning objectives:

• be familiar with the Lisp family of progrmaming languages, with particular emphasis on ANSI Common Lisp;
• be familiar with basic components of Common Lisp, such as s-expressions, data structures, and program flow;
• be familiar with the Lisp top-level and debugger;
• be exposed to the functional programming paradigm.

CSE 459.41 lists two learning objectives:

• master the syntax involved in writing COBOL programs;
• be familiar with the reasons for implementing and using COBOL code.

CSE 459.51 lists four learning objectives:

• be familiar with Perl's data types;
• be familiar with text and file manipulations using Perl;
• be familiar with using DBI to access a database;
• be familiar with basic CGI scripts written in Perl.

CSE 655 lists the following learning objectives:

• master using syntax-related concepts including context-free grammars, parse trees, and recursive-descent parsing, printing, execution and code generation;
• master analyzing programming language design issues related to data types, expressions and control structures;
• master analyzing variable binding and scope rules;
• master analyzing parameter passing methods;
• master implementation techniques for imperative languages;
• master analyzing data abstraction-related issues;
• be familiar with principles of object-oriented languages;
• be familiar with implementing object-oriented languages;
• be familiar with using functional programming languages;
• be familiar with implementing functional programming languages.

CSE 755 lists the following learning objectives:

• master using attribute grammars for specifying context-sensitive grammars;
• master using the meta-circular approach to defining operational semantics of Lisp;
• master using the axiomatic approach to reasoning about the behavior of imperative programs;
• be familiar with using structured operational semantics;
• be exposed to using denotational semantics.

CSE 756 lists the following learning objectives:

• master using lexical analyzer and parser generator tools
• master building symbol tables and generating intermediate code;
• master generating assembly code for a RISC machine;
• master programming in Java;
• be familiar with compiler architecture;
• be familiar with register allocation;
• be exposed to compiler optimizations.

2.3 Relation to rest of the program

CSE 459, usually 459.21 or 459.22, is a prerequisite for a number of courses such as CSE 662, CSE 677, etc. that have programming labs that use C or C++. Again, given the students' software development experience from CSE 321, 459.21 or 459.22 provides the students with the appropriate programming skills needed to complete these labs.

CSE 655: The prerequisites for CSE 655 are CSE 560 and 625 (which in turn has Math 366 as a prerequisite). CSE 625 provides students with the formal machinery (such as regular expressions and context free grammars) needed to gain a thorough understanding of the concepts underlying various languages, and to serve as a basis for suitable implementations of the languages. And the discussion of functional programming in 655, given the essential and natural role that recursive thinking plays in this discussion, builds on the exposure that students have had to recursion in earlier courses, including Math 366 and 625.

CSE 560 provides students with a conceptual model of the underlying hardware including the memory, so that students can appreciate the constraints that language implementations have to work with. Too, the solid software development experience of CSE 560, including the need for proper documentation, serves the students well in their 655 project. Thus these prerequisites prepare students well for CSE 655.

CSE 655 serves as a prerequisite for CSE 721, CSE 755, and CSE 756. CSE 721 is a course on Parallel computing (which relatively few undergraduates take); CSE 655 prepares students for this course by ensuring that they have a thorough understanding of sequential programming languages and implementation questions concerning them. CSE 755 as described earlier in this report builds on CSE 655; it focuses on the theoretical foundations of programming languages. CSE 756, also as described earlier, continues the 655-discussion of implementation of languages. CSE 655 is serving the needs of these courses well.

CSE 755: The prerequisite for CSE 755 is CSE 655. CSE 655 provides students with both the formal machinery concerning context-free grammars of languages, as well as the maturity in terms of having a good grasp of general language concepts including run-time issues. The understanding of automata-theoretic ideas that students gain in CSE 625 (which is a prereq for CSE 655) also helps students in CSE 755 since this course builds on those ideas. Finally, students get to see, in CSE 755, the precise basis for ideas such as pre- and post-conditions, as well as loop invariants, that they have been exposed to since CSE 221.

CSE 755 is a prerequisite only for research seminars (CSE 788.XX and CSE888.XX). These are primarily geared towards PhD students, so very few undergraduate students take these courses.

CSE 756: The prerequisites for CSE 756 are CSE 625, CSE 655, and CSE 680. CSE 756 builds on the material in both CSE 625 and CSE 655. Scanning and parsing techniques which are a main topic of CSE 756 are heavily dependent on finite-state as well as push-down automata and other mechanisms which students study from a formal point of view in CSE 625. The interpreter project in CSE 655 also requires students to do parsing but the grammar of the underlying language is sufficiently simplified that students do not need to see many of the complexities that they see in CSE 756 and that are unavoidable in a real compiler. CSE 756 also, of course, builds on the 655 material, in particular run-time mechanisms appropriate for static scope languages since students implement such mechanisms in their 756 compiler project. CSE 680 is less directly connected with 756; nevertheless, many of the data structure and algorithms that students study in 680 have important connections to the kinds of structures and algorithms they use in 756.

CSE 756 is not a prerequisite for any other course.

In summary, the prerequisites for the courses in the group are satisfactory. And the few courses that have courses in the group as prerequisites are satisfied with the courses.

2.4 Relation to program outcomes

2.4.1 CSE Outcomes

1. Students will:
   1. Demonstrate proficiency in the areas of software design and development, algorithms, operating systems, programming languages, information systems, and computer architecture.
   2. Demonstrate proficiency in relevant aspects of mathematics, including discrete mathematics and probability, as well as electrical circuits and devices.
   3. Successfully apply these principles and practices to a variety of problems.
2. Students will:
   1. Demonstrate an understanding of differential and integral calculus, and of statistics.
   2. Demonstrate an understanding of the basic principles of physics and at least one other laboratory-based science.
   3. Demonstrate an understanding of the basic principles of at least one other engineering discipline in addition to computing and electrical engineering.
3. Students will:
   1. Demonstrate familiarity with basic concepts and contemporary issues in the social sciences and the humanities.
   2. Demonstrate an understanding of social, professional and ethical considerations related to engineering in general and to computing in particular.
4. Students will:
   1. Demonstrate an ability to work effectively in teams.
   2. Demonstrate an ability to communicate effectively.
5. Graduates will:
   1. Find suitable positions in industry and government that offer the prospect of challenging and rewarding careers in computing.
   2. Demonstrate an ability to acquire new knowledge in the computing discipline and to engage in life-long learning.
   3. [Graduates with an aptitude for, and interest in, graduate studies will] Apply to and be accepted for entry by strong graduate programs in computing.

By allowing students to apply, in a new programming language, the skills they have gained in CSE 221-222-321, CSE 459 contributes toward meeting CSE outcomes I.i and I.iii. In CSE 655 students gain a thorough understanding of important concepts underlying programming languages and how they are implemented; thus it contributes very strongly towards meeting outcome I.i. The students practice what they learn on reasonable sized programming projects and other homework assignments, hence I.iii is also strongly met. Outcome I.ii is also met since students rely heavily on ideas from discrete mathematics from Math 366 and CSE 625. CSE 755 also contributes toward I.i and I.ii, by providing students with a thorough understanding of the mathematically sound foundations underlying key programming language constructs. And CSE 756, because of its extensive use of formal, mathematical ideas underlying programming languages and algorithms built on these ideas, contributes toward CSE I.i, I.ii and I.iii.

By providing coverage of languages that students are likely to use in their future employment, CSE 459 contributes strongly towards meeting CSE outcome V.i. Much of the material in CSE 655, dealing with implementation problems of realistic languages is directly related to actual practice in the software industry, so CSE 655 also strongly contributes toward meeting V.i. CSE 756 also contributes substantially toward meeting V.i since the techniques employed as well as the tools used (such as lex and yacc) in this course are frequently used in industry.

The documentation that is required to accompany the various programming tasks in these courses, from the relatively simple ones in CSE 459 through the much more involved programs in CSE 655 to the compiler project in CSE 756 all allow us students to improve their (written) communication skills. The frequently interactive nature of the CSE 655 lectures helps willing students to participate in expressing ideas in a group setting, and thus improve their oral communication abilities. Thus these courses help us meet outcome IV.ii to a moderate extent.

The attention paid in CSE 655 to such problems as memory leaks that may occur unless appropriate steps are taken in language implementation, as well as usability problems resulting from poorly designed syntax or user interfaces, and the professional responsibility of software engineers to pay attention to such problems, helps this course contribute toward meeting outcome III.ii. In addition, and indeed even more important, is the concern for ensuring that the software they design, such as the interpreter that students build in CSE 655, functions correctly. All of these concerns also form an important part of the compiler project in CSE 756, so that course too contributes toward this outcome. Correctness concerns are also central to CSE 755, thus that course also contributes to this outcome.

The focus, in CSE 755, on foundational issues underlying programming languages, as well as the facility that students gain in CSE 655 and CSE 756 in using mathematical tools such as regular and context free grammars helps these courses prepare interested students for advanced studies in good graduate programs, thereby contributing toward meeting outcome V.iii.

The frequent classroom discussions in CSE 655 involving students with a range of backgrounds (including some with a reasonable amount of industrial experience) improves the ability of students to work with people with different backgrounds. Further, in both CSE 655 and CSE 756, students are encouraged to (and do) carry on extensive on-line discussions (on dedicated newsgroups) about problems they encounter in their projects. Thus these courses help us meet outcome IV.i to a limited extent. These courses also contribute to outcome V.iii; CSE 459 prepares students to pick up new programming languages on their own; CSE 655 provides the basic foundation that enables students to ask the right questions both about language concepts and implementation issues when encountering a new language; CSE 756 strengthens this foundation by providing a deeper understanding of problems that are commonly encountered in real implementations of languages.

The contribution that these courses make toward meeting various CSE outcomes is summarized in the following table:

2.4.2 EC 2000 Criterion 3 Outcomes

1. an ability to apply knowledge of mathematics, science, and engineering
2. an ability to design and conduct experiments, as well as to analyze and interpret data
3. an ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
4. an ability to function on multi-disciplinary teams
5. an ability to identify, formulate, and solve engineering problems
6. an understanding of professional and ethical responsibility
7. an ability to communicate effectively
8. the broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context
9. a recognition of the need for, and an ability to engage in, life-long learning
10. a knowledge of contemporary issues
11. an ability to use the techniques, skills, and modern engineering tools necessary for modern engineering practice.

The variety of programs that students design and implement to solve problems of varying difficulty in CSE 459, CSE 655, and CSE 755, contribute strongly toward meeting criterion 3c. Further, the range of languages and tools that the students not only use in these courses but also analyze (in CSE 655 and CSE 756), strongly contributes toward meeting criterion 3k.

The use of mathematical concepts such as regular expressions and context free grammars in CSE 655 and CSE 756, and the even more detailed mathematical basis that CSE 755 builds on, help these courses contribute toward meeting criterion 3a. The need for debugging and correcting problems in the systems that the students design and implement in these courses contributes toward meeting criterion 3b. The focus on building correctly functioning software, as well as the attention paid in CSE 655 to common sources (such as memory leaks) of problems in software systems and ways of avoiding these problems, help the students understand the professional responsibilities of software engineers, contributing toward 3f. The documentation that students are expected to provide for the systems they design in these courses, as well as the frequent class discussions in CSE 655 help these courses contribute toward meeting 3g. Further, the range of (to them) new languages and tools that students in these courses have to explore and use, makes a contribution towards stressing the importance of life-long learning, criterion 3i. This is especially so in CSE 655 because of the functional programming project that it includes; this project requires students to formulate the problem in a very different form than they have used in solving programming problems elsewhere in the curriculum, given that the basic primitives of functional programming are quite different from the ones the students have been used to since their beginning courses.

The contribution that these courses make toward meeting various EC 2000 Criterion 3 outcomes is summarized in the following table:

2.5 Major changes since the previous report

Three new 459's have since been developed: 459.23 on Java; 459.61 on Perl; and 459.11 on Unix Programming Environment. Of the other languages/systems mentioned in the previous report, Tcl/Tk seems to have been replaced by a variety of tools to help designers build GUI systems of various kinds. Python is still used but not as widely as Perl. Given this, for now there are no plans to develop additional 459's.

Changes in 755: The previous report noted: "... students find the CSE 755 a bit too theoretical, and we are exploring ways to address this..."

The 755 material has been somewhat modified. It now includes a fairly extensive programming project, requiring students to implement a Lisp interpreter. While this is a very practical programming task, it relates very naturally with the theoretical discussion of operational semantics in the course and thus helps the students see the relevance of the theoretical foundations. The coverage of soundness and completeness of axiom systems as well as that of denotational semantics has been reduced.

Textbooks for 655 and 755: The previous report noted: "Students have often complained about the textbooks for some of the courses in the group, especially for CSE 655 and 755. While many books are available, they tend to be either superficial surveys, or deeply theoretical discussions of mathematical models of languages."

Unfortunately, this situation has not improved. Although many new programming language books have been published, they are similar to the earlier books. Therefore we continue to rely heavily on class notes for both courses.

2.6 Continuing concerns

To address this problem, we are considering developing a set of class notes for some of the 459's that the various GTAs who teach the course can adopt. Such a set of notes already exists in the case of 459.11 (Unix); these notes were developed when the course was developed (by Wu-Chi Feng) several years ago when the course was first developed and have been used since then. There is also no problem in the case of 459.31 (Lisp) or 459.51 (Perl). Matt Curtin who has a special interest in Lisp has taught 459.31 for several years. Similarly, Bob Joseph who has a special interest in Perl developed 459.51 over the last three years and has taught it each time. If sections of these courses were to be taught by GTAs (or others), the materials developed by Matt and Bob can be used by them.

459.22 (C++) is one that poses a particularly serious problem. Since 321 is the prerequisite, students have already had a year of working in RESOLVE-C++. So this course should focus on the differences between standard C++ and RESOLVE and on how to apply the lessons learned in the 221-sequence in standard C++. Instead, as noted above, GTAs teaching this course have often spent considerable time discussing basic OO ideas as part of the course. Having a standard set of notes for this course would certainly help. 459.21 (C) and 459.23 (Java) could also benefit from having standard sets of notes that GTAs could teach from.

There is an unrelated concern with respect to 459.11. This course currently focuses on csh but this shell is not widely used any longer; indeed, it is considered by many UNIX experts to be very deficient. We intend to revise the course to use a different Bourne-compatible shell before the course is offered next time (probably in Winter 2006). This would include replacing csh in the first objective of the course with a more widely used shell.

CSE 655: This course is in satisfactory condition (except for the lack of a good textbook). One point, however, is the one identified in Section 2.2; i.e., the objective with respect to varible bindings/scope rule and that with respect to parameter passing methods should be reduced from mastery-level to familiarity-level; at the same time, instructors need to ensure that the class discussion ensures that the average student's level of achievement for these objectives does not fall below the familiarity-level.

CSE 755: As noted in 2.5, the introduction of the Lisp interpreter project enables students to see the practical importance of operational semantics. We plan to look for other additions that will similarly help highlight the importance of other essential topics in 755. For example, an extended discussion of compiler optimization based on formal semantics might be a useful addition; alternately, a discussion of how type inferencing works, based on proof rules analgouos to the ones in axiomatic semantics, might illustrate the practical uses of such formalisms.

CSE 756: As noted earlier, Gerald Baumgartner used to teach 756 until last year. Since Gerald left the department at the end of 2003-'04, the course was not offered this year since no suitable instructor was available. Although the topic is very much in Atanas Rountev's area of interest, Atanas is involved with 655 and 755, as well as with the advanced Software Engineering courses (757, 758); so it was not possible to fit it into his schedule. Neelam Soundarajan would also be able to teach the course but again given the number of sections of 655 and 755 that have to be taught, the course did not fit into his schedule either. It looks as if unless a new faculty member with interest in compilers joins the department or someone currently in the department develops a strong enough interest in teaching the course, we may not be able to offer it during some years. Bob Mathis may also be able to teach the course. In any case, this is clearly a concern given the importance of the topic.

The importance of continuing to offer this course on a regular basis was reiterated during the presentation/discussion of this report in the Curriculum Committee. It was also noted that there is considerable continuing student interest (from both undergraduate and graduate students) in the course.

3. Conclusions

People involved in preparing report: Neelam Soundarajan, Atanas Rountev, Bob Mathis.

Date of report: Feb. 2005.