Final recursion.

Discussion of Scheme and Racket
Post Reply
kbprince
Posts: 1
Joined: Sat Jan 05, 2013 12:51 pm

Final recursion.

Post by kbprince » Sat Jan 05, 2013 1:00 pm

Here is the baby end of the parser.
It treats one 'begin ' implicit.
He must be, roughly, the first call to whom l 'on pass:
- the name of function
- the list of the expressions of the body of function

Code: Select all

(define (trec-body fun body term)
  (if (null? body) #t
    (if (null? (cdr body))
        ;; Last expression of body
        (trec-expr fun (car body) (and term #t))
      (and
       ;; Some non-last expression
       (trec-expr fun (car body) (and term #f))
       ;; Continue with the other expressions
       (trec-body fun (cdr body) term)))))
ignorable (c 'est-à-dire an interlocking of 'if ' or.
Lorsqu 'il is wrong, he points out qu 'on is " under " a function not - ignorable (as 'pus ' for instance).

It determines this qu 'on must go back if they meet function in the course of the parsing.
more precisely, the function which really turns stocks and determines if c 'est recursive - terminal or not resembles this:

Code: Select all

(define (trec-expr fun expr term)
  (cond
   ((not (pair? expr)) #t)
   ((eq? fun (car expr))
    ;; Found a call to 'fun'
    (if (not term) #f ;; No need to continue
      ;; Checks 'fun's args, but with 'term' set to false
      (trec-body fun (cdr expr) #f)))
   ;; This is not a call to fun. Go inside.
   (else
    (case (car expr)
      ((if) (trec-if fun (cdr expr) term))
      ((cond) (trec-cond fun (cdr expr) term))
      ;; Idem for every special form like:
      ;; apply case cond define do fluid-let lambda let let* letrec named-lambda etc.
      ((let) (trec-let fun (cdr expr) term))
      ...
      (else
       ;; This is a normal function (like '+' 'cons' etc.)
       ;; Checks its args, with 'term' set to false
       (trec-body fun (cdr expr) #f))))))
(and not trec-yew tree), as well as all other parsers for special forms remains to make, as well as 'trec-cond ' in the 14th line: 'trec-apply ' 'trec-hut ' 'trec-define ' 'trec-do ' 'trec-fluid-let ' 'trec-lambda ' 'trec-let ' 'trec-let* ' 'trec-named-lambda ' etc .

Can you help Me Please to finish this program ?!
I must write a program which takes in argument a list corresponding to a function and returns ' * #t ' s 'il s 'agit d 'une final recursion and ' * #f ' otherwise.

Thanks

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Final recursion.

Post by saulgoode » Wed Jan 16, 2013 11:43 am

Firstly, you will need to quote the identifiers in your 'case' statement.

I believe that your individual parsers (trec-if, trec-cond, trec-begin, ...) should be implemented something like the following:

Code: Select all

(define (trec-if fun expr term)
  (let ((consequent (cadr expr))
        (alternative (caddr expr)) )
    (if (pair? consequent)
      (if (eq? fun (car consequent))
        #t ; last expression of consequent is a tail call
        (trec-expr fun consequent term) ; test last expression in case it is a
                                        ; 'begin, 'let, 'if, or other compound block
        )
      ; consequent does not contain a tail call
      (if (pair? alternative)
        (if (eq? fun (car alternative))
          #t ; last expression of alternative is a tail call
          (trec-expr fun alternative term) )
        ; alternative not provide, or does not contain a tail call
        #f ))))
The procedures for each of the other operations should follow the same pattern, parsing each expression for tail calls per the specification.

Post Reply