csc 123 - scheme intro notes:

to run scheme on solaris at hofstra:
/shared/csc/local/bin/scheme

(do setenv PATH /shared/csc/local/bin/scheme:$PATH)  This is MIT Scheme.

However, since we're switching from solaris to linux, this won't work unless
you're directly logged on to husun3.  You can download scheme from the "MIT
Scheme" link on the homepage.  MIT scheme is the recommended variety.  In the
windows version of scheme, to load a scheme file from a location, say 
c:\scheme\myprogram.scm, do (load "c:\\scheme\\myprogram.scm") : you need
the double \\ because \ is the special escape character inside strings. You
can also use the Unix style "/": (load "C:/Scheme/Myprogram.scm").


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))))