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?