>128
>* どうして scheme の map〜保証しないのでしょうか．

これはC言語等でも起こりうる問題です。
単純な話、mapで適用されるリストの評価順序が
schemeの仕様で規定されていない為です。

例えば下の様なmapの実装だと、
(define (map1 proc x)
　(let loop ((l x))
　　(if (pair? l)
　　　(cons (proc (car l)) (loop (cdr l)))
　　　'())))

consの両辺の引数の評価順序は仕様では規定されてないので、
どっちが先に評価されるかは、完全に処理系に依存します。
この実装でもschemeのmapの仕様は満たしています。
破壊操作を前提とするなら、専用のmapを作るか持ってくる
必要があります。

>* Common Lisp では末尾再帰〜

実装者が手抜きすれば当然、最適化してくれません。
まともな処理系ならコンパイルすれば最適化されると思います。
ただし、仕様に完全に組みこまれているわけではないので、
実際に「最適化可能」と謳っていても、schemeのスペシャリストが
書く様な複雑怪奇な再帰を使ったコードが完全に最適化される
可能性は低いと思います。