AlexiaChen.github.io

AlexiaChen.github.io copied to clipboard

--- title: 程序的含义 date: 2017-10-15 10:30:46 tags: - 语义学 - 程序语言理论 --- > *武士的刀，不应以刀鞘束缚，而应该以你的灵魂来约束。这个时代已经不需要武士了，但无论时代如何变迁，人都会有不能忘却的东西。即使有一天弃剑的时代到来，这一灵魂约束的正直之剑也绝不能丢弃。* -- *志村 《银魂》* ## 前言 编程语言，以及我们用编程语言所写的程序，这些都是软件工程师工作的基础。我们用编程语言和程序阐明复杂的想法，并在彼此间交流这些想法，当然最重要的是在计算机中实现这些想法。 程序员是注重实践实际的职业，他们通过阅读文档，学习教程，研究现有的程序以及修改自己的简单程序来学习新的编程语言，而不会过多的思考那些程序有什么含义。然而，计算机编程不单是与程序相关，重要的是程序员要表达思想。程序只是思想的静态表示，是曾经存在于程序员脑海中的某个结构的快照。程序是有了含义才值得写下来的。那么是什么把代码和它的含义连接在一起的呢？怎样才能能将一个程序的含义描述得更具体一点呢？ ## “含义”的含义 在[语言学](https://en.wikipedia.org/wiki/Linguistics)中，[语义学(semantics)](https://en.wikipedia.org/wiki/Semantics)研究的是单词和它们含义之间的关系。比如，dog只是纸上一些符号的组合，或者由某人的声带引起的一系列空气震动，这与真正的狗或者通常意义上的狗的概念极为不同。语义不止关注抽象含义本身的基本性质，还关注具体的记号如何与它们抽象含义关联起来。 在计算机科学里，[形式语义学](https://en.wikipedia.org/wiki/Semantics_(computer_science))偏向的是找到**确定程序**难以捉摸的含义的方法，并利用这些方法发现或者证明编程语言中有趣的东西。从定义新的编程语言和编译优化这种具体应用，到构造程序正确性的数学证明这样更抽象的领域，林林种种。这是一般的软件工程师接触不到的概念。 为了完整的定义编程语言，第一需要语法，描述程序看起来是什么样子；第二，语义，描述程序的含义。 但是许多语言都没有官方的书面规范，而只有一个可用的解释器或编译器。比如Ruby语言，它就没有标准规范，而是靠Matz先生的Ruby解释器(MRI)来规范的，也就是靠实现规范,任何一份Ruby的文档如果与MRI实际行为不一致，那么一定是文档错了。类似的语言还说有PHP和Perl。 另一些语言，是像C++，ECMAScript，Java描述编程语言的方法就是写一份平实的官方文档（一般是英文）。这些语言的标准化通过专家组成的委员会写成，与语言的实现无关，以至于这些语言的编译器解释器实现方式多种多样。通过官方规范定义一种语言更为严谨，这样所做的设计决策更有可能是经过深思熟虑的，而不是某一个特定实现的意外结果。但是语言标准规范，为了严谨化，通常非常难懂，文档中有没有矛盾，歧义的地方很难考证，这样的一份英文文档没有形式化的方法可以验证推导。 还有一种第三种方法来定义描述编程语言，就是使用形式语义学中的数学方法准确的描述编程语言的含义。这样的做法不仅能用适合系统分析甚至自动化分析的格式写出规范，还能保证其完全没有歧义，这样就可以对规范是否一致，是否含有冲突，以及是否有疏漏进行全面检查。 ##...

AlexiaChen

--- title: 什么是类型安全? date: 2017-03-16 15:30:48 tags: - 类型系统 - 程序语言理论 --- ## 什么是类型安全？ 有时候有些人说，Java是个类型安全的语言，那么这些人到底是在说什么？所有的类型安全的语言是一样的吗？ 事实上，一个语言类型安全的定义是取决于语言类型系统的定义。简而言之，类型安全能保证程序的行为是意义明确的（well-defined）。更广泛的来说，我将要讨论的话题就是，一个语言的类型系统是推导程序正确性，安全性的一个有利工具。类型系统也是程序语言理论一个热门的研究领域。 思考下，为什么动态类型的语言，比如，Python，Javascript这些语言没有良好的代码提示工具呢？也为什么没有良好的函数定义跳转工具呢？ 其实就是由于类型系统的影响，导致没有工具能非常正确分析程序结构，导致跳转，提示不正确。简单的程序可能可以分析出来，但是一旦程序结构复杂了，就难以作出代码的正确提示。所以为了弥补Javascript的不足，才有了静态类型的[TypeScript](http://www.typescriptlang.org/)，这样静态类型的语言在语言编译的时候就可以借助编译器或者静态分析工具分析出大量隐含的错误(警告)，也更利于为其开发良好的代码提示，重构工具，也更利于大型项目的开发维护。好处是不言自明了。 ## 基本的类型安全 类型安全基本可以用一句话总结：有良好的类型系统的语言能保证自身程序不出错。 这句话其实不是我创造的，是来自于[Robin Milner](https://en.wikipedia.org/wiki/Robin_Milner)他1978年的一篇论文，论文叫[《A Theory of Type Polymorphism in Programming》](https://courses.engr.illinois.edu/cs421/sp2013/project/milner-polymorphism.pdf)。翻译过来就是，编程中的类型多态理论。 好，下面我们来逐步讲解这句话是什么意思。...

AlexiaChen

--- title: CPU缓存效果概要 date: 2018-02-8 17:16:53 tags: - 计算机体系结构 - 性能优化 --- ## 前言 大部分看过[《CSAPP》](https://book.douban.com/subject/1230413/)这本经典的人，一般都能理解CPU缓存的大概机制，并能简单通过CPU的缓存机制来优化程序性能。 我这篇文章主要也是用一些代码样例来从一些不同的角度演示缓存的工作机制和实战中的代码优化。 ## Example 1：内存访问和性能 比较以下两种不同的循环，哪种循环相对更快？(不用管是什么语言的代码) ``` java int[] arr = new int[64 * 1024 *...

AlexiaChen

--- title: 谈谈函数式编程 date: 2016-09-05 15:38:56 tags: - 函数式编程 - lambda演算 - Y组合子 --- # 什么是函数式编程 其实有关于函数式编程我有在之前的博文[《编程语言为何如此众多》](http://mathxh-love.org/blog/2016/05/19/programming-language/)提到过，有兴趣的可以去看看 :) 那么到底什么是函数式呢？听上去好厉害，好高大上的样子。 大家都知道面向对象编程提到的几个特性：封装，继承，多态，一切皆对象。那么其实函数式编程也有它固有的几个特点：不可变量，惰性求值，高阶函数，无副作用，一切皆函数。 ## 从停机问题开始 调程序的时候经常会遇到死循环的Bug，聪明的你有没有想过发明一个自动检查程序里面有没有死循环的工具呢？不管你有没有过这种想法，反正我有过，可惜答案是，没有！ 停机问题在[wiki](https://en.wikipedia.org/wiki/Halting_problem)上的描述比较学术，又是什么图灵机，又是数学中的集合。因为涉及到[计算理论](https://en.wikipedia.org/wiki/Theory_of_computation)的东西，为了防止小白看不懂，下面用一个小白话来讲， 停机问题：**给定任意一个程序及其输入，判断该程序是否能够在有限次计算以内结束。** ## 假设存在停机算法 如果存在停机算法，那么对于给定任意一个函数以及这个函数的输入,停机算法就能告诉你这个函数会不会结束。 ``` javascript...

AlexiaChen

--- title: 再次理解同步异步和阻塞非阻塞 date: 2017-07-27 09:30:35 tags: - IO - 同步异步 - 阻塞非阻塞 --- > *唉，涉及到网络IO和文件IO的时候又把这些概念混淆了。* --- ### 从编程角度阐释 异步与同步与单线程或多线程都无关，是以任务的执行顺序有关，是更加高层次的抽象概念，下面以线程举例子： 同步（一个任务的开始必须依赖另一个任务的完成） - 单线程： ``` 1 thread: / / | |...

AlexiaChen

--- title: SQLite的并发 date: 2017-02-23 17:48:40 tags: - SQLite - 数据库 --- > *以前没有好好看过SQLite，并没有对它有更深入点的了解，就当软件本地的配置文件和小规模数据统计来使用，对它的一些知识不是很清晰，今天就借助SQLite官方文档选择性的了解下，主要关注并发，多线程和多进程访问* #### 多个进程应用实例是否能同时访问单个数据库文件？ 多进程能同时打开一个数据库，多进程也能同时对一个数据库进行SELECT，但是任意一时刻，有且仅有一个进程能修改一个数据库。 SQLite使用读写锁来控制数据库的访问。但是，使用时请注意：这种锁机制可能在网络文件系统（NFS）上不能正确工作。所以，应该避免多进程访问一个在网络文件系统上的数据库文件。另外，在Windows下，这个锁机制如果在不运行Share.exe守护进程的情况下，在FAT文件系统下就无法工作，由于锁机制，数据库文件在Windows网络共享中多进程访问有严重BUG，所以不要在多台Windows机器之间共享数据库文件。 应该明白，没有一个为嵌入式设计的数据库会支持高并发的，SQLIte允许多进程同时打开，读取数据。但是多进程写数据库下，当任意一个进程想写的话，那么在进程修改数据库期间SQLite会锁住整个数据库文件。但是这样一般只会耗费几毫秒。其他进程只用简单等待锁释放就可以进行操作了。 如果有高并发的需求，一定选择C/S模型的数据库（MySQL，SQLserver，PostgreSQL）。 但是，从经验上讲，大多数应用程序不需要这么大的并发。 当SQLite试图访问一个被其他进程锁住的数据库文件，那么SQLite默认行为会返回SQLITE_BUSY。 #### SQLite是否线程安全？ 是的，如果要让SQLite支持线程安全，就使用SQLITE_THREADSAFE预编译宏来编译SQlite。当然，不用担心，Windows和Linux的二进制发布版就是这样编译的。 SQLite支持线程安全是为了用互斥量同步公共的数据结构。然而要请求和释放锁，所以SQLite性能会略有下降。如果开发者没有线程安全这样的需求，可以重新编译SQLite，关闭互斥量以得到最大性能。 实际上加锁不会太影响性能，影响性能的是锁争用，如果不是多线程，我觉得也可以单线程程序使用线程安全版本的SQLite。

AlexiaChen

--- title: 为什么使用多线程在大多数情况下是个坏注意？ date: 2018-03-20 14:00:00 tags: - 线程 --- ## 简介 什么是线程？ - 诞生并成长于操作系统这个世界中 - 在用户级别的工具中慢慢演进 - 被提议为多种多样的问题的一种解决方案 那么，上面说的如此明确了，我们是否在现实工作中成为一个彻头彻尾的“多线程程序员”呢？ 多线程带来的问题： 多线程程序很难编写 相对于多线程的一个折中方案： 采用事件驱动的思想 声明： - 对于大多数的场景，事件要比多线程更好 - 多线程一般只能用于真正确实需要用到CPU并行的场景 ##...

AlexiaChen

--- title: 从底层角度看待函数的调用 date: 2014-03-05 12:01:23 tags: - 内存模型 - C/C++ - 汇编语言 --- > 可能分析的时候会用到一点汇编语言，不过都很简单，不影响理解文章。 # 预备知识 在开始正文之前，需要复习下函数调用的约定。 - __cdecl: C/C++函数**默认**调用约定，参数依次从右向左传递，并压入堆栈，最后由调用函数清空堆栈，这种方式适用于传递参数个数可变的被调用函数，只有被调用函数才知道它传递了多少个参数给被调用函数，比如printf(); - __stdcall：参数由右向左传递，并压入堆栈，由被调用函数清空堆栈，当函数有可变参数个数时，函数调用约定自动转换成__cdecl调用约定; - __thiscall：C++非静态成员函数默认调用约定，不能使用个数可变参数，调用非静态成员函数时，this指针直接保存在ecx寄存器中，不入栈，其他方面同__stdcall； - __fastcall：凡是接口函数都必须指明其调用规范，除非接口函数是类的非静态成员函数； # 简洁的内存模型抽象...

AlexiaChen

--- title: DNS是怎样工作的？ date: 2017-03-09 15:38:56 tags: - DNS - 计算机网络 - TCP/IP --- >*直接开始正文算了，主要是总结。* ## Episode 1-----网站是未知的 先来陈述一个事实，计算机和其他设备在因特网上互相通信识别对方都是通过IP地址进行的。但是人们并不擅长记忆类似于10.0.0.1 192.168.1.0等这样的IP地址，所以就用了字符文字串（google.com, wikipidia.org） 而域名系统（Domain Name System, DNS）,就是把IP地址和字符文本串关联在一起的系统，这样就能找到IP地址了。 假设个场景： 小A在浏览器里输入的一串mathxh.com的网址 首先，浏览器和操作系统会去它们各自的缓存中检查是否有mathxh.com的地址，如果没有，那么操作系统会去请求**解析器**(resolver) 啥是resolver呀？请看下一章 ##...

AlexiaChen

--- title: 开始学编译原理一点有趣的东西 date: 2017-03-28 10:48:27 tags: - 编译原理 - 程序语言理论 --- > *唉，好像又回到大学被《编译原理》狂虐的时代了。因为最近在设计自己的脚本语言解释器，由于词法分析阶段用正则文法(3型文法)就能搞定，但是语法分析阶段不学习上下文无关文法(2型文法)是不行的了，所以出来混迟早是要还的* 我在之前的文章《什么是类型安全》提到过著名语言学家乔姆斯基的一个例子，是为了说明语法和语义的区别。其实乔姆斯基作为世界顶级的语言学专家为语言学的研究发展做出了很大的贡献，不要以为人类的语言与程序设计语言没有半点关系（确实，它们之间的关系并不大），乔姆斯基的贡献之一，就是在[形式语言(formal language)](https://en.wikipedia.org/wiki/Formal_language)领域提出了著名的[乔姆斯基层级谱系(Chomsky hierarchy)](https://en.wikipedia.org/wiki/Chomsky_hierarchy)，它把所有的形式语言的形式文法分成了四大类，分别是0型文法，1型文法，2型文法，3型文法。从包含关系上来说，0型文法 > 1型文法 > 2型文法 > 3型文法。 符号'>'表示，X范围大于X， 0型文法是1，2，3型文法的超集(superset)。 那么计算机编程语言到底与上面的形式文法有什么关系呢？因为计算机编程语言的定义就需要用到上面的形式化文法来描述。 其实很多计算机相关的语言背后都有一定的基础。比如： - LISP，背后是λ演算，这个数学基础给了LISP非常强大的表达能力；（虽然多数人不直接用LISP）至少，LISP给现在各种支持函数式编程的语言提供了借鉴。 -...

AlexiaChen