Scoring protocol does not timeout when scheme code has infinite loop

[greynotgrayskies]

If there's an infinite loop in scheme code that is tail-recursive, OK does not time it out, but continues to run indefinitely.

[greynotgrayskies]

The problem is a bit more complex than I thought. For a solution like this, and the scoring protocol times out just fine:

(define (deep-map fn s)
        (deep-map fn s))

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --score --local --no-update
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Scoring tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout

---------------------------------------------------------------------
deep-map
    Passed: 0
    Failed: 1
[k..........] 0.0% passed

---------------------------------------------------------------------
Point breakdown
    deep-map: 0.0/1

Score:
    Total: 0.0

~/workspace/cs61a/grading/hw09$ 

However, this particular solution causes OK to hang indefinitely after grading. OK doesn't respond to a keyboard interrupt after this, so you have to terminate the process some other way:

(define (deep-map fn s)
  (cond ((null? s) nil)
      ((integer? (car s)) (deep-map fn (cons (fn (car s)) (cdr s))))
      ((list? (car s)) (deep-map fn (car s)))
  )     
)

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --score --local --no-update
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Scoring tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout


^C^C^C^Z
[1]+  Stopped                 python3 ok -q deep-map --score --local --no-update
~/workspace/cs61a/grading/hw09$ kill %1
[1]+  Terminated              python3 ok -q deep-map --score --local --no-update
~/workspace/cs61a/grading/hw09$ 

This also affects the normal grading protocol:

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --local
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Running tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout

^Z
[1]+  Stopped                 python3 ok -q deep-map --local
~/workspace/cs61a/grading/hw09$ kill %1
[1]+  Terminated              python3 ok -q deep-map --local

[kavigupta]

Confirmed, repros on 1.14.19

[kavigupta]

I'm pretty sure this is related to memory usage. That specific piece of student code is equivalent to

(define (deep-map fn s)
  (deep-map fn (cons (fn (car s)) (cdr s))))

which, since the test case is (deep-map square '(2 3)), this is equivalent to (define (f x) (f (* x x))) (f 2). This leads to a repeated squaring of 2. On iteration i, this creates the number 2^(2^i), which takes 2^i bits to store. Empirically, the test case above uses all 8GB of my computer's memory and that causes the slowdown towards the end

I think the solution to this is probably to limit the memory usage of ok somehow.