CODEWITHSUNDEEP
schemeletrec
user1915570
user1915570

Reputation: 386

confusion of letrec, Scheme

I am struggling the difference between let, letrec, let* ... since scheme is not my primary programming language, my memory is not existing for long time.. I have this function.. now I am very confusing with letrec here.. this is again recursion.that I can understand...but can't make connection enough in this code.. (maybe still confuse about recursion) can someone explain why here need letrec 

(define myFunc
  (lambda (start end res func)
    (letrec ((func:rec_func
              (lambda (x i y)
                (if (>= i start)
                    (func:rec_func (cons i x) (- i res) (cons (func i) y))  ;; line6
                    (cons x (cons y '()))))))                               ;; line7
      (func:rec_func '() end '()))))

(edited) what I understand it's tail recursion

-> [Q1] Does it tail recursion?

-> [Q2] then, should use always letrec for tail recursion?

this function returns the lists of x, y with boundaries of start, end so it checks index i is inside boundaries , if yes, then do line 6

-> [Q3]then, what does line6 ? I can't get the line6

Upvotes: 2

Views: 934

Answers (3)

R Sahu
R Sahu

Reputation: 206687

[Q1] Does it tail recursion?

Answer Yes, it does tail recursion.

[Q2] then, should use always letrec for tail recursion?

Answer There are two ways of interpreting your question.

  1. Should we always use letrec for tail recursion? I don't think you meant to ask this. But ...

    The answer is no. Top level lambda functions can also be used for tail recursion.

  2. Should letrec always use tail recursion?

    The answer to that is: It's better for any recursive function to be tail recursive. If you can, you should make it tail recursive.

[Q3] then what does line6 ?

The code at line 6 performs the recursive call.

Let's say start is 0, end is 5, and res is 1. In the first call to func:rec_func, x is the empty list (), i is 5, and y is the empty list ().

When the first recursive function is called at line 6, the arguments are (cons i x), (- i res), and (cons (func i) y), which evaluate to: (5), 4, and ((func 5).

In the next iteration, the arguments are (4 5), 3, and ((func 4) (func 5)).

It continues until i becomes less than start. Then the recursion stops with the result ((0 1 2 3 4 5) ((func 0) (func 1) (func 2) (func 3) (func 4) (func 5)))

The code at line 7 is executed when the terminating criterion for the recursion is met, which is when (>= i start) is false.

Upvotes: 0

estebarb
estebarb

Reputation: 475

The difference with letrec, let and let* is when they do the declaration available to the program.

(letrec ((X (you could use X here))
         (Y (you could use X here too))
         )
     (X also is available here)
)


(let   ((X (nope, X isn't declared yet))
         (Y (in fact, no declaration body will see X))
         )
     (But X is available here)
)


(let* ((X (X isn't available here))
         (Y (but you could use it here))
         )
     (X also is available here)
)

To recap:

  1. The scope of a variable declared with letrec is ALL inside of the body of letrec. The compiler do some magic so the references are replaced after the declarations are over.
  2. The scope of a variable declared with let* are all expresions in the scope of let* after the declaration of the variable.
  3. And the scope of a variable declared with let is just the body of let, not the declaration parts.

Upvotes: 8

zwol
zwol

Reputation: 140748

If I remember correctly, this construct requires letrec rather than let or let* because the body of func:rec_func refers to itself. If you used let or let* here, the symbol func:rec_func within the nested lambda would be bound to any definition visible outside the top-level form, or undefined if there was no such definition - neither is what you want.

Upvotes: 1

Related Questions