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

Functional programming (Spring 2010): front; laboratory: agenda, references, projects, tools; notes (normal paced): 1, 2, 3, 4, 5, 6, 7, 8 (Spring 2009); notes (fast paced): 1, 2, 3, 4 (Spring 2010) (discontinued); applications: robots; mailing list: send mail, view archive, subscribe; author: Ciprian Dorin Craciun, ccraciun@info.uvt.ro;

Discontinued due to lack of student interest.

Optional (but highly recommended) reading

The following essays are stolen from Shriram Krishnamurthi:

• Beating the Averages, by Paul Graham;
• Teach Yourself Programming in Ten Years, by Peter Norvig;
• The Perils of JavaSchools, by Joel Spolsky;

Discussion topics

Concepts

• programming paradigms:
  • imperative;
  • declarative:
    • functional;
    • logic;
• functional programming specific concepts:
  • side-effects;
  • recursion;
  • high-order functions;
  • first class functions;
  • (lexical) closures;
  • continuations;
  • lazy evaluation;
  • (hygienic) macros;

Languages

• pure functional:
  • Haskell;
• mainly functional:
  • Lisp (family):
    • Scheme;
    • Common Lisp;
    • NewLisp;
    • Arc;
  • Erlang;
• supporting functional style:
  • Python;
  • Ruby;
  • JavaScript;
  • Lua;

Quick preview

• Quick: An Introduction to PLT Scheme with Pictures;

First contact with Lisp

Interpreter

Steps to get started with the Lisp interpreter:

1. installation:
   1. see the tools page;
   2. pick up an implementation (either Common Lisp, or Scheme);
   3. (for Windows) download the installation package and execute it;
   4. (for Linux):
      • for Debian (Ubuntu, and other derivatives): aptitude install clisp (for GNU Common Lisp) or aptitude install plt-scheme (for PLT Scheme);
      • for ArchLinux: pacman -S clisp (for GNU Common Lisp) or pacman -S drscheme (for PLT Scheme);
2. enter:
   1. (for Windows) click the icon on desktop or search in Start Menu;
   2. (for Linux) open a terminal, and type clisp (for GNU Common Lisp) or mzscheme (for PLT Scheme);
3. evaluation: just write code, press Enter and see the evaluation results;
4. exit:
   1. (for Windows or Linux) either enter (exit);
   2. (for Linux) either press Ctrl+D; don't press Ctrl+Z!

Basic data-types

Basic data types

• atoms:
  • booleans:
    • t, nil, () (CL);
    • #t, #f (S);
  • numbers (integer, rational, real, complex);
  • symbols;
• strings;
• lists;
• comments;

Examples (the text [1]> (for Common Lisp) or < (for Scheme) is actually the prompter and should not be written to the interpreter):

• numbers (either Common Lisp or Scheme):

[1]> 3.14
3.14

[2]> 20
20

[3]> 1/3
1/3

[4]> 55.2e-20
5.52E-19

• symbols as constant identifiers:
  • for Common Lisp:

[1]> pi
3.1415926535897932385L0

[2]> t
T

[3]> nil
NIL

• • for Scheme:

> pi
3.141592653589793

> null
()

• quoted symbols (for Common Lisp or Scheme) (notice the quote character ' before the symbol):

; in Common Lisp the symbols are case insensitive
[1]> 'abc
ABC
[2]> 'AbC
ABC

; in Scheme the symbols are case sensitive
> 'abc
abc
> 'AbC
AbC

• booleans (only for Scheme):

> #t
#t

> #f
#f

• strings (for both Common Lisp or Scheme)

[1]> ""
""

[2]> "abc"
"abc"

[3]> "AbC"
"AbC"

• lists (for both Common Lisp or Scheme) (again notice the quote character before the first opening parenthesis):

[1]> '(1 2)
(1 2)

[2]> '(1 (2 3) (4 (5 6)) 7)
(1 (2 3) (4 (5 6)) 7)

[3]> '(1 abc 2 cde)
(1 ACC 2 CDE)

[4]> '("abc" 1 (33 "4"))
("abc" 1 (33 "4"))

[5]> '()
NIL

[6]> '(1 () a)
(1 NIL A)

[7]> '(() ())
(NIL NIL)

Basic code

Generic topics

• function calls;
• predicates;
• naming conventions;

In the examples (for both Common Lisp or Scheme) notice that instead of putting the output of the evaluator on the next line, I've put the expected output as a comment after the expression ...expression... ; => ...expected-output...; and I've also dropped the prompter [1]>.

Arithmetic expressions

• arithmetic functions:
  • +, -, *, /, mod, rem (CL + S);
  • 1+, 1- (CL);
  • min, max (CL + S);
  • abs, floor, ceiling, trucncate, round (CL + S);
  • sqrt, exp, expt, log (CL + S);
  • signum (CL);
  • sin, cos, tan (CL + S);
  • examples:

(+ 1 2 3 4) ; => 10
(- 1 2 3 4) ; => -9
(* 1 2 3 4) ; => 24
(/ 1 2 3 4) ; => 1/24

; only in Common Lisp

(mod 7 3) ; => 1
(rem 7 3) ; => 1

; only in Common Lisp
(1+ 2) ; => 3
(1- 2) ; => 1

(min 1 2 3) ; => 1
(max 1/2 2 33/5) ; => 33/5

(abs -2.3) ; => 2.3
(floor 1/2) ; => 1
(truncate 1/2) ; => 1
(ceiling 1/2) ; => 2
(round 1.5) ; => 2
(round 2.5) ; => 2

(sqrt 1/4) ; => 1/2
(exp 2) ; => 7.389056
(expt 5/3 2) ; => 25/9
(log (exp 2)) ; => 2.0

(sqrt 1/4) ; => 1/2
(exp 2) ; => 7.389056
(expt 5/3 2) ; => 25/9
(log (exp 2)) ; => 2

(signum -55) ; => -1
(signum -55/3) ; => -1
(signum -55.0) ; => -1.0

(sin (/ pi 2)) ; => 0.707106...

• arithmetic predicates:
  • zerop, plusp, minusp (CL);
  • zero?, positive?, negative? (S);
  • <, <=, =, >=, >, /= (CL + S);
  • evenp, oddp (CL);
  • even?, odd? (S);
  • examples for Common Lisp:

(zerop 0) ; => t
(zerop 1) ; => nil
(plusp 1) ; => t
(plusp -1) ; => nil
(plusp 0) ; => nil
(minusp -1) ; => t
(minusp 1) ; => nil
(minusp 0) ; => nil

(< 1 2 3) ; => t
(< 1 3 1) ; => nil
(= 1 2 3) ; => nil
(/= 1 2 3) ; => t

(evenp 1) ; => nil
(oddp 1) ; => t

• • examples for Scheme:

(zero? 0) ; => #t
(zero? 1) ; => #f
(positive? 1) ; => #t
(positive? -1) ; => #f
(positive? 0) ; => #f
(negative? -1) ; => #t
(negative? 1) ; => #f
(negative? 0) ; => #f

(< 1 2 3) ; => #t
(< 1 3 1) ; => #f
(= 1 2 3) ; => #f

(even? 1) ; => #f
(odd? 1) ; => #t

Boolean expressions

• truth and falsehood;
• boolean functions;
  • not, null (CL);
  • not, null? (S);
• boolean forms;
  • and, or (CL + S);
• examples for Common Lisp:

(not nil) ; => t
(not ()) ; => t
(not t) ; => nil
(not 1) ; => nil
(null nil) ; => t
(null ()) ; => t
(null '(1 2 3)) ; => nil
(null 1) ; => nil

(and t nil) ; => nil
(and t t) ; => t
(and 1 2 3) ; => 3
(and 1 nil) ; => nil
(or t nil) ; => t
(or nil nil) ; => nil
(or 1 2 nil) ; => 1
(or nil 1 nil) ; => 1

• examples for Scheme:

(not null) ; => #f ; see the difference with Common Lisp
(not '()) ; => #f ; like above
(not #t) ; => #f
(not 1) ; => #f
(null? null) ; => #t
(null? '()) ; => #t
(null? '(1 2 3)) ; => #f
(null? 1) ; => #f

(and #t null) ; => null
(and #t #t) ; => #t
(and 1 2 3) ; => 3
(and 1 null) ; => null
(or #t null) ; => t
(or null null) ; => null
(or 1 2 null) ; => 1
(or null 1 null) ; => 1

Type predicates

• atomp (CL);
• symbolp (CL);
• symbol? (S);
• numberp, integerp, realp, rationalp, floatp, complexp (CL);
• number?, integer?, real?, rational?, complex? (S);
• stringp (CL);
• string? (S);
• listp (CL);
• list?, pair? (S);
• examples for Common Lisp:

(atom 'a) ; => t
(atom "a") ; => t
(atom 1) ; => t
(atom nil) ; => t
(atom '(1 2)) ; => nil
(atom ()) ; => t

(listp ()) ; => t
(listp '(1 2)) ; => t
(listp t) ; => nil
(listp nil) ; => t

(symbolp t) ; => t
(symbolp nil) ; => t
(symbolp "a") ; => nil
(symbolp 'a) ; => t
(symbolp ()) ; => nil

• examples for Scheme:

(list? '()) ; => #t
(list? '(1 2)) ; => #t
(list? #t) ; => #f ; see the difference with Common Lisp
(list? null) ; => #t

(symbol? 't) ; => t
(symbol? null) ; => #f ; see the difference with Common Lisp
(symbol? "a") ; => #f
(symbol? 'a) ; => #t
(symbol? '()) ; => #f ; see the difference with Common Lisp

References

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

For 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) What is Scheme?;
• (m) Code Consists of Expressions (and all sections hierarchically under this one);
• (m) The Boolean Values #t and #f;
• Comments;
• All Values are Pointers, All Values are Pointers;
• Objects Have Types, Variables Don't;

Also for Scheme from the book How to Design Programs (recommended):

• Section 1., Students, Teachers, and Computers (the entire section);
• Section 2., Numbers, Expressions, Simple Programs (the entire section);

For Common Lisp from the book Practical Common Lisp:

• (m) Chapter 1., Introduction: Why Lisp? (the entire chapter);
• (m) Chapter 2., Lather, Rinse, Repeat: A Tour of the REPL (all sections from the Free Your Mind: Interactive Programming section, up to, and including, the "Hello, World," Lisp Style section; optionally the entire chapter);
• (m) Chapter 4., Syntax and Semantics (all sections from the beginning up to, but excluding, the Macros section, but also read the Truth, Falsehood, and Equality section);