Data Structures Notes

Note: these notes are directly related to the CPS 305 Ryerson Course and it's associated text book, and were created as a reference for myself. I will be updating it as the course progresses.

Week 01
Extras
- All Operators

Week 01

Text Book pages: 1 - 5, 11 - 28

Syntax Basics

Atoms

atoms evalutate themselves. ex:

numbers: 2, 2.0, 3/5
characters: #\a, #\@
strings: "abcg", "Hello World!"
booleans: T (true) and NIL (false)
symbols: a symbol evaluates to the value it identifies. Made up of leters, numbers, and characters like + - / * = <> ? ! _

S-expressions

S-expressions have specific rules for evaluation. Grouped S-expressions are called forms

syntax: ( op a1 a2 a3 ... )

op: the operator

a1 a2 a3 ...: the operands

Expressions

; same as doing 2 * 8
; operator comes first than the two numbers/parameters
(* 2 8)
; evaluates to 16

; you can chain operations aswell
; same as doing 2 + 4 * 4
(+ 2 (* 4 4))
; evaluates to 18

; another example
; same as doing (8/2) - (8*4)
(- (/ 8 2) (* 4 8))
; evaluates to -28

; (2 + 4 * 6) * (3 + 5 + 7)
(* (+ 2 (* 4 6)) (+ 3 5 7))
; evaluates to 390

; (2 - (3 - (6 + (4/5)))) / (3 * (6 - 2))
(/
    (- 2 (- 3 (+ 6 4/5)))     ; numerator
    (* 3 (- 6 2))             ; denominator
)
; evaluates to 29/60

Note: expressions can be written in one line or across many, use whatever is more comfortable.

Variables and Constants

Note: the examples below are for defining global variables and constants. Meaning that they sit in the global scope and can be accessed from anywhere in the program.

If you want to define a variable to be in only a local scope such as within a function or block you should use let instead of defvar.

Variables:
- Structure: (defvar [variable name] [value of variable] "description of variable")
Constants:
- Structure: (defparameter [constant name] [value of constant] "description of constant")
  
  Note: The description of variables/constants are optional with defining them.

; defines a mutable vairable *total-glasses* and assigns it's value to be 0
; u dont need the * * prefixing and suffixing the variable like the examples do, however it is good practice
(defvar *total-glasses* 0 "Total glasses so far")

; (defvar *total-glasses* 3) will not change the value of *total-glasses* because it has aldready been initialized
; setq will let u change the value
(setq *total-glasses* 3)

; same as *total-glasses* += 1
(setq *total-glasses* (+ *total-glasses* 1))


; defines a constant variable B and assigns it's value to be 20
; defined the constant B with the value of 20
; the value of a constant CANNOT be changed
(defparameter B 20)

Named Procedures

also refered to as functions

Structure: (defun [name of procedure] [parameters] [body])

; squares the value of x
(defun square (x) (* x x))

; gets the sum of the squares of two numbers
(defun sum-of-squares (x y)
    ; calls the square function from within this function
    (+ (square x) (square y))
)

Anonymous Functions

Sometimes we may want to quicly have a funtion and call it directly, for these cases we use lambda.

Structure: (lambda ([parameters...]) ([body]) [parameters (that will be used )...])

((lambda (x y) (+ x y)) 2 2)
; evaluates to 4

Blocks

Blocks allow for controlled sequential exectution. Strcuture: (block [name] [body])

(block test
    (print "hello")
    (+ 2 2)
)

; evaluates to:
; "hello"
; 4

block lets u create a named block, however progn can be used in place of block if you are calling the block directly. Structure: (progn [body])

(progn
    (print "hello")
    (+ 2 2)
)
; evaluates to:
; "hello"
; 4

Branching

Conditional expressions calculate the value of their first form and, depending on it, execute one of several alternative code paths.

(if (condition)
    (option-1)
    ; else
    (option-2)
)

When we need to do several things at once, in one of the conditional branches, it’s one of the cases when we need to use progn or block:

; if 6 > 4
(if (> 6 4)
    (progn (print "hello") (print "lisp"))
    ; else
    (print "world"))

; evalutates to:
; "hello"
; "lisp"

When we want to evaluate several conditions in a row we use cond:

(cond
    ; if condition 1
    ((> 4 6)
        (print "hello"))

    ; else if condition 2
    ((= 675 675)
        (print "world"))

    ; else
    (t ("nothing else worked")))

; evaluates to:
; "world"

Loops

To created a simple loop that loops from 0 to n-1, dotimes can be used.

Structure: (dotimes (i [n] [completed value]))

The completed value is an optional value that will be returned with the loop completes and is NIL by default.

Note: this is analogous to the for i in range(n): syntax used in python.

(dotimes (i 3)
    (print i))

; evaluates to:
; 0
; 1
; 2
; NIL

The i will have the current loop iteration assigned to it. It can be renamed.

A more versatile way to create loops is to use do.

Structure:

(do ((i [start value] ([increment by] [operation] i)

([body])))

(([exit condition]) i)

([body]))

(defvar i 0)
(do ((i 0 (1+ i))
    (print i))
    ((> i 4) i)
    ((print i)))

Note: i needs to be initialized prior.

End of Week 01

Extras

All Operators

Comparison operators (for numbers)

Operator	Meaning
`(= x y)`	x is `equal` to y
`(/= x y)`	x is `not equal` to y
`(< x y)`	x is `less than` to y
`(> x y)`	x is `greater` to y
`(<= x y)`	x is `less than or equal` to y
`(>= x y)`	x is `greater than or equal` to y
`max x y`	compares x and y and returns the `maximum` between the two
`min x y`	compares x and y and returns the `minimum` between the two

Logical operators (for booleans)

Operator	Meaning
`(and a b)`	a `and` b are both not `NIL`
`(or a b)`	a `or` b is not `NIL`
`(not a)`	`NIL` if a is `T` and `T` if a is `NIL`

nathanielfernandes/cps305-notes.md