On 2/24/07, William D Clinger <will_at_ccs.neu.edu> wrote:
There appears to be a slight problem in the specification you've given
- I think the code is a bit too strong as a specification.
> The map procedure applies proc element-wise to the lists and
> returns a newly allocated list of the results, in order.
> The dynamic order in which proc is applied to the elements
> of the lists is unspecified.
This imposes, as it states, no requirements on the dynamic order in
which proc is called.
> When all arguments are as they should be, the map procedure
> must behave as though it had been defined by
>
> (define (map proc list1 . lists)
> (define (map1 proc list)
> (if (null? list)
> '()
> (cons (proc (car list))
> (map1 proc (cdr list)))))
> (cond ((null? lists) (map1 proc list1))
> ((null? list1) '())
> (else
> (cons (apply proc (car list1) (map1 car lists))
> (apply map proc (cdr list1)
> (map1 cdr lists))))))
This imposes a complex relationship between the order in which proc is
called in the various arguments, and the order in which arguments to
the cons and apply functions are evaluated. For example, if the
Scheme implementation in which map was used was one where every
procedure application evaluated the arguments from right to left, then
this implementation of map would do the same with regard to the order
in which proc was called.
This is the case even though the argument evalution order is
unspecified. For any implementation [1], there is some order in which
proc would be called if map were defined as above. Your language
requires this order to be the same as that in which proc is actually
called, even if map is implemented in some other way.
This accidental (I assume) overspecification points to the problem of
specifying the behavior via a sample implementation - the sample
implementation often overdetermines the result.
[1] Even if this order is not determined before hand, there is some
order in which they would be chosen. For some Scheme
implemenntations, this might require predicting the output of a random
number generator.
--
sam th
samth_at_ccs.neu.edu
Received on Sat Feb 24 2007 - 16:31:32 UTC