2008年12月19日星期五

Write Yourself a Scheme in 48 Hours/Parsing(四)

上一次,我们给出了原子(Atom)的解析器,其中已经把逻辑类型(#t/#f)的解析功能一并做进去了。

接下来是解析数值的组件:

Haskell语言: Parsing 代码片段九

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

这一段不难理解,主要是 $ 和 . 两个函数的运用。 many1 解析器匹配一个或多个参数,所以我们可以用来匹配一个或多个数字字符(0-9)。不过我们需要返回的是一个LispVal数值,所以还要把解析到的字符串 再转为数字。于是,我们用 . 组合 Number和read。它先将传入的参数作用于右值,再将得到的结果作用于左值。

many1返回的值实际上是 Parser String,而我们需要一个 String,还要返回一个 Parser LispVal。所以 Number . read 读不了它。liftM 起到析值的作用。也就是说,我们将many1 digit解析得到的 Parser String,传递给 $ (它等效于一对括号)的左值, liftM (Number . read)。

为了使用这个 Monad ,我们需要导入 Monad 模块:

import Monad

这种风格的编程--重度依赖函数组合、应用、传递--在 Haskell 代码中非常普遍。它通常可以使你在一行中写出非常复杂的算法。有时候你可能需要从右向左读Haskell代码(想想我们学过的那些数学公式)。

Barolo 号称意大利国酒--要知道正是古罗马的军团将亚平宁半岛的葡萄酒文化带到了法国和整个地中海沿岸,至今意大利仍是世界第一大葡萄酒生产国--但它的强劲却 令很多初尝葡萄酒的人退避三舍。很多初学者比较难接受Haskell浓烈粹的FP风格。我个人也仍处于努力学习的阶段。但是,也正是这种风格,是它的魅力 所在。

现在,我们可以编写一个 parserExpr 接受字符串、数值和原子语素了:

Haskell语言: Parsing 代码片段十

parseExpr :: Parser LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber

然后修改 readExpr 以使其调用新的 parser:

Haskell语言: Parsing 代码片段十一

readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"

最后,我要说的是,其实在这一章,我将代码文件分成了三份:BuildIn.hs,Parser.hs,Parsers.hs。其中 Parser.hs是主程序,其它两个文件定义为两个模块。但是多文件编译的话,学原文上的方法并不成功,可能是ubuntu默认的shell和 debian不同,不过更大的可能是高版本的ghc编译器参数变了,总之,我编译的时候用的是:

为了阅读方便,我完整给出三个文件的代码。

BuildIn.hs:

module BuildIn where

data LispVal = Atom String
| List [LispVal]
| DottedList [LispVal] LispVal
| Number Integer
| String String
| Bool Bool

Parsers.hs:

module Parsers where

import Monad
import Text.ParserCombinators.Parsec hiding (spaces)
import BuildIn

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

spaces :: Parser()
spaces = skipMany1 space

readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"

parseString :: Parser LispVal
parseString = do char '"'
x <- many (noneOf "\"")
char '"'
return $ String x

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
rest <- many (letter <|> digit <|> symbol)
let atom = first:rest
return $ case atom of
"#t" -> Bool True
"#f" -> Bool False
otherwise -> Atom atom

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

parseExpr :: Parser LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber

Parser.hs

module Main where

import System.Environment
import Parsers

main :: IO ()
main = do args <- getArgs
putStrLn (readExpr (args !! 0))

2008年12月7日星期日

Write Yourself a Scheme in 48 Hours/Parsing(三)

上一节的时候我们讨论到了用附加的解释器组件扩展功能的方法。这一次我们再加些料。 首先,我们定义出Scheme语言中的一些类型:

Haskell语言: Parsing 代码片段六

data LispVal = Atom String
| List [LispVal]
| DottedList [LispVal] LispVal
| Number Integer
| String String
| Bool Bool

事实上,Haskell里一切都可以看作是函数,data也不例外。千万不要拿这个东西去随便对应你以前见过的其它叫data的东西。事实上 Haskell里的Type、Class、Instance和Data跟OO语言里的概念都完全不是一回事儿。如果你有学过近世代数,可以去看看上节里推 荐的T1的那篇Monad教程。

这里,使用data,我们定义了 LispVal 可能的几种类型:

  • Atom 是一个文本,它表示一个原子命名
  • 若干 LispVal 的序列成为一个 List (注意 List 也是一种 data Lispval,所以这是一个递归的定义)
  • . 联接列表和一个 LispVal 值,组成一个 DottedList
  • Number 存储整数
  • String 存储字符串
  • Bool 存储逻辑值

因为Haskell的类型和构造器取自不同的命名空间,所以这里我们定义了与系统类型相同的String、Bool之类的类型,也不会靠成什么问题。类型和构造器都是PASCAL命名。

现在编写几个解释器函数。首先是字符串。字符串是一对双引号标记,包含若干文。

Haskell语言: Parsing 代码片段七

parseString :: Parser LispVal
parseString = do char '"'
x <- many (noneOf "\"")
char '"'
return $ String x

这儿又出来一新的妖招:我们没用 >>,而是用了一个do。这是为了可以取到引号之间的值,这里我们用了char和many两个解析工具。按作者的解释,通常不需要取得 action返回值的时候(比如为了组合它们生成新的monad),使用>>,而需要取值并用于下一个action的时候,用 >>= 或 do-notation。

取值完成以后,我们将其 return 为一个 LispVal 。抽象数据类型中的每个构造器也同样可以看作是一个函数:返回一个该类型的值。函数进行参数的式匹配的时候,也可以根据data来匹配。

内置函数 return 可以把我们的 LispVal 提升为一个Parser monad。每一行do代码虽然都要求是同一个类型,但是但是我们的字符串解析函数只是返回了一个 LispVal,这时候就靠 return 帮我们搞定这个类型封装啦。这样,整个 parseString action 就成为了一个 Parser LispVal。

$只是括号的简写 return $ String x 等同于 return (String x),这个在Haskell的语法教程中都会有介绍。不过这里有特别提出,$是一个操作符,所以你能对一个函数做什么,就能对它做什么,传递、局部化等 等。在这里,它相当于一个 apply。

Atom 就是一个原子语素,一个字母或符号,跟随若干数值或字母、符号之类的:

Haskell语言: Parsing 代码片段八

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
rest <- many (letter <|> digit <|> symbol)
let atom = first:rest
return $ case atom of
"#t" -> Bool True
"#f" -> Bool False
otherwise -> Atom atom

这里出现了一个新的 Pasec combinator,选择运算符 <|>。它尝试第一个parser,失败就尝试第二个。哪个成功就返回哪个parser的值。

读取语素的第一个字符以及其余部分后,我们需要把它们合在一起。let语法定义了一个atom变量,我们使用联接符:把它们联起来。如果不用:,还可以用 [first] ++ rest。

case是基本语句,语法书都讲得很明白,这里不多讨论了。

发芽网挂了……明天再继续吧……

有一件挺让人无语的事儿就是你费事儿排的版它总不给显示,在Blogger的编辑器上编辑源码真不是人干的事儿,现在我改用Muse了……不过还是比较麻烦的……有些代码我想还是放到发芽上比较方便。

2008年12月6日星期六

Write Yourself a Scheme in 48 Hours/Parsing(二)

囧然发现,代码的排版总是会丢失缩近。这个当然不能怪发芽网的服务不好,因为直接可以看到的是blogger的有些模板就有问题。这东西的可视化编辑器又慢,功能又不全。

我现在用gmail的内置编辑器,不过这东西也不能算好用,它没办法编辑HTML源码。网上有人贴过muse向blogger发布的代码。等这个坑填完我肯定是要再去弄muse的,到时候不妨拿来看看(话说,muse真是个好东西吖)。

上次讲到了如何利用 oneOf 函数提取代码中的符号。因为我们没有处理空格,如果符号前有多的空格,就会出错了。

作者的解释是,Parsec的spaces不符合他的要求,虽然另有一个lexeme可用,但是这里我们可以自己定做一个。

Haskell语言: Parsing 代码片段四

spaces :: Parser ()
spaces = skipMany1 space

这东西其实比我猜想的简单多了,还是直接拿了一个东西来用,跟oneOf换汤不换药嘛。

现在我们修改一下readExpr,把这个新组件串进去。

readExpr input = case parse (spaces >> symbol) "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"

这里我没用发芽网的服务,主要是给大家看到红字标明的修改标记。如果没有心理准备,大概会被这个简单的用法小小震惊一下。>>符号是 Monad 的四个标准运算符之一,"bind"操作符。通过它,我们把skipMany1 space传入symbol中,组成一个新的parser Monad。这里作者特别有介绍,不同的Monad,它的bind行为可能完全不同。具体的情况一定要阅读文档来确定。在Parser Monad中,它就是尝试匹配第一个组件,不行再匹配第二个,直至匹配成功或最终返回错误。

Monad一个非常强大的地方就在于这种组合能力,这与OO中的继承或接口复用还是有很大不同的。等这个教程跟完,如果我觉得我对Monad有些了 解了,可能会写一些关于Monad的文章。其实关于Monad,国内已经有一篇非常强大的文章,来自Javaeye社区的Trustno1。简单介绍一下 背景,这大佬多年以前在程序员上以"恶魔吹着笛子来"为署名写了一系列Python教程,这几篇文章将我和很多程序员引入了Python领域。至于 Lee……不需要我多介绍了吧:)。

这一小节的完整代码:

Haskell语言: Parsing第二部分的完整代码

module Main where

import System.Environment
import Text.ParserCombinators.Parsec hiding (spaces)

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

spaces :: Parser()
spaces = skipMany1 space

readExpr :: String -> String
readExpr input = case parse (spaces >> symbol) "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"

main :: IO ()
main = do args <- getArgs
putStrLn (readExpr (args !! 0)

Write Yourself a Scheme in 48 Hours/Parsing (一)

前一章其实标题本来是"编译与运行"。但是这两步反而难度不高,看了教程就很容易能明白,所以我没有讨论它。 上一章里重点介绍了开发工具,因为Haskell的语法决定,我们需要一个顺手的工具。 还重点介绍了Monad,主要是从我等下里巴人的角度解释一下怎么用它。 对于一个完全的新手,其实还应该学习一些关于Haskell基本数据结构和函数定义的知识,不过这方面的东西最好找专门的Haskell语言教程。

这一章,会继续练习Monad的使用。我们还会见到一些来自GHC标准库的强大武器。

这次我们 import 进来一个新的库

import Text.ParserCombinators.Parsec hiding (spaces)

Parsec库是Haskell中专门的解释器工具库。hiding关键字指出,我们导入这个库时,把 spaces 函数排除在外--因为我们随后要自己实现一个不同的逻辑。

Haskell语言: Parsing 代码片段二

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

上面是类型声明,也就是说给oneOf函数传这一串符号进去,它返回一个解释器类型。其接收代码文本,针对oneOf传入的符号串进行处理。类似oneOf的这些解释器Monad生成工具,在Parsec库里还有一些其它的解析工具,后面我们会用到一些。

OK,这个解释器(其实是个解释器零件)我们怎么使用它呢?现在我们写一个解析表达式的工具:

Haskell语言: Parsing 代码片段三

readExpr :: String -&gt; String
readExpr input = case parse symbol "lisp" input of
Left err -&gt; "No match: " ++ show err
Right val -&gt; "Found value"

这个用法很简单,利用 Parsec 库的 parse,我们把定义好的 symbol 传给 parse ("lisp" 作为注册进来的 symbol 的命名),然后接收一个字符串,parse会返回一个 data ,其中 Left 是表示错误信息,err中有具体内容,Right val则是匹配正确后的结果,这里我们先不管它返回了什么,输出一个"Found value"。

这段程序可以看出,symbol 的作用比较简单,只要字符串里有任一个匹配oneOf的字符,解析器会把它做为一个词素提出来。而parse就处理这个解析结果。

这样,很简单的接收命令行参数然后传出解析结果。!!是haskell的列表索引操作符。也就是说,它只处理args的第一个元素。 编译以后执行试试吧,你会看到,它校验你输入的文本中,第一个字符是否在symbol注册的符号中。并返回相应的值。 解释器还很简单,但是后面我们会慢慢完善它。

这一章的重点,在于学会如何组合多个函数或Monad。具体的原理和定义,推荐一份已经被汉化出来的教程:函数式编程另类指南,其中的currying和Continuations知识,与我们在这里使用的组合技术相关。

事实上,如果那东西把你搞糊涂了,倒不如当那些名词和定理不存在,我们继续写程序吧XD。

今天的代码:

Haskell语言: Parsing的完整代码

module Main where

import System.Environment
import Text.ParserCombinators.Parsec hiding (spaces)

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

readExpr :: String -&gt; String
readExpr input = case parse symbol "lisp" input of
Left err -&gt; "No match: " ++ show err
Right val -&gt; "Found value"

main :: IO ()
main = do args &lt;- getArgs
putStrLn (readExpr (args !! 0))

柚子!

今天在超市看到一个小朋友,大概也就一岁多两岁。爷爷买了两个大柚子,他坐在车里抱着柚子玩。到收银台爷爷把柚子拿给收银员,小朋友哇的一声就哭了,一边哭还一边往收银台上爬,想把柚子抢回来。收银员赶紧刷完把柚子还给他。柚子一抱到怀里,小家伙立刻就安静了,脸上还挂着泪珠。安安静静的坐在购物车里。

2008年12月2日星期二

Write Yourself a Scheme in 48 Hours/First Steps

本章原文地址: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/First_Steps

第一章的内容不多,准备知识而已。这一章的名字就叫“First Step”。起点也很朴实:开发环境的准备。

前面说过,这份例子是以最主流的Haskell编译器ghc为工具的。当然,ghc本身有一个还不错的shell环境,ghci。不过我们是要跟着写代码,做项目的,不能关机就扔,所以得要有个正经的源码编辑器。

作者推荐Emacs,如果你在Windows上,可以试试ntemacs。Emacs有个相当中规中矩的haskell-mode。里面的功能说实话我还没好好挖掘过,不过值得向大家推荐一下,默认的设置就算挺好用了。

如果你用不惯Emacs,其实VIM也不错,我本人是Emacs党,不过有回也试了试用VIM写Haskell代码,对于我这类初级用户,感觉没太 大差别。本书作者认为,hskell不是一种用记事本能搞定的语言。确实,虽然它只是纯文本,但是数学化的灵魂还在(还记得数学里那些鬼画符一样的表达式 吧),如果记事本,缩进格式足够把人搞疯的。不需要什么很伟大的IDE,有个靠谱的文本编辑器还是有必要的。

其实作者也有交待,你要是真用不惯这些 “非”主流编辑器,Eclipse有个 Fucntion Programming,联想到Eclipse连支持个XML都JJYY,这个Haskell插件竟然已经到了0.9.x,haskell这个圈子水真深啊……)。甚至还有个 http://www.haskell.org/visualhaskell/ ,看截图应该是VS6的,不过这种小众语言能支持这玩意儿已经很雷人了)。

另外,我相信一个另小众的编辑器:yi肯定是支持Haskell的。因为,它是Haskell写成的!这东西我没用过,不过谣言频道有人刷屏说这是一款向 Emacs 致敬的作品。从截图看真的有点像Emacs。

本章的示例代码不多,写个简单的入门例程:

module Main where
import System.Environment

main :: IO ()
main = do
args <- getArgs
putStrLn ("Hello, " ++ args !! 0)

如果你对Haskell还不熟……嗯……

module Main这一行用来声明一个模块,这东西比较像Python的模块概念(如果你没学过Python,这句话请无视)。虽然写个小脚本的话你不加这个也能跑,不过养成好习惯总是好的。

import 显而易见,就是用来导入外部模块的。这东西跟Python里用法差不多(如果你没学过Python,这句话请无视)。

4-7行很短,但是对于有学过其它编程语言的人会是一种颠覆性的打击,就算你上一门学的是Python也一样(如果你没学过Python,这句话请无视)。

第 4行是函数类型声明,它指明了main函数的类型是IO单子,这就是它的返回值。这在Haskell语言里是不同寻常的一种类型。我们先把这个事儿放一 边。之前如果你学过其它编程语言,那么我想你还记得,有些语言一定要有类型声明,比如C++或Java;有些语言根本没有类型声明,比如Python(如 果你没学过Python,这句话请无视)。

然而Haskell这个变态,是可以有类型声明,也可以没有的。如果你不写,它会自己猜,然后选匹配的类型里最常用的来编译(这一点不同于 Javascript的动态类型)。以我的经验,只要你程序写得正确没有bug,几乎不会出现猜不出来的。然而,自己明确指定类型,可运用到更精准和丰富 的数据类型。显然,从可读性上讲也是有好处的。当然,C#也有类似的匿名类型,Haskell学的C#也说不定。

如果你在知道Haskell是上世纪八十年代就有的语言以后还看不出上句话是一个冷笑话,还是不要学Haskell了……

顺便说一下,haskell对程序代码的排版规范要求非常严格,首先它的语法结构依赖缩进,这一点和Python一样(如果你没学过Python, 这句话请无视),子语句要缩进一级,这一点Haskell学的Python也说不定(参见上一段!)。其次,所有模块名都应该是PASCAL命名,所有函 数名都应该是驼峰命名,切记!

现在我们终于说到这个万恶的单子(Monad)了。作为一门纯函数语言,Haskell是相当数学化的,我个人觉得 Haskell根本就是一门代数语言。它的函数其实就是算法定义。所以要求必须是“确定的”。也就是说,函数内部除了返回值,不能影响到外部。函数本身输 入值固定的话,必须确定的返回固定的值。

但是这样的话,就没办法解决一些麻烦,比如程序运行过程中需要保存状态,程序本身需要输入输出(不然我们怎么看到结果呢?)。这些功能都是不符合确定性的。

所以,Monad就应运而生了。关于Monad的定义,Haskell有一套漂亮的表达。不过我现在不打算关注它。我们只要知道这个东西相当于可以传递和保存值的对象就可以了。现在我们的任务是,先学会用现有的Monad,比如本教程中提到的各种Monad。

Haskell的main函数相当于c的main函数,都是程序执行入口,所以没得说,这个肯定是一个Monad,事实上它必须是IO()。所以我们的程序代码也一定要匹配这个结果。

如果要返回一个Monad,有两种办法,一种是把返回值用return 函数封装(编译器会根据你的函数定义选择类型),术语称为lift,当然,被lift的值要匹配定义的Monad;另一种是组合多个Monad。

后者看起来麻烦,其实操作起来很简单。比如do操作,它后面可以带多行语句,每一行要么是一个action,要么是一个a<-action的 取值操作。这里的action,就是指Monand化的一个事物,可以理解为一个对象实例(那么一个Monad定义可看作是一个类定义)。

因为串化为一组Monad,do的子语句是按顺序执行的,do块相当于我们在普通的命令式语言中编写的代码片段。

想到这一点,或许你会初步体会到Haskell是一个多么与众不同的语言。

实际上do对每行代码有更细致的规定,它其实是一个语法糖,本原是一组Monad串行操作。如果原文你不能允分理解,没关系,后面我们还会大量运用Monad,我们会熟悉它的。

本章教程最后还讲解了运算符和例程的编译方法,这个没有太惊诧的东西,不多讨论了。

重点学习读取输入,打印字符到输出,基本编译指令。

以及,Haskell中字符串就是序列,它的联接用++,而不是单个加号。