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


Functional programming (Spring 2010):

Discontinued due to lack of student interest.

Optional (but highly recommended) reading

edit

The following essays are stolen from Shriram Krishnamurthi:

Discussion topics

edit
Concepts
Languages
Quick preview

First contact with Lisp

edit

Interpreter

edit

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

edit
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

edit
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

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 (recommended):

For Common Lisp from the book Practical Common Lisp: