[序]Scheme 与 Algorithm

这篇本来计划些内容的，不过后来有变动。
因为和另一篇“Scheme Toy”是同时开篇的，后来写着那篇，结果这篇就给废弃了。
两篇计划的内容有些重复，而且本来是把那篇作为这篇的简化版和详细版的。
既然那篇已经写完了，虽然写着不注意使得内容上已经和这篇有所偏离，这里也无心再重复。
最后把这篇的框架整理完，算一个索引吧，质量什么也是无力的事情了（摊手。
在那里写每行间有空行的，结果这里也开始乱断行了。

创建日期：2010年12月13日


* 序言

此篇是随意的笔记，仅尽力为一些可述的内容建立关联，算是导读性质。
另外，虽然文字设法去接触一些理论化的东西，不过关注点会放在使用。
也就是说从概念和接口的角度来发现应用，对实现的细节暂时不去暴露。
所以，一个不幸的后果是，以下内容无任何技术含量，留下的仅仅是文字的堆砌而已。
如果确实要使用到下面涉及的一些内容，还是要有相关教材的阅读经验，而不仅仅接触一下的罗列。
注意：以下各部分未按一定次序排列，而是又若干话题引开。


* SICP

历史上传奇的MIT6.001课程教材，受很大的推崇。原因略。
有提供在线版本获得：http://mitpress.mit.edu/sicp/

大致内容可以参考目录，也章节相联系，不过话题还是算比较分散的。
本来是说这里再简单整理一个索引的，不过有在另一篇里写了一些。


* Scheme Toy

这个算自己断断续续写了近一个月的科普文。

首先补遗一下：
关于数值计算，符号计算，矩阵模型，并行模型这些话题结果那里漏写了。
于是就写在这里吧，Scheme有对于这些应用还是可以胜任的。
在Scheme有Number Tower，数字分精确和非精确两种。
高精度数和分数都是精确类型中很有用的东西，特别在一些数学问题上。
比如某些的数列增长很快，很容易就计算到比较大的整数上面。
复合类型可以用列表来表示，这样很容易对符号进行计算。
例如求导数，可以用数值方法进行大量的运算，求更精确的近似解。
或者可以直接对表达式求导，判断运算类型，然后选择适用的规则。
矩阵的话，本身是一个符号，可以表达点的关联，以及向量的变换。
矩阵可以按照符号的方式进行计算，并用来抽象现实中的情景。
并行模型的话，一种是说多任务，一种是说传统的并发。
协同式多任务是对连续的一种有趣的应用，强调的是配合。
并发的话则是注意同步锁的问题，要避免其中的冲突。
这些内容是计算写到的，不过后来给忽略掉了，因为主线往后推了。
还有GCD和奇偶上的话题，可以涉及一些基础的数论知识。

说到主线，最初的动机是从SICP跳跃的发现一些有趣的东西来作些说明。
所以最初的内容还是从该书的前三章来挑选的，并寻找一些生活中的例子。
这个算是出发点，就是Scheme中机制可以让问题的描述变得简单。
这种简单是语言对功能的抽象，以及编码对思维的抽象。
因为Lambda是Church数方面的理论，所以这次的问题也主要侧重数学方面。
当然，是生活中的数学了，比如第一节就是说关于表达式与计算器什么的。
关于语言呢，是一中用来表达思维的方式，因为Scheme语言有层次状的结构。
也就是说一种应用可以基于更基础的运用，这样在使用的时候会更专注到抽象过程中。
也就是说，去运用数学知识去讨论问题的本身，把问题能够描述清楚了。
这样解决过程就显得很直接，作为对思维的表达，而不是反过来专注表述本身的意义。
关于副作用，为视为函数式语言的特征，使得状态的改变变得复杂。
不过同时，状态在迭代与递归过程中的变化，又是可以利用的东西。
Scheme在这些方面没有什么限制，而且让仍一种范式都很方便。
而且因为是考虑思维上面的东西，用C/C++/Java来重写并是困难的事情。
使用Scheme只是让人的关注点牵引到某些容易忽视的本质，
而对于这种本质的表达却是可以使用更具体的更方便目的的工具上的。

关于Scheme的资料，还可以参考一下内容：
Scheme - Wikipedia
[[http://en.wikipedia.org/wiki/Scheme_(programming_language)]]
Yet Another Scheme Tutorial
[[http://www.shido.info/lisp/idx_scm_e.html]]
Teach Yourself Scheme in Fixnum Days
[[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html]]
schemers.org
[[http://www.schemers.org/]]
CLiki
[[http://www.cliki.net/]]
CMU Artificial Intelligence Repository
[[http://www.cs.cmu.edu/Groups/AI/0.html]]
The SLIB Portable Scheme Library
[[http://people.csail.mit.edu/jaffer/SLIB.html]]
这上面有一些是教程，一些是索引，一些是代码。
这些可以作为查阅的参考，或者寻找参考的出发点。
实体书方面的学校里有一些老的书籍，比较偏实例，不多。

下面来说实现方面的，说些自己在意到的实现：
TinyScheme可作用于嵌入式，一点完整的语言子集，Gimp就在用它。
Scm这是和Slib结合最好的一个实现，优点是Slib是纯Scheme代码的
Kawa是一个Java环境下的Scheme嵌入工具。
MIT Scheme这是Sicp的书配环境，某种意义上是很重要的参考。
Plt-scheme教学为目的的，很集成，实用的文档和功能组件丰富。
Sisc一个很完整的Java实现，实现了很多的东西
Gambit可以编译执行，性能有优势，可加入C语句一起编译。
还有个浏览器js的在bluishcoder.co.nz/jsscheme/
这里无法多列举以及适用的场合，以及如何用自己的小实现。
现在Plt-scheme改名Racket了，适合学习，不过可变类型和R5RS不一致。
关于标准方面有R5RS，和R4RS兼容，虽然各实现有区别，但不会和它冲突。
还有R6RS提出了很多有用的想法，这些想法在各实现中均有表达。
比如错误处理，包管理，结构什么的，还有未涉及网络和线程方面的特性。
SRFIs是作为一个可参考的标准或者作为库存在的，也可以用。
个人一般在意各实现在数学类型和对连续的支持上的程度，以及用途。
不过其实自己其实也很偏向Python实现，因为库多。

关于Scheme的编辑器，自己的要求是有有括号匹配就行。
通常出于演示目的所写出的代码不会组合层次太复杂。
要严格注意要缩进，左括号对应好右括号，这个可以通过缩进和断行的帮助。
右括号数量够后写一行就行，行尾一串右括号不必多少顾虑。

接下来一个写编写实现以及99个小问题。


* 数学方面

在话题中Scheme是工具，是关注的出发点，但是也需要其他方面的东西。
所以在Scheme Toy的后半部就开始想从SICP说到以外的内容了。
关于各实现的网络或线程或一定会用到的扩展库什么的是不一定非要说的了。
因为这些内容在用别的语言时，是也会接触到的一些东西，不作为重点。
于是下面的内容还是以一些手头的书籍为参考了，这里参考到的有：
离散数学 Discreted Mathematics @ Richard Johnsonbaugh
算法算法手册Algorithms in a nutshell @ George T. Heineman
数学建模与数学实验 @ 赵静, 但琦
《------------------------------附一下目录会比较好------------
这里仅仅是可以参照，所以在此文之外有很多有价值的东西可读的。


是想说数学方面的，所以话题会不仅限于这几本书涉及的方面，
不过有个内容的出发点还是有必要的，虽然说查阅的让人很难受。
总的来说，查阅的方式，对于基础知识来说，不是很适合的了解方式。
还是来列举一些这里涉及的话题吧，都是自己还不够深入的东西：
离散数学、数据结构、算法分析、数值计算、数学建模、线性规划
暂时就仅仅了列了下关键字，因为内容说起来很缺少自信的感觉
还有算法导论和计算机艺术都还怀有敬畏之心，不做说明。
不过这里总在所数学模型，在作为思路展现，没有细入。

这里真的有很多值得写的东西，真的，这行是占位用的。

看起来这篇是说Scheme，其实这里才是重点的。


* 算法复用

这里的复用有三个方面，一是思维的复用，二是模型的复用，三是库的复用。
按照重要定排列，思维的复用是最重要，它是对模型模型运用的根本。
模型也很重要，它是对思维的表达和运用，同时也是对现实的抽象。
然后来说库的复用，它不是作为这里的重点，不过是很实用的东西。

模型的话，算是很有用的东西，这里是指的一些数学模型。
比如说在上一节里用的很简单的例子就是集合论以及图论方面的一些模型。
这一节的下面来说库的复用方面的东西，文档形式也算。

Dictionary of Algorithms and Data Structures
http://www.nist.gov/dads/
算法与数据结构词典

Data Structures and Algorithms with Object-Oriented Design Patterns
http://www.brpreiss.com/
一个五种语言来写同样问题的书籍系列

C++中的算法复用主要体现在模板与泛型方面的部分
首先是STL，属于C++标准
http://www.sgi.com/tech/stl/
http://www.cplusplus.com/reference/stl/
包含各种Containers容器Algorithms算法，以及一些使用函数。
此外Boost中还有一些，比如
http://www.boost.org/doc/libs/release/libs/graph/doc/table_of_contents.html
就是Boost Graph Library描述了一些图方面的哦算法

Java的情况和C++有点类似，作为语言机制上来说算法复用是有必要的。
PHP也有类似的库存在，还有其他一些语言平台的情况也差不多。

Python是个发展活跃的语言，虽然库设计不如Java精致，但很易用。
其自带的List/Dict类型可以做很多用途，外加for的语句和生成器。
在文档的Data Types和Numeric and Mathematical Modules两节是相关的库。
第三方库的话Graph方面参考
http://wiki.python.org/moin/PythonGraphApi
并有NetworkX这样抽象为库的存在http://networkx.lanl.gov/

在Haskell的Wiki上有关于纯函数语言的资料，而ML/Ocaml也和Scheme更像一点。
Common Lisp晚于Scheme，标准化了很多必要的部件。
CLOS是个很特别的设计，也有很多其他的亮点的东西存在。
Emacs Lisp用于嵌入，居然没词法定界用不了词法闭包，但执行命令是够了。
不过三者表达循环的方式都不相同，相同有不同的东西有点让人困惑。
而算上Maxima就又创在了一种特别的东西了，再算Dylan呢。
还是暂且把它们当作长得有点像的不同的东西看待吧，但都值得参考。
再说就是Lisp本身，除了S表达式，还有M表达式和I表达式可用。

最后来说Scheme，自身可以直观的表达算法，一般基于代码复用。
有Maxima包含了很多东西，是Common Lisp之上的东西，可参考。
线性规划和图论方面的东西都有，最为一个DSL的库存在。
[[http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/edu/tut/0.html]]

怎么觉得还有很多不重要的闲散的存在可以滥说说呢。
比如说关于FP有很多Paper来着。


* 代码展示

这篇没有这部分了


* 补充说明

这次换行太多，自己已经不习惯。
而且所写缺乏内容，对此深表歉意。
东西要写给别人看，这我还没有做到。


* 总结

关于Lambda和Scheme可看
http://en.wikipedia.org/wiki/Lambda_calculus
http://library.readscheme.org/page1.html