Functional LanguagesFunctional Languages (Applicative, value-oriented)Importance of Functional Languages…ExpressionsMore ExpressionsHoare's Principles of StructuringSlide 7Properties of Pure ExpressionsA Scheme ContinuationBasic Data Types in Application LanguagesComposite Data Types(continue) Data TypesSlide 13ArchetypesInfinite Sequences ArchetypeInfinite Sequences Archetype (cont)Notes on Sequence ArchetypeMore on Sequence ArchetypeCompleteness and ConsistencyBoolean Archetype (partial)Completeness and Consistency (cont)Infinite SequencesSlide 23Slide 24Infinite Sequences (cont)Finite SequencesFinite Sequences (cont)Operations on SequencesFinite SetsHigher Order FunctionsHigher Order Functions (cont)Functional ProgrammingFunctional AbstractionFunctional Abstraction (cont)Slide 35Map ArchetypeFilteringA Scheme FilterFilter ArchetypeSequences and SetsA Note on CorrectnessMore on CorrectnessContinue Correctness of Set IntersectionComposition ArchetypeConstruction ArchetypeHaskell & ML: Interesting FeaturesType InferencingType Inferencing (cont)PolymorphismPolymorphism (cont)Functional LanguagesFunctional Languages (Applicative, value-oriented)Importance?•In their pure form they dispense with notion of assignment–claim is: it's easier to program in them–also: easier to reason about programs written in them•FPL's encourage thinking at higher levels of abstraction–support modifying and combining existing programs–thus, FPL's encourage programmers to work in units larger than statements of conventional languages: "programming in the large"•FPL's provide a paradigm for parallel computing–absence of assignment (single assignment) } provide basis–independence of evaluation order } for parallel–ability to operate on entire data structures } functional programmingImportance of Functional Languages…•Valuable in developing executable specifications and prototype implementations–Simple underlying semantics•rigorous mathematical foundations•ability to operate on entire data structures => ideal vehicle for capturing specifications•Utility to AI–Most AI done in func langs (extensibility. symbolic manipulation)•Functional Programming is tied to CS theory–provides framework for viewing decidability questions•(both programming and computers)–Good introduction to Denotational Semantics•functional in formExpressions•Key purpose of functional programming:–to extend the advantages of expressions (over statements) to an entire programming language•Backus ('78 FP paper) has said that expressions and statements come from two different worlds.–expressions: (a + b) * c arithmetic (a + b) = 0 relational ¬(a  b) boolean–statements: the usual assortment with assignment singled out–assignments alter the state of a computation (ordering is important) e.g. a:= a * i; i:= i + 1•In contrast, ordering of expressions is not side-effecting and therefore not order dependent (Church-Rosser property /Church Diamond)More Expressions•With Church-Rosser–reasoning about expressions is easier–order independence supports fine-grained parallelism–Diamond property is quite useful•Referential transparency–In a fixed context, the replacement of a subexpression by its value is completely independent of the surrounding expression•having once evaluated an expression in a given context, shouldn’t have to do it again.Alternative: referential transparency is the universal ability to substitute equals for equals (useful in common subexpression optimizations and mathematical reasoning)Hoare's Principles of Structuring(1973, "Hints on Programming Language Design," Stanford Tech Rep)1) Transparency of meaning–Meaning of whole expression can be understood in terms of meanings of its subexpressions.2) Transparency of Purpose–Purpose of each part consists solely of its contribution to the purpose of the whole. No side effects.3) Independence of Parts–Meaning of independent parts can be understood completely independently.•In E + F, E can be understood independently of F.Hoare's Principles of Structuring4) Recursive Application–Both construction and analysis of structure (e.g. expressions) can be accomplished through recursive application of uniform rules.5) Narrow Interfaces–Interface between parts is clear, narrow (minimal number of inputs and outputs) and well controlled.6) Manifestness of Structure–Structural relationships among parts are obvious. e.g. one expression is subexpression of another if the first is textually embedded in the second. Expressions are unrelated if they are not structurally related.Properties of Pure Expressions•Value is independent of evaluation order•Expressions can be evaluated in parallel•Referential transparency•No side-effects (Church Rosser)•Inputs to an expression are obvious from written form•Effects of operation are obvious from written form  Meet Hoare's principles well Good attributes to extend to all programming (?)A Scheme Continuation(set init-rand (lambda (seed) (lambda () (set seed (mod (+ (* seed 9) 5) 1025)))))(set rand (init-rand 1))•Sequence of calls to (rand) produces a changing set of values•So much for referential transparency…Basic Data Types in Application Languages•Atomic data types - Integers I } + , - , x ,  , / , = , - Reals R }  ,  ,  ,  ,  - Strings = ,  - Boolean B = ,  , , , , Composite Data Types•Sequences (a generic data type) e.g. <'CS655', 'CS654', 'CS851'> < <'CS655', 'CS851'>, < 'CS654’> > -- can have subsequences to any depth as long as subsequences are matching type. i.e. <'CS655'>  'CS655'•"sequence" by itself is not a type–type of a sequence determined by its components Sequence(I ) = sequence of integer Sequence(R) = sequence of real, etc.(continue) Data Types•Notational convenience concerning sequences: * means sequence of objects of type  e.g. I* is sequence of integers.•Typical operations on sequences - 1) constructors: build sequences from components 2) selectors: select elements from a sequence 3) discriminators: distinguish among different classes of sequences. e.g. empty vs. non-empty. Would like to: a) minimize overall set b) have set be