「Text.Read」Day 3. - 30天Hackage之旅

2016-11-24 本文已影响46人 kdepp

Text.Read 做的事情和 Text.Show 刚好相反，是把字符串反序列化为对应的数据类型。反序列化，自然就和语法解析有关，也因此 Text.Read 要比 Text.Show 相对复杂许多。

初步使用

继续使用 Tree 数据结构为例：

import Text.Read

infixr 5 :^:
data Tree a =  Leaf a  |  Tree a :^: Tree a
   deriving (Show, Read)

main = print (read "Leaf 1 :^: (Leaf 2 :^: Leaf 3)" :: Tree Int)

可以看到，Read 的用法十分简单，就是直接用小写的 read 读取一个字符串，并返回希望得到的类型，需要注意的是，必须注明想要得到的类型，如此处的 Tree Int。

如果不适用 deriving Read 而选择自己去定义 Read 实例的话，官方的示例是这么写的：

instance (Read a) => Read (Tree a) where
        readsPrec d r =  readParen (d > app_prec)
                         (\r -> [(Leaf m,t) |
                                 ("Leaf",s) <- lex r,
                                 (m,t) <- readsPrec (app_prec+1) s]) r

                      ++ readParen (d > up_prec)
                         (\r -> [(u:^:v,w) |
                                 (u,s) <- readsPrec (up_prec+1) r,
                                 (":^:",t) <- lex s,
                                 (v,w) <- readsPrec (up_prec+1) t]) r
          where app_prec = 10
                up_prec = 5

上半段代码尝试读取 Leaf 的形式，下半段尝试读取 :^: 的形式，app_prec 表示函数调用的优先级是 10， up_prec 表示 :^: 的优先级是 5。看到这里，可能就要问了，readsPrec 到底是在干什么？以及它和我们真正使用的 read 有什么关系？

初探源码

先来看看 read 是怎么定义的？

read :: Read a => String -> a
read s = either errorWithoutStackTrace id (readEither s)

readEither :: Read a => String -> Either String a
readEither s =
  case [ x | (x,"") <- readPrec_to_S read' minPrec s ] of
    [x] -> Right x
    []  -> Left "Prelude.read: no parse"
    _   -> Left "Prelude.read: ambiguous parse"
 where
  read' =
    do x <- readPrec
       lift P.skipSpaces
       return x

readPrec     = readS_to_Prec readsPrec

readS_to_Prec f = P (\n -> readS_to_P (f n))

不要被上面的代码吓到，以上是截取了多个模块中的代码，来展示 read 和 readsPrec 之间的联系。可以看到，这里绕的弯还不少，大概有这么几个函数需要我们摸清楚门道：

read ==> readEither ==> readPrec ==> readsPrec

注意，这里 readPrec 和 readsPrec 是两个不同的函数，有的时候真得是要吐槽下 Haskell 函数库中命名的不拘小节，命名的时候如此小的差别，确实不利于阅读源码。
为了讲清楚这些函数，就必须先分别来看一下它们的类型签名。

read :: Read a => String -> a
readEither :: Read a => String -> Either String a
readPrec     :: ReadPrec a
readsPrec :: Int -> ReadS a

哇偶！好多不认识的面孔！这里有一个类型类：Read，有两个陌生的类型：ReadPrec、ReadS ，都是什么鬼？别着急，慢慢来看：

-- 类型
newtype ReadPrec a = P (Prec -> ReadP a)

newtype ReadP a = R (forall b . (a -> P b) -> P b)
data P a
  = Get (Char -> P a)
  | Look (String -> P a)
  | Fail
  | Result a (P a)
  | Final [(a,String)]
  deriving Functor

type ReadS a = String -> [(a,String)]

-- 类型类
class Read a where
  {-# MINIMAL readsPrec | readPrec #-}
  readsPrec    :: Int -> ReadS a
  readList     :: ReadS [a]

  readPrec     :: ReadPrec a
  readListPrec :: ReadPrec [a]

ReadS a
- 这是一个写 Parser 时一个非常基础的类型，就是 String -> [(a,String)] 的别名，其含义就是从一个字符串，获得一个数组的元组。元组中包含一个类型为 a 的最终数据，以及剩余字符串。这就是 readsPrec 最终会返回的类型，很明显，这个类型很方便我们获取反序列化的结果，直接套上 fst . head 就可能拿到结果。
data P a
- 这是一个有趣的类型，在这个类型中存储的其实就是一个 Parser 的工作状态：
  - Get (Char -> P a) ，表示需要获取一个字符，然后返回一个新的 Parser 状态
  - Look (String -> P a)，表示需要往后多看一个字符串，然后返回一个新的 Parser 状态
  - Fail，字面意思，表示 Parser 失败了
  - Result a (P a)，表示获得了一个可能的解，然后返回一个新的 Parser 状态，继续尝试其他可能
  - Final [(a,String)]，表示完成 parse 后得到的结果
- 这样的数据结构，反映了一个很好的思路，就是将复杂运算（此处就是 Parse）转化为各个不同的状态。只要能描述清楚状态，以及状态之间的转移，那逻辑就已将完成了一半。剩下就是把实际的复杂运算，藏到各个类型类的实例中去，比如 Monad。
- 这里，P a 中的 Get 和 Look 天然具备了 (a -> P b) -> P b 的类型签名，可以知道，肯定要使用 CPS 了。
ReadP a
- 一个 CPS 结构，这里的类型变量 a 就表示想让 Parser 收到的数据类型。在 Text.ParserCombinators.ReadP 中，显示声明了各种常见类型类的实例 Functor, Monad，之后还写了以 ReadP 为基础的一系列 Parser Combinators。
- 笔者猜测，ReadP a 和 ReadS a 应该是同构的。对应的，在 ReadP 的模块中定义了 ReadP 和 ReadS 互转的两个函数。基于这个猜想，我们可以认为，ReadP 更适用于做实际 parse 工作，可以很好地进行 combinator 组合，最终再把结果转回 ReadS，方便直观地获取最终 parse 结果。

-- Text.ParserCombinators.ReadP 源码中，对 ReadS 有如下注释

-- Note that this kind of backtracking parser is very inefficient;
-- reading a large structure may be quite slow (cf 'ReadP').


- ReadPrec a
- 可以将 `ReadPrec a` 看作是 `ReadP a` 外面又套了一层 Reader Monad，传入的环境就是当前所处的操作优先级 Precedence。稍微看一下 ReadPrec 的源代码就会发现，其实就是把 ReadP 的很多操作加上了 lift。

- class Read a
- 两组函数，每组两个，一组使用 ReadS，另一组使用 ReadPrec，只要实现 `readPrec` 和 `readsPrec` 中的一个就可以工作。其中， Haskell 2010 Report 中规定要实现的是 `readsPrec`，而`readPrec` 是 GHC 才有的方法，也是 GHC 更推荐使用的方法。事实上，在绝大部分的 Read 实例中，Text.Read 也都是选择去实现 `readPrec`.


## Text.Read.Lex

说了那么多 Read 内部的类型和类型类，再来回看我们在 `instance Read (Tree a)` 中的实现，你会发现其实真正用到的生面孔只有两个函数，即 `readParen` 和 `lex`。没错，我们刚刚说的所有内容，实际上都藏在了这两个函数下。而 `readParen` 又是完全依赖于 `lex` 实现的用于匹配括号的辅助函数，所以接下来，就让我们把焦点放在 “lex” 上。

``` Haskell
lex :: ReadS String             -- As defined by H2010
lex s  = readP_to_S L.hsLex s

可以看到，lex 其实就是简单将 L.hsLex 从 ReadP 转成了 ReadS。所以真正实现都在 L 中，也就是 Text.Read.Lex 中。Text.Read.Lex 模块在 Hackage 上的描述是：

The cut-down Haskell lexer, used by Text.Read

由此可知，Text.Read.Lex 就是一个建议的 Haskell 语法解析器，且是专门写给 Text.Read 用的。翻阅一下它的代码，也可以发现，Lex 就是使用 ReadP 提供的 Parser Combinator 来对 Haskell 语法（针对由 show 输出的文本）进行解析。

-- ^ Haskell lexemes.
data Lexeme
  = Char   Char         -- ^ Character literal
  | String String       -- ^ String literal, with escapes interpreted
  | Punc   String       -- ^ Punctuation or reserved symbol, e.g. @(@, @::@
  | Ident  String       -- ^ Haskell identifier, e.g. @foo@, @Baz@
  | Symbol String       -- ^ Haskell symbol, e.g. @>>@, @:%@
  | Number Number       -- ^ @since 4.6.0.0
  | EOF
 deriving (Eq, Show)

可以看到，Lex 定义了一些语言的基础元素，不过其中并没有涉及表达式和语句，这是因为 show 输出内容其实就只可能是一个表达式，所以只要好好描述表达式中可能包含的元素就够了。源代码中，有较大篇幅涉及数字和各种字符的解析，虽然值得阅读，但因为和 read 关系不大，所以就不再深入了。

最后再列一下 Text.Read 所有涉及的代码模块：

Text.Read
Text.Read.Lex
GHC.Read
Text.ParserCombinators.ReadP
Text.ParserCombinators.ReadPrec

总结

以上即笔者变读变总结的 Read 类型类的源码分析，希望对于大家理解 Read 能有所帮助。

对于 Read 类型类，大部分时候我们都会直接 deriving 它的实例，最多要实现，也只是简单得套用 readParen 和 lex 就可以搞定了。但对于笔者而言，这里真正有趣的是理解 Read 的实现机制。这里特别有启发的就是两点：

将状态描述为数据类型，然后以此来构建状态转移的情况，多数情况需要用到 Monad 和 Alternative 的实例来描述多状态组合时的效果。在 Text.Read 中即为 P a 类型。
使用 CPS 搭配上面的状态类型，描述状态转移本身。在 Text.Read 中即为 newtype ReadP a 类型。

「Text.Read」Day 3. - 30天Hackage之旅

初步使用

初探源码

-- Text.ParserCombinators.ReadP 源码中，对 ReadS 有如下注释

总结

猜你喜欢

热点阅读