Programming and Programs

Programming and Programs
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Algorithms:
- An unambiguous process for solving a problem using a finite amount of resources
Heuristic:
- A problem solving process that is not guaranteed to be perfect/exact

Possible Audiences

People:
- Are intelligent so may not follow the instructions exactly/literally and, as a result, be more "forgiving" (e.g., Wet Hair - Apply Shampoo - Lather - Rinse - Repeat)
Computers:
- Are not intelligent, follow instructions exactly, and so are not at all forgiving

Writing for the Audience

People:
- Algorithms may be written in a natural language and can often be underspecified and/or ambiguous (though problems may sometimes arise)
Computers:
- Algorithms must be written in a language that is unambiguous and must account for every detail
- (Courtesy of Saturday Morning Breakfast Cereal)

Languages

Defined:
- A language consists of a set of words/symbols/tokens (called a lexicon), a set of rules for combining lexical items into larger constructs (called a syntax or grammar), and the meanings of those constructs (called the semantics)
Kinds:
- Natural - a language that developed through use and repetition (i.e., for the purposes of communication)
- Constructed - a language that has been planned or consciously devised

Programming Languages

Definitions:
- A programming language is a language that is or can easily (and usually automatically) be converted into machine-readable form
- An imperative programming language is a programming language that is used to record/describe algorithms and heuristics
Levels of (Imperative) Programming Languages:
- Lowest Level - Machine language contains instructions that are only readily readable by a computer
- Low Level - Assembly language replaces operations and storage locations with names and symbols making it more human-readable
- Higher Level - Readily human-readable (e.g., C, Java, Python, Ruby) but can be converted to machine instructions

Programs in Imperative Languages

Token:
- A token is the conceptually smallest element of a construct -- it is similar to a word or punctuation mark in natural language
Expressions:
- An expression is a syntactically valid construct that can be evaluated (i.e., results in a value)
Statements:
- A statement is (roughly) a smallest syntactically valid construct that conveys a complete command -- it is simlar to a sentence in a natural language
Programs:
- A program is a collection of statements to solve a particular problem in a particular imperative programming language (i.e., an algorithm/heuristic written in an imperative programming language)

A Conceptual Model of the Flow through a Program

Control Transfer:
- A transition of the processor from one statement to another
Flow of Control:
- A sequence of control transfers
Tracing:
- Manually following the flow of control through a program

A Visual Model of the Flow through a (Linear) Program

From Algorithms to Programs (in Higher Level Imperative Languages)

Comments:
- Natural language descriptions that make programs easier to understand
Modules:
- Statements that are grouped together (and called methods, functions, subroutines, subprograms, etc...) and given information in named entities (called parameters) that they use to solve a particular part of a problem
Input Module:
- A module that provides input capabilities
Memory/Recall:
- Information is stored in named entities (called variables or attributes depending on the context) which may or may not have an associated type/characteristics (e.g., integers, real numbers, characters, Booleans)

From Algorithms to Programs (cont.)

Operations:
- An operator is a symbol that represents an operation that can be performed on one (unary), two (binary), or three (ternary) operands and evaluates to a result
Conditions:
- An individual statement or a block of statements can be performed under some conditions but not others
Iteration:
- An individual statement or a block of statements can be performed repeatedly/iteratively (perhaps based on one or more conditions)
Output Module:
- A library module that provides output capabilities

Simulating a Computer

An Observation:
- Beginning programmers often forget that computers follow instructions exactly
A Useful Exercise:
- Execute some algorithms/programs written in structured English using a "simulated computer"

Simulating a Computer (cont.)

Algorithm CoursesReporter. Create an entity name courses. Store the number of courses you are taking in courses. Move your pencil to column 0. Write the value in courses. End Algorithm.

Before Starting the Programming Process

Understand the relevant features of the programming language being used
Understand the development environment being used

Steps in the Programming Process

Understand the problem domain and specific problem
Decompose the problem into parts
Solve examples of each part of the problem by hand
Understand any existing designs/components/modules
Create a detailed design of the new components/modules
For each new component/module:
1. Implement the component/module (which will consist of algorithms and data structures) in the programming language being used
2. Test the component/module
3. If necessary, debug the component/module
Test and debug the complete program
Refactor the components/modules to improve the implementation and/or generalize the components/modules (to make them applicable in a wider variety of circumstances)

About You and the Programming Process

A Big Misconception:
- Using the above process is slow
In Fact:
- It is a time-consuming process, but not a slow one (relatively)
- You will be much more productive (i.e., assignments will take less time) if you use the above process

Learning to Program/Code

Where You May Have Difficulty:
- Understanding the problem
- Solving the problem "by hand"
- Formally describing the algorithm
- Implementing the algorithm in a programming language
Overcoming These Difficulties:
- Be self-aware (i.e., know which difficulties you are having)
- Memorize terms, syntax, etc...
- Understand and use common patterns
- Try and try again (with as little assistance as possible)

There's Always More to Learn