Movatterモバイル変換
[0]ホーム
CSc 520
Principles of Programming Languages
:
Christian Collberg
Department of Computer Science
University of Arizona
In contrast to procedural languages, functional programsdon't concern themselves with state and memorylocations. Instead, they work exclusivelywithvalues, andexpressions andfunctionswhich 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 moredeclarative than procedural ones; i.e. they describewhat is to be computed rather thanhow it should be computed.
Common characteristics of functional programming languages:
- Simple andconcise syntax and semantics.
- Repetition is expressed asrecursion rather than iteration.
- Functions are first class objects. I.e. functions can be manipulated just as easily as integers, floats, etc. in other languages.
- Data as functions. I.e. we can build a function on the fly and then execute it. (Some languages).
- Higher-order functions. I.e. functions can take functions as arguments and return functions as results.
- Lazy evaluation. Expressions are evaluated only when needed. This allows us to buildinfinite data structures, where only the parts we need are actually constructed. (Some languages).
- Garbage Collection. Dynamic memory that is no longer needed is automatically reclaimed by the system. GC is also available in some imperative languages (Modula-3, Eiffel) but not in others (C, C++, Pascal).
- Polymorphic types. Functions can work on data of different types. (Some languages).
- Functional programs can be more easilymanipulated mathematically than procedural programs.
Pure vs. Impure FPL
- Some functional languages arepure, 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.
- Functions and data share the same representation:S-Expressions.
- Scheme is animpure functional language.
- I.e., Scheme hasimperative features.
- I.e., in Scheme it is possible to program withside-effects.
- S-expressions are constructed usingdotted pairs.
- Scheme ishomoiconic, self-representing, i.e. programs and data are both represented the same (as S-expressions).
- To evaluate an expression(op arg1 arg2 arg3) we first evaluate the arguments, then apply the operatorop to the resulting values. This is known asapplicative-order evaluation.
- This is not the only possible order of evaluation
- Innormal-order evaluation parameters to a function are always passed unevaluated.
- Both applicative-order and normal-order evaluation can sometimes lead to extra work.
- Somespecial forms (cond,if, etc) must use normal order since they need to consume their arguments unevaluated.t
- One way to define the semantics of a language (the effects that programs written in the language will have), is to write ametacircular interpreter.
- I.e, we define the language by writing an interpreter for it, in the language itself.
- A metacircular interpreter for Scheme consists of two mutually recursive functions,Eval andApply.
- Lists areheterogeneous, they can contain elements of different types, including other lists.
- (equal? L1 L2) does a structural comparison of two lists.
- (eqv? L1 L2) does a ``pointer comparison''.
- This is sometimes referred to asdeep equivalence vs.shallow equivalence.
1#1
- Unlike languages like Java and C which arestatically typed (we describe in the program text what type each variable is) Scheme isdynamically typed. We can test at runtime what particular type of number an atom is:
- (complex? arg),(real? arg)
- (rational? arg),(integer? arg)
- A function ishigher-order if
- it takes another function as an argument, or
- it returns a function as its result.
- Functional programs make extensive use of higher-order functions to make programs smaller and more elegant.
- We use higher-order functions to encapsulate common patterns of computation.
- Haskell isstatically typed (the signature of all functions and the types of all variables are known prior to execution);
- Haskell useslazy rather than eager evaluation (expressions are only evaluated when needed);
- Haskell usestype inference to assign types to expressions, freeing the programmer from having to give explicit types;
- Haskell ispure (it has no side-effects).
- No expression is evaluated until its value is needed.
- No shared expression is evaluated more than once; if the expression is ever evaluated then the result is shared between all those places in which it is used.
- No shared expression should be evaluated more than once.
- Lazy evaluation makes it possible for functions in Haskell to manipulate `infinite' data structures.
- The advantage of lazy evaluation is that it allows us to construct infinite objects piece by piece as necessary
- Consider the following function which can be used to produce infinite lists of integer values:
countFrom n = n : countFrom (n+1) ? countFrom 1 [1, 2, 3, 4, 5, 6, 7, 8,^C{Interrupted!}] (53 reductions, 160 cells) ?- Haskell only supports one-argument functions. Multi-argument functions are constructed by successive application of arguments, one at a time.
- Currying is the preferred way of constructing multi-argument functions.
- The main advantage of currying is that it allows us to define specialized versions of an existing function.
- A function is specialized by supplying values for one or more (but not all) of its arguments.
- The most important concept of functional programming isreferential transparency.
- RT means that the value of a particular expression (or sub-expression) is always the same, regardless of where it occurs.
- RT makes functional programs easier to reason about mathematically.
- Pure functional programming languages are referentially transparent.
- We can evaluate itby substitution. I.e. we can replace a function application by the function definition itself.
- Expressions and sub-expressions always have the same value, regardless of the environment in which they're evaluated.
- The order in which sub-expressions are evaluated doesn't effect the final result.
- Functions have no side-effects.
- There are no global variables.
- Programs with side effects are hard to read and understand.
- Referential transparency -- expressions without side-effects can be executed in any order.
- equational reasoning -- if two expressions are ever the same, they are always the same.
- Interacting with the real world (file IO, terminal IO, GUI, networking, etc) doesn't seem to fit in well in the functional paradigm.
- Since, in these cases, we are actually ``changing the state of the world'', side-effect free programming is problematic.
- Haskell usesmonads to sequence IO operations. See Scott, pp. 607-609.
- A monad is an Abstract Data Type that supports sequencing.
- In pure functional languages variables never change.
- If we want to change the second element of a list[1,2,3] to 4, we have to create a new list, copying the elements from the original list.
- If we want to sort a list in a functional language we have to create new lists, rather than sorting in-place, which is more efficient.
- Adding two matrices 2#2 will create a new matrix, even if we're throwing away 3#3, and could do the addition in-place.
- Similarly, how do we construct an array of 0s without copying the entire array for every new element?
- Sisal is a functional language intended to be used for high-performance codes (scientific programming, think FORTRAN).
- The Sisal compiler tries to verify that an updated array will never be used again, if so, a copy need not be made.
- The Sisal compiler can remove 99-100% of all unnecessary copy operations this way.
http://tamanoir.ece.uci.edu/projects/sisal/sisaltutorial/Tutorial.htmltype OneDim = array [ real ];type TwoDim = array [ OneDim ];function generate( n : integer returns TwoDim, TwoDim ) for i in 1, n cross j in 1, n returns array of real(i)/real(j) array of real(i)*real(j) end forend function % generate
function doit( n : integer; A, B : TwoDim returns TwoDim ) for i in 1, n cross j in 1, n c := for k in 1, n t := A[i,k] * B[k,j] returns value of sum t end for returns array of c end forend function % doitfunction main( n : integer returns TwoDim )let A, B := generate( n )in doit( n, A, B )end letend function % main
- The Sisal compiler will automatically parallelize the code on the previous slide.
- Although the code looks imperative, it is actually functional. The compiler makes the necessary transformations of the loops intotail-recursion.
- Branch of mathematical logic. Provides a foundation for mathematics. Describes -- like Turing machines -- that which can be effectively computed.
- In contrast to Turing machines, lambda calculus does not care about any underlying ``hardware'' but rather uses simple syntactic transformation rules to define computations.
- A theory of functions where functions are manipulated in a purely syntactic way.
- Lambda calculus is the theoretical foundation of functional programming languages.
- To evaluate a lambda expression wereduce it until we can apply no more reduction rules. There are four principal reductions that we use:
- -- variable renaming to avoid name clashes in .
- -- function application.
- -- formula simplification.
- -- evaluation of predefined constants and functions.
- Question:
Can every lambda expression be reduced to a normal form?
- Answer: No.
4#4
- Lambda calculus containsnon-terminating reductions.
- Question:
Is there more than one way to reduce a lambda expression?
- Answer: Yes.
- Theleftmost redex is that redex whose 5#5 is textually to the left of all other redexes within the expression.
- Anoutermost redex is defined to be a redex which is not contained within any other redex.
- Aninnermost redex is defined to be a redex which contains no other redex.
- Anormal order reduction always reduces the leftmost outermost (or ) first.
- Aapplicative order reduction always reduces the leftmost innermost (or ) first.
- Question:
If there is more than one reduction strategy, does each one lead to the same normal form expression?
- Answer: Yes, if a lambda expression is in normal form, it is unique, except for changes in bound variables.
- Theorem:
For any lambda expressions 6#6, 7#7 and 8#8, if 9#9 and 10#10, there is a lambda expression 11#11 such that 12#12 and 13#13.
- Corollary:
For any lambda expressions 6#6, 14#14 and 15#15, if 16#16 and 17#17, where 14#14 and 15#15 are in normal form, 14#14 and 15#15 are variants of each other (except for changes in variables, using ).
- Question:
Is there a reduction strategy that will guarantee that a normal form expression will be produced, if one exists?
- Theorem:
For any lambda expressions 6#6 and 15#15, if 17#17 where 15#15 is in normal form, there is a normal order reduction from 6#6 to 15#15.
- Answer: Yes, normal order reduction will produce a normal form lambda expression, if on exists.
The effectively computable functions on the positive integers are precisely those functions definable in the pure lambda calculus.
- Turing Machines and lambda calculus are equivalent.
- Since it's not possible to determine whether a Turing Machine will terminate, it's not possible to determine whether a normal order reduction will terminate.
- Pure lambda calculus has no constant -- everything is a function.
- Data structures (lists), numbers, booleans, control structures (if-expressions, recursion) can all be constructed within a pure lambda calculus.
Christian S. Collberg
2005-04-22
[8]ページ先頭