Yongwei Xing's base with ET: March 2010

Wednesday, March 31, 2010

SharePoint Web Service(5)--Make use of the return XML

When you use the web service to manipulate, like add a new item or update a item list. After processing, the server would return a value which is a XML code snippet. In this XML code snippet, you can get a lot of information you need.

When you create a new item in a list, and you want to know the new ID for this item. You can see there is a attribute named ows_ID, this is the ID for the new item. In addition, you can get some basic information about the list and the item. There is a Errorcode attribute, when the operation is successful, the Errorcode would be zero. When error comes up, you can check the Errorcode and error information here.

CSS Position

In the CSS, one of the most difficult concepts is the position property. There is a wonderful page Learn CSS position in ten steps. Simple, detail and useful with examples.

Building a simple compiler series (8)–Yacc

Yacc(Yet another compiler-compiler), another powerful tool for generator a parser according to a specify context free grammar.

Yacc provides a general tool for imposing structure on the input to a computer program. The Yacc user prepares a specification of the input process; this includes rules describing the input structure, code to be invoked when these rules are recognized, and a low-level routine to do the basic input. Yacc then generates a function to control the input process. This function, called a parser, calls the user-supplied low-level input routine (the lexical analyzer) to pick up the basic items (called tokens) from the input stream. These tokens are organized according to the input structure rules, called grammar rules; when one of these rules has been recognized, then user code supplied for this rule, an action, is invoked; actions have the ability to return values and make use of the values of other actions.

Yacc file specifcation just like below which is similar with the Lex file specification.

declarations
%%
rules
%%
programs

Here is a quick demo which based on here. You can refer to that link for more iinformation.I add a main function and a yyerror function. I will add more detail information and other examples in next post. Here is just a simple example which shows what’s the yacc like, how to use it, and what is it like.

%{
# include
# include
int regs[26];
int base;
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /* supplies precedence for unary minus */
%% /* beginning of rules section */
list : /* empty */
| list stat '\n'
| list error '\n'
{ yyerrok; }
;
stat : expr
{ printf( "%d\n", $1 ); }
| LETTER '=' expr
{ regs[$1] = $3; }
;
expr : '(' expr ')'
{ $$ = $2; }
| expr '+' expr
{ $$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{ $$ = $1 / $3; }
| expr '%' expr
{ $$ = $1 % $3; }
| expr '&' expr
{ $$ = $1 & $3; }
| expr '|' expr
{ $$ = $1 | $3; }
| '-' expr %prec UMINUS
{ $$ = - $2; }
| LETTER
{ $$ = regs[$1]; }
| number
;
number : DIGIT
{ $$ = $1; base = ($1==0) ? 8 : 10; }
| number DIGIT
{ $$ = base * $1 + $2; }
;
%% /* start of programs */
yylex() { /* lexical analysis routine */
/* returns LETTER for a lower case letter, yylval = 0 through 25 */
/* return DIGIT for a digit, yylval = 0 through 9 */
/* all other characters are returned immediately */
int c;
while( (c=getchar()) == ' ' ) {/* skip blanks */ }
/* c is now nonblank */
if( islower( c ) ) {
yylval = c - 'a';
return ( LETTER );
}
if( isdigit( c ) ) {
yylval = c - '0';
return( DIGIT );
}
return( c );
}
main()
{
return yyparse();
}
int yyerror(char *s)
{
fprintf(stderr,"%s\n",s);
return 0;
}

The input file.

The result of the expression.

SICP Series-chapter 1.2.1-1.2.2

When we talk about the recursive, factorial is one of the most classical problem. In the LISP world, recursive is very normal, but you also can use the “iterative process”. But this is a special iterative process. You can take a look at the example below to compare it with others which are written by other programming language.
(defun fact-iter(product iter maxiter)
(if (> iter maxiter)
      product
      (fact-iter (* product iter)
                 (+ iter 1)
                 maxiter)))

(defun fact (n)
(fact-iter 1 1 n))

1.9 The first one is recursive, the second one is iterative.

1.10

(defun A (x y)
(cond ((= y 0) 0)
        ((= x 0) (* y 2))
        ((= y 1) 2)
        (t (A (- x 1)
              (A x (- y 1))))))

(A 1 10)
(A 0 (A 1 9))
(* 2 (A 1 9))
(* 2 (A 0 (A 1 8)))
(* 2 (* 2 (A 1 8)))
….
You can see that the (A 1 10)=2^10

(defun f (n) (A 0 n)) ;2n
(defun g (n) (A 1 n));2^n
(defun h (n) (A 2 n)); 2^2^… (n times)

Another common pattern of computation is called tree recursive, Fibonacci is one of the most classical example.
1.11 Tree recursive is very inefficiency, when I take the n as 100, my laptop runs for a very long time. When I use the iterative version, even the n is 10000, it takes less then one second. You can see the run-time information when the n=2000 and n=20. You will see the big gap between them.

(defun f-rec(n)
   (cond ((< n 3) n)
           (t (+ (f-rec (- n 1))
               (* 2 (f-rec (- n 2)))
               (* 3 (f-rec (- n 3)))))))

(defun f-iter(n)
   (if (< n 3)
       n
       (f-iter-aux 2 1 0 n)))

(defun f-iter-aux (a b c n)
   (if (= n 2)
       a
       (f-iter-aux (+ a
                       (* 2 b)
                       (* 3 c))
                   a
                   b
                   (- n 1))))

1.12 This exercise is very similar to the Fibonacci
(defun pascal (positionr positionc)
   (cond ((= positionr 1) 1)
          ((= positionc positionr) 1)
          ((= positionc 1) 1)
          (t (+ (pascal (- positionr 1) positionc)
              (pascal (- positionr 1) (- positionc 1))))))

Regular Expression to replace number with new value based on orig

Today, I meet a problem, I need replace a lot of numbers in a file with a new value which is based on original value, like the original value is 50, I need use 50*0.8 to replace it. Regular expression is the best choice, which is a Swiss knife for software engineer. But I am shamed to say that I am not familiar with the regular expression. But we have powerful Stackoverflow. I asked a question in this site, Jens A gave me a pretty answer about it soon.

String s = "This is the number 2.5. And this is 7";
s = Regex.Replace(s, @"(\+|-)?\d+(\.\d*)?", m => {return (Double.Parse(m.ToString())*0.8).ToString();});

Tuesday, March 30, 2010

SICP Series-chapter 1.1

In the section, it gives some very basic introduction about the LISP(a familiar of LISP, mainly Schema in this book). Like the basic expression, naming ,environment and other element of language.

1.4. The common lisp has some difference with Schema, so I re-write the small program in the exercise. Actually, you can use the function name as you like, just like the example in the exercise. But in the Common Lisp, if you want to tell the interpreter that a name is a function , you need add a key word function. If you want to call a function based on a symbol, you need use the funcall key word to tell the interpreter, you also can use the #’ to instead of funcall.

(defun a-plus-b-v2 (a b)
   (funcall (if (> b 0)
                 (function +)
               (function -))
           a
           b))

1.5 From the code, you can easily know that the p is a infinite recursive function. If the test function return 0, it means normal order, the p would be evaluated until it’s actually needed.

From the screenshot, we can tell that it’s normal order.

1.6 It would cause a infinite function call.

1.7 According to the exercise, the good-enough? function may cause big problem when the number is very small. From the code we can see that it use the guess number’s square to compare the original number, the comparison number is o.oo1. When the number is larger, it’s ok. But when the number is very small, like 0.06 or 0.005, it would cause big inaccuracy. In order to decrease the inaccuracy, there is a strategy that compare last iteration’s guess with current guess.

(defun sqrt-iter(guess x)
   (let (improveguess (improve guess x))
       (if (good-enoughp guess improveguess)
           improveguess
           (sqrt-iter (improve improveguess x)
                       x))))

(defun improve (guess x)
   (average guess (/ x guess)))

(defun average (x y)
   (/ (+ x y) 2))

(defun good-enoughpv2 (guess x)
   (let (temp (/ guess x))
       (and (> temp 0.99) (< temp 1.01))))

(defun sqrtv(x)
   (sqrt-iter 1.0 x))
1.8 This is the same as the example in the textbook. The only different is the improve-guess function

Structure and Interpretation of Computer Programs Note Series

I have mentioned in my previous post that I have two goals this year, one is to build a simple compiler, another one is to write a LISP interpreter using LISP. I am learning the compiler principle now. It’s time to start my second goal. I am always willing to learn the Common Lisp. I have been learning it from last year, but I am just reading some manuals and some articles. SICP is a an excellent book about the LISP, not only the language itself, but also some great minds about computer science. Doing the excises and writing a small interpreter just like the Register Machine in chapter 5 is a good path to master this language and learn those great minds.

Structure and Interpretation of Computer Programs is a great book which are used by many universities as textbook published by MIT. But, recently, MIT uses the Python to replace the LISP in his course.The language used in this book is a dialect of LISP called Schema, I will use the Common Lisp in this note series. (Actually, clisp)

Monday, March 29, 2010

Different about DateDiff between SSMS and ReportBuilder

Recently, I am building a report using the SQL Server reporting service. I met a problem about datediff. There are two datetime values 2010-04-23 08:00:00 and 2010-04-22 17:00:00. If you use the TSQL built-in function DATEDIFF to check the value in SQL Server Management Studio like below:

DATEDIFF(d,'2010-04-23 08:00:00','2010-04-22 17:00:00')

You would get the -1.
But, if you use the DATEDIFF in the ReportBuilder, it would return 0. I guess that Within SSMS if you cross midnight you have triggered a day boundary so it get -1. in ReportBuilder it is looking for 24 hours to be between the two values so it gets 0.

Sunday, March 28, 2010

民国老课本

在《读库1001》上，邓康延有篇文章，叫《老课本》，这篇文章带我们阅览了民国的小学课本。民国时期，任何人都可以出版小学课本，此文中展示的课本是由蔡元培，张元济编撰的。一个是北大校长，近代最为杰出的教育家，一个是商务印书馆的创始人，大师编小书，并没有大材小用之感，反而见其远见与慎重。在那风云会际的年代，课本上没有民族国家，没有道德说教，没有千年文化，也没有万里河山。有的只是简单直白的一花一木，一针一线，仁爱，谦让，诚信，友爱，都在每一页上哪寥寥数语中显示出来。每一页，都是上面是一幅精美的黑白插图，下面是隽永的小楷的数排文字。中间间或有几张彩色的插页，历经九十多年，依然颜色鲜艳。较之我辈曾经读过的课本，和现在林林总总的课本，不是好上多少倍。

Saturday, March 27, 2010

Building a simple compiler series(7)

Last post, I have a brief introduction about the Lex, and gave a simple example. Lex is a important tool for me to achieve my goal, so I want to say more about this tool.

Regular expressions in Lex

A regular expression is a pattern description using a meta language. An expression is made up of symbols. Normal symbols are characters and numbers, but there are other symbols that have special meaning in Lex. Below are some symbols and definitions about the regular expression in Lex.(These tables come from here)

Character	Meaning
A-Z, 0-9, a-z	Characters and numbers that form part of the pattern.
.	Matches any character except \n.
-	Used to denote range. Example: A-Z implies all characters from A to Z.
[ ]	A character class. Matches any character in the brackets. If the first character is ^ then it indicates a negation pattern. Example: [abC] matches either of a, b, and C.
*	Match zero or more occurrences of the preceding pattern.
+	Matches one or more occurrences of the preceding pattern.
?	Matches zero or one occurrences of the preceding pattern.
$	Matches end of line as the last character of the pattern.
{ }	Indicates how many times a pattern can be present. Example: A{1,3} implies one or three occurrences of A may be present.
\	Used to escape meta characters. Also used to remove the special meaning of characters as defined in this table.
^	Negation.
\|	Logical OR between expressions.
"<some symbols>"	Literal meanings of characters. Meta characters hold.
/	Look ahead. Matches the preceding pattern only if followed by the succeeding expression. Example: A0/1 matches A0 only if A01 is the input.
( )	Groups a series of regular expressions.

Tokens in Lex are similar to variable names in C language. Each token has its own expression.

Token	Associated expression	Meaning
number	([0-9])+	1 or more occurrences of a digit
chars	[A-Za-z]	Any character
blank	" "	A blank space
word	(chars)+	1 or more occurrences of chars
variable	(chars)+(number)(chars)( number)*	Â

The internal variables and functions in Lex

yyin	Of the type FILE*. This points to the current file being parsed by the lexer.
yyout	Of the type FILE*. This points to the location where the output of the lexer will be written. By default, both yyin and yyout point to standard input and output.
yytext	The text of the matched pattern is stored in this variable (char*).
yyleng	Gives the length of the matched pattern.
yylineno	Provides current line number information. (May or may not be supported by the lexer.)

yylex()	The function that starts the analysis. It is automatically generated by Lex.
yywrap()	This function is called when end of file (or input) is encountered. If this function returns 1, the parsing stops. So, this can be used to parse multiple files. Code can be written in the third section, which will allow multiple files to be parsed. The strategy is to make yyin file pointer (see the preceding table) point to a different file until all the files are parsed. At the end, yywrap() can return 1 to indicate end of parsing.
yyless(int n)	This function can be used to push back all but first Â‘nÂ’ characters of the read token.
yymore()	This function tells the lexer to append the next token to the current token.

Lex declarations

In the definition section, you not only can add C variables, but also you can add the lex declarations like below:

%{
int wordCount = 0;
%}
chars [A-za-z\_\'\.\"]
numbers ([0-9])+
delim [" "\n\t]
whitespace {delim}+
words {chars}+
%%

The content of test file.

The result

2015

不知道什么时候，Twitter上2015成了一个热门词汇，大有取代1984的劲头，从网上转点喜闻乐见的东西：

2015年，我到和菜头家里做客，看到地板上的网线和正在闪烁的路由器，我大喜过望。“想不到你家里还能…！”此时菜头夫人在一旁说：“这是一毛不拔送的新款灯具，完全模拟有互联网的日子。” （作者：王佩）
2015年，我到王佩家里做客，看到他正打开twiiter，我大喜过望。“想不到你家里还能…”此时王夫人在一旁说：“这是我们家的局域网，我们互Follow，完全模拟有twitter的日子”。（作者：连岳）
2015年，我到一毛不拔家里做客，看到电脑里的纳斯塔客和纽约股市行情，我大喜过望。“想不到你家里还能…！”此时一毛不拔夫人在一旁说：“自从不能炒美股后，一毛不拔就疯了，这是医生吩咐道的，完全模拟有互联网的日子。”（作者：莫之许）
2015年，我到莫之许家里做客，看到彪形大汉保镖与停在草坪的总统座机，我大喜过望：“想不到你真的成了…”此时莫之许夫人在一旁说：“保镖是在劳务市场雇来的，座机是充气模型，完全模拟奥巴马的日子。”（作者：宋石男）
2015年，我到宋石男家里做客，看到林志玲躺在他的床上，我大喜过望：“想不到你真的搞了…”此时宋夫人在一旁说：“这是莫之许买充气总统座机的赠品，完全模拟有林志玲日的日子。” （作者：抑扬）
2015年，我到方滨兴家做客，看到搜索天安门居然页面被重置了。我大惊失色，“你……怎么还会被墙？！”方夫人说，自从GFW被推倒后，他就疯了，这是他自己在家里搭的，完全模拟有墙的日子。（作者：photoxu）
@wenyunchao: 2015年，我到笑蜀家做家，看到他桌面放着《南方周末》，我大惊失色，“你，你们家怎么还有这个？”笑蜀夫人说，自从《南方周末》被关闭后，笑蜀就疯了，她不得不找人印份只有一个读者的报纸，还告诉他改月报了，不然印不起。
@shourou 2015年，我到李长江家作客，看见他孙子正喂他喝三鹿，我当时就震惊了。“怎么你还喝…？”他孙子抬头说：“有人高价收购我爷爷的肾结石，所以我现在要用最好最快的方法生产。” #2015
@doubleaf: 2015年，我探望李毅中。看见一老年男子在书桌前签署关闭网站的命令。我大惊失色：现在居然还有网站可关闭？不是早全国断网了吗？李夫人说：自从所有网站关闭后，老李就失业了，整天闷闷不乐，这是他自己攒下以前的文件，没事签着过瘾的。
RT @baozuitun RT @adingwang: #2015 年，我到@luoyonghao 罗永浩家做客，门开了，开门的是是是是曾轶可
RT @cloudymount: RT @digitalboy: #2015 6月4日随着海底光缆的切断，方兴滨失业，在抗议之后移民香港，当天他在博客写到：欢迎来到我在中国的新家。
RT @wuquan: RT @pufei: 2015年，全球共产党国家网络管制会议召开，会议口号为：同一个共党，同一堵高墙。 #2015
RT @lianyue: 中宣部最新禁令：媒体严禁炒作2015话题，以新华社通稿为准。

“博士”

《Friends》里面的Rose是古生物学博士，他的父亲每次提到自己的儿子的时候，都会很自豪的加上Doctor这个称号。作为和谐社会的主流电视台的热播情景喜剧，代表着西方民众的主流价值观，由此可见，博士这个称号，也许不是一个褒义词，但至少不是一个贬义词。但在中国这个神奇的土地上，博士这个词语似乎有着超出学术范畴的社会内涵，特别是女博士，有的时候甚至成为了一种嘲弄的词汇。
在中国读博士就是一件比较高风险的事情。中国高等教育培养的人才呈现一种下降的趋势，本科生好于硕士研究生，硕士研究生好于博士研究生。原复旦大学校长杨福家也说过，他能保证复旦大学本科生的质量，无法保证复旦大学研究生的质量。后半句是实话，前半句夸大了。在中国众多的博士当中，除去当初年少无知一不小心直博的，一心只想混个文凭的达官显贵，不想离开学校进入社会的，并非没有一颗红心向太阳，誓把青春热血谱写在实验台上的热血青年。数年寒窗无人问，一朝成名天下知。最终要是能够名利双收，学术上成绩斐然，事业也蒸蒸日上，这就是一个最好的结果，我不知道全国有多少人的结果是这样皆大欢喜。都说社会黑暗，校园是象牙塔，实际上呢？读书人有读书人的玩法，流氓不可怕，就怕流氓有文化。名利双收不了，哪怕是得其中一样，也不枉费了数年的光阴，和当初对理想的追求，怕就怕到时候竹篮打水一场空。多年以来，中国在教育科技上的无所作为，学术腐败，学术丑闻，媚上欺下，早已经使得原本应该受人尊敬，代表社会最高知识阶层的这一群体，渐渐的退去了光环。这样说，对那些沉浸于学术，正直无畏的人来说，是有点不公平的，但是没有办法，他们虽然出淤泥而不染，可社会已经是泥足深陷，他们的声音被众多的呻吟与歇斯底里给掩盖了，只能说声抱歉。
相比与男博士，女博士的境遇要差了许多。近几年，女博士似乎已经成为了灭绝师太的代名词。当听说身边的女性亲朋好友读博士的时候，许多人的第一反应先是惊讶，而后就浮想联翩。女博士要承担的社会压力明显要大的多。首先是学术压力，中国教育的评价体系有点畸形，要是不能够及时的发出相应的论文，就意味着延期，漫漫长路不知道什么时候才是个头。其次是来自家庭的压力，在许多中国的家庭，女性要是过了一定的岁数还未嫁出去，本人也许还未着急，周围的父母，七大姑八大姨早就像热锅上的蚂蚁，每次回家，打电话，主旋律总是围绕了嫁人，当然，这一条并不是对所有人都适用。再次，是社会上的压力，多年以来的这种畸形的观念在蔓延着，若要是给一个有志青年介绍女朋友，告诉他是女博士，不知道有多少人会不为所动。
当一个社会用这样的眼光去看待博士这个群体的时候，究竟是博士这个群体出现了问题，还是这个社会出现了问题？

Friday, March 26, 2010

My favourite web site

If you are asked to list your favourite sites, what would be on that list? YouTube, Facebook, Twitter,…the list would be very very long. With the development of the Internet technology, hardware side and software side, more and more excellent sites emerge. Not only the SNS sites, but also other sites of various fields.The Social Networking Service web sites should be the outstanding representative in those site. The Facebook has more than 400 million users. The Youtube accounts for 7.8% of Network traffic. There are more than 50 million messages sent from Twitter. Many people even live in it.

I can not access those SNS site from my country freely, I can not participate in it, I am not aware of their popularity. But there are still a lot of excellent site I like very much.

Wikipedia Free encyclopedia I can not say more about this site. I love this site most.
Stack Overflow A site for programmer to ask/answer question. I love this site, not only it help solve a lot of problem, but also help me learn a lot of other knowledge.
Coding Horror From the name, you can guess this is a programmer’s site, actually it’s a blog. The author of this blog is very productive.
Google Reader Strictly speaking, it’s not a web site, it’s a service provided by Google. I have more than 100 feeds in it, so you can say I collect more than 100 sites in one site. I like those sites, but I can’t list all of them, so I just give you the Google Reader.
Reddit It’s a social news site. Users can post the links and stories that they want to show and share. You always can find interesting topics here.On the other hand, millions of users help you find the most interesting and attractive topic for you.
Google I do not how many people consider the Google as a site or a service? But i also want to list it here.
Youku/Tudou I can not access the YouTube, I only can choose the local substitute.

Building a simple compiler series(6)

Lexical analyze is a important part in the processing of compiling. If you just want to learn something about the compiler and try to write a simple compiler by yourself, you do not need write a lexical analyzer by yourself. In computer science, there is a program named Lex which is used to generate lexical analyzers. You can find it on many Unix/Linux system you can install the flex using apt-get in Ubuntu, this tool is writen by Eric Schmidt and Mike Lesk. Lex and the parser generator, such as yacc and bison, are used together. The lex is used to provide the tokens for parser.

Structure of a lex file

Definition section
%%
Rules section
%%
C code section

The definition section is the place to define macros and to include the header files. You also can write any C code here.

The rules section is the most important part in the lex file.Patterns are simply regular expressions. When the lex sees some text in the input matching a given pattern, it would execute the C code which is associated to the pattern.

The C code section contains statements and functions.

There are some internal variables and functions which would be used in the lex source file.

yyin yyout yytext yyleng yylineno (Lex Variables)

yylex() yywrap() yyless(int n) yymore()

Here is an simple example which pick all the number from a file

Then create a file containing string mixing character and number. The string is skdj3244sdkfj234kjsdfkl23kjl12

Thursday, March 25, 2010

Bit Reversal

If you do not sleep,chat,eat snack,drink beverage and play your PSP in your Data Structure and Algorithm class, you may be already familiar with the topic I will write. This is the dividing and conquering algorithm. This is a common algorithm that you would see a lot in practice. The essence of it is to make the original problem smaller and smaller until to unit, and solve them individually, then combine the results.

Take the bit reversal as an example, there is x=(abcdefghijk)(each character stands for 1 or 0), reversing the bit means to make the x’=(kjihgfedcba).Keep you mind that we want to reverser the bit in a byte, not reverse the character in s string or an element in a array.

Given abcdefgh
step1 badcfehg
step2 dcbahgfe
step3 hgfedcba

The complexity for it is Ω(logn).
It can reverser the bit (on a 32-bit machine), but there is a problem, For example, the input is 10001111101, it would reverse the whole byte including the heading 0s. The output is 10111110001000000000000000000000.

static int BitReversal(int n)
{
int u0 = 0x55555555; // 01010101010101010101010101010101
int u1 = 0x33333333; // 00110011001100110011001100110011
int u2 = 0x0F0F0F0F; // 00001111000011110000111100001111
int u3 = 0x00FF00FF; // 00000000111111110000000011111111

int x, y, z;
x = n;
y = (x >> 1) & u0;
z = (x & u0) << 1;
x = y | z;

y = (x >> 2) & u1;
z = (x & u1) << 2;
x = y | z;

y = (x >> 4) & u2;
z = (x & u2) << 4;
x = y | z;

y = (x >> 8) & u3;
z = (x & u3) << 8;
x = y | z;

y = (x >> 16) & u4;
z = (x & u4) << 16;
x = y | z;

return x;
}

Yongwei Xing's base with ET