CSC302 2006S, Class 39: Presentations (3) FP
Admin:
* Late again: Dimitar
Overview
* Background of FP
* Example of Difference
* The FP
/Background of FP/
[Angeline's presentation would have benefitted from an outline
(Powerpoint, whatever), not only because she speaks so quietly, but also
because there are so many issues that a summary would help. Even the board would suffice.]
[The topic regularly refers to "he", without giving an introduction. E.g., "We are considering a paper by John Backus, entitled, ..., which was.]
* Language designed by John Backus in reaction to what he sees as problems.
* Languages are too large, without giving that much extra power.
* Want special characteristics of languages: Power, provability, etc.
* Multiple models
* Operation model: Too low level
* Lambda Calclus: lacks storage
* The von Neumann model: Very complex, constraining
* Unfortunately, the von Neumann model seems to be the primary model for modern languages
* One significant problem of the von neumann model - Word at a time programming: The emphasis on von Neumann programs is assignment statements, and each assignment statement does little more than move "one word" from one part of memory to another.
/Example of Differences/
* Consider the problem of computing the inner product of two vectors.
ip <<1,3,5>,<2,4,6>>
TRANSPOSE => <<1,2>,<3,4>,<5,6>>
MULTIPLY PAIRS => <2,12,30>
SUM => 44
* How would we write this in a typical imperative language?
c := 0;
for i := 1 until n do
c := c + a[i] x b[i]
[Erasing the board during the example was a bad idea; showing the steps would have been nice in getting to the code.]
* Problems:
* Mixes the three parts of the problem (transposing, multiplying, and sum)
* Deals with too fine-grained data.
* Doesn't show states
* Suggested functional solution:
Def IP = (Insert +) o (ApplyToAll *) o Transpose
Example IP <<1,3,5>, <2,4,6>>
=> (Insert +) o (ApplyToAll *) o Transpose : <<1,3,5>, <2,4,6>>
=> (Insert +) o (ApplyToAll *) : <<1,2>, <3,4>, <5,6>>
=> (Insert +) : <*:<1,2> *:<3,4>, *:<5,6>>
=> (Insert +) : <2, ,12, 30>
=> +:<2, +:<12,30>>
=> 44
* Permits us to more easily build new functions out of old
* More readable
Reusable frameworks and changeable parts
* Languages provide a framework and let the programmers write their own parts
* Typical von Neumann languages provide a very large framework, which means there are fewer changable parts.
* Limits the power of the changeable parts.
* But perhaps we can design a language with with a smaller framework that supports more changeable parts.
[Davis would also benefit from an outline or overview or board. What are the key ideas?]
/FP/
* Review: Problems with von Neumann
* Too many state changes for each part of a computation
* Word-at-a-time bottlenecking
* ...
[Alex mispronounced von Neumann]
* Some alternatives
* Applicative state transition system (AST)
* Functional programming sytem (FP)
* Every function takes one parameter
* Formal functional programming system
* Define language in itself
* Four parts
* Functional stytle
* Algebra to prove algorithms correct
* Formal functional programming system
* State transition
* Basic functional programming system
* Fixed set of combining forms called functional forms
* Functions map objects to objects; take a single argument
* NO LAMBDAS
* Hard to follow programs you didn't write.
* An FP system
* A set of objects
* A set of functions that map objects to objects
* A central operation, application
* Functional forms to combine
* A set of definitions to define some basic functions
* FP
* Object: Atom, sequence, or underfined
* Special atoms:
* Phi (empty sequence) (both an atom and a sequence)
* T (true),
* F (false)
* Application applying a function f to an object
* +:<1,2> = 3
* 1: = A
* tl: =
* Definition:
1:x == -> x1 ; bottom
s:x == and n>= s => xs ; bottom
* Bottom-preserving (If you apply a function to undefined, you get undefined).
Functional forms:
* An expression that denotes a function
* (fog):x = f:(g:x)
* Form is Def l === r
* l is an unused function symbol
* r is a functional form
* Semantics:
* f must be one o four things
Example: Defining factorial
Def ! = eq0 -> 1 ; x o (id, !osub1]
Factorial example
/Summary of FP/
* FP systems as programming languages
* Minimal and powerful, but hard to think of as programming language
* Limitations
* Fixed language, not history sensitive
* Expressive power
* Easy to define "more power" systems
[Alex claims that you can get an "infinitely powerful language"; but nothing really gives you more powerful.]
* Advantages of FP systems
[Only 35 minutes]
Question: Since behind the scenes, it's probably implemented as a von Neumann machine, what's the difference?