乐正

Actions speak louder than words.

计算机程序的构造和解释-习题解答

目标是完成《计算机程序的构造和解释》一书所有的习题。会不断更新,希望在年底之前能完成。

第一章: 构造过程抽象

1.1 程序设计的基本元素

1.2 过程与它们所产生的计算

1.3 用高阶函数做抽象

第二章: 构造数据抽象

2.1 数据抽象导引

2.2 层次性数据和闭包性质

2.3 符号数据

2.4 抽象数据的多重表示

2.5 带有通用型操作的系统

第三章: 模块化、对象和状态

3.1 赋值和局部状态

3.2 求值的环境模型

3.3 用变动数据做模拟

3.4 并发:时间是一个本质问题

3.5 流

  • 3.5.1 流作为延时的表(练习 3.50练习 3.51练习 3.52)
  • 3.5.2 无穷流(练习 3.53练习 3.54练习 3.55练习 3.56练习 3.57练习 3.58练习 3.59练习 3.60,练习 3.61,练习 3.62)
  • 3.5.3 流计算模式的使用(练习 3.63,练习 3.64,练习 3.65,练习 3.66,练习 3.67,练习 3.68,练习 3.69,练习 3.70,练习 3.71,练习 3.72,练习 3.73,练习 3.74,练习 3.75,练习 3.76)
  • 3.5.4 流和延时求值(练习 3.77,练习 3.78,练习 3.79,练习 3.80)
  • 3.5.5 函数式程序的模块化和对象的模块化(练习 3.81,练习 3.82)

第四章: 元语言抽象

4.1 元循环求值器

4.2 Scheme 的变形 —— 惰性求值

  • 4.2.1 正则序和应用序(练习 4.25,练习 4.26)
  • 4.2.2 一个采用惰性求值的解释器(练习 4.27,练习 4.28,练习 4.29,练习 4.30,练习 4.31)
  • 4.2.3 将流作为惰性的表(练习 4.32,练习 4.33,练习 4.34)

4.3 Scheme 的变形 —— 非确定性求值

  • 4.3.1 amb 和搜索(练习 4.35,练习 4.36,练习 4.37)
  • 4.3.2 非确定性程序的实例(练习 4.38,练习 4.39,练习 4.40,练习 4.41,练习 4.42,练习 4.43,练习 4.44,练习 4.45,练习 4.46,练习 4.47,练习 4.48,练习 4.49)
  • 4.3.3 实现 amb 求值器(练习 4.50,练习 4.51,练习 4.52,练习 4.53,练习 4.54)

4.4 逻辑程序设计

  • 4.4.1 演绎信息检索(练习 4.55,练习 4.56,练习 4.57,练习 4.58,练习 4.59,练习 4.60,练习 4.61,练习 4.62,练习 4.63)
  • 4.4.2 查询系统如何工作
  • 4.4.3 逻辑程序设计是数理逻辑吗(练习 4.64,练习 4.65,练习 4.66,练习 4.67,练习 4.68,练习 4.69)
  • 4.4.4 查询系统的实现(练习 4.70,练习 4.71,练习 4.72,练习 4.73,练习 4.74,练习 4.75,练习 4.76,练习 4.77,练习 4.78,练习 4.79)

第五章: 寄存器机器里的计算

5.1 寄存器机器的设计(练习 5.1)

  • 5.1.1 一种描述寄存器机器的语言(练习 5.2)
  • 5.1.2 机器设计的抽象(练习 5.3)
  • 5.1.3 子程序
  • 5.1.4 采用堆栈实现递归(练习 5.4,练习 5.5,练习 5.6)
  • 5.1.5 指令总结

5.2 一个寄存器机器模拟器(练习 5.7)

  • 5.2.1 机器模型
  • 5.2.2 汇编程序(练习 5.8)
  • 5.2.3 为指令生成执行过程(练习 5.9,练习 5.10,练习 5.11,练习 5.12,练习 5.13)
  • 5.2.4 监视机器执行(练习 5.14,练习 5.15,练习 5.16,练习 5.17,练习 5.18,练习 5.19)

5.3 存储分配和废料收集

  • 5.3.1 将存储看作向量(练习 5.20,练习 5.21,练习 5.22)
  • 5.3.2 维持一种无穷存储的假象

5.4 显式控制的求值器

  • 5.4.1 显式控制求值器的内核
  • 5.4.2 序列的求值和尾递归
  • 5.4.3 条件、赋值和定义(练习 5.23,练习 5.24,练习 5.25)
  • 5.4.4 求值器的运行(练习 5.26,练习 5.27,练习 5.28,练习 5.29,练习 5.30)

5.5 编译

  • 5.5.1 编译器的结构(练习 5.31,练习 5.32)
  • 5.5.2 表达式的编译
  • 5.5.3 组合式的编译
  • 5.5.4 指令序列的组合
  • 5.5.5 编译代码的实例(练习 5.33,练习 5.34,练习 5.35,练习 5.36,练习 5.37,练习 5.38)
  • 5.5.6 词法地址(练习 5.39,练习 5.40,练习 5.41,练习 5.42,练习 5.43,练习 5.44)
  • 5.5.7 编译代码和求值器的互连(练习 5.45,练习 5.46,练习 5.47,练习 5.48,练习 5.49,练习 5.50,练习 5.51,练习 5.52)

机器学习基础

现今,机器学习已应用于多个领域,远超出大多数人的想象,下面就是假想的一日,其中很 多场景都会碰到机器学习:假设你想起今天是某位朋友的生日,打算通过邮局给她邮寄一张 生日贺卡你打开浏览器搜索趣味卡片,搜索引擎显示了10个最相关的链接你认为第二个链接 最符合你的要求,点击了这个链接,搜索引擎将记录这次点击,并从中学习以优化下次搜索 结果然后,你检查电子邮件系统,此时垃圾邮件过滤器已经在后台自动过滤垃圾广告邮件, 并将其放在垃圾箱内接着你去商店购买这张生日卡片,并给你朋友的孩子挑选了一些尿布结 账时,收银员给了你一张1美元的优惠券,可以用于购买6罐装的啤酒之所以你会得到这张优 惠券,是因为款台收费软件基于以前的统计知识,认为买尿布的人往往也会买啤酒然后你去 邮局邮寄这张贺卡,手写识别软件识别出邮寄地址,并将贺卡发送给正确的邮车当天你还去 了贷款申请机构,查看自己是否能够申请贷款,办事员并不是直接给出结果,而是将你最近 的金融活动信息输入计算机,由软件来判定你是否合格最后,你还去了赌场想找些乐子,当 你步入前门时,尾随你进来的一个家伙被突然出现的保安给拦了下来“对不起,索普先生, 我们不得不请您离开赌场我们不欢迎老千”。

什么是机器学习?

简单地说,机器学习就是把无序的数据转换成有用的信息

机器学习横跨计算机科学、工程技术和统计学等多个学科,需要多学科的专业知识。

关键术语

  • 专家系统。
  • 特征,也称作属性。
  • 实例。
  • 分类。
  • 训练集。
  • 训练样本。
  • 目标变量。
  • 测试数据。
  • 知识表示。

机器学习的主要任务

  • 分类
  • 回归
  • 监督学习
  • 非监督学习
  • 密度估计
  • 聚类

选择合适算法

监督学习的用处: + K近邻算法: 线性回归 + 朴素贝叶斯算法: 局部加权线性回归 + 支持向量机: Ridge回归 + 决策树: Lasso最小回归系数估计

非监督学习的用处 + K-均值 - 最大期望值算法 + DBSCAN - Parzen窗设计

开发机器学习应用步骤

  1. 收集数据
  2. 准备输入数据
  3. 分析输入数据
  4. 训练算法
  5. 测试算法
  6. 使用算法

Laravel 源码解读

为WEB艺术家创造的框架

由SitePoint发起的2015年最流行WEB框架的调查中,Laravel已巨大的优势获得了商用使用 数量、个人项目使用数量的第一名。当之无愧是目前最好的WEB框架之一。那么就让我们来 一步一步探究这样优秀的框架究竟是如何实现的吧。

最流行框架投票

目录

入口文件 index.php

一个基于Laravel的应用,当WEB服务器接受到来自外部的请求后,会将这个这个请求解析到 应用根目录的 public/index.php 中。

Laravel源码解读-index.php (laravel_index.php) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<?php
/**
 * Laravel - A PHP Framework For Web Artisans
 *
 * @package  Laravel
 * @author   Taylor Otwell <taylorotwell@gmail.com>
 */

/*
|--------------------------------------------------------------------------
| Register The Auto Loader
|--------------------------------------------------------------------------
|
| Composer provides a convenient, automatically generated class loader for
| our application. We just need to utilize it! We'll simply require it
| into the script here so that we don't have to worry about manual
| loading any of our classes later on. It feels nice to relax.
|
*/

require __DIR__.'/../bootstrap/autoload.php';

/*
|--------------------------------------------------------------------------
| Turn On The Lights
|--------------------------------------------------------------------------
|
| We need to illuminate PHP development, so let us turn on the lights.
| This bootstraps the framework and gets it ready for use, then it
| will load up this application so that we can run it and send
| the responses back to the browser and delight our users.
|
*/

$app = require_once __DIR__.'/../bootstrap/app.php';

/*
|--------------------------------------------------------------------------
| Run The Application
|--------------------------------------------------------------------------
|
| Once we have the application, we can handle the incoming request
| through the kernel, and send the associated response back to
| the client's browser allowing them to enjoy the creative
| and wonderful application we have prepared for them.
|
*/

$kernel = $app->make(Illuminate\Contracts\Http\Kernel::class);

$response = $kernel->handle(
    $request = Illuminate\Http\Request::capture()
);

$response->send();

$kernel->terminate($request, $response);

第二十一行代码

1
require __DIR__.'/../bootstrap/autoload.php';

为Laravel应用引入了由Composer提供的类加载器,这样Laravel应用便无需再手动加载任 何的类。其加载原理不是此次探究的目标,所以仅仅这样使用就好了。接下的代码,便是重 点。

Illuminate\Foundation\Application 类

该类的继承结构如下:

类继承结构

第三十五行代码

1
$app = require_once __DIR__.'/../bootstrap/app.php';

它将我的视线引入到了另外一个文件中,去看看到底发生了什么吧。

Laravel源码解读-app.php (laravel_app.php) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
<?php

/*
|--------------------------------------------------------------------------
| Create The Application
|--------------------------------------------------------------------------
|
| The first thing we will do is create a new Laravel application instance
| which serves as the "glue" for all the components of Laravel, and is
| the IoC container for the system binding all of the various parts.
|
*/

$app = new Illuminate\Foundation\Application(
    realpath(__DIR__.'/../')
);

/*
|--------------------------------------------------------------------------
| Bind Important Interfaces
|--------------------------------------------------------------------------
|
| Next, we need to bind some important interfaces into the container so
| we will be able to resolve them when needed. The kernels serve the
| incoming requests to this application from both the web and CLI.
|
*/

$app->singleton(
    Illuminate\Contracts\Http\Kernel::class,
    App\Http\Kernel::class
);

$app->singleton(
    Illuminate\Contracts\Console\Kernel::class,
    App\Console\Kernel::class
);

$app->singleton(
    Illuminate\Contracts\Debug\ExceptionHandler::class,
    App\Exceptions\Handler::class
);

/*
|--------------------------------------------------------------------------
| Return The Application
|--------------------------------------------------------------------------
|
| This script returns the application instance. The instance is given to
| the calling script so we can separate the building of the instances
| from the actual running of the application and sending responses.
|
*/

return $app;

看第十四行,原来$app是一个 Illuminate\Foundation\Application 对象,那么在创 建这个对象的时候又发生了什么呢?

从它的构造方法看起:

Illuminate\Foundation\Application 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Create a new Illuminate application instance.
 *
 * @param  string|null  $basePath
 * @return void
 */
public function __construct($basePath = null)
{
    $this->registerBaseBindings();

    $this->registerBaseServiceProviders();

    $this->registerCoreContainerAliases();

    if ($basePath) {
        $this->setBasePath($basePath);
    }
}

顺着函数调用,往下看。在这个构造函数中,首先调用了registerBaseBindings方法。

Illuminate\Foundation\Application#registerBaseBindings
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
  * Register the basic bindings into the container.
  *
  * @return void
  */
protected function registerBaseBindings()
{
    static::setInstance($this);

    $this->instance('app', $this);

    $this->instance('Illuminate\Container\Container', $this);
}

这段代码,是将实例对象注入到容器中。那么,这个容器是什么呢?答案还是要从这段调用 中去寻找。

static::setInstance($this) 所做的就是将 $this 赋值给自身的 instance 静态变 量。重点看 $this->instance('app', $this)

instance 函数的作用是绑定一个已有对象到容器中,这个对象在容器中共享并且可以通 过键获取。

Illuminate\Container\Container#instance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
  * Register an existing instance as shared in the container.
  *
  * @param  string  $abstract
  * @param  mixed   $instance
  * @return void
  */
public function instance($abstract, $instance)
{
    if (is_array($abstract)) {
        // $abstract 是这样的一个数组 ['actual key' => 'alias']
        list($abstract, $alias) = $this->extractAlias($abstract);

        // 实际上的行为是 $this->aliases[$alias] = $abstract;
        $this->alias($abstract, $alias);
    }

    unset($this->aliases[$abstract]);

    // 检查是否有这个键是否已经注册到容器中
    // $bound 是一个boolean值
    $bound = $this->bound($abstract);

    $this->instances[$abstract] = $instance;

    if ($bound) {
        $this->rebound($abstract);
    }
}

视线重新回到Application类中,接下来调用了这个方法 $this->registerBaseServiceProviders()

Illuminate\Foundation\Application#registerBaseServiceProviders
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
  * Register all of the base service providers.
  *
  * @return void
  */
protected function registerBaseServiceProviders()
{
    $this->register(new EventServiceProvider($this));

    $this->register(new RoutingServiceProvider($this));
}

/**
  * Register a service provider with the application.
  *
  * @param  \Illuminate\Support\ServiceProvider|string  $provider
  * @param  array  $options
  * @param  bool   $force
  * @return \Illuminate\Support\ServiceProvider
  */
public function register($provider, $options = [], $force = false)
{
    if ($registered = $this->getProvider($provider) && !$force) {
        return $registered;
    }

    // If the given "provider" is a string, we will resolve it, passing in the
    // application instance automatically for the developer. This is simply
    // a more convenient way of specifying your service provider classes.
    if (is_string($provider)) {
        $provider = $this->resolveProviderClass($provider);
    }

    $provider->register();

    // Once we have registered the service we will iterate through the options
    // and set each of them on the application so they will be available on
    // the actual loading of the service objects and for developer usage.
    foreach ($options as $key => $value) {
        $this[$key] = $value;
    }

    $this->markAsRegistered($provider);

    // If the application has already booted, we will call this boot method on
    // the provider class so it has an opportunity to do its boot logic and
    // will be ready for any usage by the developer's application logics.
    if ($this->booted) {
        $this->bootProvider($provider);
    }

    return $provider;
}

其中,EventServiceProvider和RoutingServiceProvider分别是

  • Illuminate\Events\EventServiceProvider
  • Illuminate\Routing\RoutingServiceProvider

这些ServiceProvider是 Illuminate\Support\ServiceProvider 的子类,它接受一个 Application 对象作为构造函数参数,存储在实例变量 $app 中。

注入所有基础 Service Provider

register 方法中,每个ServiceProvider被调用了自身的 register 方法。首先看 看 EventServiceProvider 中的吧。

Illuminate\Events\EventServiceProvider#register
1
2
3
4
5
6
7
8
public function register()
{
    $this->app->singleton('events', function ($app) {
        return (new Dispatcher($app))->setQueueResolver(function () use ($app) {
            return $app->make('Illuminate\Contracts\Queue\Factory');
        });
    });
}

上面方法体将一个 Illuminate\Events\Dispatcher 对象以键 events 绑定到了容器 中,它负责实现事件的调度。

再看看 Illuminate\Routing\RoutingServiceProvider:

Illuminate\Routing\RoutingServiceProvider#register
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public function register()
{
    $this->registerRouter();

    $this->registerUrlGenerator();

    $this->registerRedirector();

    $this->registerPsrRequest();

    $this->registerPsrResponse();

    $this->registerResponseFactory();
}

首页是在Laravel中接触的最多的 route 被注册,它是 Illuminate\Routing\Router 对象。