• 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 } { interpreter } { lambda calculus }

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

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

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

    0. Parser

    虽然 Lisp 的语法接近没有,但是还是总还是需要一个 Parser。Haskell 写Parser 的利器便是 parsec 。其实一开始有点想自己实现一个简单的 parser combiner ,但是最后还是懒(

    Lisp 语法——所谓 S-expressions ,其实就是嵌套的列表,语法定义非常的简单

    List → Expr (spaces) List | Expr
    Expr → '(' List ')' | Atom
    

    当然其实还有 quote 、dotted 之类的语法糖,也就是多加几个分支而已。

    接下来便开始愉快的写代码了。写 Haskell 第一步当然是考虑类型。Scheme 语言内的数据类型这个解释器暂且实现四种:Number 整型、Float 浮点、String 字符串以及 Bool 。再加上语法中的 ListDottedList 以及通用的标识符 Atom ,便可以定义一个有 7 个值( constructor )的类型 LispVal

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

    当然,顺便让他们能够被 show 一下

    instance Show LispVal where
        show (Atom name) = name
        show (List contents) = "(" ++ unwordsList contents ++ ")"
        show (DottedList h t) = "(" ++ unwordsList h ++ " . " ++ show t ++ ")"
        show (String ctns) = "\"" ++ ctns ++ "\""
        show (Number num) = show num
        show (Float num) = show num
        show (Bool True) = "#t"
        show (Bool False) = "#f"
    
    unwordsList :: [LispVal] -> String
    unwordsList = unwords . map show
    

    然后便是拼 parsec 的组合子,将语法对应解析到七个 constructor 上

    type LispParser = Parser LispVal
    
    parseExpr :: LispParser
    parseExpr = parseString <|> parseNumber <|> parseListSugar <|> parseAtom <|> do
        _ <- char '('
        x <- try parseList <|> parseDottedList
        _ <- char ')'
        return x
    

    分别按照对应的语法规则实现 parseString parseNumber parseAtom parseList parseDottedList 即可(参考),其中 parseListSugar 用于解析 quote 之类的语法糖。

    1. 执行、规约

    如何将一个 S 表达式变成一个值?

    最普通的情况,考虑一个 S 表达式表达函数调用。我们都知道 lambda calculus 的三条规则:

    α-conversion: changing bound variables (alpha);

    β-reduction: applying functions to their arguments (beta);

    η-conversion: which captures a notion of extensionality (eta).

    实现执行 Lisp 语句,实际上就是实现 β 规约——代换求值的过程。将一个 List 看作为 ((λV1.λV2.λV3.(...).E) ...) E3') E2') E1') ,作代换 E [V:=E'] 直到得到一个不能再规约的 β 范式。

    得到了 β 范式之后呢?在实际的编程中表达式总会有一个值。经过上述过程之后得到的 β 范式,在实际中可能有两种形式:只包含一个自由变量的表达式 M,或者一个 lambda 表达式 λV.E 。

    显然,如果最后的结果是只包含一个自由变量的表达式,我们的程序运行结果就是这个自由变量所对应的值。那么这个值到底是多少呢?这就涉及到一个很常见的 闭包 概念。如果规约结果是个函数,类似的,程序的运行结果可能是一个函数,而在这里还有另外一种可能—— Lisp 是一种不支持默认的函数部分应用的语言,如果规约出的 β 范式结果是一个函数,也有可能是程序出错——参数数目不一致。

    这里暂且不讨论如何得到最后的结果,先实现对一个 Lisp 表达式进行 β 规约的 eval 函数。

    由于存在抛错(参数数目不匹配)的情况,首先需要定义一个异常类型(利用 Control.Monad.Error 包),并实现从 Either 类型中获取值

    -- import
    import Control.Monad.Error
    
    -- type
    data LispError = NumArgs Integer [LispVal]
    
    extractValue :: ThrowsError a -> a
    extractValue (Right val) = val
    extractValue _           = undefined
    
    instance Show LispError where
        show (NumArgs expr found) = "Expected " ++ show expr ++ " args; found values " ++ unwordsList found
    
    instance Error LispError where
        noMsg = Default "An error has occurred"
        strMsg = Default
    
    type ThrowsError = Either LispError
    

    目前为止,我们的 eval 过程只是对表达式进行规约,接受的参数类型为 LispVal ,返回值也是一个 LispVal ,当然也可能抛异常。

    eval :: LispVal -> ThrowsError LispVal
    

    接着我们考虑如何表达一个函数。

    从 λ 表达式和 Lisp 函数的形式来看,有两个要素——形参和函数体。我们可以用一个包含两个字段的 record 来表示。

    data LispFunc = LispFunc {
        paramsList :: [String],
        body :: [LispVal]
    }
    

    并且函数应该作为语言中的一个类型

    data LispVal = Atom String
                 | List [LispVal]
                 | DottedList [LispVal] LispVal
                 | Number Integer
                 | Float Double
                 | String String
                 | Bool Bool
                 | Lambda LispFunc
    

    然后 show 一下

        show (Lambda LispFunc { paramsList = params }) =
          "(lambda (" ++ unwords (map show params) ++ ") ...)"
    

    在 Scheme 中,表示一个函数的语法为 (lambda (params) (body)) 。如果在执行过程中碰到这种形式的表达式,我们会把它规约为一个函数。用模式匹配很容易做到。

    eval (List (Atom "lambda" : List params : funcBody)) =
         makeFunction params funcBody
    
    -- makeFunction
    makeFunction :: [LispVal] -> [LispVal] -> LispVal
    makeFunction args funcBody = Lambda $ LispFunc (map show args) funcBody
    

    然后考虑通用的函数调用语句 (function params...)

    {- 妈呀写的好累 -}

    {- TODO -}

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

    | { functional programming }

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

    作者: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 admin@hcyue.me -d hcyue.me
    

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

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

  • Haskeller 的 PureScript 试水

    | { haskell } { purescript } { functional programming }

    -- 讲道理虽然自称 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演算介绍:过程与数据结构(一)

    | { lambda calculus } { computer science }

    λ-calculus

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

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

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

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

    数据

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

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

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

  • The Mind Language

    | { computer science }

    最近开的一个坑,预想中是一门 Lisp 方言。

    另外,手撸状态机真是天坑,一辈子没写过这么多 switch

    Example Code

    # Definition of cons, car, cdr
    
    def cons fst, snd =
        sel -> sel fst, snd
    
    def car pair =
        pair (fst, snd) -> fst
    
    def cdr pair =
        pair (fst, snd) -> snd
    
    # Definition of boolean
    
    def true x, y =
        x
    def false x, y =
        y
    
    def fakeIf condi, fst, snd =
        condi fst, snd
    
    
    # Codes above are not the real definitions
    # In fact they are implemented in interpreter
    
    def fib n =
        if n == 0 || n == 1,
            n,
            fib (n - 1) + fib (n - 2)
    
    def fizzBuss =
        def buildList start, end =
            if start == end then end
            else cons start, (buildList (start + 1), end)
        def helper n =
            if n % 3 == 0 && n % 5 == 0 then "Fizz Buzz"
            else if n % 3 == 0 then "Fizz"
            else if n % 5 == 0 then "Buzz"
            else n
        print map (buildList 1, 100), helper
    

    Grammar

    <MindProgram> := <Declarations>
    
    <Declarations> := <Definition> [ "\n+" <Declarations> ]
    
    <Definition> := "def" "(" <ValueDefinition> | <FunctionDefinition> )
    
    <ValueDefinition> := <DefinitionHead> <DefinitionTail>
    
    <FunctionDefinition> := <DefinitionHead> <ParamList> <DefinitionTail>
    
    <DefinitionHead> := <Identifier>
    
    <DefinitionTail> := <DeclarOperator> [ <Declarations> "\n"]  [ <LetBlock> ] <Expression>
    
    <ParamList> := <ParamDeclaration> ["," <ParamList> ]
    
    <ParamDeclaration> := <Identifier> 
    
    <LetBlock> := "let" <Declarations> "in"
    
    <LetDeclarations> := <Assignment> ["\n" <LetDeclarations>]
    
    <Assignment> := <ValueDefinition> | <FunctionDefinition>
    
    <Expression> := <Value> | <Literal> | <FunctionCall> | <Expression> <Operator> <Expression> 
    
    <Value> := <Identifier>
    
    <Literal> := <StringLiteral> | <CharLiteral> | <NumberLiteral> | <LambdaFunction> | <ListLiteral>
    
    <StringLiteral> := ""* [^"]* ""
    
    <CharLiteral> := "' [^'] '"
    
    <NumberLiteral> := "[0-9]+("."[0-9]+)?"
    
    <LambdaFunction> := <Identifier> "->" <Expression>
    
    <ListLiteral> := "[" <ListElements> "]"
    
    <ListElements> := <ListElement> ["," <ListElement>]
    
    <ListElement> := <Identifier> | <Literal>
    
    <Identifier> := "[_a-zA-Z][_0-9a-zA-z]"*
    
  • 重构半衰期

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

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

    *大综合楼,一跃解千愁

    Haskell 练习

    记一次离散作业

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

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

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

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

  • OOM Killer 大爆炸

    | { linux }

    讲道理把 OOM killer 设成 2 居然会把整个系统搞挂……

    enter image description here

    于是整个 OS 的内存管理全部挂掉,能用的命令只有 echo

    还好是可以以文件的形式强行修改服务进程的。

    echo 0 > /proc/sys/vm/overcommit_memory
    

    然后试了试 ls ,终于能够运行。

    一激动之下多按了几个↑,然后……

    enter image description here

    ……………………………………