2011-02-05

T-ara - Bo Peep Bo Peep & 王彩樺 - 保庇

“T-ara - Bo Peep Bo Peep” amazon
“保庇 (BOBEE)” - 王彩樺

for lyrics, info, videos of other versions, see: http://xahlee.org/music/bo_peep.html

Guy Steele on Parallel Programing

Perm url with updates: http://xahlee.org/comp/Guy_Steele_parallel_computing.html

Guy Steele on Parallel Programing

Xah Lee, 2011-02-05, 2011-02-06

A fascinating talk by the computer scientist Guy Steele. (popularly known as one of the author of Scheme Lisp)

How to Think about Parallel Programming: Not! (2011-01-14) By Guy Steele. @ Source www.infoq.com

The talk is a bit long, at 70 minutes. The first 26 minutes he goes thru 2 computer programs written for 1970s machines. It's quite interesting to see how software on punch card works. For most of us, we've never seen a punch card. He goes thru it “line by line”, actually “hole by hole”. Watching it, it gives you a sense of how computers are like in the 1970s.

At 00:27, he starts talking about “automating resource management”, and quickly to the main point of his talk, as in the title, about what sort of programing paradigms are good for parallel programing. Here, parallel programing means solving a problem by utilizing multiple CPU or nodes (as in clusters or grid). This is important today, because CPU don't get much faster anymore; instead, each computer is getting more CPU (multi-core).

In the rest 40 min of the talk, he steps thru 2 programs that solve a simple problem of splitting a sentence into words. First program is typical procedural style, using do-loop (accumulator). The second program is written in his language Fortress, using functional style. He then summarizes a few key problems with traditional programing patterns, and itemize a few functional programing patterns that he thinks is critical for programing languages to automate parallel computing.

In summary, as a premise, he believes that programers should not worry about parallelism at all, but the programing language should automatically do it. Then, he illustrates that there are few programing patterns that we must stop using, because if you do write your code in such paradigm, then it would be very hard to parallelize the code, either manually or by machine AI.

If you are a functional programer and read FP news in the last couple of years, his talk doesn't seem much new. However, i find it very interesting, because:

  • ① This is the first time i see Guy Steele talk. He talks slightly fast. Very bright guy.
  • ② The detailed discussion of punch card code on 1970s machine is quite a eye-opener for those of us who haven't been there.
  • ③ You get to see Fortress code, and its use of fancy unicode chars.
  • ④ Thru the latter half of talk, you get a concrete sense of some critical “do's & don'ts” in coding paradigms about what makes automated parallel programing possible or impossible.

In much of 2000s, i did not understand why compilers couldn't just automatically do parallelism. My thought have always been that a piece of code is just a concrete specification of algorithm and machine hardware is irrelevant. But i realized, that any concrete specification of algorithm is specific to a particular hardware, by nature. (See: Why Must Software Be Rewritten For Multi-Core Processors?.)

Parallel Computing vs Concurrency Problems

Note that parallel programing and concurrency problem are not the same thing.

Parallel programing is about writing code that can use multiple CPU. Concurrency problems is about problems of concurrent computations using the same resource or time (e.g. race condition, file locking). See: Parallel computingConcurrency (computer science)

Elegant Functional Style ≠ Automatic Parallelism

I've been doing functional programing for about 17 years (since 1993), pretty much ever since i started programing with my first language Mathematica. One paradigm i use frequently, is sequencing functions, aka chaining functions, piping, fold, nest. In some sense, most of my programs is one single sequence of function chain. The input is feed to a function, then its output to another, then another, until the last function spits out the desired output. It is extremely elegant, no state whatsoever, and often i even take the extra mile to avoid using any local temp variables or constants in my functions. But after watching this video, i learned, that function chaining is NOT good for parallelism, despite it is considered a very elegant functional paradigm.

As a functional programer, typically we are familiar with all the FP style constructs, and we strive for such elegance. The important thing i learned from this video is that, elegance in functional style does not mean it will be good for parallelism. Similarly, software written with purely functional language such as Haskell, does not imply it'll be good for parallelism. (but will be a lot better than procedural langs, of course.) FP and Automatic Parallelism certainly share some aspects, such as declarative code and not maintaing states, but is not the same issue.

Here's a few properties of functions he think it's important for automatic parallelism . (if you haven't watched the whole video carefully, you probably won't understand it because it's out of context. I'm listing them here for myself too)

  • Associativity . (grouping doesn't matter) e.g. ((a ⊕ b) ⊕ c) == (a ⊕ (b ⊕ c))
  • Commutativity . (order doesn't matter.) e.g. (a ⊕ b) == (b ⊕ a)
  • Idempotent
  • Identity
  • Zero

Here's things you should avoid, from his slide:

  • DO loops.
  • linear linked list
  • Java style iterator.
  • even arrays are suspect.
  • as soon as you say “fist, SUM = 0” you are hosed.
  • accumulators are BAD. They encourage sequential dependence and tempt you to use non-associative updates.
  • If you say, “process sub-problems in order,” you lose.
  • The great tricks of the sequential past WON'T WORK.
  • The programing idioms that have become second nature to us as everyday tools for the last 50 years WON'T WORK.

Conclusion:

  • A program organized according to linear problem decomposition principles can be really hard to parallelize. (e.g. accumulator, do loop)
  • A program organized according to independence and divide-and-conquer principles is easy to run in parallel or sequentially, according to available resources.
  • The new strategy has costs and overheads. They will be reduced over time but will not disappear.
  • in a world of parallel computers of wildly varying sizes, this is our only hope for program portability in the future.
  • Better language design can encourage “independent thinking” that allows parallel computers to run programs effectively.

Here's a paper written by Guy Steele in 2009, which kinda summarize the points in this talk. (requires lisp knowledge to understand)

Organizing Functional Code for Parallel Execution “or, foldl and foldr Considered Slightly Harmful”. (2009-08) Guy Steele. @ Source labs.oracle.com

Fortress & Unicode

It's interesting that Fortress language freely uses unicode chars. For example, list delimiters are not the typical curly bracket {1,2,3} or square bracket [1,2,3], but the unicode angle bracket ⟨1,2,3⟩. (See: Matching Brackets in Unicode.) It also uses the circle plus ⊕ as operator. (See: Math Symbols in Unicode.)

I really appreciate such use of unicode. The tradition of sticking to the 95 chars in ASCII of 1960s is extremely limiting. It creates complex problems manifested in:

All these problems occur because we are jamming so many meanings into about 20 symbols in ASCII.

See also:

Also, most of today's languages do not support unicode in function or variable names, so you can forget about using unicode in variable names (e.g. α=3) or function names (e.g. “lambda” as “λ” or “function” as “ƒ”), or defining your own operators (e.g. “⊕”). (Exceptions i know that works well in practice are: Mathematica, Javascript, Java, Emacs Lisp. See: Unicode Support in Ruby, Perl, Python, Emacs Lisp.)

2011-02-03

mandelbrot set simply explained with video

Perm url with updates: http://xahlee.org/cmaci/fractal/mandelbrot.html

Mandelbrot Set Basic Tutorial (no complex number needed)

Xah Lee, 2006-05, 2011-02-03

This page gives a easy-to-understand explanation of the Mandelbrot Set fractal without using complex numbers.

Formula

The Mandelbrot Set is defined as follows. Define a function f to be this formula:

f[{a_, b_}] := {a*a - b*b + c1, 2*a*b + c2}

The a, b, c1, c2 are (real) numbers, and c1 and c2 are fixed numbers (constants).

For example, if we set c1=0 and c2=0, then the formula becomes:

f[{a_,b_}] := {a * a - b * b , 2 * a * b}

and then f[{3,4}] evaluates to {-7,24}.

The input is a pair of numbers, and output is also a pair of numbers. You can plot them as points on the plane. You can think of these numbers as vectors.

Iteration of Formula

For each point {c1,c2} in the plane, let's compute the recursion (nesting) of f, starting inital input {0,0}. That is, we compute f[f[f[…f[{0,0}]…]]].

If this infinite recursion creates a resulting point further and further from the point {0,0} in a way that it eventually can pass any circle centered on {0,0} however large, then we say that the number {c1,c2} escapes. We define the Mandelbrot set as the set of points that do NOT escape.

For example, suppose {c1,c2} is {3,4}. So, the first iteration is to compute f[{0,0}]. We get {3,4}. Then we compute f[{3,4}], we get {-4,28}. Then f[{-4,28}] is {-765,-220}. The sequence we get for first 5 steps this:

{ {3, 4}, {-4, 28}, {-765, -220}, {536828, 336604}, {174882048771, 361396904228}}

By looking at the formula, you can see that it just gets larger and larger. So, the point {3,4} escapes, thus is NOT a member of the Mandelbrot set.

Now, if we set {c1,c2} to be {0.1,0.1}, the first 5 steps is:

{ {0.1, 0.1}, {0.1, 0.12}, {0.0956, 0.124}, {0.0937634, 0.123709}, {0.0934877, 0.123199}}

The first number clearly decreases slowly, but the second number increases slowly. One can prove that if we continue the computation forever, the point does NOT escape, thus {0.1,0.1} is a point in the Mandelbrot set.

Plot of Mandelbrot Set

To plot the set, we have to compute all possible point in the plane. For each point {c1,c2}, we have to compute f infinitely many times. For practical purposes, let's just say we do one thousand steps for each point. If it gets large, we color the point white, otherwise black.

Here's a plot. The black colored region are points in the Mandelbrot set.

the Mandelbrot set

A plot of the mandelbrot set.

You get this weird-looking ass-shaped thing. And, see those weird-looking jagged edges? That's the fascinating aspect about the Mandelbrot set. If you zoom in, you'll see that this weird-looking jagged edge is never smooth no matter what magnification, and the pattern of this ass-shape seem to repeat at random places forever, yet not in some particular predictable ordered fashion.

In the above animation, you can see this weird pattern. The Mandelbrot set is usually plotted with color. A typical coloring scheme (used in the above animation) is to color a point by how fast the point {c1,c2} escapes.

The following is another zoom-in animation at a different point. Supposedly it's the deepest zoom-in animation on record. It's computed on a machine with 12 CPU, for 6 months, in 2010.

“Deepest Mandelbrot Set Zoom Animation ever - a New Record! 10^275 (2.1E275 or 2^915)”

Mandelbrot Set Formula with Complex Numbers

The above formula can be expressed in complex numbers. Using complex numbers, the function f is:

f[z_] := z^2+C

For many free software that plots the Mandelbrot set, see: Fractal Software.

Google's Fractal Map

Google made a fractal application, based on Google Maps, at juliamap.googlelabs.com.

Though, am rather disappointed. When you zoom in just a few steps, the iteration does not automatically increase enough to get crispy edges.

Much better are some dedicated fractal apps. See: Great Fractal Software.

For a basic explanation of the mandelbrot set, see: Mandelbrot Set Basic Tutorial (no complex number needed).

2011-02-02

Google URL Shortening Service Format

Perm url with updates: http://xahlee.org/js/Google_url_shortening.html

Google URL Shortening Service URL Format

Xah Lee, 2011-02-02

Google has a url shortening service, at http://goo.gl/.

Here's some example of url it generates:

• goo.gl/3PrCo ⇒ xahlee.org/comp/FSF_free_beer_free_speech.html
• goo.gl/EH5fn ⇒ xahlee.org/kbd/dvorak_and_all_keyboard_layouts.html
• goo.gl/jzgjD ⇒ xahlee.org/comp/netscape_dot_com_nostalgia.html
• goo.gl/vfsem ⇒ xahlee.org/Periodic_dosage_dir/t2/cherry.html
• goo.gl/uc19a ⇒ xahlee.org/UnixResource_dir/writ/larry_wall_n_cults.html
• goo.gl/WBdW7 ⇒ xahlee.org/js/html5_video_audio.html
• goo.gl/bW0LZ ⇒ xahlee.org/emacs/elisp_all_about_lines.html
• goo.gl/ZPmVY ⇒ xahlee.org/Periodic_dosage_dir/lacru/odalisque.html
• goo.gl/1Zb9s ⇒ xahlee.org/Periodic_dosage_dir/sanga_pemci/hollaback_girl.html
• goo.gl/RvN1E ⇒ xahlee.org/perl-python/system_calls.html
• goo.gl/uXyas ⇒ xahlee.org/comp/netscape_dot_com_nostalgia.html
• goo.gl/Aq3BR ⇒ xahlee.blogspot.com/2011/02/sous-vide-heavy-metal-boredom-habits.html
• goo.gl/VS4X1 ⇒ xahlee.blogspot.com/2011/02/pirated-oreilly-books.html
• goo.gl/FoWLz ⇒ www.reddit.com/r/emacs/comments/fbg4l/ask_remacs_help_me_get_started_with_some_real/
• goo.gl/CfWhQ ⇒ www.reddit.com/r/emacs/comments/fbg4l/ask_remacs_help_me_get_started_with_some_real/

Notice that the format is goo.gl/xxxxx, and the xxxxx is 5 chars. Also, notice that each time you submit, it gives a new short url (if you are logged in). This means multiple short urls maps to the same original url.

There's something i don't understand about it.

The possible chars seem to be digits and english letters, both lower case and upper case. So, that's a total of 10+26+26=62 chars per slot. With 5 slots, the total space is 26^5 = 916.132832 * 10^6. Consider the number of urls that exist, and consider that one url can generate multiple short urls, this does not seem enough.

Also, i think i read somewhere from Google, that the new url is supposedly to be permanent. That is, years later they would return the same original url (assuming Google still lives). So, this means, i can't see how they can maintain this 5 char scheme. Perhaps in the future they might change the 5-slots scheme with more slots or chars.

For each url that exists, perhaps 1 in 1M are actually using url shortening service. So maybe the 5-slots 62 chars scheme would work fine for the foreseeable future.

See also: URL Shortening is BAD.

sous vide, heavy metal, boredom habits

deleted. see here instead: http://xaharts.org/misc/sous_vide_cooking.html

pirated OReilly Books

Discovered that the entire Perl Cookbook is now available online. Originally i thought it's official from O'Reilly, but until trying to announce the url, i realized it's pirated. The site actually contains ~100 O'Reilly books. The url is 〔http://docstore.mik.ua/orelly/〕. Screenshot: . The site is Google ranked at 5. (i discovered it while Google search Perl modules.) I guess the site is making money by the ads.

Ι wonder if O'Reilly knew. Ι hope they can take action, but i guess it's fruitless. Am also guessing that there are probably tens or hundreds of such sites. (they are all over bittorrent anyway.)

See also: Software Freedom is Free Speech or Free Beer?Pathetically Elational Regex Language (PERL).

2011-01-31

Netscape Nostalgia; Code Rush

Perm url with updates: http://xahlee.org/comp/netscape_dot_com_nostalgia.html

Netscape Nostalgia; Code Rush

Xah Lee, 2011-01-31

A documentary film “Code Rush”, on Netscape 1998. Ahh... the dot com, nostalgia!

“Netscape Mozilla Documentary 1998 - 2000 ProJect Code Rush”

This is the first time i see Jamie Zawinski. Remember, he's famous for being blamed for the Emacs/XEmacs schism. (See: GNU Emacs and Xemacs Schism, by Ben WingMy Experience of Emacs vs XEmacs.) He's also well-known as a coder who developed serious RSI (Repetitive Strain Injury). (See: Celebrity Programers with RSI)

For some dot com nostalgia, see:

SEO copywriter joke ...

There's this tweet going around the net:

So this SEO copywriter walks into a bar, grill, pub, public house, Irish bar, bartender, drinks, beer, wine, liquor, four loko. — Victor Haffling (lahaff) 2011-01-06

The original author seems to be Victor Haffling (lahaff), on 2011-01-06. Screenshot of his tweet:

Chinese Breast Enlargement Vibro-Stimulator

this page's content is removed due to possible incompatibilities with Google's AdSense. For the content, goto http://xahlee.org/funny/chinese_breast_enlarger_ad.html