Lisp Recursion Issue With Stack

Question

I have just hit another bump in the road along my journey with Scheme. It's probably safe to say my table has had enough of me banging my head into it... I have written a function to find the min and max number within a list for class homework. The logic is sound (i think so...) and everything works fine, however, only the value of the first function call is returned from the (define (iterator aList minNum maxNum)). What I am noticing with the debugger is that after every recursion / function call I see (using DrRacket) that function call being pushed to the stack. Once the recursion happens for the last time and the code jumps down to the return of (list minNum maxNum) it doesn't return what it should, as I can see the values are correct, instead I see the function calls coming off the stack one by one until it gets to the very first one. Thus the initial values which would be the first two values form the list are returned instead. I know the stack is FIFO, however, I am not even trying to push anything to the stack. In theory I just want to call the function again and keep passing values back up... Any guidance on this would be much appreciated.

 (define (findMinMax aList)
  (define (iterator aList minNum maxNum)
   (when(not(null? aList))
    (cond
    ((> minNum (car aList))
     (set! minNum (car aList)))
    ((< maxNum (car aList))
     (set! maxNum (car aList))))
   (iterator (cdr aList) minNum maxNum))
   (list minNum maxNum))
 (cond ; setting the first two atoms in a list appropriately to the min and max variables.
 ((< (car aList) (car(cdr aList)))
  (iterator (cdr (cdr aList)) (car aList) (car(cdr aList))))
 ((> (car aList) (car(cdr aList)))
  (iterator (cdr (cdr aList)) (car(cdr aList)) (car aList)))
 (else
  (iterator (cdr (cdr aList)) (car aList) (car(cdr aList))))))

GoZoner · Accepted Answer · 2013-10-21 18:31:34Z

2

Your sophistication with Scheme is already much better than most on SO! There is a very useful Scheme syntactic keyword 'named-let' that makes it easy to define internal, recursive function definitions. Here is an example to take you to the next level:

(define (findMinMax list)
  (assert (not (null? list)))
  (let finding ((list (cdr list))
                (lMin (car list))
                (lMax (car list)))
    (if (null? list)
        (values lMin lMax)
        (finding (cdr list)
                 (min lMin (car list))
                 (max lMax (car list))))))

Note also that I've used the values syntactic form to return two values. And, I used builtin functions min and max. Also, the use of finding is tail-recursive meaning that the Scheme compiler converts this recursive call into an iterative call and thus no stack frame is required.

edited Oct 21, 2013 at 18:31

answered Oct 21, 2013 at 14:23

GoZoner

70.7k20 gold badges100 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

WorBlux Over a year ago

You also shadow a global function to a variable (a general no-no) and that variable to another variable with the name list. (confusing if you don't know whats going on).

GoZoner Over a year ago

Thanks. I consider this an advantage; I love the strict lexical scoping of Scheme. Cheers!

Sylwester · Accepted Answer · 2013-10-21 08:29:37Z

You need to rewrite the code not to use either set! or when since it's holding you back on learning Scheme. You have to think differently when writing in a Lisp dialect than an Algol dialect so try just making the change in the recursion rather than using set! and use 3 way if and just one expression in the body of a procedure.

(define (my-length lst)
  (define (length-aux lst n)
    (if (null? lst)
        n ; base case, return the length
        (length-aux (cdr lst) (+ n 1)))) ; instead of set! we put the new value as argument

  (length-aux lst 0)) ; one expression that calls the auxiliary procedure to do the calculations

Your internal procedure can be made just as simple:

(define (iterator aList minNum maxNum)
  (if (null? <???>)
      (list minNum maxNum)
      (iterator <???> 
                (min <???> <???>)
                (max <???> <???>))))

Or maybe with if instead of min/max

(define (iterator aList minNum maxNum)
  (if (null? <???>)
      (list minNum maxNum)
      (let ((n (car aList))) ; use n to compare with minNum/maxNum
        (iterator <???> 
                  (if <???> <???> <???>)
                  (if <???> <???> <???>))))

Will Ness · Accepted Answer · 2013-10-23 07:25:06Z

You have some misleading indentation. Indentation step of 1 is really not advisable. 2 is OK but 4 is better while you're learning Scheme.

You actually just need to make some minimal changes, syntax-wise. Instead of

(define (findMinMax aList)
    (define (iterator aList minNum maxNum)
        (when (not (null? aList))
            (cond
                ((> minNum (car aList))           ; change the local 
                    (set! minNum (car aList)))    ;   variable's value
                ((< maxNum (car aList))
                    (set! maxNum (car aList))))
            (iterator (cdr aList) minNum maxNum)) ; pass new values on, but
                                          ; ignore recursive result, and
        (list minNum maxNum))             ; return the current values instead!

you need:

(define (findMinMax aList)
    (define (iterator aList minNum maxNum)
        (if (not (null? aList))
            (begin
                (cond
                    ((> minNum (car aList))
                        (set! minNum (car aList)))
                    ((< maxNum (car aList))
                        (set! maxNum (car aList))))
                (iterator (cdr aList) minNum maxNum)) ; return recursive result!
            (list minNum maxNum)))                    ; ELSE - base case

the initial call is just:

    (iterator (cdr aList) (car aList) (car aList)))

WorBlux · Accepted Answer · 2013-10-21 23:24:12Z

0

Yes stay away from set! or you won't learn the ropes of the functional aspect of scheme. You can use it if something is otherwise very messy but it's rare that that's the case.

A lot of answers here are expressed in terms of recursion, but often simpler to understand are higher order functions

Both the built-in min and max are defined in some implementations in terms of fold.

(define (min first . L) (fold (lambda (x y) (if (< x y) x y)) first L))
(define (max first . L) (fold (lambda (x y) (if (> x y) x y)) first L))

(define (MinMax first . L)
  (define (internal y x)
    (let ((min (car x))
          (max (cdr x)))
      (cons (if (< min y) min y)
            (if (> max y) max y))))
  (fold internal (cons first first) L))

Notice how much cleaner the code is when you can fit what your doing to a higher order function. Two lines to define the ADT, Two lines to tell fold how to carry along the local state, and one line for the actual procedure.

;;Sample Call

> (minmax 0 9 3 4 7 6 -2)

;Value 4: (-2 . 9)

edited Oct 21, 2013 at 23:24

answered Oct 21, 2013 at 18:22

WorBlux

1,41311 silver badges20 bronze badges

1 Comment

WorBlux Over a year ago

(X < y) was a brain fart, changed to the correct notation (< x y). Fold is in the srfi 1 library, which is supported by most scheme implementations. The syntax is (fold kons knil L) and is formaly defined as (fold kons knil '()) -> knil and (fold kons knil L) -> (fold kons (kons (car L) knil) (cdr L)) How its definition is implemented in the procedure is irrelevant.

Collectives™ on Stack Overflow

Lisp Recursion Issue With Stack

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related