Reading Note: The Implementation of Functional Programming Languages

最近(又)开始挖坑想造语言,于是翻出了SPJ爷的The Implementation of Functional Programming Languages
要说这书1987年就出版了,比我岁数还大orz。书从lambda calculus讲起,到High level language的compile,
最后说到Graph Reduction以及G-Machine,完整的讲述了如何在冯诺伊曼架构下实现函数式语言。

书分三个部分,Compiling High Level Language,Graph Reduction和Advanced Graph Reduction(喂。
笔记也会按照章节来写,补充一些细节啥的(大概。

Part I: Compiling High Level Languages

Part II: Graph Reduction

Part III: Advanced Graph Reduction

行程备忘

交通

飞机

  • 2016.02.15 北京-东京 [08:25 - 12:45] < T3, 羽田 > JL020
  • 2016.02.21 东京-冲绳 [10:30 - 13:20] <羽田, 冲绳> NH469
  • 2016.02.25 冲绳-东京 [14:10 - 16:30] <冲绳, 羽田> NH468
  • 2016.02.27 东京-北京 [18:00 - 21:30] <成田, T3> JL869

地下铁


住宿

  • 02.15 - 02.20 ホテルマイステイズ横浜(中区末吉町4-81,横浜市, 231-0055)

    • 机场->宾馆(方案一 ¥480) :
      Keikyu Line Haneda Airport Domestic Termination Station ->
      (京急机场线:Airport急行 新逗子) -> 6站同车(京急本线) -> 神奈川新町 ->
      (京急本线 各停 开往浦贺) -> 黄金町 -> 120米
      
  • 02.20 - 02.21 東京木場ホテル(江東区木場1-4-3, 江東区, 東京都, 135-0042)

    • 宾馆->宾馆(¥640):
      黄金町 -> (京急本线各停->品川) -> 横滨 -> (京急本线快特->京成高砂) -> (同车浅草线) -> 日本桥
      -> (东西线->东叶胜田台) -> 木场(东京) -> 270米
      
    • 宾馆->机场(¥730):
      木场 -> (东西线->中野) -> 日本桥 -> (浅草快特->羽田机场) -> (坐10站就对了) -> Keiyu Line Haneda
      
  • 02.21 - 02.25 HOTEL StoRK 那覇新都心(おもろまち2-6-40 那覇市, 900-0006)

    • 机场->宾馆(¥300): 结心电车(赤嶺駅 - 歌町)
    • 宾馆->机场(¥300): 结心电车
  • 02.25 - 02.27 〒フレックステイイン東十条(114-0032 東京都, 北区中十条2-10-2, 日本, 東京都, JP)

    • 机场->宾馆(¥710):
      羽田机场第二大楼 -> (东京单轨电车) -> 滨松町 -> (京滨东北线) -> 东十条 -> 210米
      
    • 宾馆->机场(¥1400):
      东十条 -> (京滨东北线快速->蒲田) -> 田端(东京) -> (山手线:各停 外环) ->
      日暮里 -> (京城本线特急->成田空港) -> 京成高砂 -> (sky kusesu线->成田) -> 空港第二楼
      

预算总计: ¥4560


安排

日期 宿泊 早间备选地点 午饭 下午备选地点 晚饭 备注+晚间
02.15 横滨 飞机餐 横滨站周边 豊野丼^1 抵达12:45 休整好约14:00
02.16 横滨 中华街、关帝庙 福満園^2 sea paradise水族馆 CANTINA逗子店^3 晚餐也可选择松屋
02.17 横滨 三溪园 Kichinro拉面 泡面博物馆 一风堂 lotteria汉堡!!
02.18 横滨 铁道模型博物馆 回转寿司[^6] 拉面博物馆 温野菜^4五点之后 藍屋 いたり家^5
02.19 横滨 富!士!山! 华丽屋咖喱 lotteria汉堡 Makaino Farm牧场可以一去
02.20 东京 秋叶原 高达咖啡 果断还是秋叶原 Isomarusuisan
02.21 那霸 国际大道 Suitenrou
02.22 那霸 首里城 しむじょう^7 金城町石叠 备选里挑一家吧 备选餐厅^8 三竹寿(tsuke面)
02.23 那霸 识名园 蓝蓝路无名汉堡 波之上海滩 高良食堂
02.24 那霸 やちむん通り Bambohe烧肉^9 午饭吉野家! 奢侈的kaki小屋(5:30)
02.25 东京 第一牧志公设市场 2F海鲜饭! 随便吧(
02.26 东京 台场看无聊的高达 回转寿司[^10] 大概就是秋叶原了
02.27 北京 回家啦

[^6]: Mawashizushi KATSU katumidori.co.jp

[^10]: Muten Kura Sushi Shinagawa Ekimae

一颗赛艇的Haskell资料

感觉有必要留出一个地方Mark一些很Mind Blow的资源,来观察一下我的技能树到底是怎么点歪的(误
绝赞更新中!(不

  • The Algebra of Algebraic Data Types

    Type calculus好顶赞。解释了我多年Algebra Datatype为什么名字带Algebra的困惑(。
    在类型上做代数运算什么的简直打开了新世界的大门!

  • Comonads are objects

    我见过最通俗易懂的介绍Comonad的文章。通俗到了什么程度呢?在看前两个例子的时候我甚至没反应过来是在说Comonad…
    如果说Monad使Haskell成为最好的命令式语言,那么Comonad就使Haskell成为了最好的面向对象语言(笑

Kata:Lens-Maker

最近在研究Profunctor这个东西。其定义虽然很简单但却有点意义不明..
听人安利这个Kata做完就会有个大概的认识于是试一试。

这个Kata基本上就是从头造个Lens库出来.. 难度自然也是鬼畜级别的。所以可能会坑很多天..


首先是一些基本类型定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE RankNTypes #-}

module MicroLens where

import Control.Applicative
import Data.Monoid
import qualified Data.Traversable as T
import Prelude hiding (sum)
import Unsafe.Coerce

---------------------------------------------------------
-- Some basic libraries

class Profunctor p where

dimap :: (a' -> a) -> (b -> b') -> (p a b -> p a' b')
dimap f g = lmap f . rmap g
lmap :: (a' -> a) -> (p a b -> p a' b)
lmap f = dimap f id
rmap :: (b -> b') -> (p a b -> p a b')
rmap f = dimap id f

class Profunctor p => Choice p where

left' :: p a b -> p (Either a c) (Either b c)
right' :: p a b -> p (Either c a) (Either c b)

instance Profunctor (->) where

dimap f g h = g . h . f

instance Choice (->) where

left' f = either (Left . f) Right
right' f = either Left (Right . f)

class Contravariant f where

contramap :: (a' -> a) -> (f a -> f a')

-- Control.Applicative.Const replicated here for your
-- convenience
newtype K b a = K { getK :: b } deriving Functor

instance Monoid b => Applicative (K b) where

pure _ = K mempty
K e <*> K f = K (e <> f)

instance Contravariant (K b) where

contramap f (K b) = K b

newtype Id a = Id { getId :: a } deriving Functor

instance Applicative Id where

pure = Id
Id f <*> Id x = Id (f x)

---------------------------------------------------------
-- The lens types you'll implement

-- | Optic is the general pattern for all other lens types.
type Optic p f s t a b =
p a (f b) -> p s (f t)

type Iso s t a b =
forall p f . (Profunctor p, Functor f) =>
Optic p f s t a b

type Lens s t a b =
forall f . Functor f =>
Optic (->) f s t a b

type Traversal s t a b =
forall f . Applicative f =>
Optic (->) f s t a b

type Fold s a =
forall f . (Contravariant f, Applicative f) =>
Optic (->) f s s a a

type Prism s t a b =
forall p f . (Choice p, Applicative f) =>
Optic p f s t a b

那么先从最简单的_1,_2开始。它们的语义很简单,分别“聚焦”于一个pair的第一个元素和第二个元素。

1
2
3
4
5
6
7
-- | A lens focusing on the first element in a pair
_1 :: Lens (a, x) (b, x) a b
_1 = undefined

-- | A lens focusing on the second element in a pair
_2 :: Lens (x, a) (x, b) a b
_2 = undefined

类型签名可能有些吓人,不过我们展开之后可以发现,_1的类型为(a -> f b) -> ((a, x) -> f (b, x)),某种意义上相当于pairfmap
Follow the type,我们可以很容易地写出实现:

1
2
3
4
5
6
7
-- | A lens focusing on the first element in a pair
_1 :: Lens (a, x) (b, x) a b
_1 = \f (a,x) -> (, x) <$> f a

-- | A lens focusing on the second element in a pair
_2 :: Lens (x, a) (x, b) a b
_2 = \f (x,a) -> (x, ) <$> f a

update : 今天肝完了后半部分.. 然而完全不理解自己在做什么。于是放上看到的最优雅的实现,希望有朝一日我也能解释(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
-- | A function which takes a lens and looks through it.
-- The type given is specialized to provide a hint as to
-- how to write 'view'. The more intuitive type for its use
-- is
--
-- @
-- view :: Lens s t a b -> (s -> a)
-- @
view :: Optic (->) (K a) s t a b -> (s -> a)
view l = getK . l K

-- | A function which takes a lens and a transformation function
-- and applies that transformer at the focal point of the lens.
-- The type given is specialized to provide a hint as to how to
-- write 'over'. The more intuitive type for its use is
--
-- @
-- over :: Lens s t a b -> (a -> b) -> (s -> t)
-- @
over :: Optic (->) Id s t a b -> (a -> b) -> (s -> t)
over l f = getId . l (Id . f)

-- | A function from a lens and a value which sets the value
-- at the focal point of the lens. The type given has been
-- specialized to provide a hint as to how to write 'set'. The
-- more intuitive type for its use is
--
-- @
-- set :: Lens s t a b -> b -> (s -> t)
-- @
set :: Optic (->) Id s t a b -> b -> (s -> t)
set l b = getId . l (Id . const b)

-- | A traversal which focuses on each element in any
-- Traversable container.
elements :: T.Traversable f => Traversal (f a) (f b) a b
elements = T.traverse

-- | A function which takes a Traversal and pulls out each
-- element it focuses on in order. The type has been
-- specialized, as the others, but a more normal type might be
--
-- @
-- toListOf :: Traversal s s a a -> (s -> [a])
-- @
toListOf :: Optic (->) (K (Endo [a])) s s a a -> (s -> [a])
toListOf l s = appEndo (getK $ l (\a -> K $ Endo (a:)) s) []

-- | A function which takes any kind of Optic which might
-- be focused on zero subparts and returns Just the first
-- subpart or else Nothing.
--
-- @
-- preview :: Traversal s s a a -> (s -> Maybe a)
-- @
preview :: Optic (->) (K (First a)) s s a a -> (s -> Maybe a)
preview l s = getFirst (getK $ l (\a -> K $ First $ Just a) s)

-- | A helper function which witnesses the fact that any
-- container which is both a Functor and a Contravariant
-- must actually be empty.
coerce :: (Contravariant f, Functor f) => f a -> f b
coerce = contramap (const ()) . fmap (const ())

-- f a -> f Void

-- | A Fold which views the result of a function application
to :: (a -> b) -> Fold a b
to f g = contramap f . g . f

-- | A prism which focuses on the left branch of an Either
_Left :: Prism (Either a x) (Either b x) a b
_Left = rmap (either (fmap Left) (pure . Right)) . left'

-- | A prism which focuses on the right branch of an Either
_Right :: Prism (Either x a) (Either x b) a b
_Right = rmap (either (pure . Left) (fmap Right)) . right'

-- | An iso which witnesses that tuples can be flipped without
-- losing any information
_flip :: Iso (a, b) (a, b) (b, a) (b, a)
_flip = dimap swap (fmap swap) where swap (a, b) = (b, a)

Emacs配置流水账

一直看Haskell群里的人安利Emacs,于是想试试看到底怎么样。遇到的问题什么的大概都会堆到这里嗯。

安装Emacs

之前也是道听途说Spacemacs这个Emacs发行版做的非常好,于是就偷懒直接用未修改的spacemacs了(其实是不会改吧。

先到GNU官网弄个Emacs原版,然后把spacemacs配置文件clone到~/.emacs.d/就行了。

安装Haskell-Mode

spacemacs默认似乎并不带许多语言的支持,所以第一件事当然是要先装上haskell-mode。按照文档一步步来就没问题了。

这么干会被spacemacs无情的删掉!正确的方法请看下面(

待更。


2016.01.31 update

快捷键好多啊orz 而且Evil这货是要我同时背下emacs和vim的快捷键吗!(虽然确实很好用(逃

install custom packages

不同于普通的Emacs直接使用M-x package-install,spacemacs竟然会自动删掉这样装好的包… 对于一个啥都不懂的新手来说真是无比嘲讽。出现这个问题的原因是因为spacemacs引入了layer的概念(大概相当于文件夹?),不属于任何layer的包会被当作orphan包删掉… 解决办法:

  • 不使用layer

不使用layer的方法也是可行的,不过最好还是不要这么干。只需要把包加入配置文件中的dotspacemacs-additional-packages就好了。大概就是…

1
(setq dotspacemacs-additional-packages '(<package-1> <package-2> ...))

然后可以在dotspacemacs/user-config里写配置。

  • 创建一个自定义layer

比如说我需要装各种haskell插件,于是M-x configuration-layer/create-layer先创建一个layer,位置在private就好(文档上看似乎只有private是装包能用的,不过git will be ignored是怎么回事…)。之后就会要求给这个layer起个名字,我这里叫Haskell(然而规范都是小写,好孩子不要学)。

生成好的文件位于~/.emacs.d/private/<layer>下,结构大概像这样:

1
2
3
4
5
6
7
8
9
[layer-name]
|__ [local]*
| |__ [example-mode-1]
| | ...
| |__ [example-mode-n]
|__ config.el*
|__ funcs.el*
|__ keybindings.el*
|__ packages.el

看不懂也没什么关系… 只需要打开(C-x C-fpackages.el修改一下就行了。比如我想要装haskell-mode,ghc-mod,structure-haskell-mode这三个插件,那么就要把这里改成这样:

1
2
3
4
5
6
7
(setq Haskell-packages
'(
;; package names go here
haskell-mode
ghc
shm
))

这样还不算完成配置,还需要为每一个包定义初始化函数。

1
2
3
4
5
6
7
8
(defun Haskell/init-haskell-mode ()
(use-package haskell-mode))

(defun Haskell/init-ghc ()
(use-package ghc))

(defun Haskell/init-shm ()
(use-package shm))

这里只用了最简单的use-package变量,更多的用法可以参考use-package文档。快捷键什么的,以后再折腾吧。

配置好以后使用C-x C-s保存,然后SPC f e R可以重新加载配置文件,之后emacs就会安装列出来的这些包了。

更改主题

其实本来spacemacs默认的主题给我的印象还不错,直到我打开了一个haskell文件… 所以更换一个更顺眼的主题就是下一个折腾的目标了。毕竟现在还不会手写emacs lisp来搞一些黑科技,所以姑且就先求助于themes-megapack吧。

这个包好想自带了,所以只需要在~/.spacemacs里面的dotspacemacs-configuration-layers中添加themes-megapack就好了。里面大概有86种主题(虽然好看的没几种),可以在theme gallery预览。个人还是比较偏好sanityinc-tomorrow-night啦,monokai在这里支持的着色似乎有些少?

可以使用SPC T h来选择主题,但需要注意的是这不是永久变更。如果更改每次启动时加载的主题的话,需要把~/.spacemacs里面的dotspacemacs-themes的第一项改成选好的主题名字。


2016.02.01 update

添加自动补全

话说默认竟然是没有自动补全的还是有点不爽,虽然什么都自己动手来大概就是开源社区的哲学吧(。打开基础的补全功能需要auto-complete这个插件,在.spacemacs里取消注释就行了。之后需要为auto-complete提供一个后端,这里用company-ghc。安装什么的都和上面一样,配置里要显示指明一下:

1
2
3
4
5
6
7
(defun haskell/init-company-ghc ()
(use-package company-ghc)
:init
(require 'company)
(add-hook 'after-init-hook 'global-company-mode) ;; global mode
(add-to-list 'company-backends 'company-ghc)
(custom-set-variables '(company-ghc-show-info t)))

这样就能实现函数的补全了。标准库什么的完全没问题!不过目前来看还有两个缺点,一个是启动时速度有些慢,另一个比较烦的是没法补全模块名称。这个哪天再折腾一下吧。

haskell-mode的一些完善工作

首先,装一些不错的包

1
cabal install hasktags structured-haskell-mode stylish-haskell present

给haskell-mode添加一些key-bindings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
;; (defun haskell/init-haskell-mode ()
;; ...
:config
(custom-set-variables
'(haskell-process-suggest-remove-import-lines t)
'(haskell-process-auto-import-loaded-modules t)
'(haskell-process-log t)
;; add cabal repl support.if use stack, replace 'cabal-repl with 'stack-ghci.
'(haskell-process-type 'cabal-repl))

(eval-after-load 'haskell-mode '(progn
(define-key haskell-mode-map (kbd "C-c C-l") 'haskell-process-load-or-reload)
(define-key haskell-mode-map (kbd "C-c C-z") 'haskell-interactive-switch)
(define-key haskell-mode-map (kbd "C-c C-n C-t") 'haskell-process-do-type)
(define-key haskell-mode-map (kbd "C-c C-n C-i") 'haskell-process-do-info)
(define-key haskell-mode-map (kbd "C-c C-n C-c") 'haskell-process-cabal-build)
(define-key haskell-mode-map (kbd "C-c C-n c") 'haskell-process-cabal)
(define-key haskell-mode-map (kbd "SPC") 'haskell-mode-contextual-space)))
(eval-after-load 'haskell-cabal '(progn
(define-key haskell-cabal-mode-map (kbd "C-c C-z") 'haskell-interactive-switch)
(define-key haskell-cabal-mode-map (kbd "C-c C-k") 'haskell-interactive-mode-clear)
(define-key haskell-cabal-mode-map (kbd "C-c C-c") 'haskell-process-cabal-build)
(define-key haskell-cabal-mode-map (kbd "C-c c") 'haskell-process-cabal)))

然后可能就是折腾一下ghc-mod和学习一下它们复杂的快捷键了orz。


2016.02.02 update

啊啊果然之前是ghc-mod没有配置好。每次都在这里po配置实在太麻烦了,于是把配置放在了github上(https://github.com/SuperHex/spacemacs-haskell-config)。
之后就专心维护这份配置文件了!之后可能会研究一下传说中逆天的org mode,希望能解救我于堆积如山的bookmark之中吧(。今天好水啊(。

使用Continuation Monad实现Coroutine

其实知道Continuation Monad还可以这么用还是因为CodeWars上的一道题。足足肝了三天还是没完全想明白orz。姑且先记录一下现在的想法吧。

先来回顾一下Continuation Monad的定义:

1
2
3
4
5
newtype Cont r a = Cont { runCont :: (a -> r) -> r }

-- useful alias
(|>) :: a -> (a -> r) -> r
x |> f = f x

从上一篇文章中我们知道f >>= g不过就是f x展开为一连串的apply形式:

1
2
3
4
Cont r x == ($ x)
== \f -> x |> f
== \f -> x |> (\g -> g |> f)
== \f -> x |> (\g -> g |> ... (\z -> z |> f))

这种形式到底有什么用呢?我们马上就能看到。

现在的问题是Coroutine该如何实现?我们可以把它抽象为一个指挥棒传递的过程。一个线程x开心的运行着一些计算,直到它需要输入或输出一些数据。这个时候它把指挥棒交给另一个线程y,直到y产生一些输入输出,再交还指挥棒。等等,这个描述是不是和上面的展开式有点像?如果把每一个lambda表达式都看成一个计算的话,这正是我们需要的。于是根据语义我们可以写下

1
2
3
4
5
6
7
8
9
{-# LANGUAGE DeriveFunctor #-}

-- u : input type d : output type
newtype Coroutine r u d a = Coroutine { runCoroutine :: (a -> r) -> r } deriving Functor

data Command r u d a = Done a
| Out d (Coroutine r u d a)
| In (\u -> Coroutine r u d a)
deriving Functor

这里详细的解释一下。Coroutine实际上和Cotinuation是一个东西,只不过多了额外的两个类型参数。u为输入参数的类型,d为输出参数的类型。Command r u d a里则定义了三种基本类型,分别为Done a表示计算完成,没有输入输出;Out d (Coroutine r u d a)表示输出类型为d的数据,同时执行参数中的计算;In (\u -> Coroutine r u d a)表示需要输入数据,并在等待输入时执行参数中的计算。很优雅的抽象,对吧?下一步就是将Coroutine声明为Monad:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- useful alias
apply = runCoroutine

instance Applicative (Coroutine r u d) where

pure = return
(<*>) = ap

instance Monad (Coroutine r u d) where

return a = Coroutine ($ a)
f >>= g = Coroutine $ \k -> apply f $
\a -> case a of
Done x -> (g x) `apply` k
Out d c -> k $ Out d (c >>= g)
In fn -> k $ In (\u -> fn u >>= g)

这里在做的实际上和原来并没有太大区别,只是在每一个lambda表达式中多了一个判断。

  • 如果计算完成了(Done a),那么直接进行下一个计算。
  • 如果计算需要输出类型为d的数据(`Out d (Coroutine r u d a)),那么挂起这个计算,直到另一个计算返回结果,并将函数应用到这个结果上。
  • 如果计算需要输入一个u类型,那么同样挂起计算,等到有输入的时候将输入传给另一个计算。

这样看起来可能很抽象,并且我们现在还没办法构建真正的”continuation” 。不妨定义一些helper function:

1
2
3
4
5
6
7
8
9
10
11
output :: a -> Coroutine r u a ()
input :: Coroutine r v d v
produce :: [a] -> Coroutine r u a ()
consume :: Coroutine [t] u t a -> [t]
filterC :: (v -> Bool) -> Coroutine r v v ()
limit :: Int -> Coroutine r v v ()
suppress :: Int -> Coroutine r v v ()

-- alias
mkCoroutine :: Command r u d a -> Coroutine r u d a
mkCoroutine command = Coroutine ($ command)

先来看output,我们希望它立刻输出一些东西,于是可以写出:

1
2
output :: a -> Coroutine r u a ()
output v = mkCoroutine $ Out v (return ())

然后是input,它在获取一个输入后返回它:

1
2
input :: Coroutine r v d v
input u = mkCoroutine $ In (\u -> return u)

produce连续的产生输出,而consume将所有的Out提取出来:

1
2
3
4
5
6
7
8
produce :: [a] -> Coroutine r u a ()
produce xs = mapM_ output xs

consume :: Coroutine [t] u t a -> [t]
consume c = runCoroutine c go
where go (Done _) = []
go (Out d n) = d : consume n
go (In _) = []

filterC挑选出每一个符合条件的输入并输出:

1
2
3
4
5
filterC :: (v -> Bool) -> Coroutine r v v ()
filterC p = do
i <- input
when (p i) (output i)
filterC p

最后,limit类似于takesuppress类似于drop

1
2
3
4
5
6
7
limit :: Int -> Coroutine r v v ()
limit n = replicateM_ n (input >>= output)

suppress :: Int -> Coroutine r v v ()
suppress n
| n > 0 = input >> suppress (n-1)
| otherwise = forever $ input >>= output

现在,我们就可以用这些函数来构建一些有趣的东西了

1
2
3
p1 = filterC even >>> limit 5

consume (produce [0..] >>> p1) === [0, 2, 4, 6, 8]

更多的玩法就留给读者去发掘吧w

Continuation Monad

啊啊啊啊Github连击又断掉了!好的那么我们今天来谈Continuation Monad(哭丧脸。

Continuation Monad 长什么样子?大概像这样:

1
2
3
4
5
newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where

return a = Cont ($ a)
m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c

那么Continuation究竟是一个什么概念?一般来说,Continuation表示的是“剩下的计算”的概念。熟悉命令式语言的读者可能对此没有什么概念,不过在命令式的世界里这件事可以粗略的表示为“分号后面的部分”。举个例子来说,假设我们这样一个表达式foo (bar x y) z,观察括号里面的部分,(bar x y)求值之后,需要应用到foo _ z。写成合法的表达式就是\a -> foo a z,这也就是“剩下的计算”的语义。这样,我们就可以通过把bar x y应用到\a -> foo a z来重新构建原来的形式。

不过这样看起来实在不太雅观,我们能不能把它变的好看一点呢?不如试试把外面的放到里面,把里面的放到外面?这样我们就有了\k -> k (bar a b)。这里k表示剩余的计算。

这样表示起来我们就获得了很好的灵活性。看看原来的表达式foo (bar a b) z,我们不仅仅把bar a b从上下文中提取了出来,而且还能在这个subexpression中操作外面的上下文!等等这个是不是听起来很耳熟?仿佛已经闻到了一股清新的Monad的气味!

不妨把这个想象成一种挂起的计算,并且我们能够显式地控制接下来将要发生什么。那么,我们要怎么推广到一般情况呢?观察到内部的subexpression并没有变化,不妨把它作为参数,得到\x k -> k x。呃…这不就是单纯的flip ($)吗!看起来,Continuation本质上并没有比函数应用多出什么东西。

那么作为一个Haskell程序员,我们这个时候肯定会思考这个东西,本质上是在一些上下文上面构建计算,这是个Monad吧?嗯没错,它的确是Monad。为了使它成为Monad,我们从两个基本的概念开始构建:

  • 对于Monad m,类型m a代表在这个Monad上下文当中的a类型
  • 我们挂起的计算本质上是颠倒顺序的函数应用

那么这个Monad的上下文是什么?对于x :: a来说,这仅仅意味着我们对它应用flip ($)$的类型签名为(a -> b) -> a -> bflip ($)的类型则是简单的a -> (a -> b) -> b。噢,看起来已经有点像Cont的形式了!正如一个continuation代表着“未来的”某种计算,类型a自然就代表着某种意义上的“过去”。把(a -> b) -> b替换成Cont b a,我们就得到了return的类型a -> Cont b a

所以一个Cont r a究竟意味着什么?不过是一个等待着接受一个函数a -> r,并把它应用到a类型的函数罢了。实际上,如果给一个id函数进去,Cont r aa完全是等价的!在这种语义下,>>=该怎么实现呢?

回想一下Continuation的语义,我们所做的只不过是定义了一个函数,这里就叫做|>吧,这个函数所做的唯一的事情就是将它的第一个参数应用到第二个参数上。

1
2
(|>) :: a -> (a -> r) -> r
x |> f = f x

我们再来观察一下>>=的类型:(>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b,展开类型之后即(>>=) :: (a -> r) -> r -> (a -> (b -> r) -> r) -> (b -> r) -> r。注意到返回类型应该是(b -> r) -> r,我们应该能够很自然的写出

1
(x |>) >>= (|>) = \f -> x |> (\b -> b |> f)

现在一切都很显然了,我们所做的不过是一连串的函数应用而已。把|>翻译为runCont c f,我们就得到了前面看到的m >>= k = \f -> runCont m (\b -> runCont (k b) f)。不怎么好理解是不是?人肉展开一下可以知道,我们实际上就是构造了这样一大串无用的表达式\f -> x |> (\a -> a |> (\b -> b |> ........ (\z -> z |> f))))。对,没错,你已经得到了Continuation Monad。是不是有一种上当的感觉?绕了这么大一个圈子最后只是把一个好好的f x变成了一大串无用的lambda表达式?别着急,就连最“无用”的id都能起到很大的作用,在下一篇文章里我们就介绍Continuation Monad的应用:Coroutine

Type family快速教程

最近没有什么填的上的坑啊。于是为了Github连击不断,只好在这水一水理论了。

PS. 发现Codewars这个站很有意思,有兴趣的可以来互fo:http://www.codewars.com/users/kokonotsu

好的言归正传,今天来说说type family。

是什么

type family是GHC用来支持ad-hoc数据类型重载的扩展,相当于data type的type class。两种风味data familytype family,两种定义形式stand alone的和class associated的。写出来是这个样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
{-# LANGUAGE TypeFamilies #-}

-- Standalone data family
data family XList a
data instance XList Char = XNil | XCons Char (XList a)
data instance XList () = XList Int

-- Standalone type family
type family GMap k v
type instance GMap Int Int = Map Int Int
type instance GMap () a = a

-- Associated form
class FamilyClass m where
data Foo m :: * -> *
type Bar
foobar :: Foo -> Bar

instance FamilyClass Int where

data Foo Int v = Foo (Map Int v)
type Bar = [Int]
foobar = ...

大概就是这样,即构造一个抽象类型,依照不同的类型有不同的实现,但依然有一个统一的接口。按照维基的说法,可以把type family理解成一个类型层面的函数部分应用,即高阶kind。

为什么

这玩意有什么用?某种意义上来说,它可以取代Functional Dependencies。

1
2
3
4
5
6
7
8
{-# LANGUAGE FunctionalDependencies, TypeFamilies #-}

class FuncClass a b | b -> a where

foo :: a -> b -> a

class FamClass a where

data Elem a :: * -> * -> *
bar :: a -> Elem a -> a

这样。可以避免Multi Parameter Class的出现。同时可以根据具体类型实现不同的优化,颇有一番Dependent Type的味道。

还有什么?

基本用法就是这样了。需要注意的是type family的类型变量是限定在class范围内的。就上面的例子而言,data Elem a中的a必须要与class FamClass a中的a一致。此外还有GHC类型推导的一些坑,可以参照Haskell Wiki

以上。是不是速度太快了啊(逃

请问您今天要来点Monad Transformer吗?

最近在思考关于Hakell的学习曲线的问题。Haskell的入门难已经广为人知了吧… 虽然我从一窍不通到现在缺失经历了很长一段时间的挣扎,不过我还是很好奇这个难度的实体究竟是什么。如果说Monad对新手来说是第一道难以逾越的门槛的话,那么搞清楚后面几道难关是什么队学习总是会有些帮助。粗略地看起来,Haskell中的难度大概有这么几个方面:

  • 副作用: Monad -> Monad Transformer -> Comonad -> Continuation Monad -> Free Monad -> ….
  • 并发模型: MVar -> STM -> …
  • 并行模型: Eval Monad -> Par Monad -> …
  • 运行时特性: Template Haskell -> Quasi Qoutation -> …
  • 类型系统: Type Family -> …

然而就算搞懂了以上这些非常抽象的概念之后,Haskell也才刚刚只是算入门而已(更不要再算上GHC那些进化的比我学习都快的特性了)。嘛,一门能搞一辈子的语言,不也是挺好的嘛。

好了那么言归正传,今天就来谈一谈Monad Transformer这个东西。

为什么需要Monad Transformer?

我们知道Monad是隐式保存了额外状态信息的计算过程,那么既然有了Monad,为什么还需要Monad Transformer呢?

解释起来很简单。每一种Monad都有其独特的功能,比如Reader Monad提供了类似全局(不)变量的功能,Writer Monad提供了计算同时记录信息的功能,State Monad提供了可变状态,IO Monad提供了副作用。这些Monad各有各的功能,但是,我要是想并发地执行多个线程,它们共享一个配置文件,其中每条线程读取硬盘上的一些文件,并能在读取失败的时候保存日志,要怎么办?这些Monad各司其职这很好,但我们需要一种手段把它们组合起来,于是这里就用到了Monad Transformer

好吧… 但Monad Transformer究竟是什么?

本质上说,Monad Transformer就是一个个Monad堆起来的栈。可以想象一个洋葱,最里面的一层是原始的Monad,每在外面增加一层就会增加一层Monad的功能。比较有意思的一点是,Monad Transformer依然可以被当作Monad Transformer的参数,也就是说可以组合出任意复杂的Monad Transformer来(类比把Monad堆得任意高)。

Shut up and show me the code!

考虑上面说的那个例子。首先我们需要一些IO操作,所以在最底层我们放置IO Monad

1
2
foo :: IO String
foo = readFile "foo.txt"

硬编码总不是一件好事,对吧?我们来把要读取得文件名写成配置文件:

1
2
3
4
newtype Config = Config { fileName :: String } deriving Show

defaultConfig :: Reader Config Config
defaultConfig = return $ Config { fileName = "foo.txt" }

现在为了在IO Monad中使用这个配置文件,我们就要用到ReaderT了:

1
2
3
4
5
-- newtype ReaderT r m a
foo :: ReaderT Config IO String
foo = do
name <- ask
liftIO $ readFile name

关于liftIO的事情之后再讨论,现在可以这样使用它:

1
2
3
-- runReaderT :: ReaderT r m a -> r -> m a
getFoo :: IO String
getFoo = runReaderT foo defaultConfig

再多一点Monad Transformer!

好吧。现在我们希望foo在做IO操作的时候需要打印日志。这么做似乎没有什么特别的理由,但是现实世界本来就不是讲道理的对吧w。这时候我们就需要用到Writer Monad,同时我们的程序会变成这样:

1
2
3
4
5
foo :: ReaderT Config (WriterT String IO) a
foo = do
name <- ask
liftIO $ readFile name
lift . tell $ "I am reading " ++ name ++ " !"

好吧,lift又是什么?读者可以先自行猜测一下,我们这里先不理会它。实际上我们发现,在使用了Monad Transformer之后,除了类型签名变得不太雅致以外,我们完全不用任何特殊的写法就可以同时获得三个Monad的功能(忽略那些lift的话… 事实上,的确可以忽略),这真是太棒了!

lift!lift!lift!

前面出现了许多奇奇怪怪的lift操作,什么是lift?我们来看一下它的签名:

1
2
3
class MonadTrans (t :: (* -> *) -> * -> *) where
lift :: Monad m => m a -> t m a
-- Defined in ‘Control.Monad.Trans.Class’

这里需要说明的是,如果不加任何提示,默认是会留在最外层的Monad的。比如两个State Monad叠在一起:

1
2
3
4
5
6
7
bar :: StateT Int (State String) (String,Int)
bar = do
modify (+1) -- outer monad
lift $ modify (++ "1") -- inner monad
a <- get
b <- lift get
return (b,a)

这就属于需要显示说明的情况。而不同的Monad叠在一起时,只要内层的Monad实现了外层的接口,就可以不用显示的lift操作。

1
2
3
4
5
ask :: MonadReader r m => m r
-- 注意到类型为m,只需实现MonadReader接口

instance MonadReader r m => MonadReader r (StateT s m)
-- 可以在StateT中直接使用ask

那么IO操作要怎么办?难道我们要一点点lift . lift . lift ...过去吗?由于IO类型没有Transformer,所以Haskell提供了MonadIO类型类,可以直接使用liftIO来提升IO操作。

自定义的Monad Transformer?

这个完全可以再单开一篇文章来讲了… 可以参考Real World Haskell第十八章实现的MaybeT

Monad Transformer的顺序?

在有的情况下,Monad Transformer的顺序是无关紧要的,比如上例的两个State Monad。但在有的情况下,交换顺序可能得到完全错误的结果,这要依使用场景而定。例如如果要交换fooReaderTWriterT的顺序的话,使用execWriterT就会抛弃内层的ReaderT Config IO String结果,只留下String类型的日志。

以上。