CODEWITHSUNDEEP
recursionracketinfinite-loop
brj
brj

Reputation: 373

Why does `rest` return `'(())` instead of `'()` in racket

I came across this program on how variadic procedures can be used to implement composition of arbitrary number of functions

(define compose-n
  (lambda fs
    (cond
      [(null? fs) identity]
      [else (lambda (x)
              ((first fs) ((apply compose-n (rest fs)) x)))])))

However, when I remove the apply on the last line and perform the application by hand,

(define removed-compose-n
  (lambda fs
    (cond
      [(null? fs) identity]
      [else (lambda (x)
              ((first fs) ((removed-compose-n (rest fs)) x)))])))

this begins to loop and consume all the memory, crashing my computer. Furthermore, when I tried printing out fs to see what was going on

(define removed-compose-n
  (lambda fs
    (printf "fs : ~s\n" fs)
    (cond
      [(null? fs) identity]
      [else (lambda (x)
              ((first fs) ((removed-compose-n (rest fs)) x)))])))

I was surprised to see

fs : (#<procedure:id>)
fs : (())
fs : (())
fs : (())
fs : (())
fs : (())
fs : (^C                      
; user break [,bt for context]

this suggests to me that (rest fs) evaluates to '(()), which is what is causing removed-compose-n to loop, but compose-n gets away with this as (apply compose-n '(())) is same as (compose-n '()), which matches the base case of the recursion/first cond clause.

Why does (rest fs) evaluate '(()) instead of '(), causing removed-compose-n to loop? Or is the reason for looping something else entirely that I missed?

Upvotes: 0

Views: 130

Answers (2)

brj
brj

Reputation: 373

I finally understood what's happening, variadic procedure semantics had slipped my mind.

The issue wasn't rest returning '(()). rest indeed returns '(). However, variadic procedures like removed-compose-n collect their arguments into a list (indeed, that is how variadicity is achieved, since length of the list is not fixed). So for example, for the application (removed-compose-n identity add1 sub1) the value of fs will be '(identity add1 sub1) and for the application (removed-compose-n identity) the value of fs will be '(identity). Similarly, for the application (removed-compose-n '()) the value of fs will be '(()), which causes the loop.

Upvotes: 0

Atharva Shukla
Atharva Shukla

Reputation: 2137

Consider a simple case where you're applying removed-compose-n to add1:

(removed-compose-n add1)

The fs within the body of the function evaluates to (list add1). Since it's not an '(), we evaluate the RHS of the second cond-clause.

(lambda (x)
  ((first (list add1)) ((removed-compose-n (rest (list add1))) x)))

Evaluating the first and rest:

(lambda (x)
  (add1 ((removed-compose-n '()) x)))

When we evaluate the following sub-expression:

(removed-compose-n '())

The fs will have the value (list '()), which is the same as '(()). This infinite-loops because the next application will still be (removed-compose-n '())

Using apply "splices" the arguments. The second example passes in the list itself without splicing its elements.

Upvotes: 1

Related Questions