Transcription
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFunctional ProgrammingRobert BieberMarch 1, 2011Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryOutline1PreliminariesJohn BackusIssues With von Neumann Languages2A Functional Programming SystemFoundationsComponents of an FP SystemThe Algebra of Programs3Practical Functional ProgrammingHaskellRubyRobert BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesThe von Neumann ArchitectureRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesExcessive "Housekeeping" Code/ Computes d o t p r o d u c t o f two v e c t o r s /public i n t d o t P r o d u c t ( i n t [ ] a , i n t [ ] b ){i n t res 0;f o r ( i n t i 0 ; i a . l e n g t h ; i )r e s a [ i ] b [ i ] ;return res ;}Robert BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryJohn BackusIssues With von Neumann LanguagesPotential ProblemsNot if f references global variables.int f ( int x){r e t u r n someGlobalVariable ;}Or if f interacts with the user.int f ( int x){int ret ;s c a n f ( "%d " , & r e t ) ;return r e t ;}Robert BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsFunction ApplicationRobert BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA 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 BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsCompositionf gRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsConstruction[f , g]Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsConditionalp f;gRobert BieberFunctional Programming
PreliminariesA 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 vonNeumann languages.A Definition consists of a name on the left side and anexpression consisting only of functional forms involvingprimitive and other defined functions on the right side.Takes the form Def name expressionRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsExamples of Functional ProgramsDef sub1 [id, 1]Def eq0 eq [id, 0]Def fact eq0 1; [id, fact sub1]Collatz Sequence:Def eq1 eq [id, 1]Def div 2 [id, 2]Def mult3add1 [1, [id, 3]]Def collatzstep even div 2; mult3add1Def collatz eq1 1 ; apndl [id, collatz collatzstep]Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsAlgebraic Properties of FP SystemsUnlike von Neumann languages, FP systems exhibit usefulalgebraic properties.Using these properties, we can manipulate programsalgebraically the way we manipulate mathematicalexpressions in high school algebra.We can prove properties of programs using theprogramming language itself.Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryFoundationsComponents of an FP SystemThe Algebra of ProgramsExamples of Algebraic Laws of the FP System[f1 , .fn ] g [f1 g, .fn g]αf [g1 , .gn ] [f g1 , .f g2 ](p f ; g) h p h f h; g h[., , .] f f id fRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyProperties of HaskellPure functional language: no concept of state, functionshave no side-effects (except for I/O).Unlike Backus’ FP system, handles multiple argumentfunctions by currying.User writes program by specifying type signatures andfunction definitions.Functions are first class objects and can be passed toother functions.Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyExample Haskell Programc o l l a t z S t e p : : I n t I n tc o l l a t z S t e p x i f x ‘mod‘ 2 0then x ‘ div ‘ 2else 3 x 1c o l l a t z : : I n t [ I n t ]c o l l a t z x i f x 1 then [ 1 ]else x : ( c o l l a t z c o l l a t z S t e p x )main dox getLineputStrLn show c o l l a t z read xRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyExecutionRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyPointfree StyleAvoid use of variable names in function definitions.Favor function composition and partial application.Very similar to Backus’ style.Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyExamplesA function, sumx2, which multiplies every element of a list by 2and sums the resultant list.Normal:sumx2 xs sum (map ( 2) xs)Pointfree:sumx2 sum . map ( 2)Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyProperties of RubyDynamic object-oriented scripting lanugage.Allows methods to accept "blocks" as their final argument:basically anonymous functions.Blocks minimize "housekeeping code" that Backus cited.Robert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummaryHaskellRubyFile I/O ExampleC Example:FILE f i n fopen ( " t e s t . t x t " , " r " ) ;while ( ! f e o f ( f i n ) ){f s c a n f ( f i n , "%s \ n " , t e x t ) ;p r i n t f ( "%s \ n " , t e x t ) ;}fclose ( f i n ) ;Ruby Example:IO . f o r e a c h ( ’ t e s t . t x t ’ ) do l i n e puts l i n eendRobert BieberFunctional Programming
PreliminariesA Functional Programming SystemPractical Functional ProgrammingSummarySummaryImperative programming languages are inflexible, anddon’t exhibit useful algebraic properties.FP systems allow the user to create programs bycombining simpler functions, and these programs can bemanipulated algebraically.In modern languages we have both purely functionallanguages and imperative/object-oriented languages whichincorporate functional features.Robert BieberFunctional Programming
AppendixFor Further ReadingFor Further Reading IJ. Backus.Can Programming Be Liberated from the von NeumannStyle? A Functional Style and Its Algebra of Programs.Communications of the ACM, 21(8):, 1978.Haskell ointfreeRuby DocumentationGuides and API Documentationhttp://www.ruby-doc.org/Robert BieberFunctional Programming
A Functional Programming System Practical Functional Programming Summary Haskell Ruby Properties of Haskell Pure functional language: no concept of state, functions have no side-effects (except for I/O). Unlike Backus' FP system, handles multiple argument functions by currying. User writes program by specifying type signatures and function .
