PreliminariesJohn BackusIssues With von Neumann LanguagesA Functional Programming SystemFoundationsComponents of an FP SystemThe Algebra of ProgramsPractical Functional ProgrammingHaskellRubySummaryAppendixAppendixPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFunctional ProgrammingRobert BieberMarch 1, 2011Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryOutline1PreliminariesJohn BackusIssues With von Neumann Languages2A Functional Programming SystemFoundationsComponents of an FP SystemThe Algebra of Programs3Practical Functional ProgrammingHaskellRubyRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesJohn BackusBorn 1924.Died 2007.Directed development of FORTRAN, released in 1957.Backus-Naur Form.Received Turing Award in 1977 for his work onprogramming languages.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesThe von Neumann ArchitectureRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesExcessive "Housekeeping" Code/ ∗∗ Computes dot prod uct o f two ve c t or s∗ /public i n t dot Prod uct ( i n t [ ] a , i n t [ ] b ){i n t res = 0 ;fo r ( i n t i = 0; i < a . l en gt h ; i ++)res += a [ i ] ∗ b [ i ] ;return re s ;}Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesLack of Useful Algebraic PropertiesExample:f (x) + 2f (x) + 3f (x) (1)= (1 + 2 + 3)f (x) (2)= 6f (x) (3)Compare to:i n t y = 1∗ f ( x ) + 2∗ f ( x ) + 3∗ f ( x ) ;Is y == 6*f(x)?Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesPotential ProblemsNot if f references global variables.i n t f ( i n t x ){return someGlobalVariable ++;}Or if f interacts with the user.i n t f ( i n t x ){i n t r e t ;scanf ( "%d " , &r e t ) ;return r e t ;}Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsCharasteristics of an FP SystemThe system is not history-sensitive.Functions have no side-effects.Functions are formed by combining other functions.Programs built in an FP system can be transformed byuseful algebraic properties.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsStructure of an FP SystemA set O of objects.A set F of primitive functions.The application operation.A set F of functional forms.A set D of defined functions.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsObjectsObjects are the data on which our programs operate.Atoms are numbers and combinations of characters:12, T , F , FOOLists are any combination of atoms:< 3, 4, 5 >, < A, B, < C, D >>, φ⊥ represents “bottom,” or “undefined” Any list containing ⊥is equivalent to ⊥, and any function that operates on ⊥returns ⊥.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsPrimitive FunctionsA function is a mapping from the set of objects to the set ofobjects.Functions accept a single argument and return a singleresult.The primitive functions are those “built-in” to the system.Functions are applied with the application operator :.For any function f and any object x, f : x ≡ the result ofapplying f to x.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsFunction ApplicationRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsExamples of Function Applicationid : A = A+ :< 3, 4 >= 72 :< 5, 6, 7 >= 6− : 1 =⊥tl :⊥=⊥ (Remember that all functions are ⊥ preserving).trans :<< 1, 2 >, < 5, 6 >>=<< 1, 5 >, < 2, 6 >>Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsFunctional FormsFunctional forms are expressions that represent functions.Functional forms are operators with functions as theiroperands.We can use functional forms to construct more usefulfunctions from the supplied primitives.Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsExamples of Functional FormsComposition: f ◦ g : x ≡ f : (g : x)Apply to All: αf :< x1, x2, ...xn>≡< f : x1, f : x2, ...f : xn>Insert: /f :< x1, x2, ...xn>≡ f :< x1, /f < x2, ...xn>>Construction: [f1, f2, ...fn] : x ≡< f1: x, f2: x, ...fn: x >Condition: (p → f ; g) ≡ (p : x) = T → f : x; g : xConstant: x : y ≡ xRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsCompositionf ◦ gRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsConstruction[f , g]Robert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsConditionalp → f ; gRobert Bieber Functional ProgrammingPreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsDefinitionsA definition, or defined function, associates a name with afunctional form.Definitions are analogous to function definitions in
View Full Document
Unlocking...