计算机相关

谈谈我认识的函数式编程

在谈论函数式编程前,我想先聊聊编程的本质。

在我看来编程是指使用计算机解决某个或某类问题的实践过程。

这里面涉及人和机两个概念。人编写程序,计算机执行程序。懂得计算机原理的人应该都知道计算机底层只能表达 0 和 1 两种值而已。而程序却能描绘世间万物。如何把世间万物映射为0/1,亦或者如何使用 0/1 来描述世间万物,这就是编程。

编程是通过什么手段做到呢,答案是抽象

什么是抽象呢,这里引用下 SICP 的描述:

  1. 将若干简单认识组合成一个复杂认识,由此产生出各种复杂的认识
  2. 将两个认识放在一起对照,由此得到有关他们相互关系的认识
  3. 将有关认识与所有其他认识隔离开,这就是抽象

该描述本身就很抽象,我们可以举例具体说明下。

比如我们对狗的认识可以这么描述:

class Dog {
    speak() {
        console.log('wang wang')
    }
    breath() {
        console.log('hu hu')
    }
}

而对猫的认识则可以这么描述:

class Cat {
    speak() {
        console.log('miao miao')
    }
    breath() {
        console.log('si si')
    }
}

我们还认识树:

class Tree {
    breath() {
        console.log('fu fu')
    }
}

我们把 Dog 和 Cat 放到一起对照,发现他们都能 speak。 由此我们得知 Dog 和 Cat 冥冥中有种关系使得彼此关联。

同时我们把 Tree 也加进来,发现 Dog 和 Cat 所具有的这种关系(都可以 speak ),是 Tree 不具有的。由此我们可以抽象出一种新的认识:Animal,而 Animal 则应该可以包含 Dog 和 Cat:

class Animal {
    speak() {}
}

class Dog extends Animal {}
class Cat extends Animal {}

以此类推,我们还能发现 Dog,Cat,Tree 都可以 breath,于是我们就又能抽象出一种新的认识:Creature

class Creature {
    breath() {}
}

class Animal extends Creature {
    speak() {}
}

class Dog extends Animal {}
class Cat extends Animal {}

class Tree extends Creature {}

有心人可能突然发现,欸?这不是用的面向对象里的继承的思想吗?

没错,面向对象的继承正是实现抽象的手段之一,另外值得注意的是,面向对象本身这个大概念都只是实现抽象的手段之一而已。除了面向对象之外,还有其他手段实现抽象吗?答案是肯定的,那就是函数式。

函数式编程的概念由来已久,但时至今日方才渐渐被工业界广泛接受,甚至是追捧。

函数式和面向对象的区别是啥? 在我看来其最大的区别就是:面向对象早已被业界广泛采用并得到长久的发展,时至今日即使与逐渐兴起的函数式相比也是不落下风,甚至还有点小小的优势。

但俗话说一山不容二虎,函数式和面向对象到底谁才能打败对方成为最后的王者呢?我们在项目中又该如何抉择呢?

拜托,这是小孩子才有的思维,成年人当然是全要了。

二者本质上都是为了抽象,只是使用了两种不同的思路解决相同的问题罢了,而具体哪个好当然要具体问题具体分析了,只要明确了要解决的问题的特点,并且对函数式和面向对象的异同了然于胸,自然就会做出合理的选择。

函数式到底是啥呢?

在给出我对函数式的理解之前,我想先回顾下面向对象的定义,如果能有面向对象来类比着理解函数式,相信会更好理解点。

面向对象是指把对象和类作为组织代码的基本单元,那类比着,函数式则是指把函数作为组织代码的基本单元。

这么说貌似有些笼统了,一般来说并不是所有以对象和类作为组织代码的基本单元就能称之为面向对象了,必须还同时使用了封装,继承,多态三大特性。同样的,如果你的代码都是使用函数组织的,也不能就称之为函数式编程了,必须还具备一些函数式所特有的特性才行。具体是哪些特性,且听我一一道来。

我们上文曾提过,计算机内部都是 0/1 串,为了能够更好的抽象,编程语言一般都会有类型的概念。某种 0/1 串表示的是 number,而另一种 0/1 串则代表着 string。

请注意,类型这个概念则是我们一切编程的基础,也是我们对计算机的第一个抽象。(特指编程语言,忽略硬件抽象)

以 js 为例,我们知道 js 包含 number,string,boolean,undefined,null,object,symbol,bigint 等基础类型。

这些我们都能理解,这里需要着重说的是 Function 这个类型,在 js 里 Fucntion 是属于 object 的范畴的,但本身的确也算一种细化的类型。

在讨论函数式时,函数其实算作一种特殊的类型,它是一个类型的同时,也是一个类型构造器。

我们以 js 为例:

function id(a) {
    return a
}

对于 id 来说它的类型是:

id :: a -> a

用大白话来说,就是给 id 任意类型的输入,都会输出相同类型的值

再来看个稍微复杂点的类型:

function C(a) {
    if (!(this instanceof C)) {
        return new C(a)
    }
    this.value = a
}

C 其实在 js 里是一个构造函数, 而构造函数一般情况下需要使用 new 来构造, 我们在定义 C 时,使用了一个小技巧,判断 this 是否为 C 的实例, 不是的话就手动返回一个 new 构造的 C, 这样的话我们就可以通过 C('value') 达到 new C('value') 的效果。

这个函数的类型是:

C :: a -> C a

即输入任意类型,都会返回被 C 包裹的相应类型。

let a = C(1) // number -> C<number>
let b = C(false) // boolean -> C<boolean>
let c = C('')  // string -> C<string>

此处可以更明显的看出函数作为类型构造器的作用。

我们再来看一个稍微特殊点的函数:

// add :: (number, number)-> number
function add(a, b) {
    return a + b
}

这种函数需要一次性传入两个类型,才能返回结果,我们再来看看下面的这个函数:

// add :: number -> number -> number
function add(a) {
    return b => a + b
}

这个函数比较有意思,输入一个 number 类型后,返回的是另一个函数:number -> number, 只有给返回的函数再输入一个 number 类型,才能得到最终的 number 结果:

add(1)(2) // 3

这种函数,被称之为柯里化函数。我们可以简单实现一个把任意多参数的函数转换成柯里化函数的工具函数:

function curry(fn) {
    return (...args) => _curry(fn, ...args)
}
function _curry(fn, ...args) {
    if (args.length >= fn.length) {
        return fn(...args)
    } else {
        return (...restArgs) => _curry(fn, ...args, ...restArgs)
    }
}

function add(a, b, c) {
    return a + b + c
}
const $add = curry(add)
$add(1, 2, 3) // 6
$add(1, 2)(3) // 6
$add(1)(2)(3) // 6

柯里化函数是函数式编程里的一个重要概念。

你可能会很奇怪,curry 看似很牛逼,实际上并没有啥卵用吧,谁会闲着没事把参数拆开传呢?

别急,好戏还在后头。

curry 搭配干活的是一个叫做 compose 的工具函数。compose 的作用是把形如:d => a(b(c(d))) 这样的函数转变成: d => compose(a, b, c)(d) 的调用形式。

这里值得注意的是,a/b/c 三个函数都是接收一个参数并且返回一个参数的函数。

下面我们来看下 compose 的实现:

function pipe(...fns) {
    return (...args) => {
        return fns.slice(1).reduce((prev, curr) => curr(prev), fns[0](...args))
    }
}
function compose(...fns) {
    return pipe(...fns.reverse())
}

有了 compose 我们就能这么操作:

const add = curry((a, b) => a + b)
const multi = curry((a, b) => a * b)

const addAndMulti = compose(multi(2), add(1))
addAndMulti(1) // 4

上面使用 compose 时,是从右往左算的,也就是 先 add(1)multi(2),这与我们从左往右的思维是相背的,因此我们还可以使用 pipe 函数实现从左往右的调用顺序(之所以起名为 pipe 是因为,这样数据就会像流水一样从管道左侧流向右侧):

const addAndMulti = pipe(add(1), multi(2))

此时是不是有点明白 curyy 的作用了呢,它可以把多参数的函数转成单参数的函数。而 compose 则可以很方便的复用这些单参数函数,组合成各种不同的函数。

目前为止我们已经实现了很多的函数,但我们好像还没有仔细的想过函数的本质是什么?在我看来,在类型系统中,函数本身是一种类型,所以它可以当作参数传递给其他函数,也可以当作结果返回。同时函数又是一个类型构造器,它可以把一种类型映射成另一种类型。对于多参数的函数来说,我们可以把它柯里化,这样就变成单参数函数。

接下来我们再来看一个例子,我们首先定义一个 map 函数:

// map :: (a -> b) -> [a] -> [b]
function map(fn, list) {
    return list.map(fn)
}

map 函数接受两个类型,第一个是函数 a -> b: 能够把类型 a 映射成 类型 b 的函数;第二个是一个包含 a 类型元素的数组。而输出则是经过第一个函数映射后的新数组 [b]

这个函数貌似也没啥特殊的地方,而且内部实现也是相当简略,还不如直接调用岂不更简单,为啥还要非套一层函数呢?

别急,下面就是见证奇迹的时刻:

我们先用之前的 curry 函数把 map 柯里化一下,并引入 add 函数

const map = curry((fn, list) => list.map(fn))
const add = curry((a, b) => a + b)

现在,假设我们需要实现一个函数,该函数输入一个数组,把数组中每个值都 +1 之后再返回。

此时我们就可以这么实现:

const mapAdd = map(add(1))

mapAdd([1, 2, 3]) // [2, 3, 4]

还是继续上面的例子,这次我们不但要 +1 还要把数组反转。

const reverse = arr => arr.reverse()
const reverseMapAdd = arr => reverse( map(add(1))(arr) )

我们发现在定义 reverseMapAdd 时,必须要声明参数 arr,而定义 mapAdd 时却不需要声明参数。其实 mapAdd 的完整定义应该是这样的:

const mapAdd = arr => map(add(1))(arr)

如果我们把 map(add(1)) 单独抽出来:

const _mapAdd = map(add(1))
const mapAdd = arr => _mapAdd(arr)

我们不难发现,mapAdd 其实就是 _mapAdd 本身,我们在定义 mapAdd 时根本不需要声明参数。

这种形式的函数被称为是 pointfree 的(point 即代表参数的意思),不引入参数可以使得函数更简洁明了。

这时候我们再来看下 reverseMapAdd 能不能定义成符合 pointfree 的呢?答案当然是可以的,那就是用上我们刚认识的 compose 函数:

const reverseMapAdd = compose(reverse, map(add(1)))

大家在仔细观察这个 map 函数,会发现一个很特殊的地方,那就是他的第一个参数是函数,第二个参数是数组。按照正常的思维方式,我们会把这两个参数位置换一下:

const map = function(list, fn) {
    return list.map(fn)
}

因为我们在面向对象的范式中,常规的调用方式就是 对象.方法,在面向对象的思维里,一定是先有对象,才有对象的方法调用,也就是说方法是属于对象的。 那是因为面向对象是以对象为抽象的基本单位的,所有的抽象关系都是建立在对象(类)之上,方法不过是对象所特有的行为而已。 面向对象的抽象过程就是先有各种各样的对象,然后把具有相同行为的对象归为一类,抽象出类的概念。而类与类之间则又把相似性抽象为接口或继承等关系。

但是在函数式的范式中,函数才是抽象的基本单位。函数本身是有类型的,函数类型由入参类型和出参类型共同决定,而如果函数 a 的出参类型和函数 b 的入参类型一致, 那么函数 a 和 函数 b 则是可组合的(compose)。函数式的抽象过程就是抽象出函数的组合方式。我们刚学习的 compose 就算是最基础的组合方式了。

也因此,函数式在抽象的过程中只关心函数而不在乎具体的数据,所以这也是为什么在函数式中定义的 map 函数会把函数当作第一参数,而数据放到最后了。这种定义函数的方式是函数式编程的一大特点。

给大家举了 map 的例子其实并不仅仅是为了阐述函数参数的定义习惯问题,这里面其实还隐藏着一个惊天大秘密,那就是函数式编程里大名顶顶的 functor

functor 中文翻译为函子,咋一听好像和函数有关系,其实他们的关系跟 Java 和 JavaScript 的关系差不多。

functor 是一个特殊的计算结构,你可以把它理解成一个盒子,这个盒子有一个任意类型的值,同时这个盒子还提供了如何把这个值映射成其他值的方法。

数组就算作是一个 functor,数组本身是一个盒子,数组里含有一个元组值(可以把数组[1,2,3]理解成[(1,2,3)]),同时数组还提供了一个 map 方法可以把内部的值映射成其他值。

我们可以定义一个更加通用的 functor

function Box(value) {
    if (!(value instanceof Box)) {
        return new Box(value)
    }
    this.value = value
}
Box.prototype.map = function(f) {
    return Box(f(this.value))
}

Box 可以理解为一个盒子,这个盒子内部保存一个值 value,同时这个盒子提供了 map 方法把盒子内部的值映射成其他值。因此 Box 就是一个标准的 functor

而其实我们之前定义的 map 函数的真正类型则是这样的:

// map :: Functor f => (a -> b) -> f a -> f b
function map(f, functor) {
    return functor.map(f)
}

// 下面是之前的定义
// map :: (a -> b) -> [a] -> [b]
function map(fn, list) {
    return list.map(fn)
}

函数本身的实现没有什么变化,但是函数的入参类型则从数组变成了更加通用的 functor,现在 map 的适用范围则更加广泛了。

只是一个 Box 还看不出 map 的威力,我们再来看看一个新的 functor

const Option = {
    Some(value) {
        if (!(value instanceof Option.Some)) {
            return new Option.Some(value)
        }
        this.value = value
    },
    None() {
        if (!(value instanceof Option.None)) {
            return new Option.None()
        }
        this.value = void 0
    },
}
Option.Some.prototype.map = function(f) {
    return Option.Some(f(this.value))
}
Option.None.prototype.map = function(f) {
    return this
}

Option 是一个特殊的 functor,因为它的值有两种可能,要么是 Some 要么是 NoneSomemapBox 一致,而 Nonemap 则什么也不做。这个 functor 的具体作用我们可以通过一个例子看下:

const {Some, None} = Option

const handler = map(add(1))

handler(Some(1)) // Some(2)
handler(None())  // None()

我们看到,handler 在接收一个 Some 时,会正常处理 add(1) 的逻辑,所以最后返回 Some(2); 而在接收一个 None 时,则什么也不做,继续返回 None

如果使用面向过程的编码方式则大致等价于:

function add(a, b) {
    return a + b
}
function handler(value) {
    if (value !== undefined) {
        return add(1, value)
    } else {
        return undefined
    }
}
handler(1) // 2
handler()  // undefined

我们看到 Option 这个 functor 完美的把条件判断的逻辑封装起来,我们在调用 map 的过程中完全不需要考虑错误的情况如何处理,因为 mapOption 已经帮你处理好了。 更有意思的是,即使是多次联合操作也完全没问题。

const init = v => v >= 0 ? Some(v) : None()
const handler = compose(map(add(1)), map(add(1)), map(add(1)), init)
handler(1)  // Some(4)
handler(-1) // None()

Option 可以处理两种情况,而对第二种情况(None)则是直接忽略。但有些时候我们希望第二种情况也能带上某些信息,比如异常。

异常在编码的过程中是在所难免的,而一般编程语言都会提供 try-catch 等语法结构来捕获异常,在函数式编程的世界里则完全可以使用 functor 来处理。

const Result = {
    Ok() {
        if (!(value instanceof Result.Ok)) {
            return new Result.Ok(value)
        }
        this.value = value
    }
    Err() {
        if (!(value instanceof Result.Err)) {
            return new Result.Err(value)
        }
        this.value = value
    }
}
Result.Ok.prototype.map = function(f) {
    return Result.Ok(f(this.value))
}
Result.Err.prototype.map = function(f) {
    return this
}

Reuslt 这个 functorOption 很像,不过它的第二种情况 Err 会保存错误信息。

const {Ok, Err} = Result
const init = function(v) {
    if (v >= 0) {
        return Ok(v)
    } else {
        return Err('必须大于 0')
    }
}
const handler = compose(map(add(1)), map(add(1)), map(add(1)), init)
handler(1)  // Ok(4)
handler(-1) // Err('必须大于 0')

还记得我们刚刚说的函数式的抽象过程就是抽象出函数的组合方式吗,我们看看上面的handler的定义中, 大家可以考虑下,为什么可以把众多的 map 放到一起 compose? 这是因为,map 函数保证了只要输入了一个 functor 就一定会返回一个 functor。 所以 map 算作是我们认识的第二个抽像组合方式(compose 是第一个)。

map 很强大,但是我们发现 map 并不能改变 functor 的子类型,比如 map Ok 就一定返回 Ok,map Some 也一定返回 Some,而有时候我们需要 map Ok 时能返回 Err,map Some 时能返回 None。 我们希望有一种模式可以自由操控具体的返回类型,如果有个这个函数的话,那么它的类型大概应该是这样的:

// unknown :: Functor f => (a -> f b) -> f a -> f b

我们再拿出 map 的定义看一下:

// map :: Functor f => (a -> b) -> f a -> f b

我们发现唯一的不同就是第一个参数类型,mapa -> b 而我们期望的那个函数则是 a -> f b,其实这个函数在函数式编程中早已有了一席之地,不过他的真正类型是这样的:

// chain :: Monad m => (a -> m b) -> m a -> m b
function chain(f, monad) {
    return monad.chain(f)
}

大家可能会一脸懵逼,这个传说中的函数和 map 的实现貌似差不多啊,而这个 monad 又是什么鬼,和 functor 有啥关系呢?

是的,chain 表示的只是一种概念,而真正的实现在 monadchain 方法里。正如同 map 也只是一个概念,不同的 functor 都会有自己的 map 实现一样。

而这个 monad 其实是和 functor 是一类的东西。它也是代表一个黑盒,内部也保存一个值,但是具有一个 chain 方法,可以把 自己映射成另一个 monad

我们之前介绍的 Option 其实也是一个 monad,它的完整定义如下:

const Option = {
    Some(value) {
        if (!(value instanceof Option.Some)) {
            return new Option.Some(value)
        }
        this.value = value
    },
    None() {
        if (!(value instanceof Option.None)) {
            return new Option.None()
        }
        this.value = void 0
    },
}
Option.Some.prototype.map = function(f) {
    return Option.Some(f(this.value))
}
Option.Some.prototype.chain = function(f) {
    return f(this.value)
}

Option.None.prototype.map = function(f) {
    return this
}
Option.None.prototype.chain = function(f) {
    return this
}

我们不难发现,Somemapchain 唯一的区别就是,map 把映射后的值再次放回 Some 中, 而 chain 却是直接返回映射后的值。

同样的 Result 其实也是 monad

const Result = {
    Ok() {
        if (!(value instanceof Result.Ok)) {
            return new Result.Ok(value)
        }
        this.value = value
    }
    Err() {
        if (!(value instanceof Result.Err)) {
            return new Result.Err(value)
        }
        this.value = value
    }
}
Result.Ok.prototype.map = function(f) {
    return Result.Ok(f(this.value))
}
Result.Ok.prototype.chain = function(f) {
    return f(this.value)
}
Result.Err.prototype.map = function(f) {
    return this
}
Result.Err.prototype.chain = function(f) {
    return this
}

我们将通过一个实际的例子展示 chain 的巨大威力:

假如我们要实现一个四则运算:

const lit = a => Ok(a)
const add = curry((a, b) => {
    return OK(a + b)
})
const sub = curry((a, b) => {
    return OK(a - b)
})
const mul = curry((a, b) => {
    return Ok(a * b)
})
const div = curry((a, b) => {
    if (b === 0) return Err('除数不能为 0')
    return Ok(a / b)
})

const expr = compose(chain(div(1)), chain(add(1)))(lit(1)) // Ok(2)
const expr2 = compose(chain(div(0)), chain(add(1)))(lit(1)) // Err('除数不能为 0')

我们发现,compose 可以完美的把 chain 串联起来,就和串联 map 一样,这是因为 chain 一定接收一个 monad 也一定会返回一个 monad。 其实我们也可以使用链式调用:

const expr = lit(1).chain(add(1)).chain(div(1)) // Ok(2)
const expr2 = lit(1).chain(add(1)).chain(div(0)) // Err('除数不能为 0')

即使是异步也不在话下:

const validate = curry(keyword => {
    if (!keyword) return Err('请输入关键词')
    else return Ok(keyword)
})
const query = curry(keyword => {
    return new Promise
})

假如我们要实现四则运算:

// 我们首先定义一下四则运算类型:
const Expr = {
    Lit(value) {
        if (!(value instanceof Expr.Lit)) {
            return new Expr.Lit(value)
        }
        this.value = value
    }
    Add(expr1, expr2) {
        if (!(value instanceof Expr.Lit)) {
            return new Expr.Add(value)
        }
        this.value = [expr1, expr2]
    }
    Sub(expr1, expr2) {
        if (!(value instanceof Expr.Lit)) {
            return new Expr.Sub(value)
        }
        this.value = [expr1, expr2]
    }
    Mul(expr1, expr2) {
        if (!(value instanceof Expr.Lit)) {
            return new Expr.Mul(value)
        }
        this.value = [expr1, expr2]
    }
    Div(expr1, expr2) {
        if (!(value instanceof Expr.Lit)) {
            return new Expr.Div(value)
        }
        this.value = [expr1, expr2]
    }
}
// 我们可以这样表达一个四则运算:
const {Lit, Add, Sub, Mul, Div} = Expr
const expr = Div(Lit(4), Lit(2)) // expr 即表示计算 4 / 2

// 下面我们要定义一个常规的 exec 函数来解析 expr
const exec = (expr) => {
    if (expr instanceof Lit) {
        return expr.value
    } else if (expr instanceof Add) {
        return exec(expr.value[0]) + exec(expr.value[1])
    } else if (expr instanceof Sub) {
        return exec(expr.value[0]) - exec(expr.value[1])
    } else if (expr instanceof Mul) {
        return exec(expr.value[0]) * exec(expr.value[1])
    } else if (expr instanceof Div) {
        return exec(expr.value[0]) / exec(expr.value[1])
    }
}

exec(expr) // 2

// 上面的 exec 即是我们使用面向过程的方式来定义的,看似好像也是很简洁的
// 但是我们忽略一个问题,那就是被除数不能为 0。我们需要额外处理这个异常
// 所以要定义一个安全版本的 exec

const safeExec = (expr) => {
    if (expr instanceof Lit) {
        return expr.value
    } else if (expr instanceof Add) {
        return safeExec(expr.value[0]) + safeExec(expr.value[1])
    } else if (expr instanceof Sub) {
        return safeExec(expr.value[0]) - safeExec(expr.value[1])
    } else if (expr instanceof Mul) {
        return safeExec(expr.value[0]) * safeExec(expr.value[1])
    } else if (expr instanceof Div) {
        if safeExec(expr.value[1] === 0) {
            throw new Error('除数不能为 0')
        } else {
            return safeExec(expr.value[0]) / safeExec(expr.value[1])
        }
    }
}

// 下面我们通过函数式的方式来定义:
const safeExec2 = (expr) => {
    if (expr instanceof Lit) {
        return Ok(expr.value)
    } else if (expr instanceof Add) {
        return chain(
            v1 => {
                chain(

                    safeExec2(expr.value[1])
                )
            }
            safeExec2(expr.value[0]),
        )
        return Ok(add)
            .ap(safeExec2(expr.value[0]))
            .ap(safeExec2(expr.value[1]))
    }
}

未完待续。。。

  • curry
  • compose
  • functor
  • monad
  • applicative

指针是类型还是地址

编程语言中的类型系统的本质是将现实中的数据进行有意义的分类,然后做映射。

比如现实中有整数也有浮点数,对应到类型系统就是 intfloat 等。

intfloat 等这些类型还有个共同特点——都是数值类型,数值类型的一个属性就是可以做四则运算,所以我们可以对同属 int 类型的变量 ab 做如下操作:a + b

我们还知道数据是存储在内存中的,而内存是有地址的。地址本质上其实就是一串数字,但是为了能够更好的区分存储了不同类型数据的地址,我们强行把地址进行了分类,即存储了整数的地址和存储了浮点数的地址,对应到类型系统就是 int*float* 等。

int*, float* 等这些类型还有个共同特点——都是指针类型,指针类型的一个属性就是可以使用间接运算符 * 获取其保存的地址所对应的数据(右值语义),所以我们可以对 int* 类型的变量 a 做如下操作:*a

从上述的对比来看,指针其实类比着数值这个层次的概念。他本身是更高层面的一种特质描述。

数值和数值类型的区别是数值是一种更笼统的描述,它描述的是一种特质(可运算的东西),而数值类型就是类型系统中int,float 等类型的统称。

指针和指针类型的区别就是指针是一种更笼统的描述,它描述的是一种特质(可间接获取值的东西),而指针类型是类型系统中int *,float*等类型的统称。

而地址则只和指针类型有关系,即类型系统中的指针类型映射的是现实世界中的地址(语义上)。

总结就是,狭义上指针和指针类型其实是不同层次的描述;广义上指针可以是指针类型的简称(就好比数值和数值类型的关系,我们既可以说 1 是数值类型的数据,也可以说 1 是数值);而因为指针类型存储的就是(语义上的)地址,所以巨义上指针代表的也就是地址数据。

再总结就是,狭义上比起指针是地址,指针是类型更贴合一些;广义上只要理解了指针的本质,这些无非就是话术而已,不同的说法适用于不同的语境。

二叉树前中后序遍历的非递归实现

递归改非递归一般都会用到栈这个结构,栈的特点就是先进后出,所以说栈其实是维护了一个特定顺序的结构。

我们先定义这么一种操作:

左遍历:指从给定节点开始无限遍历其左子节点直到叶子节点为止,并将其依次压入栈中。(这样在栈中的节点就都满足一个性质:入栈时一定是先根后左,出栈时一定是先左后根)

function traversal(node) {
    const stack = []
    while(node) {
        console.log(node) // ------> @1
        stack.push(node)
        node = node.left
    }
    while(stack.length) {
        node = stack.pop()
        console.log(node) // ------> @2
    }
}

如果我们在入栈的时候访问节点(@1),则可以保证根->左的顺序

如果我们在出栈的时候访问节点(@2),则可以保证左->根的顺序

这里大家肯定会问,这个只是从根节点开始的左子节点的顺序呀,如果有右子节点怎么办呢?

我们拿先序遍历举例说明:

先序遍历要求的顺序是 根->左->右 。由前面的讨论我们已经可以做到根->左的顺序访问了,即只要做到入栈时访问即可。

那么如果有右子节点该如何处理呢?右子节的入栈条件是什么呢?

要解决这个问题我们需要先定义好出栈的含义,首先我们可以明确的是,对于先序遍历来说,入栈时访问,因此按照我们之前的定义,根节点一定在左子节点前被访问, 而出栈的时机则是左遍历结束,因为此时对于栈顶节点来说:

  1. 该节点的根节点一定访问过了(入栈时)
  2. 该节点没有左子节点(根据左遍历的定义即可推出),或左子节点已经访问过了

而这不正是访问右子节点的前置条件吗?换句话说,直接对出栈节点的右子节点左遍历。

function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {         // -----> @1
            console.log(node) // 访问节点
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的根和左都可以保证已经访问过
            node = node.right // -----> @2
        }
    }
}

@1处的 while 循环是我们定义的 左遍历,而对右节点左遍历就是把当前 node 赋值为右子节点(@2),并跳到@1处开始右节点的左遍历

按照上述讨论我们再来分析下中序遍历

中序遍历要求的顺序是 左->根->右 。由前面的讨论我们已经可以做到左->根的顺序访问了,即只要做到出栈时访问即可。

我们通过入栈维护了根->左的存储顺序,而又通过出栈获取左->根的访问顺序。

此时出栈的时机也是左遍历结束,因为此时对于栈顶节点来说:

  1. 该节点左子节点一定访问过了
  2. 现在正好需要访问该节点,并对右子树进行左遍历
function traversal(node) {
    const stack = []
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack.pop() // 此时的栈顶节点的左子树都已访问过
            console.log(node) // 访问节点
            node = node.right // 准备左遍历右子树
        }
    }
}

大家可能已经注意到,前序遍历和中序遍历的代码几乎一样,只是访问的时机不同。

最后我们再来看下后序遍历

相比于前序和中序,后序稍微复杂点。目前我们已经可以做到根->左或者左->根的访问顺序了, 但是后序遍历要求左->右->根,显然我们能够参考的是之前实现的左->根的定义,即出栈时访问。 但是后序遍历的右节点是介于左和根之间的, 这点则和中序遍历不同,因此对于出栈的处理也不同。 我们知道中序遍历中出栈的条件是左遍历结束。 但是后序遍历时,判断栈顶节点能否出栈除了左遍历结束还有两种情况需要考虑:

  1. 右子树还没有访问,需要先遍历右子树(不可以出栈);
  2. 右子树已经访问过了,可以访问该节点了(可以出栈)。

问题的关键就在于右子树有没有被访问过,因此我们需要定义一个变量保存上一个被访问的节点,以此来区分上述的两种情况。

function traversal(node) {
    const stack = []
    let lastVisit = null
    while (stack.length > 0 || node) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        if(stack.length) {
            node = stack[stack.length - 1] // 查看栈顶节点
            if (!node.right || node.right === lastVisit) { // 栈顶节点没有右子节点或右子节点已经访问过,则可以访问该节点
                node = stack.pop()
                console.log(node) // 访问节点
                lastVisit = node // 更新最新访问节点
                node = null // node 置空跳过while循环,再次处理栈
            } else {
                node = node.right // 栈顶节点的右子树没有遍历,则开始遍历右子树
            }
        }
    }
}

总结一下:

前序遍历:左遍历根节点,入栈时访问,出栈时左遍历右子节点

中序遍历:左遍历根节点,出栈时访问,出栈时左遍历右子节点

后序遍历:左遍历根节点,出栈时访问,记录上次访问的节点,出栈前判断上次访问节点是否为其右子节点,是则允许出栈,否则继续左遍历右子节点

\r 与 \n 的区别

我们都知道在 Linux 系统中使用 \n 表示下一行行首的位置,而在 Windows 中同样的含义却是使用 \r\n 表示,这是为什么呢?

\r 全称 Carriage Return,简称 CR,中文翻译回车,表示输入指针回到当前行行首(注意这里和我们平时认知中的回车含义不同)

\n 全称 Line Feed,简称 LF,中文翻译换行,表示输入指针换到下一行(不一定是下一行行首)

\r\n 其实就是表示两步操作,先回到行首,再往下移一行,最终的效果就是输入指针到了下一行行首。之所以这么设计,是有历史原因的,早期的打字机是机械式设备,对于可视字符由左向右依次打印,对于控制字符,则相应的做出调整。比如 \r 字符就是把打印指针移到最左侧,\n 字符就是把纸张上移一行(其实也就相当于把打印指针下移一行),而这两个字符放到一起就实现了打印机开始在下一行打印的功能。

后来计算机发展起来了,但早期的存储资源很是稀缺,而使用两个字符表示换到下一行行首有点不划算,所以 Linux 系列的操作系统决定使用 \n 这一个字符来表示这一含义。而 Windows 则保留了传统的做法。

下面有个小例子来描述 \r 的效果:

fn main() {
	println!("abc\rcba"); // cba
}

因为 \r 表示回到当前行行首,所以后面的 cba 就覆盖了缓冲区中的 abc,最终的打印结果也是 cba

JavaScript 相关

JavaScript 中的编解码问题

JavaScript 提供了众多编解码方法,比如 escapeencodeURIbtoacharCodeAtcodePointAt 等等。今天我们就来详细的捋一捋这些方法的异同和使用场景。

说到编解码不得不提到大名顶顶的 UTF-8,这个想必每个前端都不会陌生,因为我们的 HTML 文件的 head 标签内第一行往往是这么写的:<meta charset="UTF-8">

这里就不详细讲解 UTF-8 的具体编码方式了,但为了方便讲解上面提到的几个方法,常见的几种编码方式之间的关系还是要简单的提一下的。

大家都知道,无论是文本,图片,视频还是可以执行的游戏在计算机看来都是由 01 组成的。在存储层面,计算机并不关心你是何种格式的文件,也不 care 你是用什么编码方式进行存储,所有格式的编码方式不过是人类为了方便统一协作而约定俗成罢了。

注意,上面提到了编码这个概念。计算机最小的存储单位是比特(bit),一个比特要么是 0,要么是 1。因为一个比特对于人类来说能表示的范围太小了,所以约定用 8 个比特来代表一个字节(byte)。计算机最早是美国人发明的,所以最早的编码方式 ASCII 也是根据英语量身定做的。早期的美国人只需要存储 a-zA-Z0-9 以及其他常见的标点符号,加起来都没超过 128 个,用一个字节表示(一个字节有 8 bit,存储的信息量是 2^8 = 256)绰绰有余。

后来随着互联网的发展,越来越多的国家参与进来,但如何编码这些国家的文字却是个大问题。因此各个国家都推出了自己的编码方案,比如中国的 GB2312GBK。显然这种方式严重影响了不同语种的人群的交流,于是全球为了统一编码共同制定了一个新的编码标准:UnicodeUnicode 收录了几乎所有已知的字符,为了保持兼容,前 256 个字符和 ASCII 表示的含义相同。

值得注意的是,Unicode 只是给字符分配了统一的编号而已,却没有规定如何存储这些编号,于是又衍生出了不同的编码方式,比较出名的有 UTF-8UTF-16UTF-32。这三种编码的细节就不在这里罗嗦了,想了解的可以直接查阅 WIKI。

不过不了解细节也没关系,需要知道的是:

  1. UTF-8 对一个字符编码时使用 1 - 4 个字节不等;
  2. UTF-16 对一个字符编码时使用 2 个或 4 个字节;
  3. UTF-32 对一个字符编码时使用 4 个字节(所以这种编码方式很少使用)。

总的而言,UTF-8 在存储空间上有不小的优势,因此被使用的越来越广泛(当然也不尽然,对于纯中文来说,UTF-16 也许会更好也说不准,但谁让计算机早期一直是欧美引领着呢,他们使用的字符用 UTF-8 效果更好)。

科普结束,下面进入正文。

JavaScript 中如何获取一个字符的 Unicode 码值?

在 ES6 之前我们只有一个方法那就是 String.prototype.charCodeAt,我们直接看下 MDN 是如何介绍这个方法的:

charCodeAt() 方法返回 0 到 65535 之间的整数,表示给定索引处的 UTF-16 代码单元

UTF-16 编码单元匹配能用一个 UTF-16 编码单元表示的 Unicode 码点。如果 Unicode 码点不能用一个 UTF-16 编码单元表示(因为它的值大于0xFFFF),则所返回的编码单元会是这个码点代理对的第一个编码单元) 。

有点懵,对不对。这个介绍确实让人一言难尽,听我白话文给你解释一下。

charCodeAt 返回给定索引处字符在 UTF-16 编码下的 Unicode 码值。为什么要说是在 UTF-16 编码下呢,为什么不直接说是 Unicode 码值呢。这是因为该函数只能返回 0 到 65535 之间的整数,而我们之前说过,UTF-16 使用 2 个或 4 个字节来编码字符,码值为 0 - 65535 之间的字符使用 UTF-16 编码正是使用 2 个字节的情况。换句话说凡是 Unicode 码值大于 65535 的字符,其 UTF-16 的编码必定使用 4 个字节,也就是说此时 charCodeAt 只能返回前两个字节,比如大家熟知的 emoji 表情:

'🀄'.charCodeAt() // 55356

而 🀄 真实的 Unicode 码值是:126980

大家可能又会有疑问了,那 charCodeAt 为啥不返回完整的 Unicode 码值呢,搞这一出是闹哪样?不是不想,而是没赶上。JavaScript 第一版被开发出来时还没有 UTF-16 编码,它使用的是一个叫做 UCS-2 的编码方式,这种编码方式就只能表示这么多的字符,并且在一段时间内 UCS-2 和 UTF-16 表示的是同一种编码,只是后来 UTF-16 又扩充了定义,成为了 UCS-2 的超集,才造成当下的尴尬局面。

好在,ES6 引进了新的方法能够获取完整的 Unicode 码值了,那就是 codePointAt

'🀄'.codePointAt() // 126980

示例代码都没有给方法传 index 参数,是因为不传参时,方法内部会默认当成传 0 处理。

JavaScript 中如何对 URL 进行编码

凡是使用 JavaScript 发送过异步请求的前端应该都知道需要对 URL 进行编码,也大概率都知道应该使用 encodeURI 或者 encodeURIComponent 来编码。这里我也不详细解释两者的区别了,我们来分析下为什么要对 URL 编码。

我们先来看下 URL 是如何定义的:

[协议类型]://[访问资源需要的凭证信息]@[服务器地址]:[端口号]/[资源层级UNIX文件路径][文件名]?[查询]#[片段ID]

对于一个合法的 URL, : / @ ? # = 等字符都是具有特定分隔符的作用,为了避免歧义,其他的填充片段理应进行编码。另外 URL 还规定其必须由可打印的 ASCII 字符构成。因此我们看到,encodeURI 对除了 ; , / ? : @ & = + $ A-Z a-z 0-9 - _ . ! ~ * ' ( ) # 之外的所有字符都会进行转义编码;而 encodeURIComponent 则对除了 A-Z a-z 0-9 - _ . ! ~ * ' ( ) 之外的所有字符进行转义编码。而编码的方式也很简单,那就是使用字符的 UTF-8 编码来表示。比如 的 UTF-8 使用 3 个字节表示 :0xE4 0xB8 0xAD,其对应的 URL 编码则为 %E4%B8%AD

JavaScript 中如何获取一个字符的 UTF-8 编码

我们刚刚提到,encodeURIComponent 会对字符进行 UTF-8 编码,但可惜不是所有字符。不过莫慌,JavaScript 提供了更加强大的编码方法:TextEncoder:

const encoder = new TextEncoder();
encoder.encode('中'); // Uint8Array(3) [228, 184, 173]

JavaScript 中如何进行 Base64 编码

这个就比较简单了: btoa。这个函数容易和对应的解码函数:atob 搞混,其实也不难记,这里的 b 代表 binary,a 代表 ASCII。我们的变量(JavaScript 字符串)在内存中都是二进制形式保存的,所以是 binary,而 Base64 都是可打印的 ASCII 字符。所以 btoa 就是编码,而 atob 则是解码。

JavaScript 中获取对象属性的若干方法比较

对象的属性有这么几种情况:

  1. 是否可枚举
  2. 是否是 Symbol
  3. 是否属于自身

所以一个对象的属性的性质有 2^3 = 8 种情况。下面我们就来做个小实验:

let sa = Symbol()
let _sa = Symbol()
let a = {a: true, [sa]: true} // a 是普通属性,sa 是 Symbol 属性,默认都是可枚举的
Object.defineProperty(a, '_a', { // _a 普通不可枚举属性
	enumerable: false,
	value: true
})
Object.defineProperty(a, _sa, { // _sa Symbol 不可枚举属性
	enumerable: false,
	value: true
})

let sb = Symbol()
let _sb = Symbol()
let b = Object.create(a) // a 在 b 的原型链上
b.b = true // b 是普通可枚举属性
b[sb] = true // sb 是 Symbol 可枚举属性
Object.defineProperty(b, '_b', { // _b 是普通不可枚举属性
	enumerable: false,
	value: true
})
Object.defineProperty(b, _sb, { // _sb 是 Symbol 不可枚举属性
	enumerable: false,
	value: true
})

对于 b 来说,一共有这么几种属性:

属性是否自身是否 Symbol是否可枚举
b
_b
sb
_sb
a
_a
sa
_sa

是否 b 自有属性就看属性名里是否有 b,是否 Symbol 就看属性名里是否有 s,是否可枚举就看属性名里的 _

for (let prop in b) console.log(prop) // b, a

Object.keys(b) // b

Object.getOwnPropertyNames(b) // b, _b

Object.getOwnPropertySymbols(b) // sb, _sb

Reflect.ownKeys(b) // b, _b, sb, _sb

由此我们可以看到:

  • for...in => 获取当前对象及其原型链上所有可枚举且非Symbol属性
  • Object.keys => 获取当前对象上所有可枚举且非Symbol属性
  • Object.getOwnPropertyNames => 获取当前对象上所有非Symbol属性
  • Object.getOwnPropertySymbols(b) => 获取当前对象上所有Symbol属性
  • Reflect.ownKeys => 获取当前对象所有属性

这么来看其实还是有点绕,我这里总结一下就是:

  1. 在 Symbol 出现以前,只有是否可枚举,以及是否原型链的区别。 而跟原型链相关的只有 for...in。其他的都是和自身属性相关。
  2. 而获取自身属性分为是否可枚举,因此有 Object.keys 获取可枚举的,Object.getOwnPropertyNames 获取所有的。
  3. 后面出了 Symbol 的概念,所以有了针对获取所有 Symbol 的方法就是:Object.getOwnPropertySymbols
  4. 这个时候如果想获取所有自身属性的时候,就比较麻烦,所以有了 Reflect.ownKeys

这里其实有个小问题,那就是我们无法区分 Symbol 是否可枚举。

我们可以通过 {Object.keys} / {Object.getOwnPropertyNames} - {Object.keys} 区分 可枚举普通属性/不可枚举普通属性

而对于Symbol属性,我们只能获取所有的,无法区分是否可枚举。

所以,js还提供了一个方法 obj.propertyIsEnumerable 来判断自有属性是否可枚举。

另外还有一个更强大的方法:Object.getOwnPropertyDescriptor 能够获取自有属性的相关描述,包括是否可枚举,是否可写,是否可配置等。

情景

  1. 获取对象自身可枚举非 Symbol 属性:
    Object.keys(b) // b
    
  2. 获取对象自身可枚举 Symbol 属性:
    // 方法 1
    Object.getOwnProerptySymbols(b).filter(prop => b.propertyIsEnumerable(prop)) // sb
    // 方法 2
    Object.getOwnProerptySymbols(b).filter(prop => Object.getOwnPropertyDescriptor(b, prop).enumerable) // sb
    
  3. 获取对象自身所有可枚举属性:
    Reflect.ownKeys(b).filter(prop => b.propertyIsEnumerable(prop)) // b, sb
    
  4. 获取对象自身所有属性
    Reflect.ownKeys(b) // b, sb, _b, _sb
    

总结

  • 考虑原型链时只要考虑 for...in, 否则
  • 和 Symbol 不相关时,只要考虑 Object.keys, Object.getOwnPropertyNames
  • 和 Symbol 相关时,只要考虑 Reflect.ownKeys, Object.getOwnPropertySymbols
  • 是否可枚举使用 obj.propertyIsEnumerableObject.getOwnPropertyDescriptor 来判断。

rust 相关

rust 实用工具手册

Vec -> Vec<&str>


#![allow(unused)]
fn main() {
let a = vec!["string".to_string()];
let b:Vec<&str> = a.iter().map(|s| &**s).collect();
let b:Vec<&str> = a.iter().map(std::ops::Deref::deref).collect();
let b:Vec<&str> = a.iter().map(|s| s as &str).collect();
let b:Vec<&str> = a.iter().map(|s| &s[..]).collect();
let b:Vec<&str> = a.iter().map(|s| { let s: &str = s; s }).collect();
let b:Vec<&str> = a.iter().map(|s| s.as_ref()).collect();
let b:Vec<&str> = a.iter().map(AsRef::as_ref).collect();
let b:Vec<&str> = a.iter().map(String::as_str).collect();
assert_eq(vec!["string"], b);
}

Option::map vs Option::and_then


#![allow(unused)]
fn main() {
/// map      把 Some(T) 映射成 Some(U)
/// and_then 把 Some(T) 映射成 Option(U)
/// 也就是说,and_then 是 map 的超集

pub fn map<U, F>(self, f: F) -> Option<U> 
where 
	F: FnOnce(T) -> U

pub fn and_then<U, F>(self, f: F) -> Option<U> 
where 
	F: FnOnce(T) -> Option<U>, 

// 下述例子使用 and_then 实现 map
fn mapper(s: &str) -> i32 {
	s.parse().unwrap()
}
let v = Some("1");
let v2 = v.map(|s| mapper(s));
let v3 = v.and_then(|s| Some(mapper(s)));
asset_eq!(v2, v3);
}

&String vs &str


#![allow(unused)]
fn main() {
use std::mem::size_of;
size_of::<&String>(); // 8
size_of::<&str>();    // 16
}

rust 中的 String 和 str

str 在 rust 中是一个比较特殊的类型,因为一般来说类型都会有个固定的大小,比如 u8 是 1 个字节,i32 是 4 个字节,usize 在 64 位系统上是 8 个字节。但是 str 却没有固定的大小,更准确的说在编译期 str 没有固定的大小。

为什么强调是编译期,因为在运行期 str 是有大小的,而且一般情况下 str 的大小是不变的。这听着有点绕,怎么一会儿没有固定大小,一会儿又有固定大小的。

其实很好理解,运行期所有的东西都会从各种抽象映射成一个个字节按照约定排列在内存中,在任意时刻都可以计算出任意类型或变量的大小。因此当我们说某个类型的大小是否确定时,所隐含的前置条件就是特指编译期。

那么问题来了,编译期的类型为什么会有有无固定大小之分呢?其实搞明白这点才能真正理解 str 到底是什么,以及 str&str, String 等的区别。

正如文章开始所举的例子所示,类型一般都有大小,而类型之所以会有大小是因为这方便编译器在编译的时候就能确定某个函数栈帧所需要的最大空间是多少,相当于把计算栈帧大小的工作在编译期就处理掉了,极大的提高了程序的执行效率。

那为什么又会有动态大小类型(DST)的 str 呢?我们都知道 i32 是一个 4 字节大小的类型,在栈中它的值由 4 个连续的字节构成,而 String 是一个指针,在栈中它的值由 24 个连续的字节构成(我们会在后文详细探讨),那 str 又是什么呢,它在栈中或是堆中又是以什么样的姿态所存在的呢,这困扰了我很久。凡是入门过 rust 的一般都知道我们在实际写代码时几乎用不到 str,用的最多的是 &str。有段时间我就一直在想,既然如此,为什么就不能将我们现在理解的 &str 当成是 str 呢,为什么非要整出一个 str 这层抽象出来呢?

首先,str 不是 rust 中唯一的 DST,除此之外还有 dyn Trait[T] 等。dyn Trait 相对比较复杂我们暂且不谈,这个 [T] 在我看来和 str 比较相似。[T] 表示的是一段 T 类型的序列,具体长度不知(可以对比数组的定义看下,数组 [T; 2] 表示的是 2 个 T 组成的序列)。而 str 其实和 [u8] 比较相似,因为 str 本质也是表示一段 u8 序列,只是附带了额外的要求,那就是这些 u8 序列必须是合法的 utf-8 编码的字节序列。抛开这个限制不谈,str 本质上其实就是 [u8]

另外考虑到不定长这个概念,我们就会想到 Vec。从系统编程角度来看,Vec 本质是一个指针,所以 Vec 变量是定长的,可以在栈上存储;但是从业务角度来看,Vec 表示一组可变长度的具有相同类型的数据序列。其实现的原理也很简单,那就是栈上存指针 pointer 和长度信息 len,pointer 指向堆内的某个位置,此时该 Vec 就表示从堆内 pointer 位置开始取 len 长度的字节所构成的数据序列。

我们都知道,类型在运行时可以映射为内存中的某一个或一段字节序列,比如 u8 可以映射为内存中的 1 个字节, Vec 则可以映射为内存中的 24 个字节,但是且慢,如果 Vec 只是单纯的映射为内存中的 24 个字节,那它指向堆中的那一段字节序列又算什么呢?该用什么类型来描述这段字节序列呢?

答案就是 [T]

对比来看,u8 可以映射为内存中的 1 个字节; i32 可以映射为内存中的 4 个字节; Vec 可以映射为内存中的 24 个字节; [T] 可以映射为内存中不定长度的可以组成若干个 T 类型数据的字节; [u8] 可以映射为内存中不定长度的可以组成若干个 u8 类型数据的字节; str 可以映射为内存中不定长度的可以组成若干个 utf-8 编码字符的字节。

所以相比于 String 这个指针类型来说,str 才是更基本的字符串类型。这也是为什么官网是这么介绍 str 的:

The str type, also called a ‘string slice’, is the most primitive string type. It is usually seen in its borrowed form, &str. It is also the type of string literals, &'static str.

str 类型,也称为字符串切片,是最基本的字符串类型。它通常以借来的形式出现。它也是字符串字面值的类型, &'static str

&str 从形式上看表示的是引用的概念,但却不同于一般的引用。像 &String, &u8, &i32 这些也都是引用,它们的大小都是 8 个字节(64位系统),代表实际数据所在的内存地址。而 &str 却是 16 个字节,除了 8 个字节代表其指向的第一个字节的地址之外,还有 8 个字节代表其所涵盖的字节长度(所以 &str 又被称为胖指针,rust 中引用也是指针的一种)。

说完 str 我们再来聊聊 String

我们在前文说过 String 的大小是 24 个字节,大家可能会有疑问,String 不是可以动态改变大小的吗,怎么会是 24 个字节呢。那是因为 String 在 rust 中本质上是一个智能指针,而指针当然是有固定大小的了,为什么是 24 个字节呢?我们可以看下 String 的定义:


#![allow(unused)]
fn main() {
pub struct String {
    vec: Vec<u8>,
}

pub struct Vec<T, A: Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec<T, A: Allocator = Global> {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

pub struct Unique<T: ?Sized> {
    pointer: *const T,
    _marker: PhantomData<T>,
}

pub struct Global;
pub struct PhantomData<T: ?Sized>;
}

我们不难看出,在 64 位系统中:

sizeof(String) 
	= sizeof(Vec<u8>)
	= sizeof(RawVec<u8, Global>) + sizeof(usize)
	= sizeof(Unique<u8>) + sizeof(usize) + sizeof(Global) + 8 Bytes
	= sizeof(*const u8) + sizeof(PhantomData<u8>) + 8 Bytes + sizeof(Global) + 8 Bytes
	= 8 Bytes + 0 Bytes + 8 Bytes + 0 Bytes + 8 Bytes
	= 24 Bytes

除去零大小的 PhantomDataGlobal 之外,我们可以看出 String 本质上由三个类型构成:

  • len: usize -> 表示 String 所代表的字节序列长度
  • pointer: *const u8, -> 表示 String 所指向的堆内存地址
  • cap: usize -> 表示 String 的当前容量

总结一下:

  • str 表示一段合法的 utf-8 序列,String 表示存储在堆上的一段可以动态扩容和收缩的 utf-8 序列;
  • str 是动态大小类型,编译期无法确定大小,因此通常通过 &str 使用;
  • &str 16 (8 * 2) 字节大小,包含一个裸指针和一个长度;
  • String 24 (8 * 3) 字节大小,包含一个裸指针,一个长度和一个容量。
  • String&str 构成比较相似,String&str 多了一个容量的字段,也就拥有了自动缩扩容的能力,是一个智能指针。
  • String 拥有所指向字节的所有权,&str 则是对所指向字节的借用,一般需要配合生命周期一起使用。

Summary

TOML 简介

TOML 是什么

TOML 是由 GitHub 联合创始人 Tom Preston-Werner 等人设计的配置文件格式。

TOML 的目标

TOML的目标是成为一种最小的配置文件格式,由于明显的语义,该格式易于阅读。

TOML旨在明确地映射到哈希表。

TOML应该易于解析为多种语言的数据结构。

细则

  • TOML 是大小写敏感的
  • 一个 TOML 文件必须是合法的 utf-8 编码的 Unicode 文档
  • 制表符(Tab 0x09)和空格(Space 0x20)都代表空白
  • LF (0x0A) 或 CRLF (0x0D 0x0A) 代表换行

注释

# 不在字符串内时,处于其后的当前行内容将被当成注释

# 当前行都是注释
key = "value" # 这是一行结尾处的注释
another = "# 此处不是注释"

注释中不允许使用制表符以外的控制字符(U + 0000至U + 0008,U + 000A至U + 001F,U + 007F)。

一个键可以是不带引号的,带引号的或带点的。

裸键只能包含ASCII字母,ASCII数字,下划线和破折号(A-Za-z0-9_-)。 请注意,裸键只能由ASCII数字组成,例如 1234,但始终被解释为字符串。

key = "value"
bare_key = "value"
bare-key = "value"
1234 = "value"

带引号的键遵循与基本字符串或文字字符串完全相同的规则,并允许您使用更广泛的键名称集。 最佳实践是使用裸键,除非绝对必要。

"127.0.0.1" = "value"
"character encoding" = "value"
"ʎǝʞ" = "value"
'key2' = "value"
'quoted "value"' = "value"

带点键是一系列带有点的裸键或带引号的键。 这允许将相似的属性分组在一起。

name = "Orange"
physical.color = "orange"
physical.shape = "round"
site."google.com" = true

等价的 JSON 描述:

{
  "name": "Orange",
  "physical": {
    "color": "orange",
    "shape": "round"
  },
  "site": {
    "google.com": true
  }
}

TOML 里的值必须是下面中的一种:

键/值对之后必须有换行符(或EOF)(内联表除外)

String

有四种表达字符串的方式:基本,多行基本,文字和多行文字。 所有字符串只能包含有效的UTF-8字符。

基本字符串用引号 " 括起来。除必须转义的字符外,任何Unicode字符都可以使用:引号、反斜杠和tab以外的控制字符(U+0000到U+0008, U+000A到U+001F, U+007F)。

str = "I'm a string. \"You can quote me\". Name\tJos\u00E9\nLocation\tSF."

为了方便起见,一些流行的字符有一个紧凑的转义序列。

\b         - backspace       (U+0008)
\t         - tab             (U+0009)
\n         - linefeed        (U+000A)
\f         - form feed       (U+000C)
\r         - carriage return (U+000D)
\"         - quote           (U+0022)
\\         - backslash       (U+005C)
\uXXXX     - unicode         (U+XXXX)
\UXXXXXXXX - unicode         (U+XXXXXXXX)

多行基本字符串两边用三个引号括起来,允许换行。紧接在开始分隔符之后的换行符将被修剪。所有其他空格和换行符保持不变。

str1 = """
Roses are red
Violets are blue"""

如果要写长字符串而不引入多余的空格,可以使用“行尾反斜杠”。当一行中的最后一个非空格字符是一个未转义的\时,它将与所有的空格(包括换行符)一起被修剪,直到下一个非空格字符或结束分隔符。适用于基本字符串的所有转义序列也适用于多行基本字符串。

# The following strings are byte-for-byte equivalent:
str1 = "The quick brown fox jumps over the lazy dog."

str2 = """
The quick brown \


  fox jumps over \
    the lazy dog."""

str3 = """\
       The quick brown \
       fox jumps over \
       the lazy dog.\
       """

可以在多行基本字符串的任何位置写入一个引号或两个相邻的引号。它们也可以只写在分隔符内。

str4 = """Here are two quotation marks: "". Simple enough."""
# str5 = """Here are three quotation marks: """."""  # INVALID
str5 = """Here are three quotation marks: ""\"."""
str6 = """Here are fifteen quotation marks: ""\"""\"""\"""\"""\"."""

# "This," she said, "is just a pointless statement."
str7 = """"This," she said, "is just a pointless statement.""""

文字字符串用单引号括起来。像基本字符串一样,它们必须出现在一行中

# What you see is what you get.
winpath  = 'C:\Users\nodejs\templates'
winpath2 = '\\ServerX\admin$\system32\'
quoted   = 'Tom "Dubs" Preston-Werner'
regex    = '<\i\c*\s*>'

由于没有转义,所以无法在由单引号括起来的字符串中写入单引号。幸运的是,TOML支持文本字符串的多行版本,可以解决这个问题。

多行字面值字符串两边用三个单引号括起来,允许换行。像字面字符串一样,没有任何转义。紧接在开始分隔符之后的换行符将被修剪。分隔符之间的所有其他内容都按原样解释,不需要修改。

regex2 = '''I [dw]on't need \d{2} apples'''
lines  = '''
The first newline is
trimmed in raw strings.
   All other whitespace
   is preserved.
'''

你可以在多行文字字符串的任何地方写上1或2个单引号,但是不允许连续使用3个或更多的单引号。

quot15 = '''Here are fifteen quotation marks: """""""""""""""'''

# apos15 = '''Here are fifteen apostrophes: ''''''''''''''''''  # INVALID
apos15 = "Here are fifteen apostrophes: '''''''''''''''"

# 'That,' she said, 'is still pointless.'
str = ''''That,' she said, 'is still pointless.''''

在字面值字符串中不允许使用制表符以外的控制字符。因此,对于二进制数据,建议使用Base64或其他合适的ASCII或UTF-8编码。编码的处理将是特定于应用程序的。

Local Time

数组

数组由一对方括号包裹着一组元素组成。 元素用逗号分隔。 数组可以包含与键/值对相同的数据类型的值。 可以混合使用不同类型的值。

intergers = [1, 2, 3]
nested_arrays = [[1, 2], [3, 4]]
nested_mixed_array = [[1, 2], "1", "2"]

数组可以跨越多行。 在数组的最后一个值之后允许使用终止逗号(也称为尾随逗号)。 值,逗号和右括号之前可以有任意数量的换行符和注释。 数组值和逗号之间的缩进被视为空白并被忽略。

integers = [1, 2, 3]
integers2 = [
	1,
	2,
]

内联表

内联表为标准表提供了更紧凑的语法。 它们对于分组的数据特别有用,否则这些数据很快就会变得冗长。 内联表在花括号{}中定义。 在大括号内,可能会出现零个或多个逗号分隔的键/值对。 键/值对的形式与标准表中的键/值对相同。 允许所有值类型,包括内联表。

内联表旨在显示在一行上。 内联表中的最后一个键/值对之后不允许使用终止逗号(也称为尾随逗号)。 花括号之间不允许使用换行符,除非它们在一个值内有效。 即使这样,还是强烈建议不要将内联表拆分为多行。 如果您发现自己被这种欲望所困扰,则意味着您应该使用标准表。

a = { b = 1, c = 2 }

等价 TOML 描述:

[a]
b = 1
c = 2

等价 JSON 描述:

{
    "a": {
        "b": 1,
        "c": 2
    }
}

注意内联表是完整且独立的,意味着你不能在内联表外对内联表做任何补充定义

a = { b = 1}
a.c = 2 # 该行是不合法的

表(也称为哈希表或字典)是键/值对的集合。

表由表头和键值对构成

[table]
a = 1
b = 2

等价 JSON 描述:

{
     "table": {
         "a": 1,
         "b": 2
     }
}

注意 TOML 文件本身就是一个匿名表,因此可以直接书写键值对:

a = 1
b = 2

等价 JSON 描述:

{
    "a": 1,
    "b": 2
}

注意:一个表的范围从表头开始到下一个表头或是文件结尾结束

表头是可以嵌套的

[a.b.c]

等价 JSON 描述:

{
    "a": {
        "b": {
            "c": {
                
            }
        }
    }
}

注意:表可以没有键值对,就如同上一个例子所示

键也是可以嵌套的

[a."b.c"]
d.e = 1

等价 JSON 描述:

{
    "a": {
        "b.c": {
            "d": {
                "e": 1
            }
        }
    }
}

顶部匿名表也是一样的:

a.b.c = 1

等价 JSON 描述

{
    "a": {
        "b": {
            "c": 1
        }
    }
}

重复定义是不合法的

# 下面重复定义了 a 表,是不合法的
[a]
b = 1
[a]
c = 1
# 下面重复定义了同一个表的字段(a.b),是不合法的
[a]
b = 1
[a.b]
c = 1

表数组

表数组使用双中括号来表示。 该标头的第一个实例定义了数组及其第一个表元素,每个后续实例在该数组中创建并定义了一个新的表元素。 这些表按遇到的顺序插入到数组中。

[[a]]
b = 1
c = 2

[[a]]

[[a]]
b = 3
c = 4

等价 JSON 描述:

{
    "a": [
        { "b": 1, "c": 2 },
        {},
        { "b": 3, "c": 4 }
    ]
}

对表数组的任何引用都指向该数组的最近定义的表元素。 这使您可以在最新表内定义子表,甚至表的子数组。

[[a]]
b = 1

[a.c]
d = 2

[[a.e]]
f = 3

[[a.e]]
g = 4

[[a]]
b = 5

[[a.e]]
h = 5

等价 JSON 描述:

{
    "a": [
        { 
            "b": 1, 
            "c": {
                "d": 2
            }, 
            "e": [ 
                { "f": 3 }, 
                { "g": 4 } 
            ] 
        },
        { 
            "b": 5, 
            "e": [ 
                { "h": 5 } 
            ] 
        }
    ]
}

ABNF

;; This document describes TOML's syntax, using the ABNF format (defined in
;; RFC 5234 -- https://www.ietf.org/rfc/rfc5234.txt).
;;
;; All valid TOML documents will match this description, however certain
;; invalid documents would need to be rejected as per the semantics described
;; in the supporting text description.

;; It is possible to try this grammar interactively, using instaparse.
;;     http://instaparse.mojombo.com/
;;
;; To do so, in the lower right, click on Options and change `:input-format` to
;; ':abnf'. Then paste this entire ABNF document into the grammar entry box
;; (above the options). Then you can type or paste a sample TOML document into
;; the beige box on the left. Tada!

;; Overall Structure

toml = expression *( newline expression )

expression =  ws [ comment ]
expression =/ ws keyval ws [ comment ]
expression =/ ws table ws [ comment ]

;; Whitespace

ws = *wschar
wschar =  %x20  ; Space
wschar =/ %x09  ; Horizontal tab

;; Newline

newline =  %x0A     ; LF
newline =/ %x0D.0A  ; CRLF

;; Comment

comment-start-symbol = %x23 ; #
non-ascii = %x80-D7FF / %xE000-10FFFF
non-eol = %x09 / %x20-7F / non-ascii

comment = comment-start-symbol *non-eol

;; Key-Value pairs

keyval = key keyval-sep val

key = simple-key / dotted-key
simple-key = quoted-key / unquoted-key

unquoted-key = 1*( ALPHA / DIGIT / %x2D / %x5F ) ; A-Z / a-z / 0-9 / - / _
quoted-key = basic-string / literal-string
dotted-key = simple-key 1*( dot-sep simple-key )

dot-sep   = ws %x2E ws  ; . Period
keyval-sep = ws %x3D ws ; =

val = string / boolean / array / inline-table / date-time / float / integer

;; String

string = ml-basic-string / basic-string / ml-literal-string / literal-string

;; Basic String

basic-string = quotation-mark *basic-char quotation-mark

quotation-mark = %x22            ; "

basic-char = basic-unescaped / escaped
basic-unescaped = wschar / %x21 / %x23-5B / %x5D-7E / non-ascii
escaped = escape escape-seq-char

escape = %x5C                   ; \
escape-seq-char =  %x22         ; "    quotation mark  U+0022
escape-seq-char =/ %x5C         ; \    reverse solidus U+005C
escape-seq-char =/ %x62         ; b    backspace       U+0008
escape-seq-char =/ %x66         ; f    form feed       U+000C
escape-seq-char =/ %x6E         ; n    line feed       U+000A
escape-seq-char =/ %x72         ; r    carriage return U+000D
escape-seq-char =/ %x74         ; t    tab             U+0009
escape-seq-char =/ %x75 4HEXDIG ; uXXXX                U+XXXX
escape-seq-char =/ %x55 8HEXDIG ; UXXXXXXXX            U+XXXXXXXX

;; Multiline Basic String

ml-basic-string = ml-basic-string-delim [ newline ] ml-basic-body
                  ml-basic-string-delim
ml-basic-string-delim = 3quotation-mark
ml-basic-body = *mlb-content *( mlb-quotes 1*mlb-content ) [ mlb-quotes ]

mlb-content = mlb-char / newline / mlb-escaped-nl
mlb-char = mlb-unescaped / escaped
mlb-quotes = 1*2quotation-mark
mlb-unescaped = wschar / %x21 / %x23-5B / %x5D-7E / non-ascii
mlb-escaped-nl = escape ws newline *( wschar / newline )

;; Literal String

literal-string = apostrophe *literal-char apostrophe

apostrophe = %x27 ; ' apostrophe

literal-char = %x09 / %x20-26 / %x28-7E / non-ascii

;; Multiline Literal String

ml-literal-string = ml-literal-string-delim [ newline ] ml-literal-body
                    ml-literal-string-delim
ml-literal-string-delim = 3apostrophe
ml-literal-body = *mll-content *( mll-quotes 1*mll-content ) [ mll-quotes ]

mll-content = mll-char / newline
mll-char = %x09 / %x20-26 / %x28-7E / non-ascii
mll-quotes = 1*2apostrophe

;; Integer

integer = dec-int / hex-int / oct-int / bin-int

minus = %x2D                       ; -
plus = %x2B                        ; +
underscore = %x5F                  ; _
digit1-9 = %x31-39                 ; 1-9
digit0-7 = %x30-37                 ; 0-7
digit0-1 = %x30-31                 ; 0-1

hex-prefix = %x30.78               ; 0x
oct-prefix = %x30.6F               ; 0o
bin-prefix = %x30.62               ; 0b

dec-int = [ minus / plus ] unsigned-dec-int
unsigned-dec-int = DIGIT / digit1-9 1*( DIGIT / underscore DIGIT )

hex-int = hex-prefix HEXDIG *( HEXDIG / underscore HEXDIG )
oct-int = oct-prefix digit0-7 *( digit0-7 / underscore digit0-7 )
bin-int = bin-prefix digit0-1 *( digit0-1 / underscore digit0-1 )

;; Float

float = float-int-part ( exp / frac [ exp ] )
float =/ special-float

float-int-part = dec-int
frac = decimal-point zero-prefixable-int
decimal-point = %x2E               ; .
zero-prefixable-int = DIGIT *( DIGIT / underscore DIGIT )

exp = "e" float-exp-part
float-exp-part = [ minus / plus ] zero-prefixable-int

special-float = [ minus / plus ] ( inf / nan )
inf = %x69.6e.66  ; inf
nan = %x6e.61.6e  ; nan

;; Boolean

boolean = true / false

true    = %x74.72.75.65     ; true
false   = %x66.61.6C.73.65  ; false

;; Date and Time (as defined in RFC 3339)

date-time      = offset-date-time / local-date-time / local-date / local-time

date-fullyear  = 4DIGIT
date-month     = 2DIGIT  ; 01-12
date-mday      = 2DIGIT  ; 01-28, 01-29, 01-30, 01-31 based on month/year
time-delim     = "T" / %x20 ; T, t, or space
time-hour      = 2DIGIT  ; 00-23
time-minute    = 2DIGIT  ; 00-59
time-second    = 2DIGIT  ; 00-58, 00-59, 00-60 based on leap second rules
time-secfrac   = "." 1*DIGIT
time-numoffset = ( "+" / "-" ) time-hour ":" time-minute
time-offset    = "Z" / time-numoffset

partial-time   = time-hour ":" time-minute ":" time-second [ time-secfrac ]
full-date      = date-fullyear "-" date-month "-" date-mday
full-time      = partial-time time-offset

;; Offset Date-Time

offset-date-time = full-date time-delim full-time

;; Local Date-Time

local-date-time = full-date time-delim partial-time

;; Local Date

local-date = full-date

;; Local Time

local-time = partial-time

;; Array

array = array-open [ array-values ] ws-comment-newline array-close

array-open =  %x5B ; [
array-close = %x5D ; ]

array-values =  ws-comment-newline val ws-comment-newline array-sep array-values
array-values =/ ws-comment-newline val ws-comment-newline [ array-sep ]

array-sep = %x2C  ; , Comma

ws-comment-newline = *( wschar / [ comment ] newline )

;; Table

table = std-table / array-table

;; Standard Table

std-table = std-table-open key std-table-close

std-table-open  = %x5B ws     ; [ Left square bracket
std-table-close = ws %x5D     ; ] Right square bracket

;; Inline Table

inline-table = inline-table-open [ inline-table-keyvals ] inline-table-close

inline-table-open  = %x7B ws     ; {
inline-table-close = ws %x7D     ; }
inline-table-sep   = ws %x2C ws  ; , Comma

inline-table-keyvals = keyval [ inline-table-sep inline-table-keyvals ]

;; Array Table

array-table = array-table-open key array-table-close

array-table-open  = %x5B.5B ws  ; [[ Double left square bracket
array-table-close = ws %x5D.5D  ; ]] Double right square bracket

;; Built-in ABNF terms, reproduced here for clarity

ALPHA = %x41-5A / %x61-7A ; A-Z / a-z
DIGIT = %x30-39 ; 0-9
HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F"

FAQ

与 JSON 对比

JSON 的设计目标是通用的序列化格式,因此它要保证足够的简单(语法简单)和简洁(体积小)。简单用来简化编程语言实现,简洁用来增加传递信息的密度。因此当你的目标是序列化的话,JSON 是较好的选择。

TOML 的设计目标是易读的配置文件格式,因此它的首要任务是设计明显的语义以方便人类的阅读。所以相对 JSON 而言它的语法更加丰富,而为了更易读,也相应的增加了不少冗余的表达,因此体积相对较大。

使用 JSON 作为配置文件格式?

JSON 作为配置文件格式使用,有很多缺点陈列如下:

  1. JSON 不支持注释;
  2. 对于复杂的结构定义,JSON 不易读;(想象一个多层嵌套的对象,每个对象都有多个键值对,当一屏无法展示时,将很难确定某个键的绝对路径)
  3. 无法原生表达日期/时间;
  4. 不易表达多行字符;
  5. 无法表达十六进制数值;

注意: JSON5 扩充了 JSON 的功能,弥补了部分上述所述的缺陷。但需要引入额外解析包,并没有大范围推广开。

但是考虑到 JS 对 JSON 有内置的支持,所以对于 JS 项目来说,使用 JSON 作为配置文件也未尝不可,但对于其他项目来说使用 TOML 作为配置文件或许是更好的选择。

使用 TOML 作为序列化格式?

相信我,一般情况下这不是明智的选择。

TOML 可以无歧义的映射成几乎所有编程语言的数据结构,但编程语言的数据结构序列化成 TOML 时将会有多种表达方式;同时 TOML 人类易读的属性也导致了序列化的文件会相对较大(有冗余的表达),并不利于不同服务间的传递。

联系我

邮箱:me@ecma.cc

GitHub: github.com/lisiur