Programming Languages and Techniques

1 Programming Languages and TechniquesLecture Notes for CIS 120 Steve ZdancewicStephanie WeirichUniversity of PennsylvaniaSeptember 1, 20212 CIS 120 Lecture NotesDraft of September 1, 2021 Contents1 Overview and Program and Prerequisites .. Philosophy .. the different parts of CIS 120 fit together .. History .. Design .. 152 Introductory in CIS 120 .. Types and Expressions .. Programming .. Declarations .. A complete example .. Notes .. 443 Lists and .. 504 Tuples and Nested .. patterns .. (underscore) patterns .. 66 CIS 120 Lecture NotesDraft of September 1, 20214 CONTENTS5 User-defined datatypes: enumerations .. that carry more information .. abbreviations .. types: lists .. 726 Binary Trees757 Binary Search Binary Search Trees .. 818 Generic Functions and generic datatypes .. use generics?.

2 889 First-class Application and Anonymous Functions .. transformation .. fold .. 9710 Modularity and A motivating example: finite sets .. Abstract types and modularity .. Another example: Finite Maps .. Type checking .. 11211 Partial Functions: option types11912 Unit and Sequencing The use of ; .. 12513 Records of Named Immutable Records .. 12714 Mutable State and Mutable Records .. Aliasing: The Blessing and Curse of Mutable State .. 13315 The Abstract Stack Parts of the ASM .. Values and References to the Heap .. Simplification in the ASM .. Reference Equality .. 150 CIS 120 Lecture NotesDraft of September 1, 20215 CONTENTS16 Linked Structures: Representing Queues .. The Queue Invariants .. Implementing the basic Queue operations .. Iteration and Tail Calls .. Loop-the-loop: Examples of Iteration .. Infinite Loops.

3 16617 Local Closures .. Objects .. The generic'a reftype .. Reference (==) vs. Structural Equality (=) .. 17418 Wrapping up OCaml: Designing a GUI Taking Stock .. The Paint Application .. OCaml s Graphics Library .. Design of the GUI Library .. Localizing Coordinates .. Simple Widgets & Layout .. The widget hierarchy and therunfunction .. The Event Loop .. GUI Events .. Handlers .. Widgets .. and Notifiers .. (at last!) .. a GUI App: Lightswitch .. 19919 Transition to Farewell to OCaml .. Three Programming paradigms .. Functional Programming in OCaml .. Object-oriented Programming in java .. Imperative Programming .. Types and Interfaces .. 21320 Connecting OCaml to Core java .. Static vs. Dynamic Methods .. 219 CIS 120 Lecture NotesDraft of September 1, 20216 CONTENTS21 Arrays .. 22322 The java Differences between OCaml and java Abstract Stack Machines.

4 23123 Subtyping, Extension and Interface Recap .. Subtyping .. Multiple Interfaces .. Interface Extension .. Inheritance .. Static Types vs. Dynamic Classes .. 24724 The java ASM and dynamic Refinements to the Abstract Stack Machine .. The revised ASM in action .. 25325 Generics, Collections, and Polymorphism and Generics .. Subtyping and Generics .. The java Collections Framework .. TheCollectioninterface and its implementations .. TheMapinterface and its implementations .. BSTs and theComparableinterface .. Iterating over Collections .. Modifying the collection during iteration .. 28226 Overriding and Method Overriding and the java ASM .. Overriding and Equality .. When to override equals .. How to override equals .. Equals and subtyping .. Restoring symmetry .. 29727 Ways to handle failure .. Exceptions in java .

5 Exceptions and the abstract stack machine .. Catching multiple exceptions .. 303 CIS 120 Lecture NotesDraft of September 1, Finally .. The Exception Class Hierarchy .. Checked exceptions .. Undeclared exceptions .. Good style for exceptions .. 30828 Working with (Binary) Files .. PrintStream .. Reading text .. Writing text .. Histogram demo .. 31729 Swing: GUI Programming in Drawing with Swing .. User Interaction .. Action Listeners .. Timer .. 33530 Swing: Layout and Layout .. An extended example .. 34031 Swing: Interaction and Paint Version A: Basic structure .. Version B: Drawing Modes .. Version C: Basic Mouse Interaction .. Version D: Drag and Drop .. Version E: Keyboard Interaction .. Interlude: Datatypes and enums vs. objects .. Version F: OO-based Refactoring .. 36632 java Design Exercise: Resizable Resizable Arrays.

6 36933 Encapsulation and Queues in ML .. Queues in java .. Implementing java Queues .. 384 CIS 120 Lecture NotesDraft of September 1, 20218 CONTENTSCIS 120 Lecture NotesDraft of September 1, 2021 Chapter 1 Overview and Program Introduction and PrerequisitesCIS 120 is an introductory computer science course taught at the University students should have some previous exposure to Programming andthe 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 ofentering students are familiar with java . However, students with experience inlanguages such as Python, C, C++, Matlab, or Scheme have taken this course anddone particular, the skills that we look for in entering CIS 120 students are familiar-ity with the basictoolsof Programming , including editing, compiling and runningcode, and familiarity with the basicconceptsof Programming Languages , such asvariables, assignment, conditionals, objects, methods, arrays, and various types Course PhilosophyThe core of CIS 120 isprogramming.

7 The skill of writing computer programs isfun, useful and rewarding in its own right. By the end of the semester, studentsshould 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 aplayable game, chosen and designed by the importantly, Programming is a conceptual foundation for the study ofcomputation. This course is a prerequisite for almost every other course in thecomputer science program at Penn, both those that themselves have major pro-CIS 120 Lecture NotesDraft of September 1, 202110 Overview and Program Designgramming components and those of a more theoretical nature. The science ofcomputing 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 groundedin any other skill, learning to program takes plenty of practice to tools involved Languages , compilers, IDEs, libraries, and frameworks arelarge and complex.

8 Furthermore, many of these tools are tuned for the demandsof rigorous software engineering, including extensibility, efficiency and general philosophy for introductory computer science at Penn is to developprogramming skills in stages. We start with basic skills of algorithmic thinking in our intro CIS 110 course, though students enter Penn already with this abilitythrough exposure to AP Computer Science classes in high school, through summercamps and courses on Programming , or independent study. At this stage, studentscan write short programs, but may have less fluency with putting them togetherto form larger applications. The first part of CIS 120 continues this process bydeveloping design and analysis skills in the context of larger and more challeng-ing problems. In particular, we teach a systematic process for program design, arigorous model for thinking about computation, and a rich vocabulary of compu-tational structures.

9 The last stage (the second part of CIS 120 and beyond) is totranslate those design skills to the context of industrial-strength tools and philosophy influences our choice of tools. To facilitate practice, we prefermature platforms that have demonstrated their utility and stability. For the firstpart of CIS 120, where the goal is to develop design and analysis skills, we usethe OCaml Programming language. In the second half of the semester, we switchto the java language. This dual language approach allows us to teach programdesign in a relatively simple environment, make comparisons between differentprogramming paradigms, and motivate sophisticated features such as objects is the most-widely used dialect of the ML family of Languages . Suchlanguages are not new the first version of ML, was designed by Robin Milner inthe 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 atINRIA, the French national laboratory for computing research.

10 Although OCamlhas its origins as a research language, it has also attracted significant attention inindustry. For example, Microsoft s F# language is strongly inspired by OCaml andother ML variants. Scala and Haskell, two other strongly typed functional pro-gramming Languages , also share many common traits with 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 earlyCIS 120 Lecture NotesDraft of September 1, 202111 Overview and Program Designnineties and first released in 1995. Like OCaml, java was released as free, opensource software and all of the core code is still available for free. Popular languagesrelated to java include C# and, to a lesser extent, C++.GoalsThere are four main, interdependent goals for CIS independence in programmingWhile we expect some familiaritywith Programming , we don t expect entering students to be full-blown program-mers.