从Jekyll迁移到Hugo

最近把博客从Jekyll迁移到了Hugo,在这里记录一下。

之前一直使用Jekyll,最大的原因是Github Pages原生支持Jekyll, repo里只管理源代码就可以,不需要上传build之后的文件。 不过Jekyll也有许多不尽如人意的地方,主要是一下几点:

  • 本地开发环境不容易配置。 没有直接的可执行文件,需要安装ruby,gem,之后再安装jekyll
  • Github Pages的build配置不能按照自己的需求定制。 各种依赖的版本不能自己选择,也不能根据使用Jekyll的一些插件
  • 编译速度慢。 因为本站的文章太少,这一点倒是不是什么问题

内容迁移

博客从Jekyll迁移到Hugo,在考虑主题迁移的情况下,还是比较简单的。 Hugo的命令行可以直接从Jekyll导入文章,

hugo import jekyll /path/to/jekyll/root /target/path

这样可以直接导入文章,Jekyll中其他的静态文件会被放到static文件夹中。 这个命令比较简单,但并没有把所有事情干完。只是把Jekyll中的文章放到了Hugo中, 并且根据文件名里的时间,放到了front matter中,其他并没有改动。 文件名也仍然需要自己手动修改,去掉时间。

此外,Hugo使用的markdown,在语法上也与Jekyll有些差异,渲染出来的html也是有些不同。 这里可以在Hugo的配置文件里进行修改,也可以修改文章的语法。

自动编译

使用Jekyll的时候其实是不需要这一步的,直接推到github上就行了。 使用hugo,如果每次都是本地编译,然后把编译后的html文件推到github, 那就太不方便了。而且这样也不利于源码文件的管理。

Travis CI

Travis CI是持续集成服务,并且对于Github上的public repo是免费使用的。 利用Travis CI,可以达到每次push到Github上的时候,自动build, 并推送到repo的特定的分支。

首先需要在Travis CI上开启repo的自动集成,然后在repo里添加.travis.yml。 Travis CI会根据这个文件,进行build。根据Travis CI的文档, build过程分为几个阶段。一个静态博客的build,比较简单, 也不用所有的过程都用上。在install阶段安装hugo,script阶段调用hugo进行编译, after_success阶段把生成的文件推到github上。这是本站的使用的配置。

# .traivs.yml
language: go
go:
 - '1.10'
branches:
  only:
  - source # 只有source分支的推送才触发构建
install:
  - wget /path/to/hugo/releases -O /tmp/hugo.tar.gz
  - mkdir -p bin
  - tar -xvf /tmp/hugo.tar.gz -C bin
script:
  - bin/hugo
after_success:
  - sh .travis/push.sh
# push.sh
setup_git() {
    git config --global user.name "travis@travis-ci.org"
    git config --global user.email "Travis CI"
}

commit_files() {
    git init
    git add .
    git commit -m"Travis build: $TRAVIS_BUILD_NUMBER"
}

push() {
    git remote add origin https://${GH_TOKEN}@github.com/yourname/yourrepo.git
    git push -f -u origin master
}

cd public
setup_git
commit_files
push

由于Travis CI并没有repo的push权限,所以直接推到repo上是会验证失败的。 push.sh里,GH_TOKEN是有public_repo权限的personal access token, 可以在https://github.com/settings/tokens申请,并在Travis CI上设置。

至此,Travis CI的自动build就完成了。

Synchronized的内存屏障

问题

在V2EX上看到这样一个问题,具体来说,就是下面这份代码,注释和不注释,为什么运行会有不同

public class MyRun implements Runnable {

	private boolean stop;

	MyRun(boolean status) {
		this.stop = status;
	}

	@Override
	public void run() {
		while(!stop) {
			// System.out.println("running");
		}
		System.out.println("stop");
	}

	public void setStop(boolean stop) {
		this.stop = stop;
	}
}

// 测试代码
MyRun myRun = new MyRun(false);
new Thread(myRun).start();
Thread.sleep(1000); // 等待线程执行
myRun.setStop(true);

这个代码目的就是通过主线程修改变量,控制子线程的运行。 为了这个目的,很显然stop需要添加volitale关键字,表明stop是多线程可见的。 那么,子线程在读取stop的时候,会从先把主内存的变量同步到自己的工作内存,然后再使用, 因而可以拿到最新的stop的值。

抛开volatile不谈,单独这份代码,注释和不注释下,运行结果也有很大差异。

  • 注释的情况下,子线程没有得到stop的最新值,其工作内存中的stop一直是false,因此程序死循环。 这和预期情况一致。
  • 不注释的情况下,程序会一直输出running,知道1秒后,输出stop。显然子线程获得到了stop的最新值。 这里的我就不太理解了,为什么呢?

syncronized

最开始我以为是IO引起的用户态内核态切换,会导致从主存中同步,不过查了一圈资料,这个猜想是错误的。

println函数在jdk里的实现是这样的

public void println(String x) {
    synchronized (this) {
        print(x);
        newLine();
    }
}

里面有个synchronized,估计就是和这个有关了。

手头有本《深入理解Java虚拟机》(简称书),里边关于Java的内存模型, 有这样的说法

同步块的可见性是由“对一个变量执行unlock操作之前,必须先把此变量同不会主内存中(执行store、wirte操作)”这条规则获得的。

但是这个说法和这里用法不一样,因为书中说法,意思是退出同步块之前,要把synchronized的对象同步会主内存。 而本问题中,同步块锁住的对象this,是指System.out这个对象,并不是myRun

JSR 133 FAQ中,有如下说法

Before we can enter a synchronized block, we acquire the monitor, which has the effect of invalidating the local processor cache so that variables will be reloaded from main memory. We will then be able to see all of the writes made visible by the previous release.

这说明synchronzed可以是使本地CPU缓存失效,从而从主内存中读取最新的变量值。 但是后面的有一个*Important Note*,表明只有释放和获取的是同一把锁,才能保证happen before关系, 又让我对这段胡的理解产生了疑问。 在stackoverflow上,有一个关于这段话的提问,但是并没有让我更明白。

之后又去看Java语言规范中关于内存模型的部分。 在Java语言规范17.1节,关于synchronized块,有如下说明

attempts to perform a lock action on that object’s monitor and does not proceed further until the lock action has successfully completed

这里的一个重点是lock action,这章中只说明lock的意思是locking a monitor,并没有具体的解释。 书中写到Java内存模型有8个操作,其中一个就是lock,但是Java语言规范中并没有相关说明。 最后在Java6的虚拟机规范第8章中,才找到对其的说明,并有一个对于本问题的重要的规则

Let T be any thread, let V be any variable, and let L be any lock. There are certain constraints on the operations performed by T with respect to V and L:

  • Between a lock operation by T on L and a subsequent use or store operation by T on a variable V, an assign or load operation on V must intervene; moreover, if it is a load operation, then the read operation corresponding to that load must follow the lock operation, as seen by main memory. (Less formally: a lock operation behaves as if it flushes all variables from the thread’s working memory, after which the thread must either assign them itself or load copies anew from main memory.)

这个规则说明,synchronized可以保证其工作内存中的变量都是最新版本。对于本问题,对System.out的锁, 更新了工作内存中的值,从而退出循环。

不过,在Java7和Java8的虚拟机规范中,这一章被移除了,并将相应的内容放到了Java语言规范中, 也就是上文所引用的第17章中。但是我并没有在其中找到与这个规则具有相同意义的规则。 不知道哪里漏了。

变体

把问题中的run方法改一下,变成

public void run() {
    while(!stop) {
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    System.out.println("stop");
}

实际上也是会最后输出stop的。但是Java语言规范中明确表示,

It is important to note that neither Thread.sleep nor Thread.yield have any synchronization semantics. In particular, the compiler does not have to flush writes cached in registers out to shared memory before a call to Thread.sleep or Thread.yield, nor does the compiler have to reload values cached in registers after a call to Thread.sleep or Thread.yield.

也就是说Thread.sleep是不需要刷新工作内存的。 但是这里仍然打印了stop,说明在某种情况下,线程冲主内存同步了变量。 由于这并不是Java的规范,所以这是和JVM的具体实现相关,因此并不能依赖于这一点。

总结

Java的内存模型之前看过,但是并不是非常清楚。这次前后查了好多,也有了更多的理解。 并且还有个问题并没有搞清楚,Java8的规范里,哪条规则能够明确的推导出Java6关于lock的规则。 这个就慢慢再看吧

Updated

原贴下有贴出了一个链接,感觉说得刚靠谱。JVM虚拟机做了优化,会尽可能的保障工作内存与主内存的同步。 这样就解释了synchronizedsleep时,线程能够获取到最新变量。

想想还是太naive了,还是要多学多看啊

JDK源码阅读之String

这几天看了看Java的String的实现。Java中的所有的String字面量都是String类的实例。 文件注释中写到了,字面量生命String s = "abc"

char[] data = new char[]{'a', 'b', 'c'};
String s = new String(data)

效果是一样的。这应该是JVM来实现的。

接口

String实现了三个接口,分别是SerializableComparable<String>CharSequenceSerializable用于序列化,Comparable<String>用于比较, CharSequence则是String的一个更通用的抽象。

属性

String最重要的属性是private final char value[]value中存放着String的实际内容。 此外,Java的char的长度是16bit,两个字节。 另外一个属性是private int hash,是String得哈希值,默认为0。hash在调用hashCode()时计算, 因此不是final

构造方法

String的构造方法分为几类 * 无参构造方法,得到的就是空的字符串 * 参数是String的,直接对valuehash赋值 * char[]相关的,这类方法进行越界检查,由于String是不可变的,还会复制数组 * int[]相关的,这里的参数是Unicode的codePoint,因为Unicode是4字节的,所以使用了int。 对于基本平面(BMP)的字符,只需要char即可。对于辅助平面的字符,一个codePoint,需要两个char才能存下。 * byte[]相关的,所有从byte[]转为String的,都需要指明编码格式。 曾经有过不需要指明编码格式的方法,但是现在已经Deprecated了,因为有bug。 * StringBuilderStringBuffer,具体实现上都是复制数组,StringBuffer加了锁 * String(char[] value, boolean share),这是一个特殊的构造方法,这个方法可访问性是包内可见。 为了性能上的考量,实现上不做数组复制,只是简单的赋值。调用的时候,share一定是true

方法

所有方法方法中,涉及到可能产生新的字符串的,都会先检查参数,是否可以直接返回自身。

  • length直接返回value.length
  • isEmpty判断value.length == 0
  • hasCode返回hash,如果没有计算过,用times31算法计算,并保存结果
  • equals,不比较hashCode,直接按序比较字符
  • 其他比较相关的方法,
    • 定义了内部静态类CaseInsensitiveCompartator,用于处理大小写不敏感的比较
    • 基本上都是从前向后遍历
    • compareTo方法是按照Unicode字典序比较的,有不同则返回不同的字符的差,否则返回长度的差
  • indexOf(int ch, int fromIndex)
    • indexOf(ch) == indexOf(ch, 0)
    • 先判断ch,如果是负值(非法值)或者BMP字符,从前到后扫一遍
    • 否则是辅助平面字符,从前到后扫,比较前导代理以及后尾代理
  • indexOf(String s, int fromIndex)
    • 实现上,先找到第一个字符,然后比较余下字符。不断循环
    • 效率上比较低下,stackoverflow有个讨论,我觉得还是有道理的
  • contains,判断indexOf() > -1
  • matches,调用Pattern.matches
  • split(String regex, int limit)
    • limit表示分割后的数组的长度,若0,表示不限制结果的个数。默认为0
    • 实现上,如果regex是简单的字符串
    • 单个字符,并且不是正则表达式的元字符
    • 两个字符,第一个是'\\',并且第二个不是ascii字母和数字
    • 从前到后扫,调用indexOf
    • 否则调用Pattern
    • 空的字符串会返回
    • 但是,split方法有个坑,就是最后一个分隔符后面如果没有其他字符,那么是没有最后一个空字符串的
    • "hello,,yes,".split(",") == ["hello", "", "yes"]
  • join,静态方法,调用StringJoiner
    • null会按照"null"处理
  • concat(str),不检查参数,如果为null会报异常,如果str.length != 0,开辟新的数组。
    • 只调用一次数组复制,
  • substring,检查之后复制数组。之前某个版本好像是没有复制数组,导致了内存泄漏
  • trim,实现上是去除了前后的所有ascii码小于等于20的字符
  • replace
    • 字符替换,如果相同或者未发现,直接返回,否则遍历
    • 字符串替换,调用Pattern
  • 大小写转换相关方法的实现,考虑的东西比较多,实现比较复杂。涉及了Locale,未知名则使用系统默认的。 不同的语种,大小写规则不太一样,调用了ConditionalSpecialCasing进行实际的转换
  • toString,返回自己
  • toCharArray,调用System.arraycopy产生新的数组
  • valueOf系列
    • char[],调用构造函数
    • Object"nul"或者toString()
    • 内置类型,直接调用响应的toString()
  • native intern(),将自身添加到字符串池

2017之前

2016年,干了几件事,出去实习了,找到工作了,以及毕设相关。

先说实习,第一次是在腾讯。虽然我进去的之后的岗位也是研发实习生,但这个部门其实并不是一个做研发的部门,是做直播的,腾讯视频的一些的直播的技术支持部门,主要是体育赛事,还会有一些演唱会、新闻等等。由于不是研发部门,其实进去之后首先熟悉了演播室的直播设备,跟着值班了一段时间。除却这些直播技术,部门还负责直播的在线包装、场景设计,使用的广电行业的专用软件,Viz。我感觉Viz还是非常复杂,有各种插件用于实现各种功能,当这些插件无法实现所需要的功能时,Viz还提供脚本支持,可以编写一些复杂的动画、人机交互界面等等。这个脚本还是比较简单的,当时的leader说这个脚本其实就是VB差不多。Viz脚本其实想要招程序员的一个最重要的一点。不过由于我在腾讯的实习其实还是比较短,Viz脚本也没学多少。后来实习快结束的时候,又给我了一个开发一个内部使用的系统的任务。从2015年12月末开始,在腾讯实习了3个月多。由于不是研发部门,对研发的情况不是很了解,就我自己所在的部门,气氛是比较轻松的,也没有特别严格的作息要求。腾讯有专门的内部技术论坛,供工程师交流。

从腾讯离职之后,由师兄内推,又去了微软实习。部门是微软小冰。进去以后,我的座位是由一个会议室改的,是一个单间,与mentor的办公位不在一起,而且做的项目基本上是一个人项目,所以和其他同事的交流不多。实习期间,做了两个项目,一个是内部数据的在线编辑管理的系统吧,另一个是爬虫。第一个项目,实质上是增删改查,不过需要先把原有的文本文件的数据倒进来。而且需要有个界面,我选了Vue做前台,这里其实就是自己的选择,没有过多的比较,而且在腾讯做的项目也是用了Vue,还没忘光。第二个爬虫是mentor自己从头写的,我要做的就是增添一些功能。通过ssh远程在服务器上写,原因是用了一些库,只能在Linux上运行。因为这,把vim又好好学了一下。在微软实习,还是很轻松,没有压力,任务完成就行,mentor人也好。之后由于要开始找工作了,而且也要做毕设,就离职了。

大约8月初,各种内推就开始了,直到10月末签了三方,足足3个月。而且必须吐槽网易带了个好头,内推不免笔试,结果都成这个套路了。这段时间,除了吃饭睡觉,就是笔试面试和准备笔试面试。leetcode刷了绝大部分,没有像同学一样其他第二遍。还有就是各种基础吧,主要是笔试面试啥都问,数据库、网络、操作系统、jvm、Java的多线程、JDK的常用集合的实现各种各种,上到高并发设计,下到内存页表。经常投的Java岗,结果笔试还是一堆的c++、php。

我也也参加了不少面试,给我感觉最好的是Google和AirBnb,两者风格完全不同。Google应该是面试人数比较少,面试前后都会有电话通知,然后我就收到可面试挂了的电话。。面试官是外国人,为了面试专门飞过来的,很有经验,题目就是算法题,白板写。AirBnb 的面试官是中国人,但是面试要求说英语,一轮45分钟,大约15分钟的题目,剩下的30分钟写代码,是可运行的环境。这个是我最喜欢的方式。面试给我感觉不好的事华为和网易。华为是两面很奇怪,根本没有问一些有区分度的问题,结果就跪了。网易的面试过程还可以,但是安排比较乱,面试官和HR之间的信息沟通不畅,中间空等了好长时间。还有滴滴,虽然我没参加,但是今年的面试安排真的是一团shi。

至于论文,目的就是毕业了。自己对做科研还是没有太大的兴趣,写代码做工程更适合我。答辩时间改到明年3月,希望一切顺利!

用Rust写了一个简单的Web服务器

Rust

最近学了一阵Rust,这个语言的目的是系统编程,卖点是无GC的内存安全。为了实现这一点,Rust引入了所有权、借用、生命周期的概念。可以在编译器检查出可能的内存问题,如野指针、局部变量指针等等。不过这也对写程序造成了一定的困扰,对于move、borrow等如果理解的不是很到位,那必然要和编译器做长期的斗争。

Web服务器

骨架

Web服务器,实际上就是对socket的数据流的处理,监听端口,并对每个新的连接,开启一个新的线程进行处理。代码的骨架基本上是

match TcpListener::bind("127.0.0.1", 9999)) {
    Ok(listener) => {
        for stream in listener.incoming() {
            match stream {
                Err(e) => {
                    // error, log, ignore
                },
                Ok(s) => {
                    thread::spawn(move || handle_client(s));
                },
            }
        }
        drop(listener);
    },
    Err(e) => {
        // error, log, ignore
    }
}

其中thread::spawn(move || handle_client(s)),开启新的线程,参数是一个闭包,move关键字表示将闭包所在环境的标量的所有权强行交给闭包。之后重点是handle_client中对于TcpStream的处理,也就是解析请求,并构造响应。读取请求。

解析请求

一个HTTP的请求,格式是这样的

METHOD URI VERSION
Host: xxx
other-header: xxx

body

这个服务器目前只能处理GET和HEAD请求,并且只能处理静态文件,所有很多东西并没有做。比如querystring的解析、请求体的解析等等。各种header也只是解析,并没有真的使用。之后会慢慢完善,函数重点是

fn parse(stream: &mut TcpStream) -> Option<Request> {
    let mut s = Vec::new();
    Self::get_request(stream, &mut s);
    match String::from_utf8(s) {
        Ok(s) => {
            // parse request line and header
        },
        Err(_) => None,
    }
}

如果解析失败,返回一个None,这是Request结构的一个静态方法。解析成功则打印日志,并根据请求构造响应。

构造响应

响应的的格式为

VERSION CODE PHRASE
header: xxx
other-header: xxx

body

由于只能处理静态请求,实际上这里就是读取文件并.对于HEAD请求,只计算长度,没有响应体部分。

目前的相应的结构为

struct Response {
    head: String,
    body: String
}

通过code、mime、content等拼接字符串,得到响应头部以及响应体。最后通过TcpStream发送出去。

至此,这个web服务器就算是完成了。

最后

Rust这个语言还是非常不熟,对于lifetime的理解也太行,所以通篇没有用到lifetime标记,遇到字符串都是用的String。另外,Rust目前并没有高性能的非阻塞IO以及异步IO,有一些库在做这方面的尝试。不过对这方面不熟,没有多做尝试。

最后,项目的地址是https://github.com/iEverX/rock

利用注解实现依赖注入

准备

依赖注入是啥?

提到依赖注入(Denpendency Injection,DI),得先讲控制反转(Inversion of Control,IoC)。控制反转是一种设计原则,目的是去除代码的去耦合。通常写程序,我们会在类中实例化所需的对象,比如说

class Car {
    Tier tier = new Tier("A");
}

这里,Tier就是Car的一个依赖。像这种代码会造成一个问题,那就是TierCar之间是耦合在一起的。假如Tier的实现变了,增加了新的构造函数,原来的无参构造函数不满足Car的需求,那么就还需要修改Car的代码。如果换个方式,把代码改成下面这样

class Car {
    Tier tier;
    public void setTier(Tier tier) {
        this.tier = tier;
    }
}

那么就可以通过事先实例化一个Tier对象,通过setTier方法传给Car对象,Car的代码完全不需要修改。这就是控制反转,所谓反转,意思是依赖的控制被反转了。之前,依赖的生成有对象控制,现在依赖的生成由外层代码控制。上面的采用set方法的方式就称为依赖注入,还可以通过构造函数,或者通过接口实现。

注解

注解(Annotation)是Java在1.5版本提供的特性,通过注解可以给JVM提供额外的信息。这些额外的信息,可以在运行时获取,从而改变代码的行为。

代码实现

为了实现依赖注入,需要有以下几个东西

  • 标识一个属性通过外部注入的注解
  • 根据注解注入对象的代码
  • 一个保存组件的容器,以及生成的组件

其中最后一点就是Spring中的component-scan功能,不过我不会实现,所以本文的最后一点是手工完成的。

注解

代码很简单

@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface Inject {
    String value() default "";
}

这就OK了,一个注解就是这么简单。这里声明了一个名为Inject的注解,其关键字为@interface。与普通的接口不一样的地方是,不允许有属性,只能有方法,且方法不能有参数。此外,方法后可以跟一个default说明默认值。

在注解之上的TargetRetentionDocumented同样是注解,这些注解称为“元注解”,共有4个,除了以上三个还有一个Inherited。元注解用于对注解进行类型说明。

  • Target指明注解的使用范围,这里的ElementType.FIELD表明Inject可以注解属性,可选的值还包括TYPEPARAMETER
  • Retention指明注解的保留期限,RUNTIME表明在运行时可以获取注解信息。可选值还有SOURCECLASS,分别表示在源码和字节码中保留注解信息
  • Documented用来指明注解应该被文档化,指示javadoc之类的工具应该生成该注解的文档
  • Inherited指明注解可以被继承

Inject的定义很简单,其实可以更简单,那就是直接用Java自带的注解,比如Resource。因为注解本身不提供功能,注解功能的实现是由其他代码读取注解信息从而完成的。

使用注解

public class Car {

    @Inject
    private Tier tier;
    
    @Inject("james")
    private Driver driver;

    public void run() {
        System.out.println("A car is running, driver is " + driver.getName() + ", and its tier's brand is " + tier.getName());
    }
}

Tier的注解没有参数,说明给的是默认值,driver的注解加了参数,但是没有指明是哪个参数,这种情况下,默认使用value,当有多个参数时,不允许省略value。

读取注解并注入

static void inject(Object obj, Map<String, Object> container) {
    Field[] fields = obj.getClass().getDeclaredFields();
    for (Field field : fields) {
        field.setAccessible(true);
        Inject inject = field.getAnnotation(Inject.class);
        if (inject != null) {
            String name = inject.value();
            if (name.isEmpty()) {
                name = field.getName();
            }
            if (!container.containsKey(name)) {
                throw new RuntimeException("Object \"" + name + "\" cannot be found in container.");
            }
            try {
                field.set(obj, container.get(name));
            } catch (IllegalAccessException e) {
                // ignore
            }
        }
    }
}

这段代码通过反射获取一个类的所有字段,并获取字段上的Inject注解。如果有注解的情况下,依次根据注解的value以及属性的名字获取注入的对象名。并通过发射将对象赋给相应的属性。

实际运行

Map<String, Object> container = new HashMap<String, Object>();
container.put("james3", new Driver());
container.put("tier", new Tier());

Car car = new Car();
inject(car, container);
car.run();

在这里,通过inject方法将container中的对象根据需要注入到car中,无需car去管理对象的生成。注意到,这里的对象实例化都是有自己手动完成的。而且在实例化car时,依然自己手动调用了inject方法。所以这里简略的实现了一个依赖注入。为了自动实现以上想法,需要把car也放到container中。而container也应自动生成,可以通过扫描指定的包下的类来实现。个人感觉这里比较负责,不是很好写。具体可以参考Spring的实现。

总结

使用注解可以极大的增强代码的灵活性,而且使用注解也并不复杂,通过几个简单地API就可以完全搞定,真的是so easy!

Haskell Parsec的简短介绍[译]

本文翻译自http://unbui.lt/#!/post/haskell-parsec-basics/。这是我第一次翻译文章,这篇文章的英文看起来也不是很难,只是想尝试翻一下。由于第一次,许多地方的翻译并没有很通顺,整片文章读起来也是有些奇怪。此外代码中的注释没有翻译。以下是正文。

Parsec的存在使得在Haskell中解析文本非常简单。这篇文章的目的在于给我自己和其他人一个从零开始介绍每个函数,并配有例子的指南和参考。

首先,为什么要用Parsec而不是与之类似于正则表达式之类的东西来解析内容呢?其他语言中,把内容切分成数组,每次用正则表达式处理一部分,这种方式或者类似的其他方式,是一种非常常见的模式。在Haskell中,我们也可以采用这种方式,但是我已经看到了Parsec发出的光,我想把这种更好的方式介绍给你们。

大多数的指南都是上来就是一个完整的例子,但是我会一个一个的介绍这些不同的函数,以后这篇文章也可以作为一个使用Parsec的备忘(对我自己和所有其他人都是如此)。我尽量保证每个例子是独立的,所以跳过某些部分并不会有问题,但是请注意最开始的基础代码。我也把所有的例子的代码放到了这个文件中,可以直接使用:load命令读到ghci中使用。

基础

对于一个从头到尾的文本流,Parsec会尝试用一个规则或者规则的集合去匹配这个输入流。Parsec也是一个monadic,所以我们可以很容易把不同的规则通过do拼凑到一个序列中。一个一般的概念是,一个规则的工作方式是,每次从输入消费一个字符,并判断是否匹配。所以当把几个规则拼凑正一个序列时,每个规则会消费部分输入,直到没有输入、没有规则或者某个规则没有匹配(产生一个error)。

我们首先从最基本的开始。我qualified引入了Parsec,所以可以直接使用Parsec函数(注:无需使用包名前缀)。同时引入了Control.Applicative,因此稍后可以使用applicative形式的代码。最后给parseTest起了一个简短的别名。

-- I import qualified so that it's clear which
-- functions are from the parsec library:
import qualified Text.Parsec as Parsec

-- I am the error message infix operator, used later:
import Text.Parsec ((<?>))

-- Imported so we can play with applicative things later.
-- not qualified as mostly infix operators we'll be using.
import Control.Applicative

-- Get the Identity monad from here:
import Control.Monad.Identity (Identity)

-- alias Parsec.parse for more concise usage in my examples:
parse rule text = Parsec.parse rule "(source)" text

以上就是基本的设定,并定义了一个简单的函数parse,这个函数只是忽略了Parsec.parse的第二个参数(实际上,这个参数是带解析内容的文件名,只用于Parsec显示错误信息是能提供一些其他的信息)。

Parsec是有一系列的“积木”搭建起来的,每一块都是一个规则本身,或者是与其他规则一起组成的更复杂的规则。接下来我们看看这些基础的积木,以及它们是如何和上面的基本设定一起工作的。

Parsec.char

这个函数返回一个规则,该规则根据输入的参数,去匹配输入文本中的当前字符。我们ghci中运行一下。

ghci> someText = "Hello Hello Hello World World World"
ghci> parse (Parsec.char 'H') someText
Right 'H'
ghci> parse (Parsec.char 'e') someText
Left "(source)" (line 1, column 1):
unexpected "H"
expecting "e"

Parsec.char 'H'返回了一个会匹配单个字符'H'的规则。如果我们用这个规则匹配一个以H开头的字符串,结果是好的。如果尝试任何不是H的字母,就会失败。结果的类型总是Either ParsecError res,如果规则成功,则得到Right result,失败则得到Left error。我们可以试试模式匹配,例子非常简单:

main = do
    let result = parse (Parsec.char 'H') "Hello"
    case result of
        Right v -> putStrLn "success!"
        Left err -> putStrLn ("whoops, error: "++show err)

Parsec.string

这个函数返回的是尝试匹配字符串的规则:

ghci> parse (Parsec.string "hello") "hello world!"
Right "hello"
ghci> parse (Parsec.string "hello") "howdy"
Left "(source)" (line 1, column 1):
unexpected "o"
expecting "hello"

Parser从输入中一个一个的消费字符,直到所有的字符都匹配或者某一个字符与预期不符。因为上面的两个尝试都是以'h'开头,错误信息是遇到了unexpected 'o'。当多个规则串联在一起时,字符的消费(consuming of characters)会变得非常重要。

Parsec.oneOf

有时我们想要匹配多个字符,这时Parsec.oneOf就会非常方便。与Parsec.char相似,不过参数是[Char]类型:

ghci> parse (Parsec.oneOf "abcde") "allo"
Right 'a'
ghci> parse (Parsec.oneOf "abcde") "chewy"
Right 'c'
ghci> parse (Parsec.oneOf "abcde") "gnaw"
Left "(source)" (line 1, column 1):
unexpected "g"

可以看到,parser会消费abcde中的任意一个字符。这里我们可以用区间泪简化,比如可以使用Parsec.oneOf ['a'..'z']来匹配任意小写字母。

Parsec提供了规则来完成上面的目的,比如,Parsec.anyChar会消费任何字符:

ghci> parse Parsec.anyChar "blahblah"
Right 'b'
ghci> parse Parsec.anyChar "=-symbols..."
Right '='

规则Parsec.letter会消费任意字母,Parsec.lower会消费小写字母,Parsec.digit会消费数字,Parsec.alphaNum则是字母和数字。所有这些可以通过Parsec.oneOf来手动构建,不过这些提供了更好的错误提示信息(也可以在自己的规则里添加,我们稍后会看到)。

Parsec.noneOf

与上一个相反,这个函数的参数是不允许匹配的字符串,它会匹配任何一个不在参数中的字符。当然也可以使用区间:

ghci> parse (Parsec.noneOf ['0'..'9']) "hello"
Right 'h'
ghci> parse (Parsec.noneOf ['0'..'9']) "100"
Left "(source)" (line 1, column 1):
unexpected "1"

Parsec.many and Parsec.many1

我们有时候会希望不止解析一个字母,Parsec.many会不断尝试提供的规则,直到失败位为止。即使一次也没有成功,也不会返回失败,只是给出了一个空的结果。看看如何使用这个:

ghci> parse (Parsec.many (Parsec.char 'h')) "hhhheeelllooo!"
Right "hhhh"
ghci> parse (Parsec.many (Parsec.char 'e')) "hhhheeelllooo!"
Right ""
ghci> parse (Parsec.many Parsec.letter) "hhhheeelllooo!"
Right "hhhheeelllooo"

就像我们看到的,Parsec.many从来不会出错,它总是开心的匹配提供的规则0次,然后什么也不返回。它会尽量往前尝试,并且返回他匹配的任何东西。Parsec.many1类似,除了所给的规则至少匹配一次:

ghci> parse (Parsec.many1 Parsec.letter) "hello!!"
Right "hello"
ghci> parse (Parsec.many1 Parsec.letter) "75 hello's!"
Left "(source)" (line 1, column 1):
unexpected "7"
expecting letter

当想要匹配至少有一个字母或者数字的集合的时候,会非常有用。

Parsec.count

当想要匹配某个东西特定的次数时,可以使用Parsec.count。参数是一个数字n和一个规则,期望匹配这个规则相应的次数(或者失败),返回匹配的结果。来个例子:

ghci> parse (Parsec.count 4 Parsec.letter) "ahoythere"
Right "ahoy"
ghci> parse (Parsec.count 4 Parsec.letter) "aho"
Left "(source)" (line 1, column 4):
unexpected end of input
expecting letter

Parsec.manyTill

这个parser有两参数,尝试匹配的规则以及恰好在这个规则之后的规则。与many一样,第一个规则会匹配0次或者多次,但是如果两个规则都不匹配,会报错。下面的例子尝试匹配字母,并期望后面跟着数字:

ghci> parse (Parsec.manyTill Parsec.letter Parsec.digit) "hello12345"
Right "hello"
ghci> parse (Parsec.manyTill Parsec.letter Parsec.digit) "12345"
Right ""
ghci> parse (Parsec.manyTill Parsec.letter Parsec.digit) "hello 12345"
Left "(source)" (line 1, column 6):
unexpected " "
expecting digit or letter

注意,必须要记住,它会消费(并输出)所有的第一个规则,并且消费第二个规则匹配的任何东西(但是在输出中忽略)。当我们开始把规则串联起来,我们消费了什么,以及下一个规则要处理什么,会变得更加的重要。

我认为Parsec非常好的一点是,它提供了非常直接及时的错误信息,包括我们开头传的字符串("(source)"),错误的行号列号,以及一些指明哪里错了的有用信息。现在我们只处理了单行inxi,但是从单词的角度出发的酷。

组合规则

现在我们已经有了基本规则的经验了,接下来我们聊聊怎么把他们组合起来。Parsec,作为一个monadic,允许我们可以使用Haskell的do语法糖来写解析器。下面是一个把上面的简单规则拼凑成一个序列的例子,获取字母数字对并返回:

-- This looks for letters, then spaces, then digits.
-- we then return letters and digits in a tuple.
myParser :: Parsec.Parsec String () (String,String)
myParser = do
    letters <- Parsec.many1 Parsec.letter
    Parsec.spaces
    digits <- Parsec.many1 Parsec.digit
    return (letters,digits)

注意到我给显式的给了这个parser的类型Parsec.Parsec String () (String,String)。这个类型的参数类型,按按顺序来,是输入类型、想要在parser之间保持的一些状态(这里使用的是unit类型,也就是没有有意义的状态,稍后会快速的介绍一下),以及输出类型。在这个例子中,一个String作为输入,返回一个两个String的元组。在ghci中用:type查看这个规则的类型,会看到他们有ParsecT类型而不是Parsec类型构造的。ParsecT只是一个monad transformer,与Parsec.Parsec有相同的类型,但是有一个参数m来表明其包装的monad。无需多言,这两个类型是一样的:

-- I have to import the identity monad to use in the ParsecT definition:
import Control.Monad.Identity (Identity)

myParser1 :: Parsec.ParsecT String () Identity (String,String)
myParser1 = myParser

myParser2 :: Parsec.Parsec String () (String,String)
myParser2 = myParser

当在Parsec包中查看函数类型时,在脑子里记住这一点,会帮助你理解你在处理什么东西。每个规则都有相似的类型,虽然返回值各个规则都不一样。比如,Parsec.many返回一个所有匹配的数组。可以自己在ghci中看看。

不管怎么说,我们已经定义了myParser,可以把它传给parse函数了:

ghci> parse myParser "hello 1000"
Right ("hello","1000")
ghci> parse myParser "woohoooo0!!"
Right ("woohoooo","0")
ghci> parse myParser "1000"
Left "(source)" (line 1, column 1):
unexpected "1"
expecting letter

因为我们用的Parsec.many1,要求输入至少有一个字母,其后面跟着一个或者多个空格,最后跟着至少一个数字。我们的规则把这些包装成一个元组(但是也可以把他们包装成一个自定义类型或者任何 其他形式)。

假如我们有一系列的字母数字对,被一些分隔符分割,比如逗号。这个例子中,我们想要把他们解析成元组的列表。我们来定义一个解析分隔符的规则

mySeparator :: Parsec.Parsec String () ()
mySeparator = do
    Parsec.spaces
    Parsec.char ','
    Parsec.spaces

我又添加了显式的类型,因为当我在在测试文件中写独立的调用时,Haskell不能推断出类型。注意,只有最后一行是返回的东西,和签名的类型的是一致。其他之前的parser的返回值被忽略了。当然我们可以在一行显式的return (),不过Parsec.spaces已经做了这件事。

这个规则匹配0个或者多个空格,后跟一个逗号,再接着0或多个空格,由于我们不关心这些规则的返回值,我们可以把上面的代码脱糖成一行:

mySeparator = Parsec.spaces >> Parsec.char ',' >> Parsec.spaces

现在有了myParsermySeparator,每个都是由更小的规则构成的。用同样的方式,我们可以把新的规则组成更大的规则。还是根据上面学到的,来构建一个更冗长的规则:

--I want to return a list of pairs, this time.
myPairs :: Parsec.Parsec String () [(String,String)]
myPairs = Parsec.many $ do
    pair <- myParser
    mySeparator
    return pair

只是简单的用Parsec.many去解析0次或多次myParser后面跟着mySeparator的实例。注意,我用了do的语法糖来构建要给规则,之后把这个规则来传给Parsec.many。下面是脱糖的写法,可以清楚的看do块是Parsec.many的一个参数:

myPairs = Parsec.many (myParser >>= \pair -> mySeparator >> return pair)

鉴于Parsec.many返回一个列表(从类型签名的最后可以看出来),这个结果就是一个(String, String)的列表,我们来运行一下:

ghci> parse myPairs "hello 1, byebye 2,"
Right [("hello","1"),("byebye","2")]
ghci> parse myPairs ""
Right []
ghci> parse myPairs "hello 1, byebye 2"
Left "(source)" (line 1, column 18):
unexpected end of input
expecting digit, white space or ","

可以看到,使用Parsec.many,解析器发现没有匹配的实例,是不会报错的。但是如果一旦开始匹配输入了,失败(比如最后缺少了一个分隔符)就会导致报错。像这种普遍的分隔符分割项目的模式,有内置的函数专门进行处理。

Parsec.endBy

接受两个参数,一个解析项目的规则,一个解析分隔符的规则。本质上,Parsec.endBy和上面的函数一样,总是期望一个符合规则的字符串,然后一个分隔符,返回一个数组,元素是规则的返回值。

-- I want to return a list of pairs as above but using a built in helper:
myPairs2a :: Parsec.Parsec String () [(String,String)]
myPairs2a = Parsec.endBy myParser mySeparator

Parsec.sepBy

接受和和Parsec.endBy相同的两个参数,但是解析完最后一个项目之后,期望后面不跟着分隔符:

-- I want to return a list of pairs without a final separator:
myPairs2b :: Parsec.Parsec String () [(String,String)]
myPairs2b = Parsec.sepBy myParser mySeparator

这个规则不要求最后是一个分隔符(实际上,如果最后是个分隔符会报错(注:第二个例子不是原文的例子):

ghci> parse myPairs2b "hello 1, bye 2"
Right [("hello","1"),("bye","2")]
ghci> parse myPairs2b "hello 1, bye 2,"
Left "(source)" (line 1, column 16):
unexpected end of input
expecting white space or letter

使用Parsec.choice<|>匹配多个规则中的一个

使用Parsec.choice或者中缀操作符Parsec.<|>Control.Applicative中也有),我们可以解析不止一个规则,而第一个成功消费输入的规则会被使用(即使之后失败了也是如此,会得到一个警告)。我们来看看在实践上,它是怎么去掉我们的myParirs规则对结尾的分隔符的需要的:

--I want to return a list of pairs with an optional end separator.
myPairs2 :: Parsec.Parsec String () [(String,String)]
myPairs2 = Parsec.many $ do
    pair <- myParser
    Parsec.choice [Parsec.eof, mySeparator]
    return pair

现在,我们的规则会消费多个字母数字对,每个后面跟着一个文件结束标记(parsec提供的规则)或则我们定义的分隔符,可以使用中缀操作符:

import Text.Parsec (<|>)

myPairs3 :: Parsec.Parsec String () [(String,String)]
myPairs3 = Parsec.many $ do
    pair <- myParser
    Parsec.eof <|> mySeparator
    return pair

在这里我引入了<|>操作符,所以不用给它加前缀,也没有那么丑了。中缀操作符和Parsec.choices都支持多个选择,比如Parsec.choice [rule1, rule2, rule3] or rule1 <|> rule2 <|> rule3。在两个例子中,序列中第一个消费了输入的规则会被使用。由于接受文件结束标记或者我们自定义的分隔符,结尾不在需要分隔符了:

ghci> parse myPairs2 "hello 1, byebye 2,"
Right [("hello","1"),("byebye","2")]
ghci> parse myParis2 "hello 1, byebye 2"
Right [("hello","1"),("byebye","2")]

要记住,第一个消费了输入的规则会被使用,这点很重要。这也许会导致出乎意料的失败。比如下面这个例子:

parse (Parsec.string "hello" <|> Parsec.string "howdy") "howdy"

随便来个人可能会认为这个parser先尝试匹配"hello",并且会失败,然后在匹配"howdy"的时候回成功。而实际上,这个解析会完全的失败:

ghci> parse (Parsec.string "hello" <|> Parsec.string "howdy") "howdy"
Left "(source)" (line 1, column 1):
unexpected "o"
expecting "hello"

这是因为尝试匹配字符串"hello"时,Parsec.string "hello"创建的规则成功消费了'h',所以这个规则被选择使用,随后在下一个字符匹配失败。下面一个例子会更清楚:

ghci> parse (Parsec.string "hello" <|> Parsec.string "bye") "bye"
Right "bye"

这里,第一个规则在成功消费任何输入之前就失败了,所以第二个规则被选择没有任何问题。由于性能的原因,默认的情况下,Parsec不会“向前”看一个规则是否匹配。第一个解决方案(可能也是性能最好的)是将任何输入里相同的部分单独解析,然后再解析余下的部分,避免任何超前查看的行为,如:

ghci> parse (Parsec.char 'h' >> (Parsec.string "ello" <|> Parsec.string "owdy")) "howdy"
Right "owdy"

注意,由于忽略了第一个parser(消费了'h')的结果,所以没有返回整个字符串。如果有必要,这个是很容易改进的,可以把上面的一行标记改成一个更显式的规则:

helloOrHowdy :: Parsec.Parsec String () String
helloOrHowdy = do
    first <- Parsec.char 'h'
    rest <- Parsec.string "ello" <|> Parsec.string "owdy"
    return (first:rest)

通过手动决定哪些需要从规则里返回,我们可以通过把初始的字符加到余下的字符串上的方式来返回正确的字符串。现在错误也是基于每个规则尝试消费的部分而不是整个字符串,提升了精确性,但是可能损失了清晰性:

ghci> parse helloOrHowdy "hello"
Right "hello"
ghci> parse helloOrHowdy "allo"
Left "(source)" (line 1, column 1):
unexpected "a"
expecting "h"
ghci> parse helloOrHowdy "hoops"
Left "(source)" (line 1, column 2):
unexpected "o"
expecting "owdy"

第一个错来自Parsec.char,第二个则是Parsec.string。之后我们会展示如何提供自定义的错误信息,但我们先来看看超前查看这种更整洁的解析这些字符串的方式。

Parsec.try

当规则变得复杂时,避免超前查看会很快变得笨重。在这些情形下,我们可以命令Parsec尝试一个规则,并且如果规则匹配失败,则回退到之前的状态。Parsec.try就是做的这件事,它会catch任何失败,并且回退。考虑到性能的影响,最好是把超前查看保持在一个尽可能小的范围内,try函数中的可能的解析越少越好。Parsec.try把被包入的规则的报错信息都截获了,因此如果不正确使用的话,可能会导致产生奇怪并且没有任何帮助的错误信息。这个意思是,如果使用得当,我们能够体验到良好的错误信息的优点,我们来试一下:

helloOrHowdy2 :: Parsec.Parsec String () String
helloOrHowdy2 = Parsec.try (Parsec.string "hello") <|> Parsec.string "howdy"

这个会产生正确的解析,通常也会有更好的错误信息,但是既然任何一个解析"hello"的失败都被拦截了,错误信息只会描述choice操作符或者"howdy"的匹配失败,忽略配"hello"的匹配损失败:

ghci> parse helloOrHowdy2 "hello"
Right "hello"
ghci> parse helloOrHowdy2 "howdy"
Right "howdy"
ghci> parse helloOrHowdy2 "boo!"
Left "(source)" (line 1, column 1):
unexpected "b"
expecting "hello" or "howdy"
ghci> parse helloOrHowdy2 "hellay"
Left "(source)" (line 1, column 1):
unexpected "e"
expecting "howdy"

通过<?>操作符自定义错误信息

有时候,通常在构建自己的规则是,会想要用自己定义的匹配失败的错误信息。<?>操作符允许把一个自定义错误信息很简单的附加到任何一个规则上。我们来看看实际效果:

ghci> parse (Parsec.string "hello") "wrongstring"
Left "(source)" (line 1, column 1):
unexpected "w"
expecting "hello"
ghci> parse (Parsec.string "hello" <?> "a common greeting") "wrongstring"
Left "(source)" (line 1, column 1):
unexpected "w"
expecting a common greeting

我们简单的把一个错误信息附加到了一个Parsec.string产生的规则上。<?>的优先级是最低的,以为这任何其他的东西都会优先求值。以把一个新的错误信息附加到由<|>产生的规则链为例,那么当所有的规则都匹配失败了并且*没有消费任何输入*,这个错误信息才会被使用。只要有一个规则消费了输入,那么这个规则的错误信息将会用来描述整体的失败(当然除了这个规则被try包了起来)。这个基本的例子说明了这个事实:

ghci> -- this fails without consuming any input:
ghci> parse (Parsec.string "apple" <|> Parsec.string "bat" <?> "boom!") "cat"
Left "(source)" (line 1, column 1):
unexpected "c"
expecting boom!
ghci> -- this consumes input before failing:
ghci> parse (Parsec.string "apple" <|> Parsec.string "bat" <?> "boom!") "aunty"
Left "(source)" (line 1, column 1):
unexpected "u"
expecting "apple"

如果想要给创建的规则一个自定义的错误信息,可以把规则装进try里,catch这些可能的错误信息,并且提供自己的错误信息。这儿有一个简单的例子:

-- here we parse a basic greeting with no custom errors:
greeting :: Parsec.Parsec String () String
greeting = do
    Parsec.char 'h'
    Parsec.string "olla" <|> Parsec.string "ello"
    return "greeting"

--parse the same greeting, but wrap in try and add custom error:
greeting2 :: Parsec.Parsec String () String
greeting2 = Parsec.try greeting <?> "a greeting!"

这种做做法对于更重要的规则并不推荐,因为来自子规则的精确的错误信息会被更一般且较少帮助信息的错误信息替换掉。然而,当构建小的规则时,提供自己的错误信息会比Parsec提供的更有描述性。

利用applicative函数做到更简洁的解析

模块Control.Applicative引入了几个函数,多数是中缀操作符,在正确的场合,这些可以让规则更简洁可读。很明显我明已经使用过了这样的一个操作符<|>。Applicative函数常常使得代码变短,因为他们都是与point-free相关的,也就是不显式的引用传入的参数。

我们来把最初的parser改成applicative形式,看看每个操作符干了什么:

-- lets start again with our first parser to parse a letter/digit pair:
myParser :: Parsec.Parsec String () (String,String)
myParser = do
    letters <- Parsec.many1 Parsec.letter
    Parsec.spaces
    digits <- Parsec.many1 Parsec.digit
    return (letters,digits)

-- in applicative style:
myParserApp :: Parsec.Parsec String () (String,String)
myParserApp = (,) <$> Parsec.many1 Parsec.letter <*> (Parsec.spaces *> Parsec.many1 Parsec.digit)

-- could also be written as:
myParserApp2 :: Parsec.Parsec String () (String,String)
myParserApp2 = liftA2 (,) (Parsec.many1 Parsec.letter) (Parsec.spaces *> Parsec.many1 Parsec.digit)

-- or even (swapping *> for the more familiar >>):
myParserApp :: Parsec.Parsec String () (String,String)
myParserApp2 = liftA2 (,) (Parsec.many1 Parsec.letter) (Parsec.spaces >> Parsec.many1 Parsec.digit)

我们来一个一个看看主要的applicative操作符,看看它们到底干了什么事:

<$><*>

这个操作符本质上是fmap。左操作数是一个函数,右操作数是一个规则,并把规则的结果在返回之前传给这个函数(当规则匹配成功时,如果匹配失败,则是得到一个解析错误)。如果想要把这个函数应用到多个参数,用<*>分割参数。来看看ghci中的例子:

ghci> -- apply the result to a tuple constructor:
ghci> parse ((,) <$> Parsec.char 'a' <*> Parsec.char 'b') "ab"
Right ('a','b')
ghci> -- put the result into an array:
ghci> parse ((\a b -> [a,b]) <$> Parsec.char 'a' <*> Parsec.char 'b') "ab"
Right "ab"

整洁的一点就是无论需要多少个参数,都可以在通过在后面加一个<*>来串联起来。

liftAx

上面的一个前缀版本,liftAx接受*x*个后续参数,并把他们传给第一个。没有中缀版本那么灵活,但是有时会更加可读。这是一个和上面完全一样的例子:

ghci> -- apply the result to a tuple constructor:
ghci> parse (liftA2 (,) (Parsec.char 'a') (Parsec.char 'b')) "ab"
Right ('a','b')
ghci> -- put the result into an array:
ghci> parse (liftA2 (\a b -> [a,b]) (Parsec.char 'a') (Parsec.char 'b')) "ab"
Right "ab"

<**>

有时会想要匹配一下规则,除了其中的一个,其余的结果都扔掉。这两个操作符接受两个规则,并且返回尖括号指向的规则的结果。例子:

ghci> parse (Parsec.char 'a' <* Parsec.char 'b') "ab"
Right 'a'
ghci> parse (Parsec.char 'a' *> Parsec.char 'b') "ab"
Right 'b'

同样可以串联起来,这样可以忽略几个规则:

ghci> parse (Parsec.char 'a' <* Parsec.char 'b' <* Parsec.char 'c') "abc"
Right 'a'
ghci> parse (Parsec.char 'a' *> Parsec.char 'b' <* Parsec.char 'c') "abc"
Right 'b'
ghci> parse (Parsec.char 'a' *> Parsec.char 'b' *> Parsec.char 'c') "abc"
Right 'c'

当想要做一些类似去空格什么的或者从一些片段中提取某个片段的时候,这个经常会会特别方便。

<$

匹配右边的规则,并且如果左边的规则匹配成功,则返回左边的结果。我们来看看做这个事情的一些等价的方式:

ghci> parse ("greeting!" <$ Parsec.string "hello") "hello"
Right "greeting!"
ghci> parse (Parsec.string "hello" >> return "greeting!") "hello"
Right "greeting!"
ghci> parse (return "greeting!" <* Parsec.string "hello") "hello"
Right "greeting!"

可以看到,这些不同的方式都没有减少代码。我自己会选用更明显的第二种方式,虽然它比第一种长了一些,但是你们自己随意。

处理状态

最近我了解到可以在parser之间保持状态。当需要跟踪某个事情时,这非常有用,比如缩进的层数。这是一个非常简单的利用状态数字母的例子:

-- matches char 'h', incrementing int state by 1
-- each time one is seen.
hCountParser :: Parsec.Parsec String Int ()
hCountParser = do
    Parsec.char 'h'
    c <- Parsec.getState
    let c' = c+1
    Parsec.putState c'
    return ()

-- parse as many h's as we can, then return the state
-- to see how many there were
Parsec.runParser (Parsec.many hCountParser >> Parsec.getState) 0 "" "hhhhhhhhhhhhellooo"

对于getandset,我们可以用Parsec.modifyState来原地修改状态。一个hCountParser简单的版本:

hCountParser' :: Parsec.Parsec String Int ()
hCountParser' = do
    Parsec.char 'h'
    Parsec.modifyState (+1)
    return ()

值得注意的是,作为一个monad transformer,我们也有这样一个选择,把parser和类似于State monad的东西结合,来保存状态。这种方式与monad transformer的做事方式更一致。使用State monad,则是下面这样:

import Control.Monad       (lift)
import Control.Monad.State as S

hCountParser'' :: Parsec.ParsecT String () (S.State Int) ()
hCountParser'' = do
    char 'h'
    lift $ modify (+1)

-- after running our parser transformer, we get back our unevaluated inner state, which
-- contains our parser result and state ('h' count). We only want the state so
-- we use execState rather than runState or evalState to execute and unwrap the state monad,
-- providing an initial state to start the ball rolling.
S.execState (Parsec.runParserT (Parsec.many hCountParser2) () "" "hhhhhhhhhhhhellooo") 0

总结

我们已经了解了一些内置的函数和规则,之后又看了看如何通过组合规则来构建大的规则,包括在多个规则之中选择、通过try来超前查看,最后添加了向自己的规则添加自定义的错误信息,并且快速的尝试了一下保存状态。有了以上的经验,接下来应该会很容易了!

我建议在ghci下,通过别名引入Parsec模块(或者qualified引入)并且使用tab键来获得Parsec提供的所有东西,详细考察Parsec的函数。对这些函数使用:type,会让你对其有更深的理解,同样也是我探索这么多的函数的基础。*Real World Haskell*的这一章(英文版中文版)也是非常好的教程,并且有更为大量的实际例子,虽然其中的一小部分已经过时了。

我希望这篇文章能给你提供帮助。如果我漏掉了什么,请留下你的评论,让我知道!

年末瞎扯淡

前几天糊里糊涂的就开完题了,开题之前就知道不做这个题目。现在对于论文很烦,不知道怎么搞。根本就不是写论文的料。

Angular2的beta版出来了,今天照着quickstart和tutorial,敲了一会儿。1和2的差别相当的大,完全推翻了原来的风格。这个跨度比Python的2和3打了好几倍。Angular支持TypeScript,感觉和ES6的风格很像,除了有类型声明,都有写React的感觉了。

下午在忙一个活,是个商城的后台系统。任务是在某个报表里添加一个搜索条件。开头以为不好弄,因为我以为还要改这个搜索调用的存储过程。过程中发现貌似不用改,难度瞬间下降,以为分分钟的事。但是,事情往往和自己想的不一样啊。不加条件执行的没有问题,加了条件就没有结果,但是在数据库里直接执行SQL没有问题,调试了才发现,超时了。然后我设置了120秒的超时时间。OK,搞定。但是呢,还有另一个报表,也需要改。不过就想,没压力啊,根本就是一个逻辑。不过结果并非如此啊,这个存储过程的比刚才的多了几个参数,但问题是多的几个参数,在写代码的时候,已经把这几个参数添加到另一个参数里了。相当于是这几个条件执行了两遍,也不知道数据库是不是能优化。之前已经把超时设置了120秒,这次我又设置了600秒,因为在数据库里执行,用了6分多钟,日了狗了。

实验室的一个项目,要用Meteor,然后学了学。这玩意儿是个全端的框架,一套代码同时运行在服务器端和客户端。卖点在实时,数据库的变动,实时反映在客户端。写这个,思路和以前的不一样,完全是一套自己的东西,所以公司里用的不是很多。挺好玩的一个东西。

以上是昨天写的,今天基本啥都没干,看了两场球,世俱杯,恒大打广岛三箭,巴萨打河床,可惜恒大输了,巴萨发挥正常。

不知道写啥,就这样算了吧,还能看场皇马的联赛。

在C++中实现Haskell的map函数

C++11中引入了lambda,类似如下的语法

[value](int x) -> int { return x * x; }

其中,[]中的部分,是捕获外界变量,()中的部分则是参数,->表明返回类型,{}中是函数体。

正好这几天在看Haskell,于是想要在C++中实现Haskell中的map函数。Haskell中,map的的效果与下面的代码效果相同,

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x: map f xs

实际上是一个列表中的所有元素都用给定的函数进行计算,其结果保存为一个新的列表。

我期望最终的map函数,可以进行这样的调用

// lambda,多态
vector<int> ir = map([](int x) { return x * x; }, int_vec);
vector<bool> br map([](double n) { return n > 0; }, double_vec);

// 函数指针
int 
f(string s)
 
{ return s.length() }
vector<int> ir2 = map(f, string_vec);

// functor
struct F {
	int operator()(int n) {
		return n % 5;
	}
}
vector<int> ir3 = map(F(), int_vec);

我第一次想到的函数声明是这个样子的

template<typename T, typename R>
vector<R> map(R f(T), vector<T> list);

这个声明的问题在于,R f(T)是个函数指针,不接受lambda函数和functor,让人很无奈。于是尝试将类型改为function,也就是下面这样(之后省略template说明)

vector<R> map(function<R(T)> f, vector<T> list);

现在3中方式都可以了,但是问题是,需要强制类型转换。这就比较痛苦了。至此陷入了困境。然后我想C++标准库库中是有可以传入lambda的函数的。于是我打开了algorithm,里面有个for_each函数,其声明是这样的

template<class _InIt,
	class _Fn1> inline
	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)

也就是将函数类型作为多模板参数,于是我也将我的声明修改了一下

vector<R> map(F f, vector<T> list);

然后又报错了,C++编译器无法推断出R的类型。

其实从Haskell的map的类型可以看出来,我们并不需要3个模板参数,输入类型T,输出类型R,函数类型F,是有关系的,F(T) = R,最开始,我是使用T和R来表示F,并不是很成功。从它们的关系来看,使用F和T表示R,相比之下,要比用F,R表示T来的直白的多。现在的问题是,如何使用C++的语法来表示R。

C++11中有个decltype,可以用来表示一个类型。如下

// 声明一个x类型的y
decltype(x) y = x;
// 与下面一行功能相同
auto y = x;

// 表明函数的返回类型
auto 
f(int t)
 -> decltype(foo(t))
;

最后一行,则使用了decltype来指明函数的返回类型和foot(t)的类型一样。那么,我们就可以写出map的函数声明了

auto f_map(F f, vector<T> list) -> vector<decltype(f(T()))>

其中decltype(f(T()))T()是T类型的无参构造函数。当然也可以是用*begin(list)或者*list.end()等等,decltypesizeof类似,不会对操作数进行求值。

最终的完整函数是这这样的

template <typename T, typename F>
auto f_map(F f, vector<T> list) -> vector<decltype (f(T()))> {
	vector<decltype(f(T()))> result;
	for (auto it = begin(list); it != end(list); ++it) {
		result.push_back(f(*it));
	}
	return result;
}

现在的实现的是map,当时我还想实现更加一般化的fmap

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

fmap并没有一个统一的实现,对于列表而言,fmap的实现就是fmap = map。注意,这里Functor和C++中的Functor不是一个概念。

当然Haskell中的Functor在C++中不存在,我只是想写一个这种模式,比如对于一些容器,如setmap等等,可以进行map操作(实际上,这些容器,可以被定义为Haskell中的Functor)。但最后我放弃了,因为在C++中,这些容器并不具体有共同的基类,我可以写出函数声明,但是实现却无法统一。

template <template <typename...> class C, typename F, typename T>
auto mymap (F f, C<T> list) -> C<decltype(f(T()))>;

其实标准库中已经有了类似的函数,就是transform,不过transform并不返回值,而是通过一个指针,修改外部的变量

vector<int> result;
transform(begin(input), end(input), back_inserter(result),
		[](int x) { return x + 3; });

result就是map后返回的结果。

总体来说,由于C++和Haskell的设计理念并不相同,Haskell中的fmap无法(至少我无法)完全在C++中实现,而map由于限制较少,其实现没有问题。此外,C++的标准库中其实提供的了许多与Haskell中功能的相似的函数,但是名字并不相同,而且细节略有差异。C++的容器操作,一般是需要提供指明起止位置的iterator,对一个范围进行操作。而Haskell由于值不可修改,因此均是对所有元素进行操作的,最后返回新值。

React和Redux初探

React是Facebook开发的一套前端框架,与Angular等前端MVC框架不一样的是,React关注于构建UI,其相当于MVC中的V。而React最让人欣喜的一点在于,其使用了声明的方式开发UI,这使得基于组件(Component)的前端开发变得非常直接。然而仅仅使用React,还远远不能构建一个App,还需要有数据存储和逻辑处理,这当然可以使用MVC架构。不过,Facebook认为,MVC架构中,当Model和View增多以后,双向的数据流导致系统的复杂性增加。因而Facebook提出了一个Flux。可以认为Flux是一套应用框架,与MVC不同的是,其数据流是单向的,结构如下图所示 由于数据的单向流动,无须处理view->model的逻辑,因此系统的结构比较清晰。

React

对于如下的html代码,

<div class="post">
    <h1 style="font-size: 1.6rem">Post Title</h1>
    <div class="post-content">Some Content</div>
</div>

我们可以使用这样的React代码来构建

// app.js
var Post = React.createClass({
    render: function() {
        return (
            <div className='post'>
                <PostTitle text='Post Title' />
                <PostContent text='Some Content' />
            </div>
        );
    }
});
var PostTitle = React.createClass({
    render: function() {
        var style = {fontSize: '1.6rem'};
        return <h1 style={style}>{this.props.text}</h1>
    }
});
var PostContent = React.createClass({
    render: function() {
        return <div className='post-content'>{this.props.text}</div>
    }
});
React.render(
    <Post />,
    document.getElementById('root');
);

对应的html文件,则是

<div id="root"></div>
<script type="text/jsx" src="app.js"></script>

上面的app.js文件并不是Javascript纯粹代码,而是夹杂了一些类似HTML的代码。这是JSX代码,并不能被浏览器执行,因此需要预先编译成js代码。

从代码中,可以看到,React将原本的html代码拆成了三个组件,其中PostPostTitlePostContent两个组件构成。最后再通过React.render方法,将组件挂载到dom上。每个组件中,都有一个render方法,表示组件将要渲染的dom结构。与HTML相比,只是可以使用{}将参数传入到组件中,而组件则可以通过props获取属性。这种结构,称之为Virtual Dom,在返回的结果中,div, h1等和自己定义的PostPostTitle等类似,都是Virtual Dom,只不过div这种HTML本身已有的组件,其渲染结果就是与其对应的HTML标签。React约定,自己定义的组件使用大写字母开头,已有HTML标签为小写字母开头。并非所有HTML标签和属性都被React支持,可以在在这里查看支持的标签和属性。其中,classfor分别使用classNamehtmlFor,因为这两个都是js的关键字。

Redux

由于Flux还是属于新生事物,各种Flux实现多如牛毛,比如Reflux、Fluxxor等等,Redux也是其中的一种。Redux借鉴了函数式的编程思想,对于状态的改变,其实是如下的函数

f(state, action) => next_state

这种函数在Redux里称为Reducer, 而Flux中的Store则是多个由Reducer组成。这样,对于一个Action以及当前的状态,可以转移到下一个状态,从而更新View。

我根据其github的breaking-changes-1.0分支(地址)的例子,大致明白了现在的API,但是仍有非常多的东西不是很清楚,需要等到正式版放出之后,查看文档才能明白了。

至于Redux相比其他Flux实现有什么优点,其实我说不上来,最初吸引我的其实不是Redux,而是这篇文章,当时也根本不了解Flux(现在其实也不了解。。),就稀里糊涂的看了Redux的例子。

前端

感觉目前的前端越来越复杂,Javascript的应用也越来越多。甚至都有了以后找个前端工作的念头,谁知道呢。。