Transcript Week2.1

CMP 131
Introduction to Computer
Programming
Violetta Cavalli-Sforza
Week 2, Lecture 1
The trouble with being punctual is
that nobody's there to appreciate it
Franklin P. Jones
Homework #1
Due Thursday March 8
• Textbook pg. 25 (Exercises 1.3)
–
–
–
–
–
–
–
Exercise 1
Exercise 2a and 2b (not 2c)
Choose two of Exercise 3a – 3d (not 3e)
Exercise 4 for one of what you did for Exercise 3
Exercise 5a
Exercise 9 (state any assumptions you make)
Exercise 10a
• Turn in at the beginning of class (lab)
Brief Review of Last Week
• Logistics:
– folder mechanism is in place for exchanging information
– Stuff is up on my web page:
http://www.cs.cmu.edu/~violetta/
• Hardware and software trends
• Hardware components
• Hardware/Software interface
– Layers of the Machine
– Kinds of Software
• Computer Languages
• Syntax, Semantics, Grammars
• What happens to your program?
– Compilation, Linking, Execution
– Program errors
• Compilation vs. Interpretation etc.
Outline
• Programming Languages – a typology and
a brief history
• Software Development process
• Software Engineering steps
• Homework assignment
• Ideas from students (thank you …)
• Some case studies (or next time)
What is a Computer
Programming Language?
• A special purpose and limited language
• A set of rules and symbols used to construct a
computer program
• A language used to interact with the computer
• Capable of expressing any computer program
– Equivalent to a universal Turing machine
– All PLs are equivalent in this sense
Differences among PLs
• Not theoretical but practical:
– How easily do they allow you to perform
your task
• The Sapir-Whorf hypothesis:
– “the structure of language defines the
boundaries of thought”
– The wrong language prevents certain tasks
from being accomplished?
– Maybe not, but can certainly impede
progress.
Different Ways of Categorizing
PLs
• By closeness/remoteness from the
machine/human/application:
– machine, assembly, high-level
• By application type
• By computational model
Machine Languages
•
•
•
•
•
“Natural language” of a particular computer
Defined by hardware design of computer
Generally consists of strings of numbers
Are machine dependent
Cumbersome for humans
– Example: Adding overtime pay to base pay and
storing the result in gross pay
+1300042774
+1400593419
+1200274027
• Slow and tedious for most programmers
Assembly Languages
• Programmers began using English-like
abbreviations to substitute for machine
languages
• Represents elementary operations of computer
• Translator programs called assemblers convert
assembly-language to machine-language
• Example:
LOAD BASEPAY
ADD OVERPAY
STORE GROSSPAY
High-Level Languages
• Single statements can be written to
accomplish substantial tasks
• Allow programmers to write instructions
almost like every-day English (preferable!)
• Example:
grossPay = basePay + overTimePay
• Developed as computer usage increased,
assembly language proved inadequate and
time-consuming
• Evolved hand-in hand with hardware and
applications
PL Application Types
•
•
•
•
•
•
Numeric/scientific languages (FORTRAN)
Business languages (COBOL)
Artificial Intelligence languages (Lisp, Prolog)
Systems languages (C and its ancestors)
Multi-purpose languages (.., Ada, Java, C++)
Process/Scripting languages: view programs
and files as primary data objexts to be
manipulated (e.g. Perl, JCL, shell scripting
languages)
• Publishing/Document Description Languages
(e.g. Scribe, TeX, SGML, HTML, XML)
• Other special purpose: APL, Snobol, BASIC,
Visual BASIC, …
Computational Model Types
• A PL supports one or more computational
models
• Computational models include
–
–
–
–
Imperative
Functional or Applicative
Rule-Based or Logical
Object-Oriented
Imperative PLs
• Command-driven, statement-oriented
• Data is modified by statement
execution
• Efficient
• Structured programming: Pascal
• Modular: Modula and successors
Functional or Applicative PLs
• What is the function that must be applied to the
initial machine state to provide the desired
result?
• Function composition
– F (G (H (x)))
– Average = divide ( sum (data), number (data) )
• No global data (in the extreme)
• Example:
– Lisp (used in Artificial Intelligence)
Rule-Based or Logical PLs
• Rule-Based:
– Execute an action if enabling conditions are satisfied
– Logical-programming (Prolog)
• Declarative programming: say what you know and what you want to
know
– Connection to expert systems in artificial intelligence
• E.g. medical diagnosis, financial advisors
– Example:
• Rules:
likes(john,X) :- likes(X,food).
may_steal(X,Y) :- thief(X),likes(X,Y).
• Facts:
thief(john).
likes(mary, food).
• Conclusion?
likes(john,mary)
may_steal(john,mary)
Object-Oriented PLs
• Attempt to merge the best of
– imperative (efficiency)
– functional (flexibility and reliability)
• Ideas:
• Data is encapsulated in objects
• Actions happen by sending message to objects
• E.g. send a message to a window to tell it to turn its
background red
• SmallTalk was the first OO language (Xerox PARC)
• Examples:
– Ada, C++, Java
Evolution of Imperative PLs
FORTRAN IV (1950’s)
COBOL (1960’s)
PL/1 (1970’s)
Algol (1960’s)
Simula 67
Pascal (1970’s)
B (1969-70)
Smalltalk
(1970s-80’s)
Ada 83
Modula (1980’s)
Java (1990’s)
Ada 95
(B)CPL (1960’s)
C (1971-73)
C++ (1990’s)
Factors Affecting PL Evolution
•
•
•
•
•
•
•
Applications
Hardware/Software trends
Programming environments
Language Standardization
Internationalization
Theoretical studies
Economics
Hardware Trends
• Every year or two computer power
approximately doubles
– Memory size (RAM)
• Memory used to execute programs
– Secondary storage (permanent storage)
• E.g. disk storage, used to to hold programs and
data over time
– Processor speeds
• Speed at which computers execute their programs
Hardware/Software Trends
• Applications:
– Rapidly increasing hardware power allows
applications to get bigger and more complex
• Costs
– Hardware costs dropping
– Software development costs rising
• Software development complexity
• Programmer salaries
• Cost of slipping schedules
– Unanticipated interactions in complex systems
– Unpredictability of software development times
The PL Design Response
STRUCTURED PROGRAMMING
• Disciplined approach to writing computer
programs
• Control structures reflect the logic of the
program
– Eliminate/reduce use of GOTO instructions
(spaghetti code)
• Data structures reflect the types of data
processed by the application
• Clearer and easier to debug and modify than
unstructured programs
“MODULAR” PROGRAMMING
•
•
•
•
Large software system
Multiple users
Reusable components
Divide program into modules (packages),
each with
– An interface, visible to the user of the module
– An implementation or body, visible to
programmer of module
• Isolates users of modules from
implementation changes.
OBJECT-ORIENTED PROGRAMMING
• Objects : Reusable software components that
model items in the real world
– Created from class descriptors
– Inherit and modify class descriptions
• OOP makes software developers more productive
– Object-oriented programs often easier to understand,
correct and modify than older types of programs
• Currently the main programming language
paradigm
– But it is built on the imperative programming model such
as contained in Pascal
Our Language
• Pascal
– High-level, general-purpose programming language
– Developed in 1971 by N. Wirth of ETH at Zurich, Switzerland
– Popular programming language for teaching programming
concepts
– Easy-to-learn syntax
– Allows writing structured programs that are easy to read and
understand
– Robust against programmer’s errors
• Turbo Pascal
– A dialect of Pascal developed by Borland International
– The IDE shows its age…
The Software Development
Process
SW Development Process
• Software Lifecycle (from Online dictionary)
– The phases a software product goes through between when it is
conceived and when it is no longer available for use. The software
life-cycle typically includes the following:
•
•
•
•
•
•
•
•
Requirements analysis
Design
Construction (implementation)
Testing (validation)
Installation
Operation
Maintenance
Retirement
•
•
•
•
Quality assurance
Marketing
Sales
Support.
– The development process might need to iterate through these
phases rather than linearly;
– Other processes associated with a software product are:
SW Design as Problem Solving
• Formulate a solution as an algorithm
– Design solution alternatives
• Data representation
• Computational procedures
– Evaluate and select solution
• Several criteria and methods (next slide)
– Implement solution
• State solution in Programming Language
• Sometimes need to prototype before selecting
design
Evaluating a SW Solution
• Correctness
– mathematical verification techniques
– testing
• Efficiency
– mathematical complexity calculations
– informal and empirical evaluations
• Style
– elegance
– clearness
– conciseness
• Reusability
– generality
– modularity
SW Development Method
• Software Engineering (SE): (from Online dictionary)
– Systematic approach to the analysis, design, implementation and
maintenance of software.
– Often involves the use of “Computer Aided Software Engineering”
(CASE) tools.
– Various models of the software life-cycle, and many methodologies for
the different phases exist.
• Computer Aided Software Engineering (CASE):
– A technique for using computers to help with one or more phases of
the software life-cycle. It involves software tools and training for the
developers who will use them.
• Top-Down Design (Or “Stepwise Refinement"):
– Software design technique that describes functionality at a very high
level, then partition it repeatedly into more detailed levels one level at a
time until the detail is sufficient to allow coding
SW Development Method
• Structured language:
– A programming language in which a program could be broken
down into modules (procedures or functions) that could be
written without detailed knowledge of the inner workings of
other modules. This allows implementing the top-down design
approach.
• Structured programming:
– Any software development technique that includes structured
design and results in the development of a structured
program.
– Resulting programs are easy to maintain, read, and
understand.
• We will consider the following “SW-Engineering Steps”
to solve Pascal’s programming problems:
1. Problem statement
Language
2. Analysis
independent
3. Design
4. Implementation
Language
5. Testing & verification
dependent
6. Maintenance
AND DOCUMENT THROUGHOUT!!!
SW-Engineering Steps:
Problem Statement
• Clearly state the problem in English.
• Gain a clear understanding of what is required for
its solution.
– Become an expert in the domain
– Interact a lot with experts/clients
– The “Knowledge Engineer” figure in Artificial
Intelligence
• Try to eliminate unimportant aspects to the main
problem.
• If the problem is not totally defined, request more
information.
SW-Engineering Steps: Analysis
• Underline relevant phrases in the problem
statement
• Develop a list of problem variables & their
relationships
• Identify the problem input variables
• Identify the desired output variables
• Identify local or temporary variables
• Determine type & units for the variables
• Determine how should the output be displayed
• Determine relevant formulas needed to transform
input into output
• Identify any additional requirements or
constraints
SW-Engineering Steps: I/O Variables
• Input Variables:
– Found in the problem statement
– Describes input data supplied to the problem from outside
– Look for key words:
• Accepts, reads, prompts, input
– Example:
Read value into Fahrenheit temperature
• Output Variables:
– Found in the problem statement
– Describes information computed & displayed to user after
processing
– Look for key words:
• Writes, prints, displays, output
– Example:
Print “Case Study 1” on the screen
SW-Engineering Steps: Design
• The most difficult part in the problem-solving process.
• Develop a list of steps (Algorithm) to solve the problem,
using pseudocode, flowcharts, or
IPO (Input/Process/Output chart) charts
• Test if the algorithm will solve the problem as intended by
using sample input and checking the output.
• Top-Down design should be used.
• Pseudocode:
–
–
–
–
English-like statements
Describes steps of an algorithm in the “Design” phase
Not a programming language
Example
Repeat for N = 1 to 10
Calculate N Squared
Calculate N Cubed
Print N, Squared, Cubed
SW-Engineering Steps: Design
• IPO (Input-Processing-Output) model
– Input Requirements (declaration & action)
– Processing Requirements (action)
– Output Requirements (declaration & action)
• Input & output declarations are covered by the analysis phase
• I/O and processing actions are covered by the design phase
by writing an algorithm
– Write pseudocode for input
– Write pseudocode for processing
– Write pseudocode for output
• Processing Requirements
– Explains how is input transformed into output
– Might need to use intermediate evaluation steps
– Look for key words:
• Calculate, convert, compare, count, evaluate, etc.
– Example:
Count the total number of characters
Calculate squares and cubes for 1 through 10
Example on Board
• Problem: Counting characters in a string
• Input from terminal a word (character string)
• Output to terminal how many characters it
contains
• Process (high-level):
– Read one character at a time
– Add one to the count for each character read
– Repeat the above 2 steps until there are no
more characters
• Process (refinement):
Initialize Count to 0
REPEAT:
Read one character at a time
If a character is found, add 1 to Count
UNTIL there are no more characters
SW-Engineering Steps
• Implementation:
– Implement the algorithm as a program using a particular
programming language by converting each step in the algorithm
into statements in the programming language.
– Document the implementation all along…
• Testing & Verification:
– Desk-check the solution steps
– Test the completed program by running it several times using
several test data sets.
– Use sample test data that covers
• Correct possibilities
• Incorrect possibilities
– Repeat any of the steps if error is detected
• Maintenance:
– Modify the program
• Remove previously undetected errors
• Add new features
• Change the program according to company or government policy
changes.