csc 123 - scheme intro notes:


Best way to run scheme is to download the stable release linux or windows
binary from the MIT scheme website.

Scheme Descends from Lisp is Interpreted language (although
functions can be compiled).  Functional language - expressions
and statements blur.  Symbolic language - highly abstract - deal
with symbols without being concerned with low-level
representation.

give it an expression it will evaluate it:

3, 3.14, etc

Everything is in prefix notation, lambda-calc notation:

Don't use () without thinking.
(f a)
(f a b) 
(+ 3 4 5), etc
(/ 9 2) ; integer division
(/ 9 2.0) ; float equality
(expt 2 1000) ; don't try with any other language!

(= 3 4) ; integer equality
(> 3 4)
(equal? "abc" "abc") ; structural equality
#t, #f, and or, etc


(lambda (x) (+ x 1))

((lambda (x) (+ x 1)) 4)

(if 3 4 5)     - #t and #f.


(define a 3)   ; look ma, no type!
(define b 3.14)

(define f (lambda (x) (+ x 1)))
(f 3)  ; returns 4

(define (f x) (+ x 1))  ; same as above


Symbols:

3 - an int
'3 - a token
'(+ 3 4) ; a structural expression (not evaluated, a list of symbols).
'(a b c) - a "list data structure".

' means don't evaluate - i.e., don't beta-reduce.

Can't think of data structure the way you think in C, think about it at 
a higher level, that is to say, symbolically.

basic data structure: linked list
() - empty list
(cons 'a () - '(a)
'(a b) - a list with two symbols
(a b) - function a applied to argument b, which is evaluated first.

(car l) ; head 
(cdr l) ; tail


Scheme is untyped:
'(3 3.14)  ; a list with int and double - that's fine, even

'(3 3.14 "hello") ; is ok

; lists can even contain nested lists - don't try this with C!:

'((2 3) 4)
; note there are two elements in this list, the first is itself a list

(car '((2 3) 4)) returns (2 3)

; more examples:

; built-in operations on lists:

(append '(a b c) '(1 2 3))  ; gives '(a b c 1 2 3)

(length '(a b c)) ; gives 3

; classic n! function
(define f (lambda (n) (if (< n 2) 1 (* n (f (- n 1))))))

; Euclid's algorithm
(define (gcd a b) (if (equal? a 0) b (gcd (remainder b a) a)))

; function that returns the nth element of in list L:
(define (nth n L) (if (equal? n 0) (car L) (nth (- n 1) (cdr L))))