#lang racket
;; CSE 341 section (swapped with lecture), Monday, 7 November 2011


;; Coming back to mutation, be careful nesting lets and lambdas!
;; Have you been running into problems on the homework?
;; Have you been running into problems on the homework
;; *without realizing it*?
;;
;; Goal: write a function that multiplies its argument by the number of
;; times it has been called (including the current call).
;; (times-num-calls 4) should return 4 the first time it is called,
;; 8 the second, etc.
;;
;; Idea: set aside a binding to set! and read on every call.

;; First try.
;; This works, but...
(define num-calls 0)
(define (times-num-calls-bad-1  x)
  (begin 
    (set! num-calls (+ num-calls 1))
    (* x num-calls)))
; (times-num-calls-bad-1 4)

;; Second try.
;; We want to package up the call count in a binding that is only
;; visible in our function.
;; What's wrong?
(define (times-num-calls-bad-2  x)
  (let ([calls 0])
    (begin 
      (set! calls (+ calls 1))
      (* x calls))))
; (times-num-calls-bad-2 4)

;; Third try.
;; What's wrong?
(define times-num-calls-bad-3
  (lambda (x)
    (let ([calls 0])
      (begin 
        (set! calls (+ calls 1))
        (* x calls)))))
; (times-num-calls-bad-3 4)

;; Fourth try.
(define times-num-calls
  (let ([calls 0]) ;; defined once *ever*, used by all calls
    (lambda (x)
      (begin 
        (set! calls (+ calls 1))
        (* x calls)))))
; (times-num-calls 4)

#|
fun times_num_calls_bad x =
  let val calls = ref 0
  in
     ...
  end

val times_num_calls =
  let val calls = ref 0
  in
     (fn x => ...)
  end
|#



;; Goal: write a list reversal function using a tail recursive helper
;; function that returns a pair of the reversed list and the total 
;; number of calls to the helper thus far in the program.

;; First try.
;; What's wrong?
(define (rev-counted-bad-1 lst)
  (letrec ([f (lambda (lst acc)
                (let ([calls 0])
                  (begin (set! calls (+ calls 1))
                         (if (null? lst) 
                             (cons acc calls)
                             (f (cdr lst) (cons (car lst) acc))))))])
    (f lst null)))
; (rev-counted-bad-1  (cons 1 (cons 2 (cons 3 null))))
; (rev-counted-bad-1  (list 1 2 3 4 5 6))

;; Second try.
;; What's wrong?
(define (rev-counted-bad-2 lst)
  (letrec ([calls 0]
           [f (lambda (lst acc)
                (begin (set! calls (+ calls 1))
                       (if (null? lst) 
                           (cons acc calls)
                           (f (cdr lst) (cons (car lst) acc)))))])
    (f lst null)))
; (rev-counted-bad-2  (cons 1 (cons 2 (cons 3 null))))
; (rev-counted-bad-2  (list 1 2 3 4 5 6))

;; Third try.
(define rev-counted 
  (let ([calls 0]) ;; defined *once* ever, used by all f calls
    (lambda (lst)
      (letrec ([f (lambda (lst acc)
                    (begin (set! calls (+ calls 1))
                           (if (null? lst) 
                               (cons acc calls)
                               (f (cdr lst) (cons (car lst) acc)))))])
        (f lst null)))))
; (rev-counted  (cons 1 (cons 2 (cons 3 null))))
; (rev-counted  (list 1 2 3 4 5 6))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; A brief interlude to introduce caar, cadr, cddr, cdar, and friends ;;
;; Suppose we have a cons-cell-based binary tree where leaves store 
;; integers.  How do we access the 4 here?
(define y (cons
           (cons 
            (cons 1 2) 
            (cons 3 4)) 
           (cons 
            (cons 5 6) 
            (cons 7 8))))
;; (cdr (cdr (car y)))
;;
;; This can get noisy, so we have some nice sugar.
;; (caar y) means (car (car y))
;; (cadr y) means (car (cdr y))
;; (cddar x) means (cdr (cdr (car x)))
;;
;; In general:
;; Reading left to right, expand each a to (car ...) and each d to
;; (cdr ...), nesting as you go.
;;
;; Or, reading right to left, do the same, but wrap the expression
;; built up so far.
;;
;; What is (cdadr y)?


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Simple Math Expression Language using Pairs (SMELP)
;;
;; In ML, we would use a datatype ("one-of" type) for this:
;; datatype e = Const of int | Neg of e | Plus of e * e | Times of e * e
;; Then, we can use constructors and pattern-match on expressions.
;;
;; In Racket, cons cells (pairs) are all we need!
;; We'll represent each Expression in SMELP as a pair of the type of
;; the expression and its contents, but we need three extra pieces
;; for each kind of expression:
;;
;; 1. a function to create that expression from its parts
;;    (like an ML constructor)
;; 2. a function to test whether something is that kind of expression
;;    (like one aspect of pattern matching)
;; 3. functions to access the parts of the expression
;;    (like tuple or record accessors or, if you squint, bindings from
;;    pattern matching)

;; "Constructors"
(define (make-const i) (cons 'const i))
(define (make-plus left right) (cons 'plus (cons left right)))
(define (make-times left right) (cons 'times (cons left right)))
(define (make-neg e) (cons 'neg e))

;; "Matchers"
(define (is-const? e) (eq? 'const (car e)))
(define (is-plus?  e) (eq? 'plus  (car e)))
(define (is-times? e) (eq? 'times (car e)))
(define (is-neg?   e) (eq? 'neg   (car e)))

;; "Accessors"
(define get-i     cdr)  ;; get the Racket integer for a SMELP const
(define get-left  cadr) ;; use for plus and times
(define get-right cddr) ;; use for plus and times
(define get-exp   cdr)  ;; get the negated expression in a neg


;; An evaluator for SMELP expressions.
;; eval-smel reduces a SMELP expression to a SMELP constant.
(define (eval-smelp e)
  (cond ((is-const? e) e)
        ((is-plus?  e) (make-const (+ (get-i (eval-smelp (get-left e)))
                                      (get-i (eval-smelp (get-right e))))))
        ((is-times? e) (make-const (* (get-i (eval-smelp (get-left e)))
                                      (get-i (eval-smelp (get-right e))))))
        ((is-neg?   e) (make-const (- (get-i (eval-smelp (get-exp e))))))
        (else (error "That's not a SMELP expression!"))))
  
;; Evaluate it:
#|
(eval-smelp (make-plus (make-times (make-neg (make-const 2)) 
                                   (make-const 7))
                       (make-const 4)))
|#

;; STRUCTS ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; While pairs are nice and minimal, structs are a lot more convenient.
;; If you'd use a datatype or a record in ML, use a struct in Racket.

;; Define a new kind of struct:
(struct struct-name (field-1 field-2 etc) #:transparent)

;; This gives you a bunch of new functions (in fact, all the ones we 
;; built on our own for SMELP, but with slightly better names):
;; 1. The name of this kind of struct is a constructor function for it:
(define x (struct-name 8 "hello" (list 2 3 4)))

;; 2. Function to check if something is this kind of struct
;;    Returns #t for anything created by (struct-name ...) and #f 
;;    for anything else.
;; (struct-name? x)
;; (struct-name? (list 2 4 6))

;; 3. Functions to access fields:
;; (struct-name-field-1 x)
;; (struct-name-field-2 x)
;; (struct-name-etc x)

;; Adding the transparent attribute lets the printer in the REPL
;; print the actual contents of the struct rather than hiding them.
;; You will find this *very* convenient for the homework.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Simple Math Expression Language using Structs (SMELS)

(struct const (i) #:transparent)
(struct plus  (left right) #:transparent)
(struct times (left right) #:transparent)
(struct neg   (exp) #:transparent)

;; Structs automatically create all the pieces we created before with 
;; pairs, but from nice simple definitions. There is one nice difference:
;; With SMELP expressions, we could not tell cons cells that happened to 
;; have 'plus in the car from actual SMELP plus expressions, so is-plus?
;; might lie occasionally.   With structs, the only way to get a
;; particular kind of struct (like a plus) is to use its constructor,
;; meaning that plus? never lies: it returns #t for anything created by
;; the plus constructor and false for anything else.
  
;; We still have nothing like an ML datatype that tells us "these four
;; things all belong to the same type and nothing else does."  We just
;; have to be careful to use them that way.

;; An evaluator for SMELS expressions.
;; eval-smels reduces any SMELS expression to a SMELS constant.
(define (eval-smels e)
  (cond ((const? e) e)
        ((plus?  e) (const (+ (const-i (eval-smels (plus-left e)))
                              (const-i (eval-smels (plus-right e))))))
        ((times? e) (const (* (const-i (eval-smels (times-left e)))
                              (const-i (eval-smels (times-right e))))))
        ((neg?   e) (const (- (const-i (eval-smels (neg-exp e))))))
        (else (error "That's not a SMELS expression!"))))
  
;; Evaluate it:
;; (eval-smels (plus (times (neg (const 2)) (const 7)) (const 4)))





;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; bonus features if time:
;; functions that take a variable number of arguments:
;;Bad add
(define (my-add-1 . args)
 (if (null? args)
     0
     (+ (car args) (my-add-1 (cdr args)))))

;;Better add
(define (my-add-2 . args)
 (if (null? args)
     0
     (+ (car args) (apply my-add-2 (cdr args)))))

#| 
this is a 
multiline comment
|#
;;Best add
(define (my-add . args)
 (foldr + 0 args))

;; (my-add 0)
;; (my-add 42)
;; (my-add 1 2 3 4 5)