111UMBCUMBCan Honors University in Marylandan Honors University in MarylandFunctional Functional ProgrammingProgrammingLanguagesLanguages22UMBCUMBCan Honors University in Marylandan Honors University in MarylandIntroductionIntroductionFunctional programming paradigmFunctional programming paradigmHistoryHistoryFeatures and conceptsFeatures and conceptsExamples:Examples:LispLispMLML33UMBCUMBCan Honors University in Marylandan Honors University in MarylandFunctional ProgrammingFunctional ProgrammingThe Functional Programming Paradigm is one of the major The Functional Programming Paradigm is one of the major programming paradigms.programming paradigms.FP is a type of declarative programming paradigmFP is a type of declarative programming paradigmAlso known as Also known as applicative programmingapplicative programmingand and valuevalue--oriented programmingoriented programmingIdea: everything is a functionIdea: everything is a functionBased on sound theoretical frameworks (e.g., the lambda Based on sound theoretical frameworks (e.g., the lambda calculus)calculus)Examples of FP languagesExamples of FP languagesFirst (and most popular) FP language: LispFirst (and most popular) FP language: LispOther important FPs: ML, Haskell, Miranda, Scheme, Other important FPs: ML, Haskell, Miranda, Scheme, LogoLogo44UMBCUMBCan Honors University in Marylandan Honors University in MarylandFunctional Programming LanguagesFunctional Programming LanguagesThe design of the imperative languages is based directly on the von Neumann architectureEfficiency is the primary concern, rather than the suitability of the language for software developmentThe design of the functional languages is based on mathematical functionsA solid theoretical basis that is also closer to the user, but relatively unconcerned with the architecture of the machines on which programs will run255UMBCUMBCan Honors University in Marylandan Honors University in MarylandCharacteristics of Characteristics of Pure FPLsPure FPLsPure FP languages tend toPure FP languages tend toHave no sideHave no side--effectseffectsHave no assignment statementsHave no assignment statementsOften have no variables!Often have no variables!Be built on a small, concise frameworkBe built on a small, concise frameworkHave a simple, uniform syntaxHave a simple, uniform syntaxBe implemented via interpreters rather Be implemented via interpreters rather than compilersthan compilersBe mathematically easier to handleBe mathematically easier to handleUMBCUMBCan Honors University in Marylandan Honors University in MarylandImportance of FPImportance of FPIn their pure form FPLs dispense with notion of assignmentIn their pure form FPLs dispense with notion of assignmentclaim is: it's easier to program in themclaim is: it's easier to program in themalso: easier to reason about programs written in themalso: easier to reason about programs written in themFPLs encourage thinking at higher levels of abstractionFPLs encourage thinking at higher levels of abstractionsupport modifying and combining existing programssupport modifying and combining existing programsthus, FPL's encourage programmers to work in units larger than thus, FPL's encourage programmers to work in units larger than statements of conventional languages: "programming in the large"statements of conventional languages: "programming in the large"FPLs provide a paradigm for parallel computingFPLs provide a paradigm for parallel computingabsence of assignment (or single assignment) } provide basisabsence of assignment (or single assignment) } provide basisindependence of evaluation order } for paraindependence of evaluation order } for parallelllelability to operate on entire data structures } functionaability to operate on entire data structures } functional l programmingprogrammingUMBCUMBCan Honors University in Marylandan Honors University in MarylandImportance of FPImportance of FPFPLs are valuable in developing FPLs are valuable in developing executable specificationsexecutable specificationsand and prototype implementationsprototype implementationsSimple underlying semanticsSimple underlying semanticsrigorous mathematical foundationsrigorous mathematical foundationsability to operate on entire data structuresability to operate on entire data structuresideal vehicle for capturing specificationsideal vehicle for capturing specificationsFPLs are very useful for AI and other applications which requireFPLs are very useful for AI and other applications which requireextensive symbol manipulation.extensive symbol manipulation.Functional Programming is tied to CS theoryFunctional Programming is tied to CS theoryprovides framework for viewing decidability questionsprovides framework for viewing decidability questions(both programming and computers)(both programming and computers)Good introduction to Denotational SemanticsGood introduction to Denotational Semanticsfunctional in formfunctional in formUMBCUMBCan Honors University in Marylandan Honors University in MarylandExpressionsExpressionsKey purpose of functional programming: to extend the Key purpose of functional programming: to extend the advantages of expressions (over statements) to an entire advantages of expressions (over statements) to an entire programming languageprogramming languageBackus* has said that expressions and statements come from Backus* has said that expressions and statements come from two different worlds.two different worlds.expressions: (a + b) * c arithmeticexpressions: (a + b) * c arithmetic(a + b) = 0 relational(a + b) = 0 relational¬(a ¬(a ∨∨b) booleanb) booleanstatements: the usual assortment with assignment singled outstatements: the usual assortment with assignment singled outassignments alter the state of a computation assignments alter the state of a computation (ordering is important) (ordering is important) e.g. a:= a * i; i:= i + 1e.g. a:= a * i; i:= i + 1In contrast, ordering of expressions is not sideIn contrast, ordering of expressions is not side--effecting and effecting and therefore not order dependent