Mar 13th, Meeting with Darko

1. Shall look up language extensions provided by GHC to address the following problem:

f :: (Eq a, Eq c) => (a -> a & c -> c) -> a -> c -> (a, c)
f g x y = (g x, g y)

g :: (Eq a) => a -> a
g x = x

main = do
    putStrLn $ show $ f g 3 'c'



2. Read the chapter about Univeral Types in TAPL book in order to understand forall tag for type variables in Haskell.

3. Look up semantics on concurrent programs to prepare for the next meeting with Darko.

Tiny Basic Interpreter Working Flow

1. Restructure Interpreter with two parts: 

     a)  Execute the program already stored on the code stack;

     b)  Evaluate the statement input from the Interpreter.

2. Finish the processing rule for INPUT statement.

3. Implement the RUN statement. (Maybe using CEK machine model)

4. Extend the language feature with:

     a)  RUN expr-list

     b)  LIST expr-list

Thoughts about Programming Language Implementation

1. An IDE that distinguishes variables regarding the scopes in which they are defined. This is particularly helpful for functional programs. The idea emerged from one Google Tech Talk on Monads and Gonads.

Better Than Simplex

I. Interior Point Method (by John von Neumann)

II. Ellipsoid Method (by Naum Z. Shor in 1972)

III. Karmarkar's Algorithm (by Narendra Karmarkar in 1984)

Meeting with Deepak

Tasks:

1. Whether interior-point algorithm can work on Max-Plus Polyhedra. Check the book Introduction to Algorithms.

2. Rodriguez-Carbonell's work on invariant generating. Exponential

3. Check the paper introducing Standard Polyhedra for how to generate the convex hull of two polyhedra.

4. For programs with multiple paths, one way to preventing exponential runtime invariant generating is to get the invariant for each conditional path, then combine them along the linear path. (2^k -> k) However, the generated invariant should be weaker than the one using the exponential algorithm. Evaluate how weak this invariant can be.

5. Read the book on Abstract Algebra. See whether I'm comfortable with this mathematical foundation.

6. For the method combining Octagon and Max-Plus Polyhedron, check whether some of the disjunction constraints can subsume others. If so, then by scanning all the generated constraints, we can eliminate some of them to simplify the work.

7. Check Miné's paper:  
          A. Miné. Weakly relational numerical abstract domains. These de doctorat en informatique, École polytechnique, Palaiseau, France, 2004.


------------ Deepak's Follow on --------------------------

If you recall we discussed in the class how abstract interpretation works. Mine's thesis is about using octagonal formulas as the abstract
domain for generating invariants using abstract interpretation.

An interesting thing worth study would be to analyze how Mine' ignores or incorporates the disjunctive behavior potentially arising from
the presence of tests/conditions. As you discussed, we ignore the literal corresponding to the absence of a test when the test
is present. Does that happen in abstract interpretation? I conjecture not, but then why does the abstract interpretation also come
up with a weak invariant? 
 

Talking About The Dark Age

Due to Russell, the dark age of Western Europe is from 6th century A.D. to 10th century A.D. And in a larger view, the so-called Middle Ages are from the falling of the Western Empire until the Renaissance, which last about 1000 years.

During this era, Western Europe suffered from the barbarian invasions from the west and the north, and even the rise of Islam from the south and the east. Civilization was diminished. The Rome law was inherited partly by the papal party, but it banished non-orthodox philosophers, and forbid the teaching of secular knowledge. The persecution on heresies resulted in the spiritual separation among different parts of the former Rome Empire, which benefited the Mohammedans to conquer the small Asian, North Africa, and even Spain.

This is the overview of the dark age. However, there are still many things that I misunderstood before. First, for the rising of the papal power, I used to blame it to the avarice of the popes, whose ambition was to become the new Emperor of the Western Empire. However, due to Russell's talk about that history, the pope of Rome was originally one of the patriarchs of the Rome Empire, with that of Constantinople, Damascus, Alexandria, etc. But it is the only patriarch in the western part. Then in 5th Century A.D., Rome was totally destroyed by Goth. This brought in the time of barbarian invasions to the western Europe, especially the one of Lombard tribes into North Italy. Byzantine army was not able to defend Italy, so the Pope established the alliance with the King of Frank by crowning him as the Emperor of the Holy Rome Empire.

Not very long after that, Lombard was assimilated into Italians, and established the city states in Northern Italy. However, the dispute between Pope and Emperor became more and more severe. And for Lombards, it would be the only hope to be affiliate with Pope if they wanted to secure the freedom of their cities from the Emperor. This caused the Thirty-Year Wars, and Pope side became the ultimate winner. As an offshoot, the papal power reached its zenith.

Second, the persecution towards heretical thoughts at least before 12th Century was not quite severe. People can write their books, and put them into public discussions in order to find the unorthodox portions and recanted them.

Third, the Islam at origin was not quite religious. On the new area they conquered, Muslims didn't oblige other people to become Mohammedans. And those populace can live with peace by submitting a special tribute, which was much less than the tax of the Byzantine Empire. So not only Jews but Christians, especially Arians and Nestorians, welcomed their coming.

Before the reconquering of Spain by Christians, Muslims were quite confident about their religion, and showed their tolerance and appreciation towards secular knowledges, including Persian art and poetry, Greek philosophy and science, Babylonian astrology and alchemy, Indian mathematics and number system, etc. They translated those works into Arabic, and maintained them in colleges and libraries.

Thus, in later time, i.e. 12th Century, when western Europe revived from barbarianism, the scholars started to translate philosophical works from Greek and Arabic into Latin. There were three centers of this translating work -- Constantinople, Palermo, and Toledo. Among them, Toledo in Spain was the most productive one. And since Spain at the time was part of Arab Empire, this work was certainly done by Arabic scholars. In fact, they even established a sort of specific schools doing this job.

So finally, Russell stressed that this era was the fallen time for Western Europe, before which the splendor of Rome Empire and after which the Renaissance. However, both the Arab Empire and Byzantine Empire (i.e. Eastern Empire) conserved the civilization of ancient Greece and Rome, which was transmitted back to Western Europe to be the resource of the resuscitation of civilization. And in a larger sight, China at that time was approximately the Tang and Song Dynasties, which was the zenith of Chinese civilization. And Arab Empire was flourished itself. So the whole world was not that dark actually.

The tragedy is that during the 13th Century, both China and Arab were conquered and destroyed by Mongolian army, leaving Western Europe and Byzantine survived. Arab hasn't recovered from it until now. China was recovered partly, but was not flourished until the communication with western priests in late 16th Century and early 17th Century. This gave the chance for Western Europe to lead the world, and they really achieved.      

Reading A History of Western Philosophy

This July, I plan to finish the book "A History of Western Philosophy" written by Bertrand Rossell. Actually, I've been reading it for almost 3 years. However, hitherto I'm just at half of the book, which is the 10th Century in the medieval world.

During my reading time, I'll try to write some short comments, in order to remind me of some crucial points, and practice my English writing.