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

前言

最近的一段时间对 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 表示三个元素的元组,类型分别为 intfloatstring
  • 函数多个参数用箭头 -> 连接,比如 int -> float -> string 表示三个参数,类型分别为 intfloatstring
  • 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> 连续执行解析器 p1p2 并返回 p1 的结果;
  • val (>>.): Parser<'a,'u> -> Parser<'b,'u> -> Parser<'b,'u> 连续执行解析器 p1p2 并返回 p2 的结果;
  • val (.>>.): Parser<'a,'u> -> Parser<'b,'u> -> Parser<('a * 'b),'u> 连续执行解析器 p1p2 ,并将 p1p2 的结果放到元组中返回;
  • val between: Parser<'a,'u> -> Parser<'b,'u> -> Parser<'c,'u> -> Parser<'c,'u> 顺序解析 pOpenppClose ,并返回 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。当然很难在实际工作中应用上,但是作为一门有趣的语言,还是可以玩一玩的。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章