• 〔吐槽向〕Windows 输入法的 metro 应用兼容性改造

    |

    TL;DR

    微软真是坑爹不允许在 UWP 里用共享内存结果小狼毫就挂了,改成用 Windows 的 named pipe 来做跨进程交互后就可以用了。

    缘由

    重新捡起五笔后,一直苦恼没有一个合用的五笔输入法。身为半个初学者,很看中的一个功能就是五笔反查——总不能每个不会的字都专门打开一个反查工具;而 Windows 自带的五笔只有一个并不好用的五笔拼音混输功能。各种老牌的五笔输入法要么面界太丑要么久不更新,更有甚者会摆出一幅流氓作派。

    几年之前试水过 RIME 输入法,知道它是一个很强大的输入法,可以满足各种定制需求。但是当初的我并没有开发能力,RIME 的定制又稍显复杂,于是并没有继续下去。现在有了需求后回头看,发现 RIME 无疑是最适合现在的我的。

    但是现在要在 Windows 下使用 RIME 却有了个当初没有的新问题——兼容性。作为第一批 Windows 10 用户,无疑需要一个能够在 UWP 应用下正常使用的输入法。但是 RIME 最初的 Windows 前端「小狼毫」却对从 Windows 8 开始的 Metro 应用——包括 Windows 10 的 UWP 都不兼容。原作者也因为无暇分身而放弃了「小狼毫」的维护;其它开发者实现的其它前端又存在各种不稳定的问题——比如 RIME 吧的用户将 RIME 移植到了一个叫作 PIME 的输入法框架下,这个框架的界面实现非常的搓,除此之外它的输入服务实现也很蛋疼,经常崩溃,也没有可靠的异常处理,很多时候需要手动重启输入服务。

    开源界的一大准则就是「你行你上」和「show me the code」。当年使用小狼毫的时候没有经历过什么异常崩溃,说明它在这方面的设计是十分优秀的;现在的主要问题也就是不兼容 Metro 应用而已。既然现在自己有了开发能力,不如自已维护一下,方便自己,也方便他人。

  • Miko: Geisha 的半残编译器

    |

    人的命运就是这么不可预料,最后 Geisha 的编译器实现居然是作为学校的课程设计在考研期间抽空肝出来的。

    因为各种因素,最后交上去的结果和预想的其实差了挺远——比如没来得及实现 GC 所以闭包是残缺的;比如自定义类型根本就没有。不过总归最后做成了一个有结果的东西(虽然是半残的)。

    这篇是暑假期间作为课程报告交上去的文档。至于后续的工作,虽然现在已经考完研了但是突然又多出了一堆事情,只能看看什么时候有空能继续完善了……

    代码当然也在 GitHub 上,只不过 star 都点在了之前那个 Haskell 写的前端 demo 上,这个就无人问津 emmmm

    整体设计

    利用了 rust-peg 生成语法分析程序,以 LLVM 为代码生成后端。

  • 如何编译函数闭包

    |

    // 知乎不仅不给我开专栏还说我这篇文章zz敏感,破网站吃枣药丸

    闭包(英语:Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外。所以,有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。闭包在运行时可以有多个实例,不同的引用环境和相同的函数组合可以产生不同的实例。

    想要实现一个同时支持词法作用域与 first-class function 的编程语言,一个重要的转换就是所谓的 lambda-lifting:把嵌套函数定义(包括匿名函数)转换为独立的全局函数定义;把自由变量的引用转换为参数传递。

  • 基于 Hash 与 Winnowing 方法的文档查重

    这只是一篇实验报告

    设计思路

    基于现实计算能力考虑,许多大段文档之间的相似性比较不可能使用传统的文本 diff 算法等耗时长的方法。Hash 值可以在一定程度上反应数据的特征;但是一般的 Hash 方法强调避免碰撞,源数据的少许改变就可以引起 Hash 值的较大变化。对于查重来说,需要提取出文档的特征,这个特征在源数据相似时也应具有相似性。

    Winnowing 方法是 Saul Schleimer 等提出的提取文档特征(文档指纹)的方法。通过对文档的 K-gram 序列进行 hash ,提取出能够反应文档相似性的特征值序列,再对这个特征值序列进行比较[1],得到的相同特征值的比例即可反映出文档之间的相似性。

  • Windows LLVM 环境的二三事

    |

    讲道理,考研党被这种配环境的事情打扰了咸鱼的生活是很不开心的。

    起因是 Haskell 的 LLVM binding —— llvm-general 在 Hackage 上只支持到 3.5 版本。当然 repo 里是有后续版本的,但是作者在 issues 里说后续的版本并没有弄好。

    既然如此那就装 3.5 吧。然而下载了 LLVM 3.5.2 的源码后,Cmake 很顺利,用 VS 2017 打开也很顺利,然而编译的时候报错

    这里假装有编译 log (好吧忘记存了)

    总之就是某个类的方法后有 const 限定符,然后调用的上下文却又不是返回 const 于是不给过。

    奇怪的是报错的位置是 VS 提供的标准库文件。这就很尴尬了。我要么改 VS 的标准库要么研究一波 LLVM 源码。

    在 WSL 里试了一下,无痛编译。看来是 VS 有什么蛋疼的限制。网上稍微搜了一圈也没发现有类似情况(毕竟 3.5 的年代他们还没官方支持 VS 编译吧)。于是决定上 MinGW 来构建。

    使用 CMake 生成 MinGW 的 makefile 并没有问题,然而在 make 的时候提示命令语法错误

    命令语法不正确。
    mingw32-make.exe[2]: *** [tools\lto\CMakeFiles\LTO_exports.dir\build.make:61: tools/lto/LTO.def] Error 1
    mingw32-make.exe[2]: *** Deleting file 'tools/lto/LTO.def'
    mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:9977: tools/lto/CMakeFiles/LTO_exports.dir/all] Error 2
    mingw32-make.exe: *** [Makefile:151: all] Error 2

    找到了这个 build.make 发现这一行的命令很奇怪

    cd /d C:\Users\hcyue\code\llvm-3.5.2.build\tools\lto && "C:\Program Files\CMake\bin\cmake.exe" -E echo EXPORTS > LTO.def
    cd /d C:\Users\hcyue\code\llvm-3.5.2.build\tools\lto && type C:/Users/hcyue/code/llvm-3.5.2.src/tools/lto/lto.exports >> LTO.def

    纵横 Windows 这么多年没见过 cd 还可以带个 /d 参数的 似乎 powershell 的 cd 并不支持 /d 参数。那把它删了吧。

    之后继续报错,link 的时候找不到 symbol。发现是刚刚改的那两行生成的目标文件 LTO.def 有问题,不知道为什么没有写入成正常的文本文件,而是二进制文件(VS code 打开提示文件过大或为二进制文件)。直接 type 出来是一个奇怪的、字距拉得很开的、看起来像是文本文件的格式。很气。

    然而既然 .def 反正是文本文件,我大不了手动构建一下 def 。于是手动运行命令把 lto.exports 里的东西 type 出来

    type C:/Users/hcyue/code/llvm-3.5.2.src/tools/lto/lto.exports

    得到一大堆符号名

    lto_get_error_message
    lto_get_version
    lto_initialize_disassembler
    lto_module_create
    lto_module_create_from_fd
    lto_module_create_from_fd_at_offset
    lto_module_create_from_memory
    (……一大堆 lto 符号名)
    LLVMCreateDisasm
    LLVMCreateDisasmCPU
    LLVMDisasmDispose
    LLVMDisasmInstruction
    LLVMSetDisasmOptions

    新建个 LTO.def 把原来的覆盖掉,贴进去。

    重新运行 cmake --build . ,终于过了。

  • 使用 Parsec 处理左递归

    |

    在给之前写的 Lisp 解释器之前套上表达式语法时,遇到这样几条文法

    ExprFactor...ExprsExpr,ExprsFactorIntegerApplyIdentify...(Expr)Integer......ApplyFactor(Exprs)\begin{aligned} Expr & \rightarrow Factor ... \\\\ Exprs & \rightarrow Expr , Exprs\\\\ Factor & \rightarrow Integer|Apply|Identify|...|{(} {Expr} {)} \\\\ Integer & \rightarrow... \\\\ ...\\\\ Apply & \rightarrow Factor ( Exprs ) \end{aligned}

    显然,non-terminal ApplyApply 的派生最左端会进入 FactorFactor ,之后又会回到 ApplyApply 。教科书式的左递归。

  • Call With Current Continuation: Coroutine

    通过嵌套 call/cc 可以方便的实现协程

    (define (coroutine routine)
    (let ((current routine)
    (status 'suspended))
    (lambda args
    (cond ((null? args)
    (if (eq? status 'dead)
    (error 'dead-coroutine)
    (let ((continuation-and-value
    (call/cc (lambda (return)
    (let ((returner
    (lambda (value)
    (call/cc (lambda (next)
    (return (cons next value)))))))
    (current returner)
    (set! status 'dead))))))
    (if (pair? continuation-and-value)
    (begin (set! current (car continuation-and-value))
    (cdr continuation-and-value))
    continuation-and-value))))
    ((eq? (car args) 'status?) status)
    ((eq? (car args) 'dead?) (eq? status 'dead))
    ((eq? (car args) 'alive?) (not (eq? status 'dead)))
    ((eq? (car args) 'kill!) (set! status 'dead))
    (true nil)))))
  • Write You a Scheme

    |

    撸了个 Scheme 解释器,也算是拿 Haskell 做过东西了(虽然只是个玩具

    最大的体会就是,既熟悉了 Haskell,也巩固了 Scheme (虽然看过 SICP 但是并不是很明白它的 quosiquote 和 call/cc 之类的鬼东西

    本来是打算自己定义一门语言(像这个),但是发现挺麻烦的(大雾),而且我比较关心的也是解释执行的过程,于是还是决定把 Scheme 实现一下。大体上是跟着 Write Yourself a Scheme in 48 Hours 来的,在它的基础上增加了 Continuation 之类的玩意儿

  • 什么是函数式编程思维?

    |

    我为什么要把我的知乎回答搬到这里呢……大概是太久没发东西了来凑数吧。

    作者:nameoverflow

    链接:https://www.zhihu.com/question/28292740/answer/100284611

    来源:知乎

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    函数式编程与命令式编程最大的不同其实在于:

    函数式编程关心数据的映射,命令式编程关心解决问题的步骤

    这里的映射就是数学上“函数”的概念——一种东西和另一种东西之间的对应关系。

    这也是为什么“函数式编程”叫做“函数式编程”。

    这是什么意思呢?

    假如,现在你来到 google 面试,面试官让你把二叉树镜像反转一下(大雾

    几乎不假思索的,就可以写出这样的 Python 代码:

    def invertTree(root):
    if root is None:
    return None
    if root.left:
    invertTree(root.left)
    if root.right:
    invertTree(root.right)
    root.left, root.right = root.right, root.left
    return root

    好了,现在停下来看看这段代码究竟代表着什么——

    它的含义是:首先判断节点是否为空;然后翻转左树;然后翻转右树;最后左右互换。

    这就是命令式编程——你要做什么事情,你得把达到目的的步骤详细的描述出来,然后交给机器去运行。

    这也正是命令式编程的理论模型——图灵机的特点。一条写满数据的纸带,一条根据纸带内容运动的机器,机器每动一步都需要纸带上写着如何达到。

    那么,不用这种方式,如何翻转二叉树呢?

    函数式思维提供了另一种思维的途径——

    所谓“翻转二叉树”,可以看做是要得到一颗和原来二叉树对称的新二叉树。

    这颗新二叉树的特点是每一个节点都递归地和原树相反。

    用 haskell 代码表达出来就是:

    data Tree a = Nil | Node a (Tree a) (Tree a)
    deriving (Show, Eq)
    invert :: Tree a -> Tree a
    invert Nil = Nil
    invert (Node v l r) = Node v (invert r) (invert l)

    (防止看不懂,翻译成等价的 python )

    def invert(node):
    if node is None:
    return None
    else
    return Tree(node.value, invert(node.right), invert(node.left))

    这段代码体现的思维,就是旧树到新树的映射——对一颗二叉树而言,它的镜像树就是左右节点递归镜像的树。

    这段代码最终达到的目的同样是翻转二叉树,但是它得到结果的方式和 python 代码有着本质的差别:通过描述一个 旧树->新树 的映射,而不是描述“从旧树得到新树应该怎样做”来达到目的。

    那么这样思考有什么好处呢?

    首先,最直观的角度来说,函数式风格的代码可以写得很精简,大大减少了键盘的损耗(

    更重要的是,函数式的代码是“对映射的描述”,它不仅可以描述二叉树这样的数据结构之间的对应关系,任何能在计算机中体现的东西之间的对应关系都可以描述——比如函数和函数之间的映射(比如 functor);比如外部操作到 GUI 之间的映射(就是现在前端热炒的所谓 FRP)。它的抽象程度可以很高,这就意味着函数式的代码可以更方便的复用。

    同时,将代码写成这种样子可以方便用数学的方法进行研究(这就是为什么可以扯上“___范畴上的___”这种数学上的高深概念)

    至于什么科里化、什么数据不可变,都只是外延体现而已。

  • Let's Encrypt!

    世界因自由软件而美好。

    昨天(5月13日)发现 SSL 证书到期了。想起之前谭总说过的 Let’s Encrypt,决定体验一下。

    相比起半年前,这玩意完善了很多、傻瓜了很多。

    全程需要做的只需要 clone 一个傻瓜工具包,然后运行一行命令

    ./certbot-auto certonly --standalone --email [email protected] -d hcyue.me
    

    之后坐等几秒,SSL 验证所需要的全部证书就都被放在了 /etc/letsencrypt/live/hcyue.me/

    然后把 nginx 配置对应的项目修改为生成的 pem 即可。