Preface to the Instructor...............................................................................................................x 1 Introduction.................................................................................................................................1 Why Learn about Programming Computers?..........................................................................1 How You Will Learn to Program with This Book and Alice..................................................2 The Basics of Computer Programming...................................................................................3 Why is it called Alice?.............................................................................................................4 1 Alice............................................................................................................................................15 What is a Virtual World?.......................................................................................................15 How does Alice create an animation?...................................................................................16 An Alice virtual world...........................................................................................................16 3D Models of Objects............................................................................................................17 Tutorials.................................................................................................................................19 1 Exercises.............................................................................................................................19 Tips & Techniques 1....................................................................................................................22 Window size..........................................................................................................................22 Arranging objects...................................................................................................................22 Moving subparts of objects....................................................................................................23 A comparison of motions.......................................................................................................24 Vehicle...................................................................................................................................24 3D Text..................................................................................................................................26 2 Programming in Alice: Design and Implementation............................................................50 2-1 Scenarios and Storyboards (Design)...................................................................................51 Visual Storyboard..................................................................................................................52 Generic Template...................................................................................................................53 2-2 A First Program...................................................................................................................59 What is a Program?................................................................................................................59 2 Summary.................................................................................................................................71 Tips & Techniques 2....................................................................................................................72 Style.......................................................................................................................................72 Sound.....................................................................................................................................72 point at and onlyAffectYaw...................................................................................................74 Clipboards..............................................................................................................................76 As seen by..............................................................................................................................77 3 Methods and Parameters .......................................................................................................100 3-1 Methods: World-level........................................................................................................101 Methods...............................................................................................................................101 Why do you care?................................................................................................................101 Example...............................................................................................................................101 Creating our own method....................................................................................................102 Calling (Invoking) a Method...............................................................................................104 Comments............................................................................................................................106 Technical Note.....................................................................................................................107 3-1 Exercises........................................................................................................................108 3-2 Parameters.........................................................................................................................110 Example...............................................................................................................................110 Setting the Stage ..................................................................................................................110 Storyboard with a Parameter...............................................................................................111 Creating an Object Parameter..............................................................................................112 i Using an Object Parameter..................................................................................................113 Importance of Parameter Type............................................................................................115 Test with Arguments............................................................................................................116 Multiple Parameters.............................................................................................................117 Other types of parameters....................................................................................................121 Example...............................................................................................................................121 Number parameter...............................................................................................................122 Technical Note.....................................................................................................................122 3-2 Exercises........................................................................................................................124 3 Summary...............................................................................................................................126 3 Projects.................................................................................................................................127 Tips & Techniques 3..................................................................................................................131 Renaming an Object............................................................................................................131 Color Property as Identification...........................................................................................131 Printing your program code.................................................................................................133 Orient to...............................................................................................................................133 4 Character-Level Methods and Inheritance..........................................................................150 4-1 Creating New Characters...................................................................................................151 Example...............................................................................................................................151 A Character-Level Method..................................................................................................151 A Second Example..............................................................................................................154 Saving a New Character......................................................................................................156 Inheritance...........................................................................................................................157 Benefits: reuse and teamwork..............................................................................................157 Guidelines for Writing Character-level Methods................................................................157 Character-level Method With an Object Parameter.............................................................159 4-1 Exercises........................................................................................................................160 4 Summary...............................................................................................................................162 4 Projects.................................................................................................................................163 Tips & Techniques 4..................................................................................................................164 Properties.............................................................................................................................164 Setting Properties at Runtime..............................................................................................164 Built-in Questions (Functions)............................................................................................168 Collision...............................................................................................................................171 Expressions..........................................................................................................................171 The move to instruction.......................................................................................................173 5 Interactive Programs: Events and Event-Handling...........................................................200 5-1 Interactive Programming: Events and Event-Handlers.....................................................201 Input.....................................................................................................................................202 Design -- Storyboards..........................................................................................................202 Event-handler methods........................................................................................................203 Link Events to Event-handlers.............................................................................................203 Testing.................................................................................................................................205 Technical Notes...................................................................................................................205 Mouse-Control Example......................................................................................................207 Design -- Storyboards..........................................................................................................207 Event-handler methods........................................................................................................208 Link Events to Event-handlers.............................................................................................208 ii Technical Note.....................................................................................................................210 5-1 Exercises........................................................................................................................211 5-2 Passing Parameters to Event-Handlers..............................................................................214 Numeric parameter example................................................................................................214 Design -- storyboard............................................................................................................214 Three events, one event-handler..........................................................................................215 Parameter is used for both duration and distance................................................................215 Link events to event-handler...............................................................................................216 Pass a number parameter.....................................................................................................216 Testing.................................................................................................................................217 Object parameter example...................................................................................................217 Design -- Storyboard............................................................................................................218 Writing the event-handler....................................................................................................218 Link the event to the event-handler.....................................................................................220 Testing the program.............................................................................................................221 Technical Notes...................................................................................................................221 5-2 Exercises........................................................................................................................223 5 Summary...............................................................................................................................225 5 Projects.................................................................................................................................226 Tips & Techniques 5..................................................................................................................229 Let the mouse move objects................................................................................................229 Billboards.............................................................................................................................230 Special Effect: fog...............................................................................................................231 Rotating around an invisible object.....................................................................................233 6 Decisions and User-defined Questions................................................................................250 6-1 Decisions and Logical Questions......................................................................................251 Decisions..............................................................................................................................251 If/Else Example...................................................................................................................251 Logical Operators................................................................................................................254 Nesting If statements............................................................................................................257 Else......................................................................................................................................257 Relational operators.............................................................................................................257 6-1 Exercises........................................................................................................................259 6- 2 User-defined Questions I (Boolean).................................................................................262 Introduction to Questions....................................................................................................262 Abstraction...........................................................................................................................262 User-defined questions ........................................................................................................262 Creating a new Question......................................................................................................263 Calling the question.............................................................................................................265 A more complex Boolean question......................................................................................265 6-2 Exercises........................................................................................................................268 6-3 User-defined Questions II (Number).................................................................................271 Other types of questions ......................................................................................................271 User-defined number question.............................................................................................271 Testing.................................................................................................................................274 Using a question with a relational operator.........................................................................274 Abstracting a character-level method..................................................................................275 World-level question for generic use...................................................................................275 iii 6-3 Exercises........................................................................................................................277 6 Summary...............................................................................................................................279 6 Projects.................................................................................................................................280 Tips & Techniques 6..................................................................................................................284 If/Else and visibility as a condition.....................................................................................284 Camera: View from the back...............................................................................................285 Lighting up the rear view.....................................................................................................287 7 Repetition: A Counted Loop.................................................................................................300 7-1 Loops................................................................................................................................301 Introducing repetition..........................................................................................................301 The need for repetition.........................................................................................................301 Using a Loop........................................................................................................................303 Count....................................................................................................................................304 Loops and Do in order or Do together.................................................................................304 Technical note on looping...................................................................................................306 7-1 Exercises............................................................................................................................307 7 Summary..............................................................................................................................309 7 Projects.................................................................................................................................310 8 Repetition: Recursion............................................................................................................350 8-1 Repetition: Random motion and recursion........................................................................351 Introduction..........................................................................................................................351 Chase scene..........................................................................................................................351 Unknown number of repetitions..........................................................................................351 Random motion...................................................................................................................353 Recursion.............................................................................................................................356 8-1 Exercises........................................................................................................................359 8-2 Structural Recursion..........................................................................................................361 A closer look at generative recursion..................................................................................361 Structural recursion..............................................................................................................361 Towers of Hanoi puzzle.......................................................................................................361 Towers Method....................................................................................................................363 Conversion Question...........................................................................................................366 Exercise:..............................................................................................................................368 8 Summary...............................................................................................................................369 8 Projects.................................................................................................................................370 9 Repetition: While Statements................................................................................................400 9- 1 While ................................................................................................................................401 Revisiting the Chase............................................................................................................401 Using while..........................................................................................................................402 A game-like example...........................................................................................................403 How to determine when the race is over.............................................................................404 Random selection.................................................................................................................405 9-1 Exercises........................................................................................................................407 9-2 Infinite Repetition..............................................................................................................408 Mutually invoked methods..................................................................................................408 Infinite recursion..................................................................................................................410 Infinite Loop and while statements......................................................................................411 9-2 Exercises........................................................................................................................414 iv 9 Summary...............................................................................................................................417 9 Projects.................................................................................................................................418 10 Lists and List Processing......................................................................................................450 10-1 Lists.................................................................................................................................451 Creating a list.......................................................................................................................451 For all in order -- Iterating sequentially through a list.........................................................453 For all together -- Iterating simultaneously.........................................................................455 10-1 Exercises......................................................................................................................457 10-2 List Search.......................................................................................................................461 Simulation using a list search..............................................................................................461 First Subtask – Game in progress........................................................................................463 Second Subtask – Scoring ...................................................................................................464 10 Summary.............................................................................................................................466 10 Projects...............................................................................................................................467 11 Arrays....................................................................................................................................500 11- 1 Arrays: Creation and use................................................................................................501 Introduction to arrays...........................................................................................................501 Creating an array..................................................................................................................501 Accessing an element in an array........................................................................................501 Iterating though an array to find an element with a certain property..................................502 Searching through an array to find the tallest element ........................................................504 Using a location index variable a while statement in place of an iterator...........................507 11 Exercises.........................................................................................................................509 11- 2 Sorting arrays.................................................................................................................510 What is sorting?...................................................................................................................510 Insertion sort........................................................................................................................510 Walk through the array........................................................................................................511 Remove an element from the array......................................................................................511 Insert element in its correct location....................................................................................512 11-2 Exercises......................................................................................................................517 11 Summary.............................................................................................................................518 11 Projects...............................................................................................................................519 12 Revisiting Inheritance: Mutable variables.........................................................................550 12 -1 Inheritance......................................................................................................................551 Character-level variables.....................................................................................................551 Using a character-level method to track steering a car........................................................551 Figure 12-1-1. An initial scene............................................................................................551 Implementation....................................................................................................................552 12-1 Exercises......................................................................................................................559 12 Summary.............................................................................................................................562 13 Cool Worlds You Can Build................................................................................................600 13-1 Cool worlds.....................................................................................................................601 A flight simulator.................................................................................................................601 Initial world with billboard instructions..............................................................................601 Planning the simulation.......................................................................................................601 How do we know when the plane is flying through a ring?................................................602 When should the game end?................................................................................................603 What happens if the plane flies into the ground?................................................................605 v How do we start the game, continue to fly the plane, and keep track of the game?............607 How does the user steer the plane?......................................................................................608 13 Exercises.........................................................................................................................611 14 Transition to Real World Languages..................................................................................612 14-1 Transition to Java/C++: Syntax Switch...........................................................................613 Syntax..................................................................................................................................613 14-2: Objects and Classes........................................................................................................618 Objects.................................................................................................................................618 Classes.................................................................................................................................619 Creating (instantiating) objects............................................................................................620 “What you see is what you get”...........................................................................................621 Creating new classes............................................................................................................623 Encapsulation.......................................................................................................................624 Data Types and Structures...................................................................................................625 Methods and Functions (Questions)....................................................................................625 14-3: Program Constructs........................................................................................................322 Do in order and Do together ...............................................................................................322 Decision-making..................................................................................................................322 Repetition: loop (for)...........................................................................................................323 Repetition: while..................................................................................................................324 Repetition: recursion............................................................................................................324 14 Summary.............................................................................................................................629 Appendix A.................................................................................................................................650 Alice Tutorial 1-1....................................................................................................................650 How to Start Alice:..............................................................................................................650 World 1: Opening and Running Your First World..............................................................652 World 2: Interactive World..................................................................................................655 World 3: All About Character Objects................................................................................656 Optional: Using the Web Gallery.......................................................................................657 Moving Objects...................................................................................................................658 Arranging Multiple Character Objects (the quad view)......................................................659 Moving the Camera.............................................................................................................662 Saving a World ....................................................................................................................663 Alice Tutorial 1 - 2..................................................................................................................665 Using One-shot Instructions To Position Objects...............................................................665 Using One-Shot Instructions to Say Text............................................................................671 Using One-Shot Property Animations.................................................................................672 vi Preface to the Instructor This book takes a radically different approach to teaching introductory programming. There have been relatively few innovations in the teaching of programming in the last 30 years, despite the fact that introductory programming courses are often extremely frustrating to students. This text, with the associated Alice system, is intended to take a novel approach. We strongly recommend you see a live demonstration of the Alice system, or a videotape, before evaluating this text. The Alice system is free; the system and videos are available at www.alice.org . What is different about our approach? Our approach allows students to author on-screen movies and games, where the concept of an "object" is made tangible via on-screen characters that populate a three-dimensional micro world. Students create programs by dragging and dropping program elements (if/then statements, loops, variables, etc.) in a mouse-based editor that prohibits syntax errors. The Alice system is a powerful, modern programming environment that supports methods, functions, variables, parameters, recursion, arrays, and events. We use this strong visual environment to support an objects-first approach (described in the ACM and IEEE-CS Computing Curricula 2001 report) with an early introduction to events. In Alice, every object is an object that students can visibly see! We begin with objects in the very first chapter. In our opinion, there are four primary obstacles to introductory programming: 1) The fragile mechanics, particularly syntax, of program creation The Alice editing environment removes the frustration of syntax errors in program creation, and allows students to develop an intuition for syntax, because every time a program element is dragged into the editor, all valid "drop targets" are highlighted. 2) The inability to see the results of computation as the program runs Although textual debuggers and variable watchers are better than nothing, the Alice approach makes the state of the program inherently visible. In a sense, we offload the mental effort from the student's cognitive system to his or her perceptual system. It is much easier for a student to see that an object has moved backward instead of forward, as opposed to noticing that the "sum" variable has been decremented, rather than incremented. Today's students are immersed in a world where interactive, three-dimensional graphics are commonplace; we attempt to leverage that fact without pandering to them. 3) The lack of motivation for programming Many students take introductory programming courses only because they are required to do so. Nothing will ever be more motivating than a stellar teacher, but the right environment can go a long way. In pilot studies of classes using Alice, students do more optional exercises and are more likely to take a second class in programming than control groups of students using traditional tools. The most common request we received regarding earlier versions of Alice was the ability to share creations with peers; we have added the ability to run Alice programs in a WWW browser so students can post them on their web pages. Although we have seen increased motivation for all students, we have seen especially encouraging results with under-represented student groups, especially female students. x 4) The difficulty of understanding compound logic and learning design techniques to overcome it The Alice environment physically encourages the creation of small methods and functions. More importantly, the analogy of making a movie allows us to utilize the concept of a storyboard, which students know is an established movie-making process. Since most students cannot draw their storyboards, we encourage them to express their high level story concept in short prose snippets, which are progressively refined, essentially designing through pseudo-code. How to Use this Text Of course, as the instructor, you should use this text as you best see fit! Below are four ways we imagine the book being used, but you may discover additional ways of using this textbook: 1. As the only text in a semester-long, or short-course on programming. This would allow students to build relatively complex (say, 300-line) programs by the end of the semester or term. Such a course might be for non-majors who want to learn the concepts behind programming without a need for transitioning to a real-world language. Alternatively, this course can be used as a pre-CS1 course for students who would like to be, or are considering, a computer science major but who lack previous programming experience. In our NSF-supported study (NSF-#0126833), we found that students who jump right into a rigorous CS1 course with little or no previous programming have an extremely high attrition rate in CS1. The use of an Alice course as a pre-CS1 course has significantly reduced the attrition rate of these students in our CS1 courses. 2. As the first portion of a traditional "Introduction to Programming" course, such as CS1 Both Seymour Papert's Logo and Rich Pattis' Karel the Robot have been used this way, and these systems have inspired us greatly. Unlike these systems, Alice is powerful enough to support students for several semesters (for example, seniors majoring in Computer Science at Carnegie Mellon routinely write 3,000 line programs in Alice). However, many introductory programming courses must both teach concepts and also prepare students to write programs in traditional languages, such as Java. By learning Alice first, students are well acquainted with the fundamental concepts of programming, and can quickly learn the specific syntax rules of a particular "real" language as a transition. Our final chapter provides support for this transition, and the Alice environment can ease the transition by displaying programs with a Java-like syntax, as shown in the Figure Preface-1 below. 3. As the programming component of a "Computer Literacy" course. At many schools, computer literacy courses attempt to give a broad introduction to computers and/or "information technology" to non-majors. Many of these courses have removed their programming component and are little more than extended laboratories on "office productivity tools" such as spreadsheets and word processors. Alice has the potential to return a gentle programming component to these computer literacy courses. 4. In a high school “Introduction to Programming” course. A course in Alice has great potential for a high school environment, where a high-interest, highly-motivating environment is a teacher’s best friend. This course could be a stand-alone course as a preparation for college courses or as preparation for the College AP computing course. xi Figure Preface-1: Programs in Alice (top) can optionally be displayed with a Java-like syntax (bottom) Structure of the Book The text begins with an introduction motivating why students would want to write a computer program and addressing their fears about programming. We then have a brief first chapter on the basic concept of a three-dimensional virtual world. The text contains a traditional, paper-based tutorial as an appendix, and the Alice system also includes an interactive software-based tutorial that some students may prefer. xii The remaining chapters begin with overview and motivation of the chapter’s topic, have exercises at the end of each section, and end with a summary. For your convenience, the following is a (very) brief overview of the major concepts covered, chapter by chapter. Clearly, the major focus of the text material is an introduction to the fundamental concepts of programming. Chapter 1 3D worlds, 3D models (classes) and objects in the worlds. Chapter 2 Storyboard design and a first program. Chapter 3 World-level (global) methods and parameters. Chapter 4 Character-level methods and using inheritance to define new classes of objects. Chapter 5 Interactive programs: events and event-handling Chapter 6 Decisions and user-defined questions (functions) Chapter 7 Repetition: a Counted Loop (for) Chapter 8 Repetition: Recursion Chapter 9 Repetition: While statement Chapter 10 Lists and List Processing Chapter 11 Arrays Chapter 12 Revisiting inheritance: mutable variables Chapter 13 Cool Worlds You Can Build Chapter 14 Transition to Real World Languages (Java/C++) At the end of most chapters is a selection of larger, more free-form projects. We have found projects to be an enjoyable and important part of our Alice courses. The projects provided in this text are meant to inspire, not weigh down the student. In particular, we recommend “open- ended” projects. An open-ended project asks students to design their own animation beginning with their own storyline and using objects of their choosing. We do require that a project meet certain requirements. For example: “…an interactive world, containing two or more interactions with the mouse, at least three methods, and two characters you have created by writing character- level methods and saving out the characters.” Alice lends itself particularly well to student demonstrations of their worlds to the rest of the class on the project due date. Following most chapters is a "Tips and Techniques" section for students who may be interested in the fun features of Alice that we don’t cover as part of the fundamental concepts of programming presented in the major chapter material. Use of the Alice interface is integrated with examples for programming concepts, where needed. The Tips and Techniques sections enrich the flavor of the book with selected “how to” topics. Topic Selection and Sequence of Coverage Once again, as the instructor, the topic selection and sequence of coverage is totally in your hands! As a simple guideline, Chapters 1-7 were designed to be covered in sequence and Chapters 8 – 14 were designed to be selectively covered in whatever sequence the instructor prefers. But, of course, the nature of the Alice environment makes it easy to teach the chapters in a different order. xiii