从SICP说起：重新学习（函数式）编程

2022-02-24 20:05:00 PUBLIC

从SICP说起

2021年开始，我把主力编辑器换成了 emacs ，折腾的过程里，似懂非懂地写了一部分 elisp ，也自然地想起了在本科的时候一直藏在收藏夹里的书：SICP。

惭愧的是，虽然一直知道这本书，实际上却从来没有完整地阅读过。没想到这次阅读成了一次开端，让我有一种重新学习编程的感觉。

对函数式编程的第一印象

看完SICP前几章之后，印象最深刻的特性是：immutable，stateless，pure function。

这些特性加起来，可以总结出FP的审美倾向：我想要一个static computational graph（directed acyclic graph），而不是一个dynamic state machine（looply graph）。

结合平常写代码的经历，追踪state的变化和理解不同时刻同一个state的含义，确实消耗了大量心智带宽。

而自然的，我们常用的冯诺依曼机器是以存储（也就是状态）为核心的，如何高效地在OOP machine上实现FP呢？

这就需要一些technique的辅助：lazy evaluation/garbage collection：

lazy evaluation把所有可能的状态都提前声明，例如一个state在所有timestamp的record，但是只有真正需要的时候才触发计算。（这里有点像一个把戏，state其实还是在变化的，但是每次变化我们都认为他是一个新的state_i，以此来保证state_0永远是state_0）。
garbage collection：提前声明的变量那么多，自然有许多是用不到了，那就需要GC去释放资源了。

一些参考

比我总结的更好的FP特性：doing it the fp way in cpp
- Immutable variables
  In functional programming, you can’t modify a variable after it’s been initialized. You just can’t. You can create new variables but you can’t modify existing variables.
- No side effects
  A side effect is a state change in something other than the function that’s currently executing. Modifying a variable defined outside the function, printing out to the console, raising an exception, and reading data from a file are all examples of side effects.
- No state
  A function may have local variables containing temporary state internally, but the function cannot reference any member variables of the class or object the function belongs to. State encourages mutability leading to side effects. Functional Programming doesn’t want you to do that.
如何在CPP中利用这种写法，需要persistent data structure，例如：https://github.com/arximboldi/immer
lazy evaluation的一个广泛应用是在包管理工具中：nix\guix，语言中配置了所有的package，但只有使用的才会被实际执行安装。
相关的记忆碎片：
- rust默认variable是immutable的
- range library的实现可以认为是上述特性在CPP中的集中实现
如果想在CPP中写FP style，推荐的书是：Functinal Programming in C++
- CPP的标准变化，似乎是越来越FP的：
  - std::range list
  - std::visitor pattern match
  - std::variant, std::optional algebraic data type
组合优于继承，要traits不要class

第一次实践

需要承认的是，用FP style写出来zero-cost abstraction的实际难度还是很大（可能是我太菜了）。

不过有一些任务看起来是非常适合这种风格的。

我尝试了一个例子：把一个presentation的视频中的slide分割出来图片。

要做这么几个事：

写一个wrapper把 cv::VideoCapture 包装成一个 forward_range ，顺便需要实现一个cache机制供lazy evaluation使用。
一个简单的分割算法，不是这个例子的重点。
用 range 把几个操作pipe起来。

看看code

#include <iostream>
#include <vector>
#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#include <opencv2/videoio.hpp>
#include <range/v3/all.hpp>

const double PERCENTAGE = 0.9;
const int FREQ = 30;

using std::cout;

class VideoCaptureView : public ranges::view_facade<VideoCaptureView> {
  friend ranges::range_access;
  cv::Mat const &read() const {
    std::cout << "reading: " << cnt << std::endl;
    return (*frame_buffer)[cnt];
  }
  bool equal(ranges::default_sentinel_t) const {
    return cnt >= frame_buffer->size();
  }
  bool equal(const VideoCaptureView &that) const { return cnt == that.cnt; }
  void next() {
    cnt++;
    if (cnt == frame_buffer->size()) {
      cv::Mat frame;
      cap_ >> frame;
      if (!frame.empty()) {
        frame_buffer->push_back(frame);
      }
    }
    for (; *to_release_cnt + 2 * FREQ < cnt; (*to_release_cnt)++)
      (*frame_buffer)[*to_release_cnt].release();
  }
  bool is_end = false;
  std::shared_ptr<std::vector<cv::Mat>> frame_buffer;
  std::shared_ptr<int> to_release_cnt;
  int cnt = -1;

  cv::VideoCapture cap_;

public:
  VideoCaptureView() = default;
  explicit VideoCaptureView(const std::string &name) : cap_(name) {
    frame_buffer = std::make_shared<std::vector<cv::Mat>>();
    to_release_cnt = std::make_shared<int>(0);
    cv::Mat frame;
    cap_ >> frame;
    frame_buffer->push_back(frame);
    cnt = 0;
  }
  using ranges::view_facade<VideoCaptureView>::begin;
  using ranges::view_facade<VideoCaptureView>::end;
};



double diff_between_pairs(const cv::Mat &img1, const cv::Mat &img2) {
  cv::Mat diff;
  cv::absdiff(img1, img2, diff);

  cv::threshold(diff, diff, 50, 255, cv::THRESH_BINARY);

  auto diff_pixel = cv::mean(diff)[0];
  std::cout << diff_pixel << std::endl;
  return diff_pixel;
}

double get_kernel(const std::vector<double> &sorted_diff) {
  double kernel1 = 0;
  double kernel2 = 10;
  std::vector<int> sorted_diff_kind;
  for (int iter = 0; iter < 10; iter++) {
    double sum_1 = 0, cnt_1 = 0;
    double sum_2 = 0, cnt_2 = 0;
    for (auto &&diff : sorted_diff) {
      double dist1 = std::abs(kernel1 - diff);
      double dist2 = std::abs(kernel2 - diff);
      if (dist1 < dist2)
        sum_1 += diff, cnt_1++;
      else
        sum_2 += diff, cnt_2++;
    }
    kernel1 = sum_1 / cnt_1;
    kernel2 = sum_2 / cnt_2;
    printf("iter: %d, kernel1: %f, kernel2: %f\n", iter, kernel1, kernel2);
  }

  double err_std = 0, cnt_std = 0;
  for (auto &&diff : sorted_diff) {
    double dist1 = std::abs(kernel1 - diff);
    double dist2 = std::abs(kernel2 - diff);
    if (dist1 < dist2)
      err_std += dist1 * dist1, cnt_std++;
  }

  double class1_std = std::sqrt(err_std / cnt_std);

  std::cout << "class1_std: " << class1_std << std::endl;
  return kernel1 + class1_std;
}

int main(int argc, char **argv) {
  CPP_assert(ranges::forward_range<VideoCaptureView>);
  CPP_assert(!ranges::bidirectional_range<VideoCaptureView>);

  auto get_zipped_view = [argv](){
    return VideoCaptureView(argv[1])
      | ranges::view::transform([](const cv::Mat &img) {
          cv::Mat gray;
          cv::cvtColor(img, gray, cv::COLOR_BGR2GRAY);
          return std::make_pair(img, gray);
        })
      | ranges::view::stride(FREQ)
      | ranges::view::sliding(2);
  };

  auto window_view = get_zipped_view()
    | ranges::view::transform([](auto r) {
        auto r_vec = ranges::to<std::vector<std::pair<cv::Mat,cv::Mat>>>(r);
        return diff_between_pairs(r_vec[0].second, r_vec[1].second);
      });

  int diff_percentile = get_kernel(ranges::to<std::vector>(window_view));

  auto window_view2 = get_zipped_view()
    | ranges::view::filter([diff_percentile](auto r) {
        auto r_vec = ranges::to<std::vector<std::pair<cv::Mat,cv::Mat>>>(r);
        return diff_between_pairs(r_vec[0].second, r_vec[1].second) > diff_percentile;
      });

  ranges::for_each(window_view2 | ranges::views::enumerate, [](auto r) {
    auto idx = std::get<0>(r);
    auto r_vec = ranges::to<std::vector<std::pair<cv::Mat, cv::Mat>>>(std::get<1>(r));
    char name[100];
    sprintf(name, "result/%05ld.jpg", idx + 1);
    cv::imwrite(name, r_vec[1].first);
    if (idx == 0)
      cv::imwrite("result/00000.jpg", r_vec[0].first);
  });
}