CS102: Introduction to Computer Science II

3a. Demonstrate an understanding of the history of Generic Programming and the motivation behind the Generic Programming development

1. What role did Ada play in the history of Generic Programming?
2. What is the purpose of Generic Programming?

There are over 250 programming languages. One reason for the proliferation of programming languages is the quest to make programming easier and more powerful. One approach to achieve these goals is software reuse, which is the use of an existing program, instead of developing a new program, to solve a new problem. Ada popularized generic programming with its generics features, which influenced C++. What are some of the generic features of Ada? To review them, reread the first section, Parametric Polymorphism, and the first paragraph of Generic Parameters, in "Ada Programming". Understand the meaning of polymorphism.

1. What are some examples of modules in programming?
2. What are some examples of module composition?
3. How does Generic Programming promote reuse?

Modular programming is programming that builds programs by composing modules (existing programs that solve a part of a problem). The modules could come from several sources. Naturally, the programmer could analyze a problem, identify the sub-problems, and develop a module for each sub-problem; or, some of the modules might have been developed in the past to solve similar problems and may be (re)usable as modules by the programmer. An Ada generic is a high level abstraction, in which the parameters need not be specified until run-time. Read the example in the beginning of "Ada Programming". A goal of modular design is abstraction – watch 14:00-15:00 in "The Digital Abstraction". Two key characteristics of abstraction are "understanding behavior", but "without knowing implementation". This is one type of reuse.

"Composing Programs" mentions 3 features current programming languages have for composing complex ideas from simple ideas (what are they?), and discusses 'composition', from simple expressions to higher order functions (see the index outline on the left side of the page). In generic programming, a module (e.g. function) is first class (which means that is can be declared, defined, used as a parameter, returned as a value or, simply stated, used like any other variable). This extends the kinds of compositions that apply to functions and enables higher order abstractions, which promotes reuse.

3b. Demonstrate an understanding of the detailed components used in Generic Programming

1. The concepts of reuse, modularity, composition, hierarchy, and abstraction are illustrated by the structure of a computer. We generally find it easier to understand new concepts if we have an analogy with something we are familiar with.
2. How is abstraction related to modularity? How is abstraction used in Generic Programming?

We have reviewed modularity and composition in 3a. above. "Basics of Information" and "The Digital Abstraction" continue the discussion and extend it to address hierarchy and abstraction, as well, but from a hardware perspective. Try to extend the analogy to generics.

3c. Demonstrate an understanding of the basic components used in the Standard Template Library with C++

1. Overview the history of STL.
2. Name several types of hierarchies. What type of hierarchy is used for data? What type of hierarchy is used for algorithms?
3. Why are we interested in complexity of algorithms? How is abstraction used in complexity?
4. Name some containers and iterators in the STL.

Again, history gives us insight. "STL and Its Design Principles" presents the motivations for the STL. For examples, watch from 2:00-7:00. Four fundamental principles (what are they?), involving data and algorithms and hierarchies used for each, are discussed at 9:00. Here is a little index to slides for the entire video, which may help you navigate:

(Note that in the video modules are called components.)

Can you write and read simple examples of iterators? To review them, reread Chapter 23 of the Rook's Guide to C++. Can you give a brief overview of the STL? This article on the Standard Template Library is a concise but thorough overview.

In "STL and Its Design Principles", Stepanov mentioned that if there are many users of a generic program, then we had better validate it and measure its performance. "Complexity" points out that performance is a decision choice made during design. It presents log, linear, quadratic, and exponential complexity for classes of algorithms. 'Classes of algorithms' is an abstraction for all the algorithms that have similar performance.

'Functor' is a new term to us for GP (Generic Programming). Define Functor. What does a functor provide that a function does not? To review, study "Functors".

Unit 3 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included.

• Abstraction
• Ada
• Ada generics
• Composition
• Container
• Functor
• Generality
• Hierarchy
• Iterator
• Modularity
• Overloading
• Part-whole hierarchy
• STL
• Template