亲宝软件园·资讯

展开

从0开发3D引擎(五):函数式编程及其在引擎中的应用

Wonder-YYC 人气:1

目录

  • 上一篇博文
  • 函数式编程的优点与缺点
    • 优点
    • 缺点
  • 为什么使用Reason语言
  • 函数式编程学习资料
  • 引擎中相关的函数式编程知识点
    • 数据
      • 不可变数据
      • 可变数据
    • 函数
      • 纯函数
      • 高阶函数
      • 柯西化
    • 类型
      • 基本类型
      • Discriminated Union类型
      • 抽象类型
    • 过程
      • 组合
      • 迭代和递归
      • 模式匹配
    • 容器
    • 多态
      • GADT
      • Module Functor
  • 参考资料

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

上一篇博文

从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引擎和编辑器(二):函数式编程准备

加载全部内容

相关教程
猜你喜欢
用户评论