Functional Languages Functional Languages Applicative valueoriented 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 programming 1 Importance 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 form Expressions 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 2 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 3 Hoare s Principles of Structuring 4 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 4 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 Reals R x Strings Boolean B 5 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 complete in sense that functional composition can create any other operation 6 continue Data Types Traditional FPL constructors selectors and discriminators constructors NIL prefix Cons selectors first car rest cdr discriminators Null Null Comments about domains 1 first rest not defined on null sequences or atoms 2 Null not defined on atoms Partial functions Archetypes sequence example next slide Archetype ideal characterization as contrasted with prototypes archetype what you want prototype shows feasibility implementability Archetypes tend to be written using algebraic specification for syntax and semantics also often include pragmatics comments on efficiency 7 Infinite Sequences Archetype Syntax nil Primitive function signatures domain range null B first generic polymorphic partial rest prefix x x S prefix x S nil x1 x2 xn Rewrite rules x1 x2 xn Infinite Sequences Archetype cont Semantics nil x S z otherwise null nil true null x S false first nil x first x S x rest nil S rest x S S Existence axioms Equations Pragmatics The first rest prefix and null operations all take constant time The prefix operation is significantly slower than the others 8 Notes on Sequence Archetype a x1 x2 xn x1 x2 xn x1 x2 x3 xn NIL b domains ranges and signatures are important concepts c defined functions are generic d defined functions are partial First rest don t work on null sequences More on Sequence Archetype nil x S z otherwise tells us that members of sequence type include NIL and every result of prefix operation x S z otherwise means nothing else is included in type rest x S S first x S x define equivalence relations on well formed formulae formula equation 9 Completeness and Consistency Semantic equations are complete if they are sufficient to either prove or