Density Estimation: New Spline Approaches and a Partial Review
Martin B. Mchler a Seminar fr Statistik, ETH Zentrum u CH-8092 Zrich, Switzerland u e-mail: maechler@stat.math.ethz.ch CompStat, August 1996 (February 27, 2002)
$Id: P.tex,v 1.15 2002/02/27 17:49:20 maechler Exp
Abstract Apart from kernel estimators, there have been quite a few dierent approaches of generalized splines for density estimation. In the present paper, Maximum Penalized Likelihood (mpl) approaches are reviewed. In conclusion, penalizing the log density seems most promising. In my wp approach for semi-parametric density estimation, a novel roughness penalty is introduced. It penalizes a relative change of curvature which allows considering modes and inection points. For a given number of modes, l = (log f ) can be represented as l (x) = (x w1 ) (x wm ) exp hl (x), a semi-parametric term with parameters wj (model order m) and nonparametric part hl (). The mpl problem is equivalently solved via a boundary value dierential equation. Key words: Nonparametric, Semi-Parametric, Density estimation; Smoothing; Roughness penalty; Maximum penalized likelihood; Inection point; Boundary Value Problem, Dierential Equation, Unimodality, Multimodality.

Introduction

The nonparametric estimation of distribution or density functions is well-established and a variety of methods available, with kernel estimators being the ones most researched, see (Silverman, 1986; Izenman, 1991; Wand & Jones, 1995) for some review. Here, I will try to shed light on dierent approaches of density estimation. Whereas in nonparametric regression, spline functions have been investigated and used extensively, this is less the case for density estimation. Maximum Penalized Likelihood (mpl) estimation has been among the rst methods ((Good & Gaskins, 1971)) and still seems appealing when proper smoothness is desired ((Mchler, 1995b) and below). The histosplines of a Boneva, Kendall & Stefanov (1971) were another early approach of spline density estimation. As for the histogram however, the somewhat arbitrary choice of the knots has made the histospline less appealing. In the present paper, Ill review dierent splinelike approaches in section 2, present my own mpl approach in section 3, and in section 4 shortly look at some new approaches of semiparametric density modeling.
Maximum Penalized Likelihood (MPL)
Here, we will mainly consider generalized splines, i.e., approaches within the framework of maximum penalized likelihood estimation, mple (cf. (Thompson & Tapia, 1990, ch. 3 5) which contains (Tapia & Thompson, 1978)), considering dierent roughness penalties. Given independent observations x1 , x2 ,. , xn of X F , with smooth density d f (x) = dx F (x) on [a, b] (i.e., P [a X b] = 1 and therefore, xi [a, b] i), a < b +, our goal is to estimate the true f , or F. Sometimes, we assume that f is (twice continuously) dierentiable, and dene l(x) := log f (x) f (x) d l(x) = l (x) = dx f (x) log-density, (score function). (1)
To estimate f (or F or l, equivalently), we maximize the penalized likelihood criterion,

f F i=1

log f (xi ) (f ),

lL i=1

l(xi ) (l),
where F and L are appropriate function classes, f : [a, b] R+ , i.e., f (x) 0 for all x, or l : [a, b] R, respectively, with the property

f (t) dt =

a i l(xi ) a

el(t) dt = 1,

is the log likelihood, : L R+ or (f ) (log f ) = (l) the roughness penalty, and 0 the smoothing parameter. Often, the null space of , := {l | (l) = 0}, is nite dimensional. This is especially attractive, since in this situation, the limiting case, giving the most smooth solution, is equivalent to classical Maximum Likelihood estimation in , see below. Silverman (1982) (cf. (Silverman, 1986, ch. 5.4)), Cox & OSullivan (1990) and Gu & Qiu (1993) develop a nice theory, deriving existence and uniqueness results for a wide class of mpl problems, including speed of convergence and consistency in various norms.

Penalizing

f Good-Gaskins etc
b Good & Gaskins (1971) used the roughness penalty 1 (f ) = a f 2 (t)/f (t) dt, the Fisher b information which can be written as 1 (f ) = 4 a u 2 (t) dt where u := f. A second b b proposal was to generalize the problem to penalties 2 (f ) = a u 2 (t) dt + a u 2 (t) dt. De Montricher, Tapia & Thompson (1975) derive exact existence results for the proposed estimators of Good & Gaskins (1971), and were able to characterize the rst one as exponential spline, see also Thompson & Tapia (1990, ch. 4). However, the resulting curve has kinks, since the derivative f is discontinuous at every data point ((Silverman, 1986, 5.4.2)). Whereas the minimizer for the 2 problem will be smoother, it is delicate to be computed, because u(x) 0 is necessary ((De Montricher et al., 1975)). 2 b The Sobolev s-norm penalty 3 (f ) = a f (s) (t) dt (under f (j) (a) = f (j) (b) = 0 for j = 0, 1,. , s 1) is considered in De Montricher et al. (1975), where the authors prove existence and uniqueness, and (for s = 1) provide an approximating solution, using discretization. All these approaches have the drawback that the most smooth solution is problem atic, since the space {f ; (f ) = 0; f 0} is not well characterized or even degenerate.

Penalizing log f

Silverman (1982) (see (Silverman, 1986, 5.4.4)) introduces the penalty (l) = a l 2 (t) dt and proves consistency in three dierent norms. Silverman also proves that the solution of the constrained mpl problem (2, 3) is equivalent to solving the unconstrained problem

l(xi ) (l) n

el(t) dt,
for a very general class of penalties. The same is seen below for the Wp penalty. The choice of penalty here leads to the attractive feature that the smoothest limits ( ) are in = {l = 0} = {l quadratic} which are exactly the Gaussian distributions, and corresponds to normal ML estimation. This feature is analogous to the cubic smoothing splines in regression which lead to least squares linear regression for , and is a property which the vastly used kernel density estimates do not share (a regular smoothest limit does not exist there!). A related from several standpoints very appealing approach is to estimate (and penalize) the score function = l = f /f (which is a straight line for a Gaussian). Cox (1985) introduced and solved a penalized mean square error problem for the score function, and Ng (1994) provided further properties and computational algorithms. The logspline approach of Kooperberg & Stone (1991) and (1992) is an attractive practical approach of using cubic splines to model the log density. However, it is not an mple, but rather a ML estimation in carefully chosen space of regression splines (splines with knots determined by the data).

Penalizing Modes: Wp

Very early on, the number of modes (local maxima) of the unknown density has been considered important (e.g., (Cox, 1966; Silverman, 1981)) and even the number of bumps (concave regions between inection points) has been tried to be kept small ((Good & Gaskins, 1971), (1980)). Modes are often the important attribute of a distribution, since they (informally) lead to conclusions about the underlying population. Tests of unimodality (vs. multimodality) have been developed (see above, (Hartigan & Hartigan, 1985), and (Minnotte & Scott, 1993), for a nice graphical tool). See Mchler (1995a) for more examples in the literature. a An appealing notion of smoothness is considering local extrema and/or inection points of a curve. For nonparametric regression, I limited the number of inection points ((Mchler, 1993),(1995b)), as a special case of a very general approach of mple. Here, a for density estimation, I apply this approach to nding the best density function with a given number of local extrema, or almost equivalently, number of modes1. See Klonias (1984), Roussas (1991), and Cuevas & Gonzalez-Mantiega (1991) for approaches with a similar aim. Here, our goal is to estimate the density f such that it has (at most) m modes, i.e. typically, m = (2m 1)+ local extrema. For dierentiable functions f , w is a local extremum if and only if f (w) = 0, or equivalently, l (w) = 0. Denote the m local extrema

mode is used here for maxima x where f (x) = 0. For dierentiable densities f , this only excludes maxima at the end of the support interval, e.g., x = 0 for the exponential distribution (which has zero modes in our denition).
of f by w1 , w2 ,. , wm. From basic calculus we know that l factors into l (x) = pw (x) (1)j ehl (x) , where (5) (6) pw (x) := (x w1 )(x w2 ) (x wm ),
and hl is continuously dierentiable, but otherwise arbitrary (in the vast class of funcb tions with penalty a hl2 dt < ). The sign (1)j in (5), determined by j = 0 or 1, is assumed to be given (and will be negative, j = 1, in most situations). Note that from (5),
(log l (x)) = (l /l )(x) = hl (x) +

1 , x wj

such that hl can be regarded as l /l minus the poles. By specifying a penalty in terms of hl , we have a semi-parametric model approach, the parameters being the modes and antimodes wj , j = 1,. , m, and nonparametric component hl. b Here, we estimate f (and hl ), by maximizing the mpl (2) where (l) = a hl2 (t)dt, and L is the set of all functions l : [a, b] R fullling (5), (6) in addition to the normalizing b condition (3), a el(t) dt = 1. L is therefore the product of Qm Rm (w Qm ) and the space of functions hl;w. In eect, we will minimize over the space of hl for xed w, and globally over all mode locations w. b In the following, the situation for xed w is considered. The penalty a hl2 (t) dt contains the derivative hl which can be expressed as hl (x) = L (x) L (x)
1 + l(x)l (x) 3(1 + l2 )1 (x), x wj
by using (7) and L /L = l /l 3ll (1 + l2 )1 where L is the curvature of L(x) = x l(t) dt. Arguments in Mchler (1989) and (1993) suggest that a natural roughness a penalty for a curve y = g(x) is the relative change of curvature / where (x) = 3/2 g (x) 1 + g 2 (x) is the curvature at x. Eq. (8) implies that hl approximates the relative change of curvature apart from the poles of L. Using a Lagrange parameter for the side condition (3) and making use of Diracs distribution notation, the problem (2) is equivalent to the variational problem

(t xi )l(xi ) + hl2 (t)

Dierential Equation
Now we apply Theorem 1 of Mchler (1995b) (and (1989),(1993)) which gives the Eulera Lagrange ordinary dierential equation (=: o.d.e.) and boundary conditions for a vast class of variational problems in a convenient form: Theorem 1 (Mchler) a The minimizer f of Fg where Fg (t, g) := d dt

b a 2k

S(f (t), t) + {(d/dt)k F (t, f () (t))}2 dt 1 F = (1)+k+1 Sf [] (t) 2 Sf [0] (x) := for all t [a, b],

fullls the o.d.e. (10)

x [j] a Sf (t)

g F (t, g),

f S(f, x) f =f (x) ,

and Sf [j+1] (x) :=

for 0 j <. The boundary conditions of this very general problem are 4

(A) (B)

Sf [1] (b) = Sf [2] (b) = = Sf [] (b) = 0,

d ( dt )j F (t. ) = 0

for t. {a, b}

and j {k,. , 2k 1}.

For our problem (9), = k = 1, and S(l, x) = el n (x xi )l(xi ). Therei=1 x x fore Sf [1] (x) = a l S(l, t) dt = a el(t) dt n 1[xi x] = F (x) nFn (x), where i=1 Fn (x) is the empirical distribution function dened as Fn (x) = n1 n 1[xi x]. Furi=1 ther, F (x, l ) = hl (x) = log |l /pw (x)|. The boundary conditions (A) are 0 = Sf [1] (b) = F (t)nFn (b) which entails = n for the Lagrange parameter because F (b) = Fn (b) = 1. The conditions (B) are 0 = d/dx F = hl (x) at the boundary x = a or b. The o.d.e. is Fg (d/dx)2 F = 1/2(1)3 Sf [1] (x), and Fg =

g F (g, x)

log |g/pw (x)|

= 1/l ,

(d/dx)2 F = hl and Sf [1] = n(F Fn ) from above. Therefore, the characterizing EulerLagrange o.d.e. for problem (2) is hl (x) = with boundary conditions F (a) = 0, F (b) = 1, and hl (a) = hl (b) = 0, (12) l (x) n (Fn (x) F (x)) , 2 (11)
where Fn is the empirical distribution function. This 4th order o.d.e. for F can be rewritten as 1st order with four unknown functions (F, l, hl , hl ), F = exp(l), l = (1)j pw exp(hl ), hl = {hl } , and hl obeys (11). Note that the data only enter through Fn , and the modes (and antimodes) are specied in pw = (x w1 ) (x wm ). This boundary value o.d.e. is solved numerically to obtain the mple for xed w = (w1 , w2 ,. , wm ). I have used a collocation method o.d.e. solver, colnew from netlib, see (Bader & Ascher, 1987), and, (Ascher, Mattheij & Russell, 1988). Numerical boundary value o.d.e. solvers require an initial crude approximate solution to be provided. The log-splines of Kooperberg & Stone (1992) have been convenient pre-smoothers for this. Experience indicates that the locations wj of modes and antimodes are quite well determined by such a pre-smoother initially. For the nal estimate, the minimizer of (2), the penalized log-likelihood of the above o.d.e.-solution must be minimized over w. This is relatively easy, at least as long as the number m of local extrema is not too large for the problem. Example. The Old Faithful geyser eruption lengths are at least bimodal, and have been used before (e.g., (Silverman, 1986; Hrdle, 1990)). Here I use the data set a dat.geyser$x as supplied in the Statlib (ftp lib.stat.cmu.edu) submission S/haerdle. These are n = 272 observations (at 126 values) of consecutive eruption lengths in minutes (rounded to seconds precision). Figure 1 shows the data and a Gaussian kernel density estimate with window width h = h =.3348 which is default (3.31) from Silverman (1986) and one with smaller bandwidth h =.1. The rst kernel density looks perfect showing two modes and no unnecessary bumps. A closer look (e.g., plot F (x) and Fn (x) vs. x) however reveals that the bandwidth chosen is too large (since the asymptotic for h is geared towards unimodal densities, (Silverman, 1986, 3.4.2, p.45)). The more appropriately tting kernel (h =.1) is wiggly (see also Fig. 2).

Figure 1: Old Faithful Geyser eruption lengths, n = 272; binned data and two (Gaussian) kernel density estimates (10) with h = h =.3348 and h =.1 (dotted).
lambda= 2^{-2} lambda= 2^{-4} G kernel (h =.1)
Figure 2: Estimated densities f (x) according to the new approach, (5), (6), (2), with two 2 , 24 and [a, b] = R. Both Wp curves are much smoother modes (m = 3), for = 2 than the Gaussian kernel estimate which even ts (somewhat) less to the data than the smoother Wp curve ( = 1/4). Figure 2 shows f (x) for = 22 , 24 and the Gaussian kernel from above. The estimates of our new approach are quite better (quantied in (Mchler, 1995a), where a a more extensive comparison is made). They t better to the data while being more smooth than traditional estimates (Gaussian kernels, parametric mixture of two Gaussian, logsplines) with comparable amount of t. While theoretical results are not yet available, current experience shows that the new class of density estimates provides very smooth curves while adapting to the data very well.

Properties of Solution

By this new approach, we get the distribution function with many derivatives, simultaneously, since F ,f , l = score of f , l are continuously dierentiable. f and l are still cad-lag (right-continuous, limit from left) being continuous functions of hl and therefore of the empirical distribution Fn. The prescribed number of modes is the main smoothing parameter. The (extra) smoothing parameter is of less importance, since for the roughest situation, 0 f is still smooth, whereas for nonparametric estimators, f would converge to the sum of -spikes at xi. Most smooth solution . The mpl criterion is solved in the limit 2 (t) dt equal to zero, and hence, h 0. In other words, by making the penalty hl l the mpl method for consists of doing ordinary maximum likelihood within the class of functions satisfying hl (x) 0 x [a, b]. Therefore, hl is constant, say h0 , and l (x) = cpw (x) (where the constant c = (1)j eh0 ). Consequently, l is a polynomial of degree m + 1. We consider the following situations: Zeromodal case: m = m = 0: We have l (x) c and therefore f (x) ec. For [a, b] = [0, ], this is the well-known exponential distribution. Unimodal case: m = m = 1. If for the sign, we exclude the rare case j = 0, we have l (x) = c(x w1 ), and f (x) exp(c(x w1 )2 /2), i.e, for [a, b] = R, f is the normal density with mean w1 (and ML estimate w1 = xn ). Hence, the smoothest limit consists of parametrically estimating a normal density. General case: For simplicity, lets assume j = 1, i.e., minus sign in (5). We have l (x) = c(x w1 )(x w2 ) (x wm ), and therefore l(x) = l0 cSw (x), where x 1 Sw (x) := 0 pw (t) dt = m+1 xm+1 m ( wj )xm + m1 ( i<j wi wj )xm1 . + (1)m j wj x. How is l0 determined? Let I(c, w) := a exp(cSw (t))dt. Then, 1 = f (x)dx = el0 I(c, w), whence l0 = log I(c, w). Now, maximizing the likelihood means

n log I(c, w) + c

Sw (xi )
This ML minimization problem is quite simpler than the general mpl problem (2). Extension: Bumps and Dips. As in Good & Gaskins (1980), one may want to consider bumps and dips (maximal concave and convex regions) of the density. As there is at most one mode in a bump interval, we can eectively control the local extrema via inection points. With this approach, we can require even more qualitative smoothness, and the mpl criterion approximately penalizes relative change of curvature of the log density l. By factoring l (x) instead of l (x), we get a very similar o.d.e. boundary value problem with b 1 an additional boundary condition ensuring a t f (t) dt = n n xi , i.e., an exact rst i=1 moment property. The generalization of considering l() for 1 is straightforward. For 2, the zeros of f () and l() no longer coincide which is a conceptual problem. For = 2, e.g., l = (f f f 2 )f 2 , and we have at least f 0 = l 0.
Semiparametric log-density modeling
The logarithm of the Gaussian density is quadratic, the simplest non-trivial concave parametric curve, and the exponential family being the most predominant class of densities, it seems natural to look at exible modeling of the log density rather than the density (or its square root). Semiparametric modeling of the log density has been achieved independently by Loader (1993) and Hjort & Jones (1994) by so-called local likelihood approaches (modifying the likelihood by a localizing kernel). Both models have several nice properties and lie exibly between parametric and nonparametric density estimation. Semi-Parametric Mixture Models. With our Wp approach, a dierent kind semi-parametric density models can be envisaged. For instance, a mixture of two, f (x) = pf1 (x) + (1 p)f2 (x), (14)
where f1 and f2 are modeled to be unibumpal, i.e., with only one bump, and will be estimated by mple ( = 2, m = 0) as above. In the limit, for 1,2 , this approach comprises traditional parametric (Gaussian) mixture models.

References

Ascher, U. M., Mattheij, R. M. M. & Russell, R. D. (1988), Numerical Solution of Boundary Value Problems for Ordinary Dierential Equations, Prentice-Hall series in computational mathematics, Prentice Hall, Englewood Clis, New Jersey. Bader, G. & Ascher, U. (1987), A new basis implementation for a mixed order boundary value ODE solver, SIAM J. Sci. Statist. Comput. 8, 483500. COLNEW. Boneva, L. I., Kendall, D. G. & Stefanov, I. (1971), Spline transformation: Three new diagnostic aids for the statistical data-analyst (with discussion), Journal of the Royal Statistical Society B 33, 170. Cox, D. D. (1985), A penalty method for nonparametric estimation of the logarithmic derivative of a density function, Annals of the Inst. of Stat. Math. 37, 271288. Cox, D. D. & OSullivan, F. (1990), Asymptotic analysis of penalized likelihood and related estimators, Annals of Statistics 18(4), 16761695. Cox, D. R. (1966), Notes on the analysis of mixed frequency distributions, J. Math. Statist. Psychol. 19, 3947. Cuevas, A. & Gonzalez-Mantiega, W. (1991), Data-driven smoothing based on convexity properties, in G. G. Roussas et al., eds, Nonparametric Functional Estimation and Related Topics, Kluwer Acad. Publ., Dordrecht, pp. 225240. De Montricher, G. F., Tapia, R. A. & Thompson, J. R. (1975), Nonparametric maximum likelihood estimation of probability densities by penalty function methods, Annals of Statistics 3, 13291348. Good, I. J. & Gaskins, R. A. (1971), Non-parametric roughness penalties for probability densities, Biometrika 58, 255277.

Good, I. J. & Gaskins, R. A. (1980), Density estimation and bump-hunting by the penalized likelihood method exemplied by scattering and meteorite data, JASA 75, 42 73. Comments & Rejoinder. Gu, C. & Qiu, C. (1993), Smoothing spline density estimation: Theory, Annals of Statistics 21(1), 217234. Hrdle, W. (1990), Smoothing Techniques With Implementation in S, Springer (Berlin, a New York). Hartigan, J. A. & Hartigan, P. M. (1985), The dip test of unimodality, Annals of Statistics 13, 7084. Hjort, N. L. & Jones, M. (1994), Locally parametric nonparametric density estimation, Stat. Res. Rep. 3, Dept. Math., Univ. Oslo. Izenman, A. J. (1991), Recent developments in nonparametric density estimation, JASA 86(413), 205224. Klonias, V. K. (1984), On a class of nonparametric density and regression estimators, Annals of Statistics 12, 12631284. Kooperberg, C. & Stone, C. J. (1991), A study of logspline density estimation, Computat. Statist. Data Anal. 12, 327347. Kooperberg, C. & Stone, C. J. (1992), Logspline density estimation for censored data, Journal of Computational and Graphical Statistics 1(4), 301328. Loader, C. R. (1993), Local likelihood density estimation, Tech. Rep. 91, AT&T Bell Labs. Mchler, M. B. (1989), Parametric Smoothing Quality in Nonparametric Regression: a Shape Control by Penalizing Inection Points, Ph.d. thesis, no 8920, ETH Zurich, Switzerland. Mchler, M. B. (1993), Very smooth nonparametric curve estimation by penalizing change a of curvature, Res. Report 71, Seminar fr Statistik, ETH Zurich. u Mchler, M. B. (1995a), Estimating distributions with a xed number of modes, in a H. Rieder, ed., Robust Statistics, Data Analysis, and Computer Intensive Methods Workshop in honor of Peter J. Huber, on his 60th birthday, Vol. 109 of Lecture Notes in Statistics, Springer, Berlin, pp. 267276. Mchler, M. B. (1995b), Variational solution of penalized likelihood problems and smooth a curve estimation, Annals of Statistics 23(5), 14961517. Minnotte, M. C. & Scott, D. W. (1993), The mode tree: A tool for visualization of nonparametric density features, Journal of Computational and Graphical Statistics 2(1), 5168. Ng, P. T. (1994), Smoothing spline score estimation, SIAM J. Sci. Statist. Comput. 15, 10031025. OSullivan, F. (1988), Fast computation of fully automated log-density and log-hazard estimators, SIAM J. Sci. Statist. Comput. 9, 363379.

Roussas, G., ed. (1991), Nonparametric Functional Estimation and Related Topics, Vol. 335 of NATO ASI Series. Series C, Kluwer Academic Publishers, Dordrecht. Silverman, B. W. (1981), Using kernel density estimates to investigate multimodality, Journal of the Royal Statistical Society B 43, 9799. Silverman, B. W. (1982), On the estimation of a probability density function by the maximum penalized likelihood method, Annals of Statistics 10, 795810. Silverman, B. W. (1986), Density Estimation for Statistics and Data Analysis, Vol. 26 of Monographs on Statistics and Applied Probability, Chapman & Hall, London. Tapia, R. A. & Thompson, J. R. (1978), Nonparametric Probability Density Estimation, John Hopkins Univ. Press, Baltimore. Thompson, J. R. & Tapia, R. A. (1990), Nonparametric Function Estimation, Modeling, and Simulation, SIAM, Philadelphia. Wand, M. P. & Jones, M. C. (1995), Kernel Smoothing, Vol. 60 of Monographs on statistics and applied probability, Chapman & Hall, London.

Usability Issues in the Design of Novice Programming Systems
John F. Pane Brad A. Myers 1 August 1996 CMU-CS-96-132
School of Computer Science Carnegie Mellon University Pittsburgh, Pennsylvania 15213-3891
Also appears as: Human-Computer Interaction Institute Technical Report CMU-HCII-96-101

Abstract

This report reviews and organizes research about novice programmers. Over the past two decades, many aspects of novice programming have been investigated, resulting in the discovery of important facts and tradeoffs about what makes programming difcult to learn, and about the effectiveness of existing languages, environments, and methods of instruction. However, because this research is dispersed throughout the literature, it is difcult for designers of new programming systems to consider all of the issues collectively. The result is that most new systems are built primarily around technical objectives, perhaps considering only a subset of the usability issues summarized here. In addition to providing a checklist of issues that should be considered in the design of future systems, this report can be used to help researchers identify fruitful topics of future novice programming research.
The authors can be contacted by electronic mail at: John Pane <pane+@cs.cmu.edu> Brad Myers <bam+@cs.cmu.edu>
This research was partially sponsored by NCCOSC under Contract No. N66001-94-C-6037, Arpa Order No. B326, and partially by NSF under grant number IRI-9319969. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the ofcial policies, either expressed or implied, of the U.S. Government.
Keywords: Novice Programming Environments, Empirical Studies of Programmers, End-User Programming, Programming Languages, Human-Computer Interaction, Usability, Computer Science Education

Table of Contents

1. 2. 3. 4. 4-1. 4-2. 4-3. 4-4. 4-5. 4-6. 5. 5-1. 5-2. 5-3. 5-4. 5-5. 5-6. 5-7. 5-8. 5-9. 5-10. 5-11. 5-12. 5-13. 5-14. 5-15. 6. 6-1. 6-2. 6-3. 7. 7-1. 8. 8-1. 9. 9-1. 10. 10-1. 11. 11-1. 12. 13. 14. Introduction....1 Definitions....2 Organization of this Document....4 Visibility of System Status....5 Use Signalling to Highlight Important Information...6 Beacons.....7 Locality and Hidden Dependencies...8 Beware of Misleading Appearances....10 Avoid Subtle Distinctions in Syntax....11 Support Incremental Running and Testing with Immediate Feedback..12 Match Between System and the Real World...14 Choose an Appropriate Metaphor...15 Consistency with Metaphor....17 Consistency with External Knowledge...18 Closeness of Mapping....20 Support for Planning....23 Naturalness of the Programming Language...25 Visual vs. Textual....27 Effectiveness of Notation is Task Dependent...29 Control Structures....30 Loop and Recursion Control Structures....32 Support Direct Manipulation and Definition by Example..34 Choosing a Paradigm....35 Modularity and Abstraction....37 Cognitive Issues.....39 Instructional Design....42 User Control and Freedom....44 Avoid Requiring Premature Commitment...45 Viscosity....46 Support Secondary Notation....48 Consistency and Standards...50 Consistency in Notation....51 Recognition Rather Than Recall...53 Minimize Working Memory Load...54 Aesthetic and Minimalist Design....55 Principle of Conciseness....56 Help Users Recognize, Diagnose, and Recover from Errors..58 Support for Testing and Debugging...59 Help and Documentation....61 Provide Guiding Knowledge....62 Conclusions....63 Acknowledgments....63 Bibliography.....64

Introduction

This report summarizes research about novice programming. Over the past twenty years many research studies have discovered useful information about novice programmers, and identied good and bad aspects of todays programming systems1, both visual and textual. However, this body of research is widely distributed throughout the literature and is not well organized, making it difcult to use in guiding the design of new systems. The result is that these research results generally have not been systematically fed back into the design of new programming systems. Instead, the design of new languages and environments has most often been driven by technical objectives, such as ease of parsing, ease of generating fast code, closeness to the machine, ease of proving correctness, etc. Even systems that were designed for novice users or for teaching have not attempted to broadly survey this body of research before making critical decisions about the metaphor or model that the language is based on, the notation that is used in the language, and the environment. For example, the Turing language [Cordy 1992] was designed, in part, as a teaching language for children, with attempts to resolve perceived difculties with Pascal. However, the list of perceived difculties is focused primarily on missing features: lack of string handling facilities, type-safe variant records, modularity, concurrency, and type-safe compilation. The focus of this report is research about the novice programmer. Research that compares novices and experts is included, but research that focuses exclusively on experts is not included here unless it offers general insight into all programmers. Of course, many of the issues mentioned here are applicable to experts as well. Inspired by the Smith & Mosier user interface guidelines [Smith 1986b], we have gathered and organized this information so that it can be used in the design of new programming systems. The information is organized into topics that span the issues that researchers have explored. While the topics are interrelated in many ways, we have organized them using a subset of the usability principles called heuristics dened by the Heuristic Evaluation usability engineering method [Nielsen 1994]:2 Visibility of system status. Match between system and the real world. User control and freedom. Consistency and standards. Recognition rather than recall. Aesthetic and minimalist design. Help users recognize, diagnose, and recover from errors. Help and documentation. Each of these heuristics is represented by a section of this document. The introduction to each section contains Nielsens denition of the heuristic, followed by our interpretation of the heuristic in the domain of novice programming. Following each introductory section are topics summarizing the novice programming issues that fall into the heuristic.

References:

Beacons
Beacons are common code fragments that serve to indicate the probable presence of certain highlevel operations [Brooks 1983]. Although few have been identied, they are typically patterns that are not extremely common, and it is their infrequent appearance that makes them useful in conrming or suggesting a hypothesis about what the code does [Gellenbeck 1991b]. Thus they are useful for high-level understanding, but are less useful for detailed tasks like debugging [Wiedenbeck 1986b]. They have been shown to help experts in program comprehension [Boehm-Davis 1996]. These beacons are so strong that misleading ones can induce false comprehension in experts [Wiedenbeck 1989]. However, there is evidence that novices do not make effective use of beacons, probably because they have not learned the patterns yet [Gellenbeck 1991b, Wiedenbeck 1986a, Wiedenbeck 1986b]. This is supported in an analysis of eye movements of programmers, which found that experts spend more time viewing meaningful areas of the program while novices do not [Crosby 1990]. Even so, using colored cues to mark meaningful sections of code helps experts to nd bugs in those sections [Gilmore 1988]. Perhaps the environment should highlight meaningful areas such as beacons with color or other cues, to draw novices attention to them. This may also be instructional, because the beacons mark schemata that novices must learn anyway [Perkins 1986, Samuray 1989]. Context of Use: Justied by: Examples: Environment Empirical studies A beacon for sorting is the swapping operation, which exchanges the values of two variables:
temp := a; a := b; b := temp;
Cross References: References:
4-1. Use Signalling to Highlight Important Information [Boehm-Davis 1996, Brooks 1983, Crosby 1990, Gellenbeck 1991b, Gilmore 1988, Perkins 1986, Samuray 1989, Wiedenbeck 1986a, Wiedenbeck 1986b, Wiedenbeck 1989]
Locality and Hidden Dependencies
Many researchers argue that locality is important in programming: physical proximity should be encouraged and remote references should be avoided [Cordy 1992]; strongly-related subcomponents should be kept together, not dispersed [Bonar 1990]; delocalized plans cause difculty [Soloway 1988]; and hidden dependencies and poor visibility reduce understanding [Green 1996]. To the extent that information is visible on the screen, working memory limitations are reduced, allowing novices to perform better [Anderson 1985, Green 1987]. These observations are to some extent opposed to modularity and abstraction, which tend to hide details and make related pieces of code more distant from one another [Green 1996]. Part of this problem can be relieved by intelligent use of secondary notation [Green 1990b], or with modern environments that use powerful navigation features to make the remote code easily accessible [Goldenson 1991, Miller 1994]. [Lewis 1987] proposes replacing programming by synthesis with programming by modication, where a library of examples is provided, from which the programmer chooses an appropriate one for a starting point, identies needed modications, then modies it to suit the current need. This elevates locality because it is an important factor in understanding the examples. Context of Use: Justied by: Examples: Environment Empirical studies, expert opinion The Turing language attempts to group things physically close to one another and avoid remote references where possible. Declarations are not distinct from statements or runtime constants. For example,

[Brusilovsky 1994a, Clements 1995, Davis 1993, du Boulay 1989a, du Boulay 1989b, Goldenson 1991, Green 1996, Gugerty 1986b, Lewis 1987, Miller 1994, Myers 1988, Nardi 1993, Perkins 1986, Smith 1992]
Match Between System and the Real World
The system should speak the users language, with words, phrases, and concepts familiar to the user, rather than system-oriented terms. Follow real-world conventions, making information appear in a natural and logical order [Nielsen 1994]. The research in this section investigates the expectations and behaviors that a novice brings to programming, such as natural language and knowledge of the real world. It discusses ways that the programming system can effectively exploit the expectations and support the behaviors, in order to maximize the net positive transfer to programming. Several points are made about common programming constructs that do not match well with the way users tend to express concepts in natural language. In addition, the task-dependent nature of the effectiveness of the programming system is examined. While this section covers consistency between the programming system and the outside world, Consistency and Standards on page 50 covers internal consistency. [Payne 1986] describes a formal method for assessing both of these forms of consistency.
Choose an Appropriate Metaphor
A metaphor is a familiar analogy for how the programming system works. When the metaphor is good, users can infer how the programming system works by referring to their existing knowledge and expectations about how the modeled system works; otherwise they might be required to learn a collection of rules that seem arbitrary. In order to maximize this transfer of knowledge, the metaphor should be based on, and conceptually close to, a concrete real-world system that is widely known by the user audience [Smith 1994]. This familiarity requirement is violated by Prolog, where misconceptions abound in users models of searching, matching, and backtracking [Fung 1990, Fung 1987, Mendelsohn 1990]. An appropriate concrete model can have a strong positive effect on the usability of a programming language [Mayer 1989]. Context of Use: Justied by: Examples: Computational metaphor of the language Empirical studies, expert opinion Traditional programming languages use a computational model of the von Neumann machine, which has no physical world counterpart. Learning this computational model is an important stumbling block for novices [du Boulay 1989a, du Boulay 1989b]. The spreadsheet is widely viewed as a successful instance of a programming language that is useful to non-programmers. An important advantage of the spreadsheet is that it is based on a metaphor that ts very well with the tasks of its audience: page-oriented numerical computation for nancial or other purposes [Nardi 1993]. Use of spreadsheets requires mastery of only two concepts: cells as variables and functions as relations between variables. Typically users use fewer than ten functions, including basic arithmetic and rounding. It is not necessary to string together low-level primitives, allocate memory, name variables, include les, etc. It is a familiar, concrete, visible representation that allows users to feel as though they are working directly on the task [Lewis 1987]. Unfortunately, this metaphor does not seem to extend well to general-purpose computation. Logo uses the metaphor of a turtle in a two-dimensional world. Even this concrete model has its difculties. For example, when the turtle is facing south, the users left is the turtles right, and vice versa [Mendelsohn 1990]. [Resnick 1994] describes the extension of the Logo metaphor to parallel computing. Boxer uses a two-dimensional spatial metaphor for the organization of programs, but is not constrained to a single-level hierarchy of cells as spreadsheets are. All computational objects are represented in terms of a hierarchy of boxes, which can contain data such as text or graphics, or can contain behaviors in the form of Logo-like programs. It uses the metaphor of a port for accessing the contents of a box from a distant place in space [diSessa 1989].

Consistency with External Knowledge
Users bring to the programming task external knowledge that might interfere with correct understanding of the language. Most beginner programming errors can be interpreted as incorrect transfers from other representation/processing systems to the computer device [Bonar 1989, Mayer 1987]. Where their knowledge is lacking, it is common for novices to guess incorrect language syntax or semantics; these errors are indicators of transfers from other knowledge domains that are not compatible with the programming language [Hoc 1990]. Languages often use keywords that are loaded with meaning from natural language, and notation that is like math. While the mnemonic value of keywords is useful, it is important to beware of what is called the human interpreter problem, where reading the program in a natural language manner leads to an interpretation that is inconsistent with the correct meaning of the program [Bonar 1988b, Spohrer 1989a, Spohrer 1986b, Taylor 1990]. Students attribute to the machine the reasoning power of an average human [Sleeman 1988]. A large portion of bugs arise from inconsistency within the programming language or inconsistency between the programming language and the users outside knowledge of the world or natural language. [Pea 1986] discusses language-independent conceptual bugs which affect the ways in which novices perceive the computing domain. Context of Use: Justied by: Examples: Notation, metaphor Empirical studies, analysis of frequent novice errors, expert opinion There is a litany of inconsistencies between mathematical knowledge and the use of similar notation in programming languages like Basic, Pascal and C. Some examples lie in the use of variables [du Boulay 1989a, Putnam 1989]: a=2 and 2=a are not symmetric in assignment as they are in math; math does not use the concept of previous and next values of a variable, such as in the assignment statement a=a+1; math treats the identity of two symbols as permanent for the duration of the problem, while it is transient in programming, such as in the assignment statement a=b; math offers no hint about the direction of assignment whether the value of b goes into a or vice versa in the assignment statement a=b; initialization of variables is a concept that is foreign to math or counting. In math, the symbol + can be used as a summation operator with an arbitrary number of arguments. In many programming languages, + is only a binary operator [Hoc 1990]. Notably, spreadsheets do not restrict the addition to be a binary operator [Lewis 1987]. As mentioned in Avoid Subtle Distinctions in Syntax on page 11, Pascal does not permit a comma to be used as punctuation in a number [Pane 1996].
In natural language, then and and are often used in the sense of what next, unlike their use in Pascal or C: I went to the shop and then I bought a paper; wash your hands and set the table [Bonar 1989, du Boulay 1989a]. In Pascal, Repeat is used before the item(s) being repeated, but in natural language the opposite is usually true [Bonar 1988b, du Boulay 1989a]. In Logo, STOP causes the ow of control to return from the current procedure to the caller, but kids misinterpret this to mean that execution is halted completely [Kurland 1989]. One example of how programming does not support the natural way of expressing a task is sorting. When users are asked to sort a series of real boxes, inserting a box pushes the other boxes to make room. When dealing with arrays, this operation must be carried out explicitly by the programmer [Hoc 1990]. [Spohrer 1986b] found that many novice bugs occur when the user generates code in an order that is different than the built-in operator precedence in the language. The user expects that the program will execute in the order of generation, rather than according to the operator precedence rules of the language. This suggests that all operator precedence should be explicit rather than implicit. For example, expressions could be automatically parenthesized to show their evaluation order. Cross References: 4-5. Avoid Subtle Distinctions in Syntax 5-1. Choose an Appropriate Metaphor 5-2. Consistency with Metaphor 5-6. Naturalness of the Programming Language [Bonar 1989, Bonar 1988b, du Boulay 1989a, Hoc 1990, Kurland 1989, Lewis 1987, Mayer 1987, Pane 1996, Pea 1986, Putnam 1989, Sleeman 1988, Spohrer 1989a, Spohrer 1986b, Taylor 1990]

Closeness of Mapping

[Hoc 1990] describes programming as adaption of a plan from a familiar strategy to one that is compatible with the computer. This adaption is a renement process that can lead to the detection of incompatibilities between the real-world plan and the computers capabilities, or to a program solution that is not optimal. Similarly, [Green 1996] describes programming as mapping of operations in the problem domain into corresponding operations in the program domain. Thus it should be helpful to have a closeness of mapping between the task domain and program entities. [Merrill 1993] proposes as a design principle for all learning environments that the translation process from the students internal plans to the solutions external representation be minimized. The extent to which the language facilitates this is called the expressiveness of the language [Bell 1991]. Users have difculty understanding low-level primitives and how to compose them to form highlevel components of a plan [Hoc 1990, Nardi 1993]. This is one of the great cognitive barriers to programming [Lewis 1987]. From a psychological point of view, the composition of these primitives into high-level operations is difcult for the following reasons [Lewis 1987]: synthesis is inherently hard, because a large number of possible combinations must be explored; since primitives are unrelated to the task, they are difcult to understand; for the same reason it is hard to see what combination of primitives will produce the correct task-related behavior; synthesis must be carried out with little immediate feedback; when feedback becomes available it is informative only about the behavior of the big assembly rather than about the many little choices that had to be made in putting it together; since the fundamental maneuver is replacement of what is wanted by what to do, information about intent is not expressed directly and must be maintained separately, mentally or physically; and, it requires plan merging: constructions must be formed that carry out multiple purposes simultaneously. In addition, in traditional programming languages [Lewis 1987]: synthesis results in high viscosity because primitives and rules of combination are complex; commonly used primitives enforce the inner world / outer world distinction in which data manipulable by the system cannot be manipulated by the user; reliance on sequence as the fundamental mode of combination of primitives requires users to specify much irrelevant information; and, it takes great care and discipline to make sure the code is comprehensible. Instead, users should be permitted to formulate the problem using the objects, relationships, and processes of the problem domain [Lewis 1987]. [Fitter 1979] cites a principle of revelation in good notational schemes: the notation perceptually mimics the solution structure. Educators often address these problems by choosing to begin teaching with a small subset of the language, and to incrementally expand the subset until the entire language is nally exposed [Brusilovsky 1994b]. Sometimes, special programming environments are built around a starting subset of the full language. Another approach is to invent a special mini-language for teaching

which is not a proper subset of any full language. Usually these provide only the minimal set of primitives that are necessary to embody the desired programming concepts, and make all operations visible as concrete actions on the screen. [Brusilovsky 1994a] surveys a collection of minilanguages that are used as an introduction to programming (e.g. Karel the Robot [Pattis 1995]). A related requirement is to have built-in types and abstractions that are appropriate for the domain [Cordy 1992]. [Nardi 1993] points out that successful end-user systems are task-specic and empower the user. They lack the power of general purpose programming languages, but also lack the steep learning curve. This suggests the creation of a task-specic programming language for every task domain, which is incompatible with the desire to make a general-purpose language and environment. One approach to this dilemma is to provide high-level, task-specic, user-extensible libraries for the desired domains, and to try to eliminate the need for novices to learn a lot of lowlevel primitives [Green 1996, Green 1991, Guzdial 1992, Mendelsohn 1990]. Context of Use: Justied by: Examples: Notation and environment Observation of individual users. Here are two examples of the renement that is required to adapt a familiar strategy or plan to a programming solution: Making room in an array for insertion. The programmer must satisfy preconditions that do not exist in the original situation. using + as a binary operator, with initialization of an accumulator variable, instead of simply requesting summation. The user must decompose elementary actions into even more elementary ones [Hoc 1990, Lewis 1987]. The spreadsheet has a close mapping to the domain of numerical tables in accounting, and the common operations that are performed in that domain. There is a great distance in mapping the built-in operations of a language like Pascal to tasks such as manipulating strings. [Green 1996] uses cognitive dimensions to identify the following examples of closeness of mapping: poor: adding a vector in C or Basic; looping in LabView; success/failure in Prograph. good: electronics instrumentation in LabView; persistent variables in Prograph; locality of program plans in Prograph and LabView. [Nardi 1993] claims that Hypercards language, HyperTalk, is too much like a conventional programming language and not close enough to the end-users needs. High-level languages are more expressive than assembly languages. For example, it takes fewer statements to implement a loop in a high-level language.

in propositions. Since the english language treats this situation informally (if the choice is not a, b, or c), the confusion is not unexpected [Spohrer 1986a, Spohrer 1986b]. One way to avoid the above problem in Pascal is to use a set, where if (ch <> 'a') AND (ch <> 'b') AND (ch <> 'c') becomes if NOT (ch IN ['a', 'b', 'c']). But there are two things to note about this syntax. First, the most natural way to express this in English (if the character is not in the set.) leads novices to misplace the NOT, coding the expression illegally as if (ch NOT IN ['a', 'b', 'c']). Second, even when the NOT is positioned correctly in the expression, parenthesis are required for it to be evaluated correctly; such issues of operator precedence rarely surface in natural language. Another confusion is that programming languages often use OR for inclusive-or, while natural languages use the word for exclusive-or. Cross References: 5-3. Consistency with External Knowledge 5-4. Closeness of Mapping 5-5. Support for Planning [Biermann 1983, Bonar 1986, Bonar 1989, Bonar 1988b, Curtis 1988, Galotti 1985, Grice 1975, Hoc 1983, Hoc 1990, Ledgard 1980, Miller 1981, Nardi 1993, Nyuyen-Xuan 1987, Spohrer 1986a, Spohrer 1986b]

Visual vs. Textual

[Myers 1990] presents a taxonomy of visual programming languages. There is a widespread tendency to expect visual languages to be superior to text for novice programming. [Green 1991] calls this graphical superlativism, and cites the following claims in favor of visual languages over textual languages: two-dimensional visual perception is more natural and efcient than reading text; it is easier to get an overview of program structure in visual systems; it is easier to read a visual program because purely syntactic devices are reduced; the number of variable names is reduced in visual programs; in visual systems, relationships between components are expressed by lines rather than symbols, making it easier to follow the routes; iconic representation of components may be easier to discriminate and recognize than textual names and symbolicallyexpressed relationships; extra information is conveyed by the spatial layout of the visual program (secondary notation). [Blackwell 1996] is a comprehensive survey of these claims from the visual programming literature. If the claims are true, the benets may be particularly strong for novices.In a comparison of text-based and visual rapid-prototyping tools on a simple programming task, novice performance was closer to that of experts with the visual tools [Hasan 1996]. In Pursuit, a visual language based on a comic-strip metaphor was shown to be more effective than an equivalent textual language for novice generation of shell script programs [Modugno 1996]. Graphical superlativism was supported in [Cunniff 1987], where novices were able to recognize certain simple structures and to hand-execute short program segments more quickly and more accurately in a graphical language than in an equivalent textual language. However, there is a considerable amount of research indicating that graphical superlativism does not hold in larger more complex programs or for deprogramming tasks, where the novice must derive high-level goals and plans from the program text in order to fully understand and extend the program. Diagrammatic notations are good only for certain purposes [Gilmore 1984]. [Green 1991] claims that formalisms based on control ow are linear with exceptions, so they are easily represented in a textual language; while formalisms based on data ow may be more appropriately represented in a visual language. However, [Curtis 1988] found that a owchart representation was superior to textual pseudocode when the task involved tracing ow of control, but not for discerning highlevel relationships. If there is any advantage of owcharts over text it is at the detailed level, rather than at the overview level [Green 1992]. This may be because owcharts are poor for modularity [Green 1990a]. There is little advantage in using owcharts for supplementary documentation, although they are useful when they display knowledge that is difcult to extract from the program text [Shneiderman 1986, Shneiderman 1977]. [Atwood 1978] found that a textual program design language was better than a owchart. Overall, graphical programs take longer to understand than textual ones [Green 1992, Green 1991]. [Moher 1993] compared program comprehension in graphical vs. textual representations and found that graphics were no better than text and sometimes considerably worse. Flowcharts are of little help in debugging. They help to trace execution ow and localize the area where the bug is located, but are insufcient to identify the actual bug [Brooke 1980a, Brooke 1980b]. Visual languages are not more natural than text [Nardi 1993]. Most visual languages have high

Control Structures

One area difference between spreadsheets and many other programming languages is control structures. The lack of control structures in spreadsheets is an advantage [Nardi 1993]. [Lewis 1987] also points this out, and claims that spreadsheets are the model of the future because they allow the learner to suppress the inner world of programming, the world of variable declarations, loops, and I/O. Relationships among variables can be set up declaratively, and the system will maintain consistency. [Wandke 1988] cites a dramatic increase in cognitive effort when using control structures, leading to a reluctance to dene macros for repetitive tasks even if it would dramatically reduce the number of keystrokes required to perform a task. [Rogalski 1990] found that: high-level control structures are more difcult to express than the goto or jump style of control, but the latter is more difcult for managing complex control ow correctly; control structures that use positive alternatives present fewer difculties than negative ones (e.g. repeat until X is easier to understand than while not X, especially if X is a compound expression); difculty increases with depth of nesting; and students with a better background in math learn new control structures faster. [Sime 1977a] and [Sime 1977b] conrm that high-level control structures help the novice to manage ow of control, and also found that a structure editor assisted novices in generating correct nested control structures. Many novice errors with control structures can actually be attributed to misconception of variables. Describing a variable as a name or an address is the rst step toward xing this, although a more complex model is required when variables occur in iterative or recursive programs in imperative languages: the variable is no longer an address with a value, but needs to be seen as a function of execution, or a sequence of values [Samuray 1989]. Indeed, most introductory programming textbooks focus a great deal of attention on the use and understanding of control structures, suggesting that details about how control structures work is an area of great difculty for novices. However, in a study of high-frequency bugs, [Spohrer 1986a, Spohrer 1989a, Spohrer 1986b] found that only about one-third of bugs arise from novice misunderstandings of control structures. [Arblaster 1979] found that any type of structure is better than no structure at all, and that hierarchical structuring is not better than other types of structuring. Context of Use: Justied by: Examples: Notation Empirical studies, observations of individual users With IF statements, students make the following errors [Putnam 1989, Sleeman 1988]: expect the program to halt with an error if the condition on the IF statement is false and there is no ELSE clause; expect both the THEN and ELSE clauses to be executed;

Choosing a Paradigm

Most of the research in this report studies the classical imperative paradigm of computing where the user is in control of a single thread of execution. There are many other programming paradigms, including object-oriented, event-based, functional, programming by demonstration, graphical rewrite rules, autonomous agents, data ow, production system or rule-based programming, logic programming, parallel programming, etc. Some of these paradigms have achieved widespread use in research and professional software development communities. In other cases, only experimental systems have been developed to test a paradigm or a mixture of several paradigms. From a usability point of view, there is much room for investigation of this area, to determine the strengths and weaknesses of the various paradigms, and how the best features of multiple paradigms might be mixed into an effective novice programming system. Also, when introducing a new paradigm to people with some programming experience, there is a risk of negative transfer from the prior paradigm [Mendelsohn 1990, Siddiqi 1996, Wiedenbeck 1996]. Object oriented programming is widely advocated as a paradigm for quickly building programs from reusable components. However, this idea, when carried too far, has been found to have a detrimental impact on performance. Object oriented programming may have benets for up to three levels of class hierarchy, but deeper hierarchies have been found to be difcult to work with [Daly 1996]. A cognitive phenomena called conceptual entropy may be the root cause of this problem [Dvorak 1994]. Object-oriented design is not necessarily a natural design method. Programmers have difculty deciding which logical entities should be represented as objects and which as attributes of the objects [Dtienne 1990]. Perhaps careful construction of the programming environment could assist users with these problems and limit the use of object-oriented programming to situations where it will be helpful. Multiple inheritance may have additional advantages over single-inheritance object-oriented programming, but surveys of experienced programmers reveal mixed opinions. Some argue that it produces a more complex design, is more difcult to test, is more difcult to reuse, and is easy to abuse; while others argue that it produces a more appropriate design, and facilitates reuse and maintenance. There is little doubt that it adds complexity. An additional concern is that multiple inheritance is often implemented where it is inappropriate, resulting in object-oriented software that is more complex than is necessary. This leads to a recommendation to use multiple inheritance only where there is a strong case for using it [Daly 1995a, Daly 1995b]. Viewing procedures as object-like entities offers semantic power and syntactic elegance, but novice programmers view them with few object-like properties [Eisenberg 1987]. The authors suggest ways to improve instruction and the environment to overcome this. Note that this objectoriented view of procedures in a functional language is different than pure objects in object-oriented programming languages. [Rist 1996] describes the procedures in a functional language as encapsulations of goals with their plans; and points out that this encapsulation is orthogonal to the encapsulation of data with operations in an object-oriented language. Further, he states that goals and plans are not well captured in an object-oriented language. Context of Use: Justied by: Environment Empirical studies, informal observation of users, expert opinion.

Examples:

KidSim [Cypher 1995, Smith 1995] uses graphical rewrite rules and programming by demonstration to provide an end-user programming system for symbolic simulations of agents in a two-dimensional grid. In KidSim, user testing revealed that arbitrarily deep hierarchies caused difculties for children, so a one-level simple inheritance scheme was adopted [Smith 1994]. AgentSheets is a paradigm that consists of a large number of autonomous communicating agents organized in a grid [Repenning 1993]. This spatial metaphor supports the problem solving process, which includes creating and changing external representations of the problem as well as exploring problem spaces [Repenning 1994]. ToonTalk uses video-game animation in a city populated by robots as the means of creating and viewing programs [Kahn 1996]. It uses programming by example, but instead of automatic induction or learning, requires the user to introduce generality by removing details from the example. LiveWorld is a programming environment based on rule-like agents that are responsive to their environment [Travers 1994]. It uses a novel object system that makes computational objects, such as behavioral rules, concrete and accessible like graphical objects. ShopTalk enhances direct manipulation with natural language text, in order to overcome some of the limitations of direct manipulation in specifying objects and actions [Cohen 1989].
5-1. Choose an Appropriate Metaphor 5-3. Consistency with External Knowledge 5-5. Support for Planning 5-7. Visual vs. Textual 5-11. Support Direct Manipulation and Denition by Example 8-1. Minimize Working Memory Load [Cohen 1989, Cypher 1995, Daly 1996, Daly 1995a, Daly 1995b, Dtienne 1990, Dvorak 1994, Eisenberg 1987, Kahn 1996, Mendelsohn 1990, Repenning 1993, Repenning 1994, Rist 1996, Siddiqi 1996, Smith 1995, Smith 1994, Travers 1994, Wiedenbeck 1996]
Modularity and Abstraction
Abstraction of functionality into modules is a powerful programming concept. It can promote information hiding, reduce the amount of code that must be understood in detail, and provide a suite of primitives that can be composed to implement new functionality. When programmers understand code at an abstract level they are more likely to reuse that code in other appropriate places, and that reuse is more likely to be by invoking the code (making a procedure call), which is a more efcient form of reuse than making a copy of the code in the new context [Hoadley 1996]. But novices are not ready to use the abstraction tools which are emphasized by modern languages [Mendelsohn 1990]. Modular programming is often taught through a discipline known as top-down design, where the program is rst described at an abstract, high level, then rened into a modular hierarchy [Wirth 1983]. However, hierarchically designed programs are not always easy to develop and comprehend [Curtis 1989, Perkins 1989]. Top-down strategies are difcult for novices because their spontaneous strategies or plans are based on concrete mental execution; action-oriented rather than object-oriented [Rogalski 1990]. And, taking modularity and abstraction to the extreme can interfere with locality and visibility (see Locality and Hidden Dependencies on page 8) [Green 1996]. One problem with comprehension of modular programs is that novices do not yet have the expert strategy of reading a program in a top-down, order-of-execution manner instead they read the program like a book [Gellenbeck 1991b, Jeffries 1982, Wiedenbeck 1986b]. Novices focus on the very literal and concrete, rather than the abstract, hierarchical, general view used by experts [Onorato 1986]. An environment that helps the novice to read and understand the program in a modular fashion and to identify meaningful sections may alleviate this problem. Novices using such an environment is described make very effective use of modularity [Miller 1994]. A modular program can be modied faster than an equivalent non-modular program when at least one of the following conditions hold [Korson 1986]: modularity has been used to promote information hiding, which localizes changes; existing modules provide a suite of useful generic functions that can be composed to implement new functionality; or, the modication requires an extensive understanding and modication of the existing code. However, modularity did not help in other cases, such as adding a new feature to a program. Another kind of abstract thinking that is difcult for novices is writing a general solution to a problem rather than a solution that is specic to the situation (e.g. a program that sorts a list). This requires students to make a shift from value processing to variable processing; and to elaborate some of the control decisions that are not consciously made in solving a specic problem [Hoc 1990]. Also, a lack of abstraction is evident in the tendency of novices to code loops as sequential actions, unrolled [Hoc 1989]. Examples and analogies play an important role in learning and understanding, and explanations help learners to generalize the examples [Lewis 1987]. Context of Use: Justied by: Environment, notation, and instruction Empirical studies, observations of users, expert opinion.

[Green 1992]

[Green 1996]

[Green 1991]

[Grice 1975]

[Gugerty 1986a]

[Gugerty 1986b]

[Guzdial 1992]

[Halasz 1982]

[Hasan 1996]

[Heller 1986]
Heller, R.S. (1986). Different Logo Teaching Styles: Do They Really Matter. Empirical Studies of Programmers. E. Soloway and S. Iyengar. Washington, DC, Ablex Publishing Corporation: 117-127. Hoadley, C.M., M.C. Linn, L.M. Mann and M.J. Clancy (1996). When, Why and How Do Novice Programmers Reuse Code? Empirical Studies of Programmers: Sixth Workshop. W. D. Gray and D. A. Boehm-Davis. Norwood, NJ, Ablex Publishing Corporation: 109-129. Hoc, J.-M. (1983). Analysis of Beginner's Problem-solving Strategies in Programming. The Psychology of Computer Use. T. R. G. Green, S. J. Payne and G. van der Veer. London, Academic Press: 143-158. Hoc, J.-M. (1989). Do We Really Have Conditional Statements in Our Brains? Studying the Novice Programmer. E. Soloway and J. C. Spohrer. Hillsdale, NJ, Lawrence Erlbaum Associates: 179-90. Hoc, J.-M. and A. Nguyen-Xuan (1990). Language Semantics, Mental Models and Analogy. Psychology of Programming. J.-M. Hoc, T. R. G. Green, R. Samuray and D. J. Gilmore. London, Academic Press: 139-156. Jeffries, R.A. (1982). Comparison of Debugging Behavior of Novice and Expert Programmers. Pittsburgh, PA, Department of Psychology, Carnegie Mellon University. Kahn, K. (1996). Drawings on Napikins, Video-Game Animation, and Other Ways to Program Computers. Communications of the ACM 39(8): 49-59. Kahney, H. (1989). What Do Novice Programmers Know About Recursion. Studying the Novice Programmer. E. Soloway and J. C. Spohrer. Hillsdale, NJ, Lawrence Erlbaum Associates: 209-228. Kesler, T.E., R.B. Uram, F. Magareh-Abed, A. Fritzsche, C. Amport and H.E. Dunsmore (1984). The Effect of Indentation on Program Comprehension. International Journal of Man-Machine Studies 21: 415-428. Kessler, C.M. and J.R. Anderson (1986). A Model of Novice Debugging in LISP. Empirical Studies of Programmers. E. Soloway and S. Iyengar. Washington, DC, Ablex Publishing Corporation: 198-212. Kessler, C.M. and J.R. Anderson (1989). Learning Flow of Control: Recursive and Iterative Procedures. Studying the Novice Programmer. E. Soloway and J. C. Spohrer. Hillsdale, NJ, Lawrence Erlbaum Associates: 229260.

[Hoadley 1996]

[Hoc 1983]

[Hoc 1989]

[Hoc 1990]

[Jeffries 1982]

[Kahn 1996]

[Kahney 1989]

[Kesler 1984]

[Kessler 1986]

[Kessler 1989]

[Korson 1986]

Korson, T.D. and V.K. Vaishnavi (1986). An Empirical Study of the Effects of Modularity on Program Modiability. Empirical Studies of Programmers. E. Soloway and S. Iyengar. Washington, DC, Ablex Publishing Corporation: 168-186. Kurland, D.M. and R.D. Pea (1989). Children's Mental Models of Recursive Logo Programs. Studying the Novice Programmer. E. Soloway and J. C. Spohrer. Hillsdale, NJ, Lawrence Erlbaum Associates: 315-323. Ledgard, H.F., J. Whiteside, A. Singer and W. Seymour (1980). The Natural Language of Interactive Systems. Communications of the ACM 23(10): 556-563. Lee, A.Y. and N. Pennington (1993). Learning Computer Programming: A Route to General Reasoning Skills. Empirical Studies of Programmers: Fifth Workshop. C. R. Cook, J. C. Scholtz and J. C. Spohrer. Palo Alto, CA, Ablex Publishing Corporation: 113-1136. Lehrer, R., T. Guckenberg and L. Sancilio (1988). Inuences of LOGO on Children's Intellectual Development. Teaching and Learning Computer Programming: Multiple Research Perspectives. R. E. Mayer. Hillsdale, NJ, Lawrence Erlbaum Asociates: 75-110. Lewis, C. and G.M. Olson (1987). Can Principles of Cognition Lower the Barriers to Programming? Empirical Studies of Programmers: Second Workshop. G. M. Olson, S. Sheppard and E. Soloway. Norwood, NJ, Ablex: 248-263. Lewis, C., P. Polson, C. Wharton and J. Rieman (1990). Testing a Walkthrough Methodology for Theory-Based Design of Walk-Up-and-Use Interfaces. Proceedings of ACM CHI'90 Conference on Human Factors in Computing Systems: 235-242. Littleeld, J., V.R. Delclos, S. Lever, K.N. Clayton, J.D. Bransford and J.J. Franks (1988). Learning LOGO: Method of Teaching, Transfer of General Skills, and Attitudes Toward School and Computers. Teaching and Learning Computer Programming: Multiple Research Perspectives. R. E. Mayer. Hillsdale, NJ, Lawrence Erlbaum Asociates: 111-135. Macaulay, L. (1995). Human-Computer Interaction for Software Designers, Thompson Computer Press. Mayer, R.E. (1988). Introduction to Research on Teaching and Learning Computer Programming. Teaching and Learning Computer Programming: Multiple Research Perspectives. R. E. Mayer. Hillsdale, NJ, Lawrence Erlbaum Asociates: 1-12.

[Kurland 1989]

[Ledgard 1980]

[Lee 1993]

[Lehrer 1988]

[Lewis 1987]

[Lewis 1990]

[Littleeld 1988]

[Macaulay 1995]

[Mayer 1988]

[Mayer 1989]
Mayer, R.E. (1989). The Psychology of How Novices Learn Computer Programming. Studying the Novice Programmer. E. Soloway and J. C. Spohrer. Hillsdale, NJ, Lawrence Erlbaum Associates: 129-159. Mayer, R.E. and A.L. Fay (1987). A Chain of Cognitive Changes with Learning to Program in LOGO. Journal of Educational Psychology 79: 269-279. McKeithen, K.B. (1981). Knowledge Organization and Skill Differences in Computer Programmers. Cognitive Psychology 13: 307-325. Mendelsohn, P., T.R.G. Green and P. Brna (1990). Programming Languages in Education: The Search for an Easy Start. Psychology of Programming. J.-M. Hoc, T. R. G. Green, R. Samuray and D. J. Gilmore. London, Academic Press: 175-200. Merrill, D.C. and B.J. Reiser (1993). Scaffolding the Acquisition of Complex Skills with Reasoning-Congruent Learning Environments. Proceedings of the Workshop in Graphical Representations, Reasoning, and Communication from the World Conference on Articial Intelligence in Education (AI-ED '93). Edinburgh, Scotland, The University of Edinburgh: 9-15. Merrill, D.C. and B.J. Reiser (1994). Scaffolding Effective Problem Solving Strategies in Interactive Learning Environments. Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society. Atlanta, GA, Lawrence Erlbaum Associates. Merrill, D.C., B.J. Reiser, R. Beekelaar and A. Hamid (1992). Making Processes Visible: Scaffolding Learning with Reasoning-Congruent Representations. Proceedings of the Intelligent Tutoring System Conference. C. Frasson, G. Gauthier and G. I. McCalla. New York, Springer-Verlag: 103110. Miara, R.J., J.A. Musselman, J.A. Navarro and B. Schneiderman (1983). Program Indentation and Comprehensibility. Communications of the ACM 26: 861-867. Miller, L.A. (1981). Natural Language Programming: Styles, Strategies, and Constrasts. IBM Systems Journal 20(2): 184-215. Miller, P., J. Pane, G. Meter and S. Vorthmann (1994). Evolution of Novice Programming Environments: The Structure Editors of Carnegie Mellon University. Interactive Learning Environments 4(2): 140-158.

[Mayer 1987]

[McKeithen 1981]

[Mendelsohn 1990]

[Merrill 1993]

[Merrill 1994]

[Merrill 1992]

[Miara 1983]

[Miller 1981]

[Miller 1994]

[Modugno 1996]
Modugno, F., A.T. Corbett and B.A. Myers (1996). Evaluating Program Representation in a Visual Shell. Empirical Studies of Programmers: Sixth Workshop. W. D. Gray and D. A. Boehm-Davis. Norwood, NJ, Ablex Publishing Corporation: 131-146. Moher, T.G., D.C. Mak, B. Blumenthal and L.M. Leventhal (1993). Comparing the Comprehensibility of Textual and Graphical Programs: The Case of Petri Nets. Empirical Studies of Programmers: Fifth Workshop. C. R. Cook, J. C. Scholtz and J. C. Spohrer. Palo Alto, CA, Ablex Publishing Corporation: 137-161. Myers, B.A. (1990). Taxonomies of Visual Programming and Program Visualization. Journal of Visual Languages and Computing 1(1): 97-123. Myers, B.A., R. Chandhok and A. Sareen (1988). Automatic Data Visualizations for Novice Pascal Programmers. Proceedings of the IEEE 1988 Workshop on Visual Languages. Pittsburgh, PA: 192-198. Nanja, M. and C.R. Cook (1987). An Analysis of the On-Line Debugging Process. Empirical Studies of Programmers: Second Workshop. G. M. Olson, S. Shepard and E. Soloway. Norwood, NJ, Ablex: 172-184. Nardi, B.A. (1993). A Small Matter of Programming: Perspectives on End User Computing. Cambridge, MA, The MIT Press. Nvrat, P. and V. Rozinajov (1993). Making Programming Knowledge Explicit. Computers in Education 21(4): 281-299. Nvrat, P. and V. Rozinajov (1996). Knowledge Based Programming: An Experiment in Selecting a Data Type. Arab Gulf J. Science. Res. 14(1): 79-100. Neal, L.R. (1987). User Modelling for Syntax-Directed Editors. HumanComputer Interaction - INTERACT '87. H. J. Bullinger and B. Shackel. New York, Elesevier. Nickerson, R.S., D.N. Perkins and E.E. Smith (1985). The Teaching of Thinking. Hillsdale, NJ, Lawrence Erlbaum Associates. Nielsen, J. (1994). Heuristic Evaluation. Usability Inspection Methods. J. Nielsen and R. L. Mack. New York, John Wiley & Sons: 25-62.

[Soloway 1988]

[Spohrer 1986a]

[Spohrer 1989a]

[Spohrer 1989b]

[Spohrer 1986b]

[Taylor 1990]

[Tognazzini 1992]

[Travers 1994]

[Van Laar 1989]

[Vessey 1984]
Vessey, I. and R. Weber (1984). Conditional Statements and Program Coding: An Experimental Evaluation. International Journal of ManMachine Studies 31: 47-60. Wandke, H. (1988). User-Dened Macros in HCI: When Are They Applied? Berlin, Sektion Psychologie der Humboldt-Universitt zu Berlin. Watters, A.R. (1995). Tutorial Article No. 005: The What, Why, Who, and Where of Python. UnixWorld Online.

[Wandke 1988]

[Watters 1995]
[Wiedenbeck 1986a] Wiedenbeck, S. (1986a). Beacons in Computer Program Comprehension. International Journal of Man-Machine Studies 25: 697-709. [Wiedenbeck 1986b] Wiedenbeck, S. (1986b). Processes in Computer Program Comprehension. Empirical Studies of Programmers. E. Soloway and S. Iyengar. Washington, DC, Ablex Publishing Corporation: 48-57. [Wiedenbeck 1989] Wiedenbeck, S. (1989). The Initial Stage of Program Comprehension, University of Nebraska. Wiedenbeck, S. and J. Scholtz (1996). Adaptation of Programming Plans in Transfer Between Programming Languages: A Developmental Approach. Empirical Studies of Programmers: Sixth Workshop. W. D. Gray and D. A. Boehm-Davis. Norwood, NJ, Ablex Publishing Corporation: 233-253. Wirth, N. (1983). Program Development by Stepwise Renement. Communications of the ACM 26(1): 70-74. Wu, Q. and J.R. Anderson (1991). Strategy Selection and Change in Pascal Programming. Empirical Studies of Programming: Fourth Workshop. J. Koenemann-Belliveau, T. G. Moher and S. P. Robertson. New Brunswick, NJ, Ablex Publishing Corporation: 227-238.

[Wiedenbeck 1996]

[Wirth 1983]

[Wu 1991]