Words of Wisdom 1

Some “words of wisdom” I found during my peregrination in the “World of Books”

• Every thing should be made as simple as possible, but not simpler – Einstein
• Seek Simplicity and distrust it – Alfred N. Whitehead
• Our life is frittered away by details. Simplicity, simplicity, simplicity – Henry D. Thoreau
• There are no small change in a large system – unknown
• KISS: Keep It Simple, Stupid (or Keep It Simple as Stupid)  - unknown
• Fools ignore complexity, pragmatic suffer it, some avoid it, genius remove it – Alan J Perlier

From Foundation of Computer Science

A one I like: "If something must go wrong, it’ll go wrong" – Murphy’s laws
and one from an ex-boss : "A programmer must think to unthinkable" – Willy Kalamba

Discution Question: About Algorithms

 

What makes one algorithm better than another?

To determine which algorithm is better than another, often we compare the efficiency of one or the other. The efficiency of an algorithm is mostly associated to the time the latter takes to perform a task according to the amount "n" of the inputs, but it can also be related to any other computational resources as memory usage, required to perform the task.

Depending about inputs, there are 3 scenarios. Best-Case (input offer optimal condition), Average-Case (input has uniform distribution) and Worst-Case. The worst-case is used to define the upper bound of resource usage with non optimal input and is the most used scenario in algorithm analysis.

For the same problem (and needs), the best algorithm will be the one that will consume less resources than other in worst-case

An example of problem

To illustrate above, let us take the well know sorting list problem, and compare the Merge sort and Timsort algorithm

Merge sort was developed by John Von Neumann in 1945. The unsorted list is split in 2 and each sublists are sorted recursively using the same algorithm until sublist with a length of 0 or 1 is found (sorted). Then each sorted sublist is merged into one list. (The pseudo code can be found at http://en.wikipedia.org/wiki/Merge_sort)

Timsort a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language (Wikipedia, 2011).

Worst-case for both are O(nlogn), but timsort have Θ(n) for best-case and merge sort O(nlogn). This means that timsort and merge sort will have similar behaviour in worst-case but timsort will be more efficient in best case than merge sort.

Why programming is considered as an art

Science (from Latin word scientia meaning knowledge) is more about logical, rational, testable, explainable, reproducible facts that can be expressed in form of statement, laws, theorem etc and form a formal knowledge that can be taught. Science tends to be objective.

Art (from Latin word ars, artis standing for skills) is more about inspiration, creativity, beauty, skills, insight or enlightenment. Art tends to be subjective.

Programming is about solving problem and “teaching” a computer to execute the solution to the problem. One of programming step is the discovery of algorithm that will describe the solution executions steps. And as all discovery and solving problem process, there are no formal procedure that can be entirely applied successfully since the process induce insight, skills that cannot be objectively explained or reproduced, artistic sense, observation, etc. All these elusive qualities found in Art that allows classifying programming as art.

But programming is also science. There are formal procedure, laws, theorems, build from the past experience and knowledge in computer area. Donal Knuth, in 1974, have talked about “Computer programming as an Art” and at my point of view, provide the best description about this duality about programming.

Why neither of the solutions that you provided can be generated with a prescribed methodology

Even if some scientist as Georges Poly (Brookshear,2008, p.216) has tried to formalize the process of solving problem, there are still the insight inherent to creative activity that will “make appear” the solution to solver. For instance, the Tim Peter has taken the performance of insertion sort on best-case and merge sort on worst-case to provide an algorithm that perform efficiently on both case where these two was not competitive. This insight cannot be formalised by procedure known so far.

How do you envision the ways program verification and performance tuning will be accomplished in the future? Will it still be a work of art? Will it always be the result of one's experience?

Computing is augmenting our mind the same way industrial revolution has magnified what hands and arm can do(Moore,2005). In this quest, computer scientists are ultimalty searching for algorithms that could reproduce the solving problem processes (brookshear,2010, p.216). Even if it has been shown to be impossible, this research has produced numerous concepts and tools that help human mind in the process of solving problem, that detect conceptual errors or potentials issues that could arise on runtime in programs.

Based on that and personal observation about computer science evolution, I thinks in the future, program verification and performance tuning will be assisted by computer as done by syntax checker in current IDE with the possibility to automatically apply the best algorithm that suit to a particular context.

But the part of human skills will still be required, unless computer since capture the essence of intuition, enlightenment and dream that is unique (as we know) to human being. So there still be a part of art and experience in this area, even if assisted by computer.

Reference List:

• Aho, A. and Ullman, J.(1992). Foundations of Computer Science,Standford University Infolab [Online] available at : http://infolab.stanford.edu/~ullman/focs.html (Accessed: 24 June 2011
• Brookshear, G. (2008). Computer Science: an overview, 10th edition. Addison Wesley/Pearson.
• Donald Knut (1975),’ Computer Programming as an Art’. Communication of the ACM, Vol 17, number 12 Available at: http://fresh.homeunix.net/~luke/misc/knuth-turingaward.pdf (Accessed: 25 June 2011)
• Carty, j (2006). ‘Lecture 13: Comparing Algorithms: Complexity Theory’, Introduction to Information Technology & Computer Architecture, UCD School of Computer Science and Informatics [online] Available at: http://www.csi.ucd.ie/staff/jcarthy/home/FirstYear/Comp1001-L13.pdf (Accessed: 24 June 2011)
• Moore, J S(2005,Zurich), A Mechanized Program Verifier presented at The Verification Grand Challenge Workshop Zurich October 10--13, 2005 [Online] Austin, University of Texas Available at http://www.cs.utexas.edu/users/moore/publications/zurich-05/talk.html (Accessed: 24 June 2011)
• ‘Art’ (2011) Wikipedia. Available at : http://fr.wikipedia.org/w/index.php?title=Art&oldid=66408714 (Accessed: 25 June 2001)
• ‘Big O notation’ (2011) Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Big_O_notation&oldid=435630524 (Accessed: 25 June 2011)
• ‘Computational complexity theory’ (2011) Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Computational_complexity_theory&oldid=434310477 (Accessed: 25 June 2011)
• ‘Insertion sort’ (2011). Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Insertion_sort&oldid=435838786 (Accessed: 25 June 2011)
• ‘Merge sort’(2011) Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Merge_sort&oldid=436001760 (Accessed: 25 June 2011)
• ‘Science’ (2011), Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Science&oldid=434836180 (Accessed: 25 June 2011)
• ‘Sorting algorithm’(2011) Wikipedia. Available at : http://en.wikipedia.org/w/index.php?title=Sorting_algorithm&oldid=436094070 (Accessed: 25 June 2011)
• ‘Timesort’ (2011), Wikipedia. Available at: http://en.wikipedia.org/w/index.php?title=Timsort&oldid=433057546 (Accessed: 25 June 2011)

Discussion Question: CISC vs RISC

Computer functionalities are tied to it instructions Set (ISA) implemented in it processor. But to be Turing-Complete, a computer must flexible enough to be able to compute anything actually computable. With Stored-Program architecture, also known as Van Neumann architecture, this flexibility has to be done by instructions (program) loaded in memory, only instructions(ISA) required to execute loaded (in memory) program are hardwired into the processor.

early 1960s and onwards, programs was mostly written in Assembly and computers architects tried to fill the semantic gap by designing Instruction Set combined into single instructions that will directly support High Level Language construct and reduce the size of program, main memory access. At this time this design was an important cost saving element. This design is called Complex Instruction Set Computer, due to complex Instruction Set being implemented into the processor.(Wikipedia) However, this design has several side effect, as complications instructions decoding and scheduling, wide variation of required number of clock(Dandamudi,2005,p39).

For these and other reasons, in the early 1980s designers started looking at simple Instruction Set Architecture that produce instruction sets with far fewer instructions and they coined as opposite to CISC the term Reduced Instruction Set Computer (RISC). Despite the term will induce, the RISC goal was not to reduce the number of instructions, but the complexity. (Dandamudi, Sivarama,2005,p39).

Difference between these Two architectures can be illustrated by the table from http://arstechnica.com

CISC	RISC
Performance Strategies
Complexity from software to hardware. Decreased code size, high Cycle Per Instruction.	Complexity from hardware to software Low Cycle Per Instruction, increased code size.
Design
Instructions for performing basic, complex, and multi-cycle tasks. Memory-to-memory addressing modes. Microcode control unit. Fewer register	Instructions that perform only basic functions.  Simple addressing modes. Register-to-Register Operations. Direct execution control unit. Many register Pipelined execution to lower CPI.

(Ars Technica, 2004)

Even if, since initial research and subsequent commercialisation in the late 1970s and early 1980s, RISC design has dominated the field of computer architecture, The widespread of CISC into desktop and server computing was more due to market share being hold by earlier x86 intel’s processor RISC design was very attractive for power server, mobile and embedded device.

To summarize, CISC originate from memory cost saving need and move instructions complexities to the hardware, but encounter several performance issues sorted out by RISC. With today technologies, CISC are mainly kept for compatibility reason, but include many of solution provided by RISC. RISC is becoming more complex than before and using some of technique used to improve CISC. All these make the distinction between these two designs irrelevant. However, it should be noted that RISC still retain some important single-cycle instructions Register-to-register and load/store architecture and a large number of general purpose registers.

As stated by Michael S. Schlansker and B. Ramakrishna Rau, the computer industry has grown accustomed to, and take for granted, increase of microprocessor performance, without requiring a rewriting or recompiling of the program.(Schlansker and Ramakrishna,2000,p.1). Also the any future ISA must take this fact in account. One of the IAS that will replace CISC and RISC, could be based on parallel computing as Explicitly Parallel Instruction Computing from HP and Intel.

Reference List

• Ars Technica, (2004) RISC vs. CISC: the Post-RISC Era Available At: http://arstechnica.com/cpu/4q99/risc-cisc/rvc-5.html#Branch
• Brookshear, Computer Science an overview 10^th Edn. Addison-Wesley
• Page D.(2009) Practical Introduction to Computer Architecture, London : Springer London, 2009. Liverpool University Librairie
• Dandamudi, Sivarama P .(2005) Guide to RISC Processors for programmers and engineers, New York, NY : Springer Science+Business Media, Inc., 2005. Liverpool University Librairie
• Schlansker, M. S and Ramakrishna Rau(2000), EPIC: An Architecture for Instruction-Level Parallel Processors, HP [Online] Available at: http://www.hpl.hp.com/techreports/1999/HPL-1999-111.pdf.
• Wikipedia, (2011) Reduced instruction set computing Available at: http://en.wikipedia.org/wiki/Reduced_instruction_set_computing (Accessed:06-09-2011)
• Wikipedia, (2011) Complex instruction set computing Available at: http://en.wikipedia.org/wiki/Complex_instruction_set_computer (Accessed:06-09-2011)

What a name? Thegmp c koi ca

Un jour (+ de 10 ans de cela un ami a moi), Daniel, me posa la question de savoir quels étaient mes langages de programmations favoris.

A l'époque c'était le Php, le Visual Basic et l'ActionScript (pas tellement un langage, mais bon...). Je ne sais pas comment, mais cela lui fit penser au grand méchant loup et les trois petits cochon. Et par analogie, il me baptisa (the) Grand Méchant Programmeur et les trois petits langages. Depuis c’est mon surnom préféré.

Thanks Daniel.