CSc 520Principles of Programming Languages2: Functional ProgrammingChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Programming Paradigms• During the next few weeks we are going to work with functional programming. Before I can explain toyou what FP is, I thought I’d better put things into perspective by talking about other programmingparadigms.• Over the last 40 or so years, a number of programming paradigms (a programming paradigm is a wayto think about programs and programming) have emerged.2 Programming Paradigms. . .A programming paradigm• is a way to think about programs, programming, and problem solving,• is supported by one or more programming languages.Being familiar with several paradigms makes you a better programmer and problem solver. The mostpopular paradigms: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.13 Programming Paradigms. . .Imperative Programming• Programming with state.• Also known as procedural programming. The first to emerge in the 1940s-50s. Still the way most peoplelearn how to program.• FORTRAN, Pascal, C, BASIC.Functional Programming• Programming with values.• Arrived in the late 50s with the LISP language. LISP is still popular and widely used by AI people.• LISP, Miranda, Haskell, Gofer.4 Programming Paradigms. . .Object-Oriented Programming• Programming with objects that encapsulate data and operations.• A variant of imperative programming first introduced with the Norwegian language Simula in the mid60s.• Simula, Eiffel, Modula-3, C++.Logic Programming• Programming with relations.• Introduced in the early 70s. Based on predicate calculus. Prolog is popular with ComputationalLinguists.• Prolog, Parlog.5 Procedural ProgrammingWe program an abstraction of the Von Neumann Machine, consisting of a store (memory), a program (keptin the store), A CPU and a program counter (PC):storePCCPUAddressesDataX:Program:PC := PC + 8;X := X + 153JumpStoreUpdateComputing x:=x+11. Compute x’s address, send it to the store, get x’s value back.2. Add 1 to x’s value.3. Send x’s address and new value to the store for storage.4. Increment PC.26 Procedural Programming. . .The programmer...• uses control structures (IF, WHILE, ...) to alter the program counter (PC),• uses assignment statements to alter the store.• is in charge of memory management, i.e. declaring variables to hold values during the computation. function f a c t ( n : integer ) : integer ;var s , i : integer : = 1 ;beginwhile i<=n do s := s ∗ i ; i := i +1; end ;re tu rn s ;end f a c t .7 Procedural Programming. . .Procedural programming is difficult because:1. A procedural program can be in a large number of states. (Any combination of variable values andPC locations constitutes a possible state.) The programmer has to keep track of all of them.2. Any global variable can be changed from any location in the program. (This is particularly true oflanguages like C & C++ [Why?]).3. It is difficult to reason mathematically about a procedural program.8 Functional ProgrammingIn contrast to procedural languages, functional programs don’t concern themselves with state and memorylocations. Instead, they work exclusively with values, and expressions and functions which compute values.• Functional programming is not tied to the von Neumann machine.• It is not necessary to know anything about the underlying hardware when writing a functional program,the way you do when writing an imperative program.• Functional programs are more declarative than procedural ones; i.e. they describe what is to becomputed rather than how it should be computed.9 Functional LanguagesCommon characteristics of functional programming languages:1. Simple and concise syntax and semantics.2. Repetition is expressed as recursion rather than iteration.3. Functions are first class objects. I.e. functions can be manipulated just as easily as integers, floats,etc. in other languages.4. Data as functions. I.e. we can build a function on the fly and then execute it. (Some languages).310 Functional Languages. . .5. Higher-order functions. I.e. functions can take functions as arguments and return functions as results.6. Lazy evaluation. Expressions are evaluated only when needed. This allows us to build infinite datastructures, where only the parts we need are actually constructed. (Some languages).7. Garbage Collection. Dynamic memory that is no longer needed is automatically reclaimed by thesystem. GC is also available in some imperative languages (Modula-3, Eiffel) but not in others (C,C++, Pascal).11 Functional Languages. . .8. Polymorphic types. Functions can work on data of different types. (Some languages).9. Functional programs can be more easily manipulated mathematically than procedural programs.Pure vs. Impure FPL• Some functional languages are pure, i.e. they contain no imperative features at all. Examples: Haskell,Miranda, Gofer.• Impure languages may have assignment-statements, goto:s, while-loops, etc. Examples: LISP, ML,Scheme.12 What is a function?• A function maps argument values (inputs) to result values (outputs).• A function takes argument values from a source set (or domain).• A function produces result values that lie in a target set (or range).CapitalUSASwedenNZStockholmWashington DCWellingtonCopenhagenSource (Domain) FunctionTarget (Range)13 More on functions• A function must not map an input value to more than one output value. Example:IsPrettyJennyTrueFalsenot afunction !414 More on functions. . .• If a function F maps every element in the domain to some element in the range, then F is total. I.e.a total function is defined for all arguments.PlusIntIntInt15 More on functions. . .• A function that is undefined for some inputs, is called partial.IntIntIntDivide• Divide is partial since?0=? is undefined.16 Specifying functionsA function can be specified extensionally or intentionally.Extensionally:• Enumerate the elements of the (often infinite) set of pairs “(argument, result)” or “Argument 7→Result.”• The extensional view emphasizes the external behavior (or specification), i.e. what the function does,rather than how it does it.double = {· · ·, (1,2), (5,10), · · ·}even = {· · ·, (0,True), (1,False), · ·
View Full Document
Unlocking...