Transcript 02little-extras - Department of Computer Science

CLASSIFICATION OF
PROGRAMMING
LANGUAGES
To facilitate discussion on any subject it is convenient to group together
similar facets of the subject according to some grouping notion.
Computer programming languages are no exception.
1. Machine, Assembler and 4. Levels of abstraction
High Level Languages
(from machine level)
2. Chronological order of 5. Declarative v Nondevelopment
declarative
3. Generations
6. Paradigms
This and following slides thanks to Grant Malcolm
MACHINE CODE
• Thus, a program running on a computer is simply a sequence of bits.
• A program in this format is said to be in machine code.
• We can write programs in machine code:
23fc 0000 0001 0000 0040
0cb9 0000 000a 0000 0040
6e0c
06b9 0000 0001 0000 0040
60e8
ASSEMBLY LANGUAGE
• Assembly language (or assembler code) was our first attempt at
producing a mechanism for writing programs that was more palatable to
ourselves.
• Of course a program
written in machine
code, in order to
“run”, must first be
translated
(assembled) into
machine code.
movl
#0x1,n
compare:
cmpl
#oxa,n
cgt
end_of_loop
acddl #0x1,n
bra
compare
end_of_loop:
HIGH LEVEL LANGUAGE
• From the foregoing we can see that assembler language is not much of
an improvement on machine code!
• A more problem-oriented (rather than machine-oriented) mechanism for
creating computer programs would also be desirable.
• Hence the advent of high(er) level languages commencing with the
introduction of “Autocodes”, and going on to Algol, Fortran, Pascal,
Basic, Ada, C, etc.
Classification of programming
languages:
1. Machine, Assembler and High Level
Languages
2. Chronological order of development
3. Generations
4. Levels of abstraction (from machine
level)
5. Declarative v Non-declarative
6. Paradigms
CHRONOLOGICAL
CLASSIFICATION OF
PROGRAMMING
LANGUAGES
1940s Prelingual phase: Machine code
1950s Exploiting machine power: Assembler code, Autocodes, first version
of Fortran
1960s Increasing expressive power: Cobol, Lisp, Algol 60, Basic, PL/1 --but most “proper” programming still done in assembly language.
•
1970s Fighting the “software crisis”:
1. Reducing machine dependency –
portability.
2. Increasing program correctness Structured Programming, modular
programming and information hiding.
Examples include Pascal, Algol 68 and C.
•
•
•
1980s reducing complexity – object orientation,
functional programming.
1990s exploiting parallel and distributed hardware
(going faster!), e.g. various parallel extensions to
existing languages and dedicated parallel
languages such as occam.
2000s Genetic programming languages, DNA
computing, bio-computing?
THE SOFTWARE CRISIS
•
The phrase software crisis alludes to a set of problems encountered in the
development of computer software during the 1960s when attempting to build
larger and larger software systems using existing development techniques.
•
As a result:
– 1.Schedule and cost estimates were often grossly inaccurate.
– 2.Productivity of programmers could not keep up with demand.
– 3.Poor quality software was produced.
•
To address these problems the discipline of software engineering came into
being.
Classification of programming
languages:
1. Machine, Assembler and High Level
Languages
2. Chronological order of development
3. Generations
4. Levels of abstraction (from machine
level)
5. Declarative v Non-declarative
6. Paradigms
LANGUAGE
GENERATIONS
Generation
1st
2nd
Classification
Machine languages
Assembly languages
3rd
4th
Procedural languages
Application languages (4GLs)
5th
6th
AI techniques, inference languages
Neural networks (?), others….
Classification of programming
languages:
1. Machine, Assembler and High Level
Languages
2. Chronological order of development
3. Generations
4. Levels of abstraction (from machine
level)
5. Declarative v Non-declarative
6. Paradigms
LANGUAGE LEVELS OF
ABSTRACTION (Bal and Grune
. 94)
Level
Instructions
Low level
languages
Simple machine-like Direct memory access
instructions
and allocation
High level
languages
Expressions and
explicit flow of
control
Very high
Fully abstract
level
machine
languages
Memory handling
Memory access and
allocation through
operators
Fully hidden memory
access and automatic
allocation
Classification of programming
languages:
1. Machine, Assembler and High Level
Languages
2. Chronological order of development
3. Generations
4. Levels of abstraction (from machine level)
5. Declarative v Non-declarative
6. Paradigms
Classification of programming
languages:
1. Machine, Assembler and High Level
Languages
2. Chronological order of development
3. Generations
4. Levels of abstraction (from machine level)
5. Declarative v Non-declarative
6. Paradigms
Programming language
paradigms correspond to
natural language
Imperative: commands
“copy the value of X into Y”
Functional: noun phrases
“the sum of X and Y”
Logic: subject/predicate sentences (declarations)
“X is greater than Y”
Computational
Paradigms
Imperative: manipulate an abstract machine
– variables naming memory locations
– arithmetic and logic operators
– reference, evaluate, assignment operators
Fits von Neumann architecture closely
Key operation: assignment and control-flow
Computational
Paradigms
Functional: express problem solution as operations on data
– no named memory locations
– no assignment operators (no side-effects)
– value binding through parameter passing
Key operation: function application
Computational
Paradigms
Object-oriented: organise program as collection of
interacting entities with notion of identity
– data and operations encapsulated
– emphasis on data abstraction
Key operation: message passing
Computational
Paradigms
Logic: formally specify problem solution
– program states what properties a solution must have
– program does not state how to calculate solution
– underlying solution engine
Key operation: unification
Imperative Languages
Problem: sum twice the numbers from 1 to N
FORTRAN
C
Algol
SUM = 0
DO 11 K = 1, N
SUM = SUM + 2 * K
11 CONTINUE
sum = 0;
for (k=1; k<=N; k++)
sum += 2*k;
sum := 0;
for j :=1 to N do
sum := sum + 2*k;
Object-oriented
Languages
Problem: sum twice the numbers from 1 to N
C++
class myset : public Set {
public:
myset() {}
int sum() {
int s = 0;
SetEnumeration e = new SetEnumeration(this);
while (e.hasMoreElements())
s += ((Integer) e.nextElement()).intValue();
return s;
}
}
Functional Languages
Problem: sum twice the numbers from 1 to N
ML
fun sum(n) =
if n = 0
then 0
else 2 * n + sum (n - 1);
sum(4) evaluates to 20
Scheme
(define (sum n)
(if (= n 0) 0
(+ (* 2 n) (sum (- n 1)))
)
)
(sum 4) evaluates to 20
Logic Languages
Problem: sum twice the numbers from 1 to N
Prolog
sum(0,0).
sum(N,S) :NN is N - 1,
sum(NN, SS),
S is N*2 + SS.
?- sum(1,2).
yes
?- sum(2,4).
no
?- sum(20,S).
S = 420
Advantages of the DSL Approach

Programs in the target domain are:
Contribute to higher
programmer productivity

more concise
quicker to write

easier to maintain
Dominant cost in
large SW systems

easier to reason about
Formal verification, program
transformation, compiler optimization

These are the same arguments in favor of any high-level language!
But in addition, we should add:

written by non-programmers
Helps bridge gap between
developer and user
600.325/425 Declarative Methods - J. Eisner
slide partly thanks to Tim Sheard
25
Potential Disadvantages of DSL’s

Performance may be poor.


Unacceptable start-up costs.


new language(s) for every domain
Language creep/bloat.


design time, implementation, documentation
Tower of Babel.


“high-level languages are less efficient”
more features added incrementally
Language design/implementation is hard!!

2-5 years typical for new language
600.325/425 Declarative Methods - J. Eisner
slide thanks to Tim Sheard
26
Scripting Languages vs. DSL’s




Scripting languages are DSL’s.
Domain: system components (e.g. GUI widgets,
COM/CORBA objects, other programs, etc.).
Examples: Tcl, PERL, Visual Basic, OS shells (such
as Unix).
Design/implementation issues are similar.
600.325/425 Declarative Methods - J. Eisner
slide thanks to Tim Sheard
27
Embedded Languages

In embedded approach, each domain concept is realized directly as
a host-language construct:


domain operators are host-language procedures,
domain types are host-language user-defined data types, etc.

Creating or modifying a DSL is relatively cheap, provided a suitably
powerful host language (e.g. Haskell or Lisp) is used.

Embedding may be thought of as rapid prototyping.

Even if the domain ultimately requires generating code for a
specialized target environment, the embedded implementation can
be used for modeling and simulation.

Many language features needed by a typical DSL

e.g. support for procedural abstraction; modules; etc
will already exist in the host language;

It is straightforward to integrate code from multiple DSLs if they
share the same host implementation.
600.325/425 Declarative Methods - J. Eisner
slide thanks to Tim Sheard
28
Stand-alone System

A stand-alone implementation for a DSL can have its own
syntax and type system appropriate for just that domain.

The DSL can be ``restricted" to enforce constraints on what
can be expressed.

The DSL can have its own optimizer that relies on domainspecific optimization rules so that performance bottlenecks
can be addressed.

Automated construction tools for interpreters and compilers
can make building a stand-alone system cheaper; while
many such tools exist, some important ones are still missing.
600.325/425 Declarative Methods - J. Eisner
slide thanks to Tim Sheard
29
A User centered Approach to Language Design

Languages can be designed around several issues





To solve a computational problem
To make the implementers job easier
To make the programmer’s (user of the language) life
easier
Which of these do you think is the most important?
Which of these gets the most attention in the
programming language literature?
600.325/425 Declarative Methods - J. Eisner
slide thanks to Tim Sheard
30

Sort(X) = permutation of X whose elements are
pairwise ordered

divide(6,2) = some number x such that 2*x=6
(Could solve by a general equation solver, or by
Prolog)

sqrt(-6) = ...
600.325/425 Declarative Methods - J. Eisner
31
Language Influences Programming
Practice

Languages often strongly favor a particular
style of programming



Object-oriented languages: a style making heavy
use of objects
Functional languages: a style using many small
side-effect-free functions
Logic languages: a style using searches in a
logically-defined problem space
600.325/425 Declarative Methods - J. Eisner
slide thanks to Adam Webber (modified)
32
Fighting the Language



Languages favor a particular style, but do not
force the programmer to follow it
It is always possible to write in a style not
favored by the language
It is not usually a good idea…
600.325/425 Declarative Methods - J. Eisner
slide thanks to Adam Webber (modified)
33
Example: APL Factorial
X




An APL expression that computes X’s factorial
Expands X it into a vector of the integers 1..X,
then multiplies them all together
(You would not really do it that way in APL, since
there is a predefined factorial operator: !X)
Could be called functional, but has little in
common with most functional languages
600.325/425 Declarative Methods - J. Eisner
slide thanks to Adam Webber (modified)
34
Programming Experience Influences
Language Design


Corrections to design problems make future
dialects, as already noted
Programming styles can emerge before there
is a language that supports them


Programming with objects predates objectoriented languages
Automated theorem proving predates logic
languages
600.325/425 Declarative Methods - J. Eisner
slide thanks to Adam Webber (modified)
35
Turing Equivalence

General-purpose languages have different
strengths, but fundamentally they all have the
same power


And all have the same power as various
mathematical models of computation


{problems solvable in Java}
= {problems solvable in Fortran}
=…
= {problems solvable by Turing machine}
= {problems solvable by lambda calculus}
=…
Church-Turing thesis: this is what “computability”
means
600.325/425 Declarative Methods - J. Eisner
slide thanks to Adam Webber (modified)
36
Declarative Programming


A logic program defines a set of relations.
This “knowledge” can be used in various
ways by the interpreter to solve different
queries.
In contrast, the programs in other languages
make explicit HOW the “declarative
knowledge” is used to solve the query.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
37
Imperative vs Non-Imperative


Functional/Logic programs specify WHAT is
to be computed abstractly, leaving the details
of data organization and instruction
sequencing to the interpreter.
In constrast, Imperative programs describe
the details of HOW the results are to be
obtained, in terms of the underlying machine
model.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
38
Imperative vs Non-Imperative


Functional/Logic style clearly separates
WHAT aspects of a program (programmers’
responsibility) from the HOW aspects
(implementation decisions).
An Imperative program contains both the
specification and the implementation details,
inseparably inter-twined.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
39
Procedural vs Functional




Program: a sequence
of instructions for a von
Neumann m/c.
Computation by
instruction execution.
Iteration.
Modifiable or
updateable variables.




Program: a collection
of function definitions
(m/c independent).
Computation by term
rewriting.
Recursion.
Assign-only-once
variables.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
40
Procedural vs Object-Oriented



Emphasis on
procedural abstraction.
Top-down design;
Step-wise refinement.
Suited for programming
in the small.



Emphasis on data
abstraction.
Bottom-up design;
Reusable libraries.
Suited for programming
in the large.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
41
Procedural vs Object-Oriented


New operations cause additive changes in
procedural style, but require modifications to
all existing “class modules” in object-oriented
style.
New data representations cause additive
changes in object-oriented style, but require
modifications to all “procedure modules”.
600.325/425 Declarative Methods - J. Eisner
slide thanks to T.K. Prasad (modified)
42
Further Perspective
In addition to labels of functional, procedural, and OO
languages, we might also categorize languages based
on whether they are interpreted or compiled (or even a
hybrid).
Interpreted languages are evaluated one step at a time,
with values and variables being determined
dynamically at run time.
Compiled languages are assembled into memory, with
address locations and offsets precalculated, and then
crafted into an “executable” program.
600.325/425 Declarative Methods - J. Eisner
slide thanks to Jim Greenlee (modified)
43
What is a
programming
language?
“…a set of conventions for communicating an algorithm.” Horowitz
Purposes
– specifying algorithms and data
– communicating to other people
– establishing correctness
this and following slides thanks to James Montgomery
Why use anything
other than machine
code?
•
•
•
•
readability
machine independence
program libraries
consistency checking during implementation (e.g., typechecking)
• acceptable loss of efficiency
• dealing with scale
“The art of programming is the art of organising complexity” - Dijkstra
Why learn more than
one programming
language?
• language encourages thinking about problem in a
particular way
• depending on problem, one way of thinking may be
better
• language should match the problem
• many factors govern choice of language
–
correctness and efficiency of resulting programs
– ease of development and maintenance
– reusability and interoperability
– …
Prehistory
History of
Programming
Languages
•
c2000 BC, Babylon: “Algorithms” for calendar
computation, no explicit conditionals or iteration
•
c300 BC, Greece: Euclid expresses the greatest
common divisor algorithm using iteration
•
c1820-1870, England: Countess Ada Lovelace writes
programs for Babbage’s analytic engine
•
1950s: first modern programming languages appear
History of
Programming
Languages
FORTRAN 1954-1957, John Backus (IBM)
•
•
•
•
•
numeric, scientific computing
fixed format for punched cards
implicit typing
only numeric data
only bounded loops, test vs zero
Algol 60 1958-1960, International committee
•
•
•
•
•
•
numeric, scientific computing
free format, reserved words
block structure and lexical scope
while loops, recursion
explicit typing
BNF for formal syntax definition
History of
Programming
COBOL 1959-1960, Languages
DoD committee
•
•
•
•
business data processing
explicit data description
records and file handling
English-like syntax
APL 1956-1960, Ken Iverson (IBM)
•
•
•
•
array processing
functional programming style
nonstandard character set
multidimensional arrays
Lisp 1956-1962, John McCarthy (Stanford)
•
•
•
•
symbolic computing: AI
functional programming style
same representation for program and data
garbage collection
History of
Programming
SNOBOL 1962-1966,Languages
Farber, et al. (Bells Labs)
•
•
string processing
powerful pattern matching
PL/I 1963-1964, IBM
•
•
•
•
•
general purpose programming
powerful pattern matching
planned successor to FORTRAN, Algol 60, COBOL
user-defined exceptions
multi-tasking
Simula67 1967, Dahl & Nygaard
•
•
•
•
simulation
class concept for data abstraction
persistent objects
inheritance of properties
History of
Programming
Algol 68 1963-1968 Languages
•
•
•
•
general purpose programming
orthogonal language design
powerful mechanism for type definition
formal operational semantics
Pascal 1969, Wirth
•
•
•
teaching language
1 pass compiler
call-by-value semantics
Prolog 1972, Colmerauer & Kowalski
•
•
•
AI applications
logic programming
theorem proving based on unification
History of
Programming
C 1974, Ritchie (BellLanguages
Labs)
•
•
•
systems programming
access to machine level
efficient code generation
CLU 1974-77, Liskov (MIT)
•
•
•
•
simulation
data abstraction and exceptions
operational semantics
attempt to enable program verification
Smalltalk mid 1970s, Kay (Xerox PARC)
•
•
•
rapid prototyping
strictly object-oriented: encapsulation and inheritance
easy to write programs with complex behaviour
History of
Programming
Modula 1977, Wirth Languages
•
•
•
•
general purpose programming
modules to control interfaces between sets of procedures
real-time programming
targets large software development
Ada 1977, DoD committee
•
•
•
general purpose programming
explicit parallelism: rendezvous
exception handling
Concurrent Pascal 1976, Brinch-Hansen
•
•
asynchronous concurrent processes
monitors for safe data sharing
History of
Programming
Languages
Scheme 1975-78, Sussman
and Steele
•
general-purpose programming
•
slimline and uniform Lisp
•
closer to the Lambda Calculus
ML 1978, Milner
•
general-purpose programming
•
powerful type-checking
•
advanced garbage-collection
History of
Programming
Languages
C++ 1985, Stroustrop
(Bell Labs)
•
•
•
general purpose programming
goal: type-safe object-oriented programming
templates allow limited higher-order programming
Java Arnold, Gosling, and Steele (Sun)
•
•
•
•
•
general purpose programming
type-safe object-oriented programming
platform independent (designed for web programming)
exception handling
threads
Haskell 1989-98, Edinburgh and Yale
•
general-purpose programming
•
powerful functional language
PROGRAMMING
PARADIGMS?
•
In science a paradigm describes a set of techniques that have been found to be
effective for a given problem domain (i.e somebody somewhere must believe in
it).
•
A paradigm can typically be expressed in terms of a single principle (even if this
is in fact an over simplification).
•
This principle must be supported by a set of techniques.
•
In the context of programming languages we say that a paradigm induces a
particular way of thinking about the programming task.
We can identify four principal programming paradigms:
1. Imperative (e.g. Pascal, Ada, C).
2. Object-oriented (e.g. Java).
3. Functional (e.g. Haskell, SML).
4. Logic (e.g. Prolog).
PROGRAMMING MODELS
• The 4 main programming paradigms aim at solving general
programming problems, but sometimes there are additional aspects to a
problem which require us to “tweak” a paradigm.
• The result is not a new paradigm but a programming model founded on
a particular paradigm.
• An example is parallel or distributed programming.
SUMMARY
•
•
•
Classification of languages:
1. Machine, assembler & high level
2. Chronological order
3. Generations
4. Levels of abstraction
5. Declarative v Non-declarative.
Paradigms
Programming models