;;; $Id: lambda-1-exp-examples.scm,v 1.3 2006/01/05 22:24:09 leavens Exp $
;;; Examples in the language lambda-1-exp (see lambda-1-exp.scm)

(module lambda-1-exp-examples (lib "typedscm.ss" "typedscm")

(provide count-var-exps all-var-exps free-vars free? bound-vars bound?)

(require (lib "lambda-1-exp.scm" "lib342"))

(deftype count-var-exps (-> (expression) number))
(define count-var-exps  
  (lambda (exp)
    ;; ENSURES: result is the number of <var-exp>s in exp
    (if (var-exp? exp)
        1
        (if (lambda-exp? exp)
            (count-var-exps (lambda-exp->body exp))
            (+ (count-var-exps (app-exp->rator exp))
               (count-var-exps (app-exp->rand exp)))))))

(deftype all-var-exps (-> (expression) (list-of symbol)))
(define all-var-exps
    (lambda (exp)
      ;; ENSURES: result is a list of all the <var-exp>s in exp
      ;;          (this list may contain duplicate occurrences of symbols).
      (if (var-exp? exp)
        (list (var-exp->id exp))
        (if (lambda-exp? exp)
            (all-var-exps (lambda-exp->body exp))
            (append (all-var-exps (app-exp->rator exp))
                     (all-var-exps (app-exp->rand exp)))))))

;;; Note: in class we did all-var-exps so it returned a set,
;;; so we used set-union instead of append.
;;; A similar remark app-explies to the following, which use lists instead of sets.

(deftype free-vars (-> (expression) (list-of symbol)))
(define free-vars
  (lambda (exp)
    (if (var-exp? exp)
        (list (var-exp->id exp))
      (if (lambda-exp? exp)
          (remove-all (lambda-exp->id exp)
                      (free-vars (lambda-exp->body exp)))
          (append (free-vars (app-exp->rator exp))
                  (free-vars (app-exp->rand exp)))))))

(deftype remove-all (forall (T) (-> (T (list-of T)) (list-of T))))
(define remove-all
  (lambda (e ls)
    (if (null? ls)
        '()
        (if (equal? e (car ls))
            (remove-all e (cdr ls))
            (cons (car ls) (remove-all e (cdr ls)))))))

(deftype free? (-> (symbol expression) boolean))
(define free?
  (lambda (sym exp)
    (or (and (var-exp? exp)
             (eq? sym (var-exp->id exp)))
        (and (lambda-exp? exp)
             (and (not (eq? sym (lambda-exp->id exp)))
                  (free? sym (lambda-exp->body exp))))
        (and (app-exp? exp) ;; this test isn't needed, but symmetric
             (or (free? sym (app-exp->rator exp))
                 (free? sym (app-exp->rand exp)))))))

(deftype bound-vars (-> (expression) (list-of symbol)))
(define bound-vars
  (lambda (exp)
    (if (var-exp? exp)
        '()
      (if (lambda-exp? exp)
        (append
         (if (free? (lambda-exp->id exp) (lambda-exp->body exp))
             (list (lambda-exp->id exp))
             '())
         (bound-vars (lambda-exp->body exp)))
        (append (bound-vars (app-exp->rator exp))
                (bound-vars (app-exp->rand exp)))))))

(deftype bound? (-> (symbol expression) boolean))
(define bound?
  (lambda (sym exp)
    ;; use not not to get a proper boolean from member
    (not (not (member sym (bound-vars exp))))))

) ;; end module