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,B,C> = A
    * tl:<A,B,C> = <B,C>
  * Definition:
    1:x == <x1...xn> -> x1 ; bottom
    s:x == <x1...xn> 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?