lexical scope v let in scheme functions

Question

I've been chewing through a bit of The Little Schemer and the Peano examples got me thinking about operation size and time.

I got some help on making Peano Multiplication linear -- however (time ...) didn't show much difference between a lexically scoped version and the let-loop version.

I do however find a massive difference between the lexically scoped and let-loop versions when minting a Peano Exponent function.

The obvious question is why it makes such a difference (or perhaps it does not and my attempt at a lexically scoped Peano Exponent has some fatal error)?

-- i had thought i understood what the let-loop was doing in terms of storing the value in the parent enclosure (making the two roughly equivalent); in which way is this wrong?

;; lexically scoped version of Peano Exp
(define (exxp-lex b ex)
 (define (exxp-aux ex prod)
 (cond
 ((zero? ex) 1)
 ((= ex 1) (mX-let b prod))
 (else
 (exxp-aux (- ex 1) (mX-lex b prod)))))
 (exxp-aux ex 1))
;; let version of Peano Exp
(define (exxp-let b ex)
 (let loop ((ex ex)
 (prod 1))
 (cond
 ((zero? ex) 1)
 ((= ex 1) (mX-let prod b))
 (else
 (loop (- ex 1) (mX-let prod b))))
 ))

If it's relevant, I am using petite-chez scheme.

For reference, here are the Peano Multiplication functions.

;; a lexically scoped version Peano Multiplication
(define (mX-lex n m)
 (define (mX-aux m product)
 (if (zero? m)
 product
 (mX-aux (- m 1) (+ product n))))
 (mX-aux m 0))
;; using let for Peano Mult
(define (mX-let n m)
 (let loop ((m m)
 (product 0))
 (if (zero? m)
 product
 (loop (- m 1) (+ product n)))))

• jbm: This doesn't address your question, but just as a point of interest: all the functions above are lexically scoped and in fact Scheme is always lexically scoped. What distinguishes the ones you're referring to as lexically scoped is that they use "internal definitions" whereas the others use "named let". As I said, this is neither here nor there regarding the question; I only mention it since you seem interested in learning more about Scheme.
• ricardo: @jbm thanks. I am very interested - is there a major difference between function operation/execution in either case?
• jbm: They should be the same in this case, as would an equivalent use of letrec. (In fact, many implementations translate named let to letrec, and may do something similar with internal definitions). However, locally scoped mutually recursive procedures can be expressed with internal definitions and letrec but not with named let. I see it as coming down to what best fits the logic and flow of your function(s), there shouldn't be a big performance difference between otherwise equivalent binding forms.

Answer 1

In exxp-aux, you call (mX-let b prod) and (mX-lex b prod). You probably meant the two calls to be identical.

In exxp-let, you call (mX-let prod b).

mX-lex and mX-let are both implemented such that they would be faster if you call them with the larger multiplicand first and the smaller one second, because the second parameter controls the number of additions. Since prod is likely to be larger than b, your exxp-aux will be slower.

• ricardo: +1, accepted. wow, i changed the order of the (mX-fun b prod) calls to (mX-fun prod b)` and the speed difference disappeared. Had no idea. Now the only thing that's different is the byte size of the operation -- why is the let-loop so much smaller?
• 200_success: Funny how you had a 50-50 chance of getting the fast version, being oblivious to the performance difference due to the parameter ordering. I have no idea how to explain the difference in code size, though.
• ricardo: How costly is testing parameter size and setting the order so as to maximise performance? I mean, at what point does it generally become worth it?
• 200_success: Probably not costly. However, the point of the exercise was to implement Peano arithmetic, not performance. Would you still consider it a valid implementation if you conditionally swapped the arguments? If you wanted speed, you would just do (* b prod).