A very popular website about The History of Visual Communication recently hit the web. Here's a related one but applied to computer graphics/animation entitled A Critical History of Computer Graphics and Animation.
Wednesday, January 30, 2008
Computer Graphics and Visual Communication
Tuesday, January 29, 2008
Quants
The SocGen Scandal made the news recently shortly after the subprime crisis that affected the stock markets last summer.
Technology Review published an article where it exposes the links between the crisis and the work of financial analysts known as quants and at the same time analyze the implications of the increasing automation of the markets as we approach an era of near real time trading.
Make3D
The good folks of Stanford University came up with a software that converts single images to 3D versions.
From their website:
'Make3D converts your single picture into a 3-D model. It takes a two-dimensional image and creates a three-dimensional "fly around" model, giving the viewers access to the scene's depth and a range of points of view.
It uses powerful machine learning techniques (more details here), to learn the relation between small image patches and their depth and orientation. This allows it to model 3-d structures such as slopes of mountains or branches of trees.
After uploading your image, you can "fly" in the 3-D scene (requires VRML viewer or Adobe Shockwave), or watch a rendered 3-d movie (flash required).'
Official website
Monday, January 28, 2008
Tara Damocles Expedition
Two years in the heart of the Arctic Sea to study and understand climate change phenomena in the higher atitudes. As of september 2006, Tara will be anchored in the arctic pack-ice by 82° north and will be delivered from it nearly two years later after a 1800 kilometer drift. (read online)
Press release
Darfur, Help Spread the Word
Join the 'No More Delays in Darfur' campaign at the Online Action Center in AIUSA.
Thursday, January 24, 2008
Video as Desktop Wallpaper
If you have experienced the DreamScene feature of Windows Vista you know the feeling of having videos displayed on the desktop as a wallpaper; what maybe you don't know is that it is possible to achieve the same in XP. How? Trough the VLC media player. Just go to the 'video' menu, click on the 'wallpaper' option and you are set.
Deep Purple Live
Following last week Led Zeppelin live concert, Portuguese channel RTP2 will broadcast tomorow Deep Purple, one of the precursors of hard rock/heavy metal style in the footsteps of Black Sabbath.
GMail Tip
Here's an interesting GMail tip from digitalalchemy.tv:
Gmail has an interesting quirk where you can add a plus sign (+) after your Gmail address, and it'll still get to your inbox. It's called plus-addressing, and it essentially gives you an unlimited number of e-mail addresses to play with. Here's how it works: say your address is pinkyrocks@gmail.com, and you want to automatically label all work e-mails. Add a plus sign and a phrase to make it pinkyrocks+work@gmail.com and set up a filter to label it work (to access your filters go to Settings->Filters and create a filter for messages addressed to pinkyrocks+work@gmail.com. Then add the label work). (read full article)
Blogger Open Id Support
Blogger now supports openid, which means that we can authenticate with a blog address. Here's the official post from Blogger staff:
After just two short weeks of testing on Blogger in draft, OpenID commenting is now available for all Blogger blogs. This means that your friends and readers can leave authenticated comments on your blog using their blog URLs from OpenID-enabled services such as WordPress.com, LiveJournal, and AOL Journals, or with their AOL/AIM accounts. (more...)
Wednesday, January 23, 2008
Tuesday, January 22, 2008
How to Listen Pandora Outside the United States
The great Pandora.com is blocked from outside the US because of legal issues related with international licenses, but there are ways to overcome this.
One is globalpandora.com, a sort of web proxy to pandora;
Other is by means of a vpn, which tunnels and encrypts traffic. There is a downside in velocity but streaming audio is not that much bandwidth intense like video so you may experience some initial delay but the overall experience is good enough. You can look into SecureIX and Hotspot Shield for free, publicly accessible VPNs.
Pirates of Silicon Valley
Apple and Microsoft roots.
Read also the novel In the beginning was the command line, by Neal Stephenson.
Friday, January 18, 2008
Free Software Magazine, issue 21
In this issue of Free Software Magazine David Jacovkis reports from Colombia and explains why free software is an ethical choice. Colin McGregor interviews several key people in the GNU/Linux world as well as explaining how to get KDE looking fantastic. Then we have Terry Hancock covering the Open Hardware project and making a comprehensive list of Linux-friendly hardware. Steven Goodwin shares how much he saved by using free software for his great beer podcast, and Alan Berg entertains us with free software easter eggs, while Andrew Min will explain the basics of HTML... Monty Python style. Gary Richmond enlights us about touchpads and Google Firefox extensions you don't want to miss. For ultimate hackers, Gianluca Pignalberi manages to do sound filtering by using... the Gimp (!) while Yousef Ourabi reviews FreeBSD 7 and its graphical installer. Talking about server-side topics, Ryan Cartwright covers the installation of Exim and Spamassassi, David A. Harding explains how to create a mailing list from home, and Ken Leyba makes sure you know how to protect your server with Deny Hosts. Finally, Andrew Krause tells you all you need to know about C in order to create GTK applications.
Read it online.
Led Zeppelin Live
Tonight Portuguese TV will broadcast a Led Zeppelin live concert. Here's a preview.
Google Documentary
A doc about Google with special appearance of Vince Cerf, also known as the father of the Internet.
A Change for the Better
It's good to know that sometimes we humans use our skills to the best and is especially interesting to see that specifically in the information business area there are people aware of the social responsibility to the human general welfare and progress. Two of the most notorious and remarkable examples are the google.org and gatesfoundation initiatives. See for yourself what is their mission, but i think we can say is essentially about a change for the better.
Update: Of course, this post wouldn't be complete without a reference to the One Laptop Per Child Project (OLPC) by MIT that developed a low cost laptop aimed to education proposes in developing countries.
Update: DonorsChoose.org - Teachers ask, You choose, Students learn. I'd like to see this concept extended to the rest of the world.
Thursday, January 17, 2008
BartPE, the Bootable Windows Environment
Yesterday i posted about the options available to boot Linux in your machine without a full complete installation. One of them is trough a live cd or flash media; Windows also have his own set of options available in this respect, one being WinPE, from Microsoft, and another is BartPE.
BartPE (Bart's Preinstalled Environment) is a Live CD/ Live USB version of the Microsoft Windows XP or Windows Server 2003 operating systems.
BartPE allows a user to boot Windows XP/Windows Server 2003 from a CD-ROM, DVD or a flash disk, regardless of the condition of the installed operating systems on the internal hard drive. This means that the user can, for instance, recover data from an operating system installation that has failed due to either a software or physical hardware corruption.
It can also be used to scan for and remove rootkits, viruses and spyware (that have infected boot files) and reset a lost administrator password.
A user can create his or her own installation of BartPE using the installation disk of the operating system in question and the program PE Builder, programmed by Bart Lagerweij.
Visit the official website for more information.
Wednesday, January 16, 2008
Try Linux
Are you a Windows user that heard about this thing called Linux and want to feel what is this buzz about?
So you have to try Linux. There are plenty ways of doing it (besides buy a fresh installed new Linux box or format your hard drive to have a clean Linux installation):
dual boot;
virtual machine;
live cd/flash drives;
linux demo.
Dual boot means that you can have more than one OS in your computer and load one of them at boot time. To run Linux you need a compatible boot loader like Grub to do the task that will enable you to select which OS to load in memory at boot time. You can also configure it to start one of them by default automatically with no need of user intervention. See the documentation of your boot loader for more specific information.
A virtual machine enables you to emulate an OS inside another as a common application. It does this by creating an environment (API libraries) similar to the original one and translates this to instructions specific to the host. This is the same as the popular Java virtual machine do achieve portable java code or a native language compiler, the difference is that the java code is interpreted, although not necessarily, and a compiler create a native object specific to the host environment.
A live cd, like Knoppix, is an OS that is loaded to memory like a standard one but does not have disk access so it does everything from memory. This has advantages when you just which to try something without making permanent changes to your system.
A related concept is a boot from a pen disk. It does not however have the 'read only' limitation of a cd so you could save your documents; the limitation is that not all bios support booting from a removable media like a pen disk, but the good news are that unless you own a somewhat old machine odds are that your system supports this feature. Just enter bios setup at boot time and see for yourself if this is the case or you need an bios update.
A Linux demo is the most unobtrusive/transparent - a term borrowed mainly from web programing- of all; It's easy as open your browser and point it to the open source demo center at the open source region Stuttgart website, following their instructions and try Linux online with just a minor client installation.
The Mozart Effect
The Mozart Effect® is an inclusive term signifying the transformational powers of music in health, education, and well-being. It represents the general use of music to reduce stress, depression, or anxiety; induce relaxation or sleep; activate the body; and improve memory or awareness. Innovative and experimental uses of music and sound can improve listening disorders, dyslexia, attention deficit disorder, autism, and other mental and physical disorders and injuries.
Research with Mozart's music began in France in the late 1950s when Dr. Alfred Tomatis began his experiments in auditory stimulation for children with speech and communication disorders. By 1990, there were hundreds of centers throughout the world using Mozart's music containing high frequencies, especially the violin concertos and symphonies, to help children with dyslexia, speech disorders, and autism. In the 1990's experiments were begun at the University of California in Irvine with Mozart's music and spacial intelligence assessments. As recently as 2001, new studies in England use Mozart's music to study its effect on epilepsy.
Sources: Wikipedia, Mozarteffect
Listen Mozart music online at Radio Mozart
BeOS
BeOS is an operating system for personal computers which began development by Be Inc. in 1991. It was first written to run on BeBox hardware. Unlike some other operating systems of the time, BeOS was written to take advantage of modern hardware. Optimized for digital media work, BeOS made full use of multiprocessor systems by utilizing modular I/O bandwidth, pervasive multithreading, preemptive multitasking and a custom 64-bit journaling file system known as BFS. The BeOS GUI was developed on the principles of clarity and a clean, uncluttered design. The API was written in C++ for ease of programming. It has POSIX compatibility and access to a command line interface through the bash shell, although internally it is not a Unix-derived operating system.
BeOS was positioned as a platform which could be used by a substantial population of desktop users and a competitor to Microsoft Windows and Linux. However, it was ultimately unable to achieve a significant market share and proved commercially unviable for Be Inc. The company was acquired by Palm Inc.
The Haiku operating system it's an open source BeOS inspired operating system currently being developed by a community of former and new BeOS enthusiasts.
See also Programming the Be Operating System, an O'Reilly open book
Tuesday, January 15, 2008
Archimedes Palimpsest
The Archimedes Palimpsest is a palimpsest on parchment in the form of a codex which originally was a copy of an otherwise unknown work of the ancient mathematician, physicist, and engineer Archimedes of Syracuse and other authors. Archimedes lived in the third century BC, but the copy was made in the 10th century by an anonymous scribe. In the 12th century the codex was unbound and washed, in order that the parchment leaves could be folded in half and reused for a Christian liturgical text. It was a book of nearly 90 pages before being made a palimpsest of 177 pages; the older leaves folded so that each became two leaves of the liturgical book. The erasure was incomplete, and Archimedes' work is now readable using digital processing of ultraviolet, X-ray, and visible light.
In 1906 it was briefly inspected in Constantinople and was published, from photographs, by the Danish philologist Johan Ludvig Heiberg; shortly thereafter Archimedes' Greek text was translated into English by Thomas Heath. Before that it was not widely known among mathematicians, physicists, or historians. It contains
* "Equilibrium of Planes"
* "Spiral Lines"
* "The Measurement of the Circle"
* "Sphere and Cylinder"
* "On Floating Bodies" (only known copy in Greek)
* "The Method of Mechanical Theorems" (only known copy)
* "Stomachion" (only known copy)
The palimpsest also contains speeches by the 4th century BC politician Hypereides, and a commentary on Aristotle's Categories by Alexander of Aphrodisias.
See also the official website
Kayaking
Whitewater kayaking is the sport of paddling a kayak on a moving body of water, typically a whitewater river. Whitewater kayaking can range from simple, carefree gently moving water, to demanding, dangerous whitewater. River rapids are graded like ski runs according to the difficulty, danger or severity of the rapid. Whitewater grades (or classes) range from I or 1 (the easiest) to VI or 6 (the most difficult/dangerous). Grade/Class I can be described as slightly moving water with ripples. Grade/Class VI can be described as severe or almost unrunnable whitewater (classic example: Niagara Falls).
Video courtesy of National Geographic
Monday, January 14, 2008
Large Hadron Collider
Beneath breathtaking alpine vineyards, some 20 miles outside Geneva, 8,000 scientists are working at a feverish pace to complete the world's largest particle accelerator, the Large Hadron Collider, nicknamed the "Lord of Rings," which will probe deeper into matter than ever before. Its purpose is to replicate the birth of the universe.
The Large Hadron Collider Project was approved by CERN Council in December 1994. Because of initial funding difficulties it was proposed initially as a 2-phase project, the first stage with an energy of 10 TeV in the center-of-mass, to be operational by 2004, with an upgrade to its final energy of 14 TeV by 2008.
During the years 1995-1996, intense negotiations with non-Member States secured a substantial commitment to participate financially in the construction of the Machine. Consequently, in December 1996, Council passed a Resolution approving the construction of the 14 TeV accelerator in a single stage. The LHC will be the first machine built at CERN with substantial material contribution from non-Member States. Machine hardware is being constructed in National Laboratories in Canada, India, Japan, Russia and the USA.
The LHC will ultimately collide beams of protons at an energy of 14 TeV . Beams of lead nuclei will be also accelerated, smashing together with a collision energy of 1150 TeV.
A TeV is a unit of energy used in particle physics. 1 TeV is about the energy of motion of a flying mosquito. What makes the LHC so extraordinary is that it squeezes energy into a space about a million million times smaller than a mosquito.
The experiments will be carried out deep inside the earth in a circular tunnel 27 kilometers long, 100 meters below the surface of the Earth, where CERN physicists will crash sub-atomic particles whirring around at the speed of light and monitor the debris of these tiny crashes, to calibrate the relationship between matter and energy and learn more about how matter came into existence in the first few seconds of the Big Bang.
The ultimate prize is to find an almost particle, the Higgs-Boson, a key part of what physicists call the Standard Model of the subatomic world. CERN's Large Hadron Collider will be supplied with protons from the injector chain Linac2 - Proton Synchrotron Booster (PSB) - Proton Synchrotron (PS) - Super Proton Synchrotron (SPS). These accelerators were upgraded to meet the very stringent needs of the LHC.
The tunnel was formerly used to house the LEP, an electron-positron collider. The underground infrastructure of LEP included experimental areas at four points, each incorporating experimental and service caverns, plus an equipment cavern with injection tunnels connected to allow particle transfer from the SPS machine. Plus additional galleries parallel to the main tunnel were used to house klystrons and their power supplies. On the surface a total of 37 buildings housed all the necessary equipment and services for the LEP machine and experimental operations. The LEP-2 upgrade consisted essentially of the addition of two sets of galleries thus allowing a doubling of the number of klystrons and related power supplies.
For the LHC project, the existing LEP tunnel has been re-used after the complete dismantling of the LEP machine. In addition new structures have been added including experimental and service caverns destined to accommodate two new experiments two transfer tunnels of about 2.5 km each in length and beam dump facilities comprising two sets of straight tunnels and caverns. 32 new surface buildings of various sizes have also been constructed.
LHC@Home, a distributed computing project, was started to support the construction and calibration of the LHC. The project uses the BOINC platform to simulate how particles will travel in the tunnel. With this information, the scientists will be able to determine how the magnets should be calibrated to gain the most stable "orbit" of the beams in the ring.
While many have voiced concerns that the LHC will destroy the Universe, engineers close to the project admit that the possibility is infinitesimally small. As CERN has pointed out, if the Earth were in danger of any such fate, it would have happened billions of years ago from the bombardment of protons the planet receives that are millions of times more energetic than anything that could be produced by the LHC.
The Large Hadron Collider is expected to create tiny black holes within the Earth. However there exists an entirely theoretical phenomenon known as Hawking Radiation, which some physicists expect to cause these black holes to dissipate. The primary cause for concern is the fact that Hawking Radiation - the only means by which these black holes could be dissipated, is entirely theoretical.
CERN performed a study to investigate whether such dangerous events as micro black holes, strangelets, or magnetic monopoles could occur. The report concluded, "We find no basis for any conceivable threat". It has been claimed that a strong argument for the safety of colliders such as the LHC comes from the simple fact that cosmic rays with energies up to twenty million times the LHC's 1.4×10¹³ eV capacity have been bombarding the Earth, Moon and other objects in the solar system for billions of years with no such effects. Yet CERN themselves claim that the Hadron Collider is to recreate conditions that haven't existed since a fraction of a second after the big bang, making it difficult to accept that the conditions within the collider are quite as everyday.
As with any new and untested experiment, it is not possible to say with utter certainty what will happen. John Nelson at the University of Birmingham stated of RHIC that "it is astonishingly unlikely that there is any risk-but I could not prove it." Furthermore, in academia there is some question, albeit among a minority of scientists, of whether the Hawking radiation theory is correct.
Souces: Daily Galaxy, CERN, Wikipedia
Friday, January 11, 2008
Elephant's Dream
Elephants Dream is a computer-generated short film. Except for Reaktor, a modular sound studio, and Mac OS X, the OS of the cluster used to render the final production, all software used in production was open source. It premiered on March 24, 2006, after about 8 months of work. Beginning production in September 2005, it was developed under the name Orange by a team of seven artists and animators from around the world. Its name was later changed from Machina and renamed to Elephants Dream (named after the way in which Dutch children's stories abruptly end). (read full storie at wikipedia)
Elephants Dream is the world’s first open movie, made entirely with open source graphics software such as Blender, and with all production files freely available to use however you please, under a Creative Commons license.
The short film was created by the Orange Open Movie Project studio in Amsterdam during 2005/2006, bringing together a diverse team of artists and developers from all over the world. (official website)
Thursday, January 10, 2008
Computer Networks - The Heralds of Resource Sharing
A documentary film about the history of the ARPANET and birth of the Internet.
MapReduce
Recently hit the web news that Google processes 20 petabytes (!) of data per day. To do this Google implemented a framework named MapReduce to deal with this vast amounts of data in his large decentralized cluster network.
From Google Labs:
"MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper.
Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.
Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day."
Slides
See also How Google Works
Monday, January 7, 2008
Jacques Cousteau
Jacques-Yves Cousteau was a French naval officer, explorer, ecologist, filmmaker, scientist, photographer and researcher who studied the sea and all forms of life in water. He co-developed the aqua-lung, pioneered marine conservation and was a member of the Académie française. (see Wikipedia full article)
Cousteau Society biography
Related: PBS Jean-Michel Cousteau, Ocean Adventures - Sharks at Risk.
MegaTransect
MegaTransect was the name for a project conducted in Africa in 1999 by J. Michael Fay to spend 455 days on the expedition hike of 2000 km across the Congo Basin of Africa to survey the ecological and environmental status of the region. 'MegaTransect' is named for the transect methodology.
For 15 months Wildlife Conservation Society biologist J. Michael Fay hiked across central Africa (map)—2,000 miles (3,200 kilometers) through dense forests and remote villages—to Africa’s Atlantic coast.
Along the way Fay and his team surveyed the land and wildlife of the Congo River Basin, recording animals and plants that may well become threatened as humans press into the wilds.
Mike Fay later went on to carry out the MegaFlyover in 2004.
See also National Geographic description
Whale Song
Whale song is the sound made by whales to communicate. The word "song" is used in particular to describe the pattern of regular and predictable sounds made by some species of whales (notably the humpback) in a way that is reminiscent of human singing.
The mechanisms used to produce sound vary from one family of cetaceans to another. Marine mammals, such as whales, dolphins, and porpoises, are much more dependent on sound for communication and sensation than land mammals are , as other senses are of limited effectiveness in water. Sight is limited for marine mammals because of the way water absorbs light. Smell is also limited, as molecules diffuse more slowly in water than air, which makes smelling less effective. In addition, the speed of sound in water is roughly four times that in the atmosphere at sea level. Because sea-mammals are so dependent on hearing to communicate and feed, environmentalists and cetologists are concerned that they are being harmed by the increased ambient noise in the world's oceans caused by ships and marine seismic surveys. (read Wikipedia full article)
Prof. Richard A. Muller course Physics for Future Presidents at Berkeley has a lecture about waves where he talks about the ocean sound channel and whales communication. Forward the video to about 35 min to watch his explanation.
Carl.Sagan's Cosmos series also talks about this issue at chapter 11, The Persistence Of Memory.
Thursday, January 3, 2008
Wednesday, January 2, 2008
Lambda Calculus
In mathematical logic and computer science, lambda calculus, also λ-calculus, is a formal system designed to investigate function definition, function application, and recursion. It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s; Church used lambda calculus in 1936 to give a negative answer to the Entscheidungsproblem. Lambda calculus can be used to define what a computable function is.
In Turing's words:"a function is said to be 'effectively calculable' if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematically expressible definition. Such a definition was first given by Godel at Princeton in 1934... These functions were described as 'general recursive' by Godel ... Another definition of effective calculability has been given by Church... who identifies it with definability. The author [i.e. Turing himself] has recently suggested a definition corresponding more closely to the intuitive idea... It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process. ' We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine... The development of these ideas leads to the author's definition of a computable function, and to an identification of computability [in Turing's precise technical sense] with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions are equivalent."
Turing here gives a view on what is now known and famous as Church's thesis. Although Church's thesis is nowadays given various other interpretations, in 1936 it was the claim that effective calculability could be identified with the operations of Church's very elegant and surprising formalism, that of the lambda-calculus. As such it lay within the world of mathematical formalism. But Turing offers a reason why Church's thesis should be true, drawing on ideas external to mathematics such as that one cannot do see or choose between more than a finite number of things at one time. Church's thesis is now sometimes called the
Church-Turing thesis, but the Turing thesis is different, bringing the physical world into the picture with a claim of what can be done. It should not go without mention that Turing after referring to his machine definition of computability, also cited the work of the Polish-American logician Emil Post, which had also brought an idea of physical action into computation. However Post had not developed his ideas so fully.
The question of whether two lambda calculus expressions are equivalent cannot be solved by a general algorithm, and this was the first question, even before the halting problem, for which undecidability could be proved. Lambda calculus has greatly influenced functional programming languages, such as Lisp, ML and Haskell.
Lambda calculus can be called the smallest universal programming language. It consists of a single transformation rule (variable substitution) and a single function definition scheme. Lambda calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to the Turing machine formalism. However, lambda calculus emphasizes the use of transformation rules, and does not care about the actual machine implementing them. It is an approach more related to software than to hardware.
History and Evolution
Originally, Church had tried to construct a complete formal system for the foundations of mathematics; when the system turned out to be susceptible to the analog of Russell's paradox, he separated out the lambda calculus and used it to study computability, culminating in his negative answer to the Entscheidungsproblem.
The lambda calculus was originally developed as a foundation for mathematics. This work was done in the 1930s several years before digital computers were invented. A little earlier (in the 1920s) Moses Schonfinkel developed another theory of functions based on what are now called combinators. In the 1930s Haskell Curry rediscovered and extended Schonfinkel's theory and showed that it was equivalent to the lambda calculus. About this time Kleene showed that the lambda calculus was a universal computing system; it was one of the first such systems to be rigorously analysed. In the 1950s John McCarthy was inspired by the lambda calculus to invent the programming language LISP. In the early 1960s Peter Landin showed how the meaning of imperative programming languages could be specified by translating them into the lambda calculus. He also invented an influential prototype programming language called ISWIM. This introduced the main notations of functional programming and influenced the design of both functional and imperative languages. Building on this work, Christopher Strachey laid the foundations for the important area of denotational semantics. Technical questions concerning Strachey's work inspired the mathematical logician Dana Scott to invent the theory of domains which is now one of the most important parts of theoretical computer science. During the 1970s Peter Henderson and Jim Morris took up Landin's work and wrote a number of influential papers arguing that functional programming had important advantages for software engineering. At about the same time David Turner proposed that Schonfinkel and Curry's combinators could be used as the machine code of computers for executing functional programming languages. Such computers could exploit mathematical properties of the lambda calculus for the parallel evaluation of programs. During the 1980s several research groups took up Henderson's and Turner's ideas and started working on making functional programming practical by designing special architectures to support it; some of them with many processors.
Definition
Lambda calculus power to express any computable function derived of a very simple mechanism to define functions. Grammatically it is composed of a set of rules for function conversion (or reduction). From that it is possible to represent algebra, logic, recursion and other formalisms. In that sense it is considered an universal language.
There are three main types of conversions allowed: alfa, beta, and eta. The most important kind of conversion is beta conversion; it is the one that can be
used to simulate arbitrary evaluation mechanisms. alfa conversion is to do with the technical manipulation of bound variables and eta conversion expresses the fact that two functions that always give the same results on the same arguments are equal.
A lambda expression (necessarily an abstraction) to which alfa reduction can be applied is called an alfa-redex The term 'redex' abbreviates 'reducible expression'. The rule of alfa conversion just says that bound variables can be renamed provided no 'name clashes' occur.
A lambda expression (necessarily an application) to which beta reduction can be applied is called a beta-redex. The rule of beta conversion is like the evaluation of a function call in a programming language: the body expression of a function is evaluated in an environment in which the 'formal parameter' is bound to the 'actual parameter'.
A lambda expression (necessarily an abstraction) to which eta reduction can be applied is called an eta-redex. The rule of eta conversion expresses the property that two functions are equal if they give the same results when applied to the same arguments. This property is called extensionality.
The central concept in lambda calculus is the "expression". A "name", also called a "variable", is an identifier. An expression is defined recursively as follows:
expression := name | function | application
function := λname.expression
application := expression expression
Computable functions and lambda calculus
A function F: N -> N of natural numbers is a computable function if and only if there exists a lambda expression f such that for every pair of x, y in N, F(x) = y if and only if f x == y, where x and y are the Church numerals corresponding to x and y, respectively. This is one of the many ways to define computability; see the Church-Turing thesis for a discussion of other approaches and their equivalence.
Undecidability of equivalence
There is no algorithm which takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressions are equivalent. This was historically the first problem for which the unsolvability could be proven. Of course, in order to do so, the notion of algorithm has to be cleanly defined; Church used a definition via recursive functions, which is now known to be equivalent to all other reasonable definitions of the notion.
Church's proof first reduces the problem to determining whether a given lambda expression has a normal form. A normal form is an equivalent expression which cannot be reduced any further. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions, he constructs a lambda expression e which closely follows the proof of Gödel's first incompleteness theorem. If e is applied to its own Gödel number, a contradiction results.
Lambda calculus and programming languages
As pointed out by Peter Landin's 1965 classic A Correspondence between ALGOL 60 and Church's Lambda-notation, most programming languages are rooted in the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.
Implementing the lambda calculus on a computer involves treating "functions" as first-class objects, which raises implementation issues for stack-based programming languages. This is known as the Funarg problem.
The most prominent counterparts to lambda calculus in programming are functional programming languages, which essentially implement the calculus augmented with some constants and datatypes. Lisp uses a variant of lambda notation for defining functions, but only its purely functional subset ("Pure Lisp") is really equivalent to lambda calculus.
Functional languages are not the only ones to support functions as first-class objects. Numerous imperative languages, e.g. Pascal, have long supported passing subprograms as arguments to other subprograms. In C and C++ the equivalent result is obtained by passing pointers to the code of functions (subprograms). Such mechanisms are limited to subprograms written explicitly in the code, and do not directly support higher-level functions. Some imperative object-oriented languages have notations that represent functions of any order; such mechanisms are available in Smalltalk and more recently in Eiffel ("agents") and C# ("delegates"). As an example, the Eiffel "inline agent" expression
agent (x: REAL): REAL do Result := x * x end
denotes an object corresponding to the lambda expression ? x . x*x (with call by value). It can be treated like any other expression, e.g. assigned to a variable or passed around to routines. If the value of square is the above agent expression, then the result of applying square to a value a (ß-reduction) is expressed as square.item ([a]), where the argument is passed as a tuple.
Concurrency and parallelism
The Church-Rosser property of the lambda calculus means that evaluation (ß-reduction) can be carried out in any order, even concurrently. (Indeed, the lambda calculus is referentially transparent.) While this means the lambda calculus can model the various nondeterministic evaluation strategies, it does not offer any richer notion of parallelism, nor can it express any concurrency issues. Process calculi such as CSP, the CCS, the p calculus and the ambient calculus have been designed for such purposes.
Conclusion
We thus see that an obscure branch of mathematical logic underlies important developments in programming language theory such as:
The study of fundamental questions of computation
The design of programming languages
The semantics of programming languages
The architecture of computers.
Bibliography:
"Lambda Calculus" in Wikipedia
A Tutorial Introduction to the Lambda Calculus by Raul Rojas
The Great Philosophers - From Socrates to Turing - "Turing" by Andrew Hodges
Introduction to Functional Programming by Mike Gordon
Subscribe to:
Posts (Atom)
