• Coding is Hard, Let's go LISPing (Part 1)

    日期:2011-05-15 | 分类: | Tags:lisp DSL CLISP SBCL

    Interested in Lisp for quite a long time, it was not until recently that I started to really try writing something in Lisp. I see that Lisp is very special in its macros as well as its homoiconicity, it is very good for implementing DSLs (Domain Specific Language). So my adventure in the world of Lisp started from a work to mimic or generate a certain DSL that I use in daily work.

    Here is a simple example to define an instance in the DSL source,

    Test FunctionalTest func1_test {
        TestConditionParam = func_lvl;
        TestConditionParam = func_tim;
        PListParam = pat1;
        DatalogParam {
            Enable = Yes,
            CycleLimit = 10,
            DisableDUT = 1,
            DisableDUT = 4
        ExecEndSequence = Enable;

    The first “Test” is a keyword. "FunctionalTest" is kind of type of class, and "func1_test" is the instance name. Within the "{" and "}" braces define the intance parameters. A parameter can be a scalar parameter or a grouped one. And in the case of a grouped parameter, it has multiple second-level parameters. And the syntax for the second-level parameters is a little bit different from the first-level ones. Also, for the same parameter, no matter the first-level ones or the second-level ones, it can have more than one entries to specify multiple values. The instance represented by the code above is actually a data holder, which provide information for some software system. Usually we need to code a lot of such instances, each may have a different type and different parameters.

    At the first step of my experiments, I woule like to translate, with less deviation if possible, the DSL's syntax into Lisp s-expressions. I see that the above code of "func1_test" can be flatten to a list. So I would like to make it like this,

    (test FunctionalTest func1_test
          (TestConditionParam func_lvl)
          (TestConditionParam func_tim)
          (PListParam pat1)
          (DatalogParam ((Enable Yes)
                         (CycleLimit 10)
                         (DisableDUT 1)
                         (DisableDUT 4)))
          (ExecEndSequence Enable)))

    This means, with the above Lisp s-expression executed, it should finally generate the code of my DSL source in the above example.

    My Common Lisp functions and macros are like this.

    (defun is-flat (lst)
      (if (null lst)
          (let ((a (car lst)))
            (if (or (null a) (not (atom a)))
                (is-flat (cdr lst))))))
    (defun test-param (item)
      (let ((name (car item))
            (value (car (cdr item))))
        (if (is-flat item)
            (format nil "    ~a = ~a;" name value)
            (with-output-to-string (s)
              (format s "    ~a {~%" name)
              (format s 
                        #'(lambda (p) 
                            (let ((pname (car p)))
                              (format nil 
                                      "        ~a = ~a" 
                                      pname (car (cdr p)))))
                       (format nil ",~%")))
              (format s "~%    }")))))
    (defmacro test-params (&rest body)
        (list ,@(mapcar #'(lambda (p) (test-param `(,@p))) body))
        (format nil "~%")))
    (defmacro test-macro (fh)
      `(defmacro test (klass name &body body)
             (with-output-to-string (s)
               (format s "Test ~a ~a {~%" ,(string klass) ,(string name))
               (format s "~a~%" ,`(test-params ,@body))
               (format s "}~%~%"))

    The program distinguishes first-level and second-level parameters simply by checking if the s-expression is flat or not. So "is-flat" is a function for doing this check, and is used by "test-param". "test-params" is a macro that calls "test-param" for each of its first-level scalar or grouped parameters. And "test-macro" is a marcro that generates top-level "test" macros for outputting to different stream handles.

    And here are some utility functions for above Lisp program.

    (defun mkstr (&rest args)
      (with-output-to-string (s)
        (dolist (a args) (write-string a s))))
    (defun string-join (lst &optional (sep ""))
      (if (null lst)
          (reduce #'(lambda (a b) (mkstr a sep b)) lst)))

    So finally we have below to generate the DSL source.

    (defvar test (test-macro *standard-output*))
    (test FunctionalTest func1_test
          (TestConditionParam func_lvl)
          (TestConditionParam func_tim)
          (PListParam pat1)
          (DatalogParam ((Enable Yes)
                         (CycleLimit 10)
                         (DisableDUT 1)
                         (DisableDUT 4)))
          (ExecEndSequence Enable)))

    So, it is code, and it is data.

    Note that something tricky with the above Lisp program is that, it is not workable with popular Common Lisp implementations like SBCL . Instead it works with CLISP 's "modern" mode. If we go back to look at the last piece of code above, we see that it does not have quotes there on "FunctionalTest", nor "TestConditionParam" or everything that should be a "string" if I implement in some other languages the generation of the DSL code from a list. Lisp needs to convert these symbols into strings. But we know that standard Common Lisp cannot properly keep the cases of the symbols. (By default it makes a symbol uppercase. And although there are some setting overwrittable in the reader by using (setf (readtable-case *readtable*) :invert), it still has some problems. ) CLISP has a "modern" mode to let the reader become case-sensitive. (In other implementations like SBCL, a work-around is to use a package called "named-readtables ". )



    So far it looks like that this Lisp program just changes the DSL's syntax. Actually still it can evolve to support more features. I will show that in a next post.

  • 米国佬还是很有钱地

    日期:2011-02-27 | 分类: | Tags:LCD 工作






  • 去年10月的时候某人跟我谈到fractal的一些东西。11月的某天用plt-scheme写了一段代码,当时画了一个简单的黑白的Mandelbrot set。今天想到变彩色的其实也不麻烦,于是visualize它的这个distance特性吧。。。

    MandelBrot Set

    #lang scheme/gui
    (define (square x) (* x x))
    (define (->integer d) (inexact->exact (floor d)))
    (define (mandelbrot c n)
      (let p ([i 0] [acc 0.0])
        (if (or (>= (magnitude acc) 2.0) (equal? i n))
            (exact->inexact (/ i n))
            (p (+ i 1) (+ (square acc) c)))))
    (define (get-color d)
      (if (equal? d 1.0)
        (make-object color% "BLACK")
        (let ((r (->integer (* d 255.0)))
              (g (->integer (* d 255.0)))
              (b (modulo (->integer (* (+ 0.4 d) 255.0)) 256)))
          (make-object color% r g b))))
    (define (draw-mandelbrot-set 
             dc rmin rmax imax reso iter-limit)
      (let ((xmin 0) (ymin 0)
            (xmax (/ (- rmax rmin) reso))
            (ymax (/ (* imax 2) reso)))
        (do ((x xmin (+ x 1))) ((> x xmax))
          (do ((y ymin (+ y 1))) ((> y ymax))
            (let* ((c (make-rectangular 
                      (+ rmin (* (- x xmin) reso))
                      (- imax (* (- y ymin) reso))))
                  (m (mandelbrot c iter-limit))
                  (pen (make-object pen%)))
              (send pen set-color (get-color m))
              (send dc set-pen pen)
              (send dc draw-point x y))))))
    (define (plot-mandelbrot-set
             rmin rmax imax reso iter-limit)
        (let* ((bm (make-object bitmap%
                     (->integer (/ (- rmax rmin) reso))
                     (->integer (/ (* imax 2) reso))))
               (dc (make-object bitmap-dc%)))
          (send dc set-bitmap bm)
          (send dc clear)
          (draw-mandelbrot-set dc rmin rmax imax reso iter-limit)
          (send bm save-file "mandelbrot.png" 'png)))
    (plot-mandelbrot-set -2.4 1.0 1.2 0.002 50) ; main routine


    Mandelbrot在TED的视频 从家里看老是有点卡的,所以,还是看youku 上的吧。

    对了,最后必须要说的是:Wish him rest in piece...




    这次顺便发现了SyntaxHighlighter 这个好东西,真是太强大了!不过呢,现在它还不支持Scheme的brush。网上有些人自己写了Scheme的brush,比如这个 ,但是它有个bug是会把>,<这些处理增加;变成comments。这里我用了一个work-around的办法,不过没多试不知道会不会带来别的问题。


  • 达人秀决赛观感

    日期:2010-10-11 | 分类: | Tags:达人秀 刘伟 高晓松 波德莱尔

    刘伟夺冠这事本身在大家意料之中,我就不多说了。(本人也贡献了一票呵呵。)有意思的是刘伟这次选的节目you're beautiful是值得咀嚼一下的:这曲子我以前是听过几遍,今天突然意识到,它的词是取了为本雅明所情有独钟的波德莱尔的《致一位交臂而过的女士》的精神。它赞颂了一种美,这种美来自于偶遇的惊诧以及于观者而言的距离感。事实上在达人秀的舞台上,刘伟本人正是这种大众的偶遇的客体!而一如本雅明对波德莱尔的诗所评论的,这种美在“发达资本主义时代”的背景中升华了!


    评论一下其他选手吧:翟孝伟马丽并不是赛前我特别看好的,但他们的梁祝堪称美仑美奂,即便是由两个体格正常的人来演,也是足够站在这个决赛的舞台上的。朱晓明的问题是他重复唱了Hero,又在风格上和蔡MM撞车。蔡MM今天的音色发挥感觉不如唱When you believe那次的好,不过选曲以及与评委的对答都是很好的。另外,如饶舌街舞之类,毕竟在当下的国内还属边缘文化。至于张冯喜小朋友么,真是做到了老少通吃呢(虽然本人不是特别喜欢)。有意思的是程雷几次说错她的短信号,不知道是不是故意的。。。




    记得两个月前在国外出差的时候,在电视上看过一段当地的达人秀。那是一个简单普通的女孩子,抱着一把吉他,弹唱Sarah McLachlan的Angel。在面对评委时尤显羞怯质朴,她的梦想是去拉斯维加斯表演一次,最后全场起立为她喝彩。这个节目的形与神,看来中国达人秀都学到了呢。




  • 指数衰减曲线的拟合

    日期:2010-07-24 | 分类: | Tags:指数曲线 拟合 工作 美国



    y(t) = A exp(-t/tau) + C


    首先我们来看这个问题的一个简单版,在C = 0的情况下有,

    y(t) = A exp(-t/tau)


    log y = - t/tau + log A (就认为A>0吧,其实符号不影响对这个问题的讨论的)

    显然log y与t之间有一个线性关系,从而这个指数曲线的问题就转变为一个较简单的线性拟合问题了。


    log (y - C) = - t/tau + log A


    其实在许多情况下,这个C是可以测量到的,比如我们测量时等待足够长的时间就是了,这也是地球人都能想到的一个有效方法。不过我们不应该仅为如何多快好省地解决眼前的单一问题而思考:) 恩,我想说的是除此以外其实还是有些别的方法的。


    y(t) = A exp(-t/tau) + C,将y对t求导的话,得到,

    dy = - A/tau * exp(-t/tau) * dt

    log dy = -t/tau + log (- A/tau * dt)

    所以当delta t为定值,即测量为等时间间隔的情况下,log(delta y)与t之间出现了一个线性关系,于是这又转化为一个线性拟合问题了。得到A与tau之后可以再计算出C。

    当时我在用上面这个方法的时候,感觉好像不是十分精确(虽然拟合结果可以说基本没什么问题),原因可能是我的delta t比较大,此时delta y与t之间的对应关系并不是很确切。于是又引出了下面这个方法,

    由y(A, tau, C) = A exp(-t/tau) + C可以得到全微分,

    dy = exp(-t/tau) * dA + A*t/tau^2 * exp(-t/tau) * dtau + dC


                                              | dA   |
    | dy | = | factor_A factor_tau factor_C | | dtau |

                                              | dC


    我们可以在一开始给出A, tau以及C的估值,同时我们即得到了估计的y,与实测的数据相减可以得到含各个观测点上的dy的向量,从而通过这个线性方程组解出dA, dtau, dC。因为我们的实测数据量通常都是大于3个,所以这个求解可以利用最小二乘法(很多软件有这样的library,比如numpy中有linalg.lstsq)。解出的dA, dtau, dC用于修正的A, tau, C的估值,如此进行迭代直至A, tau, C稳定。




    这段时间最大的收获是忙里偷闲学了一点点Haskell。感觉比较适合用来解一些数学问题,不过我不确定用在日常工作中的话会不会有明显的便利。我们做的最多的可能是text parsing了,从这一点上讲我觉得一种language能否快速流行,要看它(或者它的library)有没有很便捷的text processing能力。说到parsing,其实每个人每天每时每刻都在parsing,想到这里,显然自然还是很奥妙的呢:)


  • 炭笔素描:Chester Bennington

    日期:2010-02-19 | 分类: | Tags:Chester Bennington Linkin 炭笔 素描

    fig: chester charcoal




  • Brand New Eyes cover art

    Brand New Eyes的封面上,是一只被肢解的蝴蝶,这是一种静态的、生气已逝的、凄艳的美。蝴蝶是一种符号,它们是这样的生物,美丽优雅,而又脆弱不堪,生命短暂。以此设计封面,或许暗合了Brick by Boring Brick(BBBB)中所唱的,

    The angels are all wrong now

    She's ripping wings off of butterflies

    BBBB给人一种震惊。这个世界上有太多歌曲刻意营造出一种童话的氛围,而BBBB却在残酷地把童话击碎。 MV中小女孩的童话世界崩塌,最后她逃进了坟墓。显然坟墓的寓意是沉重,是沉重的现实。现实世界中栖身的小屋是由brick by boring brick垒砌起来的,童话中的城堡则必须被埋葬。

    BBBB的这样的主题是以前Paramore所没有尝试过的。总的来说,与上一张专辑Riot相比,Brand New Eyes的内容要宽泛得多了,这是一个进步(Riot的题材相对单调,最受欢迎的Misery Business的内容实在是...)。除BBBB外个人最喜欢的是Playing God,旋律与内容俱佳。另外慢歌Misguided Ghost也不错。其他的话,Decode好像是暮光之城(不过我没看过)的主题曲,专辑中Decode与All I Wanted这两首尤其展现了Hayley的爆发力,那嗓子真不是一般的好啊~~ Where the Lines Overlap很有喜感,甚至或许适合在婚礼上放(这里顺便想到的是,婚礼上的音乐还是该要选一下的,本人有次听到LP的Runaway~~)。


    For Those Who Wait cover art

    For Those Who Wait是Fireflight上周出的新砖。Christian Rock还是需要时不时地听一下的吧,因为一般的rock往往是有点灰暗呢。说实话个人感觉这张专辑整体不如Unbreakable,主打Desperate一般。不过总是还有好听的吧,What I've Overcome就很棒,有力量,并且很能给人力量,另外多听两遍的话觉得New Perspective也不错。至于Name,它说明了Christian的民谣也可以是满好听的,虽然个人不是特别喜欢。






  • 大巴居然被封了!MS是DNS解析不能啊,从网上找了个IP信息,总算是潜入了。。。嘘









    DFT formula





    DFT是对连续傅立叶变换的采样。下图是一个满足相关采样的例子,可以看到由于矩形窗的影响,连续傅立叶变换的结果实际上是一个有较大的main lobe(这个好像是翻译成主瓣吧)以及向外逐渐减小的一系列side lobe的包络状。所以可以宽泛地认为加窗本身就造成了频谱泄漏。只不过在相关采样的情况下,应用矩形窗的结果是DFT/FFT bin就落在那些最大衰减点(且这些点的值为0)上。


    对于非相关采样的情况,如我们所见的,single tone信号的能量会扩散到整个频谱上。这往往不是我们愿意看到的,因为这些扩散的能量除了导致我们所关注的这个tone看上去偏弱之外,还可掩蔽掉其他我们所关注的频谱成分,影响了我们对于其连续时间信号的准确认识。

    很多情况下这种频谱泄漏是不可避免的。我们都知道可能的对策是加Hanning窗之类。为什么加窗可以改善这个问题呢?加窗在时域上表现为以为乘法,亦即加窗后数据的傅立叶变换结果实际上是加窗前数据的傅立叶变换与窗数据的傅立叶变换的卷积,或者直观一点看,Hann之类的side lobe衰减比rectangular window快多了,所以应用Hann之类的话可以改善频谱泄漏的状况。不过Hann相对于rectangular有一个缺陷是,因为Hann的main lobe比较宽,所以对相邻的bin的泄漏严重,这会在能量较大的一些bin上都能明显看出来的。



    fig: different windows

    图:不同窗的mainlobe宽度及side lobe衰减比较,来自wikipedia




    这里就只先谈一个问题吧,加窗后的频谱怎么补偿?比如在ATE测试时可能需要知道DC offset是多少,或者signal tone能量到底是多少?有些不是很精确但还是可以一用的计算方法,MS网上提到这个的很少。

    实际上Hann的话计算DC offset的补偿系数是2(倍)就可以了。因为Hann的main lobe幅度趋近于0.5,所以加Hann窗后的DC分量幅度大约会是原来的一半。(记得上面我们说过卷积的事么?卷积可以认为是一种加权积分,这样好理解一点。另外需要注意的是这个简单的x2背后隐含了一个前提:加窗前的DC之外的各bin的能量及其距离导致它们在加Hann窗的过程时对DC bin的影响十分有限。所以在具体应用的时候还是要看一下的)。

    关于能量计算的话是这样,加Hann窗的话积分时应包含singal tone处的相邻3个bin(因为能量主要扩散到这2~3个bin上,另外频谱数据归一化的方法与普通做法相同),在这个功率的基础上除以一个3/8的结果就是实际功率。按Hann的函数,

    Hann function

    n从0到N-1,w(n)平方的积分结果归一化以后(或者与rectangular window的情况相比较来说),是趋于3/8,即加Hann窗的结果相对于矩形窗来说,能量只有原来的3/8。其它窗如Hamming等都可以用类似方法分析。我以前有看到过网上(现在一下子找不到source了)也有用所谓ENBW(Equivalent Noise BandWidth)来解释功率补偿的,实际上应该是一码事。


  • 西安:每寸土地皆为传奇

    日期:2009-11-30 | 分类: | Tags:西安 行走

    听到Dido那慵懒而富有磁性的嗓音,听她唱着want to see the world alone again的时候,我想,也许应该出去旅行了吧。于是一个人赴西安的远途,便这般在随性而发下开始,在背包行走时进行,也终而在恍惚与唏嘘中结束了。














  • 八卦一下

    日期:2009-11-01 | 分类: | Tags:摇滚 Avril Sum41 音乐