;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname 11-20) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) ;; THE CALL GRAPH (define-struct node (name calls)) ;; A Graph is a [List-of Node] ;; A Node is (make-node Symbol [List-of Symbol]) (define a-graph (list (make-node 'amy '(billy claire)) (make-node 'billy '(dan)) (make-node 'claire '()) (make-node 'dan '(eli)) (make-node 'eli '(claire)))) ;; Graph Name Name -> Boolean ;; is there a path from f to t in G? (check-expect (path? a-graph 'claire 'amy) false) (check-expect (path? a-graph 'billy 'eli) true) ;; TERMINATES: It does not terminate for certain inputs, e.g., (check-expect (path? b-graph 'amy 'claire) false) (define b-graph (list (make-node 'amy '(billy)) (make-node 'billy '(amy)) (make-node 'claire '()))) (define (path? G f0 t) (local (;; Name [List-of Name] -> Boolean ;; accumumulator: the path we took from f0 to f in G ;; generative recursion. without proof, it terminates (define (grace f m) (cond [(member f m) false] [(member t (look-for-f-s-calls G f)) true] [else (ormap (lambda (n) (grace n (cons f m))) (look-for-f-s-calls G f))]))) ;; --- now call first time --- (grace f0 '()))) ;; Graph Name -> [List-of Name] ;; do as name says (check-expect (look-for-f-s-calls a-graph 'amy) '(billy claire)) (check-expect (look-for-f-s-calls a-graph 'eli) '(claire)) (check-error (look-for-f-s-calls '() 'eli) "can't happen") (define (look-for-f-s-calls G f) (cond [(empty? G) (error "can't happen")] [else (if (symbol=? (node-name (first G)) f) (node-calls (first G)) (look-for-f-s-calls (rest G) f))]))