"PoP Tasks":
(Experimental Problems in Psychology of Programming)
Psychology of programming research has regularly reused some problems as
a basis for experiments. There is no canonical list of these problems as
yet, so I am trying to build a list of the problems I find as I read the
PoP literature. I have included a full bibliography, so it is possible
to access a half-remembered problem by author.
There are also some as-yet unpublished contributions
in which people have described their own experimental tasks.
This list was last updated on 25 November 1996, and is no longer maintained.
The list is currently subdivided only by whether the problem has
mainly been used in experiments that test comprehension, or whether it
has been used to test implementation.
Imlementation Tasks
- The "Noah" Problem
- The problem is described by Rist
(1995) as "Write a program that shows the average and maximum
rainfall for a period. The end of the period is signalled by an input
value of -99"
[implementation language: Pascal]
The Noah problem has been used by numerous other researchers
for other languages.
See Cunniff et. al. (1986)
[implementation languages: Pascal and FPL (a graphical language)]
and Soloway - I have not tracked down his original formulation.
- The "Index" Problem
- The problem is described by Booth
(1992) as "Write a function index which takes a list (of type a
list) and an element (of type a) and returns the position of this
element in the list (the first element has the position 1 in the
list). If the element does not appear in the list, an error message
should be given"
[implementation language: Standard ML]
- Three Prolog Problems
- Noble (1992) set three problems in
Prolog: to square all numbers in a list unless the value is less than
6, to add an element to the end of a list, and to delete the Nth
element of a list.
[implementation language: Prolog]
- The Discount Store Problem
- Chen and Vecchio (1992) tested use of
nested conditionals with a problem in which a price had to be
calculated, dependent on the quantity of items purchased
[implementation language: BASIC]
- Array Reversal Problem
- Used by Green et. al. (1987) in a
comparative language study. The problem is described as "reverse an
array in place" or "reverse a list".
[implementation languages: Basic, Pascal and Prolog]
- The Train Timetable Problem
- A second problem in the Green et. al.
(1987) study. The problem is described as "consult a timetable of
Cambridge-London trains and find the last train to arrive at or before
a stated time".
[implementation languages: Basic, Pascal and Prolog]
- The "Traffic Counting" Problem
- Derived from a standard Pascal text (Findlay & Watt 1978) by Ratcliff & Siddiqui (1985) and also used by Green et. al. (1987). The problem
specification is "A traffic survey is conducted automatically by
placing a detector at the road side, connected by data-links to a
computer. Whenever a vehicle passes the detector, it transmits a
signal consisting of the number 1. A clock in the detector is started
at the beginning of the survey, and at one second intervals thereafter
it transmits a signal consisting of the number 2. At the end of the
survey, the detector transmits a 0. Each signal is received by the
computer as a single number (i.e. it is impossible for two signals to
arrive at the same time). Design a program which reads such a set of
signals and outputs the following: a) the length of the survey period
b) the number of vehicles recorded, c) the length of the longest
waiting period without a vehicle."
[implementation languages: Basic, Pascal and Prolog]
- The "Swim Meet Competition" Problem
- This was derived from a problem in an object-oriented design
textbook (Rumbaugh et.al. 1991) by Lee and Pennington (1994). The complete problem
description rather long - it is given in an appendix to the paper. The
basic requirement is to add up the scores achieved by different
competitors across multiple swimming events, on an individual and team
basis.
[implementation language: design only]
- The "RJE" Problem
- This problem, described by Scholtz &
Wiedenbeck (1992), is described as follows: "You are asked to
simulate a (simplified) version of a remote job entry facility which
modifies and transmits data between two computers. Your program will
do three things to each line of text read in: 1) Reverse the order of
the characters. 2) Translate the upper case characters to lower case
and vice versa. 3) If a line is less than 60 characters long, fill it
with *'s and write out a line of length 60. If a line is greater than
60, write it out as separate lines of exactly 60, filling the last
line with *'s if necessary."
[implementation language: Pascal and Icon (a string processing language)]
- The Manufacturing Capacity Problem
- Chatel et. al. (1992) used this
problem to test transfer between familiar and unfamiliar languages:
'You have been contacted in order to set up a car factory management
computing program. Various car models are to be manufactured. As the
end of the year is close, one of the executives in charge of the
production has asked you to estimate the car manufacturing capacity
for the next year, i.e. the number of cars which may be manufactured
with the available component parts in stock. This should make it
possible, in the future, to order component parts according to the
number of cars which are bought. In the first place, your program
should answer the following question: "How many standard model cars
can be manufactured with the component parts which are available in
stock?" You will take into account only the external parts of the car
and not the internal parts such as the engine, the seats etc.'
[implementation languages: Smalltalk, Pascal, C and Lisp]
- A Matrix Append Problem
- Pandey and Burnett (1993) used this
to compare their Forms/3 environment to Pascal and APL. It is
described as "Write a program in Pascal that appends two appropriately
shaped matrices into a single matrix. For example the program applied
to the matrices [two 3x3 matrices] returns the matrix [a 3 row by 6
column matrix]".
[implementation languages: Pascal, APL and Forms/3]
- Fibonacci Sequence Problem
- Pandey and Burnett (1993) used this
at the same time as the matrix append problem. The problem is:
"Write a program in OSU-APL that computes the first N elements
of the Fibonacci sequence. In the Fibonacci sequence, the first
two elements are 1, and each element after that is the sum of the
previous two elements. For example, given an N of 10, the program
produces: 1 1 2 3 5 8 13 21 34 55".
[implementation languages: Pascal, APL and Forms/3]
- Updating Stock Problem
- Hoc (1983) used this task to investigate
the effects on programmer strategies of successive constraints
introduced within a simulated computer. The problem is described as:
"The subject's task is to perform transactions as indicated by the
transaction file: e.g. '3 13' means 'add 13 to the quantity of item 3
in the old stock file' ... by the nature of the 'computer', files can
only be traversed sequentially, and so all the transactions for a
given item number must be done together. When all transactions for a
given item are completed, the value of the old stock cell is sent to
the new stock file."
[implementation languages: simulated computer]
- The Gifts Problem
- Hoc (1981) compared two structured
design methods by asking subjects trained in each method to spend 3
hours designing a program for allocating gift tokens to mail-order
customers under a rather complicated set of rules. The paper describes
these rules quite fully.
[implementation languages: flowcharts, then an unspecified language]
- Drug Company Deliveries
- Saariluoma & Sajaniemi (1994)
compared spreadsheet programs in the case where the elements naturally
formed rectangular areas, and where they didn't. Subjects had to write
spreadsheet formulae to work out subtotals from a table of different
categories of drugs against the number of deliveries in each month
of the year.
[implementation languages: spreadsheet]
- Carpets and Wallpaper
- Green and Navarro (1995)
also investigated problems based on rectangular areas - but in the
real world, rather than in a table of numbers. The program "took as
data the dimensions of a set of rooms, plus constants for price and
size of carpet rolls and of wallpaper rolls, and computed the total
cost of carpets and of wallpaper (no allowance being made for doors
windows etc.). Three different qualities of carpet were allowed for".
(The complete program wasn't published but is available by ftp from
Green's web page)
[implementation languages: LabView, Basic, Excel spreadsheet]
- The Lift Control Problem
- This is reported by Sonnentag (1996)
and originally attributed to Guindon (1990).
It is described as "design a software system that controls the
movement of N lifts between M floors by taking into account various
realistic constraints".
[implementation languages: Design only]
Comprehension Tasks
- BASIC Comprehension Problems
- Chee (1993) used the following problems to
assess understanding of models of BASIC: translate algebraic
expressions into BASIC; assess validity of assignment and increment
statements; predict output of loop summing numbers from 1 to 4;
calculate salary from hourly wage.
[implementation language: BASIC]
- Lambda Expression Comprehension
- Eisenberg et. al. (1987) tested
understanding of Scheme, and particularly of lambda-expressions, with
a series of expressions that carried out simple arithmetic operations
in the context of function applications. The complete test set is
included in an appendix to the paper.
[implementation language: Scheme]
- The Family Tree Problem
- This problem was used by Ormerod et. al.
(1986) to test comprehension of one of the classic problem domains
for introductory Prolog examples: relationships in a family tree. Two
families were presented in diagrammatic form, or as listings of facts
and rules. Subjects were asked to answer questions about the
relationships between specific individuals, based on either the
listing or diagrammatic representation. An alternative problem tested
a less familiar domain by presenting a hierarchy of management
functions that was homomorphic to one of the family trees.
[implementation language: Prolog]
- The Shellsort Problem
- Wiedenbeck (1986) Used an
implementation of a shell sort algorithm in Pascal to test the effect
of "beacon" lines on program comprehension and memory. The paper
includes a listing of the Pascal procedure which was used as test
material.
[implementation language: Pascal]
- The "Rocket" Problem
- Used by Curtis et.al. (1989), and
attributed originally to Barrodale et. al.
(1971), although they also cite its use by Shephard et. al. (1979) and Gilmore and Smith (1984). More recently, this
problem was used in comprehension studies by Green et al. (1991), then by Moher et. al. (1993). Green et. al. describe the
problems as: "The rocket program computes the path of a rocket of
given mass; the structure includes a while-loop (until rocket lands),
inside which is a conditional (the rocket tilts at time 11) and some
arithmetic". Most of the uses of this problem have been comparing
comprehension of graphical and text versions of the program. Curtis et.al. (1989) intended it to exhibit
complex algorithmic requirements without complex data structures
[implementation languages: FORTRAN, flowcharts, generic text, LabView,
Petri nets]
- The "Airport" Problem
- This has the same provenance as the Rocket problem, and was used
for similar purposes. It is described by Green et. al. (1991) as a
"simple Monte Carlo simulation, consisting of a for-loop (number of
trials) containing two conditionals (random arrival or departure) and
a nested conditional in which queues are serviced". Curtis et.al. (1989) contrasted it with the Rocket
and Inventory problems as containing both complex algorithms and
complex data structures.
[implementation languages: FORTRAN, flowcharts, generic text,
LabView, Petri nets]
- The "Inventory" Problem
- This was also derived by Curtis et.al.
(1989) from Barrodale et. al.
(1971), but it was not picked up by Green et al. (1991). According
to Curtis et. al., it "maintained an inventory for a grocery
distribution center. It processed orders for items at multiple stores
by fetching item records from a data base, decerementing the on-hand
inventory by the size of the order, reordering stock if necesary, and
preparing a bill for the total order." It was intended to express a
simple algorithm operating with a complex data structure.
[implementation languages: FORTRAN, flowcharts]
- The "Average" Program
- This is one of a set of four programs used by Soloway and Ehrlich (1984) and also by Détienne and Soloway (1990). It "calculates the
average of some numbers that are read in; the stopping condition is
the reading of the sentinel value, 99999." These studies focussed on
plan comprehension: a listing of the program is given in the Détienne
and Soloway paper.
[implementation language: Pascal]
- The "MaxNumber" Program
- This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It "finds the maximum
of some numbers." A listing of the program is given in the Détienne
and Soloway paper.
[implementation language: Pascal]
- The "Maxsentence" Program
- This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It "tests to see if
some variable contains a number that is greater than a maximum, and if
so, the variable is reset to the maximum." (This is a prison sentence,
not a text sentence; it is determined by a number of convictions). A
listing of the program is given in the Détienne and Soloway paper.
[implementation language: Pascal]
- The "SQRT" Program
- This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It caclulates the
square root of 10 numbers. A guard prevents the square root being
taken of a negative number. A listing of the program is given in the
Détienne and Soloway paper.
[implementation language: Pascal]
- The Backtracking Exercise
- This was used by
Taylor (1990) to study understanding of the
backtracking mechanism in Prolog. It was first devised by
Coombs & Stell (1985) in a study of
backtracking errors. It consists of 10 clauses, listed in
Taylor (1990) for which students were
simply asked to describe the execution process.
[implementation language: Prolog]
- Clients and Product Orders
- This was used by Pennington (1987)
amongst other programs that are not described to assess the
representations built by COBOL and FORTRAN programmers while
reading program text.
The problem is also used by Curtis et. al. (1984)
and Soloway et. al. (1983).
Only the COBOL text is given in the paper.
"This program solves a toy problem in which a list of clients and
their product orders for a month are processed and average order
sizes for two subsets of clients are computed".
[implementation language: COBOL and FORTRAN]
- Petrol Pump Controller
- This is described by
Brooke and Duncan (1980) as being used to
compare reading of flowcharts to (assembler-level) pseudocode.
The paper includes
a block diagram of the machine, a complete flowchart, and a complete
pseudocode listing.
[implementation language: flowchart and pseudocode]
- The Hungry Hare
- This was originally described by
Sime et. al. (1973)
as a program to control the eating habits of a mechanical hare. Two
synthetic languages were used, in which conditionals such as: (if
(juicy) then (if (leafy) then (if (green) then grill) else boil) else fry)
were expressed in either nested or GOTO form. The problem has since been
adapted by
Scanlan (1989) (amongst others) to compare
flowcharts and pseudocode. A drawing of the mechanical hare itself
can be found in
Arblaster et. al. (1978)
[implementation language: synthetic languages, flowchart and pseudocode]
Arblaster, A.T., Sime, M.E. & Green. T.R.G.
"Jumping to some purpose" The Computer Journal, 22(2), 105-109.
Barrodale, I., Roberts, F.D.K. & Ehle, B.L. (1971)
"Elementary Computer Applications in Science, Engineering and
Business" Wiley, New York.
Booth, S. (1992)
"The experience of learning to program. Example: recursion." in
Proceedings of The 5th Workshop of the Psychology of Programming
Interest Group: INRIA, Paris
Brooke, J.B. & Duncan, K.D. (1980)
"An experimental study of flowcharts as an aid to identification
of procedural faults". Ergonomics, 23(4) 387-399.
Chatel, S., Détienne, F. & Borne, I. (1992)
"Transfer among programming languages: an assessment of various
indicators" in Proceedings of The 5th Workshop of the Psychology of
Programming Interest Group: INRIA, Paris
Chee, Y.S. (1993)
"Applying Gentner's theory of analogy to the teaching of computer
programming" IJMMS 38, 347-368
Chen, H.-G & Vecchio, R.P. (1992)
"Nested IF-THEN-ELSE constructs in end-user computing: personality and
aptitude as predictors of programming ability" IJMMS 36(6), 843-860
Coombs, M.J. & Stell, J.G. (1985)
"A model for debugging Prolog by symbolic execution: the separation of
specification and procedure." Research Report No. MMIGR 137, Dept. of
Computer Science, University of Strathclyde
Cunniff, N., Taylor, R.P. & Black, J.B. (1986)
"Does programming language affect the type of conceptual bugs in beginners'
programs? A comparison of FPL and Pascal". Proc. CHI '86.
Curtis, B., Forman, I., Brooks, R.E., Soloway, E. & Ehrlich, K. (1984)
"Psychological perspectives for software science"
Information Processing and Management, 20, 81-96
Curtis, B., Shephard, S., Kruesi-Bailey, E. Bailey, J.. & Boehm-Davis,
D (1989)
"Experimental evaluation of software documentation formats" J. Systems
& Softwarew 9(2) 167-207
Détienne, F. and Soloway, E. (1990)
"An empirically-derived control structure for the process of program
understanding" IJMMS 33, 323-342
Eisenberg, M, Resnick, M & Turbak, F. (1987)
"Understanding procedures as objects" in Empirical Studies of
Programmers: 2nd Workshop: Ablex
Findlay, W. & Watt, D.A. (1978)
"Pascal: an introduction to methodical programming" (1st ed.) pp60-66:
Pitman
Gilmore, D.J. & Smith, H.T. (1984)
"An investigation of the utility of flowcharts during computer program
debugging" IJMMS 20, 357-372
Green, T.R.G., Bellamy, R.K.E. & Parker, J.M. (1987)
"Parsing and gnisrap: a model of device use" in Empirical Studies of
Programmers: 2nd Workshop: Ablex
Green, T.R.G., Petre, M. & Bellamy, R.K.E. (1991)
"Comprehensibility of visual and textual programs: a test of
superlativism against the 'Match-Mismatch' conjecture" in Empirical
Studies of Programmers: 4th Workshop: Ablex
Green, T. R. G. and Navarro, R. (1995)
Programming plans, imagery, and visual programming.
In Nordby, K., Helmersen, P. H., Gilmore, D. J, and
Arnesen, S. (1995) INTERACT-95. London: Chapman and Hall (pp. 139-144).
Guindon, R. (1990)
"Designing the design process: exploiting opportunistic thoughts"
Human-Computer Interaction, 5, 305-344
Hoc, J.-M. (1981)
"Planning and direction of problem solving in
structured programming: an empirical comparison between two methods"
Int. J. Man-Machine Studies 15, 363-383.
Hoc, J.-M. (1983)
"Analysis of beginners' problem-solving strategies in
programming". In T.R.G. Green, S.J.Payne and G.C. van der Veer (Eds.)
The Psychology of Computer Use. Academic Press.
Lee, A. & Pennington, N (1994)
"The effects of paradigm on cognitive activities in design" IJHCS
40(4) 577-601
Moher, T.G., Mak, D.C., Blumenthal, B & Leventhal, L.M. (1993)
"Comparing the comprehensibility of textual and graphical programs:
the case of Petri nets" in Empirical Studies of Programmers:
5th Workshop: Ablex
Noble, R. (1992)
"Preferential use of examples by novices learning prolog" in
Proceedings of The 5th Workshop of the Psychology of Programming
Interest Group: INRIA, Paris
Ormerod, T.C., Manktelow, K.I., Robson, E.H. & Steward, A.P. (1986)
"Content and representation effects with reasoning tasks in PROLOG
form" Behaviour and Information Technology 5(2) 157-168
Pandey, R.K. & Burnett, M.M. (1993)
"Is it easier to write matrix manipulation programs visually or textually?
An empirical study" In 1993 IEEE Symposium on Visual Languages.
Pennington, N. (1987)
"Stimulus structures and mental representations in expert comprehension
of computer programs" Cognitive Psychology 19, 295-341.
Ratcliff, B. & Siddiqui, J.I.A. (1985)
"An empirical investigation into problem decomposition strategies used
in program design" IJMMS 22, 77-90
Rist, R.S. (1995)
"Program structure and design" to appear in Cognitive Science
Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. & Lorensen, W.
(1991)
"Object-Oriented Modeling and Design", p.193: Prentice Hall
Saariluoma, P. & Sajaniemi, J. (1994)
"Transforming verbal descriptions into mathematical formulas in spreadsheet calculation". International Journal of Human Computer Studies, 41(6), 915-948.
Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. & Lorensen, W.
(1991)
"Object-Oriented Modeling and Design", p.193: Prentice Hall
Scanlan, D.A. (1989)
"Structured flowcharts outperform pseudocode: an experimental
comparison". IEEE Software, September 1989.
Scholtz, J. & Wiedenbeck, S. (1992)
"The role of planning in learning a new programming language" IJMMS
37(2), 191-214
Sheppard, S.B., Curtis, B., Milliman, P. & Love, T. (1979)
"Modern coding pratices and programmer performance" Computer 12(12)
41-49
Sime, M.E., Green, T.R.G. & Guest, D.J. (1973)
"Psychological evaluation of two conditional constructiuons used in
computer languages". IJMMS 5, 105-113.
Soloway, E., Ehrlich, K. & Black, J.B. (1983)
"Beyond numbers: Don't ask 'how many' ... ask 'why'" Proc. Conf.
Human Factors in Computer Systems.
Soloway, E. and Ehrlich, K. (1984)
"Empirical studies of programming knowledge" IEEE Transactions on
Software Engineering, 10(5), 595-609
Sonnentag, S. (1996)
"Planning and knowledge about strategies: their relationship to
work characteristics in software design"
Behaviour and Information Technology 15(4), 213-225.
Taylor, J. (1990)
"Analysing novices analysing Prolog: What stories do novices tell
themselves about Prolog?" Instructional Science 19(4/5), 283-309
Wiedenbeck, S. (1986)
"Beacons in computer program comprehension" IJMMS 25, 697-709
Click to return to Alan 
Blackwell's home page.