[ previous | schedule | next ]
I used many information resources in compiling this
material. They are listed at the bottom of
this page.
There have been thousands of programming languages developed and used over the years. I even helped develop and implement one myself (See the ACM journal Transactions on Modeling and Computer Simulation, Volume 1 Number 2, 1991).
They can be classified into a handful of programming paradigms. A paradigm is a model for thinking about something.
Most languages follow the procedural (aka imperative) paradigm. Java is an example. Such languages follow the viewpoint that programs are sequences of detailed instructions. Variables are associated with memory locations and values are stored into and fetched from these locations for use in sequential, conditional and iterative operations. Procedural languages are abstractions of assembler and machine languages and as such are founded on the Von Neumann machine architecture.
We will look at examples of a number of procedural languages. There will be a handout for each languages containing an example program in that language. These examples will not be included on the web because most are photocopied from various books.
We will also look at two alternative language/programming paradigms: functional and logic, with Scheme as an example of the former and Prolog as an example of the latter. Link to notes on Scheme. Link to notes on Prolog.
See http://www.frank-buss.de/challenge/ to compare numerous solutions to the same problem, written in a variety of languages (Lisp, C, C++, Java, Haskell, Python, etc).
Selected Procedural Programming Languages at a Glance
Anytime you have to select illustrative programming languages, someone will be offended by the omissions. C'est la vie. These are languages which are considered significant and for which I have ready reference material. Over the nearly 30 years since I took my first computer science course, I have written at least one program in all these langauges except C#.
Languages are grouped by the decade with which they are normally associated.
--------------------------------------------- 1950s ------------------------------------------------------
FORTRAN FORmula TRANslator
Genesis: memo from IBM employee John Backus to his boss in December 1953 suggesting that a high level programming language be developed for algebraic and other mathematical applications. The first compiler was released in 1957.
Motivation: The motivation was to address the high cost of developing and debugging assembler language code. It was originally thought that FORTRAN would "virtually eliminate coding and debugging".
Significance: More code for scientific and technical applications
has been written in FORTRAN than in any other language. It has been
adapted regularly over the years and an object-oriented dialect now exists.
COBOL COmmon Business Oriented Language
Genesis: A meeting at Pentagon in May 1959 between DoD officials, representatives from computer manufacturers and consultants. The first compiler was released in late 1960.
Motivation: The motivation was to quickly make available a common programming language for business applications. They wanted programs that were readable by non-technical personnel and therefore to be written in something close to English natural language.
Significance: More code has been written in COBOL than
in any other language. It has been adapted somewhat over the years
and an object-oriented dialect now exists.
ALGOL ALGOrithmic Language
Genesis: A petition by professional programmer user groups to the ACM (the leading computer science professional organization) in 1957 to develop a universal programming language. The initial language design appeared in 1958 with subsequent major revision in 1960 (Algol 60).
Motivation: The motivation was to address the plethora of new programming languages which seemed to spring up with every new computer system and application. None of the languages were based on a theory of design. A well designed universal language would facilititate the communication of algorithms and programs among users worldwide.
Significance: The first language with a theoretically sound
design, ALGOL has provided the syntactic basis for most subsequent procedural
languages. Prior languages were very punch-card oriented, with one
statement per line. ALGOL introduced free format.
--------------------------------------------- 1960s ------------------------------------------------------
BASIC
Genesis: BASIC was developed at Dartmouth College in 1964 for use by its undergraduate students.
Motivation: Their motivation was to provide a simple programming language that could be easily learned and used by the many nonscience students at Dartmouth.
Significance: The first language designed for time-sharing
(e.g. interactive) rather than batch processing. It was implemented
as an interpreter rather than a compiler. It was also the programming
language provided with the first generation of personal computers which
became available starting in 1975. Bill Gates' first Microsoft product
was a Basic interpreter.
PL/I Programming Language I
Genesis: PL/I was developed at IBM for release in conjunction with its revolutionary new operating system OS/360. The initial language design was completed in 1964 and the first compiler in 1965.
Motivation: The motivation was to provide IBM customers a single language to fit all their application programming needs, from scientific to business.
Significance: Worst case of feature bloat in the history
of computing. It tried to be all things to all people and the language
was subsequently so complex that no one could understand it all and the
compilers never generated reliable code.
SIMULA SIMULAtion language
Genesis: Work by Kristen Nygaard and Ole-Johan Dahl of the Norwegian Computing Center in 1961. The SIMULA I compiler was implemented in 1964. The next major revision of the language was SIMULA 67, which included the "class" construct. The first SIMULA 67 compiler was implemented in 1969.
Motivation: The motivation was to have a programming language which could serve the special requirements of simulation programming. This included support for concurrency and the specification of processes.
Significance: SIMULA 67 is the mother of all object-oriented
programming languages from Smalltalk to C++ to Java and beyond.
--------------------------------------------- 1970s ------------------------------------------------------
Pascal Blaise Pascal, French mathematician and philosopher
Genesis: Pascal was developed by Niklaus Wirth at The Swiss Federal Institute of Technology in the late 1960s. It first saw widespread use in the mid 1970s.
Motivation: His motivation was to provide a simple language with sound theoretical design for teaching introductory programming. The design of Pascal was based on ALGOL.
Significance: Probably the best non-object-oriented language
for teaching procedural programming. A few universities still use
it, and some left it behind only quite recently.
C
Genesis: Brian Kernighan and Dennis Ritchie developed this language at AT&T Bell Laboratories in the early 1970s. It was a successor to the BCPL language.
Motivation: The motivation was to have a higher level language than assembly language for implementing the UNIX operation system which they were developing at the same time. There were obviously other high level languages available, but their demands required a language uniquely designed for systems programming -- including features for both very abstract and assembly-level operations.
Significance: C is the successor to FORTRAN as the language
of choice for scientific and technical applications. It is almost
universally used for implementing system software due to its very high
performance characteristics (C compilers produce very fast code).
--------------------------------------------- 1980s ------------------------------------------------------
C++
Genesis: Bjarne Stroustrup developed this extension to C at AT&T Bell Laboratories starting in 1979, implementing it as a C compiler preprocessor. The first C++ compiler was released in 1985. C++ is a legal expression in C which means to increment the value stored in variable C.
Motivation: His motivation was to have a nice SIMULA-like language to implement simulation programs. As a native Scandinavian, Stroustrup had experience programming in SIMULA 67.
Significance: C++ is the most popular language to offer
both object-oriented features and very high performance. It is used
to write both applications and system software.
Ada Augusta Ada Byron, Countess of Lovelace, Charles Babbage's "programmer"
Genesis: Ada was designed at the Department of Defense in the mid 1970's. First complete version published in 1983.
Motivation: Their motivation was to provide a universal language for DoD projects. Such a language and compiler must include strict compile-time checking and runtime exceptional handling features, so the software could reliably run in embedded real-time environments such as sophisticated weaponry.
Significance: Prime example of design by committee.
Its Package feature exemplified the encapsulation principle of object-oriented
programming (further OO support was added in the 1995 language revision).
DoD required its contractors for many years to program in Ada but not so
much any more. Used by a small but influential group of universities
to teach introductory programming.
--------------------------------------------- 1990s ------------------------------------------------------
Perl Practical Extraction and Report Language
Genesis: Developed by Larry Wall, a UNIX programmer, in 1986, along with its interpreter. It now runs as a hybrid compiler/interpreter much like Java does.
Motivation: The motivation was to provide a high level language for efficiently manipulating the contents of text files and generating reports. It is well suited for pattern matching and other text processing.
Signficance: Heavily used for server-side processing of Web forms.
It is extremely portable and is used primarily as a scripting language.
Java
Genesis: Bill Joy and James Gosling at Sun Microsystems designed Java in 1993 as successor to their unsuccessful Oak language. It became available in 1995.
Motivation: Their motivation was to provide a very portable language for programming networked information appliances. They wanted to adopt the best of C++ while avoiding its level of complexity, dubbed the “C--" approach.
Significance: Java and its Javascript dialect have become
very popular for programming web-based applications. It is also a
nice alternative to C++ for teaching beginning programming!
--------------------------------------------- 2000s ------------------------------------------------------
C# C-sharp
Genesis: Developed by Microsoft around the turn of the century.
Motivation: Their native language for the emerging .NET programming platform for network-enabled applications software. Its heritage is C++. This is the Microsoft alternative to Java.
Signficance: Has rapidly risen as a developer's tool of choice, particularly when used
with Visual Studio.
Python
Genesis: Developed by Markus Fleck originally in 1990-91 but did not attract widespread attention until 2002 or so.
Motivation: Wanted an extensible, object oriented scripting language with simple syntax (statements are grouped through indentation!) and loose typing but also the ability to tap into OS system calls.
Signficance: Is being adopted by adventurous computer science educators as an introductory language. Emerging as a tool for both
client- and server-side web programming. Also the most widely used
programming language to be named after a British comedy troup.
Functional programming with Scheme
Functional languages support a conceptually pure view of computing.
Lisp is the original
Scheme is a popular dialect of Lisp
All examples and classroom demonstration are performed using the
popular (and free), DrScheme software. See http://www.drscheme.org
Lists and Expressions are basic structures
Examples:
( list 1 2 3 ) This list consists of three numbers
( list (list 1 2) 3 ) This list consists of a
sublist and a number
( list (list 1) (list 2) (list 3) ) This list consists
of three sublists
(+ 1 2 ) This is a call to procedure “+” with arguments
1 and 2.
(car (list 1 2 3) ) This is a call to procedure “car”
with argument (list 1 2 3)
(cdr (list 1 2 3) ) This is a call to procedure
“cdr” with argument (1 2 3)
(cons 1 (list 2 3) ) This is a call to procedure
“cons” with arguments 1 and (list 2 3)
Procedures demonstrated in above examples are:
list
- Takes zero or more args, all values
- Result is list consisting of those values
- Example: ( list 1 2 3 )
car : Contents of Address Register (IBM 704)
- Result is first list value
- Example: ( car (list 1 2 3 ) ) is 1
cdr: Contents of Data Register (IBM 704)
- Result is list with first value removed
- Example: ( cdr (list 1 2 3 ) ) is (list 2 3 )
cons: CONStruct
- Takes two args, a value followed by a list
- Result is list having first arg as head
- Example: ( cons 1 (list 2 3 ) ) is (list 1 2 3 )
Notice that car and cdr are used to break down lists and cons is used to build up lists.
What is the value of:
(car ( cdr ( cdr ( list 1 2 3))))
What is the value of:
(car (cons 1 (list 2 3)))
What is the value of:
(cdr (cons 1 (list 2 3)))
What is the value of:
(cons (car (list 1 2 3)) (cdr (list 1 2 3)))
Lambda Expressions
Expression that defines a procedure!
General format:
(define (name parameters) (expressions))
Where
- define is keyword that tells Scheme you are defining
a procedure
- name is procedure name
- parameters is 0 or more formal parameters
- list of expressions is procedure body
--------------- optional: why called “lambda expressions”?-----------------
Procedures are actually defined as anonymous lambda expressions:
(lambda (parameters) (expressions))
then the lambda expression is associated with the procedure name by
making it the second argument in a define:
(define name lambda-expression)
Substituting the first into the second, we get the long version of the
named procedure definition:
(define name (lambda (parameters) (expressions)))
This is used so frequently that Scheme allows the shorthand version
(define (name parameters) (expressions))
-----------------------------------------------------------------------------------
Example: procedure that takes one parameter and calculates its square
(define (square x) (* x x))
Once the procedure is defined, we can call it:
(square 5) This calls procedure “square” with argument
5.
How about 5 to the 4th power (5 squared squared)?
(square (square 5))
How about 5 to the 8th power (5 squared squared squared)?
(square (square (square 5)))
Conditional Expressions
The if-then-else construct. General format is:
(cond ((condition) then-part) (else
else-part) )
- cond and else are keywords
- condition is boolean expression
- then-part is expression
- else-part is expression
Example: define procedure to return larger of its two arguments
(define (larger x y)
(cond ((> x y) x) (else y)))
Example: procedure to compute sum of all values in list, using cond.
See Figure 9.9 on page 449 of textbook (3rd edition).
(define (adder input-list)
(cond ((null? input-list) 0)
(else(+ (car input-list)
(adder (cdr input-list))))))
Procedure adder takes one argument, a list. The procedure body
consists of one “if statement”.
You can read it as this: If the list is empty, return 0, else
return the “+” of the first list item with the sum of the remaining list.
Yeow, a recursive definition!
It’s logical if you think about it.
The sum 1+2+3+4 is just 1+ the sum 2+3+4, right? e.g. 1+9.
9, the sum 2+3+4, is just 2+ the sum 3+4. e.g. 2+7
7, the sum 3+4, is just 3+ the value 4. e.g. 3+4
The approach is to use car to strip off the first value of a list, apply adder to the remainder (cdr) of that list and when adder comes back with its result, add the two together using +.
But we can’t keep using car and cdr forever, because eventually the list becomes empty! When that happens, (null? Input-list) becomes true and we return the sum of 0.
Work through it step by step:
Big note: looping occurred here! Scheme does looping through a combination of “if” and recursive calls.
----------------------- optional -----------------------------------------
Alternatively can use if instead of cond. General form:
( if (condition) then-part else-part )
- if is keyword
- condition is boolean expression
- then-part is expression
- else-part is expression
The choice is yours, you can have keyword “if” or you can have keyword “else”, but not both. However, cond allows else-if’s where if doesn’t.
Example: define procedure to return larger of its two arguments
(define (bigger x y)
(if (> x y) x y))
Example: procedure to compute sum of all values in list, using if.
(define (sum input-list)
(if (null? input-list) 0
(+ (car input-list)
(sum (cdr input-list)))))
This works the same way as the previous example.
-------------------------------------------------------------------------------------
SOME FACTS AND DEFINITIONS
· Prolog means "Programming in Logic"
· Originally designed for natural language processing and theorem
proving
· This is a declarative rather than a procedural style of programming
· Language structure is extremely simple
· All programs are really databases, blurring the distinction
between program and data
Logic is expressed as a set of facts and rules.
· A fact states a relationship between two things. A fact
is always true.
· A rule has the form “if Q then P.” Boolean expression Q is evaluated
and if true, P becomes true otherwise P becomes false.
· After facts and rules are established, computation is triggered
by queries (a.k.a. goals)
· Queries are entered interactively at command prompt
· Prolog attempts to satisfy the query based on facts and rules.
Process is called unification.
______________________
Amzi! Corporation offers a number of Prolog-related
products. Their premier product is Amzi!
Prolog+Logic Server, which you can download for a free 180-day trial.
______________________
Enough already! Let's look at an example.
______________________
EXAMPLE: FAMILY RELATIONSHIPS
Here are some Prolog facts, based on my family and my wife Nancy's family:
mother(iva, pete).
mother(iva, ed).
mother(iva, becky).
mother(kay, nancy).
mother(kay, bob).
mother(kay, diane).
husband(dwight, iva).
husband(robert, kay).
husband(pete, nancy).
The line "mother(iva,pete)." is read" "iva is the mother of pete."
Now, introduce a rule.
wife(X,Y) :- husband(Y,X).
Read it as "wife(X,Y) is true if husband(Y,X) is true." Or, "X is the wife of Y if Y is the husband of X". X and Y are variables, which begin with upper-case letters in Prolog.
Here is a second rule.
father(X,Y) :- husband(X,Z), mother(Z,Y).
Read it as "X is the father of Y if, for some Z, X is the husband of
Z and Z is the mother of Y." We'll skip the social implications of
this rule.
Given these facts and rules, we can now issue some queries. In Amzi Prolog, queries are entered by starting up a listener (window with interactive command line interpreter). The query prompt is: ?-
In the interactions below, Prolog responses will be in italics.
We start by telling it to consult our set of facts and rules. Assume they were stored under the file name: FAMILY.PRO.
?- consult('FAMILY.PRO').
yes
?-
Note that query syntax is similar to fact/rule syntax. Also, it must end with a period.
If our query can be matched to a fact, it is trivially true. For example:
?- mother(kay, nancy).
yes
?-
Queries can also be matched to a number of facts. Consider the
query: mother(kay, Who).
Who is a variable. Prolog will attempt to find all possible values
of Who for which the query succeeds.
?- mother(kay, Who).
Who = nancy
If no matches are found, the system responds "no" If at least one match is found, it responds with the first match, as shown above. It then waits for you to respond. If you press the ENTER key, it will abandon the search and issue another query prompt (it will also respond "yes" because there were additional matches -- bob and diane -- that you did not see).
?- mother(kay, Who).
Who = nancy <-- you press ENTER
here
yes
?-
If you press the SEMICOLON key (;) instead, it will continue the search and present the next match.
?- mother(kay, Who).
Who = nancy ; <-- you press SEMICOLON
here
Who = bob
If you continue to press SEMICOLON, eventually the list will be exhausted and it responds with "no" then issues the next query prompt.
The unification process really kicks in when you issue a prompt like:
father(dwight, Who).
What would you expect the response to be?
Suppose you wanted to add a new rule to define the "parent" relationship? Logically, I'd express this as "X is a parent of Y if X is the mother of Y or X is the father of Y." The "or" relationship is expressed using ";" (rather than "," for and)..
History of Programming Languages, R.L. Wexelblat (editor), Academic
Press, 1981.
An Invitation to Computer Science, G. Michael Schneider and
Judith L. Gersting, Brooks/Cole, 2000.
The Design and Evolution of C++, Bjarne Stroustrup, Addison
Wesley, 1994.
The C Programming Language, Brian Kernighan and Dennis Ritchie,
Addison Wesley, 1978.
Ada: An Advanced Introduction, Narian Gehani, Prentice-Hall,
1984.
An Introduction to Programming and Problem Solving with Pascal,
Michael Schneider, et al, Wiley, 1982.
The LIttle Schemer (4th edition), Daniel Friedman and Matthias
Felleisen, MIT Press, 1996.
Programming Perl, Larry Wall, et al, O'Reilly & Associates,
1996.
Introduction to Programming Languages, Wesley Peterson, Prentice-Hall,
1974.
Computer Science: FORTRAN Language Programming, Alexandra Forsythe,
et al, Wiley, 1970.
Introduction to SIMULA 67, Gunther Lamprecht, Vieweg, 1983.
A Programmer's Introduction to C#, Eric Gunnerson, APress, 2000.
Fundamentals of COBOL programming, Carl Feingold, WC Brown,
1973.
Several web pages were consulted to fill in some gaps. Here is an interesting one: http://www.aaxnet.com/info/hist.html
All the above books are available for you to borrow from my personal collection.