初探 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。当然很难在实际工作中应用上，但是作为一门有趣的语言，还是可以玩一玩的。