Use of local in Racket/Scheme

Question

In Exercise 18.1.12 from htdp, I've re-written the maxi function using "local".

;; maxi : non-empty-lon  ->  number
;; to determine the largest number on alon
(define (maxi alon)
  (cond
    [(empty? (rest alon)) (first alon)]
    [else (local ((define m (maxi (rest alon))))
            (cond
              [(> (first alon) m) (first alon)]
              [(> m (first (rest alon))) m]
              [else (first (rest alon))]))]))

I'm not sure why I would do this in "real life" as it seems the book's version is shorter, clearer and probably faster as well.

(define (maxi alon)
  (cond
    [(empty? (rest alon)) (first alon)]
    [else (cond
        [(> (first alon) (maxi (rest alon))) (first alon)]
        [else (maxi (rest alon))])]))

Was it meant to be a purely pedagogical exercise? Could an experienced Schemer comment on the code above? Thank you.

Terat

Well, here's a Socratic question for you: Why do you think the non-local version is "probably faster"? I'll post a real answer to this question after hearing your thoughts. :-) – Oralee

Sifu Chris, thank you for questioning my ASS-umptions. I'm learning to appreciate your insight more and more. So it seems that the "local" version is much faster than the "pure" recursive version when the list gets large. I arrived at this conclusion by calling the time function on a list with 20 numbers and was astounded to see an average of 550x difference in performance. I don't know how Racket/Scheme works internally to explain the discrepancy though. Stepping through the "local" version seems to show that 20 versions of the local function "m" are producing a value. – Terat

Answer 1

Personally, I think this is a poor example of the importance of local and I don't believe you fully understood the importance of the question, so what I will do is go through the concept that you should notice, then go through your example and finally give you a better example.

CONCEPT

First off, the idea of local here (among many other things) is to clarify the meaning of snippets of code.

YOUR EXAMPLE

Lets consider your example, you define a local constant called m which appears to be correct. Although, since the letter m has no significant meaning your solution appears to be unclear. So, how might we fix your solution?

We need to give m a name that clearly identifies what m represents. So, we begin by directly considering what m represents which is (maxi (rest alon))

Well (maxi (rest alon)) simply says find the maximum number of (rest alon)

So lets rename m to find-max

Now your code looks like:

;; maxi : non-empty-lon  ->  number
;; to determine the largest number on alon
(define (maxi alon)
  (cond
    [(empty? (rest alon)) (first alon)]
    [else (local ((define find-max (maxi (rest alon))))
            (cond
              [(> (first alon) find-max) (first alon)]
              [(> find-max (first (rest alon))) find-max]
              [else (first (rest alon))]))]))

Replacing m with find-max makes the code much clearer! Leaving us with a rule of thumb, give your constants meaningful names.

MY EXAMPLE

To further clarify, lets consider a function that consumes two points and produces the slope of the line segment created by connecting the two points. Our first approach might be:

;;where x1,y1 belong to point 1 and x2,y2 belong to point 2
(define (find-slope x1 y1 x2 y2)
  (sqrt (+ (sqr (- x2 x1))) (sqr (- y2 y1))))

But we could be clearer using local:

(define (find-slope x1 y1 x2 y2)
  (local
    [(define delta-x (- x2 x1))
     (define delta-y (- y2 y1))]
    (sqrt (+ (sqr delta-x)) (sqr delta-y))))

Notice how delta describes what the function does at that part; finding the change in x or y. So, what we need to learn here is that, although the first solution may make use of less code, the second solution describes what we are doing and can be easily read. That was the entire idea of the question and it may seem stupid, but it is a convention they tend to stress when learning scheme in an academic setting.

As for the efficiency of the first and second solution, the second solution is definitely much faster for obvious reasons (after you look at how Racket evaluates expressions), but that wasn't the main purpose of the question.

Hope this helps

Epeirogeny

Thank you Adrian for taking time to explain things clearly! I'm in your debt. – Terat

Answer 2

Instead of using local, one can go as well using Racket's internal definitions (especially with more recent versions).

For example:

(define (maxi alon)
  (cond
    [(empty? (rest alon)) (first alon)]
    [else (define m (maxi (rest alon)))        ; here is an internal define
          (cond
            [(> (first alon) m) (first alon)]
            [(> m (first (rest alon))) m]
            [else (first (rest alon))])]))

Hemimorphite

Note that internal definitions (on purpose) is not available in the teaching languages. In order to emphasize that the definitions are local, one has to use local. – Culprit

Answer 3

Using local is way faster here because it only evaluates (maxi (rest alon)) once per recursion, whereas with the second version it evaluates (maxi (rest alon)) twice whenever it gets to the last case:

  (cond
    [(> (first alon) (maxi (rest alon))) (first alon)]
    [else (maxi (rest alon))])

Local saves the result so you don't do the same work twice. Notice if you lift the (maxi (rest alon)) out with local, it isn't in the else case anymore:

(local ((define m (maxi (rest alon))))
  (cond
    [(> (first alon) m) (first alon)]
    [else m]))

Helluva