Cqxq编程空间

搜集各种计算机语言的资料。还有一些古老的计算机语言的资料!

2008年1月11日 星期五

古老的语言

1011011000000000,让计算机进行一次加法
1011010100000000,让计算机进行一次减法

标签:

2008年1月6日 星期日

微软的F#

F#,微软研究院正在研究的一种函数式程序设计语言。其灵感来自于 OCaml。其突出的优势是,与visual Studio 2005 紧密整合。F# 可以与.net 平台的其它语言例如C#,VB.net 相互调用操作。想了解更多关于F#,可以访问如下内容:

Home of F# at Microsoft Research: http://research.microsoft.com/fsharp

Don Syme's Blog: http://blogs.msdn.com/dsyme

Community site for F#: http://cs.hubfs.net

关于 函数试程序设计语言:

1) 函数式程序设计是一种强调表达式赋值而不是执行命令的程序设计。Erlang程序设计语言就是一种函数式程序设计语言。由于改变程序中某部分的全局变量可能对程序其它某部分有意想不到的影响,Erlang避免了对在多个函数中常用的全局变量的使用。  

2) 在ITU-TS较早的定义中,函数式程序设计是“主要以可能嵌套的函数过程调用的顺序来构造程序的一种方法。”函数过程是指相关的简单程序,它被其它程序调用,并且从调用它的程序中获得且返还数值。

标签:

2008年1月4日 星期五

改变自己编程中的思维方法(作者:ZZ)

我是从学习Java编程开始接触OOP(面向对象编程),刚开始使用Java编写程序的时候感觉很别扭,因为我早以习惯用C来编写程序,很欣赏C的简洁性 和高效性,喜欢C简练而表达能力丰富的风格,特别忍受不了Java运行起来慢吞吞的速度,相对冗长的代码,而且一个很简单的事情,要写好多类,一个类调用 一个类,心里的抵触情绪很强。

我对Java的面向对象的特性琢磨良久,自认为有所领悟,也开始有意识的运用OOP风格来写程序,然而还是经常会觉得不知道应该怎样提炼类,面对一个具体的问题的时候,会觉得脑子里千头万绪的,不知道怎么下手,一不小心,又会回到原来的思路上去。

举个例子,要发广告邮件,广告邮件列表存在数据库里面。倘若用C来写的话,一般会这样思考,先把邮件内容读入,然后连接数据库,循环取邮件地址,调用本机的qmail的sendmail命令发送。

然后考虑用Java来实现,既然是OOP,就不能什么代码都塞到main过程里面,于是就设计了三个类:

一个类是负责读取数据库,取邮件地址,调用qmail的sendmail命令发送;
一个类是读邮件内容,MIME编码成HTML格式的,再加上邮件头;
一个主类负责从命令读参数,处理命令行参数,调用发email的类。

把一件工作按照功能划分为3个模块分别处理,每个类完成一件模块任务。

仔 细的分析一下,就会发现这样的设计完全是从程序员实现程序功能的角度来设计的,或者说,设计类的时候,是自低向上的,从机器的角度到现实世界的角度来分析 问题的。因此在设计的时候,就已经把程序编程实现的细节都考虑进去了,企图从底层实现程序这样的出发点来达到满足现实世界的软件需求的目标。

这样的分析方法其实是不适用于Java这样面向对象的编程语言,因为,如果改用C语言,封装两个C函数,都会比Java实现起来轻松的多,逻辑上也清楚的多。

我觉得面向对象的精髓在于考虑问题的思路是从现实世界的人类思维习惯出发的,只要领会了这一点,就领会了面向对象的思维方法。

举一个非常简单的例子:假使现在需要写一个网页计数器,客户访问一次页面,网页计数器加1,计数器是这样来访问的

http://hostname/count.cgi?id=xxx

后台有一个数据库表,保存每个id(一个id对应一个被统计访问次数的页面)的计数器当前值,请求页面一次,对应id的计数器的字段加1(这里我们忽略并发更新数据库表,出现的表锁定的问题)。

如果按照一般从程序实现的角度来分析,我们会这样考虑:首先是从HTTP GET请求取到id,然后按照id查数据库表,获得某id对应的访问计数值,然后加1,更新数据库,最后向页面显示访问计数。

现在假设一个没有程序设计经验的人,他会怎样来思考这个问题的呢?他会提出什么样的需求呢?他很可能会这样想:

我需要有一个计数器,这个计数器应该有这样的功能,刷新一次页面,访问量就会加1,另外最好还有一个计数器清0的功能,当然计数器如果有一个可以设为任意值的功能的话,我就可以作弊了。

做为一个没有程序设计经验的人来说,他完全不会想到对数据库应该如何操作,对于HTTP变量该如何传递,他考虑问题的角度就是我有什么需求,我的业务逻辑是什么,软件应该有什么功能。

按照这样的思路(请注意,他的思路其实就是我们平时在生活中习惯的思维方式),我们知道需要有一个计数器类 Counter,有一个必须的和两个可选的方法:

getCount() // 取计数器值方法
resetCounter() // 计数器清0方法
setCount() // 设计数器为相应的值方法

把Counter类完整的定义如下:

public class Counter {
public int getCount(int id) {}
public void resetCounter(int id) {}
public void setCount(int id, int currentCount) {}
}

解决问题的框架已经有了,来看一下如何使用Counter。 在count.cgi里面调用Counter来计数,程序片断如下:

// 这里从HTTP环境里面取id值
...
Counter myCounter = new Counter(); // 获得计数器
int currentCount = myCounter.getCount(id); // 从计数器中取计数
// 这里向客户浏览器输出
...

程序的框架全都写好了,剩下的就是实现Counter类方法里面具体的代码了,此时才去考虑具体的程序语言实现的细节,比如,在getCount()方法里面访问数据库,更新计数值。

从上面的例子中看到,面向对象的思维方法其实就是我们在现实生活中习惯的思维方式,是从人类考虑问题的角度出发,把人类解决问题的思维方式逐步翻译成程序能够理解的思维方式的过程,在这个翻译的过程中,软件也就逐步被设计好了。

在运用面向对象的思维方法进行软件设计的过程中,最容易犯的错误就是开始分析的时候,就想到了程序代码实现的细节,因此封装的类完全是基于程序实现逻辑,而不是基于解决问题的业务逻辑。

学习JDBC编程的经典错误问法是:“我怎样封装对数据库的select操作?”

面向对象的设计是基于解决业务问题的设计,而不是基于具体编程技术的设计。我不会去封装select语句的,我只封装解决问题的业务逻辑,对数据库的读取是在业务逻辑的编码实现阶段才去考虑的问题。

回过头看上面那个发广告邮件的例子,应该如何应用面向对象的思维方法呢?

对于一个邮件来说,有邮件头,邮件体,和邮件地址这三个属性,发送邮件,需要一个发送的方法,另外还需要一个能把所有邮件地址列出来的方法。所以应该如下设计:

类JunkMail

属性:
head
body
address
方法:
sendMail() // 发送邮件
listAllMail() // 列邮件地址

用Java来表示:

public class JunkMail {
private String head;
private String body;
private String address;
public JunkMain() { // 默认的类构造器
// 从外部配置文件读邮件头和邮件体
this.head=...;
this.body=...;
}

public static boolean sendMail(String address) {
// 调用qmail,发送email
}

public static Collection listAllMail() {
// 访问数据库,返回一个邮件地址集合
}
}

当把JunkMail设计好了以后,再调用JunkMail类完成邮件的发送,将是非常轻松的事情。

如果说传统的面向过程的编程是符合机器运行指令的流程的话,那么面向对象的思维方法就是符合现实生活中人类解决问题的思维过程。

在面向对象的软件分析和设计的时候,要提醒自己,不要一上来就去想程序代码的实现,应该抛开具体编程语言的束缚,集中精力分析我们要实现的软件的业务逻辑,分析软件的业务流程,思考应该如何去描述和实现软件的业务。毕竟软件只是一个载体,业务才是我们真正要实现的目标。

但是在设计过程中,心里却往往在担心,如果我完全不去考虑程序代码的实现的话,那么我怎么知道我的设计一定合理呢?我怎么知道我设计的类、接口一定可以实现呢?所以经常可以看到的现象就是:

在设计过程中,虽然知道不能过早考虑代码实现,但是每设计一个类,一个接口,心里都要不知不觉的用自己熟悉的编程语言大概的评估一下,看看能否编出来,因此,一不小心,就会又回到按照程序功能实现的思路进行设计的老路上去了。

举 个例子来说明,在做Web程序设计的时候,经常要遇到分页显示数据的情况。比如说需要把系统中所有的用户都列出来这样的功能。假设使用User类来表示用 户,增加用户addUser(),删除用户deleteUser(),查询所有用户listUsers()方法。而数据库中有一个user表,一条记录是 一个用户的信息。下面考虑一下User类的方法的实现:

addUser()和deleteUser()方法都好实现,就是对数据库增加记录和删除记录。对于listUsers()方法,其实就是对user表的select,取出一个记录集。但是该怎么从listUsers()方法中得到所有用户的列表呢?

一 个方法调用的返回值只有一个,没有多个,所以很多情况下采用的办法就是返回值定义为集合类型,比如Vector。这样就可以在listUsers()方法 的具体代码实现的时候,从数据库依次取出一个个记录,插入到Vector里面来。在主程序里面,调用listUsers()方法可以返回一个 Vector,然后再对Vector遍历操作,就可以得到用户列表了。

public class User {

public static void addUser(...) {
// 数据库insert一条记录
}

public static void deleteUser(...) {
// 数据库delete一条记录
}

public Vector listUsers(...) {
// 数据库select结果放到一个集合里面
}
}

这 样的设计基本合理,但是仍然有点小问题。因为在设计的时候,就考虑到了用Java的集合类Vector来实现对不定长数据集的存放,因而违反了面向对象设 计的一个原则:在设计的时候不应过早的考虑具体程序语言的实现。所以必须用抽象的方法,和具体实现无关的方法来表达业务逻辑。

我们知道,通常对具有集合特征的数据结构进行遍历通常可以使用next和hasNext方法,next实现取下一个用户,hasNext判断是否还有元素。 因此我们定义一个接口Iterator,这个接口中定义两个方法next和hasNext:

public interface Iterator {
public boolean hasNext() {}
public Object next() {}
}

而User类的listUses方法返回值改为Iterator接口的实现类:

public class User {
...
public Iterator listUsers() {
}
...
}

这 样就把User类的设计和具体的实现方法分离开了,因为此时任何实现了next()和hasNext()方法的类都可以做为listUsers的返回值, 都可以被用来表达“用户列表”,而不仅仅可以使用Vector而已。比如,我可以用ArrayList来表达用户列表,因为ArrayList也实现了 Iterator,当然我也可以自己专门写一个类来存放用户列表,只要实现next()和hasNext()方法就行了。

这样在具体的编写代码的时候,程序员具有了最大的灵活性,可以根据具体的情况,采用不同的编程方法来存放用户列表。特别是降低了程序的耦合度,提高了程序的可移植性。对于上面那个JunkMail的listAllMail()方法也同样应该改为接口类型。

然后,在主程序里面就这样来使用User类的listUsers方法:

User myUser = new User();
Iterator iterator = myUser.listUsers();
while (iterator.hasNext()) {
iterator.next();
}

这样就可以完全不用考虑程序代码实现了,从高层次上把功能抽象出来,定义成为接口,同时又可以把系统设计的很合理,完全根据业务的需求来进行设计。

结语

通 过上面的几个例子的设计说明,使用面向对象的思维方法,其实是一个把业务逻辑从具体的编程技术当中抽象出来的过程,而这个抽象的过程是自上而下的,非常符 合人类的思维习惯,也就是先不考虑问题解决的细节,把问题的最主要的方面抽象成为一个简单的框架,集中精力思考如何解决主要矛盾,然后在解决问题的过程 中,再把问题的细节分割成一个一个小问题,再专门去解决细节问题。

因而一旦牢牢的抓住了这一点,你就会发现在软件设计和开发过程中,你自己总是会不知不觉的运用面向对象的思维方法来设计和编写程序,并且程序的设计和开发也变得不再那么枯燥,而一个合理运用面向对象技术进行设计和架构的软件,更是具备了思维的艺术美感。

标签:

2008年1月1日 星期二

Spring 编程入门十大问题解答

1、如何学习Spring?

  你可以通过下列途径学习spring:

  (1) spring下载包中doc目录下的MVC-step-by-step和sample目录下的例子都是比较好的spring开发的例子。

   (2) AppFuse集成了目前最流行的几个开源轻量级框架或者工具 Ant,XDoclet,Spring,Hibernate(iBATIS),JUnit,Cactus,StrutsTestCase,Canoo's WebTest,Struts Menu,Display Tag Library,OSCache,JSTL,Struts 。

  你可以通过AppFuse源代码来学习spring。

AppFuse网站:http://raibledesigns.com/wiki/Wiki.jsp?page=AppFuse

  (3)Spring 开发指南(夏昕)(http://www.xiaxin.net/Spring_Dev_Guide.rar)

  一本spring的入门书籍,里面介绍了反转控制和依赖注射的概念,以及spring的bean管理,spring的MVC,spring和hibernte,iBatis的结合。

  (4) spring学习的中文论坛

  SpringFramework中文论坛(http://spring.jactiongroup.net)

  Java视线论坛(http://forum.javaeye.com)的spring栏目

  2、利用Spring框架编程,console打印出log4j:WARN Please initialize the log4j system properly?

  说明你的log4j.properties没有配置。请把log4j.properties放到工程的classpath中,eclipse的classpath为bin目录,由于编译后src目录下的文件会拷贝到bin目录下,所以你可以把log4j.properties放到src目录下。

  这里给出一个log4j.properties的例子:

log4j.rootLogger=DEBUG,stdout
log4j.appender.stdout=org.apache.log4j.ConsoleAppender
log4j.appender.stdout.layout=org.apache.log4j.PatternLayout
log4j.appender.stdout.layout.ConversionPattern=%d %5p (%F:%L) - %m%n

  3、出现 java.lang.NoClassDefFoundError?

  一般情况下是由于你没有把必要的jar包放到lib中。

  比如你要采用spring和hibernate(带事务支持的话),你除了spring.jar外还需要hibernat.jar、aopalliance.jar、cglig.jar、jakarta-commons下的几个jar包。

http://www.springframework.org/download.html下载spring开发包,提供两种zip包
spring -framework-1.1.3-with-dependencies.zip和spring-framework-1.1.3.zip,我建议你下载 spring-framework-1.1.3-with-dependencies.zip。这个zip解压缩后比后者多一个lib目录,其中有 hibernate、j2ee、dom4j、aopalliance、jakarta-commons等常用包。

  4、java.io.FileNotFoundException: Could not open class path resource [....hbm.xml],提示找不到xml文件?

  原因一般有两个:

  (1)该xml文件没有在classpath中。

  (2)applicationContext-hibernate.xml中的xml名字没有带包名。比如:

<bean id="sessionFactory" class="org.springframework.orm.hibernate.LocalSessionFactoryBean">
<property name="dataSource"><ref bean="dataSource"/></property>
<property name="mappingResources">
 <list>
  <value>User.hbm.xml</value>
  错,改为:
  <value>com/yz/spring/domain/User.hbm.xml</value>
 </list>
</property>
<property name="hibernateProperties">
<props>
 <prop key="hibernate.dialect"> net.sf.hibernate.dialect.MySQLDialect </prop>
 <prop key="hibernate.show_sql">true</prop>
</props>
</property>
</bean>

  5、org.springframework.beans.NotWritablePropertyException: Invalid property 'postDao' of bean class?

  出现异常的原因是在application-xxx.xml中property name的错误。

  <property name="...."> 中name的名字是与bean的set方法相关的,而且要注意大小写。

  比如

public class PostManageImpl extends BaseManage implements PostManage {
 private PostDAO dao = null;
 public void setPostDAO(PostDAO postDAO){
  this.dao = postDAO;
 }
}

  那么xml的定义应该是:

<bean id="postManage" parent="txProxyTemplate">
<property name="target">
 <bean class="com.yz.spring.service.implement.PostManageImpl">
  <property name="postDAO"><ref bean="postDAO"/></property> 对
  <property name="dao"><ref bean="postDAO"/></property> 错
 </bean>
</property>
</bean>

  6、Spring中如何实现事务管理?

  首先,如果使用mysql,确定mysql为InnoDB类型。

  事务管理的控制应该放到商业逻辑层。你可以写个处理商业逻辑的JavaBean,在该JavaBean中调用DAO,然后把该Bean的方法纳入spring的事务管理。

  比如:xml文件定义如下:

<bean id="txProxyTemplate" abstract="true"
class="org.springframework.transaction.interceptor.TransactionProxyFactoryBean">
<property name="transactionManager"><ref bean="transactionManager"/></property>
<property name="transactionAttributes">
<props>
<prop key="save*">PROPAGATION_REQUIRED</prop>
<prop key="remove*">PROPAGATION_REQUIRED</prop>
<prop key="*">PROPAGATION_REQUIRED</prop>
</props>
</property>
</bean>

<bean id="userManage" parent="txProxyTemplate">
 <property name="target">
  <bean class="com.yz.spring.service.implement.UserManageImpl">
   <property name="userDAO"><ref bean="userDAO"/></property>
  </bean>
 </property>
</bean>

  com.yz.spring.service.implement.UserManageImpl就是我们的实现商业逻辑的JavaBean。我们通过parent元素声明其事务支持。

  7、如何管理Spring框架下更多的JavaBean?

  JavaBean越多,spring配置文件就越大,这样不易维护。为了使配置清晰,我们可以将JavaBean分类管理,放在不同的配置文件中。 应用启动时将所有的xml同时加载。

  比如:

   DAO层的JavaBean放到applicationContext-hibernate.xml中,商业逻辑层的JavaBean放到 applicationContext-service.xml中。然后启动类中调用以下代码载入所有的ApplicationContext。

String[] paths = {"com/yz/spring/dao/hibernate/applicationContext-hibernate.xml",
"com/yz/spring/service/applicationContext-service.xml"};
ctx = new ClassPathXmlApplicationContext(paths);

  8、web应用中如何加载ApplicationContext?

  可以通过定义web.xml,由web容器自动加载。

<servlet>
<servlet-name>context</servlet-name>
<servlet-class>org.springframework.web.context.ContextLoaderServlet</servlet-class>
<load-on-startup>1</load-on-startup>
</servlet>

<context-param>
<param-name>contextConfigLocation</param-name>
<param-value>/WEB-INF/applicationContext-hibernate.xml</param-value>
<param-value>/WEB-INF/applicationContext-service.xml</param-value>
</context-param>

  9、在spring中如何配置的log4j?

  在web.xml中加入以下代码即可。

<context-param>
<param-name>log4jConfigLocation</param-name>
<param-value>/WEB-INF/log4j.properties</param-value>
</context-param>

  10、Spring框架入门的编程问题解决了,我该如何更深地领会Spring框架呢?

  这两本书你该去看看。这两本书是由Spring的作者Rod Johnson编写的。

Expert One on one J2EE Design and Development
Expert One on one J2EE Development Without EJB

  你也该看看martinfowler的Inversion of Control Containers and the Dependency Injection pattern。

http://www.martinfowler.com/articles/injection.html
 
  再好好研读一下spring的文档。

http://www.jactiongroup.net/reference/html/index.html(中文版,未全部翻译)

  还有就是多实践吧。

标签:

技术趋势:Functional Pogramming函数编程风云再起

甫于日前落幕的Software Development 2.0研讨会,来宾之一的Andrei Alexandrescu被问到未来编程语言的趋势时,他认为函数编程(Functional Pogramming)可能会再度兴起。我认同他的看法,我过去发表的JavaFX文章中,碰巧也有提到这一点。

目前两大开发平台(Java.NET)都开始出现函数编程思维的踪迹。Java平台的JavaFX语言,具备所有重要函数编程的特色,所以应该归类为函数语言(或者至少是多重思维语言);.NET平台的C# 3.0也存在相当多函数编程的影子。微软的LINQ本来就源自于函数语言,更不用提微软官方的F#语言,F#沿用相当多ML语言的语法,更是彻底的函数语言(其中的F,应该是Functional的意思)。

根据Tiobe对于200712月语言需求所做的统计,面向对象语言占54.4%,程序语言(Procedure Language)占41.9%,函数语言占2.0%,而逻辑语言占1.8%。以上加起来刚好百分之百。

但是,这样的分类并不精确。现在的语言很少是单一思维,几乎都是多重思维(Multi-paradigm),特别是面向对象和函数编程,因为两者间并没有冲突的地方,许多面向对象语言会渐渐纳入函数编程的特色。例如,尽管C# 3.0具有相当多函数语言的特色,但是依然会被Tiobe归类于面向对象语言的类别。

函数编程最重要的基础是Lambda Calculus,在C# 3.0称为「Lambda表示式」,在Python称为「Lambda函数」,在PowerShell称为Scriptblock(剧本区块),在Java称为匿名方法(Anonymous Method),不同语言会用不同名词称呼它,但其实都是类似的东西。从这个角度来看,许多主流语言多少都具备函数编程的能力。这个趋势应该会延续下去,许多既有语言推出新版本时,会持续加入函数语言的特色。

另外,我最喜欢的REBOL,许多人工智能专家使用的Common Lisp,近年兴起的ErlangPerl高手唐凤专精的Haskell,这些也都是函数语言。为什么我们喜欢函数编程?因为函数编程可以让我们把时间花在有生产力的事情上,而不是处理许多琐碎的事。简单地说,函数语言可以让我们用简单的方式写程序,但是威力又强大。

编程语言专家Ravi Sethi教授认为「简单」与「威力」,正是函数编程的两大优势。简单,来自于以「值」(Value)为中心,不用理会下面平台是什么机器、内存要如何配置、如何指定。函数编程的威力,则来自于「递归」以及将函数视为「First-class」(一等)的值(函数本身就是值,可以被传递、被指定)。

自动内存管理虽然始于函数语言,但是近年来已经进入各大主流语言。而将函数视为一等的数据型别,也开始进入各大主流语言。这些都要归功于函数语言,尤其是Lisp

Lisp
是函数语言的始祖,诞生于1958年,相当于50年前。换算成人类年龄的话,Lisp已经算是程序语言中的人瑞了。Lisp的后继者众多,其中,至今仍然最活跃的是诞生于1980年代的Common Lisp,它在Tiobe的排名是第十七名。在Peter Seibel写出《Practical Common Lisp》一书,并得到Jolt Award之后,让大家逐渐对Common Lisp一改印象,开始认为它不只是学术上的语言,而是一种务实的语言。

一般来说,相较于CPascal这类命令式编程(Imperative Programming),函数编程的缺点是效率比较差,这也是函数语言一直无法流行的主因之一。不过,随着处理器速度的提升,编译程序技术的进步,都让效率不再是问题,甚至在数学运算上,用CleanOCaml(这些都是函数语言)开发出来的程序,效率也不会比C差。

尤其是在多核心处理器和分布式计算时代,函数编程更是比Imperative编程具有更强的优势。例如近年来逐渐受到重视的Erlang,正是将重点放在Concurrency与容错上。用Erlang可以轻松开发出来的系统,如果改用别种语言开发,可能会造成程序长度暴增以及不稳定的情况。

如果你想学习函数编程,而且如果你使用.NET平台,我会建议你使用F#;如果你使用Java平台,你可以考虑JavaFX;如果你没有Java.NET平台考虑的话,那么你可以选择Common LispErlang

若未曾使用过函数编程技术,思维就会受到传统Imperative编程作法的拉扯,一开始时会很不习惯,但只要坚持下去,等到跨过门坎之后,函数编程其实更自然,生产力更高

标签:

学会开放性的思维 xpiloveyou(原作)

经常在论坛中看到一些问题:“我应该学习哪门语言?”“XX语言能做什么吗?”我对想对这类想法给一个我的见解。本文多少涉及到一些语言的评论,仅代表个人意见。

学会开放性的思维

我发现初学者最喜欢问的一个问题就是“我应该学什么语言?”。想不浪费时间学好一门语言然后就用这个语言解决所有问题。在提出我的见解前我先引用一段Eric Raymond的话:

如果你还不会任何计算机语言,我建议你从Python开始。它设计清晰,文档齐全,对初学者很合适。尽管是一门很好的初级语言,它不仅仅只是个玩具。它非常强大,灵活,也适合做大型项目。
但 是记住,如果你只会一门语言,你将不会达到黑客所要求的技术水平,甚至也不能达到一个普通程序员的水平---你需要学会如何以一个通用的方法思考编程问 题,独立于任何语言。要做一名真正的黑客,你需要学会如何在几天内通过一些手册,结合你现在所知,迅速掌握一门新语言。这意味着你应该学会几种不同的语 言。如果要做一些重要的编程,你将不得不学习C语言,Unix的核心语言。其他对黑客而言比较重要的语言包括Perl和LISP。 Perl很实用,值得 一学;它被广泛用于活动网页和系统管理,因此即便你从不用Perl写程序,至少也应该能读懂它。 LISP 值得学习是因为当你最终掌握了它你会得到丰富 的经验;这些经验使你在以后的日子里成为一个更好的程序员,即使你实际上可能很少使用LISP本身。当然,实际上你最好四种都会。 (Python, C, Perl, and LISP). 除了是最重要的四种基本语言,它们还代表了四种非常不同的编程方法,每种都会让你受益非浅。

大 家看了这段话是否立刻就想按Eric Raymond的话从Pyton开始学习?或者学习他提出的四种中的C语言?且慢,我们注意这样几句话:“你需要学 会如何以一个通用的方法思考编程问题,独立于任何语言。”“(Python, C, Perl, and LISP). 除了是最重要的四种基本语言,它 们还代表了四种非常不同的编程方法,每种都会让你受益非浅。” 可以看出Eric Raymond提出四种语言实际是提出四种不同的编程思想。他想告诉大 家的就是:开放的思维,不要局限在一个语言当中,即“通用的方法思考编程问题”。


也 许有人反对说精通一门比懂很多而不精要好。确实我们必须精通一门,这个是可以根据自己需要来选择的。但不代表我们只需要学习一门语言,因为只懂一门语言很 容易被它的局限性限制。C语言很灵活但是对数据的抽象处理不够。C++够强大也灵活了吧?它学习了C的灵活和高效以及Simula的抽象数据能力。可是C ++的面向对象机制比不上Java。而当你学了Lisp以后你会发现原来程序还可以这样编,虽然C++也号称可扩展性,但Lisp的扩展性是C++所不能 及的。而且Lisp是一种函数型语言,与面向机器的语言有着不同的思维方式,Java也从这里借用了不少思想。我觉得每一个语言都有最擅长的领域和不够的 地方。没有一种语言真正通用,即使是C++,有些问题用C++来做实在有点吃力。这里一定有人有对C++痛苦的回忆。Java确实很优秀,适合分布式计 算,但Java太安全了,可能不少有黑客气质的不喜欢它,因为它为了安全牺牲了很多灵活性。

我 们应该学会开放性思维,看问题要看到最核心的问题,最根本的根本,而不会被其他的枝叶或表象所迷惑,做到这一步后才算比较成功。这样就会有一种分析问题的 方法,学会怎么样把问题的表象剖开,看到它的本质。这时你碰到任何具体的问题,只要给点时间,都能轻而易举地解决。选择程序设计语言在这里只是选择不同工 具。

并不是说工具不重要,但是如果没有一个很好的思想,那么这个工具你能用的好吗?而且解 决一个问题并不是只有一种可能,或者这个问题的解决可能分几个部分而不同部分要不同的方法。这个时候没有开放性的思维,能解决好这个问题吗?就以 Emacs为例。Emacs的底层代码是C写的而上层代码却是Lisp。也因此Emacs足够强大快速而且又有很强的可扩展性。如果仅采用单一的C编写, 那么就是vi了。它很快也很灵活,但它扩展性怎么样?

看到一些关于该选择什么语言的问题我 觉得真可笑,不知道他们想的是学语言还是学着解决问题。我们学习编程只是为了学习写程序本身还是为了学会用编程解决问题呢?如果是前者,真好你是个历史学 家,尤其是只用C和汇编的可以称为考古学家了。如果是后者,那么不必再问选择什么语言了,学会编程的思想最重要,选择一门语言然后学习它的思维方式。这时 先选哪门就和应该上午吃苹果还是下午吃橘子一样了,你应该熟悉更多的工具。

补充一些就是独 立于程序语言以外的编程思想,那就是算法,数据结构,和编码规范。不论你精通多少门语言,当遇到一个问题能否用最快最好的方法解决,那就是考验你的算法设 计能力和数据结构的操作能力了。而用程序清晰的表述一个问题就是看你编码是否规范了。当你需要改进程序时你会发现一个编写清晰易读的程序维护起来要方便的 多,这也有助于快速的解决问题

标签:

LISP之根源(作者:保罗格雷厄姆)

约翰麦卡锡于1960年发表了一篇非凡的论文,他在这篇论文中对编程的贡献有如 欧几里德对几何的贡献.1 他向我们展示了,在只给定几个简单的操作符和一个 表示函数的记号的基础上, 如何构造出一个完整的编程语言. 麦卡锡称这种语 言为Lisp, 意为List Processing, 因为他的主要思想之一是用一种简单的数据 结构表(list)来代表代码和数据.

值得注意的是,麦卡锡所作的发现,不仅是计算机史上划时代的大事, 而且是一种 在我们这个时代编程越来越趋向的模式.我认为目前为止只有两种真正干净利落, 始终如一的编程模式:C语言模式和Lisp语言模式.此二者就象两座高地, 在它们 中间是尤如沼泽的低地.随着计算机变得越来越强大,新开发的语言一直在坚定地 趋向于Lisp模式. 二十年来,开发新编程语言的一个流行的秘决是,取C语言的计 算模式,逐渐地往上加Lisp模式的特性,例如运行时类型和无用单元收集.

在这篇文章中我尽可能用最简单的术语来解释约翰麦卡锡所做的发现. 关键是我 们不仅要学习某个人四十年前得出的有趣理论结果, 而且展示编程语言的发展方 向. Lisp的不同寻常之处--也就是它优质的定义--是它能够自己来编写自己. 为了理解约翰麦卡锡所表述的这个特点,我们将追溯他的步伐,并将他的数学标记 转换成能够运行的Common Lisp代码.

七个原始操作符

开始我们先定义表达式.表达式或是一个原子(atom),它是一个字母序列(如 foo),或是一个由零个或多个表达式组成的(list), 表达式之间用空格分开, 放入一对括号中. 以下是一些表达式:

foo
()
(foo)
(foo bar)
(a b (c) d)
最后一个表达式是由四个元素组成的表, 第三个元素本身是由一个元素组成的表.

在算术中表达式 1 + 1 得出值2. 正确的Lisp表达式也有值. 如果表达式e得出 值v,我们说e返回v. 下一步我们将定义几种表达式以及它们的返回值.

如果一个表达式是表,我们称第一个元素为操作符,其余的元素为自变量.我们将 定义七个原始(从公理的意义上说)操作符: quote,atom,eq,car,cdr,cons,和 cond.

  1. (quote x) 返回x.为了可读性我们把(quote x)简记 为'x.

    > (quote a)
    a
    > 'a
    a
    > (quote (a b c))
    (a b c)

  2. (atom x)返回原子t如果x的值是一个原子或是空表,否则返回(). 在Lisp中我们 按惯例用原子t表示真, 而用空表表示假.

    > (atom 'a)
    t
    > (atom '(a b c))
    ()
    > (atom '())
    t

    既然有了一个自变量需要求值的操作符, 我们可以看一下quote的作用. 通过引 用(quote)一个表,我们避免它被求值. 一个未被引用的表作为自变量传给象 atom这样的操作符将被视为代码:

    > (atom (atom 'a))
    t

    反之一个被引用的表仅被视为表, 在此例中就是有两个元素的表:

    > (atom '(atom 'a))
    ()

    这与我们在英语中使用引号的方式一致. Cambridge(剑桥)是一个位于麻萨诸塞 州有90000人口的城镇. 而``Cambridge''是一个由9个字母组成的单词.

    引用看上去可能有点奇怪因为极少有其它语言有类似的概念. 它和Lisp最与众 不同的特征紧密联系:代码和数据由相同的数据结构构成, 而我们用quote操作符 来区分它们.

  3. (eq x y)返回t如果xy的值是同一个原子或都是空表, 否则返回().

    > (eq 'a 'a)
    t
    > (eq 'a 'b)
    ()
    > (eq '() '())
    t

  4. (car x)期望x的值是一个表并且返回x的第一个元素.

    > (car '(a b c))
    a

  5. (cdr x)期望x的值是一个表并且返回x的第一个元素之后的所有元素.
    > (cdr '(a b c))
    (b c)

  6. (cons x y)期望y的值是一个表并且返回一个新表,它的第一个元素是x的值, 后 面跟着y的值的各个元素.

    > (cons 'a '(b c))
    (a b c)
    > (cons 'a (cons 'b (cons 'c '())))
    (a b c)
    > (car (cons 'a '(b c)))
    a
    > (cdr (cons 'a '(b c)))
    (b c)
  7. (cond ($p_{1}$...$e_{1}$) ...($p_{n}$...$e_{n}$)) 的求值规则如下. p表达式依次求值直到有一个 返回t. 如果能找到这样的p表达式,相应的e表达式的值作为整个cond表达式的 返回值.

    > (cond ((eq 'a 'b) 'first)
    ((atom 'a) 'second))
    second

    当表达式以七个原始操作符中的五个开头时,它的自变量总是要求值的.2 我们称这样 的操作符为函数.

函数的表示

接着我们定义一个记号来描述函数.函数表示为(lambda ($p_{1}$...$p_{n}$) e),其中 $p_{1}$...$p_{n}$是原子(叫做参数),e是表达式. 如果表达式的第一个元素形式如 上

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

则称为函数调用.它的值计算如下.每一个表达式$a_{i}$先求值,然后e再求值.在e的 求值过程中,每个出现在e中的$p_{i}$的值是相应的$a_{i}$在最近一 次的函数调用中的值.

> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y)))
'z
'(a b c))
(z b c)
如果一个表达式的第一个元素f是原子且f不是原始操作符

(f $a_{1}$...$a_{n}$)

并且f的值是一个函数(lambda ($p_{1}$...$p_{n}$)),则以上表达式的值就是

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

的值. 换句话说,参数在表达式中不但可以作为自变量也可以作为操作符使用:

> ((lambda (f) (f '(b c)))
'(lambda (x) (cons 'a x)))
(a b c)

有另外一个函数记号使得函数能提及它本身,这样我们就能方便地定义递归函 数.3 记号

(label f (lambda ($p_{1}$...$p_{n}$) e))

表示一个象(lambda ($p_{1}$...$p_{n}$) e)那样的函数,加上这样的特性: 任何出现在e中的f将求值为此label表达式, 就好象f是此函数的参数.

假设我们要定义函数(subst x y z), 它取表达式x,原子y和表z做参数,返回一个 象z那样的表, 不过z中出现的y(在任何嵌套层次上)被x代替.

> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)
我们可以这样表示此函数
(label subst (lambda (x y z)
(cond ((atom z)
(cond ((eq z y) x)
('t z)))
('t (cons (subst x y (car z))
(subst x y (cdr z)))))))
我们简记f=(label f (lambda ($p_{1}$...$p_{n}$) e))为

(defun f ($p_{1}$...$p_{n}$) e)

于是

(defun subst (x y z)
(cond ((atom z)
(cond ((eq z y) x)
('t z)))
('t (cons (subst x y (car z))
(subst x y (cdr z))))))
偶然地我们在这儿看到如何写cond表达式的缺省子句. 第一个元素是't的子句总 是会成功的. 于是

(cond (x y) ('t z))

等同于我们在某些语言中写的

if x then y else z

一些函数

既然我们有了表示函数的方法,我们根据七个原始操作符来定义一些新的函数. 为了方便我们引进一些常见模式的简记法. 我们用cxr,其中x是a或d的序列,来 简记相应的car和cdr的组合. 比如(cadr e)是(car (cdr e))的简记,它返回e的 第二个元素.

> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)
我们还用(list $e_{1}$...$e_{n}$)表示(cons $e_{1}$...(cons $e_{n}$'()) ...).
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)

现在我们定义一些新函数. 我在函数名后面加了点,以区别函数和定义它们的原 始函数,也避免与现存的common Lisp的函数冲突.

  1. (null. x)测试它的自变量是否是空表.

    (defun null. (x)
    (eq x '()))

    > (null. 'a)
    ()
    > (null. '())
    t

  2. (and. x y)返回t如果它的两个自变量都是t, 否则返回().

    (defun and. (x y)
    (cond (x (cond (y 't) ('t '())))
    ('t '())))

    > (and. (atom 'a) (eq 'a 'a))
    t
    > (and. (atom 'a) (eq 'a 'b))
    ()

  3. (not. x)返回t如果它的自变量返回(),返回()如果它的自变量返回t.

    (defun not. (x)
    (cond (x '())
    ('t 't)))

    > (not. (eq 'a 'a))
    ()
    > (not. (eq 'a 'b))
    t

  4. (append. x y)取两个表并返回它们的连结.

    (defun append. (x y)
    (cond ((null. x) y)
    ('t (cons (car x) (append. (cdr x) y)))))

    > (append. '(a b) '(c d))
    (a b c d)
    > (append. '() '(c d))
    (c d)

  5. (pair. x y)取两个相同长度的表,返回一个由双元素表构成的表,双元素表是相 应位置的x,y的元素对.

    (defun pair. (x y)
    (cond ((and. (null. x) (null. y)) '())
    ((and. (not. (atom x)) (not. (atom y)))
    (cons (list (car x) (car y))
    (pair. (cdr) (cdr y))))))

    > (pair. '(x y z) '(a b c))
    ((x a) (y b) (z c))

  6. (assoc. x y)取原子x和形如pair.函数所返回的表y,返回y中第一个符合如下条 件的表的第二个元素:它的第一个元素是x.

    (defun assoc. (x y)
    (cond ((eq (caar y) x) (cadar y))
    ('t (assoc. x (cdr y)))))

    > (assoc. 'x '((x a) (y b)))
    a
    > (assoc. 'x '((x new) (x a) (y b)))
    new

一个惊喜

因此我们能够定义函数来连接表,替换表达式等等.也许算是一个优美的表示法, 那下一步呢? 现在惊喜来了. 我们可以写一个函数作为我们语言的解释器:此函 数取任意Lisp表达式作自变量并返回它的值. 如下所示:

(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (atom (eval. (cadr e) a)))
((eq (car e) 'eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'car) (car (eval. (cadr e) a)))
((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
((eq (car e) 'cons) (cons (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'cond) (evcon. (cdr e) a))
('t (eval. (cons (assoc. (car e) a)
(cdr e))
a))))
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e))
(cons (list (cadar e) (car e)) a)))
((eq (caar e) 'lambda)
(eval. (caddar e)
(append. (pair. (cadar e) (evlis. (cdr e) a))
a)))))

(defun evcon. (c a)
(cond ((eval. (caar c) a)
(eval. (cadar c) a))
('t (evcon. (cdr c) a))))

(defun evlis. (m a)
(cond ((null. m) '())
('t (cons (eval. (car m) a)
(evlis. (cdr m) a)))))
eval.的定义比我们以前看到的都要长. 让我们考虑它的每一部分是如何工作的.

eval.有两个自变量: e是要求值的表达式, a是由一些赋给原子的值构成的表,这 些值有点象函数调用中的参数. 这个形如pair.的返回值的表叫做环境. 正是 为了构造和搜索这种表我们才写了pair.和assoc..

eval.的骨架是一个有四个子句的cond表达式. 如何对表达式求值取决于它的类 型. 第一个子句处理原子. 如果e是原子, 我们在环境中寻找它的值:

> (eval. 'x '((x a) (y b)))
a

第二个子句是另一个cond, 它处理形如(a ...)的表达式, 其中a是原子. 这包 括所有的原始操作符, 每个对应一条子句.

> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
'((x a) (y b)))
(a b c)
这几个子句(除了quote)都调用eval.来寻找自变量的值.

最后两个子句更复杂些. 为了求cond表达式的值我们调用了一个叫 evcon.的辅助函数. 它递归地对cond子句进行求值,寻找第一个元素返回t的子句. 如果找到 了这样的子句, 它返回此子句的第二个元素.

> (eval. '(cond ((atom x) 'atom)
('t 'list))
'((x '(a b))))
list

第二个子句的最后部分处理函数调用. 它把原子替换为它的值(应该是lambda 或label表达式)然后对所得结果表达式求值. 于是

(eval. '(f '(b c))
'((f (lambda (x) (cons 'a x)))))
变为
(eval. '((lambda (x) (cons 'a x)) '(b c))
'((f (lambda (x) (cons 'a x)))))
它返回(a b c).

eval.的最后cond两个子句处理第一个元素是lambda或label的函数调用.为了对label 表达式求值, 先把函数名和函数本身压入环境, 然后调用eval.对一个内部有 lambda的表达式求值. 即:

(eval. '((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))
变为
(eval. '((lambda (x)
(cond ((atom x) x)
('t (firstatom (car x)))))
y)
'((firstatom
(label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x)))))))
(y ((a b) (c d)))))
最终返回a.

最后,对形如((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)的表达式求值,先调用evlis.来 求得自变量($a_{1}$...$a_{n}$)对应的值($v_{1}$...$v_{n}$),把($p_{1}$$v_{1}$)...($p_{n}$$v_{n}$)添加到 环境里, 然后对e求值. 于是

(eval. '((lambda (x y) (cons x (cdr y)))
'a
'(b c d))
'())
变为
(eval. '(cons x (cdr y))
'((x a) (y (b c d))))
最终返回(a c d).

后果

既然理解了eval是如何工作的, 让我们回过头考虑一下这意味着什么. 我们在这 儿得到了一个非常优美的计算模型. 仅用quote,atom,eq,car,cdr,cons,和cond, 我们定义了函数eval.,它事实上实现了我们的语言,用它可以定义任何我们想要 的额外的函数.

当然早已有了各种计算模型--最著名的是图灵机. 但是图灵机程序难以读懂. 如果你要一种描述算法的语言, 你可能需要更抽象的, 而这就是约翰麦卡锡定义 Lisp的目标之一.

约翰麦卡锡于1960年定义的语言还缺不少东西. 它没有副作用, 没有连续执行 (它得和副作用在一起才有用), 没有实际可用的数,4 没有动态可视域. 但这些限制可 以令人惊讶地用极少的额外代码来补救. Steele和Sussman在一篇叫做``解释器 的艺术''的著名论文中描述了如何做到这点.5

如果你理解了约翰麦卡锡的eval, 那你就不仅仅是理解了程序语言历史中的一个 阶段. 这些思想至今仍是Lisp的语义核心. 所以从某种意义上, 学习约翰麦卡 锡的原著向我们展示了Lisp究竟是什么. 与其说Lisp是麦卡锡的设计,不如说是 他的发现. 它不是生来就是一门用于人工智能, 快速原型开发或同等层次任务的 语言. 它是你试图公理化计算的结果(之一).

随着时间的推移, 中级语言, 即被中间层程序员使用的语言, 正一致地向Lisp靠 近. 因此通过理解eval你正在明白将来的主流计算模式会是什么样.

注释

把约翰麦卡锡的记号翻译为代码的过程中我尽可能地少做改动. 我有过让代码 更容易阅读的念头, 但是我还是想保持原汁原味.

在约翰麦卡锡的论文中,假用f来表示, 而不是空表. 我用空表表示假以使例子能 在Common Lisp中运行. (fixme)

我略过了构造dotted pairs, 因为你不需要它来理解eval. 我也没有提apply, 虽然是apply(它的早期形式, 主要作用是引用自变量), 被约翰麦卡锡在1960年 称为普遍函数, eval只是不过是被apply调用的子程序来完成所有的工作.

我定义了list和cxr等作为简记法因为麦卡锡就是这么做的. 实际上 cxr等可以 被定义为普通的函数. List也可以这样, 如果我们修改eval, 这很容易做到, 让 函数可以接受任意数目的自变量.

麦卡锡的论文中只有五个原始操作符. 他使用了cond和quote,但可能把它们作 为他的元语言的一部分. 同样他也没有定义逻辑操作符and和not, 这不是个问题, 因为它们可以被定义成合适的函数.

在eval.的定义中我们调用了其它函数如pair.和assoc.,但任何我们用原始操作 符定义的函数调用都可以用eval.来代替. 即

(assoc. (car e) a)
能写成

(eval. '((label assoc.
(lambda (x y)
(cond ((eq (caar y) x) (cadar y))
('t (assoc. x (cdr y))))))
(car e)
a)
(cons (list 'e e) (cons (list 'a a) a)))

麦卡锡的eval有一个错误. 第16行是(相当于)(evlis. (cdr e) a)而不是(cdr e), 这使得自变量在一个有名函数的调用中被求值两次. 这显示当论文发表的 时候, eval的这种描述还没有用IBM 704机器语言实现. 它还证明了如果不去运 行程序, 要保证不管多短的程序的正确性是多么困难.

我还在麦卡锡的论文中碰到一个问题. 在定义了eval之后, 他继续给出了一些 更高级的函数--接受其它函数作为自变量的函数. 他定义了maplist:

(label maplist
(lambda (x f)
(cond ((null x) '())
('t (cons (f x) (maplist (cdr x) f))))))
然后用它写了一个做微分的简单函数diff. 但是diff传给maplist一个用x做参 数的函数, 对它的引用被maplist中的参数x所捕获.6

这是关于动态可视域危险性的雄辩证据, 即使是最早的更高级函数的例子也因为 它而出错. 可能麦卡锡在1960年还没有充分意识到动态可视域的含意. 动态可 视域令人惊异地在Lisp实现中存在了相当长的时间--直到Sussman和Steele于 1975年开发了Scheme. 词法可视域没使eval的定义复杂多少, 却使编译器更难 写了.

About this document ...

Lisp之根源

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split=0 roots_of_lisp.tex

The translation was initiated by Dai Yuwen on 2003-10-24


Footnotes

... 欧几里德对几何的贡献.1
``Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part1.'' Communication of the ACM 3:4, April 1960, pp. 184-195.
...当表达式以七个原始操作符中的五个开头时,它的自变量总是要求值的.2
以另外两个操作符quote和cond开头的表达式以不同的方式求值. 当 quote表达式求值时, 它的自变量不被求值,而是作为整个表达式的值返回. 在 一个正确的cond表达式中, 只有L形路径上的子表达式会被求值.
... 数.3
逻辑上我们不需要为了这定义一个新的记号. 在现有的记号中用 一个叫做Y组合器的函数上的函数, 我们可以定义递归函数. 可能麦卡锡在写 这篇论文的时候还不知道Y组合器; 无论如何, label可读性更强.
... 没有实际可用的数,4
在麦卡锡的1960 年的Lisp中, 做算术是可能的, 比如用一个有n个原子的表表示数n.
... 的艺术''的著名论文中描述了如何做到这点.5
Guy Lewis Steele, Jr. and Gerald Jay Sussman, ``The Art of the Interpreter, or the Modularity Complex(Parts Zero,One,and Two),'' MIT AL Lab Memo 453, May 1978.
... 对它的引用被maplist中的参数x所捕获.6
当代的Lisp程序 员在这儿会用mapcar代替maplist. 这个例子解开了一个谜团: maplist为什 么会在Common Lisp中. 它是最早的映射函数, mapcar是后来增加的.

标签: