Programming Languages

G22.2110 Spring 1998

Class #9

OO Imperative Programming Languages - Part III

Functional Programming Languages

Homework #9: Sethi Exercises 8.9, 9.3, 9.5

Read Sethi’s Chapters 8, 9, 10, 15.5, 15.6, handouts and references

Contents

C9.0. Current Assignments, PL Project

C9.1. OO Imperative Programming Languages – Part III

C9.1.1. Object-Oriented Programming in Java

C9.2. Functional Programming Languages

C9.2.1. Introduction

C9.2.2. Mathematical Functions

C9.2.3. Fundamentals of Functional Programming Languages

C9.2.4. The First Functional Programming Language: LISP

C9.2.5. An Introduction to Scheme

C9.2.6. COMMON LISP

C9.2.7. ML

C9.2.8. Miranda

C9.2.9. Applications of Functional Languages

C9.2.10. A Comparison of Functional and Imperative Languages

C9.3. Comments on Sethi's Chapters 8, 9, 10, 15.5, 15.6

C9.0. Current Assignments, PL Project

Midterm results, solution midterm, solution hw #6, missing homeworks, incompletes

Homework #8 due today

Homework #9 due April 13, 1998

PL Project – Part II due today

PL Project – Part III postponed until April 8^{th} (due April 20)

C9.1. OO Imperative Programming Languages – Part III

C9.1.1. Object-Oriented Programming in Java

Hybrid OO programming language with wrapper classes to represent the primitive types as classes.

Classes and Objects

Access control and inheritance: private, package, protected, public.

Method parameters are "pass by value".

Object references are passed by value as well to enable changes to a single object copy.

Garbage collection, and finalize method.

Single inheritance, the root is Java's Object class

Interfaces can be used to express pure design (abstract methods, and related constants, classes, and interfaces), whereas a class is a mix of design and implementation.

Java has single inheritance of implementation, and multiple interface inheritance.

Fundamental building blocks: tokens, operators, and expressions.

Java is written in Unicode (16-bit character set)

Primitive types: boolean, char, byte, short, int, long, float, double.

Collections: arrays

Control flow: if-else, switch, while and do-while, for, no goto

Exception handling

Standard objects: strings

Standard Java libraries: string, threads, class, etc.

Packages: grouping for related interfaces and classes

I/O, standard utilities (collections, design patterns, localization, miscellaneous), abstract window toolkit, applet, beans (user-composable code), rmi, networking classes, math, sql (JDBC), security.

Access to general functions of the Java runtime system and the underlying operating system (runtime, process, system, and math class).

Support for Internationalization and Localization.

C9.2. Functional Programming Languages

Functional languages are based on mathematical functions.

Fundamental ideas behind mathematical functions:

Church’s lambda functional notation.

Functional forms

C9.2.1. Introduction

At the difference of imperative programming languages, functional programming language are oriented more to particular a programming paradigm (i.e., mathematical functions) and methodology than to efficient execution on a particular computer architecture (such as von Neuman’s).

LISP:

Initially pure functional PL

Soon acquired imperative features that increased its execution efficiency

Most widespread use

COMMON LISP:

Amalgam of several 1980s dialects of LISP

Scheme:

Small, static scoped descendant of LISP

ML:

Strongly typeFL

More conventional syntax than LISP or Scheme

Miranda:

Partially based on ML

Pure FL

C9.2.2. Mathematical Functions

Mathematical functions are mappings of members from one set (i.e., domain set) to another set (i.e., range set)

Function definition specifies the domain and range sets, either explicitly or implicitly, along with the mapping

Mapping is described as an expression

Functions can be applied to a particular element of the domain set

The domain set may be the cross-product of several sets

A function returns an element of the range set

The evaluation order of mapping expressions is controlled by recursion and conditional expressions (instead of sequencing and iterative repetition common to imperative PLs)

Functions do not produce side effects (i.e., given the same set of arguments, a mathematical function always yields the same value)

C9.2.2.1. Simple Functions

Function definitions: function name, followed by a list of parameters in parentheses, followed by the mapping expression.

e.g., cube(x) º x * x * x, where x is a real number

domain and range sets are the real numbers

the symbol º id used to mean "is defined as"

the parameter x can represent any member of the domain set

x is fixed to represent one specific element during evaluation of the function expression.

No such thing as a variable in mathematical functions.

Function applications are specified by pairing the function name with a particular element of the domain set.

The range element is obtained by evaluating the function mapping expression with the domain element substituted for the occurences of the parameter.

e.g., cube(2.0) yields the value 8.0

During evaluation, the mapping of a function contains no unbound variables (i..e, name for a particular value). Every occurrence of a parameter is bound to a value from the domain set and is considered a constant during evaluation.

Early theoretical work on functions separated the task of defining a function from that of naming the function.

Lambda notation (Church) provides a method for defining nameless functions. A lambda expression specifies the parameter and the mapping of a function. The value of a lambda expression is the function itself.

e.g., l (x)x*x*x

Parameter of lambda expression is sometimes called a "bound variable"

(l (x)x*x*x)(2) results in the value 8.

C9.2.2.2. Functional Forms

Complex functions in mathematics are defined in terms of other functions.

A higher-order function, or functional form, is one that either takes functions as parameters or yields a function as its result, or both.

e.g., function composition

h º f o g

two functional parameters

yields a function whose value is 1st actual parameter function applied to result of 2^{nd}.

f(x) º x+2, g(x) º 3*x then h(x) º f(g(x)) = (3*x) + 2

Construction is a functional form that takes a list of function as parameters

e.g., g(x) º x*x, h(x) º 2*x, i(x) º x / 2

[g,h,I](4) yields (16,8,2)

Apply-to-all is a functional form that takes a single function as a parameter

e.g., h(x) º x*x

a (h,(2,3,4)) yields (4,9,16)

C9.2.3. Fundamentals of Functional Programming Languages

Idea is to mimic mathematical functions to the greatest extent possible.

Imperative language:

Expression is evaluation and the result is stored in a memory location represented as a variable in a program.

Intermediate results of expression evaluations must also be stored (handled by the compiler in high level languages).

Purely functional PL:

Does not use variables or assignment statements.

Repetition is done by recursion instead of iteration (iteration requires variables to control it).

Programs are function definitions, and function application specifications.

Executions consist of evaluating the function applications.

Without variables, the execution of a purely functional program has no state.

The execution of a function always produces the same result when given the same parameters (referential transparency). As a result semantics are far simpler than that of imperative languages or FLs that include imperative features.

Functional languages are often implemented with interpreters, but they can also be compiled.

A FL provides a set of primitive functions (set of functional forms to construct complex functions from those primitive functions), a function application operation, and some structure or structures for storing data.

Imperative languages include some kind of function definition and enactment facility but have restrictions on the types of values that can be returned, cannot return a function (which limits the kinds of functional forms that can be provided), and are subject to functional side effects.

C9.2.4. The First Functional Programming Language: LISP

Evolved over the past 30 years.

Includes imperative language features: imperative-style variables, assignment statements, iteration.

C9.2.4.1. Data Types and Structures

Only 2 types of objects initially: atoms and lists.

These were not types (as in imperative languages), in fact the original version of LISP was typeless.

Atoms, which have the form of identifiers, are the symbols of LISP. Numeric constants are also considered atoms.

LISP originally used lists as its data structure because they were thought to be an essential part of list processing, but LISP rarely requires insertion and deletion.

Elements of simple lists are restricted to atoms:

e.g., (A B C D)

Nested list structures includes atoms and sublists:

e.g., (A (B C) D (E ( F G)))

Lists are usually stored as single-linked lists structures, in which each node has two pointers and represents an element:

Atom node has its first pointer pointing to some representation of the atom (symbol or numeric value).

Sublist element node has its first pointer pointing to the first node of the sublist, and its second pointer pointing to the next element of the list.

A list is referenced by a pointer to its first element.

C9.2.4.2. The First LISP Interpreter

Original intent was to have a notation for LISP programs that would be as close to FORTRAN’s as possible, with additions when necessary. This was called M-notation (meta-notation).

A compiler would translate programs written in M-notation into semantically equivalent machine code for the IBM 704.

McCarthy believed that the processing of symbolic lists was a more natural model of computation than Turing machines.

A common requirement of the study of computation is that one must be able to prove certain computability characteristics of the whole class of whatever model of computation is being use (in the Turing machine model, a universal Turing machine can mimic the operations of any other Turing machine). Hence the idea of constructing a universal LISP function that could evaluate any other LISP function.

Universal LISP function requirements:

Notation that allows functions to be expressed in the same way as data.

As parenthesized list notation had already been adopted for LISP data, it was decided to invent conventions for function definitions and function calls that could also be expressed in list notation.

Function calls were specified in a prefix form (Cambridge Polish):

(function_name argument_1 … argument_n)

e.g., (+ 5 7) evaluates to 12

Lambda notation was chosen and modified to specify function definitions. Modifications pertained to allowing the binding of functions to names so that functions could be referenced by other functions and by themselves. This name binding was specified by a list consisting of the function name and a list containing the lambda expression:

(function_name (LAMBDA (arg_1 … arg_n) expression))

LISP functions specified in this new notation were called S-expressions (symbolic expressions). An S-expression, or expression, can either be a list or an atom (as eventually both data and code were called S-expressions).

Note that nameless functions, although odd, are sometimes useful in functional programming (as well as mathematics).

McCarthy successfully developped a universal function that could evaluate any other function.

This function was called EVAL and was itself in the form of an expression.

It was noticed that an implementation of EVAL could serve as a LISP interpreter, and such implementation was quickly undertaken.

All early LISP systems copied EVAL and were therefore interpretive.

The definition of M-notation was never completed or implemented.

S-expressions became LISP’s only notation.

The use of the same notation for data and code has important consequences.

Much of the original language design was frozen, keeping certain odd features, such as the conditional expression form and the use of zero for both the NIL address and logical false.

Another feature of early LISP systems that was apparently accidental was the use of dynamic scoping: functions were evaluated in the environment of their callers.

Contemporary dialects (past 1975) either use static scoping or allow the programmer to choose between static and dynamic scoping.

C9.2.5. An Introduction to Scheme

C9.2.5.1. Origins of Scheme

Origins:

Dialect of LISP

MIT, mid-1970s

Small size, simple syntax and semantics, therefore well suited to educational applications

Exclusive use of static scoping

Treats functions as first-class entities (functions can be the values of expressions and elements of lists, and they can be assigned to variables and passed as parameters).

C9.2.5.2. Primitive Functions

Names can consist of letters, digits, and special characters except parentheses.

Names are case insensitive but must not begin with a digit.

Interpreter is a read-evaluate-write infinite loop.

Literals evaluate to themselves

Expressions that are calls to primitive functions are evaluated as follows:

each of the parameter expressions is evaluated in no particular order.

the primitive function is applied to the parameter values, and the result value is displayed.

Scheme includes primitive functions for the basic arithmetic operations (+, -, *, /).

+ and * can have zero or more parameters, if * is given no parameters, it returns 1, if + is given no parameters, it returns 0.

/ and - can have two or more parameters.

SUB1 takes one parameter, and returns its parameter after subtracting one from it.

ADD1 takes one parameter, and returns its parameter after adding one to it.

SQRT returns the square root of its numeric parameter if the parameter value is not negative.

Scheme includes operations for manipulating lists (selecting parts of a list, contructing lists, etc.)

EVAL is a function application operation. When called, it first evaluates the parameters of the given function (necessary when the actual parameters in the function call are themselves function calls and not atoms or lists).

QUOTE or " ' " function returns its parameter without change (without evaluation).

CAR function returns the first element of a given list.

CDR returns the remainder of a given list after its CAR is removed.

e.g.,

(CAR '(ABC)) returns A

(CAR '((A B) C D)) returns (A B)

(CAR 'A) is an error (A is not a list)

(CAR '(A)) returns A

(CDR '(A B C)) returns (B C)

(CDR '((A B) C D)) returns (C D)

(CDR 'A) is an error

(CDR '(A)) returns ( ) (empty list, also equivalent to NIL)

NIL is a name that is initially bound to ( ), but the binding can be changed by a program.

NIL and ( ) are both atoms and lists.

CONS is the Scheme primitive list constructor (inverse of CAR and CDR which take a list apart)

e.g.,

(CONS 'A '( ) ) returns (A)

(CONS 'A '(B C)) returns (A B C)

(CONS '( ) '(A B)) returns (( ) A B)

(CONS '(A B) '(C D)) returns ((A B) C D)

If "lis" is a list, then (CONS (CAR lis) (CDR lis)) is the identity function.

Important predicate functions: EQ?, ATOM?, NULL?

Boolean values are #T and #F (Scheme interpreter returns ( ) instead of #F)

e.g.,

(EQ? 'A 'A) returns #T

(EQ? 'A 'B) returns ( )

(EQ? 'A '(A B)) returns ( )

(EQ? '(A B) '(A B)) returns ( ) or #T

The result of comparing lists with EQ? is implementation dependent

EQ? is often implemented as a pointer comparison (do 2 given ptrs point to same places)

Two lists that are exactly the same are often not duplicated in memory.

When creating a list, the Scheme system checks to see if there is already such a list. If so, the new list is nothing more than a new pointer to the existing list which are then equal by EQ? It the presence of an identical list cannot be detected a new one is created and EQ? yields ( ).

EQ? works for symbolic atoms but not necessarily for numeric atoms.

EQ? does not work for list parameters.

ATOM? function returns #T if its single argument is an atom and ( ) otherwise.

e.g.,

(ATOM? '(X Y)) returns ( )

(ATOM? 'X) returns #T

(ATOM? 'NIL) returns #T

(ATOM? '( )) returns #T

NULL? function tests its parameters to determine whether it is the empty list and returns #T if it is.

eg.,

(NULL? '(A B)) returns ( )

(NULL? '( )) returns #T

(NULL? 'A) returns ( )

(NULL? '( ( ) ) ) returns ( ) (parameter is not empty list, but list containing an empty list)

(NULL? NIL) returns #T

Collection of predicate functions:

=, <>, >, <, >=, <=, EVEN?, ODD?, ZERO?

= works for numeric atoms but not for symbolic atoms

EQ? works for symbolic atoms but not necessarily for numeric atoms

EQV? works both on numeric and symbolic atoms

Output functions:

(DISPLAY expression)

(NEWLINE)

C9.2.5.3. Functions for Constructing Functions

LISP-based languages use lambda notation in list form to define functions.

e.g.,

(LAMBDA (L) (CAR (CDR L))) is a function that returns the second element of its given parameter, which must be a list.

((LAMBDA (L) (CAR (CDR L))) '(A B C)) yields B

L is called a bound variable in the lambda expression (never changes in the expression once bound to an actual parameter value at the time the lambda expression is first evaluated).

DEFINE is a special form function that is used to bind a name to a value, and to bind a name to a function definition.

e.g.,

(DEFINE symbol expression)

(DEFINE pi 3.14159)

(DEFINE two_pi (* 2 pi))

(DEFINE (function_name parameter_list)

body (* sequence of expressions in the form of lists)

)

(DEFINE (square number) (* number number))

(square 5) yields 25

(DEFINE (second lst) (CAR (CDR lst)))

(second '(A B C)) returns B

C9.2.5.4. Control Flow

Scheme has two control structures:

two-way selection and multiple selection

both are special forms (semantics different from normal primitives)

Two-way selector: (IF predicate then_expression else_expression)

e.g.,

f(n) º 1 (if n =0), n*f(n-1) if n>0

(DEFINE (factorial n)

(IF (= n 0)

1

(* n (factorial (SUB1 n)))

))

Multiple selector special form: COND

e.g.,

(COND

(predicate_1 expression { expression })

(predicate_2 expression { expression })

…

(predicate_n expression { expression })

(ELSE expression { expression })

)

If no parameter to COND has a predicate that evaluates to #T, COND returns ( )

LIST is a function that constructs lists from a variable number of parameters.

e.g.,

(LIST 'apple 'orange 'grape)

equivalent to (CONS 'apple (CONS 'orange (CONS 'grape '( ) )))

C9.2.5.5. Example Scheme Functions

Membership of a given atom in a given simple list:

e.g.,

(member 'B '(A B C)) returns #T

(member 'B '(A C D E)) returns ( )

(DEFINE (member atm lis)

(COND

((NULL? lis) NIL)

((EQ? atm (CAR lis)) T)

(ELSE (member atm (CDR lis)))

))

Determining whether two given lists are equal:

e.g., simple lists

(DEFINE (equalsimp lis1 lis2)

(COND

((NULL? lis1) (NULL? lis2))

((NULL? lis2) NIL)

((EQ? (CAR lis1) (CAR lis2))

(equalsimp (CDR lis1) (CDR lis2)))

(ELSE NIL)

))

e.g., general lists

(DEFINE (equal lis1 lis2)

(COND

((ATOM? lis1) (EQ? lis1 lis2))

((ATOM? lis2) NIL)

((equal (CAR lis1) (CAR lis2))

(equal (CDR lis1) (CDR lis2)))

(ELSE NIL)

))

Concatenating lists:

e.g.,

(append '(A B) '(C D R)) returns (A B C D R)

(append '((A B) C) '(D (E F))) returns ((A B) C D (E F))

(DEFINE (append lis1 lis2)

(COND

((NULL? lis1) lis2)

(ELSE (CONS (CAR lis1) (append (CDR lis1) lis2)))

))

Computing a list that represents the intersection of the sets given by the parameter lists:

e.g.,

(DEFINE (guess lis1 lis2)

(COND

((NULL? lis1) ( ) )

((member (CAR lis1) lis2)

(CONS (CAR lis1) (guess (CDR lis1) lis2)))

(ELSE (guess (CDR lis1) lis2))

))

LET: a function that allows names to be temporarily bound to the values of subexpressions

e.g.,

(LET (

(name_1 expression_1)

(name_2 expression_2)

…

(name_n expression_n))

body

)

The first n expressions are evaluated and the resulting values are bound to their associated names.

Then the expressions in the body are evaluated.

e.g.,

(DEFINE (quadratic_roots a b c)

(LET (

(root_part_over_2a

(/SQRT (- (* b b) (* 4 a c))) (* 2 a)))

(minus_b_over_2a (/ (- 0 b) (* 2 a)))

)

(DISPLAY (+ minus_b_over_2a root_part_over_2a))

(NEWLINE)

(DISPLAY (- minus_b_over_2a root_part_over_2a))

))

LET creates a new local static scope, much the same as Ada's declare.

(new variables can be created, used, and discarded when the end of the new scope is reached).

Named components of LET are like assignment statements, but they can be used only in LET's new scope and cannot be rebound to new values in LET.

LET is just a shorhand for a LAMBDA expression:

(LET ((alpha 7)) (* 5 alpha)) is equivalent to

((LAMBDA (alpha) (* 5 alpha)) 7)

7 is bound to alpha with LET or through the parameter of the LAMBDA expression

C9.2.5.6. Functional Forms

C9.2.5.6.1. Functional Composition

Only primitive functional form provided by the original LISP.

Functions are simply applied to the results of other function calls.

e.g.,

(CDR (CDR '(A B C))) returns ( C )

(CAR (CAR '((A B) B C))) returns A

(CDR (CAR '((A B C) D))) returns (B C)

(ATOM? (CAR '(A B))) returns #T

(NULL? (CAR '(( ) B C))) returns #T

(CONS (CAR '(A B)) (CDR '(A B))) returns (A B)

C9.2.5.6.2. An Apply-to-All Functional Form

mapcar has two parameters, a function and a list.

mapcar applies the given function to each element of the given list, and it returns a list of the results of these applications.

e.g.,

(DEFINE (mapcar fun lis)

(COND

((NULL? lis) ( ))

(ELSE (CONS (fun (CAR lis)) (mapcar fun (CDR lis))))

))

(mapcar (LAMBDA (num) (* num num num)) '(3 4 2 6)) yields (27 64 8 216).

C9.2.5.7. Scheme Functions That Build Scheme Code

Exploit the fact that programs and data have the same structure, and access to the function EVAL to allow user programs to construct other programs and immediately evaluate them.

Suppose that in a program, we have a list of numeric atoms an need the sum:

(DEFINE (adder lis)

(COND

((NULL ? lis) 0)

(ELSE (+ (CAR lis) (adder (CDR lis))))

))

Alternative is to write a function that builds a call to + with the proper parameter forms. This can be done by using CONS to insert the atom + into the list of numbers:

(DEFINE (adder lis)

(COND

((NULL? lis) 0)

(ELSE (EVAL (CONS '+ lis)))

))

e.g.,

(adder '(3 4 6)) causes adder to build the list (+ 3 4 6) which is then submitted to EVAL which invokes + and returns the result 13.

C9.2.5.8. Imperative Features of Scheme

Binding of names to values, and allowing bindings to be changed later:

e.g.,

(DEFINE pi 3.14159)

(SET! pi 3.14159) (* SET returns the value it binds *)

Changing a given list:

(DEFINE lst (LIST 'A 'B))

(SET-CAR! lst 'C) (* changes the list bound to lst from (A B) to (C B) *)

(SET-CDR! lst '(D)) (* changes the list bound to lst from (C B) to (C D) *)

Problems:

Programs become harder to debug and maintain because of aliasing, and the fact that side effects allow identical function calls to produce different results at different times.

e.g.,

(DEFINE count 0)

(DEFINE (inc_count number)

(SET! count (+ count number))

)

The following two calls to inc_count, although identical, produce different results:

(inc_count 1)

1

(inc_count 1)

2

C9.2.6. COMMON LISP (1984)

Created in an effort to combine the features of several early dialects 1980s dialects of LISP, including Scheme, into a single language.

Syntax, primitive functions, and fundamental nature come from the original LISP language.

Quite complex and large language.

Allows both static and dynamic scoping (can declare a variable to be "special" to make it dynamically scoped).

Large number of data types and structures (records, arrays, complex numbers, character strings)

Powerful input/output operations

Form of packages for modularizing collections of functions and data, and also providing access control.

Imperative features of Scheme (SET!, SET-CAR!, SET-CDR! and more).

Includes a function called PROG allowing statement sequencing (common in imperative languages), labels, and the two functions GO and RETURN (for iteration control).

GO is used to transfer control to a label within the scope of PROG.

RETURN is a means of exiting the PROG, it parameter becomes the value of PROG..

(PROG (local variables)

expression_1

…

expression_n

)

local variables are initialized to NIL, have the scope of the PROG, and exist only during execution of PROG.

global names that are the same as the locals are unaffected (and hidden) in PROG.

Expressions in PROG that are atoms are treated as labels.

PROG is included in contemporary versions of LISP only to provide backward compatibility with older dialects.

COMMON LISP has better constructs to provide the capabilities of PROG: DOTIMES, DOLIST constructs for iteration, and PROG1, PROG2, and PROGN for building sequences.

SETQ is the COMMON LISP function that corresponds to Scheme's SET!

DEFUN corresponds to DEFINE.

e.g., iterative and recursive version of the list membership function

(DEFUN iterative_member (atm lst)

(PROG ( )

loop_1

(COND

((NULL lst) (RETURN NIL))

((EQUAL atm (CAR lst)) (RETURN T))

)

(SETQ lst (CDR lst))

(GO loop_1)

))

(DEFUN recursive_member (atm lst)

(COND

((NULL lst) NIL)

((EQUAL atm (CAR lst)) T)

(T (recursive_member atm (CDR lst)))

))

e.g., iterative and recursive functions that compute the length of a list:

(DEFUN iterative_length (lst)

(PROG (sum)

(SETQ sum 0)

again

(COND

((ATOM lst (RETURN sum)))

)

(SETQ sum (ADD1 sum))

(SETQ lst (CDR lst))

(GO again)

))

(DEFUN recursive_length (lst)

(COND

((NULL lst) 0)

(T ADD1 (recursive_length (CDR lst)))

)

)

Scheme is far smaller and somewhat cleaner than COMMON LISP because of its exclusive use of static scoping.

COMMON LISP was meant to be a commercial language, and was widely used for AI applications.

C9.2.7. ML (1990)

Static-scoped functional programming language like Scheme.

Uses a syntax that is more similar to that of Pascal than that of LISP.

It includes: type declarations, uses type inferencing (variables do not need to be declared), and it is strongly typed.

The type of every variable and expression can be determined at compile time (on the other hand, Scheme is essentially typeless).

ML has exception handling, and a module facility for implementing ADTs.

In ML, names can be bound to values with value declaration statements of the form:

val new_name = expression;

e.g.,

val distance = time * distance;

This is not similar to the assignment statements in the imperative languages.

val binds a name to a value, but the name cannot be later rebound to a new value. These statements do not have any side effects (simply add a name to the current environment and bind it to a value like the LET special form of Scheme).

Normal use in a let expression:

let val new_name = expression_1 in expression_2 end

ML has lists and list operations (appearance is not like those of Scheme), enumerated types, arrays, and tuples which are records.

e.g., function declarations

fun function_name (formal_parameters) = function_body_expression;

fun square (x : int) = x * x;

fun square (x) = x * x; is illegal (type of x cannot be determined by the compiler)

Functions that use arithmetic operators cannot be polymorphic.

This is also true for functions that use relational operators (except = and <>, and booleans).

Functions that use only list operations, =, <>, and tuple operators (forming and selecting) can be polymorphic.

ML selection control flow construct:

if E then then_expression else else_expression

E must evaluate to a Boolean value.

No type coercions in ML; the types of the operands of an operator or assignment simply must match to avoid syntax errors.

C9.2.8. Miranda (1986)

Similar to ML (similar syntax, static scoped, strongly typed, uses same type inferencing method).

Differs from ML:

purely functional, no variables and no assignment statement, no side effects or imperative features of any kind.

Uses different evaluation technique (lazy evaluation): no subexpression is evaluated until its value is known to be required.

Has a method of defining lists that allows infinite lists (list comprehensions).

e.g., factorial function

fact 0 = 1

fact n = n * fact (n - 1) (function definition v.s. function application)

function definitions may include more than one line

proper function form is chosen by pattern matching actual parameters to formal ones.

function is partial as it is not defined for negative parameters

e.g., function computing nth Fibonaci number

fib 0 = 1

fib 1 = 1

fib (n+2) = fib (n+1) + fib n

Guards can be added to lines of a function definition:

e.g.,

fact n = 1, if n = 0

fact n = n * fact (n - 1), if n > 0 (pattern matching would fail here)

Lists are written in brackets:

colors = ["blue", "green", "red", "yellow"]

List operators: ++ (concatenation), : (infix version of CONS), # (length of a list), .. (arithmetic series)

e.g.,

#colors is 4

5:[2, 7, 9] is [5, 2, 7, 9]

[1, 3..11] is [1, 3, 5, 7, 9, 11]

List functions:

sum [ ] = 0

sum (a:x) = a + sum x

product [ ] = 1

product (a:x) = a * product x

fact n = product [1..n]

A where clause is similar to ML's let and val, except the bindings are given after the expression that uses them.

e.g.,

quadratic_root a b c =

[minus_b_over_2a - root_part_over_2a,

minus_b_over_2a + root_part_over_2a],

where

minus_b_over_2a = - b / (2 * a)

root_part_over_2a = sqrt ((b * b - 4 * a * c) / (2 * a))

List comprehensions provide a method of describing lists that contain sets:

[body | qualifier]

e.g.,

[n * n * n | n <- [1..50]]

defines a list of the cubes of the numbers from 1 to 50.

a list of all n*n*n such that n is taken from the range of 1 to 50.

This notation can be used to describe algorithms for doing many things, such as finding permutations of lists and sorting lists.

e.g.,

function which given a number n returns a list of all of its factors

factors n = [i | i <- [1..n div 2]; n mod i = 0]

concise implementation of quicksort algorithm:

sort [ ] = [ ]

sort (a:x) = sort [b | b <- x; b <= a]

++ [a}++

sort [b | b <- x; b > a]

Definition of infinite data structures using lazy evaluation:

e.g.,

positives = [0..]

evens = [2, 4..]

squares = [n * n | n <- [0..]]

Infinite lists can be used for computing particular values of recursive functions. The infinite list can act as a table in which the lookup can be done (only as much of the table as is needed will be computed).

e.g.,

fib 0 = 1

fib 1 = 1

fib (n+2) = fiblist ! (n+1) + fiblist ! n

where

fiblist = [fib n | n <- [0..]]

The "!" operator in the expression in this function is a binary operator for array indexing.

This version of fib takes linear time, whereas the recursive version takes exponential time.

Cost of lazy evaluation is far more complicated semantics which results in much slower speed of execution. Benefit is expressive power and flexibility.

C9.2.9. Applications of Functional Languages

Few functional languages have gained widespread use over the past 35 years of their history.

The most prominent is LISP:

Versatile and powerful language

Developed for symbolic computation and list-processing applications in the AI area of computing.

Most expert systems were developed in LISP.

LISP dominates the areas of knowledge representation, machine learning, natural language processing, intelligent training systems, and the modeling of speech and vision

Outside AI: the EMACS text editor is written in LISP, the MACSYMA symbolic mathematics system is written in LISP (does symbolic calculus), the LISP machine is a PC whose entire systems software is written in LISP.

Lisp has been used successfully to construct experimental systems in a variety of application areas.

APL, although it makes heavy use of the assignment statement, is often considered a functional language (partly because of its functional forms):

Used for hardware description to management information systems

Scheme is widely used to teach functional programming, and introductory programming courses.

The use of ML, and Miranda has been restricted to research laboratories, and to teach introductory programming courses.

C9.2.10. A Comparison of Functional and Imperative Languages

Computer architecture dependency:

Imperative PLs require management of variables and assignment of values to them.

Results are increased efficiency of execution, but laborious construction of programs.

In a FL, programmer need not be concerned with variables (memory cells are not abstracted in the language).

Result is decreased efficiency of execution, but higher level of programming (i.e., less labor).

Syntactic and semantic structures:

Much simpler than that of imperative languages

Concurrent execution:

Difficult to design and use in imperative PLs (e.g., tasking model of Ada where cooperation between tasks is the responsibility of the programmer)

Functional programs can be executed by translating them into graphs which can be executed through a graph reduction process using a great deal of concurrency not specified by the programmer.

In imperative languages, the programmer must make a complicated static division of the program into its concurrent parts (written as tasks).

Programs in functional PLs can be divided into concurrent parts dynamically by the execution system. Process is highly adaptable to the underlying hardware.

Understanding concurrent programs in imperative languages is much more difficult.

Functional programs may be more efficient than imperative languages on multiprocessor machines.

C9.3. Comments on Sethi's Chapters 8, 9, 10, 15.5, 15.6