;; CSE 341 - notes on recursive function definitions (for MUPL interpreter)

#lang racket

; In the assignment, the struct for functions is defined as:
; If s1 and s2 are Racket strings and e is a mupl expression, then (fun s1 s2 e) is a mupl expression (a function).
; In e, s1 is bound to the function itself (for recursion) and s2 is bound to the (one) argument. 

; Why (you might ask) do we have this strange s1 argument?  Racket doesn't have this???

; Here's a garden-variety recursive function:
(define (fact1 n)
  (if (= n 0)
      1
      (* n (fact1 (- n 1)))))

; We could also write this as
(define fact2 
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact2 (- n 1))))))

; Note what fact2 is bound to!

; Does this work?
(define fact3 "this is an impostor function!!!")
(let ((fact3 (lambda (n)
               (if (= n 0)
                   1
                   (* n (fact3 (- n 1)))))))
  (fact3 6))

; Aargh!  Wrong binding for the recursive call!  
; (Comment out the above definition if you want to run this code!!)


; Racket provides another version of let for this:
(letrec ((fact4 (lambda (n)
               (if (= n 0)
                   1
                   (* n (fact4 (- n 1)))))))
  (fact4 6))

; now this works

; The obvious way to implement letrec is to use side effects -- make a dummy version of the variables
; to be bound (e.g. fact4), bind them to the value 'undefined', and then set the variable after the
; corresponding expression is evaluated.  And this is what Racket does -- see
; http://docs.racket-lang.org/reference/let.html

; But we've been avoiding side effects in the MUPL interpreter, hence the hack to get around this issue
; for recursive function definitions.