# Do Extraterrestrials Use Functional Programming? ... Manuel M T Chakravarty University of New South

date post

18-Apr-2020Category

## Documents

view

1download

0

Embed Size (px)

### Transcript of Do Extraterrestrials Use Functional Programming? ... Manuel M T Chakravarty University of New South

Manuel M T Chakravarty University of New South Wales

Do Extraterrestrials Use Functional Programming?

mchakravarty

α TacticalGrace TacticalGrace

Thursday, 16 May 13

» Straight to next slide

[15min Question (λ); 20min Methodology; 15min Application]

Part 1 The Question

Thursday, 16 May 13

This talk will be in three parts. (1) Discussing essence of functional programming. What makes FP tick? (2) How do FP principles influence software dev? Will propose a dev methodology for FP. (3) Look at concrete dev project, where we applied this methodology. »»Let's start with The Question…

“Do Extraterrestrials Use Functional Programming?”

Thursday, 16 May 13

» * To visit us, they need to be on an advanced technological level with a deep understanding of science. * They won't speak one of humanity's languages, though. So, how do we establish a common basis?

Thursday, 16 May 13

* How to communicate? * Common idea: universal principles may help establish a basis — universal constants or universal laws.

Thursday, 16 May 13

* How to communicate? * Common idea: universal principles may help establish a basis — universal constants or universal laws.

π?

Thursday, 16 May 13

* How to communicate? * Common idea: universal principles may help establish a basis — universal constants or universal laws.

π? E = mc2

Thursday, 16 May 13

Thursday, 16 May 13

* Computer languages? Agree on a common language of computation? * In 1936, Alonzo Church introduced the lambda calculus: * Serve as a common language? Like a computational Esperanto? * Also other calculi/machines. Famous: Turing machines. Which would aliens pick? »» Let's look: how are they related…

Alonzo Church

M, N → x | λx.M | M N

Thursday, 16 May 13

* Computer languages? Agree on a common language of computation? * In 1936, Alonzo Church introduced the lambda calculus: * Serve as a common language? Like a computational Esperanto? * Also other calculi/machines. Famous: Turing machines. Which would aliens pick? »» Let's look: how are they related…

Alonzo Church

M, N → x | λx.M | M NM, N → x | λx.M | M N

Thursday, 16 May 13

* Computer languages? Agree on a common language of computation? * In 1936, Alonzo Church introduced the lambda calculus: * Serve as a common language? Like a computational Esperanto? * Also other calculi/machines. Famous: Turing machines. Which would aliens pick? »» Let's look: how are they related…

Alonzo Church

M, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M N

Thursday, 16 May 13

Alonzo Church

M, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M N

Thursday, 16 May 13

Alonzo Church

M, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M NM, N → x | λx.M | M N

Thursday, 16 May 13

Alonzo Church

M, N → x | λx.M | M N

Alan Turing

Thursday, 16 May 13

Alonzo ChurchAlan Turing

M, N → x | λx.M | M N

Thursday, 16 May 13

* The lambda calculus and Turing machines have the same origin. * Beginning 20th century: group of famous mathematicians interested in formalising foundation of mathematics. »» This led to an important question…

M, N → x | λx.M | M N

Lambda Calculus Turing Machine

Thursday, 16 May 13

* The lambda calculus and Turing machines have the same origin. * Beginning 20th century: group of famous mathematicians interested in formalising foundation of mathematics. »» This led to an important question…

M, N → x | λx.M | M N

Lambda Calculus Turing Machine

By-product of a study of the foundation and expressive power

of mathematics.

Thursday, 16 May 13

* The lambda calculus and Turing machines have the same origin. * Beginning 20th century: group of famous mathematicians interested in formalising foundation of mathematics. »» This led to an important question…

David Hilbert

Thursday, 16 May 13

* Challenge posed by David Hilbert, 1928: the Entscheidungsproblem (decision problem) * Church & Turing, 1936, no solution, using lambda calculus & Turing machines. »» So what is the Entscheidungsproblem…

Is there a solution to the Entscheidungsproblem?

David Hilbert

Thursday, 16 May 13

* Challenge posed by David Hilbert, 1928: the Entscheidungsproblem (decision problem) * Church & Turing, 1936, no solution, using lambda calculus & Turing machines. »» So what is the Entscheidungsproblem…

Is there a solution to the Entscheidungsproblem?

David Hilbert

No!

No!

Thursday, 16 May 13

* Challenge posed by David Hilbert, 1928: the Entscheidungsproblem (decision problem) * Church & Turing, 1936, no solution, using lambda calculus & Turing machines. »» So what is the Entscheidungsproblem…

“Is there an algorithm to decide whether a given statement is provable from a set of axioms using the rules of first-order

logic?”

Thursday, 16 May 13

* In other words: Given a world & a set of fixed rules in the world, check whether the world has a particular property. »» In turn, leads to the question…

“How do you prove that an algorithm does not exist?”

Thursday, 16 May 13

* Because we cannot solve the challenge, doesn't mean it is unsolvable? * Need systematic way to rigorously prove that a solution is impossible. »» Church & Turing proceeded as follows…

Thursday, 16 May 13

* 1936, the concept of an algorithm remained to be formally defined

(1) Define a universal language or abstract machine.

(2) Show that the desired algorithm cannot be expressed in the language.

Thursday, 16 May 13

* 1936, the concept of an algorithm remained to be formally defined

Define a universal language or abstract machine.

Thursday, 16 May 13

* Two steps * Church & Turing used: (1) lambda term, (2) Turing machine * Hypothesis: universal — ie, any algorithmically computable function can be expressed »» They showed…

Define a universal language or abstract machine.

Lambda Calculus Turing Machine

M, N → x | λx.M | M N

Thursday, 16 May 13

* Two steps * Church & Turing used: (1) lambda term, (2) Turing machine * Hypothesis: universal — ie, any algorithmically computable function can be expressed »» They showed…

Lambda Calculus Turing Machine

M, N → x | λx.M | M N

Universal language

Thursday, 16 May 13

* Two steps * Church & Turing used: (1) lambda term, (2) Turing machine * Hypothesis: universal — ie, any algorithmically computable function can be expressed »» They showed…

Lambda Calculus Turing Machine

M, N → x | λx.M | M N

Universal language

Chur ch-Tu

ring t hesis

Thursday, 16 May 13

Lambda Calculus Turing Machine

M, N → x | λx.M | M N

Computational Power

=

Thursday, 16 May 13

* Any program expressible in one is expressible in the other. »» However, …

Turing MachineLambda Calculus

M, N → x | λx.M | M N

Generality

Thursday, 16 May 13

* Lambda calculus: embodies concept of (functional) *abstraction* * Functional abstraction is only one

Recommended

*View more*