初探 F#，随手写个 JSON 解析器 - 早起搬砖 morning.work

最近的一段时间对 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 命令基本操作

• 创建项目：dotnet new console -lang "F#" helloworld
• 运行项目： dotnet run
• 构建项目： dotnet build
• 添加依赖： dotnet add package xxx
• 当然，更详细的使用方法还是要靠自己去摸索了

F# 交互式命令行工具

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

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

对 F# 的一些认识

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

• obj 表示 Object， list 表示列表， [] 表示数组。比如 obj list 表示 Object 列表（在 .NET 框架中，Object 表示任意对象）， obj [] 表示 Object 数组；
• 元组中多个类型用星号 * 连接，比如 int * float * string 表示三个元素的元组，类型分别为 int 、 float 和 string ；
• 函数多个参数用箭头 -> 连接，比如 int -> float -> string 表示三个参数，类型分别为 int 、 float 和 string ；
• unit 类型表示空类型，即什么也没有，一般函数执行结果如果不想返回任何值，则在最后一行写 () 表示返回一个 unit 类型的值。如果想忽略函数的执行结果，可以通过管道操作符传递给 ignore ，比如 f() |> ignore ；

• 数组索引前面有小数点，比如 a.[1] 表示 a 的索引 0（其他语言中一般是用 a[1] 表示；
• 多个参数的函数跟其他编程语言是不同的，如果调用其他编程语言写的接口，其他语言中的多个参数在 F# 中实际上是一个元组参数，元组内的元素个数即为其实际参数个数。比如传递一个参数时可以用 f (a) 或者 f a 这样的写法，如果传递两个参数则只能写成 f (a,b) ；
• 如果在“调用”一个函数时没有传递足够的参数，实际上它会被柯里化，返回一个新的函数而不是函数的执行结果。比如函数 f a b 如果只传了一个参数 f a ，则会返回一个需要输入第二个参数的新函数 f2 b ；
• “变量”默认不可变（准确来讲不是一个变量，而是称之为“绑定”）。比如 let a = 123 表示将值 123 绑定到名称 a ，是不需要再通过 a = 456 这样的语法来改变 a 的值，但是可以再通过 let 语句来绑定新的值到名称 a 中；
• 如果要声明一个可变的变量，则需要用 let mutable a = 123 来声明，并且使用 a <- 456 这样的语法来更改其值；
• 记录类型的值默认是不可变的，比如类型 type Point = { x: int; y: int } ，通过 let a = { x=123; y=456 } 创建值之后，可以通过 with 语法修改某个字段并复制一份新的值，比如 let b = { a with y=789 } ；
• 记录类型可以直接通过等于号 = 来判断其值是否相等（像 Java 之类的语言类的实例实际上是一个地址指针，不能判断值是否相等，而只能判断是否为同一个实例）；
• 基本类型的转换可以以该类型名称为函数调用，比如 int("123") 将字符串 123 转换为 int 类型；
• 定义类型的时候，如果两个类型之间有交叉引用，则需要通过 and 语句将其连在一起定义，比如：

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

• F# 的程序是按顺序执行的，需要在 .fsproject 工程文件中对源码文件进行排序，前面未定义的内容是不可用的（比如类型和函数的定义），因此也可避免循环依赖的问题。可以参考这篇文章：https://fsharpforfunandprofit.com/posts/recipe-part3/

一些新奇特性

• 强大的自动类型推断：基本上不需要写类型声明，就像写动态语言一样方便，比如 let add a b = a + b ；
• 管道操作符 |> ：可以将结果通过管道操作符传递到多个函数执行，比如 10 |> printfn "%A" 和 printfn "%A" 10 虽然结果一样，但是表达的含义还是不一样，前者是先有结果，然后再做输出，而后者是要输出结果；
• 自定义运算符：可以为不同数据类型定义相应的运算符，很方便实现某个领域专用的语言，比如在 FParsec 中就大量运用自定义运算符来简化编程；
• Compatution（计算表达式）：提供了一种方便的语法，用于编写可使用控制流结构和绑定进行序列化和组合的计算。文档参考：https://docs.microsoft.com/zh-cn/dotnet/fsharp/language-reference/computation-expressions
• 异步工作流：在 async 块中支持 await 操作，也是通过计算表达式来实现。文档参考：https://docs.microsoft.com/zh-cn/dotnet/fsharp/language-reference/asynchronous-workflows
• TypeProvider：提供基于外部数据源动态生成数据类型，比如通过一段 JSON 字符串生成其类型定义，通过 SQL 数据库配置自动生成表的类型定义。文档参考：https://docs.microsoft.com/en-us/dotnet/fsharp/tutorials/type-providers/

一些不足之处

• 虽然现在编辑器或 IDE 的支持已经还不错了，但相对于其他编程语言比如 C#、Java、Go、TypeScript 等还有很大的差距；
• 因为 F# 自身独特的语言特性，虽然都是基于 .NET 的生态，但大部分第三方包都是为 C# 开发的，所以 F# 使用的时候就没有原生的 F# 那么爽；

以上罗列的内容可能不一定准确，但相信已经吸引了你的兴趣，如果想深入了解 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 接口

• val run: Parser<'a, unit> -> string -> ParserResult<'a,unit> 执行解析器并返回结果；
• val pfloat: Parser<float,'u> 解析浮点数值；
• val stringReturn: string -> 'a -> Parser<'a,'u> 匹配指定字符串，并返回指定的结果；
• val pstring: string -> Parser<string,'u> 解析匹配指定字符串；
• val spaces: Parser<unit,'u> 解析连续的零个或多个空白字符（比如空格、制表符、换行符等）；
• val eof: Parser<unit,'u> 当到达末尾时返回成功；
• val anyOf: seq<char> -> Parser<char,'u> 解析指定的任意一个字符；
• val choice: seq<Parser<'a,'u>> -> Parser<'a,'u> 尝试指定的任意一个解析器；
• val (|>>): Parser<'a,'u> -> ('a -> 'b) -> Parser<'b,'u> 将解析器的结果传递给指定的函数 f x ，并返回新的结果；
• val (.>>): Parser<'a,'u> -> Parser<'b,'u> -> Parser<'a,'u> 连续执行解析器 p1 和 p2 并返回 p1 的结果；
• val (>>.): Parser<'a,'u> -> Parser<'b,'u> -> Parser<'b,'u> 连续执行解析器 p1 和 p2 并返回 p2 的结果；
• val (.>>.): Parser<'a,'u> -> Parser<'b,'u> -> Parser<('a * 'b),'u> 连续执行解析器 p1 和 p2 ，并将 p1 和 p2 的结果放到元组中返回；
• val between: Parser<'a,'u> -> Parser<'b,'u> -> Parser<'c,'u> -> Parser<'c,'u> 顺序解析 pOpen 、 p 、 pClose ，并返回 p 的结果；
• val createParserForwardedToRef: unit -> Parser<'a,'u> * Parser<'a,'u> ref 创建一个空的解析器，后面可以更新其引用来更新解析器；

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