1Functional 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 thanstatements 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 programming2Importance of Functional Languages…•Valuable in developing executable specifications andprototype 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 entireprogramming language•Backus ('78 FP paper) has said that expressions and statementscome 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 andtherefore not order dependent (Church-Rosser property /ChurchDiamond)3More 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 iscompletely independent of the surrounding expression•having once evaluated an expression in a given context, shouldn’thave to do it again.Alternative: referential transparency is the universal ability tosubstitute equals for equals (useful in common subexpressionoptimizations 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 meaningsof its subexpressions.2) Transparency of Purpose–Purpose of each part consists solely of its contribution to the purpose ofthe whole. No side effects.3) Independence of Parts–Meaning of independent parts can be understood completelyindependently.•In E + F, E can be understood independently of F.4Hoare's Principles of Structuring4) Recursive Application–Both construction and analysis of structure (e.g. expressions) can beaccomplished through recursive application of uniform rules.5) Narrow Interfaces–Interface between parts is clear, narrow (minimal number of inputsand outputs) and well controlled.6) Manifestness of Structure–Structural relationships among parts are obvious. e.g. one expressionis subexpression of another if the first is textually embedded in thesecond. 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 (?)5A 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 = , ≠ , <, ≤, >, ≥6Composite 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 arematching 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 functionalcomposition can create any other operation)7(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 atomsPartialfunctions•(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 efficiencyArchetypes8•Syntax:nil ∈ τ*null: τ* → Bfirst: τ* → τrest: τ* → τ*prefix: τ x τ* → τ*x:S prefix (x, S)< > nil<x1, x2, …, xn >