Early Software Design Experience Through Computer Game Programming
in the Functional Paradigm
Tamar Paz
Technion, Israel Institute of Technology
Orna Muller
Tel-Aviv University, Israel
Abstract
Programming projects in the functional paradigm enable
beginning students of computer science (CS) in high school to experience
the
whole process of developing a complex program in a relatively short
time. In
the course of project building the students practice the various stages
of
software development, such as system requirements analysis, top-down
design,
function definition, testing, documentation, and the design of a
user-friendly
interface, all while working in a team. This early exposure to the
stages of
program development makes the concepts and principles presented more
real and
meaningful when brought up later in more advanced CS courses. This
article was
written after seven years' experience in teaching a functional
programming
course in high schools in Israel, where students have successfully coped
with
developing, from scratch, programming projects taken from the field of
artificial intelligence. This experience demonstrates that the
functional
paradigm is an excellent environment for developing a project by
beginning
students.
1 Introduction
The computer science curriculum in the Israeli high
school system includes five modules (Gal-Ezer, Beeri, Harel &
Yehudai,
1995). Each module consists of 90 academic hours. The first two modules
constitute a course, Computer Science Fundamentals, taught in a
procedural
environment. The third module presents an additional programming
paradigm and
its main goal is to expose students to a significantly different
approach to
problem solving than that of the procedural paradigm. The fourth module
focuses
on data structures and software design and the fifth module is a
theoretical
unit (such as computational models). In this article we focus on one of
the
alternatives of the third module—a functional programming course.
The selected programming environment for teaching this
module is DrScheme, which was developed at Rice University in Texas
(Felleisen,
Findler, Flatt, & Krishnamuethi, 2001)1. The main topics introduced
in the
course include elementary language functions, the two main data types
(an atom
and a list), function definition, conditionals, and recursion (Leron,
Lapidit,
Levy & Paz, 1999).
The course lasts 90 hours in one academic year of which
about 60 hours are dedicated to introducing and practicing the above
language
features. The last 30 hours are devoted to writing a final project
required for
getting a credit for the course. However, gradual preparation for the
project
is integrated in the first part of the course, as will be described in
Section
4. The majority of students choose to develop a game, usually a card
game like
Taki or Poker, or a board game like Tic-Tac-Toe, Battleships, Othello,
Mancala,
Mine Sweeper, Monopoly, Four in a Line, Lotto, Dominoes, and others.
In the following sections we first discuss why the
functional paradigm is particularly well suited for developing a
large-scale
project by beginners. Later, we illustrate how students experience the
various
stages of software development, while acquiring basic principles of
computer
science.
2 The Functional Paradigm as a Well Suited Environment
for Developing Projects by Beginning Students
The functional environment facilitates the development of
a large and complex project by beginning students, since they are able
to learn
the language’s basic grammar in a relatively short time. This allows the
major
part of the course to be devoted to problem solving and program
development
practice.
2.1 Minimal Syntax
The functional paradigm relies on a small set of
syntactic rules. All of the expressions in the environment have a
uniform
structure. Parentheses constitute the only punctuation mark, and two
basic data
types (an atom and a list2) are sufficient for describing complex data
structures and non-linear structures like trees (Abelson Sussman &
Sussman,
1996; Felleisen et al., 2001).
The uniformity of representation of the different data
types simplifies the implementation of various operations on them (such
as
searching for an item). The ease of representation is achieved thanks to
three
main characteristics of a list: flexibility in the number of items (the
number
of items in a list, when passed as an argument in a function-call, may
vary at
different calls of the function), combining of different data types (a
data
list may simultaneously contain items of different types, including
items which
are lists themselves), and simple access to each item (through a library
function). A list, therefore, is a flexible data type that has the
advantages
of an array, a record, and a linked list. Furthermore, basic operations
like
adding an item to a list or merging lists are simple to implement.
During the first part of the course, students become
familiar with the elementary functions of the environment and the basic
data
types, and learn how to define new functions. This basic knowledge
enables
them, after only 12-15 academic hours, to develop from scratch a program
for a
relatively complex task such as checking if a given Tic-Tac-Toe board is
a
winning board.
2.2 Function Composition as a Basic Operation
The functional environment, as presented to the learners
of the course, encourages decomposition of a task into sub-tasks and
writing a
function for solving each sub-task. That is to say, the environment
encourages
thinking and writing of independent modules that solve specific
problems.
Function composition, a mechanism in which the returned
values of one function serves as input for another function, is a major
tool in
the functional paradigm. A program is built by means of composing
functions as
opposed to sequencing actions in the procedural programming. Although
the
environment allows direct assignments3, the course developers decided to
hide
this capability from the students (Leron et al., 1999). Use of
assignment
commands would have permitted students to continue their procedural
routine
(i.e., giving names to intermediate results by using assignment commands
and
storing the results in variables) and to program according to familiar
algorithms from the procedural environment (Paz, 2003).
2.3 Abstraction as a Tool in Organization and Control of
Complexity
Abstraction is an important tool in organization and
control of complexity both in mathematics and in computer science.
Developing a
complex program entails a process of abstraction at the stage of
dividing the
task into sub-tasks, as well as at the stage of defining data
representation.
Control of complexity is achieved by temporarily disregarding details
and by
developing "building blocks" that are appropriate for the
problem, as
well as for the programmer (Leron, 1987; Abelson et al., 1996).
In the programming of a complex task, the problem-solver
builds a metaphoric "abstraction barrier" that separates the
handling
of the task into two nearly independent sub-tasks: above the barrier and
below
the barrier. The "above the barrier" sub-task deals with
finding a
solution to the original problem in terms of the "building
blocks"
that were selected. The "below the barrier" sub-task deals
with the
details of implementing these "building blocks" in the given
programming language (Leron, 1987).
The functional paradigm, as presented to the learners,
constantly imposes throughout the development process building
abstraction
barriers, defining "building blocks", employing them (above
the
barrier), and implementing them (below the barrier). This experience
prepares
the students for the abstraction necessary when developing a program for
solving complex problems in other paradigms as well.
2.4 Interactive and Friendly Programming Environment
The functional programming environment allows for calling
each function independently, and not only as part of a whole program.
Therefore, students can explore new functions or modules by directly
testing
them with different inputs and performing a single function debugging.
The
visual support provided by the editor and the friendly and clear error
messages
also support modular writing and debugging.
2.5 "Soft" Exposure to Recursion
Another contribution of learning the functional paradigm
at an early stage is related to the “soft” exposure to recursion. The
only
repetition structure to which students are exposed is recursion.
Therefore,
from the first stages of familiarization with the paradigm, they are
required
to cope with writing recursive functions. Recursion is considered a
powerful
technique in problem-solving and for handling complex data structures.
At the
same time, many studies have revealed that recursion is one of the most
difficult concepts for comprehension, instruction, and learning,
especially for
beginning programmers (Leron, 1988; Mann, Linn & Clancy, 1994;
Segal,
1995). The functional paradigm facilitates "soft" entry into
the
topic of recursion, thanks to the uniform structure of the functions
which the
students write, and the relative ease with which they can build
recursive
functions and follow their execution.
3 Experiencing the Program Development Stages
While developing a project in the functional programming
course, students go through the same stages that are undergone by
software
developers (as for example, described in Pressman, 2001).
3.1 Software Specifications
At the first stage of developing their project students
choose, according to their personal preferences, the kind of program
they wish
to develop. If they choose to develop a game, they decide at this point
what
type of game it will be: Will the program arrange a game between two
human
players, or between a human player and the computer? What will be the
rules of
the game? Will the computer's moves (as a player) be chosen randomly or
according to some strategy? And so on.
This phase is compatible with the software specification
analysis stage in which the requirements of the system to be built are
defined.
The requirements should take into consideration different kinds of
factors
including the system's input data and the limitations of the development
timetable. At this time, students need to describe the main tasks to be
performed (the "what"), without the task implementation (the
"how"). Clear and detailed specifications help also at later
stages
like testing and evaluation of meeting the initial requirements.
3.2 Decomposition into Sub-tasks
After defining the requirements for the complete program,
students try to identify smaller tasks within the larger task. A
schematic
description of the game's algorithm helps in identifying the major
sub-tasks
required. When developing a game, preliminary sub-tasks are likely to
be:
building a game board or a pack of cards, shuffling and dealing cards,
checking
if a win was achieved, etc. Each task undergoes additional, more refined
partitioning (by stepwise refinement) to the level of identifying
actions that
can be implemented by separate functions (Wirth, 1971).
Students get an opportunity for a hands-on experience in
a top-down design, one of the main strategies employed to cope with the
complexity of a problem. Moreover, decomposition into sub-tasks is the
first
step in building a modular program. Modularity is a central principle in
software engineering, and has significant implications on the next steps
of
development. Students experience its importance in the context of team
work,
testing and debugging, and program extension.
3.3 Data Representation
Software design also entails choosing the main structures
in which the data will be organized. Different possible representations
are
defined and then compared. Students realize that they need to take into
early
consideration the influence of data representation on the ease of
implementing
the pre-defined operations. The issue of data representation and its
effect on
later steps of development are raised and discussed.
3.4 Coding and Integration
At this stage the previously planned modules are
implemented by writing functions’ code. Students are likely to make use
of the
functions they had written during earlier stages of the course, when
building
general tools for handling different tasks such as searching for an item
in a
list, updating a list, or constructing a list of random numbers. While
using
code written and checked previously, students practice the important
principle
of reuse. Students appreciate its benefits in saving effort and being
supported
by modularity and general functions.
Coding the separate modules is followed by their
integration into a complete game. The code integration stage requires a
gradual, bottom-up process of joining the various modules that were
developed
until a complete product is achieved. This stage poses a significant
challenge
to the students. The composition process is likely to include, for
instance,
the interleaving of the human-player and the computer moves that were
implemented in separate modules. Integration often requires writing
additional
auxiliary functions. Preparation for coping with the composition stage
is done
in prior stages of the course by solving a series of problems of
increasing
complexity.
3.5 Testing and Debugging
Since a functional environment facilitates immediate
checking of each functional module after its development, testing, in
fact,
accompanies all stages of development. Particular attention is given to
testing
improper inputs by the user ("the player").
The importance of modular writing is manifested again,
since it is made apparent that when the role of each module is defined
and
clear, it is easier to locate the module responsible for an observed
problem.
The smallest possible dependency between modules facilitates the
correction of
an error in one module, with no chain-effect on other modules.
3.6 Team Work
Projects are developed in groups of 2-3 students. While
some stages, like planning, are done in a team, the implementation of
modules
is done in parallel by the different team members. The development in a
team
framework clearly demonstrates the advantages of precisely pre-defining
the
interfaces of modules, and of task partition into modules with minimal
dependency between them.
3.7 Documentation
Concise and clear documentation of the program is a
highly important component in its development. The students realize the
importance of documentation when they are asked, as part of the project
requirements, to master the modules that were developed by other members
of the
team.
A project portfolio, which the students attach to the
developed software they present, documents various aspects of their
work.
Documentation includes justification for the chosen data structures,
guidelines
for operating the game, its description and rules, documentation of each
function and module (role, passed parameters, returned value,
assumptions
taken, etc.), program outline, and also some reflection on their
personal and
team experiences.
3.8 Extension
The capability of extending the game to achieve more
complex tasks may be evident by the possibility to introduce changes in
the
developed project. For instance, to allow variation in the size of the
game
board, to change the number of participating players or to modify the
rules by
which a game is won. The students learn how their program planning
(choice of
data representation, for example) is likely to affect the degree of
generality
and the extension potential of a program. Furthermore, students are
required to
suggest and implement various extensions in their program according to
different imposed changes.
4 Gradual Learning of Program Development, In Practice
This course went through several revisions. At the
beginning, the course started with an emphasis of language features and
their
practice by writing single functions only. After few years of teaching
the
course we have realized that the gap between writing solitary functions
(or
even small modules) and writing a large-scale project was too large. The
students found it difficult to perform tasks such as planning,
decomposition,
and integration by themselves. Intensive and close guidance on the
teacher's
part was needed; therefore the experience of independent team and
personal work
was partially lost.
To overcome that gap, a well-structured, carefully
planned set of tasks was incorporated into the course from its early
stages.
This set focused on preparing the students for the final project.
According to
the current course plan, a major part of the course is devoted to a
series of
programming tasks whose complexity gradually rises. These tasks enable
students
to practice repeatedly the stages of software development and acquire an
understanding of important principles, skills, and work habits.
For example, already after 12-15 study hours, a
relatively complex task such as the following is introduced.
In a Tic-Tac-Toe game board there are 3 rows and 3
columns. Each square contains one of the following three signs: the
first
player's sign (X), the second player's sign (O) and the sign of an empty
square. A "winning board" in the game is the board in which 3
consecutive
squares (in a row, a column or a diagonal line) contain an X or 3
consecutive
squares contain an O. Write a function that gets as a parameter a
Tic-Tac-Toe
game board and returns 'true' if it is a "winning board" and
'false'
otherwise.
This task raises, at this relatively early stage, several
issues in software design. One of the issues is comparing different ways
for
dividing the task into sub-tasks while emphasizing the writing of
general
functions. For example, checking the board for a "winning
threesome"
can be done with eight functions (for the three rows, three columns and
two
diagonals). Or, alternatively, with three generalized functions: for the
rows,
for the columns and for the diagonals, and so on.
Another issue is the comparison between different
representations of the game board: a transformation of the matrix to a
linear
list of nine items, or a list with three sub-lists representing the
three rows
on the board, or a list of nine sub-lists each composed of row, column
and a
sign. In order to realize the representation effect on the ease of the
operations' implementations, students are asked to implement, using
those
representations several functions, such as updating the value of a
square in
the board, or checking whether a square is empty, and weighing
considerations
regarding which representation is preferred.
After learning conditionals and recursion, gradually more
advanced tasks are presented. Each task both practices various stages in
software design and adds a new element related to development of a game.
For
example, simulation of a lottery drawing (with no repetition) applies
working
with random numbers. Simple games like Hangman and other guessing games
put
writing interactive programs into practice. The card game of
"War"
between two players shows mutual recursion and players' taking
turns.
5 Summary
Since basic tools of the DrScheme environment can be
acquired in a relatively short time, more attention is given to basic
principles of computer science and of software design and development. A
course
such as the one described in this paper contributes to beginning
students on
several levels:
- Early exposure and significant experience in the
development process of complex programs.
- Building a complete product, a program that can be
played with, from scratch.
- Experiencing and comprehending recursion.
Beyond the contributions in the context of programming,
the developments of interesting and useful programs produce great
enthusiasm
among the students. Students' motivation and enjoyment are evident
through the
highly creative and original software they develop. Our experience shows
that
developing a project constitutes an attractive and challenging framework
for
strong students who choose to expand beyond the course requirements and
integrate additional graphic functions into their programs. Moreover,
teachers
report of students being better prepared for the more advanced CS
courses.
6 References
Abelson, H., Sussman, G.J. & Sussman, J. (1996). Structure
and Interpretation of Computer Programs. Second Edition. MIT Press,
Cambridge,
Massachusetts, London, England.
Felleisen, M., Findler, R.B., Flatt, M. &
Krishnamuethi, S. (2001). How to Design Programs. An Introduction to
Computing
and Programming. Cambridge, Massachusetts: The MIT Press. Available:
http://www.htdp.org/2001-01-18/Book/
Gal-Ezer, J., Beeri, C., Harel, D. & Yehudai, A.
(1995). A high school program in computer science. IEEE Computer. 28
(10),
73-80.
Leron, U. (1987). Abstraction barriers in mathematics and
computer science. In J. Hillel (Ed.). Proceedings of the Third
International
Conference for Logo and Mathematics Education. Montreal: Concordia
University.
Leron, U. (1988). What makes recursion hard?. Proceeding
of the Sixth International Congress of Mathematics Education (ICME6).
Budapest
(Hungary).
Leron, U., Lapidot, T., Levy, D. & Paz, T. (1999).
Functional Programming, Additional Programming Paradigm. Workbook 1-2
for
Students and a Teachers' Guide. Technion—Israel Institute of Technology.
(in
Hebrew).
Mann, L.M., Linn, M.C. & Clancy, M.J. (1994). Can
tracing tools contribute to programming proficiency? the LISP evaluation
modeler. Interactive Learning Environments. Vol. 4, No. 1, pp.
96-113.
Paz, T. (2003). Natural Thinking vs. Formal Thinking: The
Case of Functional Programming. Unpublished PhD thesis, Technion—Israel
Institute of Technology (in Hebrew).
Pressman, R.S. (2001). Software Engineering: a
practitioner's approach. 5th Edition. Boston: McGraw-Hill.
Segal, J. (1995). Empirical studies of functional
programming learners evaluating recursive functions. Instructional
Science.
Vol. 22, pp. 385-411.
Wirth, N. (1971). Program development by stepwise refinement.
Communications
of the ACM. Vol. 14, No. 4, pp. 221-227. Available: http://www.acm.org/classics/dec95/
Contact:
Tamar Paz
Department of Education in Technology and Science
Technion, Israel Institute of Technology, Haifa 32000
Israel
tamarp@tx.technion.ac.il
Orna Muller
Computer Science Group, Science Education Department
School of Education
Tel-Aviv University, Israel
ornamu@post.tau.ac.il
1 The DrScheme environment can be downloaded at the
following Web site: http://download.plt-scheme.org/drscheme/
2 An atom is a number, a string, a symbol, or a Boolean
value.
A list is an ordered set of elements consisting of atoms or other
lists.
3 The DrScheme environment allows direct assignment, as
in the following expression (set! colors '(red blue white yellow))
|
