SICP 1.25 interpreter issue

Question

1) DrRacket

2) https://inst.eecs.berkeley.edu/~cs61a/sp15/assets/interpreter/scheme.html

Using both of the interpreters above for Hacker's version with arguments (expmod 11 17 17) yields different answers. 11 for DrRacket (as the procedure should) and 0 for inst.eecs.berkeley.edu

Included is an example evaluation at the bottom. Substituting for all (< base m) into both interpreters yields different answers when using inst.eecs.berkeley.edu and therefore makes the entire timed-prime-test fail for this interpreter.

My question: What is the underlying issue with this interpreter? Is this problem due to an error in interpretation? A different method for evaluation between the two?

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))
(define (square x)
  (* x x))

(remainder (fast-expt 11 17) 17)
(remainder (* 11 (fast-expt 11 16)) 17)
(remainder (* 11 (square (fast-expt 11 8))) 17)
(remainder (* 11 (square (square (fast-expt 11 4)))) 17)
(remainder (* 11 (square (square (square (fast-expt 11 2))))) 17)
(remainder (* 11 (square (square (square (square (fast-expt 11 1)))))) 17)
(remainder (* 11 (square (square (square (square (* 11 (fast-expt 11 0))))))) 17)
(remainder (* 11 (square (square (square (square (* 11 1)))))) 17)
(remainder (* 11 (square (square (square (square 11))))) 17)
(remainder (* 11 (square (square (square 121)))) 17)
(remainder (* 11 (square (square 14641))) 17)
(remainder (* 11 (square 214358881)) 17)
(remainder (* 11 45949729863572161) 17)
(remainder 505447028499293771 17)

A link to online SICP

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#call_footnote_Temp_78

Note that expmod computes the power p=base^exp first, then finds the modulo. This means that the temporary result p can be very large. So large that it can't be represented exactly using floating point. Instead you must write a variation of your fast-expt that computes the modulo of each temporary result. In this way all numbers in the computation will be below the modulo - and you will get the correct result also in the Berkeley Scheme implementation. — soegaard

Sylwester Sylwester · Accepted Answer · 2018-08-03T22:42:35

So while DrRacket has a SICP language where SICP code should work Racket's default language is not compatible with Scheme. It's close so the two languages have more in common than Java and C#, but they are to be acknowledged as different languages. Racket has support for Scheme. Both #!r5rs and #!r6rs.

Your online intepreter might just have basic Scheme functionality and perhaps only floating point numbers. Only R7RS requires the full numeric tower so large numbers might become floats. A very easy test by me revealed that the number became inexact very fast:

(/ 1 2) ; ==> 0.5

With a full numeric tower the answer would be the rational exact number 1/2. Evalutation call/cc, and exact->inexact gave an error so the interpreter does not meet the requirement for the standard scheme reports.

You need to read the documentation and features of your chosen implementation since your program might depend on features that are not included everywhere. If I implemented a curly language that had elementary support for some Java bindings it would still not be a Java implementation since it would be incomplete.

SICP 1.25 interpreter issue

1 Answers