PerodicLaw的个人博客
0%

发表于 更新于 分类于

CSAPP的实验笔记（网址http://csapp.cs.cmu.edu/3e/labs.html）。真够无聊的……

Bomb Lab

先反汇编，从main开始，依次调用initialize_bomb phase_1 phase_defused...直到phase_6 phase_defused一系列函数。

phase_defused

先从这个被调用了6次的函数看起，因为我估计这个应该相对简单，算热身一下。

它会将num_input_string的值和6比较（一个位于0x603760的全局变量，应该是输入过多少次字符串了），如果不相等直接结束。

随后它调用sscanf，（这里已经优化成用寄存器传参了）r8 rcx rdx分别是三个接收的变量，传入的格式串为0x402619处的"%d %d %s"，输入串则在0x603870，不知道实际是什么。

如果成功读到3个数，会调用strings_not_equal，参数包括0x402622的"DrEvil"和一个变量（推测这个是刚刚读入的%s）。如果返回0,那么调用puts输出"Curses, you've found the secret phase!" "But finding it and solving it are quite different"；随后调用secret_phase函数。

不论是否返回0，都会输出"Congratulations! You've defused the bomb!"，随后结束。如果没有成功读到3个数那么直接结束。

从这里我们可以看出，这是第6关之后的一个隐藏关，需要某个字符串具有%d %d DrEvil的形式才会开启。我们等6关玩完了再解它。

阅读全文 »

发表于 更新于 分类于

MIT 6.830是研究生级别的数据库课程。其课程主页见http://db.lcs.mit.edu/6.830/sched.php。

我的代码见https://github.com/PeriodicLaw/simple-db-hw。

Lec2

关系数据库并非一开始就有的。在关系模式出现之前，最早的是IMS模型，即层次数据模型。数据用记录（元组）表示，记录有用于唯一标识的key，且记录类型之间用树状关系连接起来。 IMS实质上是只有父-子关系的关系模型，存在很多限制并且会造成冗余。IMS的操作语言是即时记录（record-in-time）的，直接操作数据库细节，被执行器直接执行，因而需要程序员手动优化。

CODASYL是用于改进IMS而出现的，用网状结构取代了树状结构，导致模型更加复杂了。然而它在操作语言上并无改进，仍然是即时记录的。

1970年，Codd提出了关系模型，并证明了关系演算和关系代数之间的等价性。Codd提出的操作语言与IMS和CODASYL不同，是set-at-a-time的。

在此基础上则有进一步的ER模型、范式等等。

Lab1

文档对整个数据库的设计的描述还是不太详细，很多靠自己摸索。

数据库设计

阅读全文 »

发表于 更新于 分类于

因为工作上的原因，时不时会遇到这样的情况：需要某些旧版本的库，或是文档里写的库在自己的软件仓库上找不到（说的就是你，Ubuntu）。 这个时候开一个虚拟机显然是不太方便的选择；使用docker，我们可以做到将库环境隔离开来，需要工作的时候切换到docker里即可，而不需要切换系统或是开个虚拟机。

这篇文章记录下docker的安装和配置的过程。

安装

首先安装docker并启动其服务。

1
2
3
sudo pacman -S docker
sudo systemctl start docker.service
sudo systemctl enable docker.service

然后，使用sudo usermod -aG docker $USER并重启。再输入docker info，如果能够看到一长串机器配置信息，那么说明安装完成。

配置

docker下载非常慢，所以我们需要使用阿里云镜像，见https://blog.csdn.net/wohaqiyi/article/details/89335932进行配置。

比如我们希望有一个独立的Ubuntu环境，在这个环境里安装一些软件包。我们输入docker pull ubuntu拉取镜像，默认是最新版也就是20.04。

输入docker run -it --name=work ubuntu /bin/bash，我们就创建了一个叫做work的容器，并且进入了它。Ctrl-P Ctrl-Q可以退出而不停止运行。

阅读全文 »

发表于 更新于 分类于

趁着618入了一个FPGA板子，但电子这玩意确实坑多，这篇来记录一下遇到过的坑。

串口

板子上有一个串口转USB的芯片，型号是叫CP2102。按照指导安装了驱动，结果插上USB线一直是提示“无法识别USB设备”，弄了好久也没搞定。 最后发现！居然是USB线（准确的说，应该是Type-A和mini-B的转换线）有问题……

Windows

Windows上需要给CP210x系列装个驱动，卖家提供的或者去官网下Windows10的应该都可以（我折腾太久都忘了现在装的是啥了……），插上后可以在设备管理器的“端口(COM和LPT)”里看到串口对应的COM号。 然后可以安装一个串口调试软件（比如这个专栏安利的https://zhuanlan.zhihu.com/p/109941792），从对应的COM口就可以通信了。

Linux

Linux上，CP210x从4.0开始就内置了CP210x的驱动了（不是默认开启的，通过sudo modprobe cp210x可以开启，但是不手动开启也可以）。插上USB线，通过lsusb可以看到这一项：

1
Bus 001 Device 005: ID 10c4:ea60 Silicon Labs CP210x UART Bridge

可以安装串口调试工具picocom，然后用sudo picocom -b 115200 /dev/ttyUSB0连接上串口，用Ctrl+a Ctrl+q退出。

阅读全文 »

发表于 更新于 分类于

在看了TAPL之后，就一直想写一个带类型系统的函数式语言的解释器，花了几天写了一个出来，并且使用天下第一的Rust语言然后clone满天飞了，下面来说说语言的设计和实现过程。

设计

我们的语法希望和简单类型Lambda演算一样，通过Lambda表达式来构造函数，通过函数调用来进行计算。除此之外，我们也希望加上一些拓展，包括元组、union、列表和不动点算子（这个很破坏类型系统，但还是要加一个）。为了方便，元组和union都是匿名的，不支持自定义类型。我们也希望有两个基本类型：Int，Bool。

在此基础上我们需要有一些运算符，包括算术、比较、逻辑。

元组的表达式设计为(xxx,xxx)，无元素元组为()，单元素元组则为(xxx,)。元组索引则类似Rust，使用x.0。

union因为是匿名的，所以没有啥好的设计可以参考，为了保证类型推导可以完成，我设计为(Int | Bool true)的形式，里面恰好有一项是有值的。解开union则需要用case表达式，设计的形式是case u of (Int a => ... | Bool b => ...)。

列表这里，我本来想有下标运算，但是这就和列表的构造冲突了，无法解析，之后是想着引入nil head tail三个“函数”（其实是运算符），但感觉这样太过奇怪，最后设计为给列表一个固定的模式匹配，也就是match l of ([] => ... | x::xs => ...)。

然后语句，语句有两种：let绑定（类型标注可选）、匿名表达式。

在实现简单类型系统之后，我又把它升级成了HM类型系统，支持自动类型推导。效果还是很满意的。

词法和语法分析

阅读全文 »

发表于 更新于 分类于

这篇来介绍一下程序语言的类型系统。部分内容是TAPL(Types And Programming Languages)的读书笔记,但不全是.

无类型Lambda演算

无类型Lambda演算其实只有两个内容：抽象(Abstract)和应用(Apply).抽象是引入Lambda表达式\(\lambda x.t\),应用是函数调用\(t \; t\).

对于无类型Lambda演算而言,其语义就是用替换完成函数调用,也就是\((\lambda x.t_1)t_2\)等于用\(t_2\)替换\(t_1\)中自由出现的所有\(x\).

基于这样的语法和语义,足以得到和图灵机等同的计算模型,例如Church数:

\[0=\lambda s.\lambda z. z, 1=\lambda s.\lambda z.s\;z, 2=\lambda s.\lambda z.s\;s\;z,\cdots\]

又例如Y组合子,可以用来构造递归函数:

\[Y=\lambda f.(\lambda x.f(\lambda y.x\;x\;y))\;(\lambda x.f(\lambda y.x\;x\;y))\]

因为\(Y\;f=f(Y\;f)\),所以也叫做不动点组合子.这个构造还是相当巧妙的.

简单类型Lambda演算

阅读全文 »

发表于 更新于

距离上次写博客又快一年了，感觉真是今非昔比。

我从Jekyll迁移到了Hexo，因为Jekyll在本地环境跑不起来（之前怎么跑的？当然是在本地写，然后在Github Pages上面直接看）。

使用Hexo的过程主要参考https://gist.github.com/btfak/18938572f5df000ebe06fbd1872e4e39，数学公式支持则是参考https://github.com/theme-next/hexo-theme-next/blob/master/docs/MATH.md并使用hexo-renderer-pandoc。

有一个坑就是nodejs不能太新，我换用了sudo pacman -S nodejs-lts-erbium，见https://zhuanlan.zhihu.com/p/136552969。

06-07更新：使用https://github.com/chekun/hexo-excerpt使得主页自动截断。

阅读全文 »

发表于 更新于 分类于

这是Sipser的《计算理论导引》的简要笔记. 计算理论还是比较难的......

前面文法看得相对多一点,后面就疯狂跳了.

第0章

计算理论主要包括三个部分,自动机理论,可计算性理论和复杂性理论.

字母表(alphabet)是一个非空有限集,其中的成员称为字母表的符号.字母表上的字符串(string)是字母表中元素的有限序列,元素的个数称为字符串的长度(记为\(|w|\)),长度为零的字符串称为空串(记为\(\epsilon\)). 字符串有子串,前缀,拼接的概念. 字符串的集合被称为语言(language).

第1章 正则语言

有限自动机

(确定性)有限自动机(DFA)是一个五元组\(M=(Q,\Sigma,\delta,q_0,F)\),其中\(Q\)为状态的有限集,\(\Sigma\)为字母表,\(δ:Q\times\Sigma\to Q\)为转移函数,\(q_0\in Q\)为初始状态,\(F\subseteq Q\)为接受状态集合.DFA可以用状态图表示.

设\(w=w_1w_2\cdots w_n\)是一个字符串,如果存在一系列状态\(r_0,r_1,\cdots,r_n\)使得\(r_0=q_0\),\(\delta(r_i,w_{i+1})=r_{i+1}\),\(r_n\in F\),则称\(w\)被DFA\(M\)所接受.DFA\(M\)所接受的全体字符串\(L(M)=\\{w\mid M接受w\\}\)称为\(M\)所接受的语言.特别的,被某个DFA接受的语言称为正规语言(regular language).

对语言我们可以定义正则运算:并运算\(A\cup B\),连接运算\(A\circ B\),星运算(闭包运算)\(A^*\).通过构造DFA乘积的方式我们可以证明正则语言的并还是正则语言.

阅读全文 »

发表于 更新于 分类于

这是Buraldi的《组合数学》的简要笔记. 这书废话挺多的,内容也比较像科普而不像专业数学书.

笔记里只会记录个人觉得有价值的内容,像图论的那几章就不记了(与其看这个不如看专门的图论书),有些看不进去的内容当然也不会记.

第1章

Nim游戏:有\(2\)个人和\(k\)堆金币,每一堆中有\(n_i\)个金币.两个人轮流取金币,每次只能取某一堆最上面的若干金币(不能不取),先取完的人胜出.

设\(n_i\)的二进制表示为\(n_i=a_{is}\cdots a_{i1} a_{i0}\),如果对于所有\(1\le j\le s\),\(a_{1j}+a_{2j}+\cdots+a_{kj}\)为偶数,则称此局面是平衡的,否则为不平衡的.

对于平衡的开始局面,后手必胜,因为先手不管怎么取都会把局面从平衡变为不平衡,然后后手每次将不平衡的局面变为平衡,最后一定是后手取完. 对于不平衡的开始局面,先手必胜,因为先手总可以取一些金币使得局面从不平衡变为平衡,然后重复刚才的过程.

第2章

对于有\(k\)种元素,每种元素有\(n_k\)个的多重集合,将其中\(n=n_1+\cdots+n_k\)个元素全部取出进行排列的种数为\(\frac{n!}{n_1!\cdots n_k!}\). 其组合意义是,先给多重集中的元素标号,排列数为\(n!\),再忽略同种元素的编号.

对于有\(k\)种元素,每种元素无穷多的多重集合,从中取出\(r\)个元素进行组合的种数为\({r+k-1}\choose r\). 其组合意义是,组合的个数可以转化为\(x_1+\cdots+x_k=r\)的正整数解个数,而这可以利用插隔板的思想求种数.

第5章

阅读全文 »