虽说早就听闻C++的模版是图灵完全的,不过当看到这样的用法的时候,还是不禁感叹这实在是太酷了!写Haskell风格的C++指日可待!
1 | template <template <typename> class m> |
相关链接:
虽说早就听闻C++的模版是图灵完全的,不过当看到这样的用法的时候,还是不禁感叹这实在是太酷了!写Haskell风格的C++指日可待!
1 | template <template <typename> class m> |
相关链接:
说起来啊一年又悄无声息的过去了呢。想想神社已经荒废了这么久没有更新,于是也来跟风写个总结什么的来凑凑数吧。
回想一下2015的前两个月我大概是在准备GSOC(Google Summer Of Code)的事情,一直忙于(试图)读懂IHaskell的源码。当然那个时候甚至连Monad是什么都没怎么搞明白,所以当然也是没有什么结果的。一月忙忙期末考试,二月过春节外加去了趟日本(名古屋->札幌->大阪)也就这么晃过去了。
然后就是喜(sang)闻(xin)乐(bing)见(kuang)的开学了。硬要说发生了什么事件的话,大概就是我选了一位非常不靠谱的导师。虽然之前就已经对这个学校的科研蛮失望的,没想到还真的能遇上更差劲的嗯…。至于说怎么个差劲法,大概就是那种成天一副我要培养你的样子,却做着自己都不知道在干什么的事情骗经费。啊那个,不好意思,经费使用情况我实在是百度不出来呢(笑)。
所以说这个学期我到底都干什么去了!(摔)
那么,暑假。算上之前在学校无所事事的事件看完了《禅与摩托车维修的艺术》和《Structure and Interpretation of Computer Program》,也就是SICP。其实与其说看完…,最近打算重新在好好翻阅一遍呢。
啊啊对对,暑假玩的最开心的事情其实是参加的那个电子竞赛呢。之前一直没有逼着自己coding,在这一个月里倒是写的很爽。虽然现在在看自己那坨要架构没架构,又乱用特性一堆Bug的C++感觉非常羞耻…,新年里好好的重构一下好了w。
之后在八月初去了武汉一趟,热到什么程度呢?等着打车的时候有个人兜里的打火机炸了哈哈哈哈哈哈哈。实际上玩的也非常不愉快,大部分时间都花在租车和开车上了,在神农架上强行翻越塌方的省道什么的,够了啦ww。
要说起来果然还是在这个学期觉醒了呢,果然还是因为那个家伙走掉了所以能够稍微静下心来吗。一学期下来大概啃了7、8篇FP的论文,感觉功力大增。所以说果然,遇到不懂的概念就去找原始论文,比那些稀奇古怪的tutorial不知道高到哪里去了!话说之后好像一直就跑偏了的样子,一直泡在Stephen Diehl的博客来着,虽然确实让我开了眼界。
然后就差不多到了现在了…,前一阵子肝完了GEB这部神作,刚刚又入手了《Concrete Mathematics》这本冷笑话集(误),也是非常推荐。
那么,其实也就是这样了。也是一如既往懒洋洋的具有博丽精神的一年呢。现在想想也很是苦恼呢,自己这种没本事GPA又不高的家伙,怎么可能出的国啊(叹)。不过既然是新年,那么也就装模作样地设定一下新年的目标好了!
这些东西不知道够不够做100天的…(算上其他一年都做不完吧喂!),不够的话,四国军棋也挺好玩的不是嘛ww。大不了把那些Haskell的用C++重写,C++的用Haskell重写一遍就是了。
更新博客!
话说其实我一直都挺想更新这里的,只不过每天领悟的东西都太琐碎,不太好单开主题(正色)。那么,希望新年里最低限度要保持月更嗯。
“请问您今天要来挖点坑吗”
说起来这一年我感觉也挺对不起我的画师的,一直因为各种原因(其实就是懒)在游戏坑上没能推进多少进度。嘛这玩意也算是开发一年多的原型了呢ww 希望…当然只是希望,新年里神明保佑突然坑就填好了!(ry
唉我就不提那些SDVX手台、3D打印机什么的硬件坑了(扶额)。
乱七八糟的事情
当然,考掉托福,刷好GPA,找个靠谱一点的实习(?)这类烦人的事情也是要办的,这就是生活啊w
嘛,以上。哦哦,这一年只剩下50分钟了啊,那么祝各位受验合格、无病息灾、弹幕回避…,新年见!
这篇文章翻译自Stephen Diehl的Blog,鉴于原文的长度,这将会是个天坑。
那么,为什么要翻译这篇文章呢?主要还是由于Stephen Diehl大神的文章实在是让人大开眼界(特别是这篇,当初看过LYAH之后就该直接来刷这个的,简直跟翻开一本黑魔法书一样)。并且,这篇blog的深度正好适合“入门”之后的中级Haskeller。这个项目从头到尾自己敲一遍基本上Haskell的种种特性就熟悉了(笑)。
注:本文会夹杂大量私货,同时会补充原文中不易理解的地方,如有错误还请指正。
那么,在开始之前,先放上目录吧。
如果有时间的话大概会实现一些扩展功能,到时候再加上吧。
虽说一直很懒不过发现神社已经有一年多的时间没有打理的时候还是很吃惊。想想真是惭愧,不过没有人来参拜果然还是没有什么动力更新呢(趴)。
说起来这一年里几乎没干什么值得一提的事情。一如往常地挖了好多的坑,填上的也没有几个。最大的收获或许就是Haskell终于感觉入了一点门,虽然依然不太敢用来写程序就是了。
那么!今天的主角自然就是Haskell了,准确的说应该就是这个名声在外的Monad
(笑)。
诶等等别跑啊我还没说完呢!
在这里吾辈自然是不会说什么
Monad不过是自函子范畴上的幺半群而已,不懂的都是⑨!
之类的老梗啦ww 毕竟有关Monad的教程实在是太多了,所以这里吾辈只是简单谈谈对于Monad的理解。
Monad就是可编程的分号。
对于新手而言对这句话肯定是一头雾水吧ww 其实配合例子来看非常简单。
那么现在假设我们要做一个数字电子线路的仿真系统。让我们要求高一点,这个系统要有时延。于是我们可以用这么个类型来表达这些信息:
1 | newtype Signal a = Signal { time :: Int, value :: a } |
非常简单,对吧?这个类型实际上就可以看作附加了时间上下文(time :: Int
)的值。
有了基本的表示类型,下面我们来表示一些基本元件。假设我们的需求很简单,只需要非门就够了:
1 | notGate :: a -> Signal a |
对于任何传进来的信号,我们的非门将它附加一个非门时延,然后将输入取反。
那么现在问题来了。这个非门如何处理已经带有一个时延的信号?当然,我们在创建基本类型的时候用了Record Syntax
,所以可以构造这样一个函数,对每个Signal a
,将其中的value
送给非门,将时延相加。于是可以这样:
1 | bind :: Signal a -> (a -> Signal b) -> Signal b |
到这里,其实你已经实现了Monad的核心了。剩下的无非是实现return
。对于普通的值,我们希望它的时延为0:
1 | instance Monad Signal where |
就是这么简单。现在我们可以享受Haskell的do
语法糖了
1 | delay2 :: a -> Signal a |
你看,Monad
不过也就是这么个小儿科的东西。它只不过是一种保持你所定义的类型所附带的额外信息的结构罢了。现在再回想一下前面那句“Monad就是可编程的分号”是不是感觉明白了很多呢。
P.S. 关于为什么只实现了非门,其实是由于这种模拟方法处理时间有一点麻烦… 例如与门,就需要处理时间同步的问题。这里就不涉及了。
下面放上最初的两个习作,也正是实现了这两种Monad
吾辈才感觉差不多理解了Monad
。下一步就要去研究Monad Transformer
了,是个更大更深的坑呢。
1 | -- Monad implemented here. |
关于为什么第二个实现是倒序的… 螃蟹卡农。嗯。
今天的幻想乡也很和平呢。
原文地址:猛击这里
博主竟然还是萌妹(误。
当你看到“Y Combinator”的时候会想到什么?如果你和我们一样,你大概会想到那家位于加利福尼亚的风投公司(比较为人所知的应该是Hacker News。
嗯,这里所说的是不动点组合子。下面是它最初的形式:
λf. (λx. f (x x))(λx. f (x x))
不不,请不要逃跑!(的确很想就是了…)这是为什么Y Combinator为什么以它命名的原因… 某种意义上它确实很酷。
为了理解究竟λf. (λx. f (x x))(λx. f (x x))
是什么意思和它能够做什么,首先我们要先了解一些lambda演算的基础。
注:如果你对函数式编程感兴趣或者对它好奇,我想你一定会享受这篇文章。如果并没有完全理解,没关系,这篇文章又不会消失!
译注:为了便于理解下文的内容,需要说明一下lambda演算中的符号表示,即:
Lambda演算(或λ-演算)是在1930年被Alonzo Church作为一种表达计算的形式系统(formal system for expressing computation)发明的。尽管其中有“微积分”一词(calculus),它却与牛顿和莱布尼兹发明的微积分相差很远。事实上,它在计算机领域的应用要比数学上要多,就我们大多数人所知。
用例子来说明可能会更加形象。让我们从草稿开始构建一些Lambda表达式。之后我们会探讨它们的含义…
基于规则1,我们可以构造这样的Lambda表达式:
x
y
很好,这些看起来还不错。下面让我们看看用规则2能做什么。
既然我们已经有了合法的表达式 x 和 y 我们可以创造:
λx. x
λy. y
λx. y
λy. x
然后是规则3:
x x
x y
(λx. x) y
(λy. y) x
(λx. x) (λx. x)
(λy. y) (λx. x)
…
小练习:试着写一些你自己的Lambda表达式。
现在让我们来看看刚刚写下的Lambda表达式。
λx. x也被称作恒等函数(identify function)。λx. x <-这里加粗的x可以被解释为输入,λx. x <-这里加粗的x可以被解释为输出。也就是说,这个函数取一个输入x,然后输出相同的x。
如果你用一些支持Lambda的语言,比如Ruby,你可能已经见过这样的写法:1
i = ->(x) { x }
如果你斜过来看一会,你可能会发现->符号有些像λ。
那么什么是λx. y?这是所谓的常函数。它忽略输入x然后返回y。1
c = ->(x){ y }
你可能会问,“λy. y是不是恒等函数?“ 的确。λx. x和λy. y是 α-恒等(α-equivalent)的。事实上,以下这些都是α-恒等的:
λx. x
λy. y
λz. z
λ☃. ☃
这将带领我们来到对 约束变量 和 自由变量 的讨论。
一个约束变量是在λ 的表达式中出现的变量并与参数具有相同的名字。一个自由变量是一个不是约束变量的变量。
举个例子,x 在 λx. x 中是一个约束变量,在 (λy.y)x 中是自由变量(传入参数)。
关于约束变量比较特殊的一点是你可以任意的重命名他们,只要对所有的变量应用就没问题。如果两个λ表达式在经过重命名后是一样的,那么就称他们是 α相等(α-equivalent)。
来看一个实际的例子:1
m = ->(horrible_variable_name) { horrible_variable_name * y }
在这个例子中,把horrible_variable_name
(约束变量)重命名是很安全的(例如x):1
m = ->(x) { x * y }
注意,你不能去重命名y,因为它是在区域外被定义的。或许y被定义为数字2
,并且m
是一个函数将自己的输入乘以2
。如果我们直接讲y重命名为z(让我们假设它被定义为0
),m将会变成一个永远返回0
的函数呢。
太酷了,我们有了函数!但是它的参数是什么呢?这时野生的规则3就跳出来了!
如果 t 和 s 都是有效的Lambda表达式,那么 t s 是一个有效的Lambda表达式
(λx.x)y 就是一个函数应用的例子。更具体的说,它表示了以y作为传入参数时对函数λx.x的调用。
我们可以使用 β-规约(β-reduction)来化简(reduce)一个函数应用。
β-规约告诉我们表达式 (λx. t) s 可以被化简为 t [x := s] 读作“表达式t中所有的x都被替换为s“(t where all bound occurrences of x in t are substituted for s)
举个例子,将在x中所有的约束出现(在这个例子中恰好也是x)替换为x我们可以将 (λx. x) s 化简为 s。
(λx. x) s
x [x := s]
s
这样,我们看到 λx. x 做了和我们期待中的恒等函数一模一样的事情。
另一件值得一提的事情是我们可以定义一个获取多于一个参数的函数,基于λ表达式的递归定义。
译注:这里想要说明的应该是函数的柯里化(Currying)。关于柯里化,可以参见维基百科
举个例子,看一下这个表达式:
λy.(λx. x) y
然后喂给它两个参数,a 和 b:
(λy.(λx. x) y) a b
((λx. x) y) [y := a]) b
(λx. x) a b
(x [x := a]) b
a b
注意这里的函数应用是左结合的,即:
(λy.(λx. x) y) a b = (((λy.(λx. x) y) a) b)
现在来看一下这个表达式:
(λx. x x)(λx. x x)
试着对它用一下β-规约?
(λx. x x)(λx. x x)
(x x) [x := (λx. x x)]
(λx. x x)(λx. x x)
等等。我们是不是又回到了开始?我们刚刚发现了 Ω (omega) ,一个分歧组合子(divergent combinator)。当一个表达式不具备 β-范式(β-normal form) 的时候,就称它是分歧的。当一个lambda表达式不能被β-规约的时候,就称它表现出β-范式。一个组合子就是一个没有自由变量的lambda表达式。
你们不对无限递归感到好奇吗?(笑
谈到递归,我们怎么在lambda演算中定义类似于递归函数呢?用Ruby写起来可能像这样:1
2
3
4
5
6
7def fact(n)
if n == 0
1
else
n * fact(n-1)
end
end
这个函数有什么特殊之处呢?它引用了自身。你可能会说类似”噢,这不过是递归而已“这样的话,不过你很可能会对lambda演算中不允许这种类型的自我引用感到吃惊,至少不是直接引用。
自我引用是一种如此简单却强大的概念,允许了像下面这句话一样对存在性的好奇。
This statement is false. (这个命题是错误的。)
那么,这个命题为真吗?如果它为真,那么它是假的;如果它为假,那么它是真的。
再来一些命题如何?
The statement below is true.(下面这个命题是真的)
The statement above is false.(上面这个命题是假的)
如果这引起了你的好奇心,那么我推荐你读一下Douglas Hofstadter的 Gödel, Escher, Bach(译注:中文名似乎叫 GEB:集异璧之大成 传说中原作者参与翻译的中译本,不可多得的奇书)。到目前为止我只读了一半,感觉就像在埃舍尔的迷宫中漫游一样。相信我,迷失在其中是值得的,但是我好像跑题了(笑。
那么,我们是如何在不采用自我引用的情况下达到自我引用呢?我想是时候回顾一下我们的神秘朋友,Y不动点组合子了。
来回顾一下我们的老朋友:
λf. (λx. f (x x))(λx. f (x x))
希望现在你对它感到更加熟悉了(笑。
现在回到阶乘函数。如果函数允许自我引用,我们就能写出如下定义:
f := λx.(if x == 0 then 1 else x * f (x–1))
但是很显然,我们已经知道这么做是不被允许的。那么,让我们回溯几步然后试一些完全不同的东西。让我们定义一个完全的lambda表达式F 以f作为参数:
F := λf. λx.(if x == 0 then 1 else x * f (x–1))
但是若想做到这一点,我们需要一些东西来使F启动,即提供给参数f一个初始值。此外,我们需要一个p使得Fp等于p。
这不仅仅是因为p是我们将要传入f(伪递归函数)这个λ表达式体中的值,同时也因为我们想要Fp能够完成和p自己能够完成的相同的事情,即允许指代它自己,而不是被当作参数传入。
以上这一段落对我来说是最棘手的一部分,它悄悄地介绍了没有直接自我引用的自我引用。所以在我们继续前进之前确保你已经理解了为什么我们要让Fp和p相等。请再读一遍吧(笑。
那么,换句话说,我们想要找到F的一个不动点。在数学的定义上,一个函数的不动点就是使得f(x) 等于 x的x取值。举个例子,对于函数f(x) = x * x,0和1就是它的不动点。
顺着这个想法,如果我们找到一个F的不动点p使得Fp等于p,我们就可以用Fp或者p(它们是同一种东西)作为那个没有直接自我引用的“递归函数”。
显然对于任意的λ表达式f,(λx. f (x x))(λx. f (x x))是它的一个不动点。
让我们看看这是怎么一回事。
1 | X = (λx. f (x x))(λx. f (x x)) |
你可以看到,对于任意的函数f,输入X保持不变。
得知了这一点,我们就可以构造一个函数,其参数为一个函数f并返回它的不动点:
λf. (λx. f (x x))(λx. f (x x))
没错,这就是我们的Y-combinator,Y不动点组合子。它返回任意函数f的不动点。让我们称呼它为Y。对于任意函数f,Yf是f的一个不动点,换句话说,f(Yf)和Yf是相等的。事实上,出于这个原因,Y-不动点组合子也被称为不动点组合子。
那么现在,我们可以令p = Yf来满足Fp等于p的要求。为了驱动这个函数,我们可以令p作为F的参数来得到F(YF),它恰好等于YF。现在我们已经准备好了。
现在让我们看看用它来实现阶乘会发生什么。试着喂给它一个3。
YF 3
F(YF) 3
λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 3
λx.(if x == 0 then 1 else x (YF)(x–1)) 3
if 3 == 0 then 1 else 3 (YF)(3–1)
3 (YF) 2
3 F(YF) 2
3 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 2)
3 (λx.(if x == 0 then 1 else x (YF)(x–1)) 2)
3 (if 2 == 0 then 1 else 2 (YF)(2–1))
3 (2 (YF) 1)
6 (YF) 1
6 F(YF) 1
6 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 1)
6 (λx.(if x == 0 then 1 else x (YF)(x–1)) 1)
6 (if 1 == 0 then 1 else 1 (YF)(1–1))
6 (YF) 0
6 F(YF) 0
6 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 0)
6 (if 0 == 0 then 1 else 0 (YF)(0–1))
6 1
6
…现在你得到它了。
3! = 6
以上。
长期不定时更新。
问题表现: 编译失败,提示函数多重定义却又不给出首次定义地点。
错误提示:1
2
3Error Compiling
Control.cpp:53: multiple definition of `TrueControl(double, double, double)'
Control.cpp.o:Control.cpp:53: first defined here
错误原因: 猜测编译器会忽略后缀为.cpp
文件中的#ifndef
?总之还是老老实实写一个.h
和一个.cpp
准没错。
解决办法:
.h
即可。(<-不规范).h
文件中并使用#ifndef ... #define... #endif
(<-规范,未测试)问题表现: 成功编译,但上传失败。
错误提示:1
2
3
4
5
6Problem Uploading to board
avrdude: stk500_recv(): programmer is not responding
-- or
Clock not synchronize
错误原因: 常见于Arduino mini等没有直接USB接口的设备。原因为设备没有引出时钟线导致时钟不同步。
解决办法: 上传的一瞬间按下Reset
按键即可,也可以按住在上传的一瞬间松开。
问题表现: 不定。
常见错误提示:1
2
3
4
5'XXX' was not declared in this scope
-- or
'XXX' does not name a type
错误原因: 你以为Include了,实际上并没有。
解决办法: 将所有需要的头文件在.ino
文件头再次#include
一次。当然不要忘记在头文件里加入#ifndef
。
解释&吐槽: 这个问题简直坑死爹了好吗!翻了好久才在Arduino论坛上找到。老外的解释是:
Arduino的编译器会将当前文件夹下用得到的文件拷贝到一个临时目录中进行编译(这也是为什么Arduino会要求将文件移到文件夹中),而编译器只会将.ino文件中包含的文件视作需要编译的文件(绕口令)。所以会无视包含中的包含。
也就是说,如果你有一个这样的包含关系:1
2
3
4
5| Arduino.ino
| library.h
| sublibrary.h
| math.h
|lib.h
而只在Arduino.h
中包含了library.h
,lib.h
那么在编译的时候编译器将不会拷贝sublibrary.h
和math.h
从而导致编译失败。
待续。
说来这个“好想做个四轴飞行器玩啊”的想法不知不觉就已经一个年头了呢,谁能想到当年这么随便的一个脑洞如今变成了学校的科研项目OTZ 既然拿了人家的经费,也就没有不把它做出来的道理,于是就这样愉快地把过程记录下来吧!
#目录
那么,开始制作吧!