程序的信息量以及反向运行

最后更新日期：2014-06-12

1. 数据的两种形态：离散态和序列化态

• 定义1.1：序列化态：数据存在于文件、网络中的状态，可以表示为 有顺序的 字节序列（或字符串）
• 定义1.2：离散态：与数据结构直接对应的形态，没有顺序

2. 我看待程序的一个观点：信息流

程序 = 输入 + 中间数据处理 + 输出

输入 = 序列化态 -> 离散态 = 反序列化

1. 手工 split
2. 正则表达式
3. parser

输出 = 离散态 -> 序列化态 = 序列化

1. 手工字符串拼接

中间处理 = 离散态 -> 离散态

3. 信息流三定理

定理3.1（信息流第一定理）：在计算机系统内，信息不能凭空产生，只能从一种形式转换成另一种形式。

例 3.1.1：随机数是否凭空产生信息？

1. 一般的伪随机数生成器（Pseudo Random Generator）只根据种子和确定的算法生成，信息全部从种子来
2. 真随机数（如 /dev/random）使用硬件收集环境噪音，信息从环境中来

定理3.2（信息流第二定理）：信息只能沿着信息量不变或减少的方向流动。

• 例 3.2.1：信息量减少：strlen() 字符串可以变成长度，但长度不能变成字符串
• 例 3.2.2：信息量不变：Integer.toString() / Integer.parseInt() 整形和字符串互转

定理3.3（信息流第三定理）：自由意志（free will）可以凭空创造信息。

4. 信息量与热力学第二定理

• 信息量：系统有序程度的度量
• 熵：系统无序程度的度量

定理4.1：同一份数据的离散态的信息量大于或等于其序列化态。

5. 程序的反向运行

程序的输入和输出互为反操作：

• 输入 = 序列化态 -> 离散态
• 输出 = 离散态 -> 序列化态

问题5.1：输入和输出可以使用同一个模板吗？（或：将输入处理程序反向运行，能否进行输出处理）

• 例 5.1.1：同一个模板 “%d %d” 既可用于 printf ，又可用于 scanf
• 例 5.1.2：同一个 java.text.SimpleDateFormat 对象，既可 format ，又可 parse

import java.util.Calendar;
import java.util.Date;
import java.util.TimeZone;
import java.text.SimpleDateFormat;
import java.text.ParseException;

public class DateFormatDemo {
    public static void main(String[] args) throws ParseException {
        final SimpleDateFormat myFormat = new SimpleDateFormat("yyyy-MM-dd");
        final TimeZone tz = TimeZone.getTimeZone("Asia/Shanghai");

        { // 1. format: Date -> String
            final Calendar cal = Calendar.getInstance(tz);
            final Date now = cal.getTime();

            System.out.println(myFormat.format(now));
        }

        { // 2. parse: String -> Date
            final Date date = myFormat.parse("1999-04-1");

            final Calendar cal = Calendar.getInstance(tz);
            cal.setTime(date);

            System.out.println(cal.get(Calendar.YEAR));
            final int month = cal.get(Calendar.MONTH) + 1; // WTF: month start from 0
            System.out.println(month);
            System.out.println(cal.get(Calendar.DAY_OF_MONTH));
        }
    }
}

问题5.1.1：Mustache 模板能反向运行吗？

或：如何从一个 Mustache 模板生成的字符串和模板，得到 json？这是可以做到的吗？

由于序列化态的信息量比离散态低，增加的这部分信息从那里来？

如果不行，那么需要满足什么条件才可以？或者能否重新设计一套模板系统使得它可以反向运行？

6. prolog: 可以反向运行的编程语言

例6.1：prolog 的列表连接函数：append(X, Y, Z)

• X Y Z 均为列表
• Z = X 与 Y 的连接

正向运行：

?- append([1], [2,3], X).
X = [1, 2, 3].

反向运行：

?- append(X, Y, [1,2,3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [] ;
false.

P.S. 据说用 prolog 写 parser 就可以实现类似我前面说的反向模板，很想学一下。

7. 写一个信息量不变的程序

定义7.1：自产生程序：自己输出自己的源代码的程序。

1. 不能读文件（信息从文件来）
2. 不能用编程语言提供的反射机制（信息从编程语言运行时来）

例：js 的 function 的 toString() 直接得到源代码属于 cheating

P.S. 我在这篇文章中阐明了为什么自产生程序一定要设置一套鉴定 cheating 的规则。