Transcript Presentation1A

“A language that doesn’t affect the way you think
about programming, is not worth knowing”
Some Initial Thoughts, and Recap
• From the Church-Turing thesis all computers are equivalent to a Turing
Machine and therefore are equivalent to each other.
• Computer manufacturers admit this; they do not say “our machine has
some magic instruction which makes our computer more powerful than the
competition”. Their advertising goes like this: “Our machines are faster,
cheaper, easier to program and are more greener”
• From the Church-Turing thesis all programs can be constructed using
two registers and two instructions, so all programming languages are
equivalent in expressibility (power,…)
• 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”
Why are these two instructions so
fundamental?
decjmpreg reg,lab
inc reg
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
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
OO
Imperative
Functional
Logic
Imperative vx. Declarative
float x;
(define (square a) (x a a))
float function square(float a) {
(square 3)
float b;
b = a x a;
return b;
}
x = square(3);
Assembler
Imperative
C
Java
Functional
Matlab
Logic
ActionScript
Object Oriented
C++
Event Driven
Lisp
Prolog
Generations
1st
Machine – level (switches)
2nd
Assembler
3rd
Programmer-friendly: C++,
Java, FORTRAN, COBOL
4th
Application: SQL, SPSS
5th
Constraint: Prolog, OPS5 (AI)
Paradigms: Imperative
• Focus on dynamic aspect of computation – operational semantics
• Specifies step-by step what must be done
Pure Forms
• Godel’s purely descriptive recursive function formalism
• Realized by Mc.Carthy’s Lisp
• Turing’s Imperative formalism
Paradigms: Functional
Paradigms: Logic
Paradigms: Object Oriented
Paradigms: Event Driven
Using conditional expressions to
define recursive functions
Thesis: All computable functions can be defined by the
recursive use of conditional expressions.
if p then a else b
n! = g(n,1)
where
g(n,s) = if n = 0 then s else g(n – 1, n x s)
Equivalence of imperative and
functional programming
Flow Diagrams: Turing Von
Neumann and McCarthy
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.
Recursion
Recursion
See Recursion
On page 269 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
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
)
Back to the “Timeline”
Our contemporary languages have evolved (?)
or have developed (?) from languages of the
past. What will our future languages look like?
In other words what are our future computing
needs (or desires) ?
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” ?
to tree :size
setpencolor [255 000 000]
if :size < 5 [stop]
fd :size
lt 30 tree :size*0.7
rt 60 tree :size*0.7
lt 30 bk :size
end