The programming languages course is a key component of the computer science curriculum. In the course, students must master a large body of skills and knowledge. Students learn to discern between various paradigms and their concomitant abstractions, to judge the utility of various language designs, and to appreciate the impact that implementation decisions have on languages.

The programming language course presents a pedagogical challenge to the educator because we ask our students to master so much material. Over time, computer science educators have evolved somewhat standard approaches to structuring these topics and this standardization can be seen in similar organization of material in Programming Language textbooks. [DeJi95, Pra84, Seb93, Set90]. Although the traditional approach continues to be successful in many programs, we feel that many undergraduate students do not gain sufficient depth of insight into the principle concepts of languages. In this paper, we advocate a different teaching approach which retains the advantages of traditional methods but also provides students a more concentrated familiarity with important concepts. We call our approach, "teaching by counter-example," because we teach by comparing examples and counter-examples.

In this paper, we first present a brief overview of the traditional approach to programming languages and discuss some of its advantages and disadvantages. Next, we describe teaching programming languages by counter-example and discuss its strengths. With this background, we then list example applications of the method in the classroom and develop several examples in detail. Finally, we conclude with a discussion of the results that we have seen using this method and provide a brief summary of our experience.

There are a plethora of books using a similar approach, which we will call the traditional approach, to programming languages. The traditional approach provides some language theory and then categorizes programming language features as concepts (e.g. types, control structures, procedures, data abstraction, exception handling, etc.), paradigms (imperative, functional, logic, object oriented), or as a combination of these two. Well-known "real" programming languages are used as examples. Design issues are discussed, abstractions are explored, and programming is practiced.

There are obvious advantages to this approach. Students are exposed to a variety of concepts, abstractions, and paradigms and get first-hand experience with real languages. Different forms of control structures and data structures are illustrated naturally and students can master a number of abstraction techniques.

On the other hand, the complexities of real languages make mastering individual concepts difficult. In particular, modern languages contain a large number of design decisions and it's often hard to separate these issues. For example, students often confuse syntax or presentation with design issues. Consider teaching the concept of class using Smalltalk. Students often confuse the concept of class with Smalltalk's presentation of classes in a browser environment; they think that object-oriented classes means having a browser.

Deeper confusions arise with semantic issues. Differentiating which features of imperative languages are due to static scoping and which stem from strong typing, for example, is confusing to students. Semantic confusion is often exacerbated because programming language design and implementation courses emphasize language support for abstraction and how this abstraction influences programming style. Because language abstractions result from many design choices, students can easily confuse abstractions with designs. For example, objects (an abstraction) can be created in functional languages through first class procedures. However, students often miss the design tradeoff between first-class procedures versus a simpler procedure call mechanism because of the focus on the abstractions that can be created with the feature (i.e. objects).

Another issue often addressed in a programming languages course is understanding the costs, both in efficiency and complexity, involved in different language features. We can lecture on cost, but design decisions are often so intertwined that changing a single feature to demonstrate the corresponding change in cost is not possible. As a result, students often lack the means to fully appreciate costs of design decisions. Finally, without some experience in implementation details, students do not fully grasp the implementation impact of design decisions.

Teaching by counter-example can overcome many of these pedagogical difficulties. In this style of teaching, one first presents and discusses an example then follows with the presentation and discussion of a counter-example in which design choices are made differently. The technique is effective when the example and counter-example isolate and illustrate an important concept. In itself, this is not a novel idea, but the difficulty lies in applying this technique effectively in teaching a programming languages course.

In the programming languages design and implementation course, we advocate retaining the traditional subject matter and organization (i.e., different paradigms, abstractions, and concepts). However, students are also provided with simple demonstration languages which can be used to make teaching by counter-example effective in the programming languages course. In particular, all aspects of the simple languages can be kept constant while one particular feature is changed to explore the effect of that design on the expressive power and efficiency of the language. The use of simple demonstration languages enables teaching by counter-example to be effective not only by isolating the studied feature, but also because experimenting with an actual language reinforces concepts in an active way, as opposed to passive memorization.

To highlight the effect of a design decision and to demonstrate why modern languages have made similar decisions, features are presented by counter-example. A simple language is first presented with a design feature, students experiment with the language to discover the advantages and liabilities presented by the feature and, finally, the feature is replaced by a different feature and the process is repeated. Students can focus on one particular design feature at a time and, by exploring a less desirable feature first and a more popular feature second, learn why the second feature is preferred. To gain greater insight on the implementation costs, students can change the design in the language themselves, if the language is simple enough.

To permit effective experimentation with opposing design decisions, the languages used in this approach must be simple in implementation and syntax. We have used languages from the MuLE system (MUltiple Language Environment [BaKi 95]) in this approach. The MuLE system contains several simple languages from different paradigms that students can simultaneously program in. Since the languages are simple, students can also change the implementations to include new or different features [BaKi 94].

A number of traditional programming language design issues are amenable to demonstration by counter-example. Table 1 provides a sampling in the form of a two-column listing of features. The first column delineates the "counter-example" and the second column states the more common "example" implementation.

As an example of teaching by counter-example, consider the design choice between dynamic and static scoping strategies. Dynamic scoping is not widely used at present. Lisp, SNOBOL and APL are languages traditionally associated with dynamic scope whereas a number of popular programming languages use static scope (e.g. Pascal, C, Ada). When teaching by counter-example, the aim is to experiment with a language which uses dynamic scope, and then experiment with the same language implemented with static scope. This experimentation is difficult to conduct using the real languages like Lisp or Pascal, and certainly implementation issues are glossed over.

We teach the difference between static and dynamic scope using SiFL (SImple Functional Language [BaKi 95]), a simple functional language that is part of the MuLE system. SiFL normally uses dynamic scoping, but it is easily reconfigured to use static scoping. Thus it is straightforward to demonstrate the

effects of both scoping mechanisms to students. Students can experiment with SiFL programs which are interpreted by either dynamic or static scope implementations of SiFL. Furthermore, students can see how scope choice influenced implementation by examining the two SiFL implementations.

For example, consider the SiFL program which appears in the figure below:

(assign y 10)

(assign p1 (proc (x) (* x y)))

(assign p2 (proc (y) (p1 y)))

(p1 3)

(p2 3)

The first statement defines a global variable named y with value 10. The next statement defines the function p1 which uses a variable named y but does not define it. Next the function p2 is defined which contains a local definition of a variable named y, and which calls p1. The final two statements are function calls to p1 and p2 respectively, with the value 3 as the parameter.

The function call to p1 returns the value 30 regardless of whether dynamic or static scoping rules are used. In either case, the reference to y in the body of p1 refers to the global variable named y with value 10. In contrast, the value returned by p2 depends on the scoping mechanism used because the scope rules change the value returned by the nested call to p1. If static scoping is used, then the reference to a variable named y in p1 refers to the global variable named y with value 10, and p1 returns the value 30. If dynamic scoping is used, then the variable named y in p1 refers to the local variable name y with value 3 (defined in p2), and p1 returns the value 9.

Although this presentation alone is useful in the classroom, the presentation is reinforced because the students have access to SiFL. Using SiFL, student's can test their hypotheses about the differences between static and dynamic scope rules interactively and design experiments to test their understanding. Furthermore, the scoping rule is easily changed in the SiFL interpreter which facilitates comparison between the static and dynamic scoping implementations of SiFL. Understanding the implementation further reinforces the concepts.

The scope rule determines how the environment is searched when a variable reference appears in an expression. Under dynamic scoping rules, the environment is searched so that the most recent definition of a variable is found. Under static scope rules, the lexical level is used like a static chain pointer to control the search. In the SiFL's implementation, a single function implements the search code, and only a few lines of the search code are concerned with using the lexical-level/static chain pointer. Consequently, it is relatively easy to disable these lines to change SiFL from static scoping to dynamic scoping.

Thus it is possible to demonstrate to students the essential concept of scoping, the environment in which a procedure is evaluated, at both a high level and an implementation level. The implementation of SiFL is enough that the changes necessary to create different scoping can be easily identified and explained. There is an immediate connection between the concept, the resulting language feature, and the implementation. No "real-life" language implementation, such as Pascal, C, or Scheme, can be conveniently used to demonstrate all three of these areas.

A second language feature that can be easily studied using MuLE is associativity. Arithmetic expressions in every language associate either to the right or the left. Normally, left association is used, so for example the expression, 18 / 6 / 3 evaluates to the value 1. SPoc, the imperative language in the MuLE family, includes simple arithmetic expressions that are right associative by default. Thus the expression 18 / 6 / 3 evaluates to 9.

(parse-expression (lambda (expr)
       (if (list? expr)
         (cond ;;then;;
           ((null? (cdr expr)) (parse-expression (car expr)))
           ((equal? (cadr expr) '+)
              (+ (parse-expression (car expr))) 
                 (parse-expression (cddr expr))))
           ((equal? (cadr expr) '-)
              (- (parse-expression (car expr)))
                 (parse-expression (cddr expr))))
           ((equal? (cadr expr) '/)
              (/ (parse-expression (car expr)))
                 (parse-expression (cddr expr)))
           ((equal? (cadr expr) '*)
              (* (parse-expression (car expr)))
                 (parse-expression (cddr expr))))
           (else (error "Illegal Expression" expr)))
         (cond ;;else;; 
            ((number? expr) expr)
            (else (variant-case (parse-id expr)
               [ID (name)
                (execute (make-ID name)) ] ;; look up name in scopes
               [ERR (msg exp) (error "Illegal Expression" expr)])))   
       ))
     );;parse-expression

To change the associativity of SPoc, we have to merely change the order in which items are evaluated. To accomplish this, in every expression we have to recognize the last operator and last expression in the list, and we evaluate the first part of expression, and then apply the last operator with the result and last expression as operands. The modified Scheme code for the function appears below.

(parse-expression (lambda (expr)
       (if (list? expr)
         (cond ;;then;;
           ((null? (cdr expr)) (parse-expression (car expr)))
           ((equal? (last (delete-last expr)) '+)
              (+ (parse-expression (delete-last (delete-last expr)))
                 (parse-expression (last expr))))
           ((equal? (last (delete-last expr)) '-)
              (- (parse-expression (delete-last (delete-last expr)))
                 (parse-expression (last expr))))
           ((equal? (last (delete-last expr)) '/)
              (/ (parse-expression (delete-last (delete-last expr)))
                 (parse-expression (last expr))))
           ((equal? (last (delete-last expr)) '*)
              (* (parse-expression (delete-last (delete-last expr)))
                 (parse-expression (last expr))))
           (else (error "Illegal Expression" expr)))
         (cond ;;else;; 
            ((number? expr) expr)
            (else (variant-case (parse-id expr)
               [ID (name)
                 (execute (make-ID name)) ] ;; look up name in scopes
               [ERR (msg exp) (error "Illegal Expression" expr)])))
       ))
     );;parse-expression

Thus using SPoc's implementation, it is straightforward to demonstrate to students the effects of right associativity and to change this associativity. The change can be demonstrated in class or given as a class project.

Teaching by counter-example is currently in use at Ithaca College in the programming languages course, facilitated by simple demonstration languages provided in the MuLE system. MuLE is being used to present students with examples of several different language design features. This paper has presented examples including scoping, the use of environments, and associativity in arithmetic expressions.