初探 F#,随手写个 JSON 解析器

老雷 创作于 2019-10-21
F# FParsec 全文约 9544 字,预计阅读时间为 24 分钟

前言

最近的一段时间对 F# 很感兴趣:首先是其“函数式”编程的语法,还有“简单得像脚本语言的静态类型语言”的特点,结合微软开源的 ML.NET 机器学习框架,跟最近“因人工智能而大火的 Python”有一拼。据说微软开发的量子计算编程语言 Q# 的语法很大程度上参考了 F#,学会 F# 给人一种“面向未来”的感觉。

开发环境准备

据我自己的折腾经验,如果你正在使用 Windows,可以使用微软官方的 Visual Studio 作为开发环境;如果非 Windows,目前使用 JetBrains 出品的 Rider 作为开发工具是最省心的,其他的编辑器可能就没那么好用了,毕竟是小众语言。如果喜欢折腾 Visual Studio Code,也可以安装 Ionide 插件,另外安装一个名叫 fantomas 的工具可以用来格式化 F# 代码。其次,你还要安装 .NET Core 3.0 的 SDK,可以参考这里:https://dotnet.microsoft.com/download/dotnet-core/3.0

以上准备好了之后,就可以通过命令 dotnet new console -lang "F#" helloworld 来创建一个新的命令行工程,开始你的 F# 之旅了。

dotnet 命令基本操作

F# 交互式命令行工具

执行命令 dotnet fsi 可以进入 F# 的交互模式,输入代码后,以两个分号 ;; 结尾并按回车即可立即执行。比如输入 printfn "hello, world";; 加回车,即可看到 hello, world 的输出。在编辑器中,一般有相应的快捷键可以将编辑器中正在输入的代码直接发送到 fsi 中执行,这样就可以立即看到代码执行的结果。

如果安装了 mono(一种开源的跨平台 .NET 实现),也可以执行命令 fsharpi 来进入 F# 的交互模式。

对 F# 的一些认识

F# 的语法来源于 OCaml,属于 ML 系语言,如果你之前只接触过 C 系的语言,则 F# 上有一些概念可能会比较陌生,当然现在很多编程语言都在互相借鉴,其实相差也不大。以下是我在初学过程中总结的一些不同之处。

类型声明

语法区别

type A =
    | A1 of int
    | A2 of B
and B =
    | B of float
    | B2 of A

一些新奇特性

一些不足之处

学习资料

以上罗列的内容可能不一定准确,但相信已经吸引了你的兴趣,如果想深入了解 F#,可以阅读以下这些网站和资料:

关于解析器组合子

最早知道解析器组合子(parser combinator)的概念是来源于王垠的文章《对 Parser 的误解》,其中有是这样介绍的:

Recursive descent 和 parser combinator 写出来的 parser 可以非常强大,甚至可以超越所谓“上下文无关文法”,因为在递归函数里面你可以做几乎任意的事情,所以你甚至可以把上下文传递到递归函数里,然后根据上下文来决定对当前的节点做什么事情。而且由于代码可以得到很多的上下文信息,如果输入的代码有语法错误,你可以根据这些信息生成非常人性化的出错信息。

维基百科中对其的描述如下:

计算机编程语法分析组合子 是一个 高阶函数 ,它接受几个的语法分析器作为输入,并返回一个新的语法分析函器作为其输出。 在这个上下文中, 语法分析器 是一个函数,它接受字符串作为输入,返回的一些结构作为输出,通常为 分析树 或一组索引表示在字符串中成功停止分析的位置。 分析器组合子使用 递归下降分析 战略,提倡模块式建造和测试。 这种分析技术是所谓的 组合分析。使用组合子构建的分析器易于构造、可读、模块化、结构良好且易于维护它们被广泛地用于 领域特定语言(如数据库的自然语言接口)的编译器和处理器的原型设计中,在这些语言中,复杂多样的语义操作与语法处理紧密集成。1989 年,Richard Frost 和 John Launchbury 演示了使用语法分析组合子构造的自然语言解释器。Graham Hutton 在 1992 年也使用了高阶函数进行基本解析。S.D. Swierstra 在 2001 年还展示了解析器组合器的实用方面。在 2008 年,Frost、Hafiz 和 Callaghan 用 Haskell 中描述了一组语法分析组合子,它们解决了长期存在的通用左递归的问题,它也是一个完整的,只需要多项式时间、空间的自顶向下解析工具。

自从知道了组合子这个概念,仿佛打开了新世界的大门。

JSON 解析器详解

在这里通过一个简单的例子来感受 F# 的简洁和强大(代码来源于 FParsec 官网的例子 Tutorial - Parsing JSON)。首先我分步简要解释一些语法,通过源码来进一步熟悉 F# 的特性,后文再给出完整的源码。

相关的 F# 语法

引用包

通过 open 语法来引用相应的包,如果没有通过 open 引入,则需要使用完整的包名称来访问接口,比如 System.Console.WriteLine() 方法用于输出内容到控制台,如果通过 open System 引入,则可以通过 Console.WriteLine() 来调用,如果通过 open System.Console 引入,则可以直接通过 WriteLine() 来调用。比如:

open System
open FParsec

模式匹配

模式匹配(Pattern Matching是每一门标榜自己可以“函数式编程”的语言的标配,就连语法上总是慢半拍的 Java 都开始引入了(参考文章:Java SE 12 扩展 Switch 语句 / 表达式完整指南)。实际上 F# 的模式匹配语法非常强大,可以对记录类型、列表类型、数组类型、元组类型等多种变化进行匹配,可以看看官方文档的实例代码感受一下:

// 判断 option 类型,Some 表示有结果,None 表示空
let printOption (data : int option) =
    match data with
    | Some var1  -> printfn "%d" var1
    | None -> ()

// 匹配元组,并且对元组的值范围做判断
let function1 x =
    match x with
    | (var1, var2) when var1 > var2 -> printfn "%d is greater than %d" var1 var2
    | (var1, var2) when var1 < var2 -> printfn "%d is less than %d" var1 var2
    | (var1, var2) -> printfn "%d equals %d" var1 var2

// 值范围判断的时候还支持 OR / AND 这样的连接
let detectZeroOR point =
    match point with
    | (0, 0) | (0, _) | (_, 0) -> printfn "Zero found."
    | _ -> printfn "Both nonzero."

// 匹配列表
let listLength list =
    match list with
    | [] -> 0
    | [ _ ] -> 1
    | [ _; _ ] -> 2
    | [ _; _; _ ] -> 3
    | _ -> List.length list

// 匹配记录类型,可以对记录的字段值进行判断
let IsMatchByName record1 (name: string) =
    match record1 with
    | { MyRecord.Name = nameFound; MyRecord.ID = _; } when nameFound = name -> true
    | _ -> false

以下是执行解析器并打印其结果的 test 函数:

let test p str =
    match run p str with
    | Success(result, _, _) -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

可区分联合

可区分联合(Discriminated unions),类似于其他编程语言的联合类型,可以用来表示某个值可以有哪几种类型的可能,一般和模式匹配一起使用。比如核心库的 option 类型应该是这样声明和使用的:

type Option<'a> =
    | Some of 'a     // 表示有值,'a 表示值类型
    | None           // 表示空值

let printValue opt =
    match opt with
    | Some x -> printfn "%A" x
    | None -> printfn "No value."

修改引用变量的值

在 F# 使用 let mutable a = value 声明可变绑定时,使用 a <- newValue 更改其值,其实是更新了绑定的名称 a 的值,而不是改变原 value 本身的值。如果要改变其值,则需要使用引用:

// a 是 int 值 10 的引用
let a = ref 10

// 修改 a 的值
a := 20

// 获取 a 的值
a.Value |> printfn "%A"

相关的 FParsec 接口

完整的 JSON 解析器源码

open System
open FParsec

// 执行解析器,并打印其结果
let test p str =
    match run p str with
    | Success(result, _, _) -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

// JSON 文档值,可以为 string、number、boolean、null、array、object 等类型
type Json =
          | JString of string
          | JNumber of float
          | JBool of bool
          | JNull
          | JList of Json list
          | JObject of Map<string, Json>

// 解析 null 值
let jnull = stringReturn "null" JNull
// 解析 true 值
let jtrue = stringReturn "true" (JBool true)
// 解析 false 值
let jfalse = stringReturn "false" (JBool false)
// 解析 number 值
let jnumber = pfloat |>> JNumber

// 解析字符串字面量,处理转义字符
let stringLiteral =
    let escape = anyOf "\"\\/bfnrt"
                  |>> function
                      | 'b' -> "\b"
                      | 'f' -> "\u000C"
                      | 'n' -> "\n"
                      | 'r' -> "\r"
                      | 't' -> "\t"
                      | c -> string c
    let unicodeEscape =
        let hex2int c = (int c &&& 15) + (int c >>> 6) * 9
        pstring "u" >>. pipe4 hex hex hex hex (fun h3 h2 h1 h0 ->
            (hex2int h3) * 4096 + (hex2int h2) * 256 + (hex2int h1) * 16 + hex2int h0
            |> char |> string
        )
    let escapedCharSnippet = pstring "\\" >>. (escape <|> unicodeEscape)
    let normalCharSnippet = manySatisfy (fun c -> c <> '"' && c <> '\\')
    between (pstring "\"") (pstring "\"")
            (stringsSepBy normalCharSnippet escapedCharSnippet)
// 解析 string 值
let jstring = stringLiteral |>> JString

// json 解析器,由于可能存在循环引用,先通过 createParserForwardedToRef 创建一个空的解析器
// 后面再更新解析器的值
let jvalue, jvalueRef = createParserForwardedToRef<Json, unit>()

let listBetweenStrings sOpen sClose pElement f =
    between (pstring sOpen) (pstring sClose)
            (spaces >>. sepBy (pElement .>> spaces) (pstring "," >>. spaces) |>> f)
// 解析 array 值
let jlist = listBetweenStrings "[" "]" jvalue JList

let keyValue = stringLiteral .>>. (spaces >>. pstring ":" >>. spaces >>. jvalue)
// 解析 object 值
let jobject = listBetweenStrings "{" "}" keyValue (Map.ofList >> JObject)

// 组装 json 解析器
do jvalueRef := choice [
                        jobject
                        jlist
                        jstring
                        jnumber
                        jtrue
                        jfalse
                        jnull ]
let json = spaces >>. jvalue .>> spaces .>> eof

// main 函数,程序执行入口
[<EntryPoint>]
let main argv =
    test json "{}"
    test json "{\"a\":123,\"b\":[123,false,null,true,{},[true,false]]}"
    test json "123"
    0

程序性能

以下是一个简单的测试结果,从结果中可以看出,其速度与专业的 JsonProvider 和 .NET Core 标准库新增的 JSON 解析器相差不大:

方法 执行 10000 次耗时(ms) 速度(次/秒)
FParsec 实现的 json parser 142.4 70225
FSharp.Data JsonProvider 36.6 273493
System.Text.Json 61.2 163492

总结

第一次接触 F# 的时候,确实令人眼前一亮,比如其 Type Provider 应该是独一无二的,F# 即拥有编写动态语言的便利,又是一门静态类型语言,即可以函数式编程,也可以面向对象编程,底层基于丰富且强大的 .NET Core。当然很难在实际工作中应用上,但是作为一门有趣的语言,还是可以玩一玩的。