Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/Notes 2
Covered topics
edit- functional programming (design) methodologies:
- statements as expressions, and (as a consequence) function return semantics (see
if
,progn
(for CL) orbegin
(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
vslet*
, orsetq
vspsetq
(for CL)) - coding style;
- recursion;
Examples
editControl 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
editFrom the the book How to Design Programs:
- Section 2., Numbers, Expressions, Simple Programs:
- (m) exercises 2.2.1 (
fahrenheit->celsius
), 2.2.2 (dollar->euro
), 2.2.3 (triangle-area
), 2.2.4 (convert3
); - (m) exercises 2.3.1 (
tax
andnetpay
), 2.3.2 (sum-coins
); - exercise 2.3.3 (
total-profit
);
- (m) exercises 2.2.1 (
- Section 3., Programs are Function Plus Variable Definitions:
- (m) after reading the problem described in section 3.1. Composing Functions: exercises 3.1.1 (
attendees
), 3.1.2, 3.1.3; - exercise 3.2.1 (constants);
- exercise 3.3.1 (conversions);
- exercises 3.3.2 (
volume-cylinder
), 3.3.5 (height
);
- (m) after reading the problem described in section 3.1. Composing Functions: exercises 3.1.1 (
- Section 4., Conditional Expressions and Functions:
- (m) exercise 4.2.2 (intervals);
- exercise 4.2.3 (equations);
- (m) exercises 4.4.1 (
interest
), 4.4.2 (tax
), 4.4.3 (pay-back
);
References
editReading
editFor Scheme from the book An Introduction to Scheme and its Implementation (recommended):
- please note that it might seem many topics to read, but the pages are quite short in length;
- (m) Code Consists of Expressions (and all sections hierarchically under this one);
- (m) Some Other Control-Flow Constructs: cond, and, and or (and all sections hierarchically under this one);
- A Note about Parentheses and Indenting (and all sections hierarchically under this one);
- let, let*, Local Definitions;
- Variable Arity: Procedures that Take a Variable Number of Arguments;
- Variable Binding Again (and all sections hierarchically under this one);
- (m) Booleans and Conditionals;
- Sequencing;
- (m) Using Predicates (and all sections hierarchically under this one);
Also for Scheme from the book How to Design Programs:
- Section 3., Programs are Function Plus Variable Definitions (the entire section);
- Section 4., Conditional Expressions and Functions (the entire section);
- Section 5., Symbolic Information (the entire section);
For Common Lisp from the book Practical Common Lisp:
- (m) Chapter 4., Syntax and Semantics (the entire chapter, except maybe the Macros section);
- (m) Chapter 5., Functions (all sections from the beginning up to, but excluding, the Function Return Values section, but the sections Optional Parameters, Rest Parameters, Keyword Parameters and Mixing Different Parameter Types are optional);
- Variable Basics, Constants, Assignment (from Chapter 6., Variables);
- (m) WHEN and UNLESS, COND, AND, OR, and NOT (from Chapter 7., Macros: Standard Control Constructs);
API
edit- if, cond, when, unless, case
For Scheme:
- Section 2.2.5., Conditionals with if, and, or, and cond, Section 4.7., Conditionals, Section 4.8.3., Effects If...: when and unless, Section 4.12., Case (from Guide: PLT Scheme);
- Section 2.12., Conditionals: if, cond, and, and or, Section 2.16., Guarded Evaluation: when and unless, Section 2.13., Dispatch: case (from Reference: PLT Scheme);
- Section 11.4.3., Conditionals, Section 11.4.5., Derived conditionals (from R6RS);
For Common Lisp:
- Section 7.6., Conditionals (from Common Lisp the Language, 2nd Edition);
- Special operator IF, Macro COND, Macro WHEN, UNLESS, Macro CASE, CCASE, ECASE (from CLHS);
- progn, prog1, prog2 (CL)
Only for Common Lisp:
- Section 7.4., Simple Sequencing (from Common Lisp the Language, 2nd Edition);
- Special Operator PROGN, Macro PROG1, PROG2 (from CLHS);
- begin, begin0 (S)
Only for Scheme:
- Section 4.8., Sequencing, (from Guide: PLT Scheme);
- Section 2.15., Sequencing: begin, begin0, and begin-for-syntax (from Reference: PLT Scheme);
- Section 11.4.7., Sequencing (from R6RS);
- values
For Scheme:
- Section 4.5.3., Multiple Values and define-values (from Guide: PLT Scheme);
- Section 1.1.3., Multiple Return Values, Section 9.1., Multiple Values (from Reference: PLT Scheme);
- ??? (from R6RS);
For Common Lisp:
- Section 7.10., Multiple Values, (from Common Lisp the Language, 2nd Edition);
- Accessor VALUES, Macro NTH-VALUE, Macro MULTIPLE-VALUE-LIST, Special Operator MULTIPLE-VALUE-PROG1 (from CLHS);
- let, let*
For Scheme:
- Section 2.2.8., Local Binding with define, let, and let*, Section 4.6., Local Binding (from Guide: PLT Scheme);
- Section 2.9., Local Binding: let, let*, letrec, ... (from Reference: PLT Scheme);
- Section 11.4.6., Binding constructs (from R6RS);
For Common Lisp:
- Section 7.5., Establishing New Variable Bindings (from Common Lisp the Language, 2nd Edition);
- Special Operator LET, LET* (from CLHS);
- defun, defconstant, defparameter, defvar (CL)
Only for Common Lisp:
- Section 5.3.1., Defining Named Functions, Section 7.1., Constants and Variables (from Common Lisp the Language, 2nd Edition);
- Macro DEFUN, Macro DEFCONSTANT, Macro DEFPARAMETER, DEFVAR (from CLHS);
- define (S)
Only for Scheme:
- Section 2.2.8., Local Binding with define, let, and let*, Section 4.5., Definitions: define (from Guide: PLT Scheme);
- Section 2.14., Definitions: define, define-syntax, ... (from Reference: PLT Scheme);
- Section 11.2., Definitions (from R6RS);
- multiple-value-bind (CL)
Only for Common Lisp:
- Section 7.10., Multiple Values (from Common Lisp the Language, 2nd Edition);
- Macro MULTIPLE-VALUE-BIND (from CLHS);
- define-values, let-values, let*-values (S)
Only for Scheme:
- Section 4.5.3., Multiple Values and define-values, Section 4.6.5., Multiple Values: let-values, let*-values, letrec-values (from Guide: PLT Scheme);
- Section 2.9., Local Binding: let, let*, letrec, ... (from Reference: PLT Scheme);
- Section 2.14., Definitions: define, define-syntax, ..., Section 11.4.6., Binding constructs (from R6RS);