Transcript OHP Slide Templates

Comp3104 2010-11 Programming Languages
Proposal 1 All humans possess a common
logical structure which operates independently of
language
Proposal 2 Language determines what the
individual perceives in the world and how he
thinks about it.
The Whorfian Hypothesis
“A language that doesn’t affect the way you think
about programming, is not worth knowing”
• All
computers are equivalent to a Turing Machine and
therefore are equivalent to each other.
• Computer manufacturers do not say “our machine has some
magic instruction which makes our computer more powerful
than the competition”. They say “Our machines are faster,
cheaper, and are more greener”
• All programs can be constructed using two registers and two
instructions, so all programming languages are equivalent
• Language developers admit this; they do not say “our
language has some magic feature which allows our language
to do more than in any other language”. Instead, their
advertising goes like this. “Our language is more user-friendly,
our compilers are faster and they produce smaller executable
files, and are more greener”
What languages do we know ?
Occam
SmallTalk
C++
COBOL
Ada
Java
PHP
C#
Assembler
ALGOL 60
C
Basic
Tcl
Haskell
F#
Joy
Lua
Oz
Python
Clean
Lisp
FORTRAN
FP
Pascal
Prolog
Scheme
Erlang
Criteria for Comparison
Prolog
Scheme
asm
Java
C
Criteria
Lang
Lang
Lang
Lang
Lang
Lang
Paradigm
Lang
Lang
Paradigm
Paradigm
Lang
Paradigm
Lang
Lang
Lang
Programming Paradigms
What is a “Paradigm” ?
Important
Paradigms
• Imperative (procedural)
• Declarative
• Functional
• Logic
• Object Oriented
• Event Driven
Imperative vs. Declarative (Functional)
float x;
(define (square a) (x a a))
float function square(float a) {
float b;
b = a x a;
return b;
}
x = square(3);
(square 3)
Assembler
Imperative
C
Java
Functional
Matlab
Logic
ActionScript
Object Oriented
C++
Event Driven
Lisp
Prolog
Timeline
Scheme : Definitions and Expressions
Scheme : Functions
(define (seven x)
(* x 7))
Scheme : Functions
(define (sum x y)
(+ x y))
Scheme : Conditionals (1)
(define (test x)
(cond ( (> x 0)1)
( (= x 0)0)
( (< x 0)-1)))
Scheme : Conditionals (2)
(define (test2 x)
(if (< x 0)(- x)
x))
Recursion
Recursion
See Recursion
On page 269 in the index of Kernighan and Richie’s book
The C Programming language
recursion
86,139,141,182,202,269
Recursion in Language: 5thC BC Panini Sanskrit Grammar Rules
20thC Chomsky theorizes that unlimited extension of English is possible
through the use of recursion.
… try Googling “Recursion”
There are known knowns. These are things we know that
we know. There are known unknowns. That is to say,
there are things that we now know we don’t know. But
there are also unknown unknowns. These are things we
do not know we don’t know
US Defense Secretary Donald Rumsfeld on February 12,
2002
Little harmonic Labyrinth
Scheme : Recursion : The Factorial Function (1)
How many ways can you get n people to sit in n chairs ?
n = 3. (A,B,C)
n = 4. (A,B,C,D)
Scheme : Recursion
sum the numbers 1 to N
(e,g, 1 to 4)
(define (sum n)
(if (= n 1)1
(+ n (sum(- n 1)))))
4+3+2+1
= 4 + (3 + 2 + 1)
= 4 + 3 + (2+1)
= 4 + 3 + 2 + (1)
(sum 4) =
4 + (sum 3) =
Scheme : Recursion (2) The Factorial Function
(define (fact n)
(if (= n 1)1
(* n (fact (- n 1)))))
Functional Recursion // Imperative Iteration
(define (fact n)
(if (= n 1)1
(* n (fact (- n 1)))))
I lost the number of my new mobile phone
How can I find the number ? Get my girlfriend to phone every
single mobile number. (OK I’ll cook supper!)
Approximate solution: Say a mobile number has 10 digits
(actually 11) and each digit can be 0 – 9 (10 possibilitities). So
the solution is 10! How long will this take? Calculatore!
Fundamental Principles of Recursion
A recursive function must call a simplified version of itself.
This is guaranteed to “bottom out” (to halt). Any call to itself
would produce an infinite regress.
Don’t run this … ah go on then ..
(define (fact n)
(if (= n 1)1
(* n (fact n))))
... and wait for the error message ... or worse
Recursion in Language
ornate
noun
begin
article
fancy
noun
begin
adjective
noun
end
verb
fancy
noun
fancy
noun
verb
relative
pronoun
ornate
noun
end
preposition
fancy
noun
Recursion in Language
ornate
noun
begin
article
fancy
noun
begin
adjective
noun
end
verb
fancy
noun
fancy
noun
verb
relative
pronoun
ornate
noun
end
preposition
fancy
noun
Recursion in Language
begin
article
adjective
noun
end
verb
fancy
noun
fancy
noun
verb
relative
pronoun
begin
ornate
noun
end
preposition
fancy
noun
Recursion is not Self-Reference
A recursive function makes reference to a simplified version
of itself: (I am) better than what (I was)
I’m the humblest person I know
I never make misteaks
“I never make predictions. I never have and I never will”
This sentence contains five words
This sentence no verb
Compilers - Parsing
A
(
A
)
+
A
var
A
)
(
+
var
Statement
var
=
expression
Expression
+
term
-
+
term
-
Term
var
num
(
expression
)
Prolog Syntax Sheet
Facts and Rules
parent(abraham, isaac).
Fact. Lower case for names.
parent(isaac, esau).
Fact. Lower case for names.
grandfather(X,Y) :- parent(X,A),parent(A,Y).
Rule. If X is the grandfather of Y then X is the parent of A and A is the
parent of Y. For example, if george “X” is the parent of colin “A” and colin “A” is the
parent of tristan “Y” then george “X” is the grandparent of Tristan “Y”.
Queries
?- parent(abraham,X).
The capital X designates an “output” variable which will be all sons of
Abraham.
?- grandfather(abraham,X).
The capital X designates an “output” variable which will be all grandchildren
of Abraham.
lectures(colin,3063).
lectures(colin,3079).
lectures(pete,3078).
lectures(richard,3062).
lectures(richard,3040).
studies(tom,3063).
studies(tom,3062).
studies(kate,3063).
studies(kate,3040).
studies(kate,3062).
?- lectures(colin,Mo),studies(kate,Mo).
?- lectures(colin,Mo),studies(X,Mo).
Monty Python Holy Grail
witch(X) :burns(X),female(X).
burns(X) :- wooden(X).
wooden(X) :- floats(X).
wooden(woodBridge).
stone(stoneBridge).
floats(bread).
floats(apple).
floats(cherry).
floats(X) :sameweight(duck, X).
female(girl).
sameweight(duck,girl).
?- witch(girl)
Monty Python Holy Grail
Yes
[trace] 12 ?- witch(girl).
Call: (7) witch(girl) ? creep
Call: (8) burns(girl) ? creep
Call: (9) wooden(girl) ? creep
Call: (10) floats(girl) ? creep
Call: (11) sameweight(duck, girl) ? creep
Exit: (11) sameweight(duck, girl) ? creep
Exit: (10) floats(girl) ? creep
Exit: (9) wooden(girl) ? creep
Exit: (8) burns(girl) ? creep
Call: (8) female(girl) ? creep
Exit: (8) female(girl) ? creep
Exit: (7) witch(girl) ? creep
Yes
Coda
It is easier to write an incorrect program
than to read a correct one.
There are two ways to write error-free
programs, only the third one works.
It is easier to change the specification to
fit the program than vice-versa
Why did the Roman Empire collapse? What is
the Latin for “office automation” ?