CODEWITHSUNDEEP
c++functional-programmingschemehigher-order-functionssicp
An5Drama
An5Drama

Reputation: 567

Is environment model necessary for higher-order procedures?

When learning SICP, 6.001 lec15 has:

A good understanding of the environment model tells me why (IMHO) C++ will never have a fully-functional map, filter, and fold-right/fold-left procedures that are as convenient as Scheme’s

SICP implements map, filter, fold-left (IMHO they are all based on recursion or iteration):

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

Here each recursive calls map will create one new env for each argument list (proc items), so they can be independent (similar for proc and cons etc).

But in my opinion, in C++ the above code can be done with the same ideas based on stack. So independence is still held.

Why does the lec say "C++ will never have a fully-functional map" due to "environment model"?

Based on this comment, in C++ map and filter can be implemented with for loop. proc etc func can be passed with one func pointer. For fold-left, we can use namespace to create one local iter although maybe not elegant. Then how to answer "the relationship between environment model and lackness of map in pre-C++11" (this is one more clear rephrase of the above question based on the comments below)?

Upvotes: 0

Views: 146

Answers (2)

Will Ness
Will Ness

Reputation: 71119

I don't know what the author meant there, but my understanding is that the most pertinent issue here is having map use an anonymous function which has access and modifies some variables external to it which are internal to the function which makes the map call:

(define (foo x y)
  (define (bar z)
    (set! x z)
    y)
  (map bar (list 1 2 3)))

Upvotes: 2

Enlico
Enlico

Reputation: 28490

As others have said, that link is very old. Things have changed a lot since then.

The short answer, in my opinion, is that the map you describe, exists already in C++ (C++20), and it's called std::ranges::views::transform, which can be used like this

auto w = v | transform(f);

which "corresponds" to

(define w (map f v))

in Scheme.

I've quoted corresponds because I don't know exactly how things happen at run-time for the Scheme code above. I know that std::ranges::views::transform is lazy, i.e. no work is actually performed (in the sense of f is not invoked at all) when writing the C++ line above. Only when accessing the values of w via the range API, will those values be actually computed, hence f will be called.

But I know it works, in terms of lazyness, like the corresponding Haskell code (which resembles the Scheme code a lot):

let w = map f v

Furthemore, the concept of "mapping" is not even as narrow as the one implied by the snippet of code and the claim that

C++ will never have a fully-functional map

because that map is an ad-hoc implementation of map for lists. So it's as "functional" as a program that explicitly deals with lists all along without ever defining high-level abstractions.

... Which is ok in Scheme because everything is a list, true, but you'd still have to redefine map_assocmap to run a function on the values of an "associative map" (which would still be a list, at the end of the day, in Scheme, e.g. (define myassocmap '((k1 v1) (k2 v2) (k3 v3))), but map_assocmap would not be map, because (map_assocmap f myassocmap) would have to call the f only on v1, v2, v3.)

But the point is that the concept of mapping is more general, and it pertains to Functors, as known in and .

And C++ does offer something in that direction. For instance, you can map an optional, in C++: given a std::optional<T> and a function of type U(T), it makes sense to execute that function on the value inside the optional, if there is one, thus obtaining a non-empty optional of type std::optional<U>, or to return an empty std::optional<U> (std::nullopt) if the original optional was empty. This, in C++, is the member function std::optional<T>::transform.

This would correspond to the following, in Scheme

(define (mapOpt f opt)
  (if (nullOpt? opt)
      'nullOpt
      (f (makeOpt (unwrapOpt opt)))))

assuming that one has defined the nullOpt?+'nullOpt+makeOpt+unwrapOpt API.

Upvotes: 2

Related Questions