Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/Notes 1
Optional (but highly recommended) reading
editThe 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
edit- Concepts
- programming paradigms:
- functional programming specific concepts:
- Languages
- pure functional:
- mainly functional:
- supporting functional style:
- Python;
- Ruby;
- JavaScript;
- Lua;
- Quick preview
First contact with Lisp
editInterpreter
editSteps to get started with the Lisp interpreter:
- installation:
- see the tools page;
- pick up an implementation (either Common Lisp, or Scheme);
- (for Windows) download the installation package and execute it;
- (for Linux):
- for Debian (Ubuntu, and other derivatives):
aptitude install clisp
(for GNU Common Lisp) oraptitude install plt-scheme
(for PLT Scheme); - for ArchLinux:
pacman -S clisp
(for GNU Common Lisp) orpacman -S drscheme
(for PLT Scheme);
- for Debian (Ubuntu, and other derivatives):
- enter:
- (for Windows) click the icon on desktop or search in Start Menu;
- (for Linux) open a terminal, and type
clisp
(for GNU Common Lisp) ormzscheme
(for PLT Scheme);
- evaluation: just write code, press
Enter
and see the evaluation results; - exit:
- (for Windows or Linux) either enter
(exit)
; - (for Linux) either press
Ctrl+D
; don't pressCtrl+Z
!
- (for Windows or Linux) either enter
Basic data-types
edit- Basic data types
- atoms:
- booleans:
- t, nil, () (CL);
- #t, #f (S);
- numbers (integer, rational, real, complex);
- symbols;
- booleans:
- 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
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) 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);