Transcript Scheme

Functional programming languages are characterized by the use of functions
(non-void methods) as the dominant control structure.
Functional Languages
APL
CLOS
FP
ML
LISP
Scheme
LISP
Scheme
• circa 1960 by John McCarthy (MIT)
• circa 1975 by Steele & Sussman
• Simple structures:
data - list
control - selection & recursion
• LISP with many extensions
• Usually interpreted (not compiled)
• Code and data have the same form (a list)
• A typeless language
• see www.drscheme.org
This is a Pure LISP-like subset.
<oneList>  ( <itemSequence> )
| <dottedPair>
<itemSequence>  
| <oneItem>
| <oneItem>  {} <itemSequence>
<dottedPair>  ( <oneItem> . <oneItem> )
<oneItem>  <quotedItem> | <unquotedItem>
<quotedItem>  ' <unquotedItem>
<unquotedItem>  <identifier>
| <integerConstant> | <realConstant>
| <booleanConstant> | <otherConstant>
| <oneList> | <dottedPair>
<identifier> is a valid identifier (case insensitive)
<integerConstant> is a valid integer literal
<realConstant> is a valid real (decimal) literal
<booleanConstant>  #t | #f
<otherConstant> is a string, character, etc. literal
NOTE: additional white space is permitted except within constants
and identifiers
Lists are essentially singly-linked lists, denoted via parentheses.
'(a b c d)
'( I (am ((a ghost) (help me)) ) )
Lists are built from 2-part cells
• the 1st part points at a list item
• the 2nd part points at the subsequent list cell
An alternative is a dotted pair (2-part cell consisting of two items)
'( x . y )
Note that '(1 2 3 4) is the same as '(1. (2 . (3 . (4 . () ) ) ) )
Avoid dot notation when possible.
Null Pointer Notation
In Scheme --In LISP ---
car
number of arguments: 1
precondition: argument must be a list of length 1 or more
postcondition: result == first item from the list
cdr
number of arguments: 1
precondition: argument must be a list of length 1 or more
postcondition: result == the argument list less the first item
cons
number of arguments: 2
postcondition: result == dotted pair of items (like prepending first to second list)
eq
number of arguments: 2
postcondition: result == arguments are equal (Scheme syntax: equals? )
atom
number of arguments: 1
postcondition: result == argument is a list (Scheme syntax (negation): list? )
(car '(a b c))
evaluates to
(car '((x y) (z)))
(cdr '(a b c))
evaluates to
evaluates to
(cdr '((x y) (z)))
(cdr '())
(cons 'a '(a b))
(cons 'x 'y)
(equal? 'a '(a))
(list? 'a)
(list? '(a))
evaluates to
evaluates to
evaluates to
evaluates to
evaluates to
evaluates to
evaluates to
Arguments are quoted to denote a literals.
'a is an abbreviation for (quote a)
'(a b) is an abbreviation for (list 'a 'b)
(cdr (cdr '(isnt that special)) )
(car (cdr '(isnt that special)) )
(car 'jack)
(car (car '((isnt that) special)) )
(car (cons 'a '(b c)) )
(cons (cons '1 '(2 3)) (cdr '(4 5 6)) )
(cons (car '(Wow can))
(cons (cdr '(this get))
(cons (equal? 'Messy 'Messy) '() )) )