;; SUMMARY OF FUNCTION AND OTHER TYPES, SO YOU KNOW WHAT YOU ARE WRITING
;;
;; 
;; AtomicPattern ::= Integer | _ | <> | <&> 
;;              in part c) also  SchemeFunction
;;              in part d) also SymbolStartingWith$
;;
;; Value ::= Integer | List of Value  ;;{this does allow for nested lists
;;
;; matchAtomicn( AtomicPattern , Value ) -> {#t, #f) except  in (d),
;;              where the value returned may be more complex
;;
;; matchListn(List of AtomicPattern, List of Value) ->{#t,#f}
;;   (except in (e), where the first arg is a 
;;                        Pattern ::= AtomicPattern | List of Pattern
;;     which allows for nesting.)


;;**** TESTING RULES****

;;  You need to know the result of the test before you run it

;;  Your eyes see what you want to see -- use the computer to check
;; the test result

;; After a change you need to rerun all previous tests (called
;; "regression testing") so embed tests in functions

;;  Give intermediate results of tests to see how far you got

;;############################################################
(define (run-tests)
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;; COMBINING ALL TEST RUNS
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  (display "testing for parts (a,b)") (display #\newline)
  (test**a** matchAtomic)
  (test**b** matchList)

  (display "testing for part (c)") (display #\newline)
  (test**c1** matchAtomic2)
;;  (test**a** matchAtomic2)
  (test**c2** matchList2)

  (display "testing for part (d)") (display #\newline)
;;  (test**d1** matchAtomic3)
  (test**d2** matchList3)
;;  (test**b** matchList3)  ;; -- matchList3 is also matchList

  (display "testing for part (e)") (display #\newline)
  (test**e** matchList4)
;;    (test**b** matchList4)  ;; -- matchList4 is also matchList
)
;;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^;;


;; THERE ARE SEVERAL TEST "SUITES" BELOW.
;; EVERY TEST IN THE "SUITE" HAS THE FORM
;;        (if  (eq?
;;   <function call>
;;   <**expected** correct result of the function call just above this line>
;;	     ) (ok n) (fail n)
;;where the functions ok and fail are used to identify the test within 
;;the suite, so you can tell which failed.
;;
   (define (ok n) (display 'ok) (display n) (display #\newline))
   (define (fail n) (display 'fail) (display n) (display #\newline))

;; To run all the test suites, use
;; (run-tests)
;; defined above.

;;############################################################
;;
;; PART (a) EBNF grammar: 
;; AtomicPattern ::= Integer | "_" | "<>" | "<&>"
;; Value ::= Integer | "(" {Value} ")"

;; The following function will be used to test matchAtomic, but also
;; matchAtomic2, matchAtomic3,... which are all extensions of the
;; basic case. By passing in the function as an argument, it also
;; allows the test results to change as the implementation
;; changes. (Avoids the need to "recompile" the test function.)

 (define (test**a** matchAtomic) 
   (begin
   ;; To run the test,  type (test**a** matchAtomic) for example
    (display "Test *a* -- for ATOMIC match in part (a).")
    (display #\newline)
         (if (eq?     
    (matchAtomic 2 2)   
    #t
          )  (ok 1)  (fail 1))
         (if (eq?     
    (matchAtomic 2 3)   
    #f
         )  (ok 2)  (fail 2))
         (if (eq?     
    (matchAtomic 2 '())  
    #f
         )  (ok 3)  (fail 3))
         (if (eq?     
    (matchAtomic 2 '((2) (3 4)))   
    #f
         )  (ok 4)  (fail 4))
         (if (eq?     
    (matchAtomic '_ 2)  
    #t
         )  (ok 5)  (fail 5))
         (if (eq?     
    (matchAtomic '_ '())  
    #t
         )  (ok 6)  (fail 6))
         (if (eq?     
    (matchAtomic '_ '((2) (3 4)))   
    #t
         )  (ok 7)  (fail 7))
         (if (eq?     
    (matchAtomic '<> 2)  
    #f
         )  (ok 8)  (fail 8))
         (if (eq?     
    (matchAtomic '<> '())  
    #t
         )  (ok 9)  (fail 9))
         (if (eq?     
    (matchAtomic '<> '((2) (3 4)))   
    #f
         )  (ok 'a)  (fail 'a))
         (if (eq?     
    (matchAtomic '<&> 2)  
    #f
         )  (ok 'b)  (fail 'b))
         (if (eq?     
    (matchAtomic '<&> '())  
    #f
         )  (ok 'c)  (fail 'c))
         (if (eq?     
    (matchAtomic '<&> '((2) (3 4)))   
    #t
         )  (ok 'd)  (fail 'd))
    (display #\newline)
    ))

;;############################################################
;; PART (c)
;;
;; AtomicPattern2 ::= AtomicPattern | Function
;; where Function maps Value to boolean


(define (nonnegative? n) (and (integer? n) (> n 0)))


 (define (test**c1** matchAtomic2)
   ;; #to run the test,  type (test**c1** matchAtomic2)
    (display "Test *c1* for ATOMIC match in part (c).")
    (display #\newline)
         (if (eq? 
    (matchAtomic2 nonnegative? 2)  
    #t  ;; because 2 is a nonnegative number
         ) (ok 1)  (fail 1)  )
         (if (eq? 
    (matchAtomic2 nonnegative? -6)  
    #f ;;  --because -6 is not nonnegative
         ) (ok 2)  (fail 2)  )
         (if (eq? 
    (matchAtomic2 nonnegative? '())  
    #f ;; -- because not a number
         ) (ok 3)  (fail 3)  )
         (if (eq? 
    (matchAtomic2 nonnegative? '((2) (3 4)))   
    #f 
         ) (ok 4)  (fail 4)  )
         (if (eq? 
    (matchAtomic2 null? 2)  
    #f ;; -- because not a list
         ) (ok 5)  (fail 5)  )
         (if (eq? 
    (matchAtomic2 null? '())  
    #t
         ) (ok 6)  (fail 6)  )
         (if (eq? 
    (matchAtomic2 null? '((2) (3 4)))   
    #f ;; -- because not the null list
         ) (ok 7)  (fail 7)  )

    ;; even? and odd? are built-in predicates on integers
         (if (eq? 
    (matchAtomic2 (lambda (x) (and (integer? x)(even? x))) 2)
    #t
         ) (ok 8)  (fail 8)  )
         (if (eq? 
    (matchAtomic2 (lambda (x) (and (integer? x)(even? x))) -6) 
    #t
         ) (ok 9)  (fail 9)  )
         (if (eq? 
    (matchAtomic2 (lambda (x) (and (integer? x)(even? x))) '())
    #f
         ) (ok 'a)  (fail 'a)  )
         (if (eq? 
    (matchAtomic2 (lambda (x) (and (integer? x)(even? x)))
				'((2) (3 4)))   
    #f
         ) (ok 'b)  (fail 'b)  )
     )

;;
;; matchAtomic2 should also pass the tests of matchAtomic
;; so try (test**a** matchAtomic2)

;;############################################################
;;  PART (d)
;;
;; AtomicPattern3 ::= AtomicPattern | SymbolIdStartingWith$
;; SymbolIdStartingWith$ ::= "$" {Character} $... matches everything,
;; like '_ matchAtomic returns #f -- if failing, ((Symbol,Value)) if
;; matching a variable, #t or () otherwise (your choice)

;;   NOTE: THE PROJECT DID NOT EXPLICITLY STATE *HOW* YOU HAD TO MODIFY
;; matchAtomic3. THE FOLLOWING TESTS ARE THEREFORE *NOT REQUIRED* FOR
;; GRADING PURPOSES. 
;;   THINK OF THEM AS (i) DESCRIPTIONS/CLARIFICATIONS OF WHAT IT
;; MEANS TO MATCH AN ATOMIC PATTERN IN THIS CASE; (ii) HINTS OF
;; SOME WAYS OF SOLVING THE BIGGER PROBLEM. BUT THERE ARE OTHER WAYS TOO.

(define (test**d1** matchAtomic3)
   (display "Test *d1* for matchAtomic3 with vars:")
   (display #\newline)
          (if (equal?    
   (matchAtomic3 '$a 2) 
   '( ($a 2) )                         ;; or just '($a 2)
               ) (ok 1) (fail 1))
          (if (equal?     
   (matchAtomic3 '$a '()) 
   '( ($a ()) )                        ;; or just '($a ())
               ) (ok 2) (fail 2))
          (if (equal? 
   (matchAtomic3 '$a '((2) (3 4)))  
   '( ($a  ((2) (3 4))) )              ;; or just '($a ((2)(3 4)) )
	        )  (ok 3) (fail 3))
     )

;; But what are we to do when the pattern is not a variable?  For
;; failed matches, return #f; for successful ones, it is your choice:
;; #t or '() or something else, whatever makes easier the writing of
;; matchList3. If you return #t, the test would be (test**a** matchAtomic3)
;; Otherwise, replace   #t in test**a** by whatever you return.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Testing full pattern matching: lists of atomic patterns against lists
;; of values
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;In all cases, Pattern ::= "(" {AtomicPattern} ")"

;;############################################################
;;
;;  PART (b)
;;
(define (test**b** matchList)
     (display "Test *b* for LIST match -- part (b) " )
     (display #\newline)
          (if (equal?
     (matchList '()  '())  
     #t
               ) (ok 1)  (fail 1)  )
	  (if (equal?
     (matchList '(1 2 3) '(1 2 3)) 
     #t 
               ) (ok 2)  (fail 2)  )
	  (if (equal?
     (matchList '(_  <&>     2  <> 3)  
		'(7 ((3 4))  2  () 3)  ) 
     #t ;; -- all elements match L-to-R
               ) (ok 3)  (fail 3)  )

	  (if (equal?
     (matchList '(1 2 3) '(1 99 3))  
     #f  ;; -- 2 and 99 don't match
               ) (ok 4)  (fail 4)  )
	  (if (equal?
     (matchList '(_  <&>   2  <> 3)  
		'(7  7     2  (8) 3) ) 
     #f ;; <&>/7 and <>/(8) don't
               ) (ok 5)  (fail 5))
  )
;; it would be nice if your program reported #f rather than "error" on
;; (matchList '() '(1) ), because the value list does not have the
;; same number of elements as the pattern list. Similarly for
;; (matchList '(_ 2 3) '(1)) If you need it, length is a built-in scm
;; function.


;;############################################################
;;
(define (test**c2** matchList2)
  (display "Test *c2* for  matchList2 in (c)")
  (display #\newline)
       (if (eq?
   (matchList2 () () )
   #t 
             ) (ok 0)  (fail 0)  )
       (if (eq?
   (matchList2 (list nonnegative?) (list 3)) 
   #t 
             ) (ok 1)  (fail 1)  )
       (if (eq?
   (matchList2 (list null?) (list 3)) 
   #f 
             ) (ok 2)  (fail 2)  )
       (if (eq?
   (matchList2 (list null? null? list?    nonnegative?)
	       (list ()   ()     '(2 (3))  4  )  ) 
   #t ;; -- each of the 4 function calls returns true
             ) (ok 3)  (fail 3)  )
       (if (eq?
   (matchList2 (list pair? 6 integer? '<>)
	          '( (2 3) 6   3      ())  )
   #t ;; -- old atomic patterns mixed with new ones still work
             ) (ok 4)  (fail 4)  )
       (if (eq?
   (matchList2 (list null? null?   list?    nonnegative?)
	       (list ()    99     '(2 (3))  4  )  ) 
   #f ;;  -- 99 is not the null list, so the full pattern does not match
             ) (ok 5)  (fail 5) )
)	     

;;############################################################
;; 

(define (test**d2** matchList3)
   (display "Test *d3* for matchList3 in (d):")
   (display  #\newline)
          (if (equal?    
   (matchList3 '($a $b) '(2 ()) )  ;; L-to-R, $a matches 2, $b matches '()
   '( ($a 2) ($b ()) )   
               ) (ok 1) 
		 (if (equal?    
   (matchList3 '($a $b) '(2 ()) )  ;; order of matched pairs does not matter
   '(  ($b ()) ($a 2) )   
                        ) (ok 1) (fail 1)) )

          (if (equal?    
  (matchList3 '($a 7  $b 8) '(2 7 () 8) )  ;; matches without variables do not
   '( ($a 2) ($b ()) )                      ;; affect bindings   
               ) (ok 2)
		 (if (equal?    
   (matchList3 '($a 7  $b 8) '(2 7 () 8) )  ;; order of matched pairs not relevant
   '(  ($b ()) ($a 2) )                      
               ) (ok 2)(fail 2)) )

	   (if (eq?
   (matchList3 '(7  8)  '(7 8) )  
   ()  ;; when there are no vars, we want ()
               ) (ok 3) (fail 3))

	   (if (eq?
   (matchList3 '($a 7 $b 8)  '(2 5  () 6) )  
   #f  ;; miss-matches (in this case 7/5 cause) (fail ure)
               ) (ok 4) (fail 4))

;; ideally we would repeat all tests in **b**, but also using $v as an
;; atomic pattern
          (if (equal? 
   (matchList3 '() '())
   '()
	        )  (ok 5) (fail 5))

	  (if (equal?
     (matchList3 '(_  <&>     2  <> 3)  
		 '(7 ((3 4))  2  () 3)  ) 
     '();; -- all elements match L-to-R
               ) (ok 6)  (fail 6) )

	  (if (equal?
     (matchList3 '(1 2 3) '(1 99 3))  
     #f  ;; -- 2 and 99 don't match
               ) (ok 7)  (fail 7)  )
	  (if (equal?
     (matchList3 '(_  <&>   2  <> 3)  
		'(7  7     2  (8) 3) ) 
     #f           ;; <&>/7 and <>/(8) don't match
               ) (ok 8)  (fail 8))
 )



;;############################################################
;;
;; PART (e)

;; AtomicPattern4 ::= AtomicPattern |
;;                   List of AtomicPattern4 

;; We don't care how you program matchAtomic4.
;; matchList4 should pass all the tests for  matchList, test**b**
;; plus

 (define (test**e** matchList4)
    (display  "Test *e* for  matchList4 -- nested patterns")
    (display #\newline)
    ;;nested patterns with only integers
          (if (equal?
    (matchList4 '((5) 6)  '((5) 6) )  
    #t
              ) (ok 1)  (fail 1)  )
	  (if (equal?
    (matchList4 '((5) 6)  '(5  6) )  
    #f 
              ) (ok 2)  (fail 2)  )
	  (if (equal?
    (matchList4 '( ((5) 6) )  '(8)   )
    #f
              ) (ok 3)  (fail 3)  )
	  (if (equal?
    (matchList4 '((5) 6)  '( () ) )  
    #f
              ) (ok 4)  (fail 4)  )

    ;;nested lists with other patterns
	  (if (equal?
    (matchList4 '(<&> (_ <> _))  '((5) (6 () (7 8))) )  
    #t
              ) (ok 5)  (fail 5)  )
	  (if (equal?
    (matchList4 '(<&> (_ <> _))  '(() (6 () (7 8)))  )  
    #f ;; first elt is null
              ) (ok 6)  (fail 6)  )
	  (if (equal?
   (matchList4 '(<&> (_ <> _))  '((5) (() (7 8))) )  
   #f ;; -- second element is too short
             ) (ok 7)  (fail 7)  )
)