Transcript Document

Chapter One: Metrics and Influences
on Language Design
Lesson 02
2
Programming Languages: lecture two
4/13/2015
Language Evaluation Criteria
A language that has poor
readability, writability, and/or
reliability has a high cost



Readability
Writability
Reliability
Cost
Example writable vs. readable:
APL has a powerful set of
operators for array operands.
Can be used to create very
complex, very long expressions.
APL has excellent writability
APL has poor readability

Reliable if programs that are written in the language tend to
be error free. Readability and writability contribute to
reliability
Example: people tend to make mistakes when using pointers
which leads to unreliable programs
3
Programming Languages: lecture two
4/13/2015
Characteristics that affect criteria
To be writable, How
should could
be readable
APL (ifbeever need to make
changes to code)
writable but not
To be reliable, must be readable and writable


readable?
4
Programming Languages: lecture two
4/13/2015
Readability
Overall simplicity




Small number of features and constructs
Minimal feature multiplicity (multiple ways to do things,
a++, a+=1,a=a+1)
Minimal operator overloading
Orthogonality


Few exceptions to the rules, always behaves as expected
Data types


Adequate predefined data types (example: int used
because no boolean)
Syntax considerations



5
Allowable Identifiers (another word for a variable)
Intuitive meaning of statements
Programming Languages: lecture two
4/13/2015
Writability


6
Support for abstraction
Expressivity
 A set of relatively convenient ways of specifying
operations (++, vector multiplication, for vs. while)
 Strength and number of operators and predefined
functions
Programming Languages: lecture two
4/13/2015
Let’s try it
A programming language that has a relatively
small number of features and constructs, has
seemingly adequate predefined data types,
statements and constructs that are intuitive, but
has little support for abstracting the data types
or for performing commonly occurring
operations needed in the target programming
domain, is ____________.
A programming language that has an relatively
small number of features and constructs, has a
large number predefined data types tailored for
use in a particular programming domain,
statements and constructs that are not very
intuitive but that are extremely powerful and
complex when employed within the target
programming domain , is ____________.
Readable, writable, both, or neither?
Readable, writable, both, or neither?
7
Programming Languages: lecture two
4/13/2015
Reliability



8
Type checking
Exception handling
Disallow aliasing
(two variables pointing to same object)
Programming Languages: lecture two
4/13/2015
Cost
Readability/writability




Training programmers to use the language
Support for design approach and problem domain
(object orientation, easy integration of appropriate
math operations, etc.)
Maintaining programs, the more readable the
better
Reliability


Constant debugging
Literal cost




9
Actual cost of compiler software (free?)
Compile time
Execution efficiency
Programming Languages: lecture two
4/13/2015
Two Major Influences on Language Design


Computer Architecture
Programming Methodologies

10
Software Design and Engineering
Approaches
Programming Languages: lecture two
4/13/2015
John von Neumann:
von Neumann Architecture



Mathematician
Member of the Manhattan
Project
Same memory for program and
data
11
Programming Languages: lecture two
4/13/2015
First programming languages…


1’s and 0’s (Machine Language)
Designed to navigate the existing architecture
Machine language:
10110000 01100001
Move the value 61h (or 97 decimal; the h-suffix means hexadecimal;
into the processor register named "AL".
Artillery firing tables:
World War II
12
ENIAC
Programming Languages: lecture two
4/13/2015
First compiled languages…

Assembly: directly translates to machine language

one to one correspondence between commands in machine
and assembly languages
Machine language:
Assembly:
10110000 01100001
MOV AL, 61h
Move the value 61h (or 97 decimal; the h-suffix means hexadecimal;
into the processor register named "AL".

Textual, so easier to
remember
IBM 360
13
Programming Languages: lecture two
4/13/2015
Finally, high-level, compiled programs
mov ax, a
cmp ax, b
jne ElseBlk
mov ax, d
mov c, ax
jmp EndOfIf

Make human readable
if (a=b) then
c := d
else
b := b + 1;
ElseBlk:
inc b
EndOfIf:
14
Programming Languages: lecture two
4/13/2015
Course is generally about the …
• Interpreted: on the fly determination of program
meaning
Text
0101010101010101010010
• Hybrid: when execute makes a pass
compiling
(machine
language)to
(source)
an intermediate form
• JIT: (just in time) subprograms compiled into
machine
code when
they compiled
are called
 Evolution
of high-level,
languages
What other kinds of
languages are there
(besides compiled)?
15
Programming Languages: lecture two
4/13/2015
Architecture first, later programming
methodologies



Control Structures?
Mid 1950s to early 1960s: machine efficiency
Late 50’s: application to problems in artificial intelligence
Late 1960s: People efficiency became important; readability,
better control structures and modularity


structured programming
top-down design and step-wise refinement
If/else condition
 Middle 1980s:
Object-orientedand
programming
checking
loops

Late 1970s: Process-oriented to data-oriented

data abstraction – data structures

Data abstraction + inheritance + polymorphism
16
Programming Languages: lecture two
4/13/2015
First high-level languages…

Considered to be “imperative”

Central features are variables, assignment
statements, and iteration
Include languages that support objectoriented programming
Include scripting languages
Include the visual languages
Examples: C, Java, Perl, JavaScript, Visual BASIC
.NET, C++




17
Programming Languages: lecture two
4/13/2015
Why imperative?

Architecture driven



Pull data and instructions from memory
Sequential operations clock driven
Also mindset driven:

Definition of an algorithm

18
A step-by-step procedure for solving a problem in a finite
number of steps
Programming Languages: lecture two
4/13/2015
A limitation to early imperative languages

When study languages



Doesn’t take long when studying algorithms to
move into the realm of recursion


Must formalize definitions
Many definitions and proofs (inductive) are
recursive in nature
Recurrence relations
Earliest high-level compiled languages
(Fortran) could not handle recursion
19
Programming Languages: lecture two
4/13/2015
The Search for Artificial Intelligence

Shortly after first high-level
languages (Mid 50’s) …



20
Allen Newell, J. C. Shaw, and
Herbert Simon “The Logical
Theorist”
Used a program to actually prove
theorems
Approach called “list processing”
Programming Languages: lecture two
4/13/2015
Artificial Intelligence (List Processing)

Proof technique




Came up with own language:
Information Processing Language
(IPL) for list processing

21
Based upon a search tree: the root was
the initial hypothesis, each branch was
a deduction based on the rules of logic.
Required recursion to elegantly solve
the tree search
Method needed for processing
symbolic data in linked lists
Never took off: too low-level,
essentially assembly language
Programming Languages: lecture two
4/13/2015
Retrofit list processing


IBM retrofitted list processing
to the first high-level
programming language:
Fortran (Fortran List
Processing Language or FLPL)
John McCarthy of MIT worked
for a summer at IBM



22
Studied symbolic differentiation
Concluded that list processing
required recursion, condition
checking, and implicit
deallocation of abandoned lists
FLPL did not have
Programming Languages: lecture two
xkcd.com
4/13/2015
LISP




McCarthy and Minsky of MIT therefore developed LISP
(List Programming Language)
Approach became known as functional programming
Each list has as first item a function, all subsequent items
are arguments
Second major category of programming languages (first
being imperative)
Function applied to
items in the list
(f, i1, i2, …, in)
23
Programming Languages: lecture two
4/13/2015
Example

Factorial mathematical definition
1 if n  0
f (n)  
n * f (n  1) if n  0

In LISP
(DEFINE (factorial n)
(IF (= n 0)
1
(* n (factorial (- n 1)))
))
24
Genealogy of Common Languages
4/13/2015
In short: functional languages…

Were the result of the vacuum left by early languages when they did
not support recursion


Virtually all “imperative” programming languages now support recursion,
linked lists, and passing of functions as arguments
Hasn’t really received widespread acceptance


25
Most list processing languages are interpreted (can be slow)
Most users find it difficult to master: many of us think “imperatively” (i.e.
step-by-step) when we think of algorithms
Programming Languages: lecture two
4/13/2015
AI strikes again

Early 70’s: it became apparent that much of AI
was comprised of logic based conclusions



Example


It can be deduced that X is the grandparent of Z if
it si true that X is the parent of Y and Y is the
parent of Z
Can query a database of fact statements and
rules


26
Predicate calculus (if a is true then b must be true)
Inference process
Like Y is the parent of Z
Looking for relationships that satisfy rule
statements like grandparent relationship
Programming Languages: lecture two
4/13/2015
Programming language categories



Logic programming languages became the third major
category
Advent of WEB drove the fourth
Categories

Imperative


Functional


Prolog
Markup/programming hybrid

27
LISP, Scheme, ML
Logic


C, Java, Perl, JavaScript,Visual BASIC
.NET, C++
JSTL, XSLT
Programming Languages: lecture two
4/13/2015
Course




Practice at several exemplary programming
languages
Focus more on C/C++ than the rest
Learn the vernacular of formally describing
languages
Gain some insight into how compilers work
28
Programming Languages: lecture two
4/13/2015
What should you study in this chapter?



Terminology
Readability/ writability/ reliability (e.g. if a language allows
aliasing how does that affect reliability)?
Homework will give you some examples
•Expression
•Orthogonal
•Syntax
•Abstraction
•Expressive
•Aliasing
29
•Construct
•Identifier
•Imperative •Interpreted
•Functional •Hybrid
•Control structures
•Compile
•Logic
•JIT
Programming Languages: lecture two
4/13/2015
30
Programming Languages: lecture two
4/13/2015
Construct


From construction, to construct something from smaller
parts
(Wikipedia) A language construct is a syntactically
allowable part of a program that may be formed from one
or more lexical tokens in accordance with the rules of a
programming language.




31
Variable
If/else
Return
Method/function/procedure
Class
Introduction
4/13/2015
Lexical


A lexicon is a dictionary
Merriam-Webster
Main Entry: lex·i·cal
Pronunciation: \ˈlek-si-kəl\
Function: adjective
Date: 1836
1 : of or relating to words or the vocabulary of a language as
distinguished from its grammar and construction
2 : of or relating to a lexicon or to lexicography
Return
32
Programming Languages: lecture two
4/13/2015
Orthogonality

Merriam-Webster
Main Entry: or·thog·o·nal
Return
Pronunciation: \ȯr-ˈthä-gə-nəl\
Function: adjective
Etymology: Middle French, from Latin orthogonius, from Greek orthogōnios, from orth+ gōnia angle — more at -gon
Date: 1612
1 a : intersecting or lying at right angles b : having perpendicular slopes or
tangents at the point of intersection <orthogonal curves>
2 : having a sum of products or an integral that is zero or sometimes one under
specified conditions: as a of real-valued functions : having the integral of the product
of each pair of functions over a specific interval equal to zero b of vectors : having
the scalar product equal to zero c of a square matrix : having the sum of products
of corresponding elements in any two rows or any two columns equal to one if
the rows or columns are the same and equal to zero otherwise : having a
transpose with which the product equals the identity matrix
3 of a linear transformation : having a matrix that is orthogonal : preserving length
and distance
4 : composed of mutually orthogonal elements <an orthogonal basis of a vector
space>
5 : statistically independent
33
Programming Languages: lecture two
4/13/2015
Orthogonality (continued)



A relatively small set of primitive constructs can be
combined in a relatively small number of ways
Every possible combination is legal, independent of
context
Negative examples

C:



34
Cannot return an array from a function
Member of a struct can be any data type except void
Members of an array can be any data type except void
Programming Languages: lecture two
4/13/2015
Syntax

Merriam-Webster
Main Entry: syn·tax
Pronunciation: \ˈsin-ˌtaks\
Function: noun
Etymology: Middle French or Late Latin; Middle French sintaxe, from Late
Latin syntaxis, from Greek, from syntassein to arrange together, from
syn- + tassein to arrange
Date: 1574
1 a : the way in which linguistic elements (as words) are put together to
form constituents (as phrases or clauses) b : the part of grammar
dealing with this
2 : a connected or orderly system : harmonious arrangement of parts
or elements <the syntax of classical architecture>
3 : syntactics especially as dealing with the formal properties of
languages or calculi
35
Introduction
4/13/2015
Expression


(Wikipedia) An expression is a combination of values,
variables, operators, and functions that are interpreted
(evaluated) according to the particular rules of
precedence and of association for a particular
programming language, which computes and then
produces (returns, in a stateful environment) another
value.
Examples:




36
a
a+b
f(x)
a==b
Return
Programming Languages: lecture two
4/13/2015
Abstraction


(Wikipedia) Abstraction is the process or result of generalization by
reducing the information content of a concept or an observable
phenomenon, typically to retain only information which is relevant for a
particular purpose. For example, abstracting a leather soccer ball to a ball
retains only the information on general ball attributes and behavior.
Similarly, abstracting happiness to an emotional state reduces the amount of
information conveyed about the emotional state. Computer scientists use
abstraction to understand and solve problems and communicate their
solutions with the computer in some particular computer language.
Examples:
 Float is an abstraction for a real number
 An Employee object in a program is an abstraction for an employee:
doesn’t describe everything about an object
Return
37
Programming Languages: lecture two
4/13/2015
Recursion

Recursion is a method where the solution to a problem
depends on solutions to smaller instances of the same
problem.
Graham, Ronald; Donald Knuth, Oren Patashnik (1990). Concrete Mathematics. Chapter 1:
Recurrent Problems. http://www-cs-faculty.stanford.edu/~knuth/gkp.html.
Donald Knuth wrote “The art of programming,” "father" of the analysis of algorithms,
big O notation

The power of recursion evidently lies in the possibility of
defining an infinite set of objects by a finite statement. In
the same manner, an infinite number of computations can
be described by a finite recursive program, even if this
program contains no explicit repetitions.
Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126.
Niklaus Wirth wrote Pascal programming language
38
Programming Languages: lecture two
4/13/2015
Recursion (continued)

Example


Factorial
if x==1 then f(x)=1
else f(x) = x * f(x-1)
Fibonacci




By definition, the first two Fibonacci numbers are 0 and 1, and each
remaining number is the sum of the previous two. Some sources omit the
initial 0, instead beginning the sequence with two 1s.
0 1 1 2 3 5 8 13 21 34 55 89 144
In mathematical terms, the sequence Fn of Fibonacci numbers is defined
by the recurrence relation
F0=0 and F1 = 1 otherwise Fn=Fn-1+Fn-2
if x==0 then f(x)=0
else if x==1 then f(x)=1
else f(x) = x * f(x-1)
39
Programming Languages: lecture two
4/13/2015
Recursion (continued)

Definition of the set of natural numbers


40
1 is in N
If an element n is in N then n+1 is in N
Programming Languages: lecture two
4/13/2015
Why no recursion early on

Efficient implementation of recursion
generally requires a memory data
structure known as a stack, and most
computer architectures designed since
the 1970s provide fast hardware
support for stacks. The routine calling
convention on the machines of the
1950s for which Fortran was originally
developed stored the return address in
the called routine, completely
preventing recursion.
41
Stack: local variables
Heap: dynamic allocation
Data: global variables
Text: program code
Programming Languages: lecture two
4/13/2015
Reasons for Studying
Programming Languages






42
Increased ability to express ideas
Improved background for choosing
appropriate languages
Increased ability to learn new
languages
Better understanding of significance
of implementation
Better use of languages that are
already known
Overall advancement of computing
Programming Languages: lecture two
4/13/2015
Where programming is used
(Programming Domains)

Scientific applications



Business applications




Symbols rather than numbers manipulated; use of linked lists
LISP
Systems programming (operating system and supporting
tools)



Produce reports, use decimal numbers and characters
COBOL
Artificial intelligence


Large numbers of floating point computations; use of arrays
Fortran
Need efficiency because of continuous use
C
Web Software

Eclectic collection of languages: markup (e.g., XHTML),
scripting (e.g., PHP), general-purpose (e.g., Java)
Return
43
Programming Languages: lecture two
4/13/2015