Transcript ppt

Prof. Charles Antony Richard
Hoare
Tony Hoare
Born in Colombo (Sri Lanka)
British parents
Oxford (England)
University of Oxford:
Hoare studied:
• Philosophy
• Latin and Greek
• Bacherol Degree in
1946
• Extra year: Statistics
Moscow (Russia)
Hoare studied:
• Russian (in the Royal
Navy)
• Statistics
• a programming
course
University State of Moscow
- machine translation of languages
- probability theory
Back to England (London) in 1960
Elliot Brothers (a small scientific computer
manufacturer)
First task: Elliot 803
• Implementation of the method for internal sorting
invented by Shell
• Hoare believed he had a faster method
Elliot 503 (the companie´s next computer)
Goal: Design the language
• Course on the language Angol 60 (in Brighton - England )
• First contact with recursive procedures
• Wrote the procedure of Quicksort
New direction: Implementation of Algol 60
(Hoare was invited to the group with responsibility for
maintenance and development of Algol.)
Back to Elliot Brothers...
• Hoare was leading a team of 15
programmers
( task: Implementation of an operating system to the
Elliot 503 computer)
• Promoted to Chief Engineer
( task: responsible for development and design of the
company´s products)
Hoare left the industry
what was the reason?
- Hoare proposed once that a programming language
definition should be formalized as a set of axioms instead
of a just a functional notation.
- But he did not see how actually to do it.
Long Term research?
Research at Queen´s University (Belfast)
(1968-1977)
- Theory of Programming and Languages
Hoare Logic
Instantiation axiom
{p[t/y]} y:=t {p}
For example:
{y+5=10} y:=y+5 {y=10}
{y+y<z} x:=y {x+y<z}
{2*(y+5)>20} y:=2*(y+5) {y>20}
Composition rule
{p} S1 {r}
{r} S2 {q}
________________________________________________________________________
{p} S1;S2 {q}
For example: if the antecedents are
1. {x+1 = y+2} x := x+1 {x=y+2}
2. {x = y+2} y := y+2 {x=y}
Then the consequent is
{x+1 = y+2} x := x+1; y := y+2 {x=y}
While rule
{p/\e} S {p}
________________________________________________________________________
{p} while e do S od {p/\¬e}
Assertions example
{x>=0 /\ y>=0}
a:=0;
b:=x;
while b>=y do
b:=b-y;
a:=a+1
od.
{x=a*y+b/\b>=0/\b<y}
Back to Oxford University
(1977)
Continuation of the research leads to:
• CSP (Communicating Sequential Processes)
1980 – Receives Turing Award
For his fundamental contributions to
the definition and design of
programming languages
Back to Industry (1999)
Senior researcher with Microsoft Research in Cambridge