大家好，本文介绍我们为什么使用函数式编程来开发引擎，以及它在引擎中的相关的知识点。

上一篇博文

从0开发3D引擎（四）：搭建测试环境

函数式编程的优点与缺点

优点

（1）粒度小
面向对象编程以类为单位，而函数式编程以函数为单位，粒度更小。

我只想要一个香蕉，而面向对象却给了我整个森林

（2）擅长处理数据，适合3D领域的编程
通过高阶函数、柯西化、函数组合等工具，函数式编程可以像流水线一样对数据进行管道操作，非常方便。

而3D程序正好要处理大量的数据，从函数式编程的角度来看：
3D程序=数据+逻辑

因此，我们可以这样使用函数式编程范式来进行3D编程：

• 使用Immutable/Mutable数据结构、Data Oriented思想来表达数据
• 使用函数来表达逻辑
• 使用组合、柯西化等操作作为工具，把数据和逻辑关联起来，进行管道操作

现代的3D引擎越来越倾向于面向数据进行设计，从而获得更佳的性能，如Unity新版本有很多Data Oriented的思想；
也越来越倾向于使用函数式编程范式，如Frostbite使用Frame Graph来封装现代图形API（DX12），而Frame Graph是面向数据的，有函数式风格的编码框架。

缺点

（1）存在性能问题

• Reduce、Map、Filter等操作需要遍历多次，会增加时间开销
  我们可以通过下面的方法来优化：
  a)减少不必要的Map、Reduce等操作；
  b)使用transducer来合并这些操作。具体可以参考Understanding transducer in Javascript

• 柯西化、组合等操作会增加时间开销

• 每次操作Immutable数据，都需要复制它为新的数据，增加了时间和内存开销

为什么使用Reason语言

本系列使用Reason语言来实现函数式编程。

Reason语言可以解决前面提到的性能问题：

• Bucklescript编译器在编译时进行了很多优化，使柯西化、组合等操作和Immutable数据被编译成了优化过的js代码，大幅减小了时间开销和内存开销
  更多编译器的优化以及与Typescript的比较可参考：
  架构最快最好的To JS编译器

• Reason支持Mutable变量、for/while进行迭代遍历、非纯函数
  在性能热点处可以使用它们来提高性能，而在其它地方则尽量使用Immutable数据、递归遍历和纯函数来提高代码的可读性和健壮性。

另外，Reason属于“非纯函数式编程语言”，为什么不使用Haskell这种“纯函数式编程语言”呢？
因为以下几点原因：
（1）获得更高的性能
在性能热点处使用非纯操作（如使用Mutable变量），提高性能。
（2）更简单易用
Reason允许非纯函数，不需要像Haskell一样使用各种Monad来隔离副作用，保持“纯函数”；
Reason使用严格求值，相对于Haskell的惰性求值更简单。

函数式编程学习资料

• JS 函数式编程指南
  这本书作为我学习函数式编程的第一本书，讲得很简单易懂，非常容易上手，推荐～

• Awesome FP JS
  收集了函数式编程相关的资料。

• F# for fun and profit
  这个博客讲了很多F#相关的函数式编程的知识点，介绍了怎样基于类型来设计、怎样处理错误等，非常全面和通俗易懂，强力推荐～
  Reason语言基于Ocaml语言，而Ocaml语言与F#语言都属于ML语言类别的，很多概念和语法都类似，所以读者在该博客学到的内容，也可以直接应用到Reason。

引擎中相关的函数式编程知识点

本文从以下几个方面进行介绍：

数据

因为我们不使用全局变量，而是通过形参传入函数需要的变量，所以所有的变量都是函数的局部变量。

我们把与引擎相关的需要持久化的数据，聚合在一起成为一个Record类型的数据，命名为“State”。该Record的一些成员是可变的（用来存放性能优先的数据），另外的成员是不可变的。

关于Record数据结构，可以参考Record。

不可变数据

介绍
不能直接修改不可变数据的值。
创建不可变数据之后，对其任何的操作，都会返回一个复制后的新数据。

示例
变量默认为不可变的（Immutable）：

//a为immutable变量
let a = 1;
//导致编译错误
a = 2;

Reason也有专门的不可变数据结构，如Tuple、List、Record。
其中，Record类似于Javascript中的Object，我们以它为例，来看下如何使用不可变数据结构：
首先定义Record的类型：

type person = {
  age: int,
  name: string
};

然后定义Record的值，它被编译器推导为person类型：

let me = {
  age: 5,
  name: "Big Reason"
};

最后操作这个Record，如修改“age”的值：

let newMe = {
    ...me,
    age: 10
};

Js.log(newMe === me); /* false */

newMe是从me复制而来的。任何对newMe的修改，都不会影响me。
（这里Reason进行了优化，只复制了修改的age字段，没有复制name字段 ）

在引擎中的应用

大部分数据都是不可变的（是不可变变量，或者是Tuple,Record等数据结构），这样的好处是：
1)不用关心数据之间的关联关系，因为每个数据都是独立的
2)不可变数据不能被修改

相关资料
Reason->Let Binding
Reason->Record
facebook immutable.js 意义何在，使用场景？
Introduction to Immutable.js and Functional Programming Concepts

可变数据

介绍
对可变数据的任何操作，都会直接修改原数据。

示例
Reason使用"ref"关键字定义Mutable变量：

let foo = ref(5);

//将foo的值取出来，设置到five这个Immutable变量中
let five = foo^; 

//修改foo的值为6，five的值仍然为5
foo := 6;

Reason也可以通过"mutable"关键字，定义Record的字段为Mutable字段:

type person = {
  name: string,
  mutable age: int
};
let baby = {name: "Baby Reason", age: 5};
//修改原数据baby->age的值为6
baby.age = baby.age + 1; 

在引擎中的应用
因为操作可变数据不需要拷贝，没有垃圾回收的开销，所以在性能热点处常常使用可变数据。

相关资料
Reason->Mutable

函数

函数是第一等公民，函数即是数据。

相关资料：
如何理解在 JavaScript 中 "函数是第一等公民" 这句话?
Reason->Function

纯函数

介绍

纯函数是这样一种函数，即相同的输入，永远会得到相同的输出，而且没有任何可观察的副作用。

示例

let a = 1;

/* func2是纯函数 */
let func2 = value => value;

/* func1是非纯函数，因为引用了外部变量"a" */
let func1 = () => a;

在引擎中的应用

脚本组件的钩子函数(如init,update,dispose等函数，这些函数会在主循环的特定时间点被调用，从而执行函数中用户的逻辑)属于纯函数，这样是为了：
1)在导入/导出为Scene Graph文件时，能够正确序列化
当导出为Scene Graph文件时，序列化钩子函数为字符串，保存在文件中；
当导入Scene Graph文件时，反序列化字符串为函数。如果钩子函数不是纯函数(如调用了外部变量)，则在此时会报错（因为外部变量并没有定义在字符串中，所以会找不到该变量）。
2)支持多线程
可以通过序列化的方式将钩子函数传到独立于主线程的脚本线程，从而在该线程中被执行，实现多线程执行脚本，提高性能。

虽然纯函数好处很多，但引擎中大多数的函数都是非纯函数，这是因为：
1)为了提高性能
2)为了简单，允许副作用，从而避免使用Monad

相关资料
第 3 章：纯函数的好处

高阶函数

介绍
高阶函数的输入或者输出为函数。

示例

//func1是高阶函数，因为它的参数是函数
let func1 = func => func(1);

let func2 = value => value * 2;

//a=2
let a = func1(func2);   

在引擎中的应用

函数之间常常有一些重复或者类似的逻辑，可以通过提出一个私有的高阶函数来消除重复。具体示例如下：
重构前：

let add1 = value => value + 2;

let add2 = value => value + 10;

let minus1 = value => value - 10;

let minus2 = value => value - 200;

let compute1 = value => value |> add1 |> minus1;

let compute2 = value => value |> add2 |> minus2;

//compute1,compute2有重复逻辑

重构后：

...

let _compute = (value, (addFunc, minusFunc)) =>
  value |> addFunc |> minusFunc;

let compute1 = value => _compute(value, (add1, minus1));

let compute2 = value => _compute(value, (add2, minus2));

相关资料
理解 JavaScript 中的高阶函数

柯西化

介绍

只传递给函数一部分参数来调用它，让它返回一个函数去处理剩下的参数。
你可以一次性地调用curry 函数，也可以每次只传一个参数分多次调用。

示例

let func1 = (value1, value2) => value1 + value2;

//传入第一个参数，func2只有一个参数value2
let func2 = func1(1);

//a=3
let a = func2(2);

在引擎中的应用

应用的地方太多了，此处省略。

相关资料
第 4 章: 柯里化（curry）
Currying

类型

Reason是强类型语言，编译时会检查类型是否正确。

本系列希望通过尽可能强的类型约束，来达到“编译通过即程序正确，减少大量的测试工作”的目的。

关于Reason类型带来的好处，参考架构最快最好的To JS编译器：

更好的类型安全: typescript是一个JS的超集，它存在很多历史包袱。而微软引入typescript更多的是作为一个工具来使用的比如IDE的代码补全，相对安全的代码重构。而这个类型的准确从第一天开始就不是它的设计初衷，以至于Facebook自己设计了一个相对更准确地类型系统Flow. 而OCaml的类型系统是已经被形式化的证明过正确的。也就是说从理论上BuckleScript 能够保证一旦编译通过是不会有运行时候类型错误的，而typescript远远做不到这点。
更多的类型推断，更好的语言特性：用过typescript的人都知道，typescript的类型推断很弱，基本上所有参数都需要显示的标注类型。不光是这点，像对函数式编程的支持，高阶类型系统GADT的支持几乎是没有。而OCaml本身是一个比Elm,PureScript还要强大的多的语言，它自身有一个非常高阶的module system，是为数不多的对dependent type提供支持的语言，polymorphic variant。而且pattern match的编译器也是优化过的。

相关资料
The "Understanding F# types" series

基本类型

介绍
Reason包含int、float、string等基本类型。

示例

//定义a为string类型
type a = string;
//定义str变量的类型为a
let str:a = "zzz";

在引擎中的应用

应用广泛，包括以下的使用场景：
1)类型驱动设计
2)领域建模
3)枚举

相关资料

Reason->Type
Algebraic type sizes and domain modelling

Discriminated Union类型

介绍
Discriminated Union类型可以接受参数，还可以组合其它的类型。

示例

//result为Discriminated Union Type
type result('a, 'b) =
  | Ok('a)
  | Error('b);

type myPayload = {data: string};

let payloadResults: list(result(myPayload, string)) = [
  Ok({data: "hi"}),
  Ok({data: "bye"}),
  Error("Something wrong happened!")
];

在引擎中的应用

作为本文后面讲到的“容器”的实现，用于领域建模

相关资料
Reason->Type Argument
Reason->Null, Undefined & Option
Discriminated Unions

抽象类型

介绍
抽象类型只给出类型名字，没有具体的定义。

示例

//value为抽象类型
type value;

在引擎中的应用

包括以下的使用场景：
1)如果不需要类型的具体定义，则将该类型定义为抽象类型

如在封装WebGL API的FFI中(什么是FFI?)，因为不需要知道“WebGL的上下文”包含哪些方法和属性，所以将其定义为抽象类型。

示例代码如下：

//抽象类型
type webgl1Context;

[@bs.send]
external getWebgl1Context : ('canvas, [@bs.as "webgl"] _) => webgl1Context = "getContext";

[@bs.send.pipe: webgl1Context]
external viewport : (int, int, int, int) => unit = "";




//client code

//gl是webgl1Context类型
//编译后的js代码为：var gl = canvasDom.getContext("webgl");
let gl = getWebgl1Context(canvasDom);   

//编译后的js代码为：gl.viewport(0,0,100,100);
gl |> viewport(0,0,100,100);

2)如果一个数据可能为多个类型,则定义一个抽象类型和它与这“多个类型”之间相互转换的FFI，然后把该数据设为该抽象类型

如脚本->属性->value字段可以为int或者float类型，因此将value设为抽象类型，并且定义抽象类型和int、float类型之间的转换FFI。

示例代码如下：

type scriptAttributeType =
  | Int
  | Float;


//抽象类型
type scriptAttributeValue;

type scriptAttributeField = {
  type_: scriptAttributeType,
  //定义value字段为该抽象类型
  value: scriptAttributeValue
};

//定义抽象类型scriptAttributeValue和int,float类型相互转换的FFI

external intToScriptAttributeValue: int => scriptAttributeValue = "%identity";

external floatToScriptAttributeValue: float => scriptAttributeValue =
  "%identity";

external scriptAttributeValueToInt: scriptAttributeValue => int = "%identity";

external scriptAttributeValueToFloat: scriptAttributeValue => float =
  "%identity";
  
  
//client code

//创建scriptAttributeField，设置value的数据

let scriptAttributeField = {
    type_: Int,
    value:intToScriptAttributeValue(10) 
};



//修改scriptAttributeField->value

let newScriptAttributeField = {
    ...scriptAttributeField,
    value: (scriptAttributeValueToInt(scriptAttributeField.value) + 1) |> intToScriptAttributeValue
};

相关资料
抽象类型(Abstract Types)

过程

组合

介绍
多个函数可以组合起来，使前一个函数的返回值作为后一个函数的输入，从而对数据进行管道处理。

示例

let func1 = value => value1 + 1;

let func2 = value => value1 + 2;

//13
10 |> func1 |> func2;

在引擎中的应用

把多个函数组合成job，再把多个job组合成一个管道操作，处理每帧的逻辑。

我们从组合的角度来分析下引擎的结构：

job = 多个函数的组合

引擎＝初始化+主循环

//而初始化和主循环的每一帧，都是由多个job组合而成的管道操作：
初始化 = create_canvas |> create_gl |> ...

每一次循环 = tick |> dispose |> reallocate_cpu_memory |> update_transform |> ...

相关资料

第 5 章: 代码组合（compose）

迭代和递归

介绍

遍历操作可以分成两类：
迭代
递归

例如广度优先遍历是迭代操作，而深度优先遍历是递归操作

Reason支持用for、while循环实现迭代操作，用“rec”关键字定义递归函数。
Reason支持尾递归优化，可将其编译成迭代操作。所以我们应该在需要遍历很多次的地方，用尾递归进行遍历。

示例

//func1为尾递归函数
let rec func1 = (value, result) => {
    value > 3 ? result : func1(value + 1, result + value);
};

//0+1+2+3=6
func1(1, 0);

在引擎中的应用

几乎所有的遍历都是尾递归遍历（因为相对于迭代，代码更可读），只有在少数使用Mutable和少数性能热点的地方，使用迭代遍历

相关资料
什么是尾递归？
Reason->Recursive Functions
Reason->Imperative Loops

模式匹配

介绍
使用switch代替if/else来处理程序分支。

示例

let func1 = value => {
    switch(value){
        | 0 => 10 
        | _ => 100
    }
};

//10
func1(0);
//100
func1(2);

在引擎中的应用

主要用在下面三种场景：

1)取出容器的值

type a = 
    | A(int)
    | B(string);
    
let aValue = switch(a){
    | A(value) => value
    | B(value) => value
};

2)处理Option

let a = Some(1);

switch(a){
    | None => ...
    | Some(value) => ...
}

3)处理枚举类型

type a = 
    | A
    | B;
    
switch(a){
    | A => ...
    | B => ...
}

相关资料
Reason->Pattern Matching!
模式匹配

容器

介绍

为了领域建模，或者为了隔离副作用来保证纯函数，需要把值封装到容器中，使外界只能操作容器，不能直接操作值。

示例

1)领域建模示例

比如我们要开发一个图书管理系统，需要对“书”进行建模。
书有书号、页数这两个数据，有小说书、技术书两种类型。
建模为：

type bookId = int;

type pageNum = int;

//book为Discriminated Union Type
//book作为容器，定义了两个Union Type：Novel、Technology
type book = 
    | Novel(bookId, pageNum)
    | Technology(bookId, pageNum);
    

现在我们创建一本小说，一本技术书，以及它们的集合list：

let novel = Novel(0, 100);

let technology = Technology(1, 200);

let bookList = [
    novel,
    technology
];

对“书”这个容器进行操作：

let getPage = (book) => 
switch(book){
    | Novel(_, page) => page
    | Technology(_, page) => page
};


let setPage = (page, book) => 
switch(book){
    | Novel(bookId, _) => Novel(bookId, page)
    | Technology(bookId, _) => Technology(bookId, page)
};

//client code

//得到新的技术书，它的页数为集合中所有书的总页数
let newTechnology =
bookList
|> List.fold_left((totalPage, book) => totalPage + getPage(book), 0)
|> setPage(_, technology);

在引擎中的应用

包含以下使用场景：
1)领域建模
2)错误处理
3)处理空值
使用Option这个容器包装空值。

相关资料

Railway Oriented Programming
The "Map and Bind and Apply, Oh my!" series
强大的容器
Monad
Applicative Functor

多态

GADT

介绍
全称为Generalized algebraic data type，可以用来实现函数参数多态。

示例
重构前，需要定义多个isXXXEqual函数来处理每种类型：

let isIntEqual = (source: int, target: int) => source == target;

let isStringEqual = (source: string, target: string) => source == target;
  
//true
isIntEqual(1, 1);

//true
isStringEqual("aaa", "aaa");

使用GADT重构后，只需要一个isEqual函数来处理所有的类型：

type isEqual(_) =
  | Int: isEqual(int)
  | Float: isEqual(float)
  | String: isEqual(string);

let isEqual = (type g, kind: isEqual(g), source: g, target: g) =>
  switch (kind) {
  | _ => source == target
  };

//true
isEqual(Int, 1, 1);

//true
isEqual(String, "aaa", "aaa");

在引擎中的应用

包含以下使用场景：
1)契约检查
使用GADT定义一个assertEqual方法来判断两个任意类型的变量是否相等，从而不需要assertStringEqual,assertIntEqual等方法。

相关资料
Why GADTs matter for performance（需要FQ）
维基百科->Generalized algebraic data type

Module Functor

介绍

module作为参数，传递给functor，得到一个新的module。

它类似于面向对象的“继承”，可以通过函子functor，在基module上扩展出新的module。

示例

module type Comparable = {
  type t;

  let equal: (t, t) => bool;
};

//module functor
module MakeAdd = (Item: Comparable) => {
  let add = (x: Item.t, newItem: Item.t, list: list(Item.t)) =>
    Item.equal(x, newItem) ? list : [newItem, ...list];
};


module A = {
  type t = int;
  let equal = (x1, x2) => x1 == x2;
};

//module B增加了add函数，该方法调用了A.equal函数
module B = MakeAdd(A);

//list == [2]
let list = B.add(1, 2, []);    
//list == [2]
let list = list |> B.add(1, 1);

在引擎中的应用

包含以下使用场景：
1)错误处理
错误信息被包装到容器Result中。
由于错误的类型不一样，所以需要不同数据结构的容器（RelationResult、SameDataResult）来包装。
这两类容器有共同的模式，可以通过“Module Functor”来消除重复：
提出基module：Result;
增加MakeRelationResult、MakeSameDataResult这两个module functor，它们将Result作为参数，返回新的module：RelationResult、SameDataResult。

相关资料
Reason->Module Functions

参考资料

用函数式编程，从0开发3D引擎和编辑器（二）：函数式编程准备