Abell Studio

这世界没有一件事情是虚空而生的。站在光里,背后就会有阴影,这深夜一片寂静,是因为你还没有听见声音。

CPU Cache与False Sharing

一、CPU 缓存架构

现代多核CPU会在每个核心上加上一个较小的SRAM高速缓存存储器称为:L1高速缓存,其中L1缓存由分为dcache数据缓存,icache指令缓存。在L1缓存的下级加一个较大的L2高速缓存, 然后会再L2之下加一个多核共享的L3高速缓存。它们之间的逻辑结构大概是这样的: image.png

相较于访问CPU高速缓存来说访问主存简直太慢了,Jeff Dean曾给出过这样一组数字:

  • L1缓存访问时间 0.5ns
  • 分支预测错误 5ns
  • L2缓存访问时间 7ns
  • 主存访问 100ns

https://colin-scott.github.io/personal_website/research/interactive_latency.html 给出了不同年份这些指标的数字,

1.1 通用的高速缓存存储器结构

告诉缓存被划分为S = 2 ^ s高速缓存组(cache set),每个组含有E个高速缓存行(cache line),每个行又由B = 2 ^ b个字节的数据块(block)和有一个标识该行是否有效(即是否已过期或者已修改)的有效位(valid bit),以及t标记位(tag bit)组成。物理结构大概是下图这样: image.png

高速缓存的大小指的是所有数据块的大小的和,即:B * E * S。

假设当前CPU地址总线有m位,从而主存有M=2^m个地址,所以每个内存地址会有m位。当CPU需要从主存加载地址为A的内存块上的字节时,会先从CPU高速缓存中获取,这时候问题来了,应该到高速缓存的什么位置去拿呢?实际上会将m位地址A划分为以下几段:

image.png

这里的m、t、b、s都是二进制数,不要想成十进制数哦

从而有m = t + b + s CPU会根据A地址中间的s位定位主存地址A映射到了哪个组中,然后根据开头的t位与组内的E个行的标记位挨个比对以确认地址A映射到了哪一行(这里有文章说是并行查询),这时会检查该行的有效位标识该行是否有效,如果有效的话最后根据后b位就直接定位主存地址A映射到了数据块中的哪个字节上了。如果通过以上的步骤没有找到对应的高速缓存地址的话,高速缓存会向主存请求包含A地址的数据块的一个拷贝,CPU必须等待,当被请求的块到达高速缓存中时高速缓存会将这个块放到对应的位置上,然后从数据块中抽取出A地址上的字节返回给CPU。注意:高速缓存从主存中一次请求的是一个数据块而非具体地址上的一个字节,这非常关键!

CSAPP书中提到了为什么选择中间位作为组索引位,其大概意思是选择中间位能够使连续内存映射到不同的组上,提高高速缓存利用率并且减小冲突覆盖的问题,但是个人感觉其解释是按照特定平台来描述的,并没有普适所有平台,这里就不以我昏昏使你昭昭了,待后续查阅更加合理的解释再说。

根据E的不同我们将高速缓存划分为以下三类:

  • 直接映射高速缓存
  • 组相连高速缓存
  • 全相连高速缓存

1.2 直接映射高速缓存

每组只有一行即E=1的高速缓存称为直接映射高速缓存。这种缓存一旦定位到了组后就无需查询对应行了。

1.2.1 直接映射高速缓存的冲突不命中

假设当前计算机b=16即数据块为16个字节,高速缓存中有两个组,s=5即内存地址的第5位决定内存地址映射到哪个组上,有下面的一段golang代码

func foo(x [8]int32, y [8]int32) int32 {
	var sum int32 = 0
	for i := 0; i < 8; i++ {
		sum += x[i] * y[i]
	}

	return sum
}

上面的程序中xy占用了8 * 4 = 2 ^ 5 = 32个字节,假设x被加载到地址为0-31的内存之中,y被加载到32-63之中,sum存在于寄存器中,不占用内存地址。如下图所示 image.png 运行时,第一次循环中,CPU需要先加载x[0],由于高速缓存中一开始并没有,所以会从主存中加载x[0]-x[3]共16个字节(数据块的大小)的数据到高速缓存的组0中再返回给CPU,接下来同样的道理会将y[0]-y[3]加载到高速缓存的组0中。这时候由于每组只有一个行就导致了上一步加载进来的x[0]-x[3]被覆盖了,下一次循环中要加载x[1]时,x[1]就不在高速缓存中了,所以又必须去内存中加载一次,结果从内存中加载会的数据又把第二次加载进来的y[0]-y[3]给覆盖了,之后的每次循环都存在这个问题,导致每次都回冲突不命中。这种高速缓存反复地加载和驱逐相同的高速缓存块的组的情况称为抖动(thrash)

为了解决这个问题我们可以将x和y两个数组的长度定为12,即:

func foo(x [12]int32, y [12]int32) int32

这样的话再看下分布情况: image.png

这样的话由于y[0]-y[3]与x[0]-x[3]不在一个组上就不会出现抖动问题了。

1.3 组相联高速缓存

组相联高速缓存每组中有多个行。

1.4 全相联高速缓存

全相联高速缓存只有一个组。

1.5 写的问题

如果CPU要写一个已经缓存了的字时,有两种方法将该数据写到下层缓存中: 1. 直写,最简单的一种方法,直接将数据写入到下层缓存。但是这种方案每次写都回引起总线流量 2. 写回,为每个行单独维护一个修改位dirty bit,标识这个缓存块被修改过,只有当替换算法要驱逐更新过的块时才将它写入到下一层缓存中。

写不命中通常有两种方法: 1. 写分配,加载低一层的缓存到高速缓存中,然后更新这个数据块。缺点是每次不命中都会导致一个块从低一层传送到高速缓存。 2. 非写分配,避开高速缓存,直接把这个数据写入到低一层中。

直写通常是非写分配的,写会通常是写分配的。

二、伪共享False Sharing

通过上文了解CPU的缓存结构后我们做一个实验来引出伪共享的问题,实验前我们先看下实验机器的一些信息。Mac上通过sysctl -a查看机器信息,这里我过滤了下只拿出来与此实验相关的一些机器指标:

hw.cachelinesize: 64 // Cacheline 64字节
hw.l1icachesize: 32768
hw.l1dcachesize: 32768 // L1数据缓存32K
hw.l2cachesize: 262144 // L2缓存256K
hw.l3cachesize: 6291456 // L3缓存6M
machdep.cpu.core_count: 4 // 4核
machdep.cpu.thread_count: 8

现在我们定义一个程序,有2个线程,两个变量a和b,线程1循环n次执行a++操作,线程2执行n次b++操作,我们用Go来描述:

type SimpleStruct struct {
	n int32
}

type PaddedStruct struct {
	n int32
	_ CacheLinePad
}

type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}

const CacheLinePadSize = 64

const Num = 10000000

func BenchmarkSimple(b *testing.B) {
	structA := SimpleStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() { // 为方便下文描述这个线程称为structA线程
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() { // 为方便下文描述这个线程称为structB线程
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

func BenchmarkSimplePad(b *testing.B) {
	structB := SimpleStruct{}
	structA := PaddedStruct{}
	wg := sync.WaitGroup{}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

运行benchmark go test -bench=. 得到以下结果 image.png 可以看到我们只在结构体中加入了一个64字节的元素性能就得到了极大的提高,这是为什么呢?

我们看下Simple这个函数的代码,假设structA线程运行在core1上,structB线程运行在core2s上,假设structA线程先执行,它会将structA这个变量与structB一起加载到core1的L1的同一cacheline中,structB线程也会将structA这个变量与structB一起加载到core2的L1的同一cacheline,structA线程修改了structA的值,它会将这个事件同步到core2上,导致core2上cacheline失效,这时就需要从低一层存储中加载最新数据,然后structB又修改了structB,又导致了cacheline失效,循环往复导致了运行效率极低。

而SimplePad这个函数中structA中加入了cachelinesize个字节,使得structA和structB处于不同的cacheline上,也就避免了上面的问题。

2.1 题外话

  1. 关于多核间同步缓存我没有查到特别好的文章,所以我就不妄加解释了,如果你想深入研究的话可以搜索这个关键词:MESI协议
  2. 上面的实验代码来自于【译】CPU 高速缓存原理和应用。最初在我在做这个实验时,写的实验代码是这样的:
var a int32
var pad [64]byte{}
var b int32
...

运行benchmark后发现运行时间并没有缩短,后来获取了a、pad、b的地址后才发现go将pad这个变量分配到了堆上,a和b两个变量在内存上还是紧挨着的,你做实验的话可以吸收这个经验:如果加上pad后发现运行时间没有缩短的话确认下a和b是不是真的被分隔到了两个cacheline上。

参考资料

阅读全文 »

理解内存对齐

相信大家都听说过内存对齐的概念,不过这里还是通过一个现象来引出本篇话题。

一、求一个结构体的size

猜下下面这个结构体会占用多少字节

type S struct {
    B byte  // Go中一个byte占1字节,int32占4个字节,int64占8个字节
    I64 int64
    I32 int32
}

是不是以为是1+8+4 = 13个字节?写段代码验证下:

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size:%d\n", unsafe.Sizeof(s))
}

输出:

s size:24

与预想显然不同,这是为什么呢?答案是编译器替我们做了内存对齐。

二、什么是内存对齐

要理解这个问题需要先了解一下字长的概念以及内存的物理结构

2.1 字长

在计算器领域,对于某种特定的计算机设计而言,字(word)是用于表示其自然的数据单位的术语。在这个特定计算机中,字是其用来一次性处理事务的一个固定长度的位(bit)组。一个字的位数即为字长

字长在计算机结构和操作的多个方面均有体现,计算机中大多数寄存器(这里应该是指通用寄存器)的大小是一个字长

上面这段话可能太过于概念化不太好理解,那么请看下面的这段64位机器上的GUN汇编器语法的汇编代码:

movq (%ecx) %eax

这段汇编代码是将eax这个寄存器中的数据作为地址访问内存,并将内存中的数据加载到eax寄存器中。

我们可以看到mov指令的后缀是q,意味着该指令将加载一个64位的数据到eax寄存器中,这样一条指令可以操作一个64位的数据,说明该机器的字长为64位,同时这段代码能够执行则说明我们机器上的CPU中的eax寄存器必定是64位的,而一条指令能够从内存中加载一个64位的数据也说明了数据总线的位宽也为64位,说明了我们的CPU可以一次从内存中加载8个字节的数据。

2.2 64位内存物理结构

内存是由若干个黑色颗粒组成的,每个内存颗粒叫做一个chip,每个chip是由8个bank组成,每个bank是二维平面上的矩阵,矩阵中的每个元素保存1个字节也就是8个bit。

对于内存中连续的8个字节比如0x0000-0x0007,并非位于一个bank上,而是位于8个bank上,每个bank保存一个字节,8个bank像是垂直叠在一起,物理上它们并不是连续的。 image.png 之所以这样设计是基于电路工作效率考虑,这样的设计可以并行取8个字节的数据,如果想取址0x0000-0x0007,每个bank只需要工作一次就可以取到,IO效率比较高,如果这8个字节在同一个bank上则需要串行读取该bank8次才能取到。

结合上面的结构图可以看到0x0000-0x0007是一列,0x0008-0x000F是另外一列,如果从内存中取8-15字节的数据也可以一次取出来,但如果我们要取1-9的数据就需要先取0-7的数据,再取8-15的数据然后拼起来,这样的话就会产生两次内存IO。所以基于性能的考虑某些CPU会强制只能读取8的倍数的内存,而这也导致了编译器再此类平台上编译时必须做内存对齐。

2.3 Cacheline

CPU通常会将Cacheline size个字节一次加载到高速缓存中(即L1、L2、L3缓存)。 这部分内容我后续会写一篇博客专门介绍下CPU高速缓存结构。

2.4 再来看结构体size的问题

以下均以64位平台,即:64位宽内存以及64位cpu(数据总线64位,寄存器64位)、cacheline size=64byte为前提

type S struct {
    B byte
    I64 int64
    I32 int32
}

在不了解内存对齐前我们可能会简单以为结构体在内存中可能是这样排列的: image.png 总共占用13个字节。我们可以看到 I64 这个字段的内存地址是1-8,而在64位平台上为了将这个字段加载到寄存器中,CPU需要两次内存IO。
但做内存对齐后: image.png 总共占用20个字节,I64这个字段的内存地址是8-15,为了将这个字段加载到寄存器中,只需要一次内存IO即可。 我们写段代码验证下是否真的占用了20个字节:

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size: %d, align: %d\n", unsafe.Sizeof(s), unsafe.Alignof(s))
}

输出:

s size: 24, align: 8

程序输出了24,而非上面我们以为的20,这是怎么回事呢?原因是结构体本身也必须要做对齐,它必须在后面再额外占用4个字节以使自己的size为8的倍数。

上面的结构体如果后面跟一个4字节的变量的话理论上说不用对齐也能保证一次内存IO就可加载,所以结构体对齐的根本原因目前我还不是特别能理解,可能为编译器做的优化,了解的同学欢迎在评论区指点一下

我们再调整下结构体的声明:

type S struct {
    B byte
    I32 int32
    I64 int64
}

再做内存对齐的话该结构体在内存中应该就是下面这个样子了: image.png 这时总共占用16个字节,相比较上面我们节省了8个字节。 写段代码验证下:

type S struct {
	B   byte
	I32 int32
	I64 int64
}
func main() {
	s := S{}
	fmt.Printf("s size:%v, s.B地址:%v, s.I32地址:%v, s.I64地址:%v\n", unsafe.Sizeof(s), &s.B, &s.I32, &s.I64)
}

输出结果:

s size:16, s.B地址:0xc0000b4010, s.I32地址:0xc0000b4014, s.I64地址:0xc0000b4018

确实占用了16字节,但貌似I32这个字段跟我们预想的不太一样,它被对齐到了4的倍数地址上,而非紧跟在B后边,这大概是编译器编译一套代码可以运行在32位又可以运行在64位平台上吧,目前没有查到相关资料姑且这么认为吧。

参考资料

字 (计算机))

带你深入理解内存对齐最底层原理

阅读全文 »

x86 CPU与IA-32架构

x86 CPU

现代计算机使用的CPU大部分都是x86CPU,包括现在牙膏厂的酷睿。x86系列CPU的原型是Intel 1978年推出的8086 CPU(就是大学微机原理与接口课上学的)。

32位CPU

在历史诸多CPU中具有里程碑意义的CPU当属386和Pentium4了。368是x86系列第一款32位CPU,Pentium4是Intel第一款64位CPU。”xx位CPU”的定位比较模糊,但一般要满足以下两个条件: 1. 具备n位宽的通用寄存器 2. 具备n位以上的地址空间

“通用寄存器”是寄存器中用于整数运算等的通用的寄存器,地址空间是指进程虚拟地址的全体范围。

指令集

多种多样的CPU有着不同的架构和速度,存在很大的差异,但尽管有这些差异一般386和Core 2都可以统称为x86CPU,这是因为386和Core 2能够执行相同的机器语言的指令。如果只是使用386指令编写的程序,在386和Core 2上都是可以跑的。像这样不同的CPU都能解释的机器语言的体系称为 指令集架构(ISA, Instruction Set Architecture) ,简称 指令集 。 Intel将x86系列CPU之中的32位CPU的指令集架构称为IA-32。IA是“Intel Architecture”。

IA-32的变迁

随着CPU技术的不同发展,CPU支持的指令越来越多,IA-32中指令增加的非常多。 首先486中增加了非常重要的指令。从486的486DX型号开始加入了 浮点数运算单元(FPU,Floating Point number Processing Unit) 支持浮点数计算。486DX所支持的浮点数运算指令称为 x87FPU指令(x87 FPU instuctions)。 386也能够支持浮点数运算,但必须添加名为387的FPU。也就是说配置有387的机器与没有配置387的机器支持的指令是不同的。 所添加的其他重要的指令还有 MMX和SSE(Streaming SIMD Extensions) 。两者都是为了支持并行处理多条数据的扩展指令。例如用通常的IA-32指令进行加法运算时一次只能执行一次加法运算,但使用MMX和SSE的加法指令可以同时执行多个运算。

IA-32的64位扩展: AMD64

AMD曾先于Intel提出x86系列的64位扩展,并推出了相应的产品。由AMD设计的x86位指令集架构称为AMD64。
Intel随后在自己的CPU中加入了和AMD64几乎相同的名为Intel64的指令集。Pentium4后期的版本和Core 2的后续产品都是基于Intel64指令集架构的。
要统称AMD64和Intel64时可以试用独立于公司名称的用语:x86-64。另外,Windows中将AMD64对应的架构称为x64。
Intel曾与HP一起开发名为IA-64的指令集架构,IA-64与IA-32架构完全不兼容。Intel推出的Itanium处理器是基于IA-64架构的。

IA-32的概要

IA-32中主要寄存器如下图:

image.png

通用寄存器 (generic register)是编程时使用频率最高的寄存器,宽度为32位的通用寄存器有eax、ebx、ecx、edx、esi、esp、ebp共8个,用于整数运算和指针处理。

指令指针 (instruction pointer) 是存放下一条要执行的代码的地址的寄存器,IA-32的指令指针为32位,称为eip。

标志寄存器 (flag register) 用于保存CPU的运行模式及表示运算状态等的标志的寄存器。 浮点数寄存器 (floating point number register) 是存放浮点数的寄存器,用于浮点数的计算。IA-32中从st0到st7有8个宽度为80位的浮点数寄存器。

MMX寄存器 (MMX register) 是MMX指令用的寄存器。MMX Pentium以及Pentiunm Ⅱ之后的CPU中有从mm0到mm7共8个64位的寄存器。但实际上MMX寄存器和浮点数寄存器是共用的,即无法同时使用浮点数寄存器和MMX寄存器。

XMM寄存器 (XMM register) 是SSE指令指令用的寄存器。Pentium Ⅲ以及之后的CPU中提供了xmm0到xmm7共8个128位宽的XMM寄存器。XMM寄存器和MMX寄存器不同,是独立的寄存器不和浮点数寄存器共用。另外 mxcsr寄存器 是表示SSE指令的运算状态的寄存器。

除上述寄存器外还有写OS内核时用到的 系统寄存器 和debug时用到的 debug寄存器 以及32位环境下用不到的段寄存器。

通用寄存器

名称由来 寄存器 | 名称的由来 | 翻译 – | – | – eax | accumulator | 累加器,很多加法乘法指令的缺省寄存器 ebx | base regiter | 基底寄存器,在内存寻址时存放基地址 ecx | count register | 计数寄存器,是重复(REP)前缀指令和LOOP指令的内定计数器 edx | data register | 数据暂存寄存器,总是被用来放整数除法产生的余数 esi | source index | 源索引寄存器 edi | destination index | 目标索引寄存器 ebp | base point | 基址指针,经常被用作高级语言函数调用的frame pointer esp | stack pointer | 用作堆栈指针,称为栈顶指针

通用寄存器的宽度都为32位,它们的一部分可以当做16位/8位寄存器使用。例如可以当eax寄存器中的低16位当做16位寄存器ax来访问,还可以将ax寄存器的高8位当做ah寄存器,低8位当做al寄存器。 image.png

IA-32中各进程的一部分地址空间被当做栈来使用,主要用于保存函数的临时变量和参数。栈的位置因OS而已,IA-32 Linux平台上,栈位于各进程地址空间中靠近3GB位置。即栈是从高地址向低地址进行延伸image.png

IA-32中用栈指针(stack pointer)来表示栈,栈指针(esp寄存器)是存放栈顶地址的寄存器

栈的操作

举个例子如果我们要向栈中压一个4字节的整数17,整个操作步骤就是先将esp寄存器-4(栈从高地址向低地址进行延伸的),然后将整数保存到esp寄存器指向的内存地址中。 image.png

出栈则正好相反,首先从esp寄存器指向的内存地址中将数据加载出来,并将esp寄存器+4。

栈帧

栈并不是连续的一整块,栈是根据每一个函数分开管理的,我们将管理单个函数数据的栈的领域称为栈帧(stack frame)。如果有这样一个程序:main函数调用函数f,f调用函数g,那么这个程序在执行g时的栈就会是下图这样:

image.png

ebp寄存器总是指向当前函数栈的栈底,栈帧的顶部与当前进程的栈顶是相同的,esp寄存器总是指向栈帧的顶部。其他架构中一般将具有和基址指针相同功能的指针称为帧指针(frame pointer)。

一个栈帧中通常保存一下信息: * 临时变量 * 源函数执行中的代码地址(返回地址) * 函数的参数 在每个栈帧上存储上述信息的具体步骤是由函数的调用约定(calling convention)决定的,各个CPU、操作系统的函数调用约定是不同的。

指令指针

指令指针(instruction pointer)是存放下一条要执行的指令的地址的寄存器。CPU从该寄存器所指向的内存地址中获取下一条指令并执行,同时将指令指针推到下一条指令,可以通过跳转指令来改变指令指针的值。

根据架构的不同,有时将指令指针称为程序计数器(program counter, pc)。

标志寄存器

eflags是32位寄存器,CPU的运行模式以及运算相关的信息等都以1个bit的形式存在该寄存器中。 image.png

标志有以下三类: 1. 表示运算结果的状态标志(status flag) 2. 用于运算控制的控制标志(control flag) 3. 用于控制计算器整体运行的系统标志(system flag)

一般程序中可用的只有状态标志和控制标志,系统标志再写OS时会用到,用户模式的进程不能修改系统标志,否则会报没有权限的错误。

状态标志的具体含义如下: 简称 | 标志的正式名称 | 含义 – | – | – CF | carry flag | 运算结果中发生进位或借位 PF | parity flag | 运算结果中的奇偶标志位 AF | auxiliary carry flag | 运算结果中低4位向高4位发生进位或借位 ZF | zero flag | 比较结果为0的时候被置为1 SF | sign flag | 运算结果为负数时被置为1 OF | overflow flag | 运算结果越过了正/负的界限

这些标志位一般与跳转指令配合使用。

字节序

32位即4个字节数据的二进制表现形式如下: image.png

MSB(Most Significant Bit)指向最高位,LSB(Least Significant Bit)指向最低位。而在内存中先放MSB所在的字节还是先放LSB所在的字节是由CPU的类型决定的,先放MSB所在字节的架构称为大端(big endian),先放LSB所在字节的架构称为小端(little endian)。通过网络传输超过2个字节数据时一般使用大端的方式,所以大端也被称为网络字节序(network byte order)

本文摘自

How to develop a compiler

阅读全文 »

PHP实现Bitmap的探索 - GMP扩展使用

一、背景

公司当前有一个用户群的系统,核心功能是根据不同的条件组去不同的业务线中get符合条件的uid列表,然后存到redis中的bitmap中。

举个🌰,如果一个用户群中有两个用户: 3和7,即[3,7],用bitmap表示那就是:00010001

最后利用redis提供的bitOp命令: bitOp AND \ bitOp XOR \ bitOp OR对各个条件组对应的uid列表bitmap做交并差集计算,得出最终的用户群并存储到redis bitmap中。

二、问题

对于上面描述的系统,如果用户群人数较多的那我们就需要执行较多次的setBit {uid} 1命令,而且如果用户群中的第一个uid是一个特别大的值比如10亿的话,就可能会一次malloc 1000000000/1024/1024/8 ~= 120M的内存,这可能会导致redis卡住一段时间,在高并发的redis实例上执行这个操作是相当危险的。而且可以预想到对于两个较大的bitmap key执行bitOp也是非常消耗CPU的,应该尽量避免在存储型的redis实例中做这种十分消耗CPU的计算操作。

实际上内存最少只能申请一个字节,即8位,所以上面的计算方式稍有出入,但相差并不大。

三、解决方案

针对上述的问题,可以将bitmap的计算挪到应用程序中来,只将最终统计出来的bitmap存储到redis中即可。
如果最终结果用户群中的第一个uid是一个特别大的值的话,可以先set 1K再设置2K..3K…这样缓存的增加bitmap的大小避免redis卡住。

四、PHP实现Bitmap

由于该系统目前是使用的PHP,所以下面记录下PHP实现Bitmap的”心路历程“。

由于要操作PHP变量的某一位,所以就要借助位运算来实现,但是又由于PHP的位运算只能作用在整型数上,所以我们无法使用字符串或者浮点数来实现,所以最先考虑的就是使用整型数组来实现。

为什么是数组呢?因为在64位机器上一个整型变量最多只能使用64位,又由于PHP的整型是有符号的,所以最高位无法供我们使用,所以一个整型变量能存储的最大的uid就是63,这真是太鸡肋了-_-||,所以只能搞个用多个整型变量了实现了。

OK,到此为止貌似找到一个看起来不错的解决方案。但是我们再思考这样一个问题:假设我们系统中最大的uid是63x100万=3.6千万(*对主流互联网公司来说这很正常吧😸*),那为了存储所有uid,我们需要1百万个整数才行,即我们需要一个拥有1百万个元素的数组,那么如果我在进程中制造了一个这样的数组会占用多少内存呢?会是64 * 1百万 / 1024 / 1024 / 8 ~= 7.6M吗?答案是否定的,因为php数组是由HashTable实现的,这是一个复杂的结构体,除了数组元素占用的内存外,还有其他的占用。(这里先不做展开,有兴趣可以自行查看下php数组的实现) 眼见为实:

<?php
ini_set('memory_limit','4G');
$arr = [];
for ($i = 0; $i < 64 * 1000000; $i++)
{
    $arr[] = PHP_INT_MAX;
}

echo "done\n";
while(1){
}

查看内存占用

image.png

可以看到大概是1.5G,比我们上面预计的大的多,这太可怕了,必须优化下我们的内存占用,才能真正在生产环境中使用。

这里需要提一句,我的机器只有8G,所以程序可能会用到swap分区,而ps命令结果中的RSS不统计swap分区的占用,在我实际实现中发现ps结果中RSS一列显示占用的内存会随着时间慢慢减少,但是我的程序中arr变量占用的内存是不可能被回收的,所以推测是物理内存中占用的部分内存被置换到了swap分区中。如果你要进行这个实验的话建议关闭swap分区,这样你能得到一个更准确的结果。

五、继续优化

基于上面的经验,如果我们要占用尽可能小的内存,那我们必须能够操作一段近乎无限长的内存且不能产生其他额外占用才可以。幸运的是PHP给我们提供了这样一个扩展:GMP,这个扩展可以让我们使用一个任意长度的整数。OK现在我们拥有了获得一块连续的内存而不会产生其他额外占用的手段,再写一段代码使用下并验证下内存占用情况:

<?php

$gmp = gmp_init(0);
gmp_setbit($gmp, 64 * 1000000, true);
echo "done\n";
while(1){}

image.png

Awesome,这次只使用了15M的内存。更加兴奋的是这个扩展提供了诸如:gmp_andgmp_orgmp_xor这样进行位运算的函数,极大的方便了我们的使用。

到此为止我们似乎找到了一个完美的解决方案,但是真的完美吗?No!其实还可以再优化一下,想象下如果我们有一个用户群,里面只有一个uid:64000000(表示为数组的话就是:[64000000]),为了存储这个用户我们需要占用7.6M内存,而这个用户群中仅仅只有一个元素,这真是极大的浪费啊!

为了优化这个问题可以拥抱上面被我们唾弃的数组😸,一个大的bitmap拆分为一个个小bitmap的数组,这一个个小的bitmap我们限制大小为1Kw位。 image.png

回到上面的问题,如果我们要存储[64000000]这个用户群的话只需要在数组的第6个元素中设置一个little bitmap: 1即可。这样我们就由一开始的占用7.6M内存优化为了占用1位内存。

OK,到此为止我们找到一个还不错的解决方案😸。

后言

为了在Mac中安装GMP扩展又耗费了很多时间,当然,这又是另外一个故事了。有时间我会分享Mac中安装GMP扩展的过程中我遇到的问题。

参考资料

  1. GNU Multiple Precision
  2. Process Memory Management in Linux
  3. 从源码看 PHP 7 数组的实现
阅读全文 »

LR分析中shift/reduce reduce/reduce冲突解决方案SLR(1)与LR(1)

此篇文章要求读者对编译原理前端部分有一定了解 此篇文章中,我们以大写英文作为非终结符,小写英文作为终结符

1. LR(0)分析法简述

LR分析法从左至右移进输入的终结符(词法分析器的输出实际是token,但在语法分析阶段会代表是一个终结符),并将终结符压入到堆栈,称为shift。如果当前栈上的符号恰好符合某个非终结符的生成式,则此时进行归约操作:将这些符号弹出栈,然后将规约后的非终结符压入堆栈,这一步就称为reduce。然后继续上面的步骤,直到没有输入。
如果最终栈上只有一个非终结符,且该非终结符就是目标符号,那证明识别成功,否则识别失败。
名称LR得名于:从左(Left)到右扫描(L),反向(Reverse)最右推导(R)。

2. LR(0)分析法的不足

上面描述的算法存在一个问题,我们以下面的语法为例说明:

// 例1
B : A c
A : b d
  | b

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是继续移进下一个终结符,一个是使用生成式A : b进行归约。这种情况称为shift/reduce冲突
继续看下面一个例子:

// 例2
A : b
C : b
D : A a
E : C d

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是根据A : b,归约为A,另一个选择是使用生成式C : b进行归约。这种情况称为reduce/reduce冲突

因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用,必须找到解决这两种冲突的方案才行,那么如何这两种冲突呢?

3. SLR(1)

对于这两种冲突,我们首先先看一种简单的解决方案:SLR(1) (Simple LR)分析法。
SLR(1)分析法首先求出所有非终结符的Follow Set,即 跟在非终结符之后的所有终结符的集合,然后前瞻一个符号(即从词法分析器中预先读入下一个终结符),如果该前瞻符号在一个非终结符的Follow Set中,就根据此非终结符的生成式进行归约。

我们以上面的例2为例,SLR(1)分析器先求出A的Follow Set为{a},C的Follow Set为{b},假设当前输入为b a,输入b之后,语法分析器面临选择:归约到A or 归约到C,此时分析器前瞻一个符号即c,由于c属于A的Follow Set,所以分析器选择归约到A。

上面的例1也可以通过此算法解决shift/reduce冲突。

遗憾的是SLR(1)依然存在问题,这里举个例子就清楚了:

// 例3
T : S
S : aAd
S : bAc
S : aec
S : bed
A : e

首先求出各个非终结符的Follow Set:

Follow(T) = {}
Follow(S) = {}
Follow(A) = {d, c}

我们假设当前的输入为a e c, 当输入e时,SLR(1)分析器面临两个选择:继续移进下一个符号 or 根据A : e归约到A,此时SLR(1)分析器前瞻符号c,c存在于Follow(A)中,但此时又可以选择移进c,所以SLR(1)此时又面临着冲突了。

SLR(1)不足之处在于Follow Set太宽泛,处于Follow Set中的前瞻符号不一定能合法的跟在非终结符之后。实际上SLR(1)忽略了分析的上下文,针对SLR(1)的不足由提出了LR(1)分析法。

4. LR(1)

LR(1)的基本原理就是只要前瞻符号能合法跟在归约的非终结符之后就可以进行归约,LR(1)会为每个生成式绑定一个** LookAhead Set**,只有前瞻符号处于这个集合之中才进行归约,它是Follow Set的子集。那么LookAhead Set如何生成呢?

4.1 LookAhead Set生成

我们将生成式一般化为下面的样子:

s -> α .x β, C 
x -> . r

其中 s,x都是非终结符,α β r可以是终结符也可以是非终结符,C 为生成式的LookAhead Set。

x的LookAhead Set = First(β C),即β的FirstSet与C串起来之后的First集

First Set可以理解为非终结符所有生成式中第一个终结符的集合

5. Merak

我将LR(1)分析算法封装成了一个Golang Parser库:Merak,并且用它实现了一个面向对象语言的Parser: Mizar。对此有兴趣的同学可以试用下,它将为你省略手写语法分析器的过程,节省宝贵的时间投入到更加有趣的编译器后端工作中。

阅读全文 »

《我的第一个面向需求的Haskell程序》续

前言

上一篇《我的第一个面向需求的Haskell程序》文章中的Haskell程序还存在一个问题: 程序只打印出了文件中有没有重复的元素但是并没有告知是哪一个元素重复了,重复了几次也没有打印出来。 所以我继续优化下上篇文章中的Haskell程序,现在这段程序变成了下面这样

代码

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    mapM_ printRepeat $ fmap (\(x:xs) -> (x, 1 + length xs)) $ group $ splitOn "\r\n" contents
    putStrLn "check done"

check x = do
    putStrLn "请输入文件名"

printRepeat::(String, Int) -> IO()
printRepeat (word, num)
    | num > 1 = putStrLn $ word ++ " repeated " ++ (show num) ++ " times."
    | otherwise = return ()

使用

$ cabal build
$ ./dist-newstyle/build/x86_64-osx/ghc-8.8.4/repeat-0.1.0.0/x/repeat/build/repeat/repeat test.txt
joM2qWfjOJc repeated 2 times.
check done

解释

首先我们使用split包提供的splitOn 函数按照换行符将文件内容切分为[String],现在我们有了:

["abc", "abc", "def", "ghi", "def"]

然后使用group函数聚合下这个List,得到:

[["abc", "abc", "abc"], ["def", "def"], ["ghi"]]

再通过fmap (\(x:xs) -> (x, 1 + length xs))即map一个lambda表达式到这个List上,将这个List中的每个元素转为元组,得到:

[("abc", 3), ("def", 2), ("ghi", 1)]

至此我们实际做了一个WordCount程序…

接下来调用printRepeat函数打印出来结果就OK了

阅读全文 »

GNU 汇编器的语法

学习汇编语法的目的

为什么要学习汇编语法呢?原因是我最近在做一个面向对象语言的编译器(地址:https://github.com/Orlion/Mizar),目前已经完成了parser部分,即已经生成了AST,下一步要做的就是语义分析了,而语义分析之后要做的就是生成AT&T汇编代码了,所以有必要提前了解下汇编语法看在语义分析的实现阶段能否有所指导。

先看一段代码

首先我们有这样一段c语言代码:

#include <stdio.h>

char msg[14] = "Hello,world!\n";
 
int main(void)
{
    puts(msg);
    return 0;
}

运行 gcc -S -Os hello.c

    .file   "hello.c"
    .section    .text.startup,"ax",@progbits
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rax
    .cfi_def_cfa_offset 16
    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax
    popq    %rdx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .globl  msg
    .data
    .align 8
    .type   msg, @object
    .size   msg, 14
msg:
    .string "Hello,world!\n"
    .ident  "GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-39)"
    .section    .note.GNU-stack,"",@progbits

接下来解释下AT&T汇编的语法

指令

指令是直接由CPU负责处理的命令,不以.开头的行首缩进的行都是指令行。

    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax

指令由操作符和作为参数的操作数组成,以 movl $msg, %edi 为例,movl 为操作符, $msg%edi 为操作数,操作数以逗号来间隔。

汇编伪操作

. 开头末尾没有:的行都是汇编伪操作。例如,.file "hello.c", .globl main。汇编伪操作是由汇编器而非CPU处理的指令。一般用于在目标文件中记录元数据(meta data)或者设定指定的属性等。例如 .string 是用来定义字符串常量的汇编伪操作。

标签(labal)

以冒号: 结尾的行都是标签行,例如:.LFB0:,main:。 标签具有为汇编伪操作生成的数据或者指令命名(标上符号)的功能,这样就可以在其他地方调用通过标签定义的符号。 标签可以以.开头

注释

支持两种注释:

# xxx

/* xxx
xxx */

助记符后缀

刚才提到的movlsubl为助记符,更准确的说movsub为助记符,末尾的l是后缀,llong的缩写,表示操作对象的数据大小。类似这样的后缀还有b,w,l

|后缀|操作对象的大小|缩写| |-|-|-| |b|8位|byte| |w|16位|word| |l|32位|long|

操作数

操作数有四种: 1. 立即数 2. 寄存器 3. 直接内存引用 4. 间接内存引用

1. 立即数

立即数就是C语言中的字面量,机器语言中立即数以整数的形式出现,能高速访问。像$27这样,立即数用$来标识,如果漏掉了$就成了直接内存引用了。立即数有8位,16位,32位。

2. 寄存器

GUN汇编器规定寄存器以%开头,例如eax寄存器写作%eax

3. 直接内存引用

直接访问固定内存地址的方式。GNC汇编器会将任何整数解释为内存地址并访问。比起使用数字,更常用符号(symbol)直接访问内存。例如.LFE0就是访问符号.LFE0所指向的地址。符号在汇编和链接的过程中会被置换为实际内存地址。

4. 间接内存引用

是将寄存器的值作为内存地址访问的方式。间接内存引用中最通用的就是下方的形式:

disp(base, index, scale)

其中任何一者都可以省略。

上述指令访问disp + (base + index * scale)的地址。 下面详细讲解,首先最简单的间接引用的形式如下:

(%eax)

即只指定基地址(base)的形式。上述表达式将eax寄存器中的值作为内存地址访问。 接着带有disp的形式如下。disp是displacement(偏移)的简称。

4(%eax)

上述就是访问 4 + (eax寄存器中值) 这个内存地址。在C语言中用来访问如下结构体中成员y的情况:

struct point {
    int x; // x占4个字节,即4个内存地址
    int y;
}

最后使用index和scale的情况如下所示:

(%ebx, %eax, 4)

上面访问的就是(ebx寄存器中的值 + eax寄存器中的值 * 4)内存地址。在C语言中用来访问数组,例如访问元素大小为4字节(例如int)的数组中元素的第%ebx个元素时就可以用这种方式。当并非所有的数组访问都可以只靠间接内存引用来表示,因为scale只能是1、2、4、8之一。

2020-09-22更

突然意识到如果要将一个复杂工程的AST编译为汇编代码必须具备能够用汇编实现这个复杂工程的能力才行,这太难了… 所以暂时放弃吧,先编译到了LLVM IR再说,嗯。

2020-10-07更

不如趁此机会学习下汇编以及后续的链接装载,有助于建立宏观的了解。所以还是继续学习吧。 😸

未完待续…

阅读全文 »

对Haskell惰性求值的理解

全文均为伪代码,没有验证,只可意会

doIf::Bool -> a -> Maybe a
doIf cond action = if cond then (Maybe action) else Nothing

我们声明了一个doIf函数,它接收两个参数:cond与action,它干一件事:如果cond == true 就调用action,并包在Maybe中返回。 如果是strict的语言的话,在调用doIf函数的之时action就会被执行了,而Haskell默认是non-strict的,所以在调用doIf时,action无需求值,只有在cond为true时才需要对action求值,如果cond为false的话action根本不会被执行,这就是non-strict与strict的区别。

阅读全文 »

我的第一个面向需求的Haskell程序

背景

上周五(20年8月28日)的时候,公司测试同学需要测试我的一个提测需求,其中有个测试用例是需要检查下下后台导出的兑换口令列表文件中是否有重复的口令。

由于导出的口令有数百万之多,肯定是不能用眼去看了,原本是打算用excel来检查的,但是我一想:ei(二声)~,最近不是正好在搞Haskell吗?正好拿来练练手,用Haskell写个检测程序。

Why is Haskell

因为这个程序写出来是要交给测试同学使用的,如果用java或者php这种解释型语言来写,还需要测试同学先去安装个java/php的解释器才行,显然是有点扯的,所以用编译型语言写完后直接build出一个可执行文件才比较方便。

当然可以将java/php的程序打包成一个可执行文件,但是又要花费我一些不必要的时间了。

编译型语言中我常用的有golang和Haskell。不可否认Go面对这个需求写起来可能更快,但是我其实还是想用Haskell练练手。

那? 开始吧!

首先,使用cabal创建一个项目

$ mkdir repeat && cd repeat
$ cabal init

导出的口令文件是以\r\n换行的,haskell的lines函数无法切分,所以需要通过cabal引入一个包:split,我的repeat.cabal文件就变成了下面这样了:

cabal-version:       >=1.10
-- Initial package description 'repeat.cabal' generated by 'cabal init'.
-- For further documentation, see http://haskell.org/cabal/users-guide/

name:                repeat
version:             0.1.0.0
-- synopsis:
-- description:
-- bug-reports:
-- license:
license-file:        LICENSE
author:              wangdongdong
maintainer:          wangdongdong@smzdm.com
-- copyright:
-- category:
build-type:          Simple
extra-source-files:  CHANGELOG.md

executable repeat
  main-is:             Main.hs
  -- other-modules:
  -- other-extensions:
  build-depends:       base >=4.13 && <4.14, split
  -- hs-source-dirs:
  default-language:    Haskell2010

编辑Main.hs

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

-- 通过模式匹配获取命令行参数中的文件名
check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    -- 暴力通过去重后的list length对比来判重,不可取
    if (length $ mylines contents) /= (length $ nub $ mylines contents)
        then putStrLn "有重复元素" 
        else putStrLn "没有重复元素"

check x = putStrLn "请输入文件名"

-- 通过split库的splitOn函数以\r\n为切割符将文件内容切分为list
mylines contents = splitOn "\r\n" contents

最后编译为可执行文件

$ cabal build

编译结果在dist-newstype文件夹之中

交付使用

$ ./repeat keywords.txt

能够满足需求!

后续优化请看

《我的第一个面向需求的Haskell程序》续

阅读全文 »

go mod 提示 unknown revision问题

通过go mod download下载公司gitlab仓库代码时提示unknown revision 由于是私有仓库且回车执行命令后并没有输入密码的提示,所以猜测是go mod download时git clone 没有输入密码提示

一番搜索后发现解决方案如下:

// 设置永久存储账号密码
git config credential.helper store
// git pull过程中允许输入用户名密码
export GIT_TERMINAL_PROMPT=1
阅读全文 »

golang 中的一些tips [持续更新中]

new() 函数

golang中的new是一个用户分配内存的函数,new(T) 为类型T分配一块内存,初始化为T类型的零值,并返回它的地址,即类型为*T的指针

int的零值是0,bool的零值是false,结构体的零值是其各元素零值的一个对象,

 type Person struct {
	Name string
	Age int
 }

的零值就是Person{“”, 0}

以Person结构体为例,new(Person) 实际等价于 &Person{}

struct 值方法与指针方法

type Person struct {
	Name string
}

// 值方法
func (p Person) SetName1(name string) {
	p.Name = name
}
// 指针方法
func (p *Person) SetName2(name string) {
	p.Name = name
}

结构体方法可以想象为:(这里并不严格)

func SetName1(p Person, name string) { ... }
func SetName2(p *Person, name string) { ... }

这样就一目了然了,一个是值传递,一个是指针传递。

还有一点需要注意:

p1 := Person{}
p2 := &Person{}

p1.SetName2("p1") // 实际会被当为 (&p1).SetName2()
p2.SetName1("p2") // 实际会被当为 (*p2).SetName1()

fmt.Println(p1.Name) // 输出p1
fmt.Println(p2.Name) // 输出空字符串

面对interface时的一个tip

如果有这样一个接口:

type Animal interface{
	SetName()
	SetAge()
}
type Cat struct {
	
}

func (cat Cat) SetName() {}
func (cat *Cat) SetAge() {}

func foo(a Animal) {
	a.SetName()
}

c1 := Cat{}
c2 := &Cat{}

foo(c1) // 报错:cat这个类型没有实现Animal接口的SetAge方法
foo(c2) // 通过

通过上面的例子可以看到: 一个指针类型拥有以它以及以它的基底类型为接收者类型的所有方法,而它的基底类型却至拥有以它本身为接收者类型的方法

变量作用域问题

有下面这个程序,猜下会怎样输出呢?

foo := 1
if true {
	foo := 2
	fmt.Println(foo)
}

fmt.Println(foo)

以为会输出2 2 ? 错!实际输出2 1

原因是go 的语义块中定义的变量是该语句块中的局部变量,if语句块中的foo实际通过 := 声明赋值时,决定了这个foo只是当前if语句块中的foo,而不是外部的foo

阅读全文 »

haskell 中的newtype

haskell中一般使用data关键字来自定义type,像这样:

data BookInfo = Book Int String [String] deriving (Show)

但有些情况下要使用newtype来定义, 举个例子,对于数字来说,它有两种选择可以表现为一个monoid,一个是 * 作为二元函数,1 作为identity, 另外一种是 + 作为二元函数,0 作为identity。那么问题来了怎么把这两种选择都实现 (这里所说的实现是指把一个数字实现为Monoid这个typeclass的instance) 呢?

Data.Monoid 这个模块导出了两个类型:ProductSum 。Product的定义如下:

Prelude Data.Monoid> :i Product
newtype Product a = Product {getProduct :: a}

Sum的定义如下:

Prelude Data.Monoid> :i Sum
newtype Sum a = Sum {getSum :: a}

Product的Monoid的instance实现:

instance Num a => Monoid (Product a) where  
    mempty = Product 1  
    Product x `mappend` Product y = Product (x * y)

很显然它将第一种选择即乘法实现了。它代表 Product a 对于所有属于 Numa 是一个 Monoid

为什么要用newtype呢?

因为newtype比较快。 如果用data的话在执行的时候会有包起来和解开来的成本,但使用newtype的话,Haskell会知道你只是要将一个type包成一个新的type,你想要内部运作完全一样只是要一个新type而已。有了这个概念,Haskell可以将包裹和解开的成本省掉。

为什么不能所有地方都用newtype呢,是因为当使用newtype来制作一个新type的时候,只能有一个值构造器,而且这个值构造器只能有一个字段。

阅读全文 »

一些范畴论上的概念

为了能真正理解Haskell中的Functor、Applicative、Monad、Monoid,以及它们到底有什么用,个人觉得还是有必要 了解 一些范畴论里面的概念的

函数 Function

函数表示特定类型之间的 态射

自函数 EndoFunction

自函数就是把类型映射到自身类型

identity :: Number -> Number

identity函数就是一个自函数的例子,它接收什么就返回什么

函子 Functor

函子与函数不同,函数描述的是类型之间的映射,而函子描述的是 范畴(category) 之间的映射

范畴

范畴是一组类型及其关系 态射 的集合。包括特定类型及其态射,比如: Int、 String、 Int -> String ;高阶类型及其态射,比如 List[Int]、 List[String]、 List[Int] -> List[String]

函子如何映射两个范畴

image.png

图中,范畴C1和范畴c2之间有映射关系,C1中Int映射到C2List[Int],C1中String映射到C2List[String],C1中的关系态射Int -> String 也映射到 C2中的关系List[Int] -> List[String]态射上。

也就是说,一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一范畴中的元素间的关系,则设为这两个范畴之间存在映射。所谓函子就是表示两个范畴之间的映射。

Haskell中,Functor是可以被map over的东西,List就是一个典型的instance。构造List[Int] 就是把Int提升到List[Int],记作:Int -> List[Int] . 这表达了一个范畴的元素可以被映射为另一个范畴的元素

我们看下Haskell中map函数的定义:

map :: (a -> b) -> [a] -> [b]

把我们上面的Int String的例子代入,配合柯里化的概念可以得出:

map :: (Int -> String) -> (List[Int] -> List[String])

map的定义清晰的告诉我们: Int -> String 这个关系可以被映射为 List[Int] -> List[String] 这种关系。这就表达了元素间的关系可以映射为另外一个范畴元素间的关系

所以List就是一个Functor

自函子

自函数是把类型映射到自身类型,那么自函子就是把范畴映射到自身范畴。

image.png

上图就是一个将范畴映射到自身的自函子。从函子的定义出发,我们考察这个自函子,始终有List[Int] -> List[String]List[Int] -> List[String] -> List[Int] -> List[String] 这两种映射。我们表述为:

类型List[Int] 映射到自己
态射f :: List[Int] -> List[String] 映射到自己

我们记作:

F(List[Int]) = List[Int]
F(f) = f
其中F是Functor

幺半群

先解释下群的概念:G为非空集合,如果在G上定义的二元运算*,满足:

(1) 封闭性:(Closure):对于任意a,b∈G,有a*b∈G
(2) 结合律(Associativity):对于任意a,b,c∈G,有(a*b)*c=a*(b*c)
(3) 幺元 (Identity):存在幺元e,使得对于任意a∈G,e*a=a*e=a
(4) 逆元:对于任意a∈G,存在逆元a^-1,使得a^-1*a=a*a^-1=e

则称(G, *) 为群,简称G为群。

如果仅满足封闭性和结合律,则该G是一个 半群(Semigroup) ; 如果满足封闭性和结合律并且存在幺元,则该G是一个 幺半群(Monoid)

接下来看下在自函子的范畴上,怎样结合幺半群的定义得出Monad

假设我们有个cube函数,它计算一个数的三次方:

cube :: Number -> Number

现在我们想在其返回值上添加一些调试信息,返回一个元组,第二个元素代表调试信息,函数签名为:

f :: Number -> (Number, String)

可以看到参数与返回值不一致。我们再看下幺半群规定的结合律。对于函数而言,结合律就是将函数以各种结合方式嵌套起来调用。我们将Haskell中的 . 函数看做这里的二元运算。

(.) :: (b -> c) -> (a -> b) -> a -> c

f . f

从函数签名可以看出右边f返回的是元组(Number, String),而左侧的f接收的是Number。所以无法组合,他们彼此不兼容。

有什么办法能消除这种不兼容?结合前面所述,cube是一个自函数,元组(Number,String)在Hask范畴是一个自函子 (这个说法看起来并不准确,(?, String)才应该是一个自函子 ) , 理由如下:

F Number = (Number, String)
F Number -> Number = (Number,String) -> (Number,String)

如果输入和输出都是元组,结果会怎样呢?

fn :: (Number,String) -> (Number,String)
fn . fn

这样是可行的,在验证满足结合律之前,我们引入一个liftM函数来辅助将f提升成fn

liftM :: (Double -> (Double, String)) -> (Double,String) -> (Double, String)
liftM f (x,y) = case r of (n,s) -> (n, y ++ s)
    where r = f x 

没有验证,就当伪代码看吧

我们来实现元组自函子范畴上的结合律:

cube :: Number -> (Number, String)
cube x = (x * x * x, "cube was called.")

sine :: Number -> (Number, String)
sine x = (Math.sin x, "sine was called.")

f = ((liftM sine) . (liftM cube)) . (liftM cube)
f (3, "")
输出:(0.956, 'cube was called.cube was called.sine was called.')

f1 = (liftM sine) . ((liftM cube) . (liftM cube))
输出:(0.956, 'cube was called.cube was called.sine was called.')

这里f和f1代表的结合顺序产生了相同的结果,说明元组自函子范畴满足结合律。

那如何找到这样一个e,使得 a * e = e * a = a ,此处的 * 就是 .

unit :: Number -> (Number, String)
unit x = (x, "")

f = (liftM sine) . (liftM cube)

f . (liftM unit) = (liftM unit) . f = f

这里的 liftM unit 就是 e 了。

unit 个人理解应该就是类型构造器

阅读全文 »

Haskell lambda 与 $ 与 函数组合

lambda

lambda就是匿名函数,有些时候我们会需要一个函数而这个函数可能只用到一次,并没有重用的场景,我们就可以搞一个 临时 的匿名函数来满足我们的计算。

(\xs -> length xs > 10)

lambda首先是一个\,后面是用空格分隔的参数,->后边就是函数体。通常会用括号括起来。

$

$函数,也叫作函数调用符,它的定义如下

($) :: (a -> b) -> a -> b  
f $ x = f x  

普通的函数调用符有最高的优先级,而 $ 的优先级则最低。用空格的函数调用符是左结合的,如 f a b c 与 ((f a) b) c 等价,而 $ 则是右结合的

$是优先级最低的中缀右结合函数,从签名来看,只是个函数调用符,相当于在右边加括号

tip: $是个中缀函数,要求左边是函数,右边是其参数

> max 5 3 * 2 + 1
11
> max 5 $ 3 * 2 + 1
7

f (g (z x))f $ g $ z x 等价

函数组合

函数组合用.函数来实现,.函数的定义为:

(.) :: (b -> c) -> (a -> b) -> a -> c  
f . g = \x -> f (g x)  

函数组合的用处之一就是生成新函数,并传递给其他函数。
假设我们有一个数字组成的list,我们要把它其中每个元素转成负数,在使用函数组合之前我们可能会这样实现:

Prelude> map (\x -> negate (abs x)) [1,2,-3,4,5,-6]
[-1,-2,-3,-4,-5,-6]

tip: 先用abs函数取绝对值,再用negate函数取反

用函数组合的话就可以这样实现:

Prelude> map (negate . abs) [1,2,-3,4,5,-6]
[-1,-2,-3,-4,-5,-6]

函数组合的另一用途就是定义 point free style (也称作 pointless style) 的函数。以下面的函数为例:

sum' :: (Num a) => [a] -> a     
sum' xs = foldl (+) 0 xs

等号的两端都有个 xs。由于有柯里化 (Currying),我们可以省掉两端的 xs。foldl (+) 0 回传的就是一个取一 List 作参数的函数,我们把它修改为 sum’ = foldl (+) 0,这就是 point free style。下面这个函数改成point free style就是:

fn x = ceiling (negate (tan (cos (max 50 x)))) 
fn = ceiling . negate . tan . cos . max 50
阅读全文 »

Haskell 函数语法

模式匹配

Prelude> let { lucky' :: Integral a => a -> String; lucky' 7 = "seven"; lucky' x = "other" }
Prelude> lucky' 7
"seven"
Prelude> lucky' 10
"other"
Prelude> lucky' "a"

<interactive>:39:1: error:
    • No instance for (Integral [Char]) arising from a use of ‘lucky'’
    • In the expression: lucky' "a"
      In an equation for ‘it’: it = lucky' "a"

tip: 在8.8.1版本ghci中如果按照书中的写法是会报没有匹配项的错误的,按照let { … } 写法则没有问题

在调用lucky时,模式会从上到下进行检查,一旦有匹配则对应的函数体便被应用。

如果我们制定的匹配模式不全时,传入一个没有被任何模式匹配到的参数时就会报错。

对Tuple同样可以使用模式匹配:

addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)  
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)  

first :: (a, b, c) -> a  
first (x, _, _) = x 

List Comprehension 也可以用模式匹配:

Prelude> let xs = [(1,3), (4,3), (2,4), (5,3), (5,6), (3,1)]  
Prelude> [a+b | (a,b) <- xs]
[4,7,6,8,11,4]

对List也可以用模式匹配:

Prelude> let {sumList :: Num a => [a] -> a; sumList [] = 0; sumList (x:xs) = x + sumList xs }
Prelude> sumList [1,2,3]
6

Guards

bmiTell :: (RealFloat a) => a -> a -> String  
bmiTell weight height  
    | weight / height ^ 2 <= 18.5 = "You're underweight, you emo, you!"  
    | weight / height ^ 2 <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"  
    | weight / height ^ 2 <= 30.0 = "You're fat! Lose some weight, fatty!"  
    | otherwise                 = "You're a whale, congratulations!"    

guard由跟在函数名及参数后边的竖线标志,通常竖线都是靠右一个缩进排成一列。一个guard就是一个布尔表达式,如果是True,就使用对应的函数体。最后的一个guard往往是otherwise,它的定义就是简单一个otherwise = True。

通过guard实现自己的compare函数

-- myCompare.hs
myCompare :: Ord a => a -> a -> Ordering
a `myCompare` b 
    | a > b = GT
    | a < b = LT
    | otherwise = EQ
Prelude> :l myCompare.hs
[1 of 1] Compiling Main             ( myCompare.hs, interpreted )
Ok, one module loaded.
*Main> 1 myCompare 2

<interactive>:2:1: error:
    • Non type-variable argument
        in the constraint: Num ((a -> a -> Ordering) -> t1 -> t2)
      (Use FlexibleContexts to permit this)
    • When checking the inferred type
        it :: forall a t1 t2.
              (Ord a, Num t1, Num ((a -> a -> Ordering) -> t1 -> t2)) =>
              t2
*Main> 1 `myCompare` 2
LT
*Main> 2 `myCompare` 1
GT
*Main> 1 `myCompare` 1
EQ

where 关键字

上面例子中的bmiTell函数weight / height ^ 2重复计算了3次,可以利用where修改:

-- bmiTell.hs

bmiTell :: RealFloat a => a -> a -> String
bmiTell weight height 
    | bmi <= 18.5 = "case 1"
    | bmi <= 25.0 = "case 2"
    | bmi <= 30.0 = "case 3"
    | otherwise = "otherwise"
    where bmi = weight / height ^ 2
*Main> :l bmiTell.hs
[1 of 1] Compiling Main             ( bmiTell.hs, interpreted )
Ok, one module loaded.
*Main> bmiTell 130 180
"case 1"

还可以继续修改:

bmiTell :: (RealFloat a) => a -> a -> String  
bmiTell weight height  
    | bmi <= skinny = "You're underweight, you emo, you!"  
    | bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"  
    | bmi <= fat    = "You're fat! Lose some weight, fatty!"  
    | otherwise     = "You're a whale, congratulations!"  
    where bmi = weight / height ^ 2  
          skinny = 18.5  
          normal = 25.0  
          fat = 30.0 

函数在where绑定中定义的名字只对当前函数可见。 where绑定也可以使用模式匹配

...
where bmi = weihgt / height ^ 2
    (skinny, normal, fat) = (18.5, 25.0, 30.0) 

where绑定可以定义名字也可以定义函数:

calcBmis :: (RealFloat a) => [(a, a)] -> [a]  
calcBmis xs = [bmi w h | (w, h) <- xs] 
    where bmi weight height = weight / height ^ 2  

let关键字

let绑定是个表达式,允许在任何地方定义局部变量,而对不同的guard不可见。let也可以使用模式匹配

cylinder :: (RealFloat a) => a -> a -> a  
cylinder r h = 
    let sideArea = 2 * pi * r * h  
        topArea = pi * r ^2  
    in  sideArea + 2 * topArea  

let的格式为let [binging] in [expression]。let中绑定的名字仅在in中可见,let中的名字必须对齐在一列。

let是个表达式,而where是个语法结构。因为let是个表达式,所以let可以随处安放:

Prelude> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]

上面的例子中let定义了一个函数。

若要在一行中绑定多个名字,可以用分号将他们分开:

Prelude> (let a = 100; b = 200; c = 300 in a*b*c, let foo = "Hey"; bar = "there" in foo ++ bar)
(6000000,"Heythere")

tip: 最后那个绑定后面的分号不是必须的,可以加上可以去掉

可以用let改写上面的calcBmis函数:

calcBmis xs = [bmi w h | (w, h) <- xs, let bmi = w / h ^ 2]

List Comprehension 中 let 绑定的样子和限制条件差不多,只不过它做的不是过滤,而是绑定名字。let 中绑定的名字在输出函数及限制条件中都可见。这一来我们就可以让我们的函数只返回胖子的 bmi 值:

calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0] 

在 (w, h) <- xs 这里无法使用 bmi 这名字,因为它在 let 绑定的前面。

在 List Comprehension 中我们忽略了 let 绑定的 in 部分,因为名字的可见性已经预先定义好了。不过,把一个 let…in 放到限制条件中也是可以的,这样名字只对这个限制条件可见。在 ghci 中 in 部分也可以省略,名字的定义就在整个交互中可见。

Prelude> let a = 1
Prelude> a
1

Case 表达式

head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"  
                      (x:_) -> x  

case的语法:

case expression of pattern -> result  
                   pattern -> result  
                   pattern -> result  
                   ...  

expression匹配符合的模式,如果符合则执行。实际上上面的模式匹配是case的语法糖而已。

函数参数的模式匹配只能用在定义函数时使用,而case可以用在任何地方:

describeList :: [a] -> String  
describeList xs = "The list is " ++ case xs of [] -> "empty."  
                                               [x] -> "a singleton list."   
                                               xs -> "a longer list." 
阅读全文 »

Haskell Type与Typeclass

Type

ghci中可以用:t检测表达式的类型

Prelude> :t "a"
"a" :: [Char]

函数也有类型,编写函数时给一个明确的类型声明是一个好习惯

removeNonUppercase :: [Char] -> [Char]
removeNonUppercase st = [c | c <- st, c `elem` ['A'..'Z']]

我们可以这样解读这个函数的类型:removeNonUppercase这个函数接收一个Char List类型的参数返回一个Char List类型的返回值

addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z

参数之间由->分隔,这样解读这个函数的类型:addThree这个函数接收3个Int类型的参数返回一个Int类型的返回值。
> tip: 按照其他语言中的习惯,Int,Int,Int -> Int好像看起来更为恰当一些,但实际haskell中->只有一个作用:它标识一个函数接收一个参数并返回一个值,其中->符号左边是参数的类型,右边是返回值的类型。haskell中所有函数都是只接收一个参数的,所有函数都是currying的。

常见类型

  • Int 整数,与平台位数相关
  • Integer 无限大整数
  • Float 单精度浮点数
  • Double 双精度浮点数
  • Bool
  • Char

Tuple的类型取决于它的长度与其中项的类型,空Tuple也是一个类型,它只有一个值()

Type variables

以head函数为例

Prelude> :t head
head :: [a] -> a

可以看到这里有个a,而a明显不是一个具体的类型,类型首字母必须是大写的,那它是什么呢,它实际上是一个类型变量,a可以是任意类型。 > tip: 与其他语言中的泛型generic很像

使用到类型变量的函数被称为“多态函数”。可以这样解读head函数的类型:head函数接收一个a类型的List参数(即任意类型的参数)返回一个a类型的返回值(参数与返回值的类型必须是一样的,都是a类型)
fst函数的类型:

Prelude> :t fst
fst :: (a, b) -> a

可以看到fst取一个包含两个型别的 Tuple 作参数,并以第一个项的型别作为回传值。这便是 fst 可以处理一个含有两种型别项的 pair 的原因。注意,a 和 b 是不同的型别变量,但它们不一定非得是不同的型别,它只是标明了首项的型别与回传值的型别相同。

Typeclass

如果一个类型属于某个typeclass,那它必定实现了Typeclass所描述的行为。

tip: 跟OOP中的接口很像

==函数的类型声明为例:

Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool

这里的Eq就是typeclass, 这里意思是说a这个type必须是Eq的一个实现(相当于OOP中的a implement Eq)
=>符号左边的部分叫做类型约束

Eq这个Typeclass提供了判断相等性的接口,凡是可比较相等性的类型必定属于Eq class

elem函数的类型为:(Eq a)=>a->[a]->Bool这是因为elem函数在判断元素是否存在于list中时使用到了==的原因。

Show的成员为可用字符串表示的类型,操作Show Typeclass最常用的函数表示show。它可以取任一Show的成员类型并将其转为字符串

Prelude> show [1,2,3]
"[1,2,3]"
Prelude> show True
"True"

ReadShow相反,read函数可以将字符串转为Read的某成员类型

Prelude> read "5" - 2 
3
Prelude> read "True" || False
True

但是执行下面的代码,就会提示错误:

Prelude> read "5"
*** Exception: Prelude.read: no parse

这是因为haskell无法推导出我们想要的是一个什么类型的值,read函数的类型声明:

Prelude> :t read
read :: Read a => String -> a

它的回传值属于Read Typeclass,但是如果我们用不到这个值,它就无法推导出这个表达式的类型。所以我们需要在表达式后跟::的类型注释,以明确其类型:

Prelude> read "5" :: Int
5
阅读全文 »

Haskell 基础

第一个函数

创建doubleMe.hs文件,编写如下代码:

doubleMe x = x + x

保存,打开ghci,输入

Prelude> :l doubleMe.hs

这样我们就加载了我们的doubleMe函数,然后就可以调用这个函数:

Prelude> doubleMe 10
20

tip: 如果修改doubleMe.hs文件需要重新导入的话可以执行:reload doubleMe.hs或者:r doubleMe.hs重新导入

if语句

Haskell中的if语句与其他语言不同,else是不可以省略的

doubleSmallNum x = if x > 10 then x else x * 2

Haskell 中的 if 语句的另一个特点就是它其实是个表达式,表达式就是返回一个值的一段代码:5 是个表达式,它返回 5;4+8 是个表达式;x+y 也是个表达式,它返回 x+y 的结果。正由于 else 是强制的,if 语句一定会返回某个值,所以说 if 语句也是个表达式。

List

列表由方括号以及被逗号间隔的元素组成:

Prelude> [1,2,3]
[1,2,3]

空列表:[],列表中所有元素必须是同一类型。

列表操作符

用 ++ 操作符连接两个list

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

用 : 连接一个元素到list头,它读作“cons”即construct简称

Prelude> 1:[2,3]
[1,2,3]

但是[2,3]:1是不被允许的,因为:的第一个参数必须是单个元素,第二个参数必须是list

字符与字符串

Prelude> "this is string"
this is string

双引号表示字符串。单个字符用”表示

Prelude> 't'
t

字符串实际是字符列表,

Prelude> 't' : "his is string"
this is string
Prelude> "this is" ++ " string"
this is string

操作

从list中取值使用!!(相当于其他语言中的arr[index])

Prelude> let l = [1,2,3]
Prelude> l!!1
2

上面的例子就是从列表l中取下标为1的元素
list可以用来装list:

Prelude> let l = [[1,2,3], [1,2,3,4], [1,2,3,4,5]]

haskell不要求每个元素的长度一致,但要求类型必须一致

  • head函数取list第一个元素
  • tail函数取list除第一个元素之后的全部
  • last返回list最后一个元素
  • init返回一个除去list最后一个元素的全部
  • length返回list长度
  • null判断list是否为空,如果是空返回True,否则False
  • reverse 反转list
  • take 返回前几个元素
  • maximum 返回最大元素
  • minimun 返回最小元素
  • sum 返回所有元素之和,product返回积
  • elem 判断一个元素是否存在于list中,通常中缀调用
Prelude> tail [[1,2,3], [1,2,3,4], [1,2,3,4,5]]
[[1,2,3,4], [1,2,3,4,5]]
Prelude> init [[1,2,3], [1,2,3,4], [1,2,3,4,5]]
[[1,2,3], [1,2,3,4]]
Prelude> reverse [1,2,3]
[3,2,1]
Prelude> take 2 [1,2,3]
[1,2]
Prelude> 1 `elem` [1,2,3]
True

Range

可以用列表符号来表示一系列元素,haskell会自动推导:

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]

Prelude> [1.0, 1.25, ..2.0]
[1.0,1.25,1.5,1.75,2.0]

Prelude> [1, 4, 15]
[1, 4, 7, 10, 13]

之所以没有输出15是因为15不属于我们定义的系列元素

List Comprehension

Prelude> [x*2 | x <- [1...10]]
[2,4,6,8,10,12,14,16,18,20]

可以给这个comprehension加个限制条件:

Prelude> [x*2 | x <- [1...10], x*2 > 12]
[14,16,18,20]

下面写一个函数,该函数使list中所有>10的奇数变为”BANG”,小于10的奇数变为BOOM:

bangBoom xs = [if x > 10 then "BANG" else "BOOM" | x <- xs, odd x]

tip: odd函数判读x是否是奇数,如果是则返回True

还可以从多个list中取元素:

[x*y | x <- [1,2,3], y <- [4,5,6]]
[4,5,6,8,10,12,12,15,18]

实现自己的length函数:

length' xs = sum [1 | _ <- xs]

_表示我们不会用到这个值
操作含有 List 的 List

Prelude> let xxs = [[1,3,5,2,3,1,2,4,5],[1,2,3,4,5,6,7,8,9],[1,2,4,2,1,6,3,1,3,2,3,6]]
Prelude> [ [ x | x <- xs, even x ] | xs <- xxs]
[[2,2,4],[2,4,6,8],[2,4,2,6,2,6]]

Tuple

(1,2)      (True, "a", 1)

Tuple List:

[(1,2),(3,4),(5,6)]

但是[(1,2),(3,4,5),(5,6)]是会报错的,因为元素类型不一致
两个元素的Tuple可以称为序对(Pair) Tuple不能是单元素的,因为没有意义

操作函数

  • fst 返回序对的首项(只能操作序对,不能操作三元组等其他数量的Tuple)
  • snd 返回序对的尾项
Prudule> fst (1,2,[1,2,3])
1
Prudule> snd (1,2,[1,2,3])
[1,2,3]
  • zip 将两个list交叉配对生成一组Pair
Prudule> zip [1 .. 5] ["one", "two", "three", "four", "five"]
[(1,"one"),(2,"two"),(3,"three"),(4,"four"),(5,"five")]
Prudule> zip [5,3,2,6,2,7,2,5,4,6,6] ["im","a","turtle"]
[(5,"im"),(3,"a"),(2,"turtle")]

若是两个不同长度的 List,较长的那个会在中间断开,去匹配较短的那个

阅读全文 »

ghci中的一些命令与case 【持续更新...】

ghic中模式匹配

按照rwh书中模式匹配一节中sumList的例子在ghci敲出这样的代码:

Prelude> sumList (x:xs) = x + sumList xs
Prelude> sumList [] = 0

调用这个函数时是会报一个错误的:

Prelude> sumList [1,2,3]
*** Exception: <interactive>:2:1-14: Non-exhaustive patterns in function sumList

而实际如何要在ghci中做一个模式匹配函数的话应该这样写:

Prelude> let { sumList' [] = 0; sumList' (x:xs) = x + sumList' xs }
Prelude> sumList' [1,2,3]
6

ghci中切换工作目录与查看当前工作目录

Prelude> :cd /tmp/
Prelude> :show paths
current working directory: 
  /tmp
module import search paths:
  .

使用:cd 命令切换到指定目录
使用:show paths目录查看当前工作目录

阅读全文 »

Haskell 自定义type与typeclass

前言

在看《Haskell趣学指南》这本书的Build Our Own Type and Typeclass一章时,不是很好理解,这里结合《Real World Haskell》这本书做一下记录。

自定义type

Part One

Haskell中使用data关键字来定义新的数据类型:

data BookInfo = Book Int String [String] deriving (Show)

那么如何解读上面的表达式呢? 首先data关键字后边的BookInfo是新类型的名字,我们称BookInfo为*类型构造器*。类型构造器用于指代(refer)类型。类型名字的首字母必须大写,因此类型构造器的首字母也必须大写。 接下来的Book是*值构造器*(或者称:*数据构造器*)的名字,类型的值就是由值构造器创建的。 Book之后的Int String [String] 是类型的组成部分 在这个例子中,Int表示书ID, String表示书名,[String]表示作者

上面的描述其实很像OOP中的累的构造方法,BookInfo部分类似于OOP中的class,上文中的值构造器类似于class的构造方法,Book可以认为是构造方法的方法名,java等一些语言中构造方法是与class是同名的,但是Haskell中很明显没有这种约束,Haskell中类型构造器和值构造器的命名是独立的, 所以其实值构造器是可以与类型构造器同名的,即上面的例子可以写成:data BookInfo = BookInfo Int String [String]

可以将值构造器看作是一个函数:它创建并返回某个类型的值。下面的例子中我们将Int String [String] 三个类型的值应用到Book, 从而创建一个BookInfo类型的值

csapp = Book 123456 "Computer Systems: A Programmer's Perspective" ["Randal E.Bryant", "David R.O'Hallaron"] 

使用 :info 命令查看更多关于给定表达式的信息

:info BookInfo

类型别名

上面BookInfo类型的例子中,Int String [String] 一眼看不出来这三个成分是干什么用的,通过类型别名可以解决这个问题:

type BookId Int
type BookName String
data BookInfo = Book BookId BookName [String]

这样是不是一目了然了呢。 > 跟golang中的type关键字或者c/c++中的typedef 很像

类型别名也可以有参数

type AssocList k v = [(k,v)]
type IntMap v = Map Int v
type IntMap = Map Int

algebraic data type

Bool类型是代数数据类型的一个典型代表,一个代数类型可以有多个值构造器

data Bool = False| True

以此为例我们可以说Bool类型由True值或False值构成 下面是《Haskell趣学指南》中的例子:

data Shape = Circle Float Float Float | Rectangle Float Float Float Float

意思是图形可以是圆形或者是长方形

Record Syntax

比较好理解暂不做过多说明,后续再补坑

Type parameters

列表类型是多态的:列表中的元素可以是任何类型。我们也可以给自定义的类型添加多态性。只要在类型定义中使用类型变量就可以做到这一点。Prelude 中定义了一种叫做*Mayb*的类型:它用来表示这样一种值——既可以有值也可能空缺,比如数据库中某行的某字段就可能为空。

data Maybe a = Nothing | Just a         -- Defined in ‘GHC.Maybe’

递归定义

一个代数数据类型的值构造器可以有多个field,我们能够定义一个类型,其中他的值构造器的field就是他自己,这样我们可以递归的定义下去。我们可以这样定义我们的List:

data List a = Empty | Cons a (List a) deriving(Show,Read,Ord) 

用record syntax表示:

data List a = Empty | Cons {headList::a, tailList::List a} deriving(Show,Read,Ord) 
ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))
Cons 3 (Cons 4 (Cons 5 Empty))

我们可以只用特殊字符来定义函数,这样他们就会自动拥有中缀的性质,同样的我们可以套用在值构造器上,因为他们不过是回传类型的函数而已

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Eq, Read, Ord)

定义函数成operator时能够同时指定fixity(不是必须的)。fixity指定了他应该是left-associative还是right-associative,还有他的优先级。infixr是右结合,infixl是左结合,infix无左右优先性。优先级0-9。例:*的fixity是infixl 7,+的fixity是infixl 6, infixl代表他们都是left-associative,但是*的优先级大于+。

这样我们就可以这样写:

ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> 100 :-: a
(:-:) 100 ((:-:) 3 ((:-:) 4 ((:-:) 5 Empty)))

haskell在deriving Show的时候仍然会视值构造器为前缀函数,因此要用括号括起来

构造自己的Typeclass

首先看一下Eq是怎么被定义的:

class Eq a Where
    (==) :: a->a->Bool
    (/=) :: a->a->Bool
    x == y = not (x /= y)
    x /= y = not (x == y)

tip: 上面的代码是书中给出的而在ghci中打印出来实际是下面这样的:

Prelude> :info Eq
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  {-# MINIMAL (==) | (/=) #-}
        -- Defined in ‘GHC.Classes’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Eq Word -- Defined in ‘GHC.Classes’
instance Eq Ordering -- Defined in ‘GHC.Classes’
...

解释下:class Eq a where代表我们定义了一个typeclass叫做Eq,a是一个类型变量,他代表任何我们在定义instance时的类型,接下来我们定义了几个函数,不一定要实现函数但一定要写出函数的类型声明。

下面看下这个类型:

data TrafficLight = Red | Yellow | Green

这里定义了一个红绿灯的类型,该类型目前还不是任何class的instance。虽然通过derive可以让它成为Eq或者Show的instance,但在这里我们手动实现:

instance Eq TrafficLight where
    Red == Red = True
    Green == Green = True
    Yellow == Yellow = True
    _ == _ = False

instance关键字用来说明我们定义某个typeclass的instance。

由于==使用/=来定义的,同样/=使用==定义的,所以我们只要在instance中复写其中一个就好了。我们这样叫做定义了一个minimail complete difinition。这是说能让类型符合class行为所最小实现的函数数量。而Eq的minimal complete difinition需要==或者/=实现其中一个。而如果Eq这样定义:

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool

当我们定义instance时就需要实现两个函数。所以minimal complete difinition就是==和/=。

我们再来写Show的instance,要满足Show的minimal complete difinition需要实现show函数,它接收一个值返回一个字符串

instance Eq TrafficLight where
    show Red = "Red light"
    show Yellow = "Yellow light"
    show Green = "Green ligth"

subclass

可以把typeclass定义成其他typeclass的subclass,Num的class声明就有点长:

class (Eq a) => Num a where
    ...

我们可以在很多地方加上类型约束,这里就是在class Num where 中的a上加上它必须是Eq instance的约束。其实这可以理解为在定义Num这个class时,必须先定义他为Eq的instance。

泛型instance

Maybe或者List这种与TrafficLight不同,Maybe是一个泛型。它接收一个类型参数(像是Int)从而构造出一个具体的类型。从Eq的typeclass的声明中可以看到a必须是一个具体的类型,而Maybe不是一个具体的类型我们不能写成这样:

instance Eq Maybe where
    ...

下面的代码虽然Maybe m 是一个具体的类型但是还有一个问题,那就是无法保证Maybe装的东西可以是Eq

instance Eq (Maybe m) where
    Just x == Just y = x == y
    Nothing == Nothing = True
    _ == _ = False

所以还应该加上一个类型约束:

instance (Eq m) => Eq (Maybe m) where
    Just x == Just y = x == y
    Nothing == Nothing = True
    _ == _ = False

大部分情况下class声明中的类型约束都是要让一个typeclass成为另一个typeclass的subclass。而在 instance 宣告中的 class constraint 则是要表达型别的要求限制。

如果想看一个 typeclass 有定义哪些 instance。可以在 ghci 中输入 :info YourTypeClass。所以输入 :info Num 会告诉你这个 typeclass 定义了哪些函数,还有哪些类型属于这个 typeclass。:info 也可以查找类型跟类型构造器的信息。如果你输入 :info Maybe。他会显示 Maybe 所属的所有 typeclass。:info 也能告诉函数的型别宣告。

Functor typeclass

首先看下Functor这个typeclass

class Functor f where
    fmap :: (a -> b) -> f a -> f b

tip: ghci 8.8.1中打印结果如下:

Prelude> :info Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
        -- Defined in ‘GHC.Base’
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’

可以看到typeclass中的类型变量f并不是一个具体的类型,而是类似于Maybe这样的泛型。从上面我们可以看到fmap接收一个从a类型映射到b类型的函数和一个装有a类型值的functor,返回一个装有b类型值的functor

看下学list时学到的map函数:

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

它接收一个从a类型映射为b类型的函数,和一个装有a类型值的List返回一个装有b类型值的List

是不是很像fmap,不错,List正是一个Functor的instance,而map就是fmap的实现(这一点看下ghci中:info Functor的打印结果就能确认)。

同样的Maybe也是Functor的一个instance:

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing

看到这不免有些疑问,为什么上面instance Eq Maybe where不行在这里写成instance Functor Maybe where就行了呢?原因是Functor要接收的是一个泛型,而不是一个具体的类型。如果把f替换成Maybe,fmap就像是这样:(a -> b) -> Maybe a -> Maybe b,如果像上面将Eq时一样将f替换成Maybe m的话就会成这个样子了:(a -> b) -> Maybe m a -> Maybe m b 这显然是不对的。

如果一个泛型是接收两个参数的呢,以Either a b为例,可以这样写:

instance Functor (Either a) where
    fmap f (Right x) = Right (f x)
    fmap f (Left x) = Left x

就是把Either a作为Functor的一个instance(Either不能作为Functor的instance)

Kind

泛型(型别构造子)接收其他类型作为它的参数来构造出一个具体的类型。这有点像函数,也是接收一个值作为参数并回传另一个值。对于类型如何被套用到泛型上,我们看下正式的定义。
像是3,"abc"或者是takeWhile的值都有自己的类型(函数也是值的一种)。类型是一个标签,值会把它带着,这样我们就能推导出它的性质。但类型也有自己的标签,叫做kind,kind是类型的类型。

我们可以在ghci中通过:k来获取一个类型的kind:

Prelude> :k Int
Int :: *

*代表这个类型是具体类型。一个具体类型是没有任何类型参数的,值只能属于具体类型。*的读法叫做star或是type。

我们再看下Maybe的kind:

Prelude> :k Maybe
Maybe :: * -> *

可以看到Maybe的类型构造子接收一个具体类型(像是Int)然后返回一个具体类型。就像Int -> Int代表这个函数接收Int并返回Int。* -> *代表这个类型构造子接收一个具体类型并返回一个具体类型。我们再对Maybe套用类型参数后再看看它的kind:

Prelude> :k Maybe Int
Maybe Int :: *
阅读全文 »

centos搭建git服务器

一、安装

  1. sudo yum install curl-devel expat-devel gettext-devel openssl-devel zlib-devel sudo yum install gcc perl-ExtUtils-MakeMaker

  2. 安装 sudo wget https://github.com/git/git/archive/v2.9.2.tar.gz sudo tar -zvxf v2.9.2.tar.gz cd git-2.9.2 sudo make prefix=/usr/local/git all sudo make prefix=/usr/local/git install

  3. 将git设置为默认路径,不然后面克隆时会报错 sudo ln -s /usr/local/git/bin/git-upload-pack /usr/bin/git-upload-pack sudo ln -s /usr/local/git/bin/git-receive-pack /usr/bin/git-receive-pack

  4. 添加git用户和用户组用来运行git服务

    sudo groupadd git
    sudo useradd git -g git
    sudo passwd git
    su - git
    

    二、创建证书登录

  5. cd /home/git
    mkdir .ssh
    chmod 700 .ssh
    touch .ssh/authorized_keys
    chmod 600 .ssh/authorized_keys
    将公钥导入到authorized_keys
    
  6. 初始化Git仓库

    cd /data
    mkdir gitrepo
    chown git:git gitrepo/
    cd gitrepo
    git init --bare starins.git
    chown -R git:git starins.git
    

    三、使用

    git clone ssh://git@ip:port/data/gitrepo/starins.git

阅读全文 »