• 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 = Node a (Maybe (Tree a)) (Maybe (Tree a))
                deriving (Show, Eq)
    
    invert :: Maybe (Tree a) -> Maybe (Tree a)
    invert Nothing = Nothing
    invert (Just Node v l r) = Just (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 即可。

  • Haskeller 的 PureScript 试水

    |

    – 讲道理虽然自称 Haskeller ,但是其实我根本不会 Haskell(

    为什么我要尝试 PureScript ?

    因为它是 Haskell 和 JavaScript 生的娃啊。

    Facebook 的 React.js 可以说是给 JavaScript 社区带来了一次 functional programming 的热潮。然而 JavaScript 毕竟不是真正的函数式编程语言——虽然有着 closure 等特性让它可以支持这种独特的范式,但是整体而言它还是基于顺序指令和事件回调的语言。

    PureScript 是一门年轻的语言——现在在 github 上可以查到的最早提交来自于 30 Sep 2013 。它致力于创造一种“类似 haskell 的编程体验”和“生成可读的 JavaScript 代码”。于是,有了它,我们终于可以在项目前端部分中愉快的写“ monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor ”了(

  • 又是一篇lambda演算介绍:过程与数据结构(一)

    |

    λ-calculus

    自从了解了lambda演算,我就觉得,每个写代码的人都应该学学它。——沃兹·基硕德

    λ演算的详细介绍可以从 Wikipedia 找到。

    简单来说,这是一个比图灵机早提出几个月的可计算性模型,表达优美形式简洁反正比图灵机高到不知道哪里去了,但是愚蠢的人类没办法在机器上直接实现它所以只能照着图灵机来造计算机,导致图灵那家伙小人得志真正的大神却退居二线(相对图灵来说的二线)

    (为了方便表示,以下将 λV.E 记为 V -> E

    数据

    在原始的 lambda 演算中,没有直接的“数字”概念。

    lambda 演算的全部规则仅有两条(其实也可以说是三条),在这种简洁的体系中没有一个容纳原生“数字”概念的空间。

    但是神奇的是,仅仅只有两条“运算方法”,却能够构造出整个直觉上的“数字”体系。这种通过“过程”构造的“数字”,我们叫它“Church Numerals”,因为它正是由引入 lambda 演算的那位神人提出的。

  • 重构半衰期

    所谓“重构半衰期”,就是“写一段代码,在时间T之后你会觉得这一段代码写得像坨 shit ”中 T 的最小值。

    之所以突然想到这个概念,是因为我发现,现在的我看几个月之前的文章简直就是羞耻 play :

    *大综合楼,一跃解千愁

    Haskell 练习

    记一次离散作业

    第一、二篇,就算不说每次都写一遍的 replicate,那两级 where 就足够让人迷醉,更不用说当时完全不知道用 monad , 甚至 lambda

    第三篇简直令人发指,双手颤抖的想要毁尸灭迹——当然最后被理智所制止。

    根据马克思主义“自我否定,螺旋上升”的事物发展理论,这个 min(T) 可以代表你的学习进展。之所以会觉得之前的东西是 shit 正是因为现在的水平和当初已经不是同一层面。

    想通了这点,我便心安理得的继续写着 shit 一样的代码了。