Transcript PPT

Imperative and functional programming languages
UC Santa Cruz
CMPS 10 – Introduction to Computer Science
www.soe.ucsc.edu/classes/cmps010/Spring11
[email protected]
2 May 2011
Homework #3
 Canceling this homework assignment: not due Wednesday
 More details on the new HW#3 assignment Wednesday
 Will update the syllabus to reflect this change once new
assignment is complete
UC SANTA CRUZ
Recap
 Programming languages evolved to address the
difficulty of writing machine code
 Assembly language developed as a faster way to
write machine code, maps very directly
 High level programming languages developed
to make it easier to write programs, reduce the gap
between human thinking and program code
 Compilation process
 A programmer writes the source code of a program
 Source code: A file of text with programming language
instructions
 A program called a compiler converts this text into
assembly langauge
 An assembler then converts the assembly language
into machine code
source code
compiler
assembly
assembler
machine
code
Microprocessor hardware can
understand and execute
UC SANTA CRUZ
Different styles of programming language
 Imperative
 Each statement is executed in order
 Each statement modifies the state of the program
 Program state is the set of values of all variables
 In language, the imperative form of verbs is the one where you are giving
orders: go there, do this, come back now.
 Similarly, imperative programs involve the programmer ordering the computer
to perform an algorithm, every step spelled out
 In widespread use, examples include: C, C++, C#, Java, FORTRAN, PHP, many
others
 Functional
 Statements define functions
 A function only produces actual values if it is used; otherwise just remains as a
definition
 Function definitions are self-contained, and have no side-effects
 Execution environment is free to pick best ordering of program statements
 Of growing interest, but still mostly used in unversities.
 Examples include Haskell, Miranda
UC SANTA CRUZ
Examples
 Consider code to add a series of integers from 1 to some
number n
Imperative
int sum_to_n(int n)
int sum = 0
int j = 0
sum = sum + j
}
return sum
// input is integer n
sumInt n | n==0
| n>0
=0
= n + sumInt(n-1)
// will use j as a counter
while (j <= n) {
j=j+1
Functional
Defines a base case (n=0), where the
output of the function is 0 when n=0.
Remaining cases are defined recursively:
the current sum is the current value of n
plus the value of the sum as of the
previous value of n (n-1)
UC SANTA CRUZ
Programs started small…
 In the early days of high level
programming languages, programs were
small
 Limited computer memory meant that
programs couldn’t grow very big
 Slow processing speed meant that programs
couldn’t run very fast
 The lack of good editing and debugging tools
meant that writing large programs was
tedious
 Before the hard disk drive, managing large
stacks of paper punched cards was tedious
 A common fear was dropping a card stack on
the floor, losing card order
Programmer standing by punched
cards
62,500 punched cards, representing the
control program for the SAGE system, ca.
1955
www.computerhistory.org/revolution/story/326
UC SANTA CRUZ
… but got larger
 Over time, the desire to make computer programs have more functionality
led to larger and larger programs.
 This created a problem of how to structure the software
 That is, how do you clump together related statements inside a large program?
 Evolutionary path
 Unstructured code
 Use of IF and GOTO to control flow of software
 Partially structured code
 Subroutines/procedures, but also use of GOTO
 Procedural code, block structuring
 Use of GOTO deprecated, all code inside procedures, basic blocks
 Data may or may not be co-located with code that operates on it
 Object-oriented
 Cluster code and associated data together into objects
UC SANTA CRUZ
Unstructured code
 Consider the following example of FORTRAN II code:
C AREA OF A TRIANGLE WITH A STANDARD SQUARE ROOT FUNCTION
C INPUT - CARD READER UNIT 5, INTEGER INPUT
C OUTPUT - LINE PRINTER UNIT 6, REAL OUTPUT
C INPUT ERROR DISPLAY ERROR OUTPUT CODE 1 IN JOB CONTROL LISTING
READ INPUT TAPE 5, 501, IA, IB, IC
501 FORMAT (3I5)
C IA, IB, AND IC MAY NOT BE NEGATIVE
C FURTHERMORE,THE SUM OF TWO SIDES OF A TRIANGLE
C IS GREATER THAN THE THIRD SIDE, SO WE CHECK FOR THAT,TOO
IF (IA) 777, 777, 701
701 IF (IB) 777, 777, 702
702 IF (IC) 777, 777, 703
703 IF (IA+IB-IC) 777,777,704
704 IF (IA+IC-IB) 777,777,705
705 IF (IB+IC-IA) 777,777,799
777 STOP 1
C USING HERON'S FORMULA WE CALCULATE THE AREA OF THE TRIANGLE
799 S = FLOATF (IA + IB + IC) / 2.0
AREA = SQRT( S * (S - FLOATF(IA)) * (S - FLOATF(IB)) *
+
(S - FLOATF(IC)))
WRITE OUTPUT TAPE 6, 601, IA, IB, IC, AREA
601 FORMAT (4H A= ,I5,5H B= ,I5,5H C= ,I5,8H AREA= ,F10.2,
+
13H SQUARE UNITS)
STOP
END
Arithmetic IF:
if (num) Sneg, Szero, Spos
If the number is negative, goto line
Sneg. If the number is zero, go to
Szero, etc.
Source: Wikipedia
UC SANTA CRUZ
Problem with unstructured code
 What if we wanted to write a large program, and compute
the area of a triangle in many places?
 Could just repeat the lines of code that compute the area
 But, this is wasteful (the same code is in memory multiple times)
 Worse, if you need to update the formula, need to do this in many
places
 This is known as the code clone problem
main
code
procedure
 Ideally would like to have the program go to the lines that
compute the area, then return back to the place in the code that
needed this
 Requires:
 Ability to save the current location
 Ability to go to another place in the software, and perform some
operation (compute area of triangle, for example)
 Ability to return to the saved location after performing the operation
 Problem: in early FORTRAN, there was no way to save the current
location or return to a given location
UC SANTA CRUZ
Procedures
 The first main way to structure code was to introduce
procedures
 These are sections of code that perform a distinct operation
 Many places in the software can ask a procedure to perform its
operation
 Within a procedure, can have variables whose values are local to the
procedure
 I.e., can have a variable named j in the main program, an one named j in
the procedure – the procedure’s j is different from main’s j
 A major advance





A large piece of software can be subdivided into multiple procedures
Each procedure can focus on doing one thing well
Related procedures can be clustered together in a large program
Makes software easier to understand and easier to write
Allowed software to grow larger
UC SANTA CRUZ
Example of procedural code
 Here is the area of a triangle again, in the language C
int main(int argc, char *argv[])
{
int a, b, c;
printf(“\nSide A: ");
scanf("%d", &a);
printf(“\nSide B: ");
Here is where the procedure
scanf("%d", &b);
is called
printf(“\nSide C: ");
scanf("%d", &c);
printf(“\nThe area of the triangle is: %f\n", area(a, b, c));
return(0);
}
Here is the procedure for computing the
area of a triangle. Though called only once,
float area( int a, int b, int c )
it could be called from many places in the
{
code, and could easily be reused in another
int s;
program.
float y;
Note that variables a, b, c in the procedure
s = (a + b + c)/2;
are different variables (but, since they are
y = sqrt( s * (s - a)*(s - b)*(s - c) );
passed to the procedure, the same values)
return( y );
as the variables a,b,c in the main program.
}
UC SANTA CRUZ
Organization of a procedural program
 In a procedural program
 Functionality is described by source code statements inside
procedures
 Data is either local to a procedure, or is global, and can be access by
the entire program
 Local: inside a procedure
 Global: outside a procedure
program
procedure
data (local)
= contains
data
(global)
code
UC SANTA CRUZ
Procedural organization in the file system
 Today, procedural programs are written down as lines of text
inside multiple text files
 Each file can contain global data and procedures
 That is, all of the global data is split up among multiple files
program
= contains
source code file
procedure
data (local)
data
(global)
code
UC SANTA CRUZ
Problems with procedural organization
 In well-organized procedural code:
 Related procedures and their associated global data are co-located in
the same file
 One file holds global data for the entire system
 But, there is nothing to enforce or even encourage this good
organization
 Consider a stack
 Procedures for push, pop and creating a new stack can be in the same file
 A global variable can hold the stack’s contents
 Also possible
 Files hold procedures that are both related and unrelated to each
other
 Some procedures are very large, and have many different functions
 Procedures in one file use global data defined in another
 Can be very hard to determine which procedures are using which data
UC SANTA CRUZ
Object-oriented software
 Object-oriented software gathers together procedures and
their associated data into a class
 This is the same notion of class as the class boxes from the data
modeling homework, #2
 For example, a stack class would have:
 Procedures for push, pop
 A data item for the contents of the stack
 In object-oriented software, global variables are deprecated
 It is still possible to have global variables, but ideally the use of such
variables will be limited
 And, in any event, most OO languages require such data to be inside a
class
UC SANTA CRUZ
Organization of Object-oriented code
 An object-oriented program is organized into a set of classes
 Each class contains code, and data related to that code
 Any global data is put into one (or more) classes
 Depending on language, one file holds one class, or one file can hold
multiple classes
 Classes can typically also contain classes (these are called inner classes)
program
= contains
class
procedure
data
UC SANTA CRUZ
Object-oriented code: pros and cons
 Benefits:
 Easier to understand an individual class, since related code and data are
clustered
 Changes to a class are more likely to have an effect that is local to that class,
due to better encapsulation of data and code
 Clustering of data+code into classes allows for more complex relationships
between classes, hence greater expressivity
 It is easier to create very large software systems using OO code than with
purely procedural code
 OO classes support inheritance, which makes it easy to create code
specialized for specific situations
 Drawbacks:
 Greater range of relationships among classes leads to OO code being more
complex than procedural code, on average
 Watch:
 Dan Ingalls on emergence of Object Oriented programming
 http://www.youtube.com/watch?v=wsvvQm511B4
UC SANTA CRUZ
Summary
 Imperative
 Procedural
 C, FORTRAN (older versions)
 Object-oriented
 C++, Java, C#, PHP, Smalltalk
 Functional
 Haskell, Miranda
 Logic programming (not covered in class)
 Prolog
UC SANTA CRUZ