博文

里耶秦简的时代错位与计算机科学中的堆栈精选

已有 16048 次阅读 2012-6-17 17:45 |个人分类:科普札记|系统分类:科普集锦| 古城, 出土文物, 里耶秦简, 古井, 时代错位

里耶秦简的时代错位与计算机科学中的堆栈(唐常杰）

昨天看了神九发射，为中国航天人的成功而高兴，搅动了童年时的飞天梦想，为了平息过度兴奋后的心情涟漪，继续寻相关节目，不期在央视纪录频道邂逅了考古纪录片《发现之路：迷城（3）》，先看上天，后看掘地，有趣。这则短片报道了湘西里耶古城的秦简奇迹，提出了竹简出土序列的时代错位问题。仔细思考后，觉得似乎可用计算机科学中的堆栈原理来解释。

里耶古城的秦简奇迹 短片中演绎了一个22个世纪前的在湘西龙山县里耶古城的突发事件。在那个大秦帝国之大厦将倾的年代，在一个月黑风高的夜晚，里耶古城的受到攻击（来自义军？楚国复辟势力？），城破之前，官员们匆匆把大量档案，包括能长期保存的竹木简牍，抛进水井，22个世纪后，成为出淤泥而不朽的国宝。

2002年6月，因水利工程而做的抢救性发掘中，在里耶镇一号古水井中出土3万多枚秦简，相比全国历代积累的6000多枚秦简，堪称奇迹。这些竹简直接或间接地描述了秦朝统一中国后的军、政、经、文领域中，与草根百姓紧密联系的一些大小事件的细节。其中还有 22个世纪前的乘法口诀“六八四十八、七八五十六”等，反映了那时的数学教育水平。

“里耶秦简”现已成为百度和谷歌上的标准关键词，比“里耶古城的秦代竹简”更简洁更普及。

为里耶高兴，古镇就要发达了，凭这些老祖宗的遗产，毫无疑义，里耶将成长为一个著名的旅游点,说不定，这些题材会被编成一部宣传里耶的电视剧。

出土序列的时间错位 按照常识，在出土文物时，上新下旧，埋藏越深层的，年代越久。但是，在里耶古城“一号井”出土的第一枚简牍却是楚简，大量的秦简埋在楚简下面。出现了发掘层中上旧下新的错位，短片指出，这是迄今（即到制作短片时）尚未解决的悬疑(相关资料点击这里）。

先进后出”的存储结构 为了解释上述这个错位悬疑，需要通俗地解释计算机科学中的数据结构—栈。简而言之，栈结构是一种“先进后出”的存储结构。其特色用英文描述，是“First In ,Last Out ”，或简称为FILO；

计算机科学中还有一种数据结构，“队列”，先进先出，模拟了日常生活中排队的规矩，先到者先享受服务；而这里要讲的堆栈，是反其道而行之。

幼儿园小朋友也会用栈结构 。幼儿园小朋友睡觉时，父母或老师会教他们这样放好衣服：先脱的衣物放下面（外衣，外裤等），后脱的放上面（毛衣，毛裤等），无意中用了一种称为“栈结构” 的高技术。而脱衣过程相当于压栈操作过程（Push）。

穿衣时，依次从栈顶拿衣服穿，自然而然，实现了后脱的衣物先穿；借用栈结构原理，小孩子也能做到有条不紊，穿衣相当于的栈的弹出（pop）操作。

拆卸机械玩具时的先卸后装 。如果你不是专家而要想拆卸一个机械玩具、钟表或仪器，用一张纸记下拆卸的零件的次序、外形好位置，把零件妥善地、有序地放成序列（栈结构），装配时按照“后拆的先装”。就能有条不紊。

计算机科学中的堆与栈 感谢19楼的意见，与其说“幼儿园小朋友也会用栈结构”，不如说计算机科学家向“幼儿园小朋友”学习，向生活学习，从生活中吸取灵感，发明了栈结构。

（如果觉得下面一段的细节较难，不妨直接跳过这一段）。

有的书把栈结构又称为“堆栈”，是因为堆与栈比较相似，在具体的程序语言中，堆和栈还是有一些区别的。堆用于分配指针空间，而栈用于控制过程调用（参数、返回机制等），对栈空间的反复使用是用时间换取空间的重要编程技巧，还有若干差别，一言难尽。

下图演示了计算机科学中的栈结构操作，1-3图演示了压栈过程。第4图是从顶弹出3号数据。直观地表达了“先进后出”的特色。堆栈广泛地用于计算机编程中，例如递归控制、编译原理中的函数调用、括号配对、复杂表达式求值，以及计算的优先级处理，等等。

计算理论中，有一种“带有栈的图灵机”，又称下推机（ pushdown automata),用于在理论上处理“前后文无关语言CFL”（现有的程序语言都属于CFL）。笔者在科学网BBS群组上上载过计算理论PPT，其中3.2.2--3.2.3节有几十页对CFL和堆栈的解释和图示，包括堆栈在识别CFL中的作用，动作特点等等，在这里一言难尽，有多个下载地址，参见博文《共享计算理论PPT 》

里耶古城的大秦官员在档案管理中不自觉地用了栈结构技术。有下列猜想：

(1) 敌档为我所用秦攻占里耶之前，里耶是楚城，自然有楚国的官府文书档案。秦军攻占里耶后，接管并改造了原来的楚国的官府，同时接管了敌方文书档案，作为治理地方的资源。

(2)平时怎么便捷怎么放。治理里耶的大秦官员用栈结构思想来管理档案，硬件可能是柜子，可能是地窖，也可能是简单堆放在地板上，软件就像今天的电脑输入法，采用了“高频先见”的技术，用得越频繁的（通常是越新的）放在越上面；用的越少的（通常是越旧的），放下面。是一种广义的栈结构技术，例如，不是一支竹简一个地址，而是一捆竹简或几捆竹简作为一个单位（给一个存储地址）来管理。

(3) 扔时怎么便捷怎么扔。在那个月黑风高的夜晚，里耶城破之前，官员们把存储的档案抛进城内的水井。做了一次栈的大弹出运动。根据（2）的分析，年代比较新的，在栈结构的上层，拿起来方便，先抛，而沉积水井下层；而年代比较旧的，包括接管的楚国的简牍（根据是（1）），在栈结构的下层，后抛，结果沉积在水井上层。其慌乱和惊慌失措情景，在许多电视剧的兵败如山倒的情节中常常见到，时代虽不同，但在突发事件时的心理行为相似，是可以理解，可以猜测的。

怎样验证上述猜想呢？不妨检查已经出土的3万多枚秦简，检查其出土次序，是否有下新而上旧的情况。如果是，解释了时代错位是由于那个月黑风高夜抛弃档案时图方便、抢速度的合理操作的自然结果。

历史题，计算机方式做 教师常用生活实例解释概念。例如，用上面的“小孩脱衣”和“里耶竹简”例子给初学者解释栈概念，反过来，给一位已经理解堆栈结构的同行讨论“里耶竹简”时，只说一个字“栈！”，对方就心有灵犀一点通了。离开了这个背景而讲“里耶竹简“，可能有点“小题大做”，或“历史题，计算机方式做”，与其说是僭越，不如当成娱乐吧。

不知是否会有考古专家看到这篇博文，这仅仅是是外行的班门弄斧，权当猜想，权当娱乐，考古专家可能会见笑了。