3
\$\begingroup\$

I'm working through SICP and have implemented exercise 1.11 (Pascal's Triangle). What I'm curious about here is performance considerations by defining functions within the main function. I would assume they get reassigned with each invocation of the function. In saying that, this style appeals to me, as the functionality is scoped to the main function, and lexical scoping is used to effect. Obviously I'm a scheme noob so please go nuts in tearing this code apart.

(define (pascal-value row elem)  

  (define (out-of-range?)  
    (or (> elem row) (< elem 1)))

  (define (edge?)
    (or (= row elem) (= elem 1)))

  (cond ((edge?) 1)
        ((out-of-range?) 0)
        (else (+ (pascal-value (- row 1) (- elem 1)) 
                 (pascal-value (- row 1) elem)))))
\$\endgroup\$
5
\$\begingroup\$

Yes, those inner functions do get reassigned at each invocation, but that's cheap. In sane implementations, the inner function bodies are compiled just once, with a new lexical environment attached each time.

(In other sane implementations, the inner functions could be inlined into the outer function, but still, it's only compiled once, not for every invocation.)

So don't worry about the performance, it's not as bad as you may think. :-)

\$\endgroup\$
  • \$\begingroup\$ Thank you, I'm just wondering if you could explain a bit further what you mean by "with a new lexical environment attached each time". I understood that as meaning that even though a new lexical environment is used for each recursive call, the inner functions are compiled only once. Is that correct? \$\endgroup\$ – stantona May 21 '14 at 20:47
  • \$\begingroup\$ @stantona Right. :-) \$\endgroup\$ – Chris Jester-Young May 21 '14 at 22:44
2
\$\begingroup\$

The big performance problem here is the algorithm, not the local functions. It takes \$O(2^{row})\$ time, because it recomputes elements that are used more than once. This is fine for small values of row, but (pascal-value 54 27) would take something like a year.

If performance is a problem, you can improve it by using an algorithm that only computes each element once and reuses it (“dynamic programming”). This takes only \$O({row}^2)\$ time. (And if you save results across calls, subsequent calls take constant time.)

I wouldn't bother with out-of-range? and edge? — not because of performance, but because they don't help readability enough to be worth their complexity. I'd just inline them in the cond.

\$\endgroup\$
  • \$\begingroup\$ That's great, and yes I realize the performance issue given the repeated computation of elements. What do you mean by "dynamic programming"? Do you mind providing links etc? Thanks. \$\endgroup\$ – stantona May 23 '14 at 21:14
  • \$\begingroup\$ @stantona Here's a Wikipedia article on dynamic programming, but, one implementation strategy for dynamic programming is to memoise results (e.g., have a arguments->results cache). \$\endgroup\$ – Chris Jester-Young May 24 '14 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.