Programming ParadigmsProgramming Paradigmsldots Programming Paradigmsldots Programming Paradigmsldots Procedural ProgrammingProcedural Programmingldots Procedural Programmingldots Functional ProgrammingFunctional LanguagesFunctional Languagesldots Functional Languagesldots What is a function?More on functionsMore on functionsldots More on functionsldots Specifying functionsSpecifying functionsldots Specifying functionsldots Function ApplicationFunction CompositionFunction Definition --- ExampleFunction SignaturesReferential TransparencyReferential Transparencyldots Referential Transparencyldots Referential Transparencyldots Referential Transparencyldots Referential Transparencyldots Referential Transparencyldots Referential Transparencyldots Readings and ReferencesHomework520 —Spring 2008 — 33CSc 520Principles of ProgrammingLanguages33 : Functional ProgrammingChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 33Programming ParadigmsDuring the next few weeks we are going to work withfunctional programming. Before I can explain to youwhat FP is, I thought I’d better put things intoperspective by talking about otherprogramming paradigms.Over the last 40 or so years, a number of programmingparadigms (a programming paradigm is a way to thinkabout programs and programming) have emerged.[2]520 —Spring 2008 — 33Programming Paradigms...A programming paradigmis a way to think about programs, programming, andproblem solving,is supported by one or more programming languages.Being familiar with several paradigms makes you a betterprogrammer and problem solver. The most popularparadigms:1. Imperative programming.2. Functional programming.3. Object-oriented programming.4. Logic Programming.When all you have is a hammer, everything looks like a nail.[3]520 —Spring 2008 — 33Programming Paradigms...Imperative ProgrammingProgramming with state.Also known as procedural programming. The first toemerge in the 1940s-50s. Still the way most peoplelearn how to program.FORTRAN, Pascal, C, BASIC.Functional ProgrammingProgramming with values.Arrived in the late 50s with the LISP language. LISP isstill popular and widely used by AI people.LISP, Miranda, Haskell, Gofer.[4]520 —Spring 2008 — 33Programming Paradigms...Object-Oriented ProgrammingProgramming with objects that encapsulate data andoperations.A variant of imperative programming first introducedwith the Norwegian language Simula in the mid 60s.Simula, Eiffel, Modula-3, C++.Logic ProgrammingProgramming with relations.Introduced in the early 70s. Based on predicatecalculus. Prolog is popular with ComputationalLinguists.Prolog, Parlog.[5]520 —Spring 2008 — 33Procedural ProgrammingWe program an abstraction of the Von Neumann Machine,consisting of astore (memory), a program (kept in thestore), ACPU and a program counter (PC):storePCCPUAddressesDataX:Program:PC := PC + 8;X := X + 153JumpStoreUpdateComputing x:=x+11. Compute x’s ad-dress, send it to thestore, get x’s valueback.2. Add 1 to x’s value.3. Send x’s addressand new value to thestore for storage.4. Increment PC.[6]520 —Spring 2008 — 33Procedural Programming...The programmer...uses control structures (IF, WHILE, ...) to alter theprogram counter (PC),uses assignment statements to alter the store.is in charge of memory management, i.e. declaringvariables to hold values during the computation.function fact ( n : integer ) : integer ;var s , i : integer : = 1 ;beginwhile i <=n do s:=s∗ i ; i := i +1; end;return s ;end fact . [7]520 —Spring 2008 — 33Procedural Programming...Procedural programming is difficult because:1. A procedural program can be in a large number ofstates. (Any combination of variable values and PClocations constitutes a possible state.) The programmerhas to keep track of all of them.2. Any global variable can be changed from any location inthe program. (This is particularly true of languages likeC & C++ [Why?]).3. It is difficult to reason mathematically about aprocedural program.[8]520 —Spring 2008 — 33Functional ProgrammingIn contrast to procedural languages, functional programsdon’t concern themselves with state and memory locations.Instead, they work exclusively with values, andexpressions and functions which compute values.Functional programming is not tied to the von Neumannmachine.It is not necessary to know anything about theunderlying hardware when writing a functional program,the way you do when writing an imperative program.Functional programs are more declarative thanprocedural ones; i.e. they describewhat is to becomputed rather than how it should be computed.[9]520 —Spring 2008 — 33Functional LanguagesCommon characteristics of functional programminglanguages:1. Simple and concise syntax and semantics.2. Repetition is expressed asrecursion rather thaniteration.3.Functions are first class objects. I.e. functions can bemanipulated just as easily as integers, floats, etc. inother languages.4.Data as functions. I.e. we can build a function on thefly and then execute it. (Some languages).[10]520 —Spring 2008 — 33Functional Languages...5. Higher-order functions. I.e. functions can takefunctions as arguments and return functions as results.6. Lazy evaluation. Expressions are evaluated only whenneeded. This allows us to buildinfinite data structures,where only the parts we need are actually constructed.(Some languages).7.Garbage Collection. Dynamic memory that is no longerneeded is automatically reclaimed by the system. GC isalso available in some imperative languages (Modula-3,Eiffel) but not in others (C, C++, Pascal).[11]520 —Spring 2008 — 33Functional Languages...8. Polymorphic types. Functions can work on data ofdifferent types. (Some languages).9. Functional programs can be more easilymanipulated mathematically than procedural programs.Pure vs. Impure FPLSome functional languages are pure, i.e. they containno imperative features at all. Examples: Haskell,Miranda, Gofer.Impure languages may have assignment-statements,goto:s, while-loops, etc. Examples: LISP, ML, Scheme.[12]520 —Spring 2008 — 33What is a function?A function maps argument values (inputs) to resultvalues (outputs).A function takes argument values from a source set (ordomain).A function produces result values that lie in a target set(or range).Target (Range)CapitalUSASwedenNZStockholmWashington DCWellingtonCopenhagenSource (Domain)
View Full Document
Unlocking...