Begin to Read The Art of Computer Programming

I baugh the book more than one year ago. Due to busy development work and other stuff to learn, I have not read it. Now it is time for me to read this great book. I will write notes when reading it.

Reading of Programming Language Pragmatics

After more than a year, I have finally finished reading PLP 2e. It is a wonderful book. Every programmer who want a complete and deep of programming language theory should read it. It teaches you compiler techniques. But unlike the dragon book which is for writing compilers, it teaches you the compiler concepts.

The book is written by Miachael Scott who is academic. I like his writing style, succint and precise. For one sentence of his writing, I often need a page to describe it. After his writing has a academic flavor, it is easy for non-academics to understand.

But there are two problems with this book. Only an instructor using this book can obtain the solutions to the exercises in the book. As a software professional outside of schools, I am not entitled to get these solutions. It is really frustrated if I can't solve one exercise and can't get the solution provided by the author. As a result, I did not do the exercises in the book.

The other problem is that the author often mention some technique in a short sentence. I often need some considerable time to understand the sentence because I am teaching myself.

During the reading of this book, I find some bugs of the book. I have emailed to the author. The author has listed these bugs in the errdata page.

Seeking in PrintStream

I played with maven today. I found the following output message when maven is downloading something. The xxx changes to indicate the download progress.

xxx/yyyK

I am curious about how this is done. As far as I know, System.out is PrintStream. In PrintStream, there is no method to seek. I searched for the answer on the web. Unfortunately, I can't find the answer. I downloaded the maven source code. After some browsing, I found that printing \r will position the following printings at the beginning of a line. The following Java code shows how it is done.

import java.io.PrintStream;

public class Print {

    public static void main(String[] args) {
        PrintStream ps = System.out;        
        ps.print("100");
        sleep2s();
        ps.print("\r200");
        sleep2s();
        ps.print("\r300");
    }

    private static void sleep2s() {
        try {
            Thread.sleep(2 * 2000);
        } catch (InterruptedException ie) {
            throw new RuntimeException(ie);
        }
    }
}

I think that Javadoc should have documented this kind of usage, which can save developers a lot of time to scratch their heads.

Install PHP 5.2.9-2 (Windows)

I have already had Apache 2.2 installed.

• Download php-5.2.9-2-Win32.zip. Extract it to C:/free/php


• Make a copy of php.ini-dist and rename it to php.ini


• Add the following text to C:/free/Apache2.2/conf/httpd.conf



#load the php main library to avoid dll hell
Loadfile "C:/free/php/php5ts.dll"

#load the sapi so that apache can use php
LoadModule php5_module "C:/free/php/php5apache2_2.dll"

#set the php.ini location so that you don't have to waste time guessing where it is
PHPIniDir "C:/free/php"

#Hook the php file extensions, notice that Addtype is NOT USED, since that's just stupid
AddHandler application/x-httpd-php .php
AddHandler application/x-httpd-php-source .phps

Opening PDF files within Firefox

I can't open pdf files side Firefox recently. I am using Firefox 3 on Windows XP.

After done some googling, I found
Opening PDF files within Firefox which provides a complete solution of this problem. The following method works for me.

   1. Close Firefox.
   2. Navigate to my Firefox profile folder.
   3. Delete the mimetypes.rdf file.
   4. Restart Firefox.

For how to find profile folder, refer to to How to find your profile.

Handle Multi-key to One-value Property File

One of my friend asked how to implement a configuration file which contains key to value mappings. One special thing is that multiple keys are mapped to one value. If Java property is used, the following text shows the property file.

# [v1]
K11=v1
K12=v1
K13=v1

# [v2]
K21=v2
K22=v2
K23=v2

# [v2]
K31=v3
K32=v3
K33=v3

It contains a lot of duplications. v1, v2 and v3 appears many times in the property file. DIY (Don't Repeat Yourself) principle is violated. One improvement is to write the following property file:

# [v1]
K11,K12,K13 = v1

# [v2]
K21, K22, K23 = v2

# [v2]
K31, K32, K33 = v3

For this property file, I need to write additional code. The following steps are one option:

• get the entry set from the property file


• create a hash map


• iterate over the entry set. k is the map entry key, v is the map entry value




• split the iterated k with , into key[]


• add (key[0], v), (key[1], v), ... to the hash map

After the above steps done, the hash map can be used to get a value for a given key. There still one problem. The property file and the Java code are separated. Then I thought about Scheme. Here is the solution in Scheme. It is tested on DrScheme, version 4.1.4.

#lang scheme
(define (find-value k)
   (let* ([ks2v '(

; multi-key to one-value mappings
((K11 K12 K13) V1)
((K21 K22 K23 K24) V2)
((K31 K32 K33 K34) V3)

                 )]
         [contain? (lambda (k keys)
                (let ([equal2k? (lambda (a) (equal? k a))])
                  (ormap equal2k? keys)))]
         [k2v (lambda (pair)
                 (if (contain? k (car pair))
                     (cadr pair)
                     #f))])
     (ormap k2v ks2v)))

This solution is elegant. Code as data characteristic of Scheme makes such kind of solutions possible. And when I was coding this solution, I had the same feeling as the quote SQL, Lisp, and Haskell are the only programming languages that I've seen where one spends more time thinking than typing.

Disable Translating Chinese Character into Character Entities in Tidy and Xmllint

For Tidy, set char-encoding to raw. The following text is my setting.

tidy -q --char-encoding raw -indent --show-warnings n --tidy-mark n -w 80

For xmllint, set encode to UTF-8 (The encoding of my XML files is UTF-8). Here is my xmllint setting.

xmllint --encode UTF-8 --format

Building DSL with Scheme

I have listened a talk made by Shriram Krishnamurthi. It is called The Swine Before Perl . The talk is about using scheme to do heavy lifting which other languages can't handle. It is a great talk. It shows me the real amazing strength of Scheme programming language. Shriram centers his talk around an example of automaton. The Scheme source code is based on the old version of PLT Scheme. As a result, the source code can't run against the current implementation. I have made a little change to the source code. I post it here for reference.

The following source code is tested in DrScheme, version 4.1.4.
The first version of automaton.

#lang slideshow
(define b-machine-states
  '((init (c more))
    (more (a more)
          (d more)
          (r end))
    (end (r end))))

(define (b-machine stream)
  (letrec ([walker (lambda (state stream)
                     (or (empty? stream)
                         (let ([transitions
                                 (cdr (assv state b-machine-states))])
                           (let ([1st (first stream)])
                             (let ([new-state (assv 1st transitions)])
                               (if new-state
                                 (walker (cadr new-state) (rest stream))
                                 false))))))])
    (walker 'init stream)))

(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))

The goto version of automaton.

#lang scheme
(define b-machine
  (letrec ([init
             (lambda (stream)
               (or (empty? stream)
                   (case (first stream)
                     [(c) (more (rest stream))]
                     [else false])))]
           [more
             (lambda (stream)
               (or (empty? stream)
                   (case (first stream)
                     [(a) (more (rest stream))]
                     [(d) (more (rest stream))]
                     [(r) (end (rest stream))]
                     [else false])))]
           [end
             (lambda (stream)
               (or (empty? stream)
                   (case (first stream)
                     [(r) (end (rest stream))]
                     [else false])))])
    init))

(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))

The second version of automaton.

#lang scheme
(define-syntax automaton
  (syntax-rules (-> :)
                [(_ init-state
                    (state : (cndn -> new-state) ...)
                    ...)
                 (letrec ([state
                            (lambda (stream)
                              (or (empty? stream)
                                  (case (first stream)
                                    [cndn (new-state (rest stream))]
                                    ...
                                    [else false])))]
                          ...)
                   init-state)]))

(define b-machine 
  (automaton init
             (init : ((c) -> more))
             (more : ((a) -> more)
                     ((d) -> more)
                     ((r) -> end))
             (end  : ((r) -> end))))



(b-machine '(c a r))
(b-machine '(c a d r))
(b-machine '(c a x))

The following code is really an elegant DSL for automaon.

(automaton init
     (init : ((c) -> more))
     (more : ((a) -> more)
             ((d) -> more)
             ((r) -> end))
     (end  : ((r) -> end)))

I have also implemented the first and goto version of automaton in Ruby.
The first version of automaton in Ruby

$b_machine_states = {
  "init" => {"c" => "more"},
  "more" => {"a" => "more",
             "d" => "more",
             "r" => "end"},
  "end" => {"r" => "end"}}

def walker(state, stream)
  if stream.empty?
    return true
  end
  first = stream[0]
  transitions = $b_machine_states[state]
  new_state = transitions[first]
  if new_state == nil
    return false
  else
    rest = stream[1, stream.length()]
    return walker(new_state, rest)
  end
end

def b_machine(stream)
  walker("init", stream)
end

print b_machine("car") , "\n"
print b_machine("cadr") , "\n"
print b_machine("cax") , "\n"

The goto version of automaton in Ruby

class Automaton
  
  def accept(stream)
    return init(stream)
  end

  private
  def init(stream)
    if stream.empty?
      return true
    end
    first = stream[0]
    case first
    when "c"
      return more(rest(stream))
    else
      false
    end
  end

  def more(stream)
    if stream.empty?
      return true
    end
    first = stream[0]
    case first
    when "a"
      return more(rest(stream))
    when "d"
      return more(rest(stream))
    when "r"
      return terminate(rest(stream))
    else
      return false
    end
  end

  def terminate(stream)
    if stream.empty?
      return true
    end
    first = stream[0]
    case first
    when "r"
      return terminate(rest(stream))
    else
      return false
    end
  end

  def rest(stream)
    return stream[1, stream.length()]
  end
end

auto = Automaton.new()
print auto.accept("car") , "\n"
print auto.accept("cadr") , "\n"
print auto.accept("cax"), "\n"

For the second version of automaton, I can't find a way to implement it in Ruby because Ruby does not have a macro system similar to Scheme. I am happy to know if anyone has a solution.

Add Fonts to Windows Command Line Console

By default, the command line console only has two fonts for Windows XP Simple Chinese version. They are Roster Font and Lucida Console. I am unhappy with them. I like Consolas and Bitstream Vera Sans Mono for command line. So I decided to add these fonts to the command line console. I have done it following Necessary criteria for fonts to be available in a command window. I have added two registry values as shown in the following registry file.

Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Console\TrueTypeFont]
"00"="Consolas"
"000"="Bitstream Vera Sans Mono"

The machine needs to be restarted after adding these stuff to registry. And I need to set the current code page to 437 in Option tab of the command line console shortcut if I want to select Consolas and Bitstream Vesa Sans Mono. The code page 936 does not work for these 2 fonts.

Subroutine Pointer in C

C has subroutine pointers. It does not require closures because it does not have nested scopes and it is static scoped. Every subroutine is at global scope. As a result, the referencing environment for a subroutine is the same whether it is created when the subroutine is first passed a parameter or when the subroutine is finally called. In the following code, plus_one has the same referencing environment whether the referencing environment is created when it is passed as a parameter to caller or when it is called in caller.

#include 
int plus_one(int n) {
    return n + 1;
}
void caller(int (*f) (int)) {
    int result = f(3);
    printf("3 plus 1 is %d\n", result);
}
int main() {
    caller(plus_one);
    return 0;
}

For a language which supports nested scope, the situation is different. In the following Common Lisp code, a closure must be created for plus_2 to make it a function which addes 2 to its sole parameter.

(let ((one 1))
  (defun plus_1 (x)
     (+ x one)))

(let ((one 5))
  (plus_1 3))

Dynamic Scope in LISP

The following program will print (3 5) in newlisp which is dynamic scoped. But it will print (3 7) in CLISP which is static scoped.

(let ((y 7)) (define (scope-test x) (list x y)))
(let ((y 5)) (scope-test 3))

Java's file.encoding property on Windows platfor

This property is used for the default encoding in Java, all readers and writers would default to using this property. file.encoding is set to the default locale of Windows operationg system since Java 1.4.2. System.getProperty("file.encoding") can be used to access this property. Code such as System.setProperty("file.encoding", "UTF-8") can be used to change this property. However, the default encoding can be not changed dynamically even this property can be changed. So the conclusion is that the default encoding can't change after JVM starts. java -dfile.encoding=UTF-8 can be used to set the default encoding when starting a JVM. I have searched for this option Java official documentation. But I can't find it.

Produce the "TeX: The Program" from tex.web

This is how I have produced the TeX: The Program from tex.web

• Install the full package of MikTex 2.7


• Get tex.web from http://www.tug.org/svn/texlive/trunk/Build/source/texk/web2c/tex.web


• Place tex.web in D:/book.


• Open a command console. Change directory to D:/book.


• Make a empty file change-file in the current directory.


• Run "weave tex.web change-file program.tex".


• Run "pdfTex program"

The result is a PDF file program.pdf and CONTENTS.tex. These files are the book.

A Quick Start of SWI-Prolog for Windows

Recently, I have been reading chapter 12 of Programming Language Pragmatics. This chapter is about logic programming. So I need a prolog implementation to try the code in the book. I choose SWI-Prolog. SWI-Prolog has a thorough reference manual. But what I want is only some quick start. After searching on Google, I don't find a decent SWI-Prolog quick start. So I have to do my work by scanning the reference book. It is kind of painful. Here, I write down what I think it is enough to do some simple things with SWI-Prolog, hoping that it will help you if you only do some simple things with SWI-Prolog.

My platform is Windows. After the installation of SWI-Prolog, add the SWI-Prolog bin directory to PATH environment varialbe. In my case, the bin directory is C:\Program Files\pl\bin.

SWI-Prolog has a plwin.exe which is GUI environment for SWI-Prolog. I prefer to use the SWI-Prolog console environment which is plcon.

• Open a command line


• change to directory containing my prolog source code. In my case, it is D:\documents\Prolog.


• type plcon to launch prolog

Now the command console looks as follows.

D:\Documents\Prolog>plcon
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.64)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

1 ?- consult(woman).
% woman compiled 0.00 sec, 1,060 bytes
true.

2 ?-

Type consult(women) to load D:\documents\Prolog\women.pro. It contains the following clauses.

:-dynamic pregnant/.
human(susan).
human(jane).
pregnant(susan).
woman(X) :- pregnant(X), human(X).

Assert can only be used to add facts to dynamic predicates in the prolog interpreter. I want to add facts for predicate pregnant. So I add the dynamic directive in the prolog source code. pregnant/1 is a predicator indicator. A predicate indicator is used to denote predicates. It's form is Name/Arity where Name is an atom denoting the name of a predicate and Arity is a integer denoting the number of its arguments. Add one fact to the prolog clause databse.

2 ?- assert(pregnant(jane)).
true.

Issue a query. Type ; to ask for more answers.

3 ?- woman(X).
X = susan ;
X = jane.

Type halt. to exit SWI-Prolog

4 ?- halt.

Iterator in Icon

In Icon programming language, iterator is very powerful. As a result, Programming Language Pragmatics dedicates a sub section to explain it. The following shows the complete running code corresponding to the code snippets in the book.

procedure main()
 write("=================================================")
 every i := 1 to 10 by 2 do {
  write(i)
 }
 write("=================================================")
 every i := 1 + upto(' ', "a ss ss") do {
  write(i)
 }
 write("=================================================")
 i := 1
 every write(i + upto(' ', "a ss ss"))
 write("=================================================")
 if 2 < 3 then {
  write("2 < 3")
 }
 write("=================================================")
 if (i := find("abc", "abcabcabc")) > 6 then {
  write(i)
 }
 write("=================================================")
 if (i := find("x", "xaax")) = find("x", "bxxx") then {
  write(i)
 } 
end

The following code explains the description at the end of the sub section. It is If the expression following suspend contains an invocation of a generator, then the subroutine will suspend repeatedly, once for each generated value.

# suspend is followed by a value
procedure FollowedByValue()
 i := 1
 while i <= 3 do {
  suspend i
        i +:= 1
 }
end

# suspend is followed by a generator expression
procedure FollowedByGenExpr()
 suspend(1|2|3)
end

# suspend is followed by a generator function invocation
procedure FollowedByGenFuncInvocation()
 suspend FollowedByValue() 
end

procedure main()
 write("=================================================")
 every write(FollowedByValue())
 write("=================================================")
 every write(FollowedByGenExpr())
 write("=================================================")
 every write(FollowedByGenFuncInvocation())
end

Iterator in Ruby and Python

Unlike Java, both languages support real iterator not just iterator object. The following code shows how to create and use iterator in Python.

def from_1_to_5():
  for i in [1, 2, 3, 4, 5]:
    yield i

for num in from_1_to_5():
  print num

The following code shows how to make it in Ruby. Desides a style similar to Python, Ruby can use iterator with block.

def iterator
  for i in [1, 2, 3, 4, 5]
    yield(i)
  end 
end

# invoke iterator in a way similar to Python
call_block do |num|
  puts "#{num}"
end
  
# invoke iterator with the use of block 
call_block { |num| puts "#{num}" }

Accumulator Generator in Common Lisp

The following code helps me understand Accumulator Generator in Common Lisp. I am still not used to lisp's true meaning. I often need to struggle to understand a little piece of lisp code. So I write down the code.

(defun foo (n) (lambda (i) (incf n i)))
(setq starting 10)
(setq acc (foo starting))
(funcall acc 1)

For a complete description of Accumulator Generator, refer to Accumulator Generator

"define-syntax" and "syntax-rules" in Scheme

Scheme has a macro mechanism which allow us to extend the Scheme language syntax. The description in Revised5 Report on the Algorithmic Language Scheme is precise. But the description has a mathematical flavor.

I refer to the book The Scheme Programming Language. It uses the following example to explain "define-syntax" and "syntax-rules". The following code is to define let. let is defined as (let <bindings> <body>) in Revised5 Report on the Algorithmic Language Scheme.

(define-syntax let
  (syntax-rules ()
    ((_ ((x v) ...) e1 e2 ...)
     ((lambda (x ...) e1 e2 ...) v ...))))

I still find the description hard for me to understand because I am very new to Scheme. After some time of struggling, I find the following way to understand it. (let <bindings> <body>) is just like a function invocation. bindings create a local binding scope. In some sense, it binds formal parameters to actual parameters. Take (let ((x 1) (y 2)) (+ x y)) as an example, x is bound to 1 and is bound to 2. body is just like the body of an function. (+ x y) will produce 3.

Back to the "define-syntax" example, we see that ((lambda (x ...) e1 e2 ...) v ...) define what we have described as function invocation. For (_ ((x v) ...) e1 e2 ...), we can see that (x v) indicate a binding. ((x v) ...) indicates any number of bindings. e1 indicates a expression in the body. e1 e2 ... indicates all the expressions in the body.

Great Programming Book

This book (Programming Language Pragmatics) by Scott is really great. Everyone who want to have a complete and deep understanding of programming languages should read this book. I bought this book from US. It costs me more than $60 which is a big amount for a Chinese citizen. Although I have not finished it yet, this book has taught me much.