On the Cognitive Prerequisites of Learning Computer Programming

To view this page ensure that Adobe Flash Player version 9.0.124 or greater is installed.

Please login or register to make a comment!

On the Cognitive Prerequisites of Learning Computer Programming Roy D. Pea D. Midian Kurland Technical Report No.

18 ON THE COGNITIVE PREREQUISITES OF LEARNING COMPUTER PROGRAMMING* Roy D. Pea and D. Midian Kurland Introduction Training in computer literacy of some form, much of which will consist of training in computer programming, is likely to involve $3 billion of the $14 billion to be spent on personal computers by 1986 (Harmon, 1983).

Who will do the training? "hardware and software manu- facturers, management consultants, -retailers, independent computer instruction centers, corporations' in-house training programs, public and private schools and universities, and a variety of consultants1' (ibid., - p. 2 7 ) .

To date, very little is known about what one needs to know in order to learn to program, and the ways in which edu- cators might provide optimal learning conditions. The ultimate suc- cess of these vast training programs in programming--especially toward the goal of providing a basic computer programming compe- tency for all individuals--will depend to a great degree on an ade- quate understanding of the developmental psychology of programming skills, a field currently in its infancy. In the absence of such a theory, training will continue, guided--or to express it more ... more. less.

aptly, misguided--by the tacit Volk theories1' of programming development that until now have served as the underpinnings of programming instruction. Our paper begins to explore the complex agenda of issues, promise, and problems that building a developmental science of programming entails. Microcomputer Use in Schools The National Center for Education Statistics has recently released figures revealing that the use of micros in schools tripled from Fall 1980 to Spring 1983. The outcome of that leap. is that there are now 120,000 microcomputers for students in 35% of the country's public *The work upon which this publication is based was performed pursuant to Contract No. 400-83-0016 of the National Institute of Education. It does not, however, necessarily reflect the views of that agency. schools: 22% of these are in elementary schools, and 64% are located in secondary schools (Reed, 1983). A staggering 4.7 million precol- lege students worked at computer terminals during the 1981-1982 school year. Yet the National Education Association reported in March 1983 that just 11.2% of the country's public school teachers use computers in teaching. Problems with Questions of the "Cognitive Demands" of Programming A common set of questions voiced by those wishing to learn computer programming (but perhaps as commonly voiced by those offering programming training or courses) is: "What do I need to know in order to learn to prsgram?"Do I need to be good at mathematics? If I'm not, can I still learn to program?" "Do I need to be a highly developed logical thinker?" h the academic community, these ques- tions get expressed in the jargon of the social sciences: "What are the cognitive demands of programming?" or What mental abilities are cognitive prerequisites for learning to program?" or "Are there individual differences in programming skill development?" The com- mon dear for the individual who would Like to learn programming, and the concern of educators and employers (frequently motivated by cost effectiveness), is that there are some persons who are either not capable of being trained to program, or who are not "developmentally ready" that they need to learn or know more fundamentally rele- vant things before embarking on the task of learning to program. While these questions are subject to empirical analyses, we have found in reviewing the literature that the uses of such empirical analyses are often quite pernicious. If persons do not get a high enough score. on a "programming aptitude measure," they may be denied educational or employment opportunities. One study is quite explicit on the uses to which they believe such findings should be put--£or student advising and placement: The rapid increase in the need for personnel in these areas is attracting many individuals needing education, and - the number who will not succeed with this education will in- crease.. . .The increase in the number of such students is already being observed by many schools, resulting in the use of relatively scarce faculty resources to educate indi- viduals who will not successfully complete a technical course, while keeping out students who might succeed if permitted to enroll. (Wileman. Konvalina & Stephens, 1981, p. 226; our emphases) Fowler & Glorfeld (1981, p. 96) note that "the need t~ identify a potentially successful student is very important for reasons such as early counseling into an appropriate career path and formation of honors section^.^ In another study, Newstead (1975, p. 89) goes so far as to say that 'lone can conclude that programming ability (as measured in this study) may be much more innate than 'business training course spiels' would have one believe. Anyone cannot be a programmer [sic] . The logic of these approaches is not hard to follow. Let the rich get richer, while the poor recede into the nontechnical background of society. Never mind that it may be possible to instruct "those who will not succeed" in another way (and the pedagogical alternatives for learning to program are many and diverse [Lemos, 1975, 1980; Papert, 19801 ). Instead, assume that "this education" that they will not succeed with is immutable and adequate for anyone wishing to learn to program only they had the right stuff.n While some may have felt that this attitude had some justification when programming was an optional activity (something one could, but need not do), it is a problem of great seriousness today, since at least a basic under- standing of (modicum of competence in) how to write and understand computer programs is at the core of the needs for any member of a computer literate society (e. g . , Sheil, 1981a, 198 1b) . We cannot continue to dismiss those who have difficulties in learning to program as flies in the ointment of a well-oiled training machine. Instead, we are obliged to try out or, if necessary, develop new means for in- struction that allow all an equal opportunity to learn about and par- ticipate in the computational powers of a technological society, one which has an impact on and will continue to have an even greater impact on the educational, work, and family lives of members of our society. Overview In preparing the available this report, we found that when we critically considered literature that aims to address the relationships between nprogramming aptitude" and interests of individuals and their pro- gramming performance, the static nature of these studies was appar- ent in that the research questions asked have not varied substantially in nearly 30 years. ~ v k r since the 1950s. when the Programmer Aptitude Battery was developed by IBM to help select programmer trainees, consistently modest correlations (at their best from 0.5 to 0.7, hence accounting for only a quarter to a half of the variance) , and in many cases much lower, have existed between an individual's score on such a measure and hs or her assessed programming skill. In addition, ever since the 1950s. global measures of programming skill, such as grade in a programming training course or supervisor ranhng, have served as skdl assessments. Studies in 1983 still take for granted the utility of this multivariate approach, and offer no greater insights--certainly none that are instructionally relevant--into what makes a successful programmer than they did three decades ago. The same is true of interest measures and programming skill assess- ments. These studies always ask whether particular ap titude vari- ables have an effect on programming success, rather than the more fundamental psychological question of how they might have such effects, in terms of component skills or knowledge representations mediating specific programming activities. Given these insufficiencies, we must often step back during the course of our review and survey the presuppositions that have guided this Line of research, asking whether they are warranted, culling from the research Literature the few studies that suggest new and promising directions, and asking many more questions than we are able to answer on the basis of available evidence. While the dearth of answers to these questions is at times disconcerting, we feel that a groundclearing is in order. The available foundations are unstable, so we must uproot them in a search for new metaphors, new ways of seeing what programming is that people may learn to do it, and what it is about people that they are able to do programming. Since the available programming aptitude literature is built upon such ques- tionable foundations, a point-by-point review of thls literature in terms of subject populations, specific measures, and correlations obtained is not useful, although we will provide brief surveys and extensive citations of the hundred or so studies of this kmd. On the other hand, we are heartened by some recent studies on the cognitive psychology of programming that begin to unravel the complex of mental activities essential to programming. In our intellectual travels through the development of programming skills, we become more and more compelled by the importance of one dominant motif: the role of purpose and goals in programming. What one needs to know in order to program will depend in fundamental ways on one's programming goals. This point has repercussions all the way from how one does programming instruction, to what kinds of programming instruction are selected on the basis of the educational values and goals that define one's programming pedagogy. To take a simple example: documenting a program and the mental skills that are required may be unnecessary for a single-use program for oness home computer sys- tem. But it is a central concern if one requires a program for the public domain that is understandable and rnaintainabae by others. So we will ask not, "What are the cognitive demands of computer pro- gramming?" as if programming were a unified homogeneous activity (which we challenge below ) , but rather, I' What are the cognitive demands of doing computer programming activity X with goal Y?" With these provisos in mind, we will now begin to develop the ground raising which we have promised. Background Issues What Is Computer Programming? We will define the core sense of ncomputer programming" as that set of activities involved in developing a reusable product consisting of a series of written instructions that make a computer accomplish some task. It is interesting to note that, although the sense of "computer programming" has not varied in nearly four decades, the set of activities involved in doing programming has undergone major quali- tative transformations. In the early days of programming, for ex- ample, the programmer had to know the details of the computer hardware in order to write a program that worked; today this is no longer true. An important consequence of this evolution of the set of activities that constitutes programming is that the "cognitive demands" made by computer programming needs specification at the level of programming subtasks, or component activities. Therefore, we must ask about the variety of cognitive activities involved in computer pro- gramming as it is carried out today, and especially as it is carried out by children as they attempt to master this complex skill. From our own work as well as our reading in the literature on pro- gramming, we find that at least four distinct levels of computer pro- gramming ability can be identified. While these levels represent pure types and are not characteristic of a single individual, they do cap- ture some of the compleldty of what it means to learn to program. While we will take up the issue of levels of programming skill devel- opment in more detail below, it is important in attempting to build an adequate characterization of the programming process to bear in mind the range of abilities included under the heading of "being able to program. Level I: Program user. Before learning how to program, one typically learns to execute already written programs such as games, demonstrations, or CAI lessons. What is learned at this level is not' trivial (i. e., what the return key or the reset key does, how to boot a disk, how to use a screen menu), but gives no information to the novice on how a computer program works or even that there is a program controlling what happens on the screen. Many adult com- puter users never advance past this level. One does not need to know about programming to be a word processor operator, make airline reservations, process payroll checks, design a budget, or do any of a growing number of computer-based activities. However, Level I users remain at the mercy of the program they are using and are powerless to effect changes in it. While it can be argued that as programs get better, there will be less need for the average person to make programming changes, we would argue that without some familiarity with programming, the user is less likely to appreciate fully the power and potential of this technology. In addition, without some appreciation of programming, the user is not likely to take full advantage of optional parameters built into sophisticated application programs which themselves constitute a high-level form of program- ming. Level LI: Code generator. At this level the student knows the syntax and semantics of the more common commands in a language. The user can read someone else's program and know what each line accomplishes. The student can locate bugs that prevent commands from being executed (e. g. , syntax errors), can load and save pro- gram files to and from an external storage device, and can write simple programs that he or she has seen previously. When program- ming, the student does very little preplanning and does not both& to document his or her program. There is no effort to optimize the coding, use error traps, or make the program user-friendly and crash resistant. A program at this level might simply consist of printing the student's name over and over on the screen or drawing the same shape repeatedly in different colors. The student operates at the level of the individual command and does not use subroutines or procedures created as part of other programs. Level III: Program generator. At this level, the student has mastered the basic commands and is thinking in terms of higher level units. Sequences of commands that accomplish program goals are known (e.g., locate and verify a keyboard input, sort a list of names or numbers, read data into a program from a separate file). The student can now read a program and say what the goal of the pro- gram is, what functions different parts of the program serve, and how the different parts are linked together. The student can locate bugs that prevent the program from functioning properly (e. g. , a sort routine that fails to correctly place the last item in a list) or bugs which cause the program to crash as a result of unanticipated conditions or inputs (e. g. , a division by zero error when the pro- gram is instructed to find the mean of a null list). The student can load, save, and merge files, and can do simple calls to and from files inside the main program. The student may be writing fairly lengthy programs for personal use, but the programs tend not to be user- friendly. While the student sees the need for documentation, he or she does not plan programs around the need for careful documentation so that the program may be maintained by others. Within this gener- a1 level, one can identify many sublevels of computer programming slull . Level IV: Software developer. At t h s level, the student is ready to write programs that are both complex and are intended to be used by others. The student now knows several languages and has a full understanding of all their features and how the languages inter- act with the host computer (e. g., how memory is allocated, how graphic buffers can be protected from being overwritten, how periph- eral devices can be controlled by the program). When given pro- grams to read, the student can scan the code and simulate mentally what the program is doing, see how the goals are achieved and, most likely, how the programs could be better written or adapted for other purposes. The student now writes programs with sophisticated error traps and built-in tests to aid in the debugging process and to ensure that the program will be reliable, provable, and maintainable. In addition to writing code that accomplishes the program's objective, the student can optimize coding to increase speed and minimize the amount of memory required for running. To decrease the time needed to write programs, the student will draw heavily on software libraries and programming utilities. Finally, the student will often design the program before generating the code,' will document the program fully, and will write the program in a structured fashion thus malung it easy for others to read and/or modify. Major issues in software engineering at this level of expertise are discussed by Thayer, Pyster and Wood (1981). There are many methodological problems with assessing computer programming abilities across these four major levels and their many sublevels. While psychological studies of expert and novice pro- grammers have revealed some efficient measures that exploit the differences in programming-specific problem-solving strategies--spe- cifically , debugging (Jeffries, 1982) and program memory organization (diPersio et al., 1980)--determining whether or not a person can program at some specified level of expertise remains a difficult task. Demands of Learning to Program: The Problem of Differentiation The question of the cognitive demands of computer programming is an enormously complex one, because nprogrammingn is not a unitary shll. Like reading, it is comprised of a large number of abilities that interrelate with the organization of the learner's knowledge base. memory and processing capacities, repertoire of comprehension strate- gies, and general problem-solving abilities. In addition, a program- mer may be highly developed in some aspects of programming but not in others. For example, it is not uncommon to find programmers who can write highly efficient and elegant code, but not code that can be understood or maintained by other programmers. Typically, in re- search on the psychology of computer programming, "learning to program" has been equated with learning the syntax and the defini- tion of commands in a programming language, just as reading is often equated with skill in decoding. However, once past the initial level of skill acquisition, what we mean by "readingn is actually reading comprehension, which entails an elaborate body of world knowledge, comprehension monitoring, inferencing , hypothesis generation, and other cognitive and metacognitive strategies that take years to devel- op fully. This lesson has been etched in high relief through the intensive efforts necessary to develop artificial intelligence systems that "understandn text (e. g . , Anderson & Bower, 1973; Schank, 1982; Schank & Abelson, 1977). Skilled reading also requires wide experience with different types of texts (e. g . , narrative, essays, plays, poetry, debate, biography) and with different goals of the reading activity (such as reading for meaning, content, style, pleas- ure). Skilled computer programming is similarly complex and context- dependent, which makes the problem of assessing the cognitive de- mands of nlearning to program'' all the more acute. This issue of "cognitive demandsn and the corresponding problem of selecting components of the question that are researchable has been a general one. The idea that some development may serve as a neces- sary prerequisite for some other development is familiar from the Literature of moral reasoning (e. g . , Tomlinson-Keasey & Keasey , 1974), language development (e.gi, Sinclair, 1969; Slobin, 1973, 1982) and, more generally, from the "invariantn developmental stage sequence arguments offered by Piaget as central to his structuralist developmental theory. This approach to the cognitive demands of programming has recently begun to be applied to programming as well (Favaro, 1983). In each case, the empirical testing of the prereq- uisite character of some specific cognitive achievement for some other cognitive achievement has depended on a refinement of the general question into specific questions that are empirically researchable. Rather than asking, as in the early days of the cognitive prerequisite controversy in developmental psy cholinguistics--I1 Daes language learn- ing require prior concept development for the ideas expressed in language?"--current language development research recognizes that such a question must be asked for specific language constructions or subparts of language, and that the answer will depend on the lin- guistic forms chosen (e. g. , Johnston, 1982). W e will urge a similar differentiation for questions about the "cognitive demands" or "pre- requisitesbf learning to program--cognitive prerequisites in order to do what specifically in programming? What Programming Is as a Cognitive Activity In this section, we first outline recent findings about the cognitive psychology of expert programming, then provide a brief account of available theories of the cognitive subtasks involved in programming, describe existing accounts of what "learning to program" involves, and then critique the popular accounts of what learning to program requires. One can begin to analyze what programming skill is as a cognitive activity by engaging in detailed analyses of what expert programmers do, and what kinds and organizations of knowledge they appear to - have stored in memory in order to do it. This research strategy has revealed significant general features of expert problem-solving com- petence and performance for a wide variety of other subject domains such as algebra (Lewis, 1981), chess (Chase & Simon, 1973), geome- try (Anderson, Greeno, Kline & Neves, 1981), physics (Chi, Felto- vich & Glaser, 1981; Larkin, McDermott, Simon & Simon, 1980), physical reasoning (deKleer & Brown, 1981), and writing (Bereiter & Scardamalia, 1982), and it has begun to provide some insights into the components of programming skill. Recent studies of programmers suggest that high-level computer programming skill is characterized by a giant assembly of highly specific, low-level knowledge fragments (Brooks, 1977; Atwood & Ramsey , 1978). For example, the design of functional "programmer's apprenticesn such as Barstow's (1979) Knowledge Based Program Construction, and Rich and Shrobe's "Lisp programmer's apprentice" (Rich & Schrobe, 1978; Shrobe, Waters & Sussman, 1979; Waters, 1982), and the MEN0 Programming Tutor (Soloway, Rubin, Woolf, Bonar & Johnson, 1982) has involved compiling a "plan library" of the basic computer programming schemas , I' or recurrent functional chunks of programming code that programmers are alleged to use. There is some behavioral evidence from studies of programmers that supports these rational and introspective analyses of "chunks" of computer programming knowledge. Eisenstadt, Laubsch and Kahney (1981) have developed a Logo-like software programming language called SOLO and used it to introduce computer-naive college psychol- ogy students to computer programming. In an analysis of novice student programs, they found that most programs were constructed from a small set of basic program schemas comparable to the "plan library" of Schrobe et al. (1979). Jeffries (1982), in a comparison of the debugging strategies of novice PASCAL programmers and graduate computer science students, found that "experts saw whole blocks of code as 'instantiations' of well-known problems" such as " calculating change. I' Soloway and his colleagues (Bonar, 1982; Ehrlich & Soloway, 1983; Johnson, Draper & Soloway, 1983; Soloway & Ehrlich, 1982; Soloway, Ehrlich, Bonar & Greenspan, 1982; also see Kahney & Eisenstadt, 1982) have begun to construct a "plan-based theory of computer programming"which also postdates the use of recurrent plans as nchunk~" in program composition. Such plans were identified in preliminary analyses of programs written by PASCAL novices (e.g., the "counter variable plan"). What is missing here, for our pur- poses, is a ~enetic account of the construction of such plan schemas from programming instruction, experience, and prior knowledge that is brought to the task of learning to program. (For the interested reader, a general account of schema theory in cognitive science is provided by Rumelhart, 1980. ) A second, related characteristic of computer programming skill is the large number of component rules that underlie an expert's generation of programming problem solutions. In an analysis of one program- mer's work on 23 different problems, Brooks (1977) demonstrated in a detailed model that about 104 rules were necessary to generate the protocol behavior. Further, Green and Barstow (1978) note that over a hundred rules for mechanically generating simple sorting and searching algorithms- (e. g . , Quicksort) are familiar to most pro- grammers. A third characteristic of computer programming skill is the ability to construct detailed mental models of how the computer is functioning when a computer program is running (Sheil, 1980, 1981a). The expert programmer can build dynamic mental representations, or "runnable mental modelsn (Collins & Gentner , 1981) in which they can simulate computer operations in response to specific problem inputs. Brooks (1977) has characterized these mental operations as "symbolic executions."The complexities of such dynamic mental models are revealed when skilled programmers gather evidence for program bugs and simulate the program's actions by hand (Jeffries, 1982). We should note that not a l l aspects of program understanding are medi- ated by hand simulation; often experts engage in a prior global search for program organizational structure, a strategy akin to that of expert text readers (Brown, 1983b; Brown & Smiley, 1978: Spiro, Bruce & Brewer, 1980) and guided by adequate program documenta- tion. Expert programmers not only have more information about the com- puter programming domain, but remember larger, meaningful chunks of information that enable them to perceive programs and remember them mote effectively than novice programmers. The classic Chase and Simon (1973) finding of short-term memory advantages for chess experts over novices for meaningful chessboard configurations but not for random configurations has been repeatedly replicated for the domain of computer programming (Curtis, Sheppard, Milliman, Borst & Love 1979; McKeithen, Reitman, Rueter & Hirtle, 1981; Norcio & erst, in press; Sheppard, Curtis, Milliman & Love, 1979; Shneider- man, 1977). For example, McKeithen et al. (1981) used the Reitman- Rueter (1980) technique for inferring individual subjects' chunking of key ALGOL programming concepts in memory from recall orders to discover the specifics of memory organization that may facilitate this performance difference. They found extensive differences in the mnemonic strategies used by beginning, intermediate, and expert ALGOL programmers to memorize ALGOL keyword stimuli. Notably, experts clustered the keyword commands according to meaning in ALGOL (e.g., those functioning in loop statements), whereas novices clustered according to a variety of surface ordinary language associ- ations (such as orthographic similarity and word length), with inter- mediates somewhere in between. In a related finding, Adelson ( 198 1) presented computer programming novices and experts with a recall task in which stimuli were lines of programming code which could be organized either procedurally (into programs) or syntactically (in terms of order relationships between different control phrases of the computer language). She found that experts recalled program lines "in the order in which they would have been evaluated in a running program, " whereas novices clustered by syntactic category. Recall clusters for experts were thus functionally or "deeply" based, where- as those of novices were based on "surface" features of programming code. This distinction is reminiscent of the striking developmental shift from surface structure-based, or "syntagmatic , " word associa- tions to functional category-based, or "paradigmatic," word associa- tions during childhood (e. g . , Nelson, 1977). DiPersio, Isbister and Shneiderman (1980) have carried this line of research further by demonstrating that performance on a program memorizationlreconstruction task provides a useful measure and pre- dictor of computer programming ability. Scores on program logic reconstruction tasks and performance on college class exams in pro- gramming were significantly correlated. The authors attributed this result to the extent of subjects' "semantic" knowledge base for the programming language, that is, the functional nature of the ?ode (which we have more appropriately designated as the "pragmatics" of programming slull). Such results are encouraging insofar as they suggest the utility of such a memory task as one measure for assess- ing computer programming skill development. More research will be required, however, for the performance levels of individuals rather than groups to be inferred from their performance on program memory tasks. It is also a widely replicated finding that expert programmers debug their programs in different ways than do novices (Atwood & Ramsey, 1978; Gould, 1975; Gould & Drongowski, 1974; Youngs, 1974). Perhaps most important is the recent finding (Jeffries, 1982) that program debugging involves comprehension processes analogous to those for reading ordinary language prose. Experts read programs for flow of control (execution), rather than Line by line (as text). In terms of identifying the specific cognitive activities involved in programming (the necessity of which we argued for earlier in our discussion of the cognitive demands of computer programming) , we need a more comprehensive account of the task of programming. Recent research in cognitive science provides such accounts, and to these theories we now turn. Theories of Cognitive Subtasks Involved in Programming It is the consensus of cognitive psychologists who have developed global theories of expert programming skill that computer programming is highly complex since "it involves subtasks that draw on different knowledge domains and a variety of cognitive processes"(Pennington, 1982, p. 11). Just as in the case of theories of problem solving in general, cognitive theories that have been developed of expert pro-. gramming articulate a set of distinctive cognitive activities that take place in the development of a computer program. These activities are required for programming whether the programmer is novice or ex- pert, since they constit& phases of the problem-solving process in any general theory of problem solving (e.g,, Heller & Greeno, 1979; Newell & Simon, 1972; Polya, 1957). They may be summarized as: (1) understanding the programming problem; (2) designing or plan- ning a programming solution; ( 3 ) writing a programming code that implements the plan; and (4) comprehension of the written program and program debugging. We will discuss each of these cognitive subtasks in turn, with an eye toward thinking about what kinds of cognitive demands each of them may make on the programmer. 1. Understanding the Problem It is generally agreed that in attempting to solve a problem, the problem solver first sets up some form of "problem representation" in working memory which is used to model a problem in terms of what the problem solver knows about the problem domain, and how that knowledge is organized for him or her. En recent studies (e. g., Chi, et al., 1981). substantive qualitative as well as quantitative differ- ences in the problem-solving processes of experts and novices for a given content domain, such as physics, have indicated that experts set up radically different kinds of problem representations in their early attempts to understand the problem presented. In the case of applying physics to mechanical problems, experts engage in extensive qualitative problem analysis, or processes of problem understanding, before attempting to solve the problem, for example, through setting up a physical representation of the problem situation that was initially depicted in words (Larkin, 1977; McDermott & Larlun, 1978; Simon & Simon, 1978). Physics experts focus on deep structural features of the problems in problem categorization studies, sorting together problems which would be solved according to specific laws of physics, unlike novices, who focus more on the surface structural features of the problem structure, such as the objects involved, physics terms used, and the physical configurations described in the problem (Chi et al., 1981). What the expert appears to know is what kinds of features of the problem should constitute part of their problem repre- sentation; this knowledge is apparently faalitated by large-scale memory units in terms of problem types that are identified in terms of deep structure, and by the experts' facility in rapidly building qualitative physical symbolic representations of the verbal problem statements. h a discussion of a computer-implemented model of physics problem solving, Larkin (1980) notes that the importance of a deep problem representation during the problem understanding process is that using these qualitative features, the [computer simulated] solver tentatively selects a method for solving the problem. It then applies key physics principles from that method to generate qualitative information about the problem--for example, information about the direction an object moves [our Design and Planning cognitive subtask]. When suffi- cient information has been generated to solve the abstracted qualitative problem, the model solver elaborates this quali- tative solution by generating corresponding quantitative equations [our Program Coding phase] to actually solve the original problem. (p. 116) What is illuminating for thinking about computer programming from problem-solving studies such as these, and in other domains such as geometry (Greeno, 1976) or writing (Flower & Hayes, 1979), is that the problem solver must have substantial domain-specific knowledge in order to set up a functional problem representation. With respect to understanding the problem, Larkin's physics solver "had to know what hnd of features to abstract in constructing a useful simplified problem. I' For developing a problem-solving plan, it "had to know what hnd of operations he could apply to solve abstracted problems," and for working out the details of the problem solution had to know "ow these [operations] were to be elaborated when he returned to construct a full solution." Although solution debugging is not men- tioned in this work, presumably he would also have to know how to check whether or not the solution was a correct one. So domain-specific knowledge is very important for understanding the programming problem. Lf a child was asked to write a graphics program to draw a Colonial home, she would have to know about what Colonial houses looked like, their key identificational features, and so on. Similarly, to develop a game system, a chld would need to know the many domain-specific facts about computer games, such as vari- able skill level, score feedback, and so on. Since domain-specific knowledge is such a fundamental aspect of understanding programming problems, serious thought needs to be given to what we know about conceptual development for any given content domain for whlch we are interested in posing programming problems for children. Certain domains, such as statistics, or simulations for complex domains such as ecosystems and economics, may well be out of reach for school- aged children, and constitute inappropriate programming project content. But the great variety of domains that children are learning about in school should provide ample opportunity for rich pro- gramming projects. A s for the specifics of the categories or types of prablems that the expert programmer is able to identify in attempting to understand the, programming problem, many different alternatives have been suggested, and little empirical evidence, even for adult experts, exists to dis- tinguish them. We summarize those described by Pennington (1982) below : a) Function-oriented. Problems would be seen as indicating different program goals or functions, in terms of what is to be ac- complished, such as "update inventory accounts and produce reports" (e. g . , Balzer , Goldman & Wile, 1977; Shneiderman & Mayer , 1979). b ) Data1 process-oriented. Problems would be seen as specifying external object classes (e. g . , updates, inventory accounts, status report), and operations (e. g. , transform initial objects to final ones) applied to specific classes of objects (e. g . , Brooks, 1982 ; Miller gr Goldstein, 1977) . el Sequence-oriented. Problems would be decomposed into their basic components or procedures, and problem representations would contain sequencing information (e. g . , Atwood, Jeffries & Polson, 1980) . As noted above, the problem representation that serves as the out- come of the problem-understanding process is one of the most funda- mental components of the problem-solving process, for programming as well as other content domains. For this reason, we expect the cogni- tive subtask of understanding the programming problem to be devel- opmentally central. The cognitive demands of understanding pro- gramming problems, as we have seen, will depend at least upon the extent and organization of a child's domain-specific knowledge that is required for the problem at hand. But since the adult expert pro- grammer literature is currently equivocal on what forms such problem representations may take, we cannot make precise the cognitive demands of program understanding. For at least some of the pro- posed alternatives, datalprocess-oriented and sequence-oriented , the child would need to be able to learn about the different classes of data objects and operations, in the first case, and about the concepts of "procedures"and "sequentiality, in the second case. Such basic requirements have direct implications for defining a "core" of minimal programming knowledge, to be discussed below. 2. Designing I Planning the Program After achieving an initial problem representation, the programmer needs to map out a plan or design for the program to be written later in programming code. Atwood et al. (1980) provide an informative description of the requirements of this process : Software design is the process of translating a set of task requirements (functional specifications) into a structured description [design or plan] of a computer system that will perform the task. There are three major aspects to this description. The original speafications are decomposed into a collection of modules, or substructures, each of which satisfies part of the original problem description. This is often referred to as modular decomposition of the problem. In addition, these modules must communicate in some way. The designer must specify the interrelationships and inter- actions among. the modules [also called procedures in smaller systems 1 . This includes the control structure, which indicates which modules are used by a given superordinate module to do its work and the conditions under which they are used. Lastly, a design may include a definition of the data structures required. (p. 3 ) According to Brooks (1982), one-third of the entire time a program team spends on a software project (including coding and testing) should be spent planning the task. Atwood et al. (1980). in a de- tailed analysis of the think-aloud protocols of two expert software designers as they solved a software design problem, found that they - had available many general design strategies, such as problem decom- position, subgoal generation, retrieval of known solutions, generation and principled or npolicy driven"se1ection of alternative solutions, and evaluative analysis and debugging of solution components. It is of some importance in this respect that a major move in programming instruction is to treat programming as an instance of a general prob- lem of structured design (Floyd, 1979) , rather than as machine and programming language-specific (Sheil, 1980 1. At this point, someone is bound to object that, in the programming process, it is possible to bypass this step of program development altogether, that one may first make an initial reading of the problem, then sit down at the keyboard and begin composing code to achieve the task. And it has been said (Galanter, 1983) that one frequently finds much preplanning in PASCAL (a compiler language) program- ming, but often little or no planning prior to code writing for pro- gramming languages such as BASIC (an interpreted language). What are we to make of this observation in terms of defining design and planning as a distinct cognitive subtask in programming? Is it op- tional? The answer to this question certainly has consequences for the cognitive demands of pr~gramming, if one subtask ingredient to it. involves whatever cognitive prerequisites there are for planning and design. In response to this objection, we allow for the distinction commonly made, and applicable to the cognitive activity of programming, be- tween planning-in-action versus preplanning (Rogoff & Gardner , 1983). In terms of this distinction, what the BASIC programmer is engaged in as he or she sits down and begins to generate program- ming code without a prior plan is planning-in-action, making decisions as he or she goes about the structure sf the program, which evolves as the materials of the program are created. Schon and Bamberger (1982) have described the outcomes of such a planning-in-action creative process in art, music, and other related domains as a conse- quence of an iterative series of '~conversations" the creator has with his or her partial creations. Bereiter (1979) has characterized a similar process in composing language text as "epistemic," in whch one comes to see and understand new things as one channels one's ideas into a written product. But to return to programming, d- though planning-in-action is certainly possible, even sufficient, to produce a program, we expect such a planned-in-action program often to have great costs for the beginning programmer. The reason has to do with the anticipated difficulties of comprehension and debugging when one goes back to try to understand what one has done in writing a program not built with foresight. Of course, for expert programmers the sheer automaticity of many programming projects, since they are able to recall successful plans for similar programs or software systems, will mean that little preplanning will be required for the program code generation. In other words, the adult program- mer often can integrate the subtasks of planning and code writing. But the child as novice programmer is not at that level of under- standing, and does not have a store of programming schemas available for ready reference during planning-in-action while creating a pro- gram. So we WLU continue in our discussion of the cognitive demands of programming to include the cognitive demands of the planning1 design cognitive subtask of programming. In terms of cognitive demands, details of the various proposals for how planning takes place in programming, whether the top-down orientations with successive plan refinement or more opportunistic approaches analogous to the work of Hayes-Roth and Hayes-Roth (1979) , imply that preadolescents may have difficulties generating program designs, particularly ones that are complex and require hypothetical and counterfactual reasoning more characteristic of the older child. We shall provide a brief review of this literature in the section on conceptual development and programming. One of the principal cognitive problems comes down to what Stefik (l98la, 1981b) in his artificial intelligence work on planning called the recognition of "commitments" of plan components, involving seeing ahead or symboli- cally executing plans or plan parts in order to mentally simulate the consequences of particular design proposals, and finding problems with those commitments that indicate the need for a new design. Pennington (1982) has indicated problems with the very general nature of proposals that program plans are hierarchical in nature, such hierarchy representing successive refinements of the program description until a solution that can be mapped out in programming code is reached. How do each of these successive versions of the plan represent and further elaborate the four basic types of program information, that is: (a) the purposelfunction of a particular plan unit; (b) the structure of the data objects; (c) the sequencing of operations (control flow); and (d) the transformations of data objects (data flow)? As she notes: Little empirical evidence exists on how programmers coordi- nate and transform the four types of information embodied in a final programming product, yet it seems that these coordinations underlie the complexity of programming and other planning tasks. (p. 19) We would agree here, but note further that studies of the develop- ment of planning for any content domain are in their infancy (Friedman, Scholnick & Cocking, 1983; Pea, 1982). What evidence exists indicates that, at least for planning problems utilizing familiar classroom chores in a chore-scheduling task where the goal is to find the shortest possible plan for doing all the chores, children from 8 to 12 years of age are capable of substantial "debugging" of long plans through revisions. We may now ask: What programming knowledge is necessary to design the program plan? As discussed earlier, expert programmers chunk familiar patterns of programs, as indicated by the quality of their program comprehension as indexed by program recall. It is currently unclear how this knowledge is organized or acquired (an account of cognitive skill acquisition comparable to J. R. Anderson [I9821 could be offered as a model of the latter), although these are fundamental developmental questions. Some proposals have been made on the character of the expert pro- grammer's memory store, but little evidence is available. Some alter- natives as reviewed by Pennington (1982) -are set out below, and aim to answer the question of what programming knowledge schemas or chunks are available to the expert. The implication for our questions about children are that whatever kinds of programming knowledge are required by children of the age of interest would have to be learnable in order for program plans drawing on such knowledge to be achev- able. So what are the schemas? a) Anything from transactions (less than a programming state- ment) to chunks (unit that accomplishes a goal) to higher level chunks (familiar algorithms) (Mayer, 1981) ; b) Hierarchy of patterns from operations (compare two numbers) to small algorithms (sum an array) to large algorithms (bubble sort) to program patterns (Shneiderman 1980; Shneiderman & Mayer 1979); c) Known solutions /plans /plan elements ( Atwood, Jeffries & Polson, 1980; Balzer et al., 1977; Miller & Goldstein, 1979) ; c l ) High-level programming units such as loop and recursion strusture (Rich, 1981; Rich & Shrobe, 1979; Soioway & Woolf, 1980; Soloway et id., 1982); e) BuiJding block units such as basic loop, augmentation, and tilter (Waters, 1979) ; f) Categories with internal structure, such as rules for data structures, enumerations (looping constructs) , mappings, etc. (Barstow, 1977, 1979). 3. Coding a Program This phase of program development consists of a translation from the most refined version of the program design into the programming code. Brookst (1975) estimate of less than 200 coding templates necessary to define the syntactical arrangements of code in statements makes clear why it is said in the programming industry that coding is a much simpler process than program design, which appears to in- volve a much more vast and initially ill-defined problem space. According to Brooks (1982), only one-sixth of the time allocated to a software project should invlove the actual writing of the program code. It is unlikely that this phase can be completely independent of the program planning phase , since different programming languages provide different options for plan implementation, such as "the availa- bility (or lack) of linked list data structures"(Pennington, 1982, p. 24). Brookst (1975, 1977) study of a programmer's coding performance found symbolic execution, or what we might describe as mental simu- lation, to be the major feature of the coding process. Brooks' account postulates that a plan element triggers a series of steps through whch a piece of code is generated and then the programmer "sym- bolically executesn that piece of code in order to assign an effect to it. This effect is compared with the intended effect of the plan element; any discrepancy causes more code to be generated until the intended effect is achieved. Then the next plan element is retrieved and the process continues. Throughout this process a representation of the program is built up, storing information about the objects (variables, data structures, etc. ) , their meanings, and their properties. (See Pennington, 1982, p . 24) Once again, as in the case of plan construction where symbolic exe- cution plays a major role, we find that program coding requires sub- stantial hypothetical thought. A s for the cognitive demands of gen- erating program code, we may note three general classes of apparent prerequisites: (1) ability to engage in hypothetical symbolic exe- cution of code; ( 2 ) ability to learn the coding templates that define the syntactical knowledge necessary for code generation : and (3) ability to keep to the goal at hand, or program plan, unless deviations from it are required to generate the code; in such an event the plan would need to be revised, with consequences for the code then to be generated to achieve it. 4. Comprehending and Debugging a Program How do programmers comprehend programs? In order to debug or modify their programs, they need to learn from their own or others' programs. If they are to realize how much progress they have made in developing a program, comprehension must play a key role. One extremely useful paper in thinking about this problem is by Green, Sime and Fitter (1980), who emphasize at some length the importance but current neglect sf developing means for "getting information - out of programs as well as into themL-the program comprehension prob- lem. They note that "some of the major problems [a programmer faces] come when the program is being debugged, or extended, or modified, or just when the past half-hour's work is being reviewed" (p. 894). Pennington (1982, p. 29) notes that "program comprehen- sion also involves reversing the forward mappings from problem representation in the external domain to successive levels of plans to programming language code." Program comprehension would thus require a n inferential retrieval of the program creation process. Four very different views of the program comprehension process have been proposed, and they have not been compared in terms of their empirical validity: one is bottom-up, one is middle-out, one is top- down, and one is transformational (Pennington, 1982, pp. 26-27, whom we follow closely in this section). Shneiderman (1976) finds expert programmers to recall more gist, or high level ldgic, of the program than do novices. He later (198Q) argued for a bottom-up construction of meaningful units of programming code, from operations to aigsrithrns on up to the £unction of the program as a whole. Atwood and Ramsey (1978) have a multiple pass model analogous to- Hayes-Roth and Hayes-Roth's (1979) opportunistic model of planning, in the sense that programmers utilize high-level and low-level infor- mation about the program structure advantageously in order to under- stand the program. On the first pass, some level of the [program] macrostruc- ture is integrated, possibly as high as program function, possibly at some level of chunking. Successive passes lead to integration of lower level propositions (working down) and successive integrations of the macrostructure (working up). (Pennington, 1982, p. 27) Brooks ( 1982) views program comprehension as hypothesis driven and as immediately seeking out the high-level schema for the program. The program reader then is said to seek out evidence for predicted program components consistent with their high-level expectations. This process works iteratively until the program reader has assimi- lated all the code to understand its precise workings. The complex transformational account offered by Rich, Shrobe and Waters (Rich, 1981; Rich & Shrobe, 1978, 1979; Rich, Shrobe, Waters, Sussman & Hewitt, 1978; Rich & Waters, 1981; Shrobe, 1979; Waters, 1978, 1979) implies that program understanding is mediated by a hierarchical representation of three levels: (1) deep plans (purpose) ; ( 2 ) surface plans (in program structure); and (3) definitions of data objects, properties, and 110 specifications for program code segments. What does all of this mean for the child who needs to be able to comprehend programs as one cognitive subtask of programming? Again, this is a complex question, since even at this level of subtask analysis this question is analogous to that of "What are the cognitive demands of (natural language) text comprehension?" which is far too general a question to be meaningful psychologically. The question asked should instead depend upon what kinds of text (in terms of text genre), logical complexity of the text, in terms of the inferences required to understand it (e. g., Clark, 1977), constituent state- ments, words and, in the case of the beginning reader, even letters, of which the text is composed (e. g., Gibson & Levin, 1975). At the most basic level, children would have to be able to read the lines of code and identify the meanings of the constituent elements of the program, or primitive commands. This much is basic. But a much more complex task is to understand the interrelationshps between these lines of code, to recognize the units, modules, or procedures which make up the meaning of the program as a whole. Studies (e. g., Kurland & Pea, 1983) demonstrate that comprehending pro- grams at multiple levels is a difficult task even for relatively expe- rienced child programmers from 8 to 12 years of age. However, what is as yet unclear is whether children do not tend to comprehend programs at "deepn levels because they have difficulty decoding even the surface syntax, or whether for the type of programming activities children typically engage in there is little incentive to probe below the surface. We have provided a brief account above of the four major constituent cognitive subtasks of programming insofar as they are currently understood in the literatures of cognitive science and software psy- chology. What we have observed is that even at this level of speci- ficity, although we can articulate at a general level some kmds of knowledge and abilities that children should have in order to mentally engage in these subtasks (which we will not review here), we found in each case that the four subtasks could be fruitfully decomposed still further. But surely such decomposition must at some point come to an end, or the resolution of our analysis will be so minute as to map one per one on each decision the programmer makes whle pro- gramming. There are no doubt an infinite diversity of those, much - Like utterances in natural language, and a cognitive demand analysis that is an infinite list is not of much use. So how fine shall the grains of the cognitive demand analysis be? Before falling into some existential abyss, let us not lose sight of the original goals of thinking about the cognitive demands of program- ming; that is, basically, to understand well enough what cognitive prerequisites different programming activities have so that children are able to pain entry to the world of programming, and so that overly complex programming subtasks are not required of them. Inevitably, there are those who will look for the curricular implica- tions of these analyses, and a certain amount of fuzziness or irnpre- cision will at first be likely. Insufficient data are available on the development of skills such as planning, symbolic execution, and problem understanding, and such data as do exist are derived from children's performances in task environments so unlike programming as not to be straightforwardly applicable to it. The consequence of this point is that s p e c i m g ages or prerequisite knowledge states at which certain programming activities can or cannot be undertaken is a risky business if done a priori, and cannot be warranted on the basis of available evidence. Instead, we need to design programming tasks in which children of different ages can attempt the programming cognitive subtasks we have outlined above, so that we can see on an empirical basis what children appear to be capable of. We will now review the few observations that have been made to date on the development of programming skills. To anticipate, our con- cerns above will not be reflected in the available literature. The Development of Programming Skills What nBecowg a Programmern Means: Children The few available studies of children's programming have not been developmental in nature, articulating intermediate stages of compe- tence en route to mastery and setting out constraints on the devel- opment of specific computer programming activities (such as those articulated above) in terms of prerequisite knowledge. Rather, these studies are observational and anecdotal studies of individuals' learning to program to show that "children can program," as well as to docu- ment some of the motivational benefits of such computer programming experience (e.g., Papert et al., 1979). We find that little thought or research has been directed to the important problem of articulating intermediate levels of computer pro&amming mastery. This is a serious knowledge gap since "understanding" is not an all-or-none mental state (e. g . , Nickerson, 1982) and the processes undergirding developmental transformations of a person's understanding are of central concern for a developmental cognitive science. Because Dewey's concept of 'Ireadiness to learn" has proven to be of such wide instructional applicability, we believe that delineating these intermediate forms of understanding must be a goal of developmental research on programming. This dearth of knowledge is compounded with the problem that, from the popular literature on children and programming, it appears as if everything we have learned about cognitive development during the last quarter century has suddenly been rendered irrelevant by the advent of the microprocessor. For example, 5-year-olds who can get a graphics cursor to work in the Logo programming language are called "programmers, 'I conveying the popular assumption that they have come to understand the logical operations ingredient to a program's flow of control, and are capable of all the cognitive subtasks of programming. Child Novice Pro~rammers Only limited evidence, somewhat bleak in character, is currently available on levels of programming abilities achieved by individuals of different age groups in the precollege-age population. These statis- tics should not, of course, be taken to indicate what each chld may be capable of if allowed his or own computer in school and the sup- port of optimal instruction. In the National Assessment of Educational Progress survey of 2500 13 -year-olds and 2500 17-year-olds during the 1977-78 school year (NAEP, 1980), even among the small percent- age of students who claimed to be able to program a computer, "per- formance on flowchart reading exercises and simple BASIC programs revealed very poor understanding of algorithmic processes involving conditional branching1' (cited by R. E. Anderson, 1982, p. 14). It is worth noting in this context that in current instructional envi- ronments, children appear to have basic conceptual and representa- tional difficulties in constructing dynamic mental models of what is happening when the computer is executing lines of their programs, which sets critical limits on the computer programming skill level that they attain. Furthermore, systematic but "naive1' mental models o r "naive epistemologies" (diSessa , 1982 ) of computer procedural func- tioning may initially guide and mislead chddren's understanding of programming, which, as we shall see, is the case for adult novice programmers. Empirical studies of the program comprehension proc- esses of children at various levels of computer programming expe- rience will be essential for an understanding of this issue. To take one example: In work at our laboratory with child Logo programmers (Kurland 81 Pea, 1983b), we have found that child novices frequently adopt a systema ic but misguided conception of the 5 manner in which control is passed between Logo procedures. Many children believe that placing the name of the executing procedure within that procedure causes execution to "1oop"back through the procedure when, in fact, what happens is that control is passed to a copy of the executing procedure. This procedure is then executed, and when that process is complete, control is passed back to the procedure which last called it. Children adopted models of flow of control which worked for simple cases, such as programs consisting of only one procedure or tail recursive procedures, but which proved inadequate when the programming goal required more complex pro- gramming constructions. In other studies of Logo programming development (Pea, Hawkins & Sheingold, 1983), even among the 25% of the children (8- and 9-year- olds, 11- and 12-year-olds) who were extremely interested in learning programming, the programs they wrote reached but a moderate level of sophistication after a year's work and approximately 30 hours of on-line programming experience. We found that children's grasp of fundamental programming concepts such as variables, tests, and recursion, and of specific Logo primitive commands such as REPEAT, was highly context-specific and rote in character. To take one example: A c u d who had written a procedure using REPEAT which repeatedly printed her namk on the screen was unable to recognize the efficiency of using the REPEAT command to draw a square. Instead, the child redundantly wrote the same line-drawing procedure four tim

less