之前在"Essentials of Programming Languages"中学习过CPS(Continuation Passing Style), 而笔记在blog改版后被丢弃, 故在这篇文章中重新详细的探讨下CPS以及尾递归, 就当是温故而知新. Continuation 在理解什么是"Continuation Passing Style"之前, 我们首先需要定义Continuation(惭愧的是我都不知道中文叫啥, 查了下好像是"续延"). Continuation是计算机程序控制状态的抽象表示, 换言之, 其就是一种表示程序执行中间某一计算步骤的控制上下文的数据结构, 即表示某一计算的未来. 一个形象的例子是阶乘函数: 1 2 3 4 let rec fact n = if n = 0 then 1 else n * (fact (n - 1)) 当我们计算(fact 4)时, 其执行过程为(用lisp的形式是因为更加形象): 1 2 3 4 5 6 7 8 9 10 (fact 4) => (* 4 (fact 3)) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24 这过程中, (* 4 #)就是一个continuation, 是(fact 3)的控制上下文, 等待着(fact 3)的计算结果传入我们的"#", (* 4 (* 3 #))也是一个continuation. 容易看到的是在这样一个计算过程中, continuation在不断增长, 因为调用栈在不断增长, 程序不得不保存*的左操作数, 计算右操作数. 接下来, 我们来看fact的尾递归版本, 所谓的尾递归(tail recursion)指的是递归函数的递归调用部分只有函数调用, 即: ...

近来想于函数式编程中寻找类似与双向链表的数据结构, 结果找到了Zipper. Zipper中文为拉链, 泛指一类常在函数式编程中使用的聚合数据结构, 其加强了原有的数据结构, 使得能够遍历或更新原有数据结构的任意部分. zipper的关键思想是将目前需要处理的部分和不需要处理的部分分开, 同时保存目前不需要的部分, 也可以将其形象的理解为光标. 本文首先介绍了如何在list的基础上构建zipper, 随后将其扩展到二叉树上. list的例子 定义zipper list或者说是单向链表, 是函数式编程中最负盛名的结构, 其既简单又实用. 当我们需要修改list中的一部分时, 例如将[1 2 3 4 5]中的[3 4 5]替换为[5 6], list就带来了问题. 这时候一个简单的做法是: 1 2 3 4 5 6 let rec changeTailOfList l1 idx l2 = match l1 with | [] -> l2 // 忽略了idx大于0的情况 | x::xs -> if idx = 0 then l2 else x :: (changeTailOfList xs (idx - 1) l2) changeTailOfList [1; 2; 3; 4; 5] 2 [5; 6] // [1; 2; 5; 6] 看起来好像挺不错, 而这时候如果我们想要修改刚刚添加的内容, 例如在上面的例子中, 我们把5替换为[7 8], 这时候同样可以采取和changeTailOfList一样的做法, 从头开始遍历列表, 在目标位置进行更改. 显而易见, 在需要频繁修改某一部分的场合下, list是不适用的(虽然list本身就不是为了频繁修改某一部分而设计的). 然而, 这种需求是确实存在的, 在可变的条件下, 我们很容易想到双向链表, 设定一个指针指向我们当前操作的位置便可以方便的进行前向或后向修改. 那我们要如何在不可变的条件下满足这一需求呢? zipper正是为了解决这一类问题. 首先我们来定义list上的zipper: 1 2 3 type 'a ListZipper = ListZipper of 'a list * 'a list let zipper l1 = ListZipper (l1, []) 对于list而言, 我们需要处理的部分总是位于某个子列表的头部, 而需要保存的部分则是目标位置前面的部分, 因此我们可以用俩个列表, 一个表示目前正在处理的部分, 另一个表示之前的部分. ...

Bitwise tricks 近来翻到一本"Hackers Delight"的书, 其主要介绍基于二进制运算的算法. 初读来大感震撼, 其结果之巧妙,过程之精简, 于仅仅是了解计算机数是用补码所表示, 并未深入了解过二进制运算的人而言不可谓不精美. 正如Dijkstra所言, 计算机程序是集逻辑美感与机械实现的矛盾体. 本文姑且将其中的一些皮毛摘录如下, 以便日后之使用, 目前倒是难以得到应用. 使最右位的1变成0 1 2 3 // 01011000 -> 01010000 // if no one then return 0 x & (x - 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n $的形式. 使最右位的0变成1 1 2 3 // 10100111 -> 10101111 // if no zero then return -1 x | (x + 1) 使尾部的1变成0 1 2 3 // 10100111 -> 10100000 // if no trailing 1s then identity x & (x + 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n - 1 $的形式. ...

Value Restriction是什么？ Value restriction是用于控制类型推断能否对值声明进行多态泛化的规则（MLton原文：“The value restriction is a rule that governs when type inference is allowed to polymorphically generalize a value declaration.”）。常出现在ML系的语言中，如SML，OCaml，F#中，其实value restriction产生的本质原因是为了保证类型系统在结合参数多态与命令式特性（imperative feature，如ref）时候的可靠性（soundness）。一个典型的例子就是： 1 2 3 4 5 6 // 如果没有value restriction let x = ref None // 'a option ref let y: int option ref = x // type checked let z: string option ref = x // type checked let () = y := Some 2 // type checked let v: string = !z // 破坏了类型安全 限制了什么？ 简单来讲，value restriction限制了类型泛化只能发生在表达式的右边是句法意义上的值。那么什么是句法意义上的值呢，SML的语言规范上明确给出了什么样的表达式是句法意义上的值（准确来说是non-expansive）: 常量，如13，"string" 变量，如x,y 函数，如fn x => e 除了ref以外的构造函数在值上的调用，如Foo v 类型上受约束的值，如v: t 每一个元素都是值的tuple, 如(v1, v2, v3) 每一个字段都是值的record, 如{l1 = v1, l2 = v2} 每一个元素都是值的list, 如[v1, v2, v3] 确切的来讲，只要是协变（covariant）的类型并且不和可变的特性相结合，那么它总是可以类型安全的泛化（OCaml manual原文：“As a corollary, covariant variables will never denote mutable locations and can be safely generalized.”）。即： ...

之前一直有使用Hexo来生成静态博客，如今将博客迁移到了Hugo下。两种工具总体而言各有优势，个人此次转移到hugo的主要原因大概是希望能够重拾写博客的习惯，本文主要介绍了使用Hugo的大致流程。首先给出个人博客的文件结构： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Root # blog根目录 | +-- archetypes +-- content |-- posts # 博客目录 |-- _index.md # 主页 +-- data +-- layouts +-- ox-hugo # org文件位置 |-- messy.org # category为Others的org文件 +-- public # submodule +-- resource +-- static +-- themes |-- xxx # 主题文件夹, submodule +-- .git +-- config.toml +-- .dir-locals.el # 自动将org文件转为markdown配置文件 +-- .gitmodules 其中只有 ox-hugo 为自定义文件夹, .dir-locals 为ox-hugo自动转换的配置文件，其他都是自动生成的。接下来个人就hugo生成博客关键部分展开介绍下。 ...

Monad是Haskell中讨论最多的结构, 需要更详细的探讨其相关内容, 即使它对于Haskell而言不是必须的:(. 参考: All about Monads Monad Support 除了之前介绍过的一些基本函数, Haskell本身定义了一些辅助函数配合Monad一起使用: sequence 1 2 3 4 -- 任意一个fail会导致整个fail sequence :: Monad m => [m a] -> m [a] sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x : y) sequence_和sequence类似但其不返回值, 在只关心序列的副作用时其非常有用. 1 2 sequence_ :: Monad m => [m a] -> m () sequence_ = flodr (>>) (return ()) mapM其由sequence和map定义 1 2 mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f as = sequence $ map f as mapM_, 类似的使用sequence_定义 1 2 mapM_ :: Monad m => (a -> m b) -> [a] -> m () mapM_ f as = sequence_ $ map f as =<<是>>=调换参数位置的版本 1 2 (=<<) :: Monad m => (a -> m b) -> m a -> m b f =<< x = x >>= f 上面提到的函数都是standard prelude中定义的, Haskell在Control.Monad模块中定义了更多函数. 下面是一些列表函数的Monad版本: foldM 1 2 3 foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a foldM f a [] = return a foldM f a (x:xs) = f a x >>= \y -> foldM f y xs filterM 1 2 3 4 5 filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] filterM p [] = return [] filterM p (x:xs) = do b <- p x ys <- filterM p xs return (if b then (x:ys) else ys) zipWithM和zipWithM_ ...

Semigroup 半群即一个集合以及在之上定义的一个满足结合律的二元运算, 在Haskell中定义为(部分): 1 2 3 class Semigroup where (<>) :: a -> a -> a {-# MINIMAL (<>) #-} Laws 1 2 -- associativity a <> (b <> c) = (a <> b) <> c Monoid “A monoid is a binary associative operation with an identity”, 在Haskell中定义为(部分): 1 2 3 4 5 6 class Monoid m where mempty :: m mappend :: m -> m -> m mconcat :: [m] -> m mconcat = foldr mappend mempty {-# MINIMAL mempty #-} Laws 1 2 3 4 5 6 7 8 -- left identity mappend menpty x = x -- right identity mappend x mempty = x -- associativity mappend x (mappend y z) = mappend (mappend x y) z 这和数学上带幺半群所满足的性质是一致的, 带幺半群即一个包含单位元的半群. ...

多态(polymorphic)最早从19世纪希腊语中引入, 其中poly代表很多(many), morph代表形式(form), 而-ic的后缀表示由…制成(made of). 因此, 多态意味着"made of many form", 即有许多形式构成. 因此单态(monomorphic)很容易猜到是"made of one form". 2019.03.04 -ary的后缀表示属于或关于(of or pertaining to), 在讨论数学上的元数(arity)时, -ary是公共的后缀, 诸如nullary(零元), unary(一元), binary(二元)等. 2019.03.07 我发现gnome-terminal下C-;会映射成;,导致我在terminal的emacs中使用快捷键C-x C-;注释行失败. 网上查阅后发现, 由于gnome-terminal没有C-;的转义序列(escape sequence), 而默认的将其识别为;. 2019.04.13 紧接3, 我发现在gnome-terminal下emacs无法使用C-;, 又懒的配置term. 于是就重新编译了带有GUI的emacs(./configure --with-gnutls=no --without-pop --with-x), 之后发现其默认会使用Anacnoda的lib, 一开始会报一些libxml2.so: undefined reference to `ucnv_close_58', 之后我将LD_LIBRARY_PATH设置为~/anaconda3/lib之后, 上述错误没有了, 但又报了新的错误libSM.so: undefined reference to `uuid_unparse_lower@UUID_1.0'. 解决方法是不使用Anaconda的lib, 而使用系统的lib(export不包含~/anaconda/bin的PATH, 随后重新configure和make), 具体原因未查明. 2019.04.13 i3-wm的layout-restore的问题. i3-save-tree生成的json文件无法直接使用, 需要手工修改layout文件, 首先需要包含一个顶层的container, 随后每一个swallows都需要声明class和instance, i3-save-tree会生成class和instance信息, 当然也可以通过xprop获取. 2019.05.01 硬件之上最重要的两种软件是操作系统和编译器, 操作系统提供处理用户应用和硬件的接口, 编译器负责将高级语言编写的程序翻译成低级语言(相对于硬件而言). 2019.05.20 ...