Programming Languages and Techniques Lecture Notes

lecture notes computer programming languages and programming languages lecture notes | pdf free download
GeorgeThomson Profile Pic
GeorgeThomson,Greenland,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
Programming Languages and Techniques Lecture Notes for CIS 120 Steve Zdancewic Stephanie Weirich University of Pennsylvania August 30, 20162 CIS 120 Lecture Notes Draft of August 30, 2016Contents 1 Overview and Program Design 9 1.1 Introduction and Prerequisites . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Course Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 How the different parts of CIS 120 fit together . . . . . . . . . . . . . 13 1.4 Course History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Program Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Introductory OCaml 23 2.1 OCaml in CIS 120 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Primitive Types and Expressions . . . . . . . . . . . . . . . . . . . . . 23 2.3 Value-oriented programming . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 let declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 Locallet declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6 Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.8 Failwith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.9 Commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.10 A complete example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.11 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3 Lists and Recursion 45 3.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4 Tuples and Nested Patterns 59 4.1 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Nested patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3 Exhaustiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.4 Wildcard (underscore) patterns . . . . . . . . . . . . . . . . . . . . . . 63 4.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 CIS 120 Lecture Notes Draft of August 30, 20164 CONTENTS 5 User-defined Datatypes 65 5.1 Atomic datatypes: enumerations . . . . . . . . . . . . . . . . . . . . . 65 5.2 Datatypes that carry more information . . . . . . . . . . . . . . . . . . 68 5.3 Type abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4 Recursive types: lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6 Binary Trees 73 7 Binary Search Trees 77 7.1 Creating Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . 79 8 Generic Functions and Datatypes 83 8.1 User-defined generic datatypes . . . . . . . . . . . . . . . . . . . . . . 85 8.2 Why use generics? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 9 First-class Functions 89 9.1 Partial Application and Anonymous Functions . . . . . . . . . . . . . 90 9.2 List transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 9.3 List fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 10 Modularity and Abstraction 97 10.1 A motivating example: finite sets . . . . . . . . . . . . . . . . . . . . . 97 10.2 Abstract types and modularity . . . . . . . . . . . . . . . . . . . . . . 98 10.3 Another example: Finite Maps . . . . . . . . . . . . . . . . . . . . . . 104 11 Partial Functions: option types 109 12 Unit and Sequencing Commands 113 12.1 The use of ‘;’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 13 Records of Named Fields 117 13.1 Immutable Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 14 Mutable State and Aliasing 119 14.1 Mutable Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 14.2 Aliasing: The Blessing and Curse of Mutable State . . . . . . . . . . . 123 15 The Abstract Stack Machine 127 15.1 Parts of the ASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 15.2 Values and References to the Heap . . . . . . . . . . . . . . . . . . . . 129 15.3 Simplification in the ASM . . . . . . . . . . . . . . . . . . . . . . . . . 132 15.4 Reference Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 CIS 120 Lecture Notes Draft of August 30, 20165 CONTENTS 16 Linked Structures: Queues 143 16.1 Representing Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 16.2 The Queue Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 16.3 Implementing the basic Queue operations . . . . . . . . . . . . . . . . 148 16.4 Iteration and Tail Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 16.5 Loop-the-loop: Examples of Iteration . . . . . . . . . . . . . . . . . . . 153 16.6 Infinite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 17 Local State 159 17.1 Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 17.2 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 17.3 The generic'a ref type . . . . . . . . . . . . . . . . . . . . . . . . . . 163 17.4 Reference (==) vs. Structural Equality (=) . . . . . . . . . . . . . . . . . 164 18 Wrapping up OCaml: Designing a GUI Library 167 18.1 Taking Stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 18.2 The Paint Application . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 18.3 OCaml’s Graphics Library . . . . . . . . . . . . . . . . . . . . . . . . . 168 18.4 Design of the GUI Library . . . . . . . . . . . . . . . . . . . . . . . . . 170 18.5 Localizing Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 18.6 Simple Widgets & Layout . . . . . . . . . . . . . . . . . . . . . . . . . 174 18.7 The widget hierarchy and therun function . . . . . . . . . . . . . . . 178 18.8 The Event Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 18.9 GUI Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 18.10Event Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 18.11Stateful Widgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 18.12Listeners and Notifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 18.13Buttons (at last) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 18.14Building a GUI App: Lightswitch . . . . . . . . . . . . . . . . . . . . . 189 19 Transition to Java 193 19.1 Farewell to OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 19.2 Three programming paradigms . . . . . . . . . . . . . . . . . . . . . . 194 19.3 Functional Programming in OCaml . . . . . . . . . . . . . . . . . . . . 195 19.4 Object-oriented programming in Java . . . . . . . . . . . . . . . . . . 197 19.5 Imperative programming . . . . . . . . . . . . . . . . . . . . . . . . . 200 19.6 Types and Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 20 Connecting OCaml to Java 207 20.1 Core Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 20.2 Static vs. Dynamic Methods . . . . . . . . . . . . . . . . . . . . . . . . 209 CIS 120 Lecture Notes Draft of August 30, 20166 CONTENTS 21 Arrays 213 21.1 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 22 The Java ASM 221 22.1 Differences between OCaml and Java Abstract Stack Machines . . . . 221 23 Subtyping, Extension and Inheritance 227 23.1 Interface Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 23.2 Subtyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 23.3 Multiple Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 23.4 Interface Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 23.5 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 23.6 Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 23.7 Static Types vs. Dynamic Classes . . . . . . . . . . . . . . . . . . . . . 237 24 The Java ASM and dynamic methods 241 24.1 Refinements to the Abstract Stack Machine . . . . . . . . . . . . . . . 242 24.2 The revised ASM in action . . . . . . . . . . . . . . . . . . . . . . . . . 243 25 Generics, Collections, and Iteration 257 25.1 Polymorphism and Generics . . . . . . . . . . . . . . . . . . . . . . . . 258 25.2 Subtyping and Generics . . . . . . . . . . . . . . . . . . . . . . . . . . 259 25.3 The Java Collections Framework . . . . . . . . . . . . . . . . . . . . . 260 25.4 Iterating over Collections . . . . . . . . . . . . . . . . . . . . . . . . . 264 26 Overriding and Equality 267 26.1 Method Overriding and the Java ASM . . . . . . . . . . . . . . . . . . 267 26.2 Overriding and Equality . . . . . . . . . . . . . . . . . . . . . . . . . . 272 26.2.1 When to override equals . . . . . . . . . . . . . . . . . . . . . . 273 26.2.2 How to override equals . . . . . . . . . . . . . . . . . . . . . . 273 26.3 Equals and subtyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 26.3.1 Restoring symmetry . . . . . . . . . . . . . . . . . . . . . . . . 279 27 Exceptions 281 27.1 Ways to handle failure . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 27.2 Exceptions in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 27.3 Exceptions and the abstract stack machine . . . . . . . . . . . . . . . . 284 27.4 Catching multiple exceptions . . . . . . . . . . . . . . . . . . . . . . . 285 27.5 Finally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 27.6 The Exception Class Hierarchy . . . . . . . . . . . . . . . . . . . . . . 287 27.7 Checked exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 27.8 Undeclared exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 CIS 120 Lecture Notes Draft of August 30, 20167 CONTENTS 27.9 Good style for exceptions . . . . . . . . . . . . . . . . . . . . . . . . . 290 28 IO 293 28.1 Working with (Binary) Files . . . . . . . . . . . . . . . . . . . . . . . . 294 28.2 PrintStream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 28.3 Reading text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 28.4 Writing text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 28.5 Histogram demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 29 Swing: GUI programming in Java 307 29.1 Drawing with Swing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 29.2 User Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 29.3 Action Listeners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 29.4 Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 30 Swing: Layout and Drawing 319 30.1 Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 30.2 An extended example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 31 Swing: Interaction and Paint Demo 337 31.1 Version A: Basic structure . . . . . . . . . . . . . . . . . . . . . . . . . 337 31.2 Version B: Drawing Modes . . . . . . . . . . . . . . . . . . . . . . . . . 340 31.3 Version C: Basic Mouse Interaction . . . . . . . . . . . . . . . . . . . . 341 31.4 Version D: Drag and Drop . . . . . . . . . . . . . . . . . . . . . . . . . 343 31.5 Version E: Keyboard Interaction . . . . . . . . . . . . . . . . . . . . . . 344 31.6 Interlude: Datatypes and enums vs. objects . . . . . . . . . . . . . . . 346 31.7 Version F: OO-based Refactoring . . . . . . . . . . . . . . . . . . . . . 348 32 Java Design Exercise: Resizable Arrays 351 32.1 Resizable Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 33 Encapsulation and Queues 363 33.1 Queues in ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 33.2 Queues in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 33.3 Implementing Java Queues . . . . . . . . . . . . . . . . . . . . . . . . 366 CIS 120 Lecture Notes Draft of August 30, 20168 CONTENTS CIS 120 Lecture Notes Draft of August 30, 2016Chapter 1 Overview and Program Design 1.1 Introduction and Prerequisites CIS 120 is an introductory computer science course taught at the University of Pennsylvania. Entering students should have some previous exposure to programming and the ability to write small programs (10-100 lines) in some imperative or object- oriented language. Because of CIS 110 and AP Computer Science, the majority of entering students are familiar with Java. However, students with experience in languages such as Python, C, C++, Matlab, or Scheme have taken this course and done well. In particular, the skills that we look for in entering CIS 120 students are familiar- ity with the basic tools of programming, including editing, compiling and running code, and familiarity with the basic concepts of programming languages, such as variables, assignment, conditionals, objects, methods, arrays, and various types of loops. 1.2 Course Philosophy The core of CIS 120 is programming. The skill of writing computer programs is fun, useful and rewarding in its own right. By the end of the semester, students should be able to design and implement—from scratch—sophisticated applica- tions involving graphical user interfaces, nontrivial data structures, mutable state, and complex control. In fact, the final homework assignment for the course is a playable game, chosen and designed by the student. More importantly, programming is a conceptual foundation for the study of computation. This course is a prerequisite for almost every other course in the computer science program at Penn, both those that themselves have major pro- CIS 120 Lecture Notes Draft of August 30, 201610 Overview and Program Design gramming components and those of a more theoretical nature. The science of computing can be thought of as a modern day version of logic and critical think- ing. However, this is a more concrete, more potent form of logic: logic grounded in computation. Like any other skill, learning to program takes plenty of practice to master. The tools involved—languages, compilers, IDEs, libraries, and frameworks—are large and complex. Furthermore, many of these tools are tuned for the demands of rigorous software engineering, including extensibility, efficiency and security. The general philosophy for introductory computer science at Penn is to develop programming skills in stages. We start with basic skills of “algorithmic thinking” in our intro CIS 110 course, though students enter Penn already with this ability through exposure to AP Computer Science classes in high school, through summer camps and courses on programming, or independent study. At this stage, students can write short programs, but may have less fluency with putting them together to form larger applications. The first part of CIS 120 continues this process by developing design and analysis skills in the context of larger and more challeng- ing problems. In particular, we teach a systematic process for program design, a rigorous model for thinking about computation, and a rich vocabulary of compu- tational structures. The last stage (the second part of CIS 120 and beyond) is to translate those design skills to the context of industrial-strength tools and design processes. This philosophy influences our choice of tools. To facilitate practice, we prefer mature platforms that have demonstrated their utility and stability. For the first part of CIS 120, where the goal is to develop design and analysis skills, we use the OCaml programming language. In the second half of the semester, we switch to the Java language. This dual language approach allows us to teach program design in a relatively simple environment, make comparisons between different programming paradigms, and motivate sophisticated features such as objects and classes. OCaml is the most-widely used dialect of the ML family of languages. Such languages are not new—the first version of ML, was designed by Robin Milner in the 1970s; the first version of OCaml was released in 1996. The OCaml implemen- tation is a free, open source project developed and maintained by researchers at INRIA, the French national laboratory for computing research. Although OCaml has its origins as a research language, it has also attracted significant attention in industry. For example, Microsoft’s F language is strongly inspired by OCaml and other ML variants. Scala and Haskell, two other strongly typed functional pro- gramming languages, also share many common traits with OCaml. Java is currently one of the most popularly used languages in the software in- dustry and representative of software object-oriented development. It was orig- inally developed by James Gosling and others at Sun Microsystems in the early CIS 120 Lecture Notes Draft of August 30, 201611 Overview and Program Design nineties and first released in 1995. Like OCaml, Java was released as free, open source software and all of the core code is still available for free. Popular languages related to Java include C and, to a lesser extent, C++. Goals There are four main, interdependent goals for CIS 120. Increased independence in programming While we expect some familiarity with programming, we don’t expect entering students to be full-blown program- mers. The first goal of 120 is to extend their programming skills, going from the ability to write program that are 10s of lines long to programs that are 1000s of lines long. Furthermore, as the semester progresses, the assignments become less con- strained, starting from the application of simple recipes, to independent problem decomposition. Fluency in program design The ability to write longer programs is founded on the process of program design. We teach necessary skills, such as test-driven devel- opment, interface specification, modular decomposition, and multiple program- ming idioms that extend individual problem solving skills to system development. Firm grasp of fundamental principles CIS 120 is not just an introductory pro- gramming course; it is primarily an introductory computer science course. It cov- ers fundamental principles of computing, such as recursion, lists and trees, in- terfaces, semantic models, mutable data structures, references, invariants, objects, and types. Fluency in core Java We aim to provide CIS 120 students with sufficient core skills in a popular programming language to enable further development in a va- riety of contexts, including: advanced CIS core courses and electives, summer in- ternships, start-up companies, contributions to open-source projects and individ- ual exploration. The Java development environment, including the availability of libraries, tools, communities, and job opportunities, satisfies this requirement. CIS 120 includes enough details about the core Java languages and common libraries for this purpose, though is not an exhaustive overview to Java or object-oriented software engineering. There are many details about the Java language that CIS 120 does not cover; the goal is to provide enough information for future self study. CIS 120 Lecture Notes Draft of August 30, 201612 Overview and Program Design Why OCaml? The first half of CIS 120 is taught in the context of the OCaml programming lan- guage. In the second half of the semester, we switch to Java for lectures and as- signments. If the goal is fluency in core Java, why use OCaml at all? We use OCaml in CIS 120 for several reasons. “The OCaml part of the class was very essential to getting It’s not Java. By far, the majority of students entering CIS 120 know only the Java fundamental ideas of programming language, and yet different programming languages foster different comp sci across. Without the second programming paradigms. Knowing only one language, such as Java, leads to a language it is easy to myopic view of programming, being unable to separate “that is how it is done” fall into routine and from “that is how it is done in Java”. By switching languages, we provide perspec- syntax lock where you tive about language-independent concepts, introducing other ways of decompos- don’t really understand ing and expressing computation that are not as well supported by Java. the bigger picture.” —CIS 120 Student Furthermore, not all students have this background in Java, nor do they have the same degree of experience. We start with OCaml to level the playing field and give students with alternative backgrounds a chance to develop sophistication in programming and review the syntax of Java on their own. (For those that need more assistance with the basics, we offer CIS 110.) Finally, learning a new programming language to competence in six weeks builds confidence. A student’s first language is difficult, because it involves learn- ing the concepts of programming at the same time. The second comes much easier, once the basic concepts are in place, and the second is understood more deeply be- cause the first provides a point of reference. “OCaml made me Rich, orthogonal vocabulary. better understand We specifically choose OCaml as an alternative language because of several features of Java that properties of the language itself. The OCaml language provides native features seemed innate to for many of the topics that we would like to study: including lists and tree-like programming, which data structures, interfaces, and first-class computation. These features can be can were merely abstractions and be studied in isolation as there are few intricate interactions with the rest of the assumptions that Java language. made. It made me a better Java programmer.” —CIS Functional programming. OCaml is a functional programming language, which 120 Student encourages the use of “persistent” (immutable) data structures. In contrast, every data structure in Java is mutable by default. Although CIS 120 is not a functional programming course, we find that the study of persistent data structures is a useful introduction to programming. In particular, persistence leads to a simpler, more CIS 120 Lecture Notes Draft of August 30, 201613 Overview and Program Design mathematical programming model. Programs can be thought of in terms of “trans- formations” of data instead of “modifications,” leading to simpler, more explicit interfaces. 1.3 How the different parts of CIS 120 fit together Homework assignments provide the core learning experience for CIS 120. Pro- gramming is a skill, one that is developed through practice. The homework assign- ments themselves include both “etudes”, which cover basic concepts directly and “applications” which develop those concepts in the context of a larger purpose. The homework assignments take time. Lectures Lectures serve many roles: they introduce, motivate and contextualize con- cepts, they demonstrate code development, they personalize learning, and moderate the speed of information acquisition. To augment your learning, we make lecture slides, demonstration code and lecture notes available on the course website. Given the availability of these re- sources, why come to class at all? • To see code development in action. Many lectures include live demonstra- tions of code design, and only the resulting code is posted on the website. That means the thought process of code development is lost: your instruc- tors will show some typical wrong turns, discuss various design trade-offs and demonstrate debugging strategies. Things will not always go accord- ing to plan, and observing what to do when this happens is also a valuable lesson. • To interact with the new material as it is presented, by asking questions. Sometimes asking a question right at the beginning can save a lot of later confusion. Also to hear the questions that your classmates have about the new material. Sometimes it is difficult to realize that you don’t fully under- stand something until someone else raises a subtle point. • To regulate the timing of information flow for difficult concepts. Sure, you can read the lecture notes in less than fifty minutes. However, sometimes slowing down, working through examples, and thinking deeply is required to internalize a topic. You may have more patience for this during lecture than while reading lecture notes on your own. • For completeness. We cannot promise to include everything in the lectures in the lecture notes. Instructors are only human, with limited time to prepare lecture notes, particularly at the end of the semester. CIS 120 Lecture Notes Draft of August 30, 201614 Overview and Program Design Labs The labs (or “recitations”) provide a small-group setting for coding practice and individual attention from the course staff. The lab grade comes primarily from lab participation. The reason is that the lab is there to get you to write code in a low-stress environment. In this environ- ment, we use pair programming, teaming you up with your classmates to find the solutions to the lab problems together. The purpose of the teams is not to divide the work—in fact, we expect that in many cases it will take longer to complete the lab work using a team than by doing it yourself The benefit of team work lies in discussing the entire exercise with your partner—often you will find that you and your partner have different ideas about how to solve the problem and find different aspects difficult. Furthermore, labs are another avenue for coding practice, adding to the quan- tity of code that you write during the semester. The folllowing parable illustrates the value of this: The ceramics teacher announced he was dividing his class into two groups. All those on the left side of the studio would be graded solely on the quantity of work they produced, all those on the right graded solely on its quality. His procedure was simple: on the final day of class he would weigh the work of the quantity group: 50 pounds of pots rated an A, 40 pounds a B, and so on. Those being graded on quality, however, needed to produce only one pot — albeit a perfect one — to get an A. Well, come grading time and a curious fact emerged: the works of highest quality were all produced by the group being graded for quan- tity It seems that while the quantity group was busily churning out piles of work — and learning from their mistakes — the quality group had sat theorizing about perfection, and in the end had little more to show for their efforts than grandiose theories and a pile of dead clay. David Bayles and Ted Orland, from “Art and Fear” 1. Exams The exams provide the fundamental assessment of course concepts, in- cluding both knowledge and application. Some students have difficulty see- ing how pencil-and-paper problems relate to writing computer programs. In- deed, when completing homework assignments, powerful tools such as IDEs, type checkers, compilers, top-levels, and online documentation are available. None of these may be used in exams. Rather, the purpose of exams is to assess both your understanding of these tools and, more importantly, the way you think about pro- gramming problems. CIS 120 Lecture Notes Draft of August 30, 201615 Overview and Program Design 1.4 Course History The CIS 120 course material, including slides, lectures, exams, examples, home- works and labs were all developed by faculty members at the University of Penn- sylvania, including Steve Zdancewic, Benjamin Pierce, Stephanie Weirich, Fer- nando Pereira, and Mitch Marcus. From Fall 2002 to Fall 2010, the course was taught primarily using the Java programming language, with excursions into Python. In Fall 2010, the course instructors radically revised the material in an ex- perimental section, introducing the OCaml language as a precursor to Java. Since Spring 2011, the dual-language course has been used for all CIS 120 students. In some ways, the use of OCaml as an introductory language can be seen as CIS 120 “returning to its roots.” In the 1990s the course was taught only in functional lan- guages: a mix of OCaml and Scheme. The last major revision of the course replaced these wholesale with Java. Joel Spolsky lamented this switch in a 2005 blog post en- titled “The Perils of JavaSchools”, available athttp://www.joelonsoftware. com/articles/ThePerilsofJavaSchools.html. 1.5 Program Design Program design is the process of translating informal specifications (“word prob- lems”) into running code. Learning how to design programs involves decompos- 1 ing problems into a set of simpler steps. The program design recipe comprises four steps: 1. Understand the problem. What are the relevant concepts in the informal description? How do the concepts relate to each other? 2. Formalize the interface. How should the program interact with its environ- ment? What types of input does it require? Why type of output should it produce? What additional information does it need? What properties about its input may it assume? What is true about the result? 3. Write test cases. How does the program behave on typical inputs? On un- usual inputs? On erroneous ones? 4. Implement the required behavior. Only after the first three steps have been addressed is it time to write code. Often, the implementation will require decomposing the problem into simpler ones and applying the design recipe again. 1 The material in this section is adapted from the excellent introductory textbook, How to Design Programs 3. CIS 120 Lecture Notes Draft of August 30, 201616 Overview and Program Design We will demonstrate this process by considering the following design problem: Imagine an owner of a movie theater who wants to know how much he should charge for tickets. The more he charges, the fewer people can afford tickets. After some experiments, the owner has determined a precise relationship between the price of a ticket and average attendance. At a price of 5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime (.10) increases attendance by 15. However, the increased atten- dance also comes at an increased cost: Each attendee costs an- other four cents (0.04), on top of the fixed per-performance cost of 180. The owner would like to be able to calculate, for any given ticket price, exactly how much profit he will make. We will develop a solution to this problem by following the design recipe in the context of the OCaml programming language. In the process, we’ll introduce OCaml by example. In the next chapter, we give a more systematic overview of its syntax and semantics. Step 1: Understand the problem. In the scenario above, there are five relevant concepts: the ticket price, (number of) attendees, revenue, cost and profit. Among these entities, we can define several relationships. From basic economics we know the basic relationships between profit, cost and revenue. In other words, we have pro t = revenue cost and revenue = price attendees Also, the scenario tells us how to compute the cost of a performance cost = 180+ attendees0:04 but does not directly specify how the ticket price determines the number of atten- dees. However, because revenue and cost (and profit, indirectly) depend on the number of attendees, they are also determined by the ticket price. Our goal is to determine the precise relationship between ticket price and profit. In programming terms, we would like to define a function that, given the ticket price, calculates the expected profit. CIS 120 Lecture Notes Draft of August 30, 201617 Overview and Program Design Step 2: Formalize the Interface. Most of the relevant concepts—cost, ticket price, revenue and profit—are dollar amounts. That raises a design choice about how to represent money. Like most programming languages, OCaml can calculate with integer and floating point values, and both are attractive for this problem, as we need to represent fractional dollars. However, the binary representation of floating point values makes it a poor choice for money, since some numeric values—such as 0.1—cannot be represented exactly, leading to rounding errors. (This “feature” is not unique to OCaml—try calculating 0.1 + 0.1 + 0.1 in your favorite program- ming language.) So let’s represent money in cents and use integer arithmetic for calculations. Our goal is to define a function that computes the profit given the ticket price, so let us begin by writing down a skeleton for this function—let’s call it profit— and noting that it takes a single input, called price. Note that the first line of this definition uses type annotations to enforce that the input and and output of the 2 function are both integers. let profit (price:int) : int = ... Step 3: Write test cases. The next step is to write test cases. Writing test cases before writing any of the interesting code—the fundamental rule of test-driven pro- gram development—has several benefits. First, it ensures that you understand the problem—if you cannot determine the answer for one specific case, you will find it difficult to solve the more general problem. Thinking about tests also influences the code that you will write later. In particular, thinking about the behavior of the program on a range of inputs will help ensure that the implementation does the right thing for each of them. Finally having test cases around is a way of “fu- tureproofing” your code. It allows you to make changes to the code later and automatically check that they have not broken the existing functionality. In the situation at hand, the informal specification suggests a couple of specific test cases: when the ticket price is either 5.00 or 4.90 (and the number of atten- dees is accordingly either 120 or 135). We can use OCaml itself to help compute what the expected values of these test cases should be. The OCaml let-expression gives a name to values that we compute, and we can use these values to compute others with thelet-in expression form. 2 OCaml will let you omit these type annotations, but including them is mandatory for CIS120. Using type annotations is good documentation; they also improve the error messages you get from the compiler. When you get a type error message, the first thing you should do is check that your type annotations correct. CIS 120 Lecture Notes Draft of August 30, 201618 Overview and Program Design let profit_500 : int = let price = 500 in let attendees = 120 in let revenue = price attendees in let cost = 18000 + 4 attendees in revenue - cost let profit_490 : int = let price = 490 in let attendees = 135 in let revenue = price attendees in let cost = 18000 + 4 attendees in revenue - cost Using these, we can write the test cases themselves: let test () : bool = (profit 500) = profit_500 ;; run_test "profit at 5.00" test let test () : bool = (profit 490) = profit_490 ;; run_test "profit at 4.90" test The predefined function test (provided by the Assert module) takes no input 3 and returns the boolean value true only when the test succeeds. We then invoke the commandrun_test to execute each test case and give it a name, which is used to report failures in the printed output; if the test succeeds, nothing is printed. After invoking the first test case, we can define the test function to check the profit function’s behavior at a different price point. Step 4: Implement the behavior. The last step is to complete the implementation. First, the profit that will be earned for a given ticket price is the revenue minus the number of attendees. Since both revenue and attendees vary with to ticket price, we can define these as functions too. let revenue (price:int) : int = ... let cost (price:int) : int = ... 3 Note that single=, compares two values for equality in OCaml. CIS 120 Lecture Notes Draft of August 30, 201619 Overview and Program Design let profit (price:int) : int = (revenue price) - (cost price) Next, we can fill these in, in terms of another function attendees that we will write in a minute. let attendees (price:int) : int = ... let revenue (price:int) : int = price (attendees price) let cost (price:int) : int = 18000 + 4 (attendees price) For attendees, we can apply the design recipe again. We have the same con- cepts as before, and the interface for attendees is determined by the code above. Furthermore, we can define the test cases for attendees from the problem state- ment. let test () : bool = (attendees 500) = 120 ;; run_test "atts. at 5.00" test let test () : bool = (attendees 490) = 135 ;; run_test "atts. at 4.90" test To finish implementing attendees, we make the assumption that there is a lin- ear relationship between the ticket price and the number of attendees. We can graph this relationship by drawing a line given the two points specified by the test cases in the problem statement. CIS 120 Lecture Notes Draft of August 30, 201620 Overview and Program Design A"endees vs. Ticket Price 160 140 -15 120 0.10 100 80 60 40 20 0 4.75 4.80 4.85 4.90 4.95 5.00 5.05 5.10 5.15 CIS120 We can determine what the function should be with a little high-school algebra. The equation for a line y =mx+b says that the number of attendees y, is equal to the slope of the line m, times the ticket pricey, plus some constant valueb. Furthermore, we can determine the slope of a line given two points: difference in attendance 15 m = = difference in price 10 Once we know the slope, we can determine the constantb by solving the equation for the line for b and plugging in the numbers from either test case. Therefore b = 120(15=10)500 = 870. Putting these values together gives us a mathematical formula specifying at- tendees in terms of the ticket price. attendees = (15=10) price +870 Translating that math into OCaml nearly completes the program design. let attendees (price : int) : int = (-15 / 10) price + 870 CIS 120 Lecture Notes Draft of August 30, 2016