Month: 十二月 2017

学习写一个编译器

# 为什么?

有一个很好的比喻:不懂编译器写程序就好比没有学过人体解剖学就去画人像一样,能当让是能,但是核心上总有些不对的地方

每个成功的项目都有很多的语言构成,拿一个简单的 Python Web 项目来说,我们可能需要 Python、yml、jinja、ini 等等多种语言(不一定是完备的变成语言)。总有一天你对发现现有的语言并不能特别好得满足你的特定需求的时候,而这时候你就需要一个编译器了。

设计一门语言还是一个很好的联系

![](http://www.craftinginterpreters.com/image/a-map-of-the-territory/mountain.png)

# 编译的步骤

![](http://www.craftinginterpreters.com/image/a-map-of-the-territory/string.png)

1. Scanning,也就是词法分析(Lexical Analysis)
2. Parsing

Python 的单元测试

# 编写测试的基本原则

每一个测试单元必须是完全独立的。每一个必须能够独立运行以及在其他的测试组中运行,不管他们的顺序如何。加载和清空数据应该使用 setUp() 和 tearDown() 方法(如果使用unittest)。

**sans-io**。也就是把逻辑和 IO 分开来,这样在测试的时候方便指定输入,以及捕获输出。

尽量让测试跑的快一点。如果一个测试在几毫秒之内跑不完的话,开发就会慢下来,以至于没有人再去跑这些测试了。如果实在有很花时间的测试,把他们单独放在一起定期执行。

如果你正在开发某样东西的过程中被打断的话,可以写一个测试,这样当你回过头来的时候还能很快想起来需要做什么。

使用有描述性的长名字。实际代码中你可能使用 `square()` 这样的名字,但是在测试用你要用 `test_square_of_number_2` 这样的名字。

测试代码的另一个用途是作为新手的介绍。让别人来看你的代码的时候,看看测试就知道他是干什么的了。

# 编写测试的思路

按照代码逻辑分支测试,把代码的每一个分支的

1. 入口参数是什么
2. 出口参数是什么
3. 副作用是什么
4. 产生的异常是什么

都测试到。

# 工具选择

Python 常用的测试工具有三种:

1. 标准库自带的 unittest
2. nose[2]
3. pytest

其中 unittest 完全是从 JUnit 移植过来的,用起来稍微有些别扭。nose 和 pytest 相比的话,网友大多推荐 pytest。详细的比较可一件参考文档。

# pytest
 
测试函数使用test_开头, pytest 默认会查找当前目录中的 `test_` 开头或者 `_test` 结尾的文件中的测试并运行。使用assert来验证语句。

## 测试某个异常抛出:

“`
import pytest
def f():
    raise SystemExit(1)
 
def test_mytest():
    with pytest.raises(SystemExit):
        f()
“`

## 执行顺序

如果在一个文件中定义了多个测试函数,那么 pytest 将按照函数定义的顺序执行。

## setup 和 teardown

setup 和 teardown 用来在测试开始前加载资源,并在测试结束后卸载资源。

1. 可以在文件中定义 setup_module 和 teardown_module 中
2. 可以在类中定义 setup_class 和 teardown_class 中定义加载和卸载方法。

## pytest 命令行选项

`pytest some_mod.py` 运行某个文件中的中的测试

`pytest tests/` 运行某个目录中的测试

`pytest -x` 在第一个错误的地方结束

pytest –pdb,当出现异常的时候, 打开pdb

## mock 和 patch

# unittest

“`
import unittest

def fun(x):
return x + 1

class MyTest(unittest.TestCase):
def setUp(self):
# bootstrapping
def tearDown(self):
#clean up
def test(self):
self.assertEqual(fun(3), 4)
“`

Unittest 中的 assert 方法:

方法 | 含义
—-|—-
assertEqual(a, b)|a == b
assertNotEqual(a, b)|a != b
assertTrue(x)|bool(x) is True
assertFalse(x)|bool(x) is False
assertIs(a, b)|a is b
assertIsNot(a, b)|a is not b
assertIsNone(x)|x is None
assertIsNotNone(x)|x is not None
assertIn(a, b)|a in b
assertNotIn(a, b)|a not in b
assertIsInstance(a, b)|isinstance(a, b)
assertNotIsInstance(a, b)|not isinstance(a, b)

save it as fun_test.py and run it by:

“`
python -m unittest fun_test
“`

# doctest

Note: only method starts with test is run by unittest module

unittest这个库没有按照PEP8来, 看着就不爽

注意docstring

需要用 unicode, 需要用u prefix

需要转义 \n

需要使用来代表空行

# 参考文档

1. https://www.reddit.com/r/Python/comments/50nqlp/is_nose_still_relevant_how_about_unittest/
2. https://agopian.info/presentations/2015_06_djangocon_europe/?full#pythonic
3. http://docs.python-guide.org/en/latest/writing/tests/
4. https://realpython.com/python-testing/
5. https://pytest-benchmark.readthedocs.io/en/latest/
6. https://medium.com/@yeraydiazdiaz/what-the-mock-cheatsheet-mocking-in-python-6a71db997832

[ZZ]如何做创业的品类选择

转自:http://mp.weixin.qq.com/s/WdK1umJkeeQdgpFS9wZh7Q

我们先看共享单车。

移动支付、移动定位、地图、无桩、电子锁等等东西都不是突然出现的技术革新,但当这些东西的普及、覆盖、技术成熟度等都达到了一个临界点,ofo、摩拜就出现了。

在这个例子下,Friction 是购买成本、是使用成本、是付费便捷度、是持有成本等等。

再看共享充电宝。

基本所有的技术基础和共享单车区别不大,但从 Friction 角度来看,有几点不同,而正是这几点不同,带来了本质的区别。

首先,充电宝很便宜,购买成本很低,所以人们可以随手购买;其次,充电宝体积很小,持有成本很低,所以人们可以随身携带;最后,充电宝无法像单车一样随处停放,所以还多出了一个归还成本。

也就是说,从 Friction 的角度来看,购买充电宝本身已经 Friction 很低,而共享充电宝的归还还反过来增加了 Friction。所以共享充电宝不如共享单车的品类好。

那比较这两种其实我们可以发现,体积大的东西才有持有成本,而有持有成本才有 Friction 可以减少,也就是才有增值点,而人们无法携带体积更大的东西,所以就需要这类东西自带移动属性,也就是类交通工具才可以。

而体积小的东西必须是人们愿意随身携带的,而且购买成本或持有成本高的,才能弥补(计算 Friction 总和)。这样的品类还有什么?

这就到了第三种公司,衣二三这类的服装租赁。

衣服这个品类非常有意思。衣服作为一个类别,是人们每天都要穿的(也就是每个人都随身携带的),但对于单件衣服来说,却有购买成本高,使用频次低(更换频次高)的问题。

所以说,衣服租赁这个品类也是个好品类。

Google 关于Machine Leaning 的笔记

前几天看了 Google 的一个关于 Machine Learning 的[slides][1],感觉不错,整理一下学习笔记

# ML 的定义

> An approach to achieve artificial intelligence through systems that can learn from experience to find patterns in that data

> ML teaches a computer to recognise patterns by examples, rather than programming it with specific rules.

一个例子:

![](https://ws1.sinaimg.cn/large/006tNc79gy1fmjv6ugbr4j31jw0mo4qp.jpg)

# feature

一般来说,几个属性就代表了几个维度。

有时候更多的维度,更容易做出分类:参考[这里](http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/)

# 机器学习的分类

## 监督学习

数据是标注过的

## 无监督的学习

从没有标注的数据中学习

## 强化学习

通过带有激励的试错来学习

# 例子

## 线性回归(Linear Regression)

## 聚类

## KNN

## 神经网络

## fully-connected 神经网络

## 深度神经网络(DNN)

深度的意思就是有很多的层。比如说,对于人脸识别,其中某些层可能会识别出线条,然后有的层会识别出眼睛等等

## 卷积神经网络(CNN)

CNN 可以用来处理图片数据,以及可以表示为图片的数据。要确定一组数据可不可以表示为图片,可以尝试交换任意两行,或者任意两列,如果交换后对数据没有影响,那么就不可以被认为是图片数据。更多细节参看这个 [Video][2]

# 算法的分类

详细讲解请看[这里][1]

## Regression

回归首先要有一个评价误差的方法,然后迭代的求出模型。回归是一类从统计中得出的方法,比如上面说到的 线性回归(用最小二乘法),还有逻辑回归等等。

## Instance Based

Instance Based 是一个决策方法。通过相似度计算找出最接近的实例。比如KNN

## Decision Tree

自定向下,做出决策

## Bayesian

## clustering

## association rules

## Artificial Neural Network

模拟人的神经系统,比如感知机

## 深度学习

其实就是很多层的神经网络,比如CNN

## 降维 (Dimensionality Reduction)

找到数据的内在属性,然后缩减维度,以便能够使用监督学习方法

还有一个ensemble没看懂

# 机器学习的输出

## 连续输出

比如拟合好的线性回归跟定一个数值,可以预测另一个数值

## 概率预测

## 分类

比如分辨出小猫小狗,或者是识别数字

[1]: https://docs.google.com/presentation/d/1kSuQyW5DTnkVaZEjGYCkfOxvzCqGEFzWBy4e9Uedd9k/preview
[2]: https://youtu.be/FmpDIaiMIeA
[3]: https://machinelearningmastery.com/a-tour-of-machine-learning-algorithms/

知识付费是一个伪需求

从分答开始,互联网似乎掀起了一股知识付费的热潮。然而在我看着这股热潮实在是个大大的泡沫,只不过是乘着支付宝和微信支付普及的东风创造出来的一个伪需求,热乎劲一过估计也就偃旗息鼓了。

互联网的精神是开放共享,而知识付费则是建立了一个付费的围墙,显然和大势是相悖的。

# 回答欲

对于付费的问题和收费的问题,人们的回答欲望是有天壤之别的。有时候看个问题不错,就是按耐不住体内的洪荒之力,想写上几千字。但是突然有个人过来说,来回答这个问题给你5块钱,瞬间就不想答了。。

本来回答问题实际上是自己的一种精神享受,而一旦加上钱以后,人们潜意识里就会觉得这是再给别人干活儿了,所以几块钱反倒会坏了事。

真正有价值的东西要么根本不会公开传播,要么那就是要出书立传,流芳千古的,会卖着屈屈几块钱?

比如说我,去开一场live,5块一个人,有1000人来听,那我也得准备上个一两天吧,但是我能教啥呢,我可以说一些爬虫的基础知识啥的,但是说深了,我也不能暴露我们的业务数据吧?比我级别高一点的,手里期权一大把,会缺这点钱?会有时间挣这点钱?哪怕是个愿意分享知识,建立自己影响力的人,那肯定会去写博客啊,这样才能扩大影响力嘛

# 眼下的红火

付费问答现在还是一个噱头,所以还会有一些名人/大V来做问答,但是这更多意义上算是粉丝经济,名人要的是曝光度,而不是在乎那屈屈几款钱。名人的话更多的是增加了曝光,这个潜在价值太大,不过说了。但是主流的开live的人,如果是邀请来的人水平够了,那人家根本不缺这点钱,花这么长时间就能在这么一点人之间扩大影响力太不值啊,也就图个新鲜。如果邀请来的人愿意长期赚live这个钱,那水平肯定高不了啊,不然谁吃这点苍蝇肉啊,所以就是大量的零基础入门python了。还有就是要想让受众广,就只能开这种基础课

# 在线教育

广义的说,知识付费也包括 K12 在内的在线教育,这部分我倒是非常看好。毕竟有的人就是学习能力差,或者说愿意听人嚼碎了再讲给他听,这种需求在线下是刚需,把线下的培训搬到线上,能够更好的传播,能够突破线下教育的地理限制,相信会有很好的发展。

# 付费问答的水平悖论

现在的这些付费问答就是听众想花5块钱卖价值百万的商业问题,回答的人要么不懂,要么也没法说。

一样,你想聊的人不稀罕这点钱,稀罕这点钱的人你不想和他聊

真正的知识付费是几百万的商业策划,几百万的UI设计。公开的问题可能是 “前端程序员怎么规划学习路径”,然而付费问答则可能是现在你花五块钱就想问“我现在会js,会一点css,会一点vue,blah,blah,”

# 真正的知识付费

其实知识付费早就存在。小说就是最好的例子,并不是什么高大上的新东西

lispy 笔记

阅读 norvig 文章[(How to Write a (Lisp) Interpreter (in Python))][1]的笔记。

作为从数学系转过来的学生,之前并没有学过编译原理,只是自己在一些文章中读过关于编译器的只言片语,借这篇文章了解一些编辑器的基本知识吧。

这篇文章主要是用 Python 实现了一个 lisp 的解释器。lisp 语言的语法非常简单,可以说lisp语言本身就是 AST 。一个解释器基本有两个部分。一部分是 parser,生成AST,另一部分是执行,运行AST。

“`
code –> (parse) –> AST –> (eval) –> result
“`

也就是我们只要去实现 parse 和 eval 两个函数就好了~

# 类型定义

这里使用了几个类型,都是直接衍生自Python 的原生类型

“`
Symbol = str # 变量
Number = (int, float)
Atom = (Symbol, Number)
List = list
Exp = (Atom, List)
Env = dict
“`

# parse

parse 传统意义上应该分为两部分,一部分是词法分析(Lexical Analysis),也就是 tokenize,把代码转换成一系列的 token。另一部分是语法分析,也就是合成 AST。常用的工具有 lex,ply 等

在 Lispy 中,我们直接使用 Python 的 str.split 来实现 tokenize

“`
def tokenize(chars: str) -> list:
return chars.replace(‘(‘, ‘ ( ‘).replace(‘)’, ‘ ) ‘).split()
“`

然后使用 read_from_tokens 构建一颗语法树。

“`
def read_from_tokens(tokens: list) -> Exp:
if len(tokens) == 0:
raise SyntaxError(‘unexpected EOF’)
token = tokens.pop(0) # 从左向右依次处理
if token == ‘(‘:
L = []
while token[0] != ‘)’:
L.append(read_from_tokens(tokens)) # 构建子树
tokens.pop(0) # 弹出 ‘(‘
return L
elif token == ‘)’:
raise SyntaxError(‘unexpected )’)
else:
return atom(token)

def atom(token: str) -> Atom:
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:
return Symbol(token)

def parse(program: str) -> Exp:
return read_from_tokens(tokenize(program))
“`

# environment

环境大概和scope是相关的一个概念了。比如 `sqrt` 和 `max` 都是全局环境中的函数。

“`
class Env(dict):

def __init__(self, params=(), args=(), outer=None):
self.update(zip(params, args))
self.outer = outer
def find(self, var):
return self if (var in self) else self.outer.find(var)

import math
import operator as op

def standard_env() -> Env:
env = Env()
env.update(vars(math)) # 引入python math 模块的方法
env.update({
‘+’: op.add, ‘-‘: op.sub, ‘*’: op.mul, ‘/’: op.truediv,
‘>’: op.gt, ‘<': op.lt, '>=’: op.ge, ‘<=': op.le, '=':op.eq, 'abs': abs, 'append': op.add, 'apply': lambda proc, args: proc(*args), 'begin': lambda *x: x[-1], 'car': lambda x: x[0], 'cdr': lambda x: x[1:], 'cons': lambda: x, y: [x] + y, 'eq?': op.is_, 'expt': pow, 'equal?': op.eq, 'length': len, 'list': lambda *x: List(x), 'list?': lambda x: isinstance(x, List), 'map': map, 'max': max, 'min': min, 'not': op.not_, 'null?': lambda x: x == [], 'number?': lambda x: isinstance(x, Number), 'print': print, 'procedure?': callable, 'round': round, 'symbol?': lambda x: isinstance(x, Symbol), }) return env global_env = standard_env() ``` # eval |表达式|语法|语义 |--|--|--| |变量引用|symbol|写出变量名就是表示引用这个变量| |常量|number|`10`| |条件式|(if test conseq alt)|`(if (> 10 20) (+ 1 1) (+ 3 3)` => 6|
|定义变量|(define symbol exp)|定义一个新的变量 `(define r 10)`|
|过程调用|(proc args…)|`(sqrt (* 2 8))` => 4|
|quotation|(quote exp)|返回表达式,而不是执行它。`(quote (+ 1 2))` => `(+ 1 2)`而不是3|
|赋值|(set! symbol exp)|注意和定义变量的区别|
|过程|(lambda (symbols…) exp)|定义一个新的过程 `(lambda (r) (* pi (* r r)))`|

“`
class Procedure:
def __init__(self, params, body, env):
self.params, self.body, self.env = params, body, env
def __call__(self, *args):
return eval(self.body, Env(self.params, args, self.env))

def eval(x: Exp, env=global_env) -> Exp:
if isinstance(x, Symbol): # 变量引用
return env[x]
elif not isinstance(x, List): # 常量
return x
op, *args = x
if op == ‘quote’:
return args[0]
elif x[0] == ‘if’: # 条件表达式
test, conseq, alt = args
exp = conseq if eval(test, env) else alt
return eval(exp, env)
elif x[0] == ‘define’: # 定义变量
_, symbol, exp = x
env[symbol] = eval(exp, env)
elif op == ‘set!’: # 变量赋值
symbol, exp = args
env.find(symbol)[symbol] = eval(exp, env)
elif op == ‘lambda’: # 定义过程
params, body = args
return Procedure(params, body, env)
else: # 过程调用 List
proc = eval(x[0], env)
args = [eval(arg, env) for arg in x[1:]]
return proc(*args)
“`

# repl

repl 的意思是 Read-Eval-Print-Loop,也就是我们常用的“解释器”。

“`
def repl(prompt=’lis.py> ‘):
while True:
val = eval(parse(input(prompt)))
if val is not None:
print(schemestr(val))

def schemestr(exp):
if isinstance(exp, List):
return f'({” “.join(map(schemestr, exp))})’)
else:
return str(exp)
“`

[1]: http://norvig.com/lispy.html