Notes about Coursera "Programming Languages": https://www.coursera.org/course/proglang - part 2 (Racket)

proglang.rkt

( Introduction to Racket:

	Racket:
		- functional focus
		- with imperative features
		- dynamically-types
		- minimalist syntax
		- advanced features: modules, macros, etc...

	(note: we will not use pattern matching, but it exists)

	Racket vs Scheme:
		- Very similar
		- Racket is the evolution of Scheme (with non backward-compatible changes) 
		- Racket is moving fast

	Basics:
		comment: 
			; look 'ma, a comment!
		mandatory header:
			#lang racket ; it could be another language
		import:
			(provide (otherFile)) ; make all functions of 'otherFile' public (they are private, by default)
		define variable:
			(define s "hello")
)

( Racket Definitions, Functions, Conditionals:

	Defining a variable:
		; using '-' in names is conventional
		(define hello-world "hello")

	Calling a function:
		; syntax is: 
		; (function-name arg1 ... argn)
		(+ 1 2) ; example: calling '+' function

	Defining a function: 
		(define cube1 ; create a binding...
			(lambda (x) ; ... to anonymous function
				(* x (* x x))))

		(define cube2
			(lambda (x)
				(* x x x) ; '*' function can take any number of arguments

		(define cube3
			(* x x x) ; we can omit 'lambda' (syntactic sugar)

	Conditionals:
		(if (= y 0) 42 666)

	Currying:
		; less common in Racket because of built-in support for multi-argument functions
		(define (pow x y)
		  (if (= y 0)
		      1
		      (* x (pow x (- y 1)))))

		(define curried-pow
		  (lambda (y)
		    (lambda (x)
		      (pow x y))))

		(define pow3 (curried-pow 3))
		; there is syntactic sugar for defining a curried function
)

( Racket Lists

	Syntax:
		empty list: null
		Cons constructor: cons ; (cons i1 my-list) ; new list adding i1 in head of my-list
		List constructor: list ; (list i1 i2 i3) 
		Access head of list: car ; historical accident
		Access tail of list: cdr ; historical accident	
		Check for empty: null?

	Code examples:
		; list processing: null, cons, null?, car, cdr
		; we won't use pattern-matching in Racket

		(define (sum xs)
		  (if (null? xs)
		      0
		      (+ (car xs) (sum (cdr xs)))))
		(sum (list 1 2 3 4)) ; returns 10
		(sum (list 1 2 "3" 4)) ; Oops, runtime error!

		(define (my-append xs ys) ; same as append already provided (we could have shadowed it but we prefer not)
		  (if (null? xs)
		      ys
		      (cons (car xs) (my-append (cdr xs) ys))))

		(define (my-map f xs) ; same as map already provided
		  (if (null? xs)
		      null
		      (cons (f (car xs)) (my-map f (cdr xs)))))

		(define foo (my-map (lambda (x) (+ x 1)) 
							(cons 3 (cons 4 (cons 5 null)))))
)

( Syntax and Parentheses
	Racket has a amazing simple syntax!

	Rackets code is composed of terms.
	A term is either:
		- an atom (e.g. #t, 32, "hi", null, 4.0, x, ...)
		- a special form (e.g. define, lambda, if) ; macros will let us write our own special forms
		- a sequence of terms in parens:
			(t1 t2 ... tn)
			if t1 is a special form, semantics is special
			else a function call

	Brackets vs parens
		[ ] can be used instead of ( ) ; just a matter of style

	Trival tree representation:
		Using parens makes tree representation (for indenting, compiling, etc...) trivial.
		No need to discuss about operator precedence

		Example:
		 (define cube (lambda (x) (* x x x)))
		 ; can be represented as:
		 define
		 /    \ 
	  cube 	lambda
	 		/	\
 		   x 	 *
 				/ | \
 			   x  x  x

   Parenthesis bias:
		Like XML, but without verbose closing
		Only harder to read at first, but them it's OK
		=> irrational dislikes of LISP parens bashing
		http://xkcd.com/297/
)

( Parentheses Matter! (Debugging Practice)
	Adding/remove parens means changing code (and probably make it fail at runtime)

	Code examples:
		; [first big difference from ML (and Java)] PARENS MATTER!!

		(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

		; base case calls the function 1 with zero arguments
		(define (fact-wrong1 n) (if (= n 0) (1) (* n (fact-wrong1 (- n 1)))))

		; so why does this work (hint: it's not recursive
		; and there is no type system):
		(define (fact-works1b n) (if (= n 0) (1) (* n (fact (- n 1)))))

		; passing 5 arguments to if: =, n, 0, 1, (* ...)
		; this is bad syntax
		;(define (fact-wrong2 n) (if = n 0 1 (* n (fact-wrong2 (- n 1)))))

		; calling n with zero arguments and also having an if
		; this is not a legal definition: bad syntax
		;(define fact-wrong3 (n) (if (= n 0) 1 (* n (fact-wrong3 (- n 1)))))

		; calling multiply with three arguments, which would be fine
		; except the second one is fact-wrong4
		(define (fact-wrong4 n) (if (= n 0) 1 (* n fact-wrong4 (- n 1))))

		; calling fact-wrong5 with zero arguments, calling result of that
		; with n-1
		(define (fact-wrong5 n) (if (= n 0) 1 (* n ((fact-wrong5) (- n 1)))))

		; treating n as a function of two arguments, passing it *
		(define (fact-wrong6 n) (if (= n 0) 1 (n * (fact-wrong6 (- n 1)))))
)

( Dynamic Typing

	For now, frustating because it does not catch "little errors" like (n * x) => need more tests / documentation
 	But it can be very useful for very flexible data structures

	Example: sum the numbers nested in a list that can contain numbers and non-numbers (we cannot do that in ML)

	Code:
		(provide (all-defined-out))

		; [second big difference from ML (and Java)] Dynamic Typing!!

		; dynamic typing: can use values of any type anywhere
		;  e.g., a list that holds numbers or other lists

		; this function sums lists of (numbers or lists of (numbers or ...)),
		; but it does assume it only encounters lists or numbers (else run-time error)
		(define (sum1 xs)
		  (if (null? xs)
		      0
		      (if (number? (car xs))
		          (+ (car xs) (sum1 (cdr xs)))
		          (+ (sum1 (car xs)) (sum1 (cdr xs))))))

		; this version does not fail on non-lists -- it treats them as 0
		(define (sum2 xs)
		  (if (null? xs)
		      0
		      (if (number? (car xs))
		          (+ (car xs) (sum2 (cdr xs)))
		          (if (list? (car xs))
		              (+ (sum2 (car xs)) (sum2 (cdr xs)))
		              (sum2 (cdr xs)))))

	  	(sum1 (list 1 2 3 (list 4)) ; 7
  		(sum1 (list 1 2 3 (list 4) "foo")) ; RUNTIME ERROR!
	  	(sum2 (list 1 2 3 (list 4) "foo")) ; 7  	
)

( Cond
	
	Cond-expressions are often better style that if expressions

	Syntax:
		(cond [test1 exp1] [test2 exp2] ... [testn expn])
		; test1 ... testn can evaluate to #t, #f or any other value (=> means #t)
		; it's a good-practice that last test (testn) is #t (true) => default case that prevents later error

	Example:
		; sum3 is equivalent to sum1 from previous segment but better style
		(define (sum3 xs)
		  (cond [(null? xs) 0]
		        [(number? (car xs)) (+ (car xs)(sum3 (cdr xs)))]
		        [#t (+ (sum3 (car xs)) (sum3 (cdr xs)))]))

		; sum4 is equivalent to sum2 from previous segment but better style
		(define (sum4 xs)
		  (cond [(null? xs) 0]
		        [(number? xs) xs]
		        [(list? (car xs)) (+ (sum4 (car xs)) (sum4 (cdr xs)))]
		        [#t (sum4 (cdr xs))]))

		; this function counts how many #f are in a (non-nested) list
		; it uses the "controversial" idiom of anything not #f is true
		(define (count-falses xs)
		  (cond [(null? xs) 0]
		        [#t (+ 1 (count-falses (cdr xs)))]))
		        [(car xs) (count-falses (cdr xs))] ; (car xs) can have any type
)

( Local Bindings:
	Syntax:
		(let ([x1 exp1] [x2 exp2] ... [n expn]) ; body where bindings exist)

	Racket has several types of local bindings
	- let
	- let*
	- letrec
	- define

	let:
		(let ([x1 exp1] [x2 exp2] ... [n expn]) ; body where bindings exist)
		All expressions are evaluated from environment before 'let'
		ex:
			(define x 3)
			(let([x x+1] [y x+1] ) ... ) ; x and y are bound to 4 
	let*:
		Similar but expressions can used previous bindings (like ML).
		Bindings can be repeated (=> previous binding is shadowed)
		ex:
			(define x 3)
			(let([x x+1] [y x+1] ) ... ) ; x=4 y=5

	letrec:
		Expressions can use environment and all bindings but are evaluated in order.
		Needed for mutual recursion, otherwise it's better not to use letrec (bad style < bugs)

	local define:
		Can be used in certain positions (beginning of a function body).
		Same semantics as letrec.


	Examples:
		#lang racket

		(provide (all-defined-out))

		; notice the parentheses in the let-expressions
		(define (max-of-list xs)
		  (cond [(null? xs) (error "max-of-list given empty list")]
		        [(null? (cdr xs)) (car xs)]
		        [#t (let ([tlans (max-of-list (cdr xs))])
		              (if (> tlans (car xs))
		                  tlans
		                  (car xs)))]))

		; 4 forms of local bindings

		; let evaluates all expressions using outer environment, 
		; *not* earlier bindings
		(define (double1 x)
		  (let ([x (+ x 3)]
		        [y (+ x 2)])
		    (+ x y -5)))

		; let* is like ML's let: environment includes previous bindings
		(define (double2 x)
		  (let* ([x (+ x 3)]
		         [y (+ x 2)])
		    (+ x y -8)))
		  
		; letrec uses an environment where all bindings in scope
		; * like ML's use of and for mutual recursion
		; * you get an error if you use a variable before it's defined
		;   where as always function bodies not used until called
		;   (bindings still evaluated in order)
		; (In versions of Racket before 6.1, you got an #<undefined> value instead,
		;  which would typically cause an error as soon as you used it.)
		(define (triple x)
		  (letrec ([y (+ x 2)]
		           [f (lambda (z) (+ z y w x))]
		           [w (+ x 7)])
		    (f -9)))

		(define (mod2 x)
		  (letrec 
		      ([even?(lambda (x) (if (zero? x) #t (odd? (- x 1))))]
		       [odd? (lambda (x) (if (zero? x) #f (even? (- x 1))))])
		    (if (even? x) 0 1)))

		(define (bad-letrec-example x)
		  (letrec ([y z] ; okay to be a lambda that uses z, but here y undefined
		           [z 13])
		    (if x y z)))

		; and you can use define locally (in some positions)
		; the same as letrec when binding local variables
		(define (mod2_b x)
		  (define even? (lambda(x)(if (zero? x) #t (odd? (- x 1)))))
		  (define odd?  (lambda(x)(if (zero? x) #f (even? (- x 1)))))
		  (if (even? x) 0 1))
)

( Toplevel Bindings

	letrec bindings can refer to previous bindings and to later bindings (in funcion bodies, only)
	But letbind binding cannot be called before later binding is evaluated
	=> cannot use shadowing (it would let to error)

	Beware: REPL works differently
	=> do not shadow bindings in the REPL
	=> do not define recursive functions in REPL

	Each file is implicitly a module

	Code:
		; Programming Languages, Dan Grossman, Jan-Mar 2013 
		; Section 5: Top-Level Bindings

		#lang racket

		(provide (all-defined-out))

		; at the top-level (*)
		; same letrec-like rules: can have forward references, but
		;  definitions still evaluate in order and cannot be repeated

		(define (f x) (+ x (* x b))) ; forward reference okay here
		(define b 3)
		(define c (+ b 4)) ; backward reference okay
		;(define d (+ e 4)) ; not okay (get an error)
		(define e 5)
		;(define f 17) ; not okay: f already defined in this module

		; (*) we are not actually at top-level -- we are in a module called 91_toplevel_bindings
)

( Mutation with set!

	We need assignment for some idioms. Beware, use it approppriatly!

	assignment:
		(set! x e) ; "set bang" updates value of x with expression e

	sequence:
		(begin e1 e2 ... en) ; evaluates to en, useful if expressions have side-effects (printing, assignments, etc...)

	Protection against mutation:
		Make a local copy via local let binding (can have the same name).

	Code:
		; Programming Languages, Dan Grossman, Jan-Mar 2013 
		; Section 5: Mutation With set!

		#lang racket

		(provide (all-defined-out))

		(define b 3) 
		(define f (lambda (x) (* 1 (+ x b)))) 
		(define c (+ b 4)) 
		(set! b 5)
		(define z (f 4))   
		(define w c)       

		; a safe version of f would make a local copy of b
		; no need to call the local varaible b also, but no reason not to either
		(define f 
		  (let ([b b])
		    (lambda (x) (* 1 (+ x b)))))

		; but maybe that is not good enough since + and * are also procedures
		(define f 
		  (let ([b b]
		        [+ +]
		        [* +])
		    (lambda (x) (* 1 (+ x b)))))

		; it turns out:
		;  1. this technique doesn't work if f calls a function that itself calls
		;     things that might get mutated
		;  2. we don't have to worry about this in Racket because +, * are immutable:
		;     the general rule is a top-level binding is mutable only if /that/ module
		;     contains a set! of it
)

( The Truth About Cons

	Pairs vs Lists:
		cons just makes a pair.
		Lists are nested pairs with null at the end.
		car: first item of pair.
		cdr: second item of pair.
		caddr: 3rd item of a list i.e. (car (cdr (cdr xs)))
		List = "proper list" vs pair = "inproper list"
		pair? returns #t for pairs and lists
		list? only returns #t for lists (proper lists)

	Style:
		Use proper list for collection of unknown size
		Pairs are OK for fixed-size collections

	Code:
		(define pr (cons 1 (cons #t "hi"))) 
		(define lst (cons 1 (cons #t (cons "hi" null))))
		(define hi (cdr (cdr pr)))
		(define hi-again (car (cdr (cdr lst))))
		(define hi-again-shorter (caddr lst))
		(define no (list? pr))
		(define yes (pair? pr))
		(define of-course (and (list? lst) (pair? lst)))
		; (define do-not-do-this (length pr))
)

( mcons For Mutable Pairs:

	cons cells are immutable
	mcons creates mutable cons cells
		- mcar/mcdr/mpair? are equivalent to car/cdr/pair? 
		- set-mcar! / set-mcdr!: update head / tail
		- but mcons cannot be mixed with cons

	Code:
		; cons cells are immutable -- this does not change a cell's contents
		(define x (cons 14 null))
		(define y x)
		(set! x (cons 42 null))
		(define fourteen (car y))

		; but since mutable pairs can be useful, Racket has them too:
		;  mcons, mcar, mcdr, set-mcar!, set-mcdr!
		(define mpr (mcons 1 (mcons #t "hi")))
		(set-mcdr! (mcdr mpr) "bye")
		(define bye (mcdr (mcdr mpr)))

		; Note: run-time error to use mcar on a cons or car on an mcons
)

( Delayed Evaluation and Thunks:

	Eager vs Delayed evaluation:
		In Racket, ML, Java (etc ...):
		- function arguments are evaluated eagerly (call-by-value)
	 	- conditional branches are not eager

 	Lazy argument evaluation via "thunk":
 		Wrap expression with zero argument function (lambda)
 		thunk = zero-argument function

 		example:
 			e ; evaluated immediately
 			(lambda () e) ; "thunk" ; not evaluated yet
 			(e) ; thunk is evaluated here 

 	Detailed examples:
 		; OK
	 	(define (factorial-normal x)
		  (if (= x 0)
		      1
		      (* x (factorial-normal (- x 1)))))

	 	; Bad implementation without eager conditional branches
		(define (my-if-bad e1 e2 e3)
		  (if e1 e2 e3))

		; Calls will never terminate...
		(define (factorial-bad x)
		  (my-if-bad (= x 0)
		             1
		             (* x 
		                (factorial-bad (- x 1)))))

		; This implementation is OK because of eager conditionals
		(define (my-if-strange-but-works e1 e2 e3)
		  (if e1 (e2) (e3)))

		(define (factorial-okay x)
		  (my-if-strange-but-works (= x 0)
					   (lambda () 1)
					   (lambda () (* x (factorial-okay (- x 1))))))
)

( Avoiding Unnecessary Computations

	Thunks can be used to skip expensive computation that is not needed
	If so, it should we called once, at most (otherwise it would be worst)
	=> that's lazy evaluation

	Code:
		; this is a silly addition function that purposely runs slows for 
		; demonstration purposes
		(define (slow-add x y)
		  (letrec ([slow-id (lambda (y z)
		                      (if (= 0 z)
		                          y
		                          (slow-id y (- z 1))))])
		    (+ (slow-id x 50000000) y)))

		; multiplies x and result of y-thunk, calling y-thunk x times
		(define (my-mult x y-thunk) ;; assumes x is >= 0
		  (cond [(= x 0) 0] ; OK, optimization
		        [(= x 1) (y-thunk)] ; OK called once
		        [#t (+ (y-thunk) (my-mult (- x 1) y-thunk))])) ; not OK: called multiple times!

		; these calls: great for 0, okay for 1, bad for > 1        
		;(my-mult 0 (lambda () (slow-add 3 4)))
		;(my-mult 1 (lambda () (slow-add 3 4)))
		;(my-mult 2 (lambda () (slow-add 3 4)))

		; these calls: okay for all
		;(my-mult 0 (let ([x (slow-add 3 4)]) (lambda () x)))
		;(my-mult 1 (let ([x (slow-add 3 4)]) (lambda () x)))
		;(my-mult 2 (let ([x (slow-add 3 4)]) (lambda () x)))

		(define (my-delay th) 
		  (mcons #f th)) ;; a one-of "type" we will update /in place/

		(define (my-force p)
		  (if (mcar p)
		      (mcdr p)
		      (begin (set-mcar! p #t)
		             (set-mcdr! p ((mcdr p)))
		             (mcdr p))))

		; these calls: great for 0, okay for 1, okay for > 1
		;(my-mult 0 (let ([x (my-delay (lambda () (slow-add 3 4)))]) (lambda () (my-force x))))
		;(my-mult 1 (let ([x (my-delay (lambda () (slow-add 3 4)))]) (lambda () (my-force x))))
)

( Delay and Force

	Lazy evaluation:
	 - do not compute until needed
	 - remember answer (compute only once)

	"Delay and force" idiom aka Promise:
		; delay function uses a thunk and wraps it inside a mutable pair 
		(define (my-delay th)
			(mcons #f th)

		; use it (promise)
		(define (my-force p)
			(if (mcar p)
				(mcdr p)
				(begin 	(set-mcar! p #t)
						(set-mcdr! p ((mcdr p)))
						(mcdr p))))

	Code:
		; this is a silly addition function that purposely runs slows for 
		; demonstration purposes
		(define (slow-add x y)
		  (letrec ([slow-id (lambda (y z)
		                      (if (= 0 z)
		                          y
		                          (slow-id y (- z 1))))])
		    (+ (slow-id x 50000000) y)))

		; multiplies x and result of y-thunk, calling y-thunk x times
		(define (my-mult x y-thunk) ;; assumes x is >= 0
		  (cond [(= x 0) 0]
		        [(= x 1) (y-thunk)]
		        [#t (+ (y-thunk) (my-mult (- x 1) y-thunk))]))

		; these calls: great for 0, okay for 1, bad for > 1        
		;(my-mult 0 (lambda () (slow-add 3 4)))
		;(my-mult 1 (lambda () (slow-add 3 4)))
		;(my-mult 2 (lambda () (slow-add 3 4)))

		; these calls: okay for all
		;(my-mult 0 (let ([x (slow-add 3 4)]) (lambda () x)))
		;(my-mult 1 (let ([x (slow-add 3 4)]) (lambda () x)))
		;(my-mult 2 (let ([x (slow-add 3 4)]) (lambda () x)))

		(define (my-delay th) 
		  (mcons #f th)) ;; a one-of "type" we will update /in place/

		(define (my-force p)
		  (if (mcar p)
		      (mcdr p)
		      (begin (set-mcar! p #t)
		             (set-mcdr! p ((mcdr p)))
		             (mcdr p))))

		; these calls: great for 0, okay for 1, okay for > 1
		;(my-mult 0 (let ([x (my-delay (lambda () (slow-add 3 4)))]) (lambda () (my-force x))))
		;(my-mult 1 (let ([x (my-delay (lambda () (slow-add 3 4)))]) (lambda () (my-force x))))
		;(my-mult 2 (let ([x (my-delay (lambda () (slow-add 3 4)))]) (lambda () (my-force x))))	
)

( Using Streams

	Stream: infinite sequence of values

	Another idiom that uses thugs
	Producer knows how to create any number of values / consumer decides how many values he wants
	concept examples: mouse actions, UNIX pipes, etc...

	We can implement streams as a pair of '(next-answer . next-thunk)



	Code:
		;; define some streams

		;(define ones-really-bad (cons 1 ones-really-bad))
		(define ones-bad (lambda () (cons 1 (ones-bad))))

		(define ones (lambda () (cons 1 ones)))

		(define nats
		  (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))])
		    (lambda () (f 1))))

		(define powers-of-two
		  (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
		    (lambda () (f 2))))

		(define (stream-maker fn arg)
		  (letrec ([f (lambda (x) 
		                (cons x (lambda () (f (fn x arg)))))])
		    (lambda () (f arg))))
		(define nats2  (stream-maker + 1))
		(define powers2 (stream-maker * 2))

		;; code that uses streams

		(define (number-until stream tester)
		  (letrec ([f (lambda (stream ans)
		                (let ([pr (stream)])
		                  (if (tester (car pr))
		                      ans
		                      (f (cdr pr) (+ ans 1)))))])
		    (f stream 1)))

		(define four (number-until powers-of-two (lambda (x) (= x 16))))
)

( Defining streams

	Simply using recursion on thunk...

	Code:
		;; define some streams

		;(define ones-really-bad (cons 1 ones-really-bad)) ; does not work!
		(define ones-bad (lambda () (cons 1 (ones-bad))))

		(define ones (lambda () (cons 1 ones)))

		; stream of positive numbers (1 2 3 ...)
		(define nats
		  (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))])
		    (lambda () (f 1))))

		; 2 4 8 16 ...
		(define powers-of-two
		  (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
		    (lambda () (f 2))))

		; helper function that prevents copy-paste
		(define (stream-maker fn arg)
		  (letrec ([f (lambda (x) 
		                (cons x (lambda () (f (fn x arg)))))])
		    (lambda () (f arg))))
		(define nats2  (stream-maker + 1))
		(define powers2 (stream-maker * 2))

		;; code that uses streams

		(define (number-until stream tester)
		  (letrec ([f (lambda (stream ans)
		                (let ([pr (stream)])
		                  (if (tester (car pr))
		                      ans
		                      (f (cdr pr) (+ ans 1)))))])
		    (f stream 1)))

		(define four (number-until powers-of-two (lambda (x) (= x 16))))
)

( Memoization
	Avoid repeating computation without thunk.

	Memoization: keep result of pure function in cache

	Code:
		; math definition, but inefficient 	 
		(define (fibonacci1 x)
		  (if (or (= x 1) (= x 2))
		      1
		      (+ (fibonacci1 (- x 1))
		         (fibonacci1 (- x 2)))))

		; optimized implementation, but we will npt focus on it now
		(define (fibonacci2 x)
		  (letrec ([f (lambda (acc1 acc2 y)
		                (if (= y x)
		                    (+ acc1 acc2)
		                    (f (+ acc1 acc2) acc1 (+ y 1))))])
		    (if (or (= x 1) (= x 2))
		        1
		        (f 1 1 3))))

		; memoized version
		(define fibonacci3
		  (letrec([memo null] ; cache with a list of pairs (arg . result)
		          [f (lambda (x)
		               (let ([ans (assoc x memo)]) ; assoc checks if x is in the head of a list of pairs, is so returns that pair
		                 (if ans 
		                     (cdr ans)
		                     (let ([new-ans (if (or (= x 1) (= x 2))
		                                        1
		                                        (+ (f (- x 1))
		                                           (f (- x 2))))])
		                       (begin 
		                         (set! memo (cons (cons x new-ans) memo)) ; update our cache
		                         new-ans)))))])
		    f))
)

( Macros: The Key Points
	macro: a way to transform new syntax into a different syntax in the source language => adding syntactic sugar (ex: andalso in ML)

	macro system: a language for defining macros

	macro expansion: the process of rewriting, before the program is run

	Racket macros:
		Defining a macro m => creating a new special form

		examples:
		 - expand "my-if e1 then e2 else e3" to "(if e1 e2 e3)" (not so exciting!)
		 - expand "comment-out e1 e2" to "e2"
		 - expand "my-delay e" to "mcons #f (lambda () e)" (create promise)

	Code:
		; You do *not* need to understand these macro definitions 
		; (that is a later optional section), but we want to show
		; uses of them

		;; a cosmetic macro -- adds then, else
		(define-syntax my-if 
		  (syntax-rules (then else)
		    [(my-if e1 then e2 else e3)
		     (if e1 e2 e3)]))

		;; a macro to replace an expression with another one
		(define-syntax comment-out
		  (syntax-rules ()
		    [(comment-out ignore instead) instead]))

		; makes it so users don't write the thunk when using my-delay
		(define-syntax my-delay
		  (syntax-rules ()
		    [(my-delay e)
		     (mcons #f (lambda () e))]))

		; some uses

		(define seven (my-if #t then 7 else 14))
		; SYNTAX ERROR: (define does-not-work (my-if #t then 7 then 9))
		; SYNTAX ERROR: (define does-not-work (my-if #t then 7 else else))

		(define no-problem (comment-out (car null) #f))

		(define x (begin (print "hello") (* 3 4)))

		(define p (my-delay (begin (print "hi") (* 3 4))))

		(define (my-force th)
		  (if (mcar th)
		      (mcdr th)
		      (begin (set-mcar! th #t)
		             (set-mcdr! th ((mcdr th)))
		             (mcdr th))))

		; (my-force p)
		; (my-force p)

	Useful but sometimes overused (if you're not sure if you need a macro, don't write it!)
	Racket macros are superior to most languages
)


Section 6

( Intro

	1. How to define datatypes in a dynamic-lang like Racket? => 2 ways:
	 - with lists
	 - with structs (better way)

 	2. How to implement our own language (interpreters)?

 	3. static vs. dynamic typing

 	4. some other related optional material
)

( Datatype-Programming in Racket Without Structs

	Way #1:
	- mix values of different types + use primitives like number?, string?, pair?, etc.
	- use cons cells to build any type of data

	ML datatype => Racket list with a symbol as first element (symbols start with a quote, i.e. 'MyType - they are similar to strings, with fast comparison)
	We'll use helper functions: constructors (i.e. MyType), test-variant (i.e. MyType?), extract-data (i.e. MyType-value)...
	Racket code is a kind of "exp -> exp" interpreter


	ML code:
		datatype int_or_string = I of int | S of string

		fun funny_sum xs =
		    case xs of
			[] => 0
		      | (I i)::xs' => i + funny_sum xs'
		      | (S s)::xs' => String.size s + funny_sum xs'

		datatype exp = Const of int 
		             | Negate of exp 
		             | Add of exp * exp
		             | Multiply of exp * exp

		(* exp -> int *)
		fun eval_exp_old e = 
		    case e of
		        Const i => i
		      | Negate e2  => ~ (eval_exp_old e2)
		      | Add(e1,e2) => (eval_exp_old e1) + (eval_exp_old e2)
		      | Multiply(e1,e2) => (eval_exp_old e1) * (eval_exp_old e2)

		(* exp -> exp *)
		(* this way is more painful here, but makes much more sense for 
		   larger languages where recursive calls can return different kinds of 
		   things (e.g., numbers or pairs or functions or ... )
		*)
		exception Error of string

		fun eval_exp_new e =
		    let
			fun get_int e =
			    case e of
				Const i => i
			      | _ => raise (Error "expected Const result")
		    in
			case e of
		            Const _ => 
			    e
			  | Negate e2  => 
			    Const (~ (get_int (eval_exp_new e2)))
			  | Add(e1,e2) => 
			    Const ((get_int (eval_exp_new e1)) + (get_int (eval_exp_new e2)))
			  | Multiply(e1,e2) => 
			    Const ((get_int (eval_exp_new e1)) * (get_int (eval_exp_new e2)))
		    end

		val test_exp = Multiply (Negate (Add (Const 2,Const 2)), Const 7)
		val old_test = eval_exp_old test_exp (* ~28 *)
		val new_test = eval_exp_new test_exp (* Const ~28 *)

	Racket code:
		; we do not need a datatype to create a list holding a mix of numbers and string
		; Note: arguably bad style to not have else clause but makes example more like ML code
		(define (funny-sum xs)
		  (cond [(null? xs) 0]
		        [(number? (car xs)) (+ (car xs) (funny-sum (cdr xs)))]
		        [(string? (car xs)) (+ (string-length (car xs)) (funny-sum (cdr xs)))]))

		; suppose we wanted a "one-of type" using nothing but lists and symbols and such, like ML's 
		; datatype exp = Const of int | Negate of exp | Add of exp * exp | Multiply of exp * exp

		; just helper functions that make lists where first element is a symbol
		; Note: More robust could check at run-time the type of thing being put in
		(define (Const i) (list 'Const i))
		(define (Negate e) (list 'Negate e))
		(define (Add e1 e2) (list 'Add e1 e2))
		(define (Multiply e1 e2) (list 'Multiply e1 e2))

		; just helper functions that test what "kind of exp"
		; Note: More robust could raise better errors for non-exp values
		(define (Const? x) (eq? (car x) 'Const))
		(define (Negate? x) (eq? (car x) 'Negate))
		(define (Add? x) (eq? (car x) 'Add))
		(define (Multiply? x) (eq? (car x) 'Multiply))

		; just helper functions that get the pieces for "one kind of exp"
		; Note: More robust could check "what kind of exp"
		(define (Const-int e) (car (cdr e)))
		(define (Negate-e e) (car (cdr e)))
		(define (Add-e1 e) (car (cdr e)))
		(define (Add-e2 e) (car (cdr (cdr e))))
		(define (Multiply-e1 e) (car (cdr e)))
		(define (Multiply-e2 e) (car (cdr (cdr e))))

		; fyi: there are built-in functions for getting 2nd, 3rd list elements that would
		; have made the above simpler:
		;(define Const-int cadr)
		;(define Negate-e cadr)
		;(define Add-e1 cadr)
		;(define Add-e2 caddr)
		;(define Multiply-e1 cadr)
		;(define Multiply-e2 caddr)

		; same recursive structure as we have in ML, just without pattern-matching
		; And one change from what we did before: returning an exp, in particular
		; a Constant, rather than an int
		(define (eval-exp e)
		  (cond [(Const? e) e] ; note returning an exp, not a number
		        [(Negate? e) (Const (- (Const-int (eval-exp (Negate-e e)))))]
		        [(Add? e) (let ([v1 (Const-int (eval-exp (Add-e1 e)))]
		                        [v2 (Const-int (eval-exp (Add-e2 e)))])
		                    (Const (+ v1 v2)))]
		        [(Multiply? e) (let ([v1 (Const-int (eval-exp (Multiply-e1 e)))]
		                             [v2 (Const-int (eval-exp (Multiply-e2 e)))])
		                         (Const (* v1 v2)))]
		        [#t (error "eval-exp expected an exp")]))

		(define a-test (eval-exp (Multiply (Negate (Add (Const 2) (Const 2))) (Const 7))))		
)

( Datatype-Programming in Racket With Structs

	struct:
		Special form used for "datatypes" like expressions.
		
		(struct 
			foo ; struct name...
			(bar baz quuxx) ; ...with 3 fields having these names 
			#:transparent ; ... displayable in REPL (other value: "#:mutable" would add "bang" field setters)
		)

		(foo e1 e2 e3) ; "constructor": returns a foo with fields set to e1, e2 and e3 
		(foo? e) ; "tester": returns #t is e was made using constructor
		(foo-bar e) / (foo-baz e) / (foo-quux e) ; "accessor": returns field or raises an error (if e is not a foo)

	code:
		(struct const (int) #:transparent)
		(struct negate (e) #:transparent)
		(struct add (e1 e2) #:transparent)
		(struct multiply (e1 e2) #:transparent)

		(define (eval-exp e)
		  (cond [(const? e) e] ; note returning an exp, not a number
		        [(negate? e) (const (- (const-int (eval-exp (negate-e e)))))]
		        [(add? e) (let ([v1 (const-int (eval-exp (add-e1 e)))]
		                        [v2 (const-int (eval-exp (add-e2 e)))])
		                    (const (+ v1 v2)))]
		        [(multiply? e) (let ([v1 (const-int (eval-exp (multiply-e1 e)))]
		                             [v2 (const-int (eval-exp (multiply-e2 e)))])
		                         (const (* v1 v2)))]
		        [#t (error "eval-exp expected an exp")]))

		(define a-test (eval-exp (multiply (negate (add (const 2) (const 2))) (const 7))))
)

( Advantages of Structs 

	structs pros / lists:
		more concise (less code to write!)
		a new kind of things (not just a list)
		less error-prone

	structs can even be enhanced with:
	 - module system (for example: struct constructor can be hidden / accessors can be shown)
	 - contract system: can let us check invariants even if constructor is exposed

	structs are special / normal functions and even macros:
	 - only structs can introduce multiple bindings 
	 - structs return false to all other tester functions (pair?, number?, etc...)
)

( Implementing Programming Languages

	1. concrete syntax (ex: (fn x => x + x) 4
	2. parsing => warnings? errors?
	3. abstract tree (AST)
	4. type checking => warnings? errors?
	5. interpreter

AST example:
		call
		/  	\
	function Constant
	/    \		| 
	x 	  +		4
   		 / \
   		Var Var
   		|    |
   		4    4

	2 approaches to implement language B:
	 1. write an interpreter ("evaluator"?) in another language A 
	 2. writer a compiler ("translator"?) in another language A to a 3rd language C
	A is the "metalanguage"

	In reality: both can be mixed (i.e. Java bytecode compiler + bytecode interpreter)
	Racket also uses a mix

	Interpreter vs compiler vs mix is about language implementation, not language definition

	Metaprogramming:
		example:
			"arithmetic language" (interpreter: our previous example with arithmetic evaluation) via Racket (metalanguage)  
)

(  What Your Interpreter Can and Cannot Assume

	How goal:
	- define syntax of language B with Racket structs
	- write B programs in Racket via constructors
	- implement interpreter for B as recursive Racket functions

	Our interpreter can assume that input is "legal AST for B" (i.e. const are numbers)
					will check for illegal AST (i.e. "(negate -7)" instead of "(negate (const -7))" )
					

	Code:
		; a larger language with two kinds of values, booleans and numbers
		; an expression is any of these:
		(struct const (int) #:transparent) ; int should hold a number
		(struct negate (e1) #:transparent)  ; e1 should hold an expression
		(struct add (e1 e2) #:transparent) ; e1, e2 should hold expressions
		(struct multiply (e1 e2) #:transparent) ; e1, e2 should hold expressions
		(struct bool (b) #:transparent) ; b should hold #t or #f
		(struct eq-num (e1 e2) #:transparent) ; e1, e2 should hold expressions
		(struct if-then-else (e1 e2 e3) #:transparent) ; e1, e2, e3 should hold expressions
		; a value in this language is a legal const or bool

		(define test1 (multiply (negate (add (const 2) 
		                                     (const 2))) 
		                        (const 7)))

		(define test2 (multiply (negate (add (const 2)
		                                     (const 2))) 
		                        (if-then-else (bool #f) 
		                                      (const 7) 
		                                      (bool #t))))

		(define non-test (multiply (negate (add (const #t) 
		                                        (const 2))) 
		                           (const 7)))

		(define (eval-exp-wrong e)
		  (cond [(const? e) 
		         e] 
		        [(negate? e) 
		         (const (- (const-int (eval-exp-wrong (negate-e1 e)))))]
		        [(add? e) 
		         (let ([i1 (const-int (eval-exp-wrong (add-e1 e)))]
		               [i2 (const-int (eval-exp-wrong (add-e2 e)))])
		           (const (+ i1 i2)))]
		        [(multiply? e) 
		         (let ([i1 (const-int (eval-exp-wrong (multiply-e1 e)))]
		               [i2 (const-int (eval-exp-wrong (multiply-e2 e)))])
		           (const (* i1 i2)))]
		        [(bool? e) 
		         e]
		        [(eq-num? e) 
		         (let ([i1 (const-int (eval-exp-wrong (eq-num-e1 e)))]
		               [i2 (const-int (eval-exp-wrong (eq-num-e2 e)))])
		           (bool (= i1 i2)))] ; creates (bool #t) or (bool #f)
		        [(if-then-else? e)
		         (if (bool-b (eval-exp-wrong (if-then-else-e1 e)))
		             (eval-exp-wrong (if-then-else-e2 e))
		             (eval-exp-wrong (if-then-else-e3 e)))]
		        [#t (error "eval-exp expected an exp")] ; not strictly necessary but helps debugging
		        ))

		(define (eval-exp e)
		  (cond [(const? e) 
		         e] 
		        [(negate? e) 
		         (let ([v (eval-exp (negate-e1 e))])
		           (if (const? v)
		               (const (- (const-int v)))
		               (error "negate applied to non-number")))]
		        [(add? e) 
		         (let ([v1 (eval-exp (add-e1 e))]
		               [v2 (eval-exp (add-e2 e))])
		           (if (and (const? v1) (const? v2))
		               (const (+ (const-int v1) (const-int v2)))
		               (error "add applied to non-number")))]
		        [(multiply? e) 
		         (let ([v1 (eval-exp (multiply-e1 e))]
		               [v2 (eval-exp (multiply-e2 e))])
		           (if (and (const? v1) (const? v2))
		               (const (* (const-int v1) (const-int v2)))
		               ((error "multiply applied to non-number"))))]
		        [(bool? e) 
		         e]
		        [(eq-num? e) 
		         (let ([v1 (eval-exp (eq-num-e1 e))]
		               [v2 (eval-exp (eq-num-e2 e))])
		           (if (and (const? v1) (const? v2))
		               (bool (= (const-int v1) (const-int v2))) ; creates (bool #t) or (bool #f)
		               (error "eq-num applied to non-number")))]
		        [(if-then-else? e) 
		         (let ([v-test (eval-exp (if-then-else-e1 e))])
		           (if (bool? v-test)
		               (if (bool-b v-test)
		                   (eval-exp (if-then-else-e2 e))
		                   (eval-exp (if-then-else-e3 e)))
		               (error "if-then-else applied to non-boolean")))]
		        [#t (error "eval-exp expected an exp")] ; not strictly necessary but helps debugging
		        ))

)

( Implementing Variables and Environments

	vars

	env: list of pairs (string . value)
	variable evaluation: look up in an env

	; should be a private helper function (but in homework, use a public one for grading prurpose )
	(define (eval-under-env e env)
		(cond ... ; case for each kind of expression
			  ...)
		)
	)

	(eval-exp ; calls eval-under-env with an empty env, initially
)

( Implementing closures

 	; closure = function + environment
	(struct closure (env fun) # transparent)

	Closure call:
	(call e1 e2) ; e1: closure, e2: argument
	 1. use current env to eval e1
	 2. use current env to evaluate e2
	 3. evaluate closure's body in closure's env extended to:
	  - map arg name to arg value
	  - map functions's name to the whole closure (for recursion)

)

( Racket Functions As “Macros” For Interpreted Language

	We can use implement
		- "andalso" with "if-then-else"
		- "double" with "multiply"
)

( ML Versus Racket

	Biggest difference: ML type system / Racket lack of it
	(note: typed Racket exists)

	ML described by a Racket programmer
		ML prevents some bugs (i.e. "(define (f x) (+ x (car x)))" :-)
		primitives like "number?" are not required in ML
		ML prevents this style of code :-(
			(define (f x) (if (> 0 x) # true (list 1 2)))
			(list t 1 "foo")

	Racket descirbed by a ML programmer
		"one big datatype" 
		there is nothing equivalent to structs
)

( what's static checking?

	static checking : anything to reject a program after it parses but before it runs
	can be 
	- part of the type system
	- or done via a "helpful tool" 

	SC prevents:
		- misuse of primitives like number?, etc...
		- checks during runtime

	In ML, SC ensures:
	- operation is not done on the wrong type (i.e. arithmetics on not-a-number)
	- variable not defined in environment
	- pattern match on redundant pattern
	- code outside a module that calls a function not in signature
	... but it does not prevent:
	- exceptions like head-of-empty-list, array-bounds errors, divide-by-zero, etc...
    - calling f instead of g (let's suppose they apply on same types) => "can't read mind"

    A question of eagerness
    	catch a bug before it happens vs. report a bug before it happens
)



( Optional: Are Closures Efficient?
)

( Soundness and Completeness
)

( Weak Typing
)

( Static Versus Dynamic Typing, Part One
)

( Static Versus Dynamic Typing, Part Two
)

( Optional: eval and quote
)