Principles of Programming Languages

:

**Christian Collberg**

* Department of Computer Science*

University of Arizona

In contrast to procedural languages, functional programs
don't concern themselves with state and memory
locations. 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 be computed rather than*how*it should be computed.

Common characteristics of functional programming languages:

- Simple and
*concise syntax*and semantics. - Repetition is expressed as
*recursion*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 build*infinite 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
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.

- Functions and data share the same representation:
*S-Expressions*. - Scheme is an
*impure*functional language. - I.e., Scheme has
*imperative*features. - I.e., in Scheme it is possible to program with
*side-effects*. - S-expressions are constructed using
*dotted pairs*. - Scheme is
*homoiconic*, self-representing, i.e. programs and data are both represented the same (as S-expressions).

- To evaluate an expression
we first evaluate the arguments, then apply the operator`(op arg1 arg2 arg3)``op`to the resulting values. This is known as*applicative-order*evaluation. - This is not the only possible order of evaluation
- In
*normal-order*evaluation parameters to a function are always passed unevaluated. - Both applicative-order and normal-order evaluation can sometimes lead to extra work.
- Some
*special 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 a
*metacircular 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`and`Apply`.

- Lists are
*heterogeneous*, 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 as
*deep equivalence*vs.*shallow equivalence*.

1#1

- Unlike languages like Java and C which are
*statically typed*(we describe in the program text what type each variable is) Scheme is*dynamically typed*. We can test at runtime what particular type of number an atom is:`(complex? arg)`,`(real? arg)``(rational? arg)`,`(integer? arg)`

- A function is
*higher-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 is
*statically typed*(the signature of all functions and the types of all variables are known prior to execution); - Haskell uses
*lazy*rather than eager evaluation (expressions are only evaluated when needed); - Haskell uses
*type inference*to assign types to expressions, freeing the programmer from having to give explicit types; - Haskell is
*pure*(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
is
*referential 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 it
*by 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 uses
*monads*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.

type 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 for end 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 for end function % doit function main( n : integer returns TwoDim ) let A, B := generate( n ) in doit( n, A, B ) end let end 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 into
*tail-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 we
*reduce*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 contains
*non-terminating reductions*.

**Question:**Is there more than one way to reduce a lambda expression?

**Answer:**Yes.

- The
*leftmost redex*is that redex whose 5#5 is textually to the left of all other redexes within the expression. - An
*outermost redex*is defined to be a redex which is not contained within any other redex. - An
*innermost redex*is defined to be a redex which contains no other redex. - A
*normal order*reduction always reduces the leftmost outermost (or ) first. - A
*applicative 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.

- Read Scott, pp. 622-623.

2005-04-22