Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/Notes 2


Functional programming (Spring 2010):

Discontinued due to lack of student interest.

Covered topics

edit
  • functional programming (design) methodologies:
  • statements as expressions, and (as a consequence) function return semantics (see if, progn (for CL) or begin (for Scheme));
  • function arguments:
    • optional arguments;
    • keyword arguments;
    • tail arguments;
  • multiple return values (see values and friends);
  • namespaces (closures) (see let and friends);
  • (possible) parallel evaluation; (see let vs let*, or setq vs psetq (for CL))
  • coding style;
  • recursion;

Examples

edit

Control structures as expressions

edit
'if' as an expression

Simple example: using if like an expression -- printing the maximum value of two variables:

  • in Scheme:
(define a 5)
(define b 7)
(print (if (> a b) a b))
  • in Java:
int a = 5;
int b = 7;
System.out.println ((a > b) ? a : b);
  • in Python:
a = 5
b = 7
print a if a > b else b
  • in Erlang:
A = 5,
B = 7,
io:format ("~p~n", [if A > B -> A; true -> B end]).
  • applicable to any programming language: we define a function that does the job; (but the drawback is that for each particular condition we have to define a new function, thus cluttering the namespace and loosing the locality relation of the code);
Simple value coercion

Another simple example: we have a function that returns a number or null (or however it is called in its respective language) if the value is not available (and thus we should default to a given value); now we want to use this output as an input to another function but taking into consideration this null case (the first function could be the lookup in a hash-table, a parameter from a configuration file, etc.):

  • in Scheme (we define a new variable visible only in this single spot):
(compute-something
    (let ((value (get-value)))
        (if (null? value) default-value value)))
  • in Erlang:
compute_something (
    case get_value () of
        null -> DefaultValue;
        Value -> Value
    end).
  • in C / C++ / Java: impossible (as an expression, without defining new functions that handle the coercion job):
Type v = getValue ();
computeSomething ((v != null) ? v : defaultValue);

A practical example: imagine we want to write a simple TCP/IP server, and we need to listen on a port (by default 9999), but this might be configured by an environment variable named PORT. We have the function listen that makes a socket listen on a port, then we have the function get-env that returns the value of the environment variable as a string, and convert-to-int which returns either the parsed number or #f in case the argument is not a number:

(define s ... obtain socket ...)
(listen s
    (let ((port (get-env "port")))
        (cond
            ((eq? port null) 9999)
            ((convert-to-int port))
            (#t 9999))))
List comprehension

More complex example: list comprehension expressions -- we have a function compute-something that takes as input a list representing a vector (from linear algebra), but we have to call it with the vectorial sum of two other vectors (represented as two lists of the same size) (as a simplification we ignore compute-something and we just print the result):

  • in Scheme:
(define a '(1 2 3))
(define b '(4 5 6))
(print (for/list ((i a) (j b)) (+ i j)))
  • in Python (only possible by using zip function):
a = [1, 2, 3]
b = [4, 5, 6]
print [i + j for i, j in zip (a, b)]
  • in Erlang (only possible by using lists:zip function):
A = [1, 2, 3],
B = [4, 5, 6],
io:format ("~p~n", [ [I + J || {I, J} <- lists:zip (A, B)] ]).
  • in C#: possible with list comprehensions (???);
  • in C / C++ / Java: impossible (as an expression, without the need to define functions) (???);

Now for a real example: imagine that we have a function returning a list of person structures (this function could be part of an ORM -- Object Relational Mapper -- framework), and we want to load in a combo-box a list of their names sorted alphabetically.

  • in Scheme (not actually tested, but proof of concept):
(define persons ... obtain the persons list ...)
(combo-set-labels! combo
    (sort (for/list ((p persons)) (person-get-name p))))
  • still in Scheme but more concise (not actually tested, but proof of concept):
(define persons ... obtain the persons list ...)
(combo-set-labels-! combo (sort (map person-get-name persons)))
  • in Python (not actually tested, but proof of concept):
persons = ... obtain the persons list ...
combo.set_labels (sorted (map (lambda p : p.name, persons))
  • in Java (not actually tested, but proof of concept):
List<Persons> persons = ... obtain the persons list ...;
List<Names> names = new ArrayList<String> ();
for (Person person : persons)
    names.append (person.getName ());
names = Collections.sort (names);
combo.setLabels (names);
  • in C#: possible with list comprehensions (???);

Multiple return values

edit
Values of the same type

Simple example: we have a compute function that computes and returns at the same time two (or multiple) values of the same time (practical examples computing min and max, or standard deviation and average, or two correlated numbers according to the normal distribution):

  • in Scheme:
(define (compute a b)
    (values (+ a b) (* a b) (/ a b)))

(define-values (s p f) (compute 1 2))
(print (list s p f))
  • in Erlang (at the shell):
Compute = fun (A, B) ->
    {A + B, A * B, A / B} end,

{S, P, F} = Compute (1, 2),
io:format ("~p ~p ~p~n", [S, P, F]).
  • in Python:
def compute (a, b) :
    return a + b, a * b, a / b

s, p, f = compute (1, 2)
print s, p, f
  • in Java (and in general in other programming languages):
int[] compute (int a, int b) {
    return new int[] {a + b, a * b, a / b};
}

...
int[] o = compute (1, 2)
s = o[0]
p = o[1]
f = o[2]
System.out.format ("%d %d %d", s, p, f);
  • in C: by using pointers:
void compute (int a, int b, int *s, int *p, int *f) {
    *s = a + b;
    *p = a + b;
    *f = a / b;
}
Values of multiple types

Complex example: what if our our function computes values of different kind:

  • in Scheme, Erlang, Python, and C: nothing changes;
  • in Java (and in general in other programming languages):
    • by casting an object array:
Object[] compute (/* arguments */) {
    return Object[] {/* compute first value */, /* compute second value */};
}

...
Object[] o = compute (/* arguments */)
// we must use a casts
TypeA a = (TypeA) o[0];
TypeB b = (TypeB) o[1];
    • by creating a special purpose structure-like class:
class Outcome {
    public Outcome (TypeA a, TypeB b) {
        this.a = a;
        this.b = b;
    }
    public TypeA a;
    public TypeB b;
}

Outcome compute (/* arguments */) {
    return new Outcome (/* compute first value */, /* compute second value */);
}

...
Outcome o = compute (/* arguments */);
    • by creating a general purpose pair-like class (or triplet, quadruplet, nth-uplet class) (usable in all these cases) (this can be extended to C++, C#, and in general to any programming language that supports meta-programming through templates / generics):
class Triplet<TypeA, TypeB, TypeC> {
    public Outcome (TypeA a, TypeB b, TypeC c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    public TypeA a;
    public TypeB b;
    public TypeC c;
}

Outcome compute (/* arguments */) {
    return new Triplet<MyTypeA, MyTypeB, MyTypeC> (/* compute first value of TypeA */, /* compute second value */, ...);
}

...
Triplet<TypeA, TypeB, TypeC> o1 = compute (/* arguments */);
Triplet<TypeA, TypeB, TypeC> o2 = compute (/* arguments */); // let's just assume we need two of this outcomes

Function arguments

edit
Optional arguments

Simple example of optional arguments: we have a function that looks-up a record in a database based on its key, but if it is not found we don't want an exception, but instead we want a context-sensible default value (by default null):

  • in Common Lisp:
(defun get-value (database key &optional (default nil))
    ...)

; ssn is Social Security Number (CNP in Romania)
(print (get-value persons ssn))
(print (get-value persons ssn "not-found"))
  • in Scheme:
(define (get-value database key (default null))
    ...)

(print (get-value persons ssn))
(print (get-value persons ssn "not-found"))
  • in Python:
def get_value (database, key, default = None) :
    ...

print get_value (database, key, "not-found")
  • in C++ / C# we have optional arguments also;
  • in Java: not possible (unless we use method overloading) (also possible in C++ / C#):
public Object getValue (Database database, Object key) {
    return getValue (database, key, null);
}

public Object getValue (Database database, Object key, Object default_) {
...
}
Keyed arguments

Keyed arguments: we have a function download that has has ability to get an URL over HTTP and allows us to specify:

  • URL (required);
  • where to output the contents (optional) (must be a file like object, by default let's say at standard output);
  • login name and password (both are optional);
  • timeout (by default 30 seconds), optional;

Question: is it possible to implement this by using optional arguments? Solution:

  • in Common Lisp:
(defun download (url &key (stream null) (login null) (password null) (timeout 60))
    ...)

(download "http://my-server/some-secret" :login "me" :password "secret")
(download "http://my-server/?some-service-query" :timeout 6)
  • in Scheme:
(define (download url #:stream (s null) #:login (l null) #:password (p null) #:timeout (t 60))
    ...)

(download "http://my-server/some-secret" #:login "me" #:password "secret")
(download "http://my-server/?some-service-query" #:timeout 6)
  • in Python (no difference than with optional arguments):
def download (url, stream = sys.stdout, login = None, password = None, timeout = 60) :
    ...

download ("http://www.google.com", stream = file ("/tmp/google.html", "w"))
download ("http://my-server/?some-service-query", timeout = 6, login = "me", password = "secret")
  • in most other programming languages (C / C++, C#, Java, Erlang, etc.) not possible, but possible in some (Ruby, etc.);
Rest arguments

Rest arguments: we need to implement a function that is able to take multiple arguments of the same kind (examples of such functions: min, max, average, etc.):

  • in Common Lisp:
(defun std-dev (&rest values)
    ...)

(print (std-dev 1 2 3 4 5 6))
  • in Scheme:
(define (std-dev . values)
    ...)

(print (std-dev 1 2 3 4 5 6))
  • in Python:
def std_dev (*values) :
    ...

print std_dev (1, 2, 3, 4)
  • in Java:
float std_dev (float ... values) {
    ...
}
  • in C / C++: not possible (there is the elipsis feature, but this is somehow different);
  • in most other languages it is impossible; however it is possible in some (Ruby);
Putting them all-together

It is possible to combine these features (at least in Common Lisp, Scheme and Python).

...

Exercises

edit

From the the book How to Design Programs:

References

edit

  The next topics are already covered by the course notes and are put here only for reference, or they are useful later when working on projects.

Reading

edit

For Scheme from the book An Introduction to Scheme and its Implementation (recommended):

Also for Scheme from the book How to Design Programs:

For Common Lisp from the book Practical Common Lisp:

if, cond, when, unless, case

For Scheme:

For Common Lisp:

progn, prog1, prog2 (CL)

Only for Common Lisp:

begin, begin0 (S)

Only for Scheme:

values

For Scheme:

For Common Lisp:

let, let*

For Scheme:

For Common Lisp:

defun, defconstant, defparameter, defvar (CL)

Only for Common Lisp:

define (S)

Only for Scheme:

multiple-value-bind (CL)

Only for Common Lisp:

define-values, let-values, let*-values (S)

Only for Scheme:

  To be finalized...

ToDo list:

  • show how normal, optional, keyed and rest arguments are combined together;
  • show the usage of recursion for an finite automaton;
  • show the usage of recursion for a network server loop;