Transcript Chapter 4: Computer Languages, Algorithms and Program

Chapter 4
Computer Languages,
Algorithms and Program
Development
Berlin Chen 2003
Textbooks: 1. Kurt F. Lauckner and Mildred D. Lintner, "The Computer Continuum,"
Prentice Hall, Second Edition, 2001.
How do computers know
what
we want them to do?
2
Outline
• What makes up a language and how do we use
language to communicate with each other and with
computers?
• How did computer programming languages evolve?
• How do computers understand what we are telling
them to do?
• What are the steps involved in building a program?
• How can we create something that would be visible
on the WWW?
3
What is Software
• Software is a set of electronic instructions that
tells the computer how to do certain tasks. A set
of instructions is often called a program
• When a computer is using a particular program,
it is said to be running or executing the program
• The two most common types of programs are
system software and application software
4
What is Software
Written by different Computer Languages
5
What is Software
• System Software
– System software exists primarily for the computer
itself, to help the computer perform specific functions
– One major type of system software is the operating
system (OS). All computers require an operating
system
– The OS tells the computer how to interact with the
user and its own devices
– Common operating systems include Windows, the
Macintosh OS, OS/2, and UNIX
6
What is Software
• Application Software
– Application software tells the computer how to
accomplish tasks the user requires, such as creating
a document or editing a graphic image.
– Some important kinds of application software are:
Word processing programs
Database management
Graphics programs
Web design tools and browsers
Communications programs
Entertainment and education
Spreadsheet software
Presentation programs
Networking software
Internet applications
Utilities
Multimedia authoring
7
Communicating with People
• Communication cycle
– One complete unit of communication
•
•
•
•
•
•
•
An idea to be sent (plan how to say)
An encoder (figure out how to phrase it clearly)
A sender (say it)
Speaker encodes
Listener decodes
A medium (through air)
information
information
A receiver (with ears)
A decoder (in the brain)
A response
Listener returns
feedback to speaker
8
Communicating with People
Speech Generation
Message Formulation
Language System
Neuromuscular Mapping
Speech Understanding
Application
Semantics,
Actions
Phone, Word,
Prosody
Feature
Extraction
Message Comprehension
Language System
Neural Transduction
Articulatory
Parameter
Vocal Tract System
Cochlea Motion
Speech Generation
Speech Analysis
9
Communicating with a Computer
• Substituting a
computer for one of
the people in the
communication
process
– Process is basically
the same
User encodes
information
Computer decodes
information
Computer
returns results
to user
• Response may be
printouts or symbols
on the monitor
10
Communicating with a Computer
Communication process is prone to failure:
A breakdown can occur any place along the cycle...
• Between two people:
• Between a person
– The person can’t hear you
and a computer:
– The phone connection is
broken in mid-call
– One person speaks only
French, while the other only
Japanese
– The power was suddenly
interrupted
– An internal wire became
disconnected
– A keyboard malfunctioned
Computer hardware is
susceptible to failure
When communicating instructions to a computer, areas
of difficulty are often part of the encoding and decoding
process.
11
Communicating with a Computer
How can we transcribe our human thoughts, usually
expressed as words into computer “thoughts”,
usually expressed as binary numbers.
12
Communicating with a Computer
• Programming languages bridge the gap
between human thought processes and
computer binary circuitry
– Communicates data manipulation instructions, such
as read, add, store, print
– Programming language: A series of specifically
defined commands designed by human programmers
to give directions to digital computers
• Commands are written as sets of instructions, called
programs
• All programming language instructions must be expressed in
binary code before the computer can perform them
13
The Role of Languages
in Communication
• Three fundamental elements of language
that contribute to the success or failure of
the communication cycle:
– Semantics 語意
語法
– Syntax
– Participants 參與者
Many subtle differences can be seen
when compare programming languages
with human languages
14
The Role of Languages
in Communication
• Semantics: Refers to meaning.
• Human language:
• Computer language:
– Refers to the meaning of
what is being said
– Words often pick up
multiple meanings.
– Phrases sometimes have
idiomatic meanings, e.g.:
• Let sleeping dogs lie
• Catch the green line and
visit the MFA
Give a language it’s meaning by associating
each language unit “word” with a particular
object or experience, e.g., “tree”
– Refers to the specific
command you wish the
computer to perform
• Imperative !
• Input, Output, Print
• Each command has a very
specific meaning.
• Computers associate one
meaning with one
computer command
– E.g. “SUB” in COBOL
15
The Role of Languages
in Communication
• Semantics (cont.)
– Computer can associate only one meaning with one
computer command
– Whereas people can evaluate context (上下前後文) to
determine which of several meaning a particular word
has
– Computers know not thing about context
• Each command must has a specific meaning
regardless of context
• Computers can’t associate idiomatic meanings with
expressions
16
The Role of Languages
in Communication
• Syntax: Refers to form, or structure
• Human language:
• Computer language:
– Refers to rules governing
grammatical structure
• Pluralization, tense,
agreement of subject and
verb, pronunciation, and
gender
– Humans tolerate the use
of language
• How many ways can you
say no? Do they have the
same meaning?
– Refers to rules
governing exact
spelling and
punctuation, plus:
• Formatting, repetition,
subdivision of tasks,
identification of variables,
definition of memory
spaces
– Computers do not
tolerate syntax errors
Rule governing exacting spelling and punctuation exist in both.
17
The Role of Languages
in Communication
• Participants:
– Human languages are used by people to
communicate with each other.
– Programming languages are used by people to
communicate with machines.
• Human language:
• Computer language:
– In the communication cycle,
humans can respond in more
than one way
• Body language/Gestures
• Facial expressions
• Laughter
• human speech
A successful communication only lies on you !
– Computer never uses
anything but binary code “0”, “1”
– People use programming
languages
– Programs must be translated
into binary code
– Computers respond by
performing the task or not! 18
The Role of Languages
in Communication
• Participants (cont.)
– Human communications
19
The Programming
Language Continuum
• In the Beginning...Early computers consisted of
special-purpose computing hardware.
– Each computer was designed to perform a particular
arithmetic task or set of tasks
– Skilled engineers had to manipulate parts of the
computer’s hardware directly
• Some computers required “fat-fingering”.
– Fat-fingering: Engineer needed to position electrical
relay switches manually (in either off or on position)
• Others required programs to be hardwired
– Hardwiring: Using solder to create circuit boards with
connections needed to perform a specific task
20
The Programming
Language Continuum
Invented by Leibniz, 1674
21
The Programming
Language Continuum
• ENIAC
– Used programs to complete
a number of different
mathematical tasks
• Programs were entered by
plugging connector cables
directly into sockets on a
plug-in board
– Set-up could take hours
– A program would
generally be used for
weeks at a time
– Intricate and error-prone
Invented by U. Penn. , 1944
22
The Programming
Language Continuum
• In the beginning… To use a computer, you
needed to know how to program it
• Today… People no longer need to know how to
program in order to use the computer
• To see how this was accomplished, lets
investigate how programming languages evolved
–
–
–
–
–
First Generation - Machine Language (code)
Second Generation - Assembly Language
Third Generation - People-Oriented Programming Languages
Fourth Generation - Non-Procedural Languages
Fifth Generation - Natural Languages
23
The Programming
Language Continuum
• First Generation - Machine Language (code)
– Machine language programs were made up of
instructions written in binary code
• This is the “native” language of the computer.
• Each instruction had two parts: Operation code, Operand
– Operation code (Opcode): The command part of a
computer instruction
» Specifies the action to be carried out
– Operand (運算元): The address of a specific location in the
computer’s memory.
• Hardware dependent: Could be performed by only one type of
computer with a particular CPU (a low-level language)
– Unintelligent (difficult to decipher) and error-prone
24
The Programming
Language Continuum
• First Generation - Machine Language (code)
Low-level or hardware-dependent languages:
computer languages that could be performed by only
one type of computer with a particular CPU
Table 4.3.1
25
The Programming
Language Continuum
• Second Generation - Assembly Language
– Assembly language programs are made up of
instructions written in mnemonics
READ
READ
LOAD
ADD
STORE
PRINT
STOP
num1
num2
num1
num2
sum
sum
Mnemonic Opcode
Symbolic Operands
– Mnemonics: Uses convenient alphabetic
abbreviations to represent operation codes, and
abstract symbols to represent operands.
– Each instruction had two parts: Operation code,
Operand
– Hardware dependent
– Because programs are not written in 1s and 0s,
the computer must first translate the program
before it can be executed
• Intelligent and less error-prone
26
The Programming
Language Continuum
• Third Generation - People-Oriented Programs
– Instructions in these languages are called
statements
– High-level languages: Use statements that
resemble English phrases combined with
mathematical terms needed to express the
problem or task being programmed
27
The Programming
Language Continuum
• Third Generation - People-Oriented Programs
– Transportable: NOT-Hardware dependent.
• The syntax and semantics of such statements do not reflect
the internal machine code or instruction set of any particular
computer
– Because programs are not written in 1s and
0s, the computer must first translate the
program (using a compiler (編譯器) or
interpreter (直譯器) ) before it can be
executed.
28
The Programming
Language Continuum
• Third Generation - People-Oriented Programs
– Pascal Example: Read in two numbers, add
them, and print them out.
Program sum2(input,output);
var
num1,num2,sum : integer;
begin
read(num1,num2);
sum:=num1+num2;
writeln(sum)
end.
29
The Programming
Language Continuum
• Fourth Generation - Non-Procedural Languages
– Programming-like systems aimed at simplifying the
programmers task of imparting instructions to a
computer
– Many are associated with specific application
packages (套裝軟體)
• Query Languages:
• Report Writers
• Application Generators
30
The Programming
Language Continuum
• Fourth Generation - Non-Procedural Languages
– Query Languages
• Enables a person to specify exactly what information they
require from the database
• Usually embedded within database management programs
– Report Writers
• Takes information retrieved from databases and formats into
attractive, usable output
– Application Generators
• A person can specify a problem, and describe the desired
results
• Included with many micro-computer programs (macros)
31
The Programming
Language Continuum
• Fourth Generation - Non-Procedural Languages
– Object-Oriented Languages
• A language that expresses a computer problem as a
series of objects a system contains, the behaviors of
those objects, and how the objects interact with
each other
• Object: Any entity contained within a system
– Examples:
» A window on your screen
» A list of names you wish to organize
» An entity that is made up of individual parts
• Some popular examples: C++, Java, etc
32
The Programming
Language Continuum
• Fourth Generation - Non-Procedural Languages
– More about “objects” in programming languages
• You can think an object as a black box, like a VCR
with some buttons and lights on it surface
• To use the VCR, you must know what the buttons do
– Buttons for the function while lights for the status
• The inside construction of the object is irrelevant
when you are using it
– You don’t need to know what the wiring is like
inside a VCR to use one
33
The Programming
Language Continuum
• Fifth Generation - Natural Languages
– Natural-Language: Languages that use ordinary
conversation in one’s own language
• Research and experimentation toward this goal
is being done
• Intelligent compilers are now being developed to
translate natural language (spoken) programs
into structured machine-coded instructions that
can be executed by computers
34
The Programming
Language Continuum
• Fifth Generation - Natural Languages
– So far, we are a long way from speaking any but the
most trivial programs directly into the computer
– Effortless, error-free natural language programs are
still some distance into the future
35
The Programming
Language Continuum
36
Assembled, Compiled, or Interpreted
Languages
• Except for those written in machine code, all
programs must be translated (to the computer’s
native language in machine code) before their
instructions can be executed
• Computer languages can be grouped according
to which translation process is used to convert the
instructions into binary code
– Assemblers
– Interpreters
– Compilers
37
Assembled, Compiled, or Interpreted
Languages
• Assembled languages
– Assembler (組譯器): a program used to translate
assembly language programs
– Produces one line of binary code per original
program statement
• The entire program is assembled before the
program is sent to the computer for execution
38
Assembled, Compiled, or Interpreted
Languages
• Interpreted Languages
– Interpreter (直譯器): A program used to translate highlevel programs
– Translates one line of the program into binary code
(several lines of object codes) at a time:
• An instruction is fetched from the original source code.
• The Interpreter checks the single instruction for errors. (If an
error is found, translation and execution ceases. Otherwise…)
• The instruction is translated into binary code.
• The binary coded instruction is executed (then discarded).
• The fetch and execute process repeats for the entire program.
The program must be reinterpreted each and every time
it’s run. It’s a slow process but helpful for locating errors
39
Assembled, Compiled, or Interpreted
Languages
• Compiled languages:
– Compiler (編譯器): a program used to translate highlevel programs
– Reads and translates the entire program into binary
code before anything is sent to the CPU for execution
• The translation process for a compiled program:
– First, the Compiler checks the entire program for syntax
errors in the original source code.
– Next, it translates all of the instructions into binary code.
» Produces several lines of object code for each
statement
» Two versions of the same program exist: the original
A global
source code version, and the binary code version
optimization
(object code).
cab be achieved
– Last, the CPU attempts execution only after the
programmer requests that the program be executed.
40
Assembled, Compiled, or Interpreted
Languages
41
Programming for Everyone
• Several ways to control what your computer does
or the way it accomplishes a particular task
– Using Macros (巨集)
– Using HTML (HyperText Markup Language): to create
Web Pages
– Using Scripts (描述語言、腳本)
• Each allows customization of current applications
42
Programming for Everyone
• Using Macros
– Macro: Set of operations within the computer
application that have been recorded for later execution
• Once recorded, the macro can be used repeatedly
on any document within that application.
• In spreadsheet programs and word processors,
macros are commonly used to speed up repetitive
tasks.
– Example: SIG can be stored as a macro that
includes a signature message at the end of a
document/letters
James R. Emmelsohn
Director of Public Relations
Martin Electronics, Detroit
43 D
Programming for Everyone
• Using HTML to create Web Pages
– HTML: A computer language consisting of special
codes intended to design the layout (or markup) of a
Web page. HTML is a formatting language
• Web browsers interpret the HTML code and
display the resulting Web pages
• Web browser: A program that displays information
from the WWW
• HTML is formatted by tags
– The tag language specifies the design and layout of Web
pages
– Each tag is delineated by angle brackets before and after
to set the tag apart as complete
44
Programming for Everyone
45
Programming for Everyone
<HTML>
<HEAD>
<TITLE> Title of Web Page </TITLE>
</HEAD>
<BODY bgcolor=#ffffff text=#000000 >
<BODY>
<H1>
<CENTER> Sample Web Page
</CENTER> </H1>
<HR>
<A HREF=“http://www.dogpile.com”>
dogpile search engine </A>
</BODY>
</HTML>
•
•
•
•
•
•
•
•
•
•
•
•
Designates an HTML document
Beginning of Header section
Contents of Title bar
End of Header section
Background=white, text=black
Top of the body of the document
H1=largest text size, H6 is
smallest
CENTER turns on centering
Turns off centering and large text
Displays a horizontal rule: thin
line
Links to the dogpile search
engine
</BODY> and
</HTML>designate the bottom of
the document
46
Programming for Everyone
• Scripting
– A means by which programmers add extensions or
additional capabilities to an application.
– A series of commands, written to accomplish some
task
• Very similar to the concept of a program.
• Extends the capabilities of the application where it
is being used.
• Examples of scripting languages:
– Perl, C++, VBScript, JavaScript
– JavaScript: A scripting language that allows the Web
page designer to add functional features to a formatted
web page created in HTML.
» JavaScript is not derived from Java, is only related to
Java in name only
47
Building a Program
• Whatever type of problem needs to be solved, a
careful thought out plan of attack, called an
algorithm, is needed before a computer solution
can be determined
– Mathematical problems, accessing information
– Analyze problems and devise plans for their solutions
• Building a program requires for major steps
1) Developing the algorithm
2) Writing the program
3) Documenting the program
4) Testing and debugging the program
48
Building a Program
• 1) Developing the algorithm
– Algorithm: A detailed description of the exact
methods used for solving a particular problem.
– To develop the algorithm, the programmer must first
analyze which data users need by asking
• What data has to be fed into the computer?
• What information do I want to get out of the computer?
– Logic: Planning the processing of the program. It
contains the instructions (or processing part) that
cause the input data to be turned into the desired
output data
49
Building a Program
• The word “algorithm” is derived from the name
of the Persian mathematician Mohammed alKowậrisimi, who lived during the ninth century
and who is credited with developing the step-bystep rules for the addition, subtraction,
multiplication, and division of ordinary decimal
numbers. When his name was written in Latin it
became Algorismus, from which algorithm is
derived
50
Building a Program
• A step-by-step program plan is created during
the planning stage.
• The three major notations for planning detailed
algorithms are used by programmers
– Flowchart: Series of visual symbols representing the
logical flow of a program
– Pseudocode: A verbal shorthand method that closely
resembles a programming language, but does not
have to follow a rigid syntax structure
51
Building a Program
• A example program “lass-list”
The diamond sharp for
a decision statement
52
Building a Program
• 2) Writing the Program
– If analysis and planning have been thoroughly done,
translating the plan into a programming language
should be a quick and easy task.
• 3) Documenting the Program
– During both the algorithm development and program
writing stages, explanations called documentation
are added to the code.
• Helps users as well as programmers understand the exact
processes to be performed.
53
Building a Program
• A example program “lass-list” (cont.)
54
Building a Program
• 4) Testing and Debugging the Program
– The program must be free of syntax errors.
– The program must be free of logic errors (semantic
errors).
– The program must be reliable. (produces correct
results)
– The program must be robust. (able to detect
execution errors)
Logic errors are more difficult to detect than
syntax errors and are harder to correct.
55
Building a Program
• Testing and Debugging the Program
– Alpha testing: Testing within the company.
– Beta testing: Testing under a wider set of conditions
using “sophisticated” users from outside the company.
56
Software Development:
A Broader View
Measures of effort spent on real-life programs:
• Comparing programs by size
Type of program
Number of Lines
The compiler for a language with a
limited instruction set.
Tens of thousands of lines
A full-featured word processor.
lines
Hundreds of thousands of
A microcomputer operating system. Approximately 2,000,000
lines
A military weapon management program.
(controlling missiles, for example) Several million lines
57
Software Development:
A Broader View
Measures of effort spent on real-life programs:
• Comparing programs by time
– Commercial software is seldom written by individuals
• Person-months - equivalent to one person
working 40 hours (eight hours per workday) a week
for four weeks.
• Person-years - equivalent to one person working
for twelve months.
• Team of 5 people working for 8 weeks = ten
person-months.
5*40*8/(40*4)=10
58
Web Page Design Software:
Dreamweaver
• What is Web page design software?
– The programs that help create pages and their
associated HTML
– Dreamweaver: A visual Web page editor primarily for
use by Web design professionals
• Created by Macromedia
• Why is it needed?
– Allows creation of Web pages without
knowledge of HTML
• Without the pain of programming. It’s clumsy to design pages
in HTMLs
• Concentrate on the creative aspects of Web page design
59
Web Page Design Software:
Dreamweaver
• What minimal functions must the programs for
creating Web pages have?
– WYSIWIG: “What you see is what you get.”
• Web page designers see exactly what it will look like.
– Allows selection of color scheme (Background and
text)
– Allows text manipulation (Typing text where you want
it, changing the size, color or style)
– Allows importation and layout of images
60
Web Page Design Software:
Dreamweaver
• What types of support are available to enhance
its use?
– Applets extend the capabilities of HTML
• Applet: A short application program, usually written in Java,
which adds enhancement and/or functionality to a Web page.
• Is special support hardware available?
– Creating audio/visual materials for the WWW
• Photo digitizers or scanners, video digitizer, and audio
digitizer.
• Once these are in a standard digital format, they can be
imported to Web development programs.
61
Web Page Design Software:
Dreamweaver
• One final note
– Dreamweaver and other Web page design software
create Web pages. You still need a place to keep your
Web page
• ISP (Internet Service Provider): A company or
organization that is used as an access point to the
WWW
– The ISP will put your Web page on its server.
– You will be given an address where you or others can
access your Web page.
– XML (Extensible Markup Language): for more
complex data and processes of Web pages
62
Chapter Summary
• Communicating with a Computer
– Binary circuitry in computer vs. symbolic thought
processes of the human mind
– Programming devised to bridge the gap between the
user and the computer
• The Role of Languages in Communication
– Major difference between human languages and
computer languages: semantics, syntax, participants
– The syntax of computer instructions are expressed in
narrowly defined patterns
63
Chapter Summary
• The Program Language Continuum
1. Hardware-wired programs
2. Human program a computer but require a program
translation before the computer can perform a task
3. Speaking instructions directly into the computer
• Assembled, Complied, or Interpreted Languages
– Assemblers translate programs written in assembly
(low-level) language into binary (machine) codes
– Interpreters translate and execute one instruction (of
high level language) at a time
– Compilers translate an entire program of high level
language) before execution
64