2009年5月29日星期五

Side-Effect

近来说FP(函数式语言)很好很强大的人越来越多了,只是因为没需求,所以就一直没动力去学。也正是因为这样,我对副作用、引用透明之类的概念总是不甚了了。昨晚忍不住拽了一位童鞋聊了聊,算是有了点收获吧。

首先是引用透明,某童鞋的说法是:引用透明就是可以用函数的返回值代替函数的调用。

我觉得的这样的说法并不完整,于是写了这样一段代码问他:

int x;

int fa(int m, int n) {
  x = m + n;
  return x;
}

int fb(int z) {
  return x + z;
}

他说fa函数不算引用透明,因为用fa的返回值代替函数调用后,整个程序的运行结果会发生变化。可问题是,如果fb从来没调用过,且没有在其他地方读写过全局变量x的值呢?

于是试着总结一下,一个引用透明的函数,似乎应该满足以下三个条件:

  1. 只通过传值调用输入数据;
  2. 只通过返回值输出数据;
  3. 不且不能读取和修改函数外的任何其他数据。

如果一个程序中的所有函数都满足这三个条件,那么就可以保证所有函数的调用都可以用返回值来代替。

而所谓副作用指的是上述第三条。如此,“没有副作用即是不对环境产生影响”是一种没错,但是没说清楚的解释。

那么,“没有副作用即是没有变量的值发生变化”又是怎么一回事?以我的理解,这是一个混乱而错误的说法。

若我对引用透明的阐述没有错,那么所谓副作用就只是指针和作用域的问题。假如C语言中没有指针和全局变量(IO的部分另说),那么也可以说C的函数是引用透明的。

扯出变量,似乎只是命令式语言的习惯性思维作祟,因为在FP里是没有变量这种东西的。

假如在某一门FP里支持这样的语法:“int x=1”,这并非是“把整数1赋值给变量x”,而是“定义符号x代表整数1”,更像数学里的说法。即使有“x=x+1”这样的语法,也并不是“计算表达式并修改变量x的值”,而是“删除符号x与原有值的关系并重新定义一个”,内存中x原指向的1的值并没有发生变化,2被存到另外的地方去了。

事实上,FP中的“x=x+1”更有可能代表的意思是累加,即“x = (x + 1) = ((x + 1) + 1) = ...”

值只能被定义,不能被修改,岂不是又慢又浪费内存?又为什么要强调引用透明?仔细想想,却也不是没有好处的。

引用透明了,垃圾回收就容易了。可以定义无穷表,且定义时不需要计算其值,也就是所谓的延迟计算。编译器可以缓存一部分函数的运算结果,加速程序运行。无副作用,所以对并发友好,更容易发挥多核CPU的计算能力。

连我这种不会FP的人都能想到这么多好处,FP果然是种很天才的东西。

奇怪的是,除了emacs和唐凤的Perl6实现,怎么没见过用FP实现的其他东西?

2009年5月28日星期四

AMR Plugin For Winamp & foobar2000

好吧,我快要叛变了。又写了个foobar2000的AMR插件,下载链接等在文末。

KMplayer就可以放AMR,但启动太慢了。foobar2000早就有相关插件,问题是歌词外挂支持不良。惦记了很久Winamp的AMR插件一直没出现,今天终于自己写了一个。

(从*UIX系统来的不算,命令行工具不算,Winamp是我现在还常用的辈分最老的程序了,总觉得有那么点英雄迟暮的味道。)

AMR由rfc3267定义,网上最容易找到的实现是3GPP发布的3GPP TS 26.104(AMR-NB)和3GPP TS 26.204(AMR-WB)。

由于写这个插件就是为了播放手机录制的音频文件,而手机录制的音频文件全部都是AMR-NB IF1格式,所以这个插件目前只实现了AMR-NB IF1的解码功能。ETSI和IF都没有文件头,应该不是设计给独立文件用的。至于AMR-WB,以后遇到了再说吧。

AMR-NB IF1格式很简单,头部为6个字节的标识信息"#!AMR\n",余下部分为若干个frame。每个frame第一字节的前4位决定了frame的字节长度(包括首字节),如1表示13,2表示14,3表示16,有个表可以查。

AMR-NB的目标码率只有一种,8kHz、13bit、单声道。而且每frame表示的数据量也是一定的,即160次采样的数据,20ms长。

因为AMR-NB格式没有任何的索引信息,所以不扫描整个文件就无法得知文件时长,这也是KMplayer播放AMR-NB时为什么不能拖动的原因。

下载:

Winamp - in_amr_v0.1_20090902.zip

foobar - foo_input_amr_v0.3.1_20120813.7z

2017-9-18
Box的下载链接挂掉了,换成了Google Drive,也不知道能用多久…
2012-8-13 oAMpF v0.3.1
增加单声道AMR-WB支持,改了几个bug。
2010-9-24 oAMpF v0.2.1
忘记具体改了什么,好像是一点bug的说。这一版的foobar插件已经比较完善了,起码我自己用没遇到什么问题。
2010-4-15 oAMRpF v0.2
基本功能跟Winamp版一样,多了示波功能
AMR-NB IF1最后一个frame的实际长度有可能小于应当值,不知道合不合规范,懒得查了
2009-5-28 oAMRpW v0.1
支持AMR-NB IF1格式
可拖放,可显示文件时长
播放损坏的文件时可能crash
不支持Winamp示波器及相关插件

2009年5月26日星期二

Build Ruby With ICC

前些日子试图用WinDDK编译Ruby失败,不过却一直惦记着。这两天突然想起,天底下除了VC和GCC,还有一个叫Intel C++ Compiler的东西,于是就试了试。

我用的ICC是v10.1.021版,虽然v11早就有了,可看起来新版本不再支持VC6了的样子,所以只好用旧版。

正常运行configure.bat,打开生成的Makefile,在最后一句include前面加上如下三行:

CC = icl
CPP = icl
LDFLAGS = -incremental:no -debug -opt:ref -opt:icf /nodefaultlib:libmmd.lib

最后一句的nodefaultlib是为了去掉对libmmd.dll的依赖,虽然据说会快一点,不过能少一个库也是好的。

编译过程没出什么问题,除了编译速度很慢很慢以外。ZLib和PDCurses用ICC重新编译过,IConv和OpenSSL则犯懒了,用的是以前VC6编译的版本,链接也都OK。

nmake test时出错,跟了一下发现是Win32API的bug。CFunc的默认调用约定是cdcel,而绝大部分Windows APIs应该用stdcall。可奇怪的是,VC6编译出来的代码,用cdcel方式调用也可以。

跑到Ruby官网上逛了一圈,发现该问题已修正,只是要下个版本才会发布。自己编译1.9.1-p120的话,还是得在编译前手工改代码。

暂时没遇到其他的问题,copy了一个用VC6编译的sqlite3_api.so,能用,ICC和VC的兼容性还蛮不错的。

benchmark没很严格地跑,随便写了一点小东西比较,比VC6编译的版本快很多,但却比MinGW(gcc 3.4)编译的略慢些,不知道算不算正常现象。我的老机器跑ICC太累,OpenMP和SSE2之类的也都用不上,先这样吧……

2009年5月21日星期四

Ruby中的负数整除问题

Ruby中两个整数相除,其结果为整数,例如1/2为0,7/3为2。这跟C是一样的,所以我一直以为Ruby的除法运算跟C是一回事。前些日子移植一个C程序时结果出错,这才发现自己又想当然了。在Ruby中,-7/3不等于-2,而是-3。

翻书,《The Ruby Programming Language》有提到这个问题。书中解释,Ruby作整除运算时对结果进行向下(负无穷大)取整,而C则是向零取整。相应的,Ruby中-7%3的结果就是2,而非-1,想来这样的结果是为了满足(a/b)*b+(a%b)=a这一等式。

C当然也可以进行向下取整,函数名为floor。近似地,向上(正无穷大)取整的函数名则叫ceil。Ruby中也有同名的两个取整方法,若想在Ruby中进行向零取整,需要调用truncate方法,而想获得跟C一样的求余结果则要用remainder方法。

仔细想想,总觉得Ruby这样的处理方式有点不妥。

像Ruby这样的动态语言,由于不存在类型声名,运算结果类型不确定就很容易出错,而且这种错误很难发现。既然都自诩为高级语言了,还不如像Javascript那样直接返回实数,这样更明确,也更贴近于数学。

退一步说,即使要取整,似乎也应该用truncate而非floor。前者是直接丢弃小数部分,应该比较快,而且跟广为流行的C保持一致。

很想知道为什么Ruby、Python、Tcl都采用(过)floor,查了查却不得其解,算了。

2012-06-28 Update

经某位家住清华园的友人指点,原来是为了所谓数学上的完备性。

当a和b都是正数时,a整除b,得数q,余数r,则满足b*q + r == a,且0 <= r < b。

当a是负数,b是正数时,向下取整可以保证上述表达式仍然成立。

至于为什么要使modulo返回正数,请参考Wikipedia

似乎不是个很有趣的原因…