Introduction to Computer Science

Lecture 6: Programming Languages

Tian-Li Yu

Taiwan Evolutionary Intelligence Laboratory (TEIL)

Department of Electrical Engineering
National Taiwan University

[email protected]

Slides made by Tian-Li Yu, Jie-Wei Wu, and Chu-Yu Hsu

Tian-Li Yu Programming Languages 1 / 45

 Programming Languages and Paradigms

PL Generations

1st 2nd 3rd 4th −−−−−−−−−−−−−−−→

Machine Assembly Fortran SQL

Instructions (Mnemonic Cobol SAS
system of MIs) Basic
C/C++
Java

Tian-Li Yu Programming Languages 2 / 45

 Programming Languages and Paradigms

Assembler: Translating MIs to Assembly

1st
2nd
Machine
Assembly
instructions
156C −−−−−−−−−−−−−−−−→ LD R5, Price
166D −−−−−−−−−−−−−−−−→ LD R6, ShippingCharge
5056 −−−−−−−−−−−−−−−−→ ADDI R0, R5, R6
306E −−−−−−−−−−−−−−−−→ ST R0, TotalCost
C000 −−−−−−−−−−−−−−−−→ HTL

Mnemonic names for op-codes

Identifiers: Descriptive names for memory
locations, chosen by the programmer

Tian-Li Yu Programming Languages 3 / 45

 Programming Languages and Paradigms

3rd Generation Languages (3GL)

Characteristics of assembly
- Machine dependent
- One-to-one mapping
- Assembler

High-level primitives
Machines independent (virtually)
One primitive to many MI mapping
Compiler & interpreter

Tian-Li Yu Programming Languages 4 / 45

 Programming Languages and Paradigms

Languages and Issues

Natural vs. formal languages

- Formal language → formal grammar

Portability
- Theoretically: different compilers
- Reality: Minor modifications

Tian-Li Yu Programming Languages 5 / 45

 Programming Languages and Paradigms

Programming Paradigms
LISP ML Schema
Functional

C++ C#
Object-oriented
Smalltalk Visual Basic Java
Machine FORTRAN BASIC C Ada
Imperative
Languages COBOL ALGOL APL Pascal

GPSS Prolog
Declarative
1950 1960 1970 1980 1990 2000

Tian-Li Yu Programming Languages 6 / 45

 Programming Languages and Paradigms

Imperative vs. Declarative

Imperative paradigm
- Procedural
- Approaching a problem by finding an algorithm to solve the problem.

Declarative paradigm
- Implemented a general problem solver
- Approaching a problem by finding a formal description of the problem.
- Will talk more about this later.

Tian-Li Yu Programming Languages 7 / 45

 Programming Languages and Paradigms

Functional Paradigm
Inputs: Old_balance Credits Debits

Find_sum Find_sum

Find_diff

Output: New_balance

Tian-Li Yu Programming Languages 8 / 45

 Programming Languages and Paradigms

Functional vs. Imperative

(Find diff (Find sum Old balance Credits) (Find sum Debits))

Temp balance ← Old balance + Credit

Total debits ← sum of all Debits
Balance ← Temp balance − Total debits

(Find Quotiant (Find sum Numbers) (Find count Numbers))

Sum ← sum of all Numbers

Count ← # of Numbers
Quotiant ← Sum / Count

Tian-Li Yu Programming Languages 9 / 45

 Programming Languages and Paradigms

Object-Oriented Paradigm

OOP (object-oriented programming)

Abstraction
Information hiding
- Encapsulation
- Polymorphism
Inheritance

References:
- http://www.codeproject.com/KB/architecture/OOP_Concepts_and_manymore.aspx
- http://en.wikipedia.org/wiki/Object-oriented_programming

Tian-Li Yu Programming Languages 10 / 45

 Imperative Paradigm

More about Imperative Paradigm

Variables and data types

Data structure
Constants and literals
Assignment and operators
Control
Comments

Tian-Li Yu Programming Languages 11 / 45

 Imperative Paradigm

Variables and Data Types

Integer
Real (floating-point)
Character
Boolean

FORTRAN Pascal C/C++ (Java)

INTEGER a, b a, b: integer; int a, b;
REAL c, d c, d: real; float c, d;
BYTE e, f e, f: char; char e, f;
LOGICAL g, h g, h: boolean; bool g, h;

Tian-Li Yu Programming Languages 12 / 45

 Imperative Paradigm

Data Structure
Homogeneous array
Heterogeneous array
FORTRAN INTEGER a(6,3)
Pascal a: array[0..5,0..2] of integer;

C/C++ int a[5][2];

C/C++
struct{
char Name[25];
int Age;
float SkillRating;
} Employee;

Tian-Li Yu Programming Languages 13 / 45

 Imperative Paradigm

Constant and Literals

a ← b + 645;
- 645 is a literal

const int a=645;

final int a=645;

A constant cannot be a l-value.

- a=b+c;

Tian-Li Yu Programming Languages 14 / 45

 Imperative Paradigm

Assignment and Operators

APL Ada, Pascal C/C++ (Java)

a <- b + c; a := b + c; a = b + c;

Operator precedence
Operator overloading

Tian-Li Yu Programming Languages 15 / 45

 Imperative Paradigm

Control
Old-fashion: goto
goto 40
20 print "passed."
goto 70
40 if (grade < 60) goto 60
goto 20
60 print "failed."
70 stop

Not recommended in modern programming

Modern programming
if (grade < 60)
then print "failed."
else print "passed."

Tian-Li Yu Programming Languages 16 / 45

 Imperative Paradigm

Control Structures

Condition Condition
true false
B?

S1 S2
if (B) S1
else S2;

Condition
false
B?

Condition while (B)

true

S1
S1;

What switch (N)

is the value
of N? { case C1: S1;break;
N = C1 N = C2 N = C3
case C2: S2;break;
S1 S2 S3
case C3: S3;break;
};

Tian-Li Yu Programming Languages 17 / 45

 Imperative Paradigm

Control Structures (contd.)

Assign Count the value 1

False
Count < 4 ?

True

Assign Count the

Body
value Count + 1

for (int Count = 1; Count < 4; Count++)

body;

Tian-Li Yu Programming Languages 18 / 45

 Imperative Paradigm

Comments
C/C++, Java

a = b + c; // This is an end-of-line comment

/**
/*
This is a
This is a
documentation
block comment
comment
*/
a = b + c; */
a = b + c;

Tian-Li Yu Programming Languages 19 / 45

 Imperative Paradigm

Calling Procedures
Calling
program unit
Control is
transferred Procedure
to procedure

Calling program Procedure is

unit requests excuted.
procedure.

Calling program
unit continues
Control is returned to
calling enviroment when
procedure is completed.

Tian-Li Yu Programming Languages 20 / 45

 Imperative Paradigm

Terminology
Starting the head with the term “void” is The former parameter list. Note
the way that a C programmer specifies that that C, as with many programming
the program unit is a procedure rather languages, requires that the data
than a function. We will learn about functions type of each parameter be specified.
shortly.

void ProjectPopulation (float GrowthRate){

int Year;

Population[0] = 100.0;
for (Year = 0; Year =< 10; Year++)
Population[Year+1] = Population[Year] + (Population[Year]*GrowthRate);

This declares a local variable These statements describe how the

named Year. populations are to be computed and
stored in the global array named Population.

Tian-Li Yu Programming Languages 21 / 45

 Imperative Paradigm

Terminology (contd.)

Procedure’s header
Local vs. global variables
Formal vs. actual parameters
Passing parameters
- Call by value (passed by value)
- Call by reference (passed by reference)
- Call by address: variant of call-by-reference.

Tian-Li Yu Programming Languages 22 / 45

 Imperative Paradigm

Call by Value
a. When the procedure is called, a copy of data
is given to the procedure
Calling environment Procedure’s environment

5 5

procedure Demo(Formal ) b. and the procedure manipulates its copy.

Calling environment Procedure’s environment
Formal ← Formal + 1;
5 6

Demo(Actual);

c. Thus, when the procedure has terminated, the

calling environment has not changed.
Calling environment

Tian-Li Yu Programming Languages 23 / 45

 Imperative Paradigm

Call by Reference
a. When the procedure is called, the formal parameter
becomes a reference to the actual parameter.
Calling environment Procedure’s environment
Actual Formal
5

procedure Demo(Formal )
Formal ← Formal + 1;
b. Thus, changes directed by the procedure are made
to the actual parameter
Demo(Actual); Calling environment Procedure’s environment
Actual Formal
6

C/C++

void Demo(int& Formal){

Formal = Formal + 1; c. and are, therefore, preserved after the procedure
} has terminated.
Calling environment
Actual
6

Tian-Li Yu Programming Languages 24 / 45

 Imperative Paradigm

Functions vs. Procedures

A program unit similar to a procedure unit except that a value is transferred back to
the calling program unit as “the value of the function.”
The function header begins with
the type of the data that will
be returned.

float CylinderVolumn (float Radius, float Height){

float Volume;

Volume = 3.14 * Radius * Radius * Height;

return Volume;

}
Terminate the function and return the Compute the volume of the cylinder
value of the variable Volume
This declares a local variable
named Volume.

Tian-Li Yu Programming Languages 25 / 45

 Imperative Paradigm

The Translation Process

Lexical analyzer: identifying tokens.

Parser: identifying syntax & semantics.

Source Lexical Code Object

Parser
program analyzer generator program

Tian-Li Yu Programming Languages 26 / 45

 Imperative Paradigm

Syntax Diagrams for Algebra

Expression
+
Expression
Term -

Term
+
Term
Factor x

Factor
x

Tian-Li Yu Programming Languages 27 / 45

 Imperative Paradigm

Grammar for Algebra

Expression → Term | Term + Expression

| Term - Expression
Term → Factor | Factor * Term | Factor / Term
Factor → x | y | z

Starting: Expression
Nonterminals: Expression, Term, Factor
Terminals: x, y, z

Tian-Li Yu Programming Languages 28 / 45

 Imperative Paradigm

Parse Tree
x +y ×z
Expression

+
Term Expression

Factor Term

x x
Factor Term

y Factor

Tian-Li Yu Programming Languages 29 / 45

 Imperative Paradigm

Ambiguity
if B1 then if B2 then S1 else S2

Statement
Statement

if Boolean then else

Statement Statement if Boolean then
expression Statement
expression

B1
B1

if Boolean then
if Boolean then else
expression Statement
expression Statement Statement

B2 S1
B2 S1 S2

Tian-Li Yu Programming Languages 30 / 45

 Imperative Paradigm

Code Generation

Coercion: implicit conversion between data types

Strongly typed: no coercion, data types have to agree with each other.

Code optimization
- x = y + z;
- w = x + z;
- w = y + (z << 1);

Tian-Li Yu Programming Languages 31 / 45

 Object-Oriented Paradigm

OOP

Object
- Active program unit containing both data and procedures
Class
- A template from which objects are constructed
- An object is an instance of the class.

Instance variables & methods (member functions)

Constructors
- Special method used to initialize a new object when it is first constructed.
Destructors vs. garbage collection

Tian-Li Yu Programming Languages 32 / 45

 Object-Oriented Paradigm

An Example of Class
Constructor assigns a value
to Remaining Power when
Instance variable an object is created.

class LaserClass
{ int RemainingPower;

LaserClass (InitialPower)
{ RemainingPower = InitialPower;
}

void turnRight ( )
{ ... }

void turnLeft ( ) methods

{ ... }

void fire ( )
{ ... }

Tian-Li Yu Programming Languages 33 / 45

 Object-Oriented Paradigm

Encapsulation

Encapsulation
- A way of restricting access to the internal components of an object
- Bundling of data with the methods operating on that data.

Examples: private vs. public, getter & setter

Tian-Li Yu Programming Languages 34 / 45

 Object-Oriented Paradigm

Polymorphism

Polymorphism
- Allows method calls to be interpreted by the object that receives the call.
- Allows different data types to be handled using a uniform interface.

Circle circle;
Rectangle rect;
Circle();
Rectangle();
circle.draw();
rect.draw();

Tian-Li Yu Programming Languages 35 / 45

 Object-Oriented Paradigm

Inheritance

Inheritance
- Allows new classes to be defined in terms of previously defined classes.

Class Base; Base *base;

Class Circle : Base; Circle circle;
Class Rectangle : Base; Rectangle rect;

base = & circle;

base -> draw();
base = & rect;
base -> draw();

Tian-Li Yu Programming Languages 36 / 45

 Object-Oriented Paradigm

Concurrency
Mutual Exclusion: A method for ensuring that data can be accessed by only one process at a time.

Monitor: A data item augmented with the ability to control access to itself

Calling
program unit
procedure is Procedure
activated.

Calling program
unit requests
procedure.

Both units
excute
simultaneiously.

Tian-Li Yu Programming Languages 37 / 45

 Declarative Programming

Declarative Programming

Resolution
- Combining two or more statements to produce a new statement (that is a logical
consequence of the originals).
- (P OR Q) AND (R OR ¬Q) resolves to (P OR R)
- Resolvent: A new statement deduced by resolution
- Clause form: A statement whose elementary components are connected by OR

Unification
- Assigning a value to a variable so that two clauses would be the same.
- Unify(Father(Mark,John), Father(x,John)) results in x is Mark.

Tian-Li Yu Programming Languages 38 / 45

 Declarative Programming

Proof by Resolution (Refutation)

We know that (P OR Q) AND (R OR ¬Q) AND (¬R) is true (KB, knowledge base).
We want to prove that P is true.
Prove by showing that KB AND ¬p is unsatisfiable (empty clause).

P OR Q R OR Q R P

P OR R

empty clause

Tian-Li Yu Programming Languages 39 / 45

 Declarative Programming

Prolog
Variables: first letter capitalized (exactly contrary to common logics).
Constants: first letter uncapitalized.
Facts:
- Consists of a single predicate
- predicateName(arguments).
parent(bill, mary).
Rules:
- conclusion :- premise.
:- means “if”
- faster(X,Z) :- faster(X,Y), faster(Y,Z).
Operators:
“is”, ==,
=, <, >, +, -, *, /, =>, =<

Tian-Li Yu Programming Languages 40 / 45

 Declarative Programming Prolog

Gnu Prolog

Gnu prolog http://www.gprolog.org/

Interactive mode
- Under the prompt | ?- , type [user].
- When finished, type Ctrl-D

Comments
- /* */ or %

Chinese incompatible.

You may consult *.pl (a pure text file)

Tian-Li Yu Programming Languages 41 / 45

 Declarative Programming Prolog

Prolog Examples
female(mary).
female(sue).
male(bill).
male(john).

parent(mary,john).
bill mary parent(bill,john).
parent(mary,sue).
parent(bill,sue).

mother(X,Y):−female(X),parent(X,Y).
john sue father(X,Y):−male(X),parent(X,Y).

son(X,Y):−male(X),parent(Y,X).
daughter(X,Y):−female(X),parent(Y,X).

sibling(X,Y):−X\=Y,parent(Z,X),parent(Z,Y).

Tian-Li Yu Programming Languages 42 / 45

 Declarative Programming Prolog

Prolog Examples

Factorial again.
If we want Prolog to compute factorials, we need to tell it what factorials are.

factorial(0,1).

factorial(N,F) :−
| ?− factorial(5,W).
N>0,
W=120 ?
N1 is N−1,
factorial(N1,F1),
F is N * F1.

Tian-Li Yu Programming Languages 43 / 45

 Declarative Programming Prolog

Fibonacci Revisited

f(0,1). f(N,F) :−c(N, , ,F).

f(1,1).
c(0,0,0,1).
f(N,F) :− c(1,0,1,1).
N>0, c(2,1,1,2).
N1 is N−1, c(N,P1,P2,P3):−
N2 is N−2, N>2,
f(N1,F1), N1 is N−1,
f(N2,F2), c(N1, P0, P1, P2),
F is F1 + F2. P2 is P0+P1,
P3 is P1+P2.

How about f(40,W)?

Tian-Li Yu Programming Languages 44 / 45

 Declarative Programming Prolog

Ordered Clauses

factorial(0,1).

factorial(N,F) :−
N>0, Try these commands:
factorial(N1,F1),
N1 is N−1, listing.
F is N * F1.
trace.
?−factorial(3,W).
notrace.

This wouldn’t work, why?

Tian-Li Yu Programming Languages 45 / 45