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

From Wikiversity
Jump to: navigation, search


Lambda lc.svg

Functional programming (Spring 2010):

Nuvola apps important.svg 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]

Important! 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: