tag:blogger.com,1999:blog-75880607385951362532024-03-27T19:53:46.854-04:00NP ContemplationNeural Networks, Machine Learning and Artificial Intelligence.Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-7588060738595136253.post-47279320556802353122012-02-16T14:04:00.000-05:002013-09-12T00:50:57.722-04:00A machine that can dream<script src="http://ynd.github.com/rbm_faces.js/js/jdataview.js" type="text/javascript">
</script><script charset="utf-8" src="http://ynd.github.com/rbm_faces.js/js/jquery.prettyLoader.js" type="text/javascript">
</script><link charset="utf-8" href="http://ynd.github.com/rbm_faces.js/css/prettyLoader.css" media="screen" rel="stylesheet" type="text/css"></link><script src="http://ynd.github.com/rbm_faces.js/js/rbm.js" type="text/javascript">
</script><script type="text/javascript">
function rbm_start() {
if (window.rbm1) {
window.rbm1.reset = true;
return;
}
var speed = 5;
rbm0 = new RBM(2304,
1024,
"http://c297721.r21.cf1.rackcdn.com/W0.bin",
"http://c297721.r21.cf1.rackcdn.com/b0.bin",
"http://c297721.r21.cf1.rackcdn.com/c0.bin",
$("#visibles-canvas"),
$("#0-hiddens-canvas"));
rbm1 = new RBM(1024,
512,
"http://c297721.r21.cf1.rackcdn.com/W1.bin",
"http://c297721.r21.cf1.rackcdn.com/b1.bin",
"http://c297721.r21.cf1.rackcdn.com/c1.bin",
$("#0-hiddens-canvas"),
$("#1-hiddens-canvas"));
function gibbs() {
var begin = new Date();
if (rbm1.ready()) {
rbm1.gibbs();
rbm0.sample_v(rbm1.v, true);
}
var end = new Date();
setTimeout(gibbs, Math.max(5, 100 - (end - begin)));
}
setTimeout(gibbs, speed);
$('#start-rbm').text("Restart!");
}
</script><br />
<div style="margin-left: 5em; width: 320px;">
<canvas height="40" id="1-hiddens-canvas" style="background-image: url("http://ynd.github.com/rbm_faces.js/images/h1.png");" width="320"><br />
</canvas><br />
<br />
<canvas height="80" id="0-hiddens-canvas" style="background-image: url("http://ynd.github.com/rbm_faces.js/images/h0.png"); margin-top: -1em; position: relative;" width="320"><br />
</canvas><br />
<br />
<div>
<canvas height="144" id="visibles-canvas" style="background-image: url("http://ynd.github.com/rbm_faces.js/images/v.png");" width="144"><br />
</canvas><br />
<button id="start-rbm" onclick="rbm_start();" style="margin-left: 20em; position: relative; top: -7em;" type="button">Start!</button></div>
</div>
<div style="text-align: center;">
<span style="font-size: x-small;">Note: This takes 20-30s to load, supported browsers are </span><span style="font-size: x-small;">Chrome, </span><span style="font-size: x-small;">Safari 4.0+, </span><br />
<span style="font-size: x-small;">Firefox 4+, </span><span style="font-size: x-small;">Opera 10.0+. It requires heavy computations.</span></div>
<div style="text-align: center;">
<br /></div>
This is a live demo of a type of Boltzmann machine in Javascript. The evolving image at the bottom is what the machine is thinking and the flickering lights are the state of its neurons. This particular machine has been shown thousands of faces, and now it imagines faces when it <i>dreams</i>.<br />
<br />
The Boltzmann machines have a remarkable ability similar to dreaming. They were first introduced by Geoff Hinton and Terry Sejnowski as a model of the brain in 1983. They can discover patterns when they are learning from data. And when run in a closed loop they can generate or <i>dream</i> new examples based on what is has learned.<br />
<br />
<br />
<br />
<br />
How do they work? The full answer is beyond the scope of this post, but for motivated readers here's a quick explanation focusing on the restricted Boltzmann machine (RBM). It is defined by its so-called <i>energy</i> function<br />
<div style="text-align: center;">
$$E({\bf v}, {\bf h}) = - \sum\limits_{i,j} v_i h_j w_{ij}$$</div>
This function measures the energy between a sensory input vector \({\bf v}\) and the state of each neuron \({\bf h}\). The parameters \(w_{ij}\) weight correlations in the data. This is used to define the probability<br />
<div style="text-align: center;">
$$p({\bf v}, {\bf h}) = \frac{e^{-E({\bf v}, {\bf h})}}{\sum\limits_{{\bf v}',{\bf h}'} e^{-E({\bf v}', {\bf h'})}}$$</div>
where the denominator is the summation of the energy of all possible configurations of inputs and brain states.<br />
<br />
Learning consists of adjusting \(w_{ij}\) to maximize the probability the RBM assigns to what you show it. This will make the neurons detect patterns in the sensory input. Dreaming consists of traveling in probable sensory inputs and brain states using Markov Chain Monte Carlo (MCMC).<br />
<br />
If you want to know more about Boltzmann machines and Deep Learning, you should checkout this <a href="http://www.youtube.com/watch?v=AyzOUbkUf3M">excellent talk</a> by Geoff Hinton, or you can read this <a href="http://www.iro.umontreal.ca/~lisa/bib/pub_subject/language/pointeurs/bengio+lecun-chapter2007.pdf">introductory paper</a> by Yoshua Bengio and Yann LeCun.<br />
<br />
You can also find <a href="http://scikit-learn.org/stable/modules/generated/sklearn.neural_network.BernoulliRBM.html#sklearn.neural_network.BernoulliRBM">here</a> a pythonic implementation of the binary restricted Boltzmann machine (RBM) that I wrote.Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com101tag:blogger.com,1999:blog-7588060738595136253.post-61498396389382529382009-08-23T23:47:00.006-04:002009-08-24T00:42:19.293-04:00Self-Organization and Conway's Game of life (With Interactive Javascript Canvas)<span style="font-weight: bold;">Introduction</span> <br />
<br />
I want to show you that self-organization is the magic of life. Conway's game of life defines a simple universe governed by 3 simple laws in which creative, intelligent and stable organism emerge and die. <br />
<br />
<br />
<span style="font-weight: bold;">Conway's Game of Life in Javascript</span> <br />
<style type="text/css">
#life-grid-1 { border: 1px solid black; }#life-grid-1-big-bang { width: 10em; margin-top:0.5em; padding:0.5em; background:black; text-align:center; float:left; cursor:pointer; font-size:2em; color: #90EE90; font-family:arial, sans-serif; }
</style><script type="text/javascript">
$(document).ready(function(){var canvas=document.getElementById("life-grid-1");var context=canvas.getContext("2d");var cellSize=10;var gridWidth=canvas.width/cellSize;var gridHeight=canvas.height/cellSize;var isRunning=false;var isEditing=false;var bigBangButton=document.getElementById("life-grid-1-big-bang");var refreshRate=100;context.fillStyle="white";context.fillRect(0,0,canvas.width,canvas.height);function onMouseMove(e){var x=e.pageX-$(canvas).offset().left;var y=e.pageY-$(canvas).offset().top;var cellX=Math.floor(x/cellSize);var cellY=Math.floor(y/cellSize);RenderLiveCell(cellX,cellY);}$(canvas).mouseup(function(e){$(canvas).unbind("mousemove",onMouseMove);isEditing=false;});$(canvas).mousedown(function(e){if(!isRunning){setInterval(ApplyGameLogic,refreshRate);isRunning=true;}onMouseMove(e);isEditing=true;$(canvas).mousemove(onMouseMove);});$(bigBangButton).click(function(){if(!isRunning){setInterval(ApplyGameLogic,refreshRate);isRunning=true;}for(var x=0;x<gridWidth;x++){for(var y=0;y<gridHeight;y++){var l=Math.round(Math.random()*10);if(l>=4&&l<=5){RenderLiveCell(x,y);}else{RenderDeadCell(x,y);}}}});function RenderCell(x,y,color){context.fillStyle=color;context.fillRect(x*cellSize,y*cellSize,cellSize,cellSize);}function RenderLiveCell(x,y){RenderCell(x,y,"black");}function RenderDeadCell(x,y){RenderCell(x,y,"white");}function IsCellAlive(pixels,x,y){var offset=y*cellSize*canvas.height*4+x*cellSize*4;return pixels[offset]==0&&pixels[offset+1]==0&&pixels[offset+2]==0;}function ApplyGameLogic(){if(isEditing){return;}var pixels=context.getImageData(0,0,canvas.width,canvas.height).data;for(var y=0;y<gridHeight;y++){for(var x=0;x<gridWidth;x++){var alive=0;for(var yy=y-1;yy<=y+1;yy++){for(var xx=x-1;xx<=x+1;xx++){if(yy>=0&&xx>=0&&yy<gridHeight&&xx<gridWidth&&!(yy==y&&xx==x)){if(IsCellAlive(pixels,xx,yy)){alive++;}}}}if(IsCellAlive(pixels,x,y)){if(alive<2||alive>3){RenderDeadCell(x,y);}}else if(alive==3){RenderLiveCell(x,y);}}}}});
</script> <br />
<canvas height="450" id="life-grid-1" width="450"></canvas><br />
<div id="life-grid-1-big-bang">Generate Big bang!</div><br />
<br />
<br />
<br />
<br />
<span style="font-weight: bold;"> <br />
Note:</span> You can also paint on the canvas using the mouse. <br />
<br />
Supported browsers are Safari 2.0+, Opera 9.0+, Firefox 1.5+ and Chrome. Use Safari or Chrome for a much better experience. Internet Explorer does not support this technology yet. <br />
<br />
<br />
<span style="font-weight: bold;">Explanation</span> <br />
<br />
The universe of the game is a two-dimensional grid of cells. Each cell can be either dead or alive. Each cell interacts with it's 8 direct neighbors in the following way: <br />
<br />
1. <span style="font-weight: bold;">Birth</span>. Any dead cell with exactly 3 live neighbors becomes live.<br />
2. <span style="font-weight: bold;">Survival</span>. Any live cell with exactly 2 or 3 live neighbors survives.<br />
3. <span style="font-weight: bold;">Death</span>. Any live cell with less than 2 or more than 3 neighbors dies.<br />
<br />
The behaviors that emerge from these simple rules may be considered creative and beautiful. <br />
<br />
<br />
<span style="font-weight: bold;">Take away</span> <br />
<br />
Here's a quote from <a href="http://www.amazon.com/Simpler-Way-Margaret-J-Wheatley/dp/1881052958">a simpler way</a> by Margaret J. Wheatley. <br />
<br />
<div style="-moz-background-clip: border; -moz-background-inline-policy: continuous; -moz-background-origin: padding; background: transparent url(http://www.netlash2.be/bloggertheme/bquote.png) no-repeat scroll left top; margin: 1em 5px; padding: 0pt 0pt 0pt 25px;">The tendency to organize is not just found in living beings. While it is increasingly difficult in science to distinguish the living from the non-living, few of us would categorize light bulbs as alive. Yet light bulbs have exhibited a breathtaking tendency to self-organize when wired together with other bulbs. Building on earlier work, theoretical biologist Stuart Kauffman conducted a light bulb experiment in the 1960s. <br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjJYW8V16CAEiX9Z96rgnH7AuIXcHIMoYUHc20AmgZl3h5HjeeAelFPZU8LbG-bSLiT-FZMWWJCPHeVMWKNGCQlae5eqbqlryIB2prrn2u9OcfvsL1zQGAeRrLz-E1-m2cdGVpn8xSBrSQ/s1600-h/Game_of_life_toad.gif" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" id="BLOGGER_PHOTO_ID_5373368591222571410" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjJYW8V16CAEiX9Z96rgnH7AuIXcHIMoYUHc20AmgZl3h5HjeeAelFPZU8LbG-bSLiT-FZMWWJCPHeVMWKNGCQlae5eqbqlryIB2prrn2u9OcfvsL1zQGAeRrLz-E1-m2cdGVpn8xSBrSQ/s320/Game_of_life_toad.gif" style="cursor: pointer; float: left; height: 98px; margin: 0pt 10px 10px 0pt; width: 98px;" /></a><span style="clear: left; color: grey; float: left; margin: 0pt 0pt 10px 10px; text-align: center; width: 98px;">Toad</span>Kauffman was interested in exploring how the complex network of human genes had developed, but he used light bulbs to demonstrate that self-organization is a fundamental process found everywhere. He wired together a network of two hundred light bulbs. Each bulb was assigned a relationship with two other bulbs. It was to turn on or off based only on the behavior of either of its two assigned partners. Even with such simple conditions, the number of possible states of on and off bulbs is 10<sup>30</sup>. The human imagination cannot begin to comprehend this number of possibilities. [...] <br />
<br />
But the pattern of organization appeared instantly. After exploring only thirteen states, the system of bulbs settled into a repeatable pattern, flashing on and off in a repetitive cycle of four configuration. [...] <br />
<br />
<a href="http://upload.wikimedia.org/wikipedia/en/f/f2/Game_of_life_animated_glider.gif" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" src="http://upload.wikimedia.org/wikipedia/en/f/f2/Game_of_life_animated_glider.gif" style="cursor: pointer; float: right; height: 84px; margin: 0pt 0pt 10px 10px; width: 84px;" /></a><span style="clear: right; color: grey; float: right; margin: 0pt 0pt 10px 10px; text-align: center; width: 84px;">Glider</span>We live in a universe which seeks organization. When simple relationships are created, patterns of organization emerge. Networks, living or not, have the capacity to self-organize. Global order arises from local connections. It was these cooperative structures that first created life. Life linked with other life and discovered how to continue discovering itself. [...] </div><br />
To me this explains how life can emerge from the inanimate. <br />
<br />
Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com30tag:blogger.com,1999:blog-7588060738595136253.post-21629716255600723082009-01-25T14:45:00.015-05:002009-01-28T23:06:22.437-05:00Clojure: Genetic Mona Lisa problem in 250 beautiful lines<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmpRJFs8_JAgTSSg82M1zrLaRNUoRbOX7eeIlsxke99SEMznxkkCZkI_9BE0M6ssNBJ1Wzf43Qr-ODIG5doVSdCXJRRps1H3qTkcQFSl-PKaV6M_Z3Sd9a2WPdNXqsss1jqoe1FdifuQ4/s1600-h/mona_last.png"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 200px; height: 178px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmpRJFs8_JAgTSSg82M1zrLaRNUoRbOX7eeIlsxke99SEMznxkkCZkI_9BE0M6ssNBJ1Wzf43Qr-ODIG5doVSdCXJRRps1H3qTkcQFSl-PKaV6M_Z3Sd9a2WPdNXqsss1jqoe1FdifuQ4/s320/mona_last.png" alt="" id="BLOGGER_PHOTO_ID_5295423007404676690" border="0" /></a><br /><a href="http://clojure.org/rationale">Clojure</a> is surrounded by hype these days. The word on the streets is that Clojure is the Next Big Thing. It has access to the largest library of code and it proposes a nice solution the to the concurrency problem. Lots more has been said...<br /><br />But I haven't seen a lot of code.<br /><br />So I set out to make a small but meaningful program in Clojure to get a sense of it's potential.<br /><br />I give Clojure two thumbs up, and I think you'll do too.<br /><br /><span style="font-weight: bold;">The Mona Lisa Problem</span><br /><br />The program I present tries to paint Mona Lisa with a small number of semi-transparent colored polygons. It does so by using Darwin's theory of evolution to evolve programs that draw Mona Lisa.<br /><br />Here's the simplified algorithm:<br />1. Generate an initial population of programs<br />2. Take the n best programs of the current population<br />3. Create Children from the best programs by mating and mutating them<br />4. Replace the current population with the n-best and the children programs<br />5. Repeat from 2 until satisfied<br /><br />See my more complete <a href="http://github.com/ynd/genetic-drawing/tree/master">java version</a> for details and don't miss <a href="http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/">Roger Alsing's seminal post</a>.<br /><br /><span style="font-weight: bold;">Clojure is Lisp</span><br /><br />Lisp code can be treated as data. That makes evolving programs painless. My Genetic Algorithm simply evolves lambdas. Running the evolved programs is a matter of calling '<span style="font-style: italic;">eval</span>.<br /><br />The program is <span style="font-weight: bold;">side-effects free</span>(almost!). The majority of the program is functional. There are only two sources of side-effects:<br />1. Drawing on the canvas<br />2. Handling the GUI<br /><br /><span style="font-weight: bold;">Clojure is Java</span><br /><br />It can be distributed and run anywhere. Clojure is compiled to Java bytecodes.<br /><br />Clojure can use Java objects directly without wrappers. I was able to create a cross-platform GUI in a few lines with Swing.<br /><br />Let me illustrate this by creating an object deriving from JPanel that overides the paint method to draw a green rectangle.<br /><pre name="code" class="python"><br />(def rec-panel (proxy [JPanel] []<br /> (paint [graphics]<br /> (doto graphics<br /> (.setColor Color/green)<br /> (.fillRect 0 0 10 10)))))<br /></pre><br /><span style="font-weight: bold;">Parallelism</span><br /><br />I painlessly parallelized my code because it is side-effects free. Clojure provides primitives that can parallelize functional code.<br /><br />The bottleneck of the application is calculating the fitness of each individual of a population. In functional terms, it is expressed by mapping each individual to it's fitness using '<span style="font-style: italic;">map</span> with '<span style="font-style: italic;">fitness</span> function as it's first argument and the population as it's second argument.<br /><br />Clojure provides the '<span style="font-style: italic;">pmap</span> function to make that mapping parallel. It divides the work between worker threads and it uses as many of them as you have CPU cores.<br /><br />Thus, writing functionaly allowed me to parallelize my code by adding one '<span style="font-style: italic;">p</span>' character.<br /><br />See <a href="http://clojure.org/api#toc571">clojure.parallel</a>.<br /><br /><span style="font-weight: bold;">Performance</span><br /><br />Performance wasn't a concern when I wrote the application. I tried to keep it simple. After all, that is the purpose of using a high-level language.<br /><br />Surprisingly, the fitness function(the bottleneck) runs faster in Clojure than in Java. Unfortunately I don't have time to dig into this now.<br /><br />Here's a graph comparing the run time the fitness function in Java and Clojure. The measure is the average of 25 samples of 100 runs of the fitness function in each language.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpXs1JRoQeT7IehZJjwVVw5iyflquQVR_ESh2npyGHjih_MMKvJ-T4zWYsHOWehbGDDGTiCl9aOySS84c7LbQO6Oixk4vTgYbwx0MR1HG0Et0r3VzQj-e8T4uhdmfT4qPBbmKZNOeQBS4/s1600-h/bench.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 193px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpXs1JRoQeT7IehZJjwVVw5iyflquQVR_ESh2npyGHjih_MMKvJ-T4zWYsHOWehbGDDGTiCl9aOySS84c7LbQO6Oixk4vTgYbwx0MR1HG0Et0r3VzQj-e8T4uhdmfT4qPBbmKZNOeQBS4/s320/bench.png" alt="" id="BLOGGER_PHOTO_ID_5295346320774992018" border="0" /></a><br /><br />Here's the <a href="http://github.com/ynd/mona-clojure/tree/master/bench">benchmark</a> for reference.<br /><br /><span style="font-weight: bold;">A deal breaker</span><br /><br />Lambdas are not garbage collected.<br /><br />Yes. That means lambdas can be the cause of memory leaks.<br /><br />As <a href="http://blog.headius.com/2008_09_11_archive.html">described by Charles Nutter</a>, each lambda in Clojure is an anonymous class in Java. The problem is that classes are never garbage collected. They reside in a special place called the PermGen.<br /><br />No need to say, my program quickly fills up the PermGen.<br /><br />The only solution for now is to extend the PermGen.<br /><pre name="code" class="python"><br />java -XX:MaxPermSize=1024m -cp clojure.jar clojure.lang.Repl mona-clojure.clj<br /></pre><br />I don't think this is a problem for most applications though.<br /><br />EDIT: As of r1232, lambdas created in eval can be GCed. Thanks to Christophe Grand for pointing it out.<br /><br /><span style="font-weight: bold;">The Mona Lisa Challenge</span><br /><br />Let's see what your favorite language can do. The challenge is to write a small program that solves the Mona Lisa problem using Genetic Programming.<br /><br />Show us some code!<br /><br />Some of the languages I'd like to see are Haskell, Factor, Potion, Ioke, Erlang among lots of others.<br /><br />Don't forget to leave a link in the comment section of this post.<br /><br /><span style="font-weight: bold;">The code</span><br /><br />Here's the <a href="http://github.com/ynd/mona-clojure/tree/master/">github</a> repository.<br /><br />Please read the <a href="http://github.com/ynd/mona-clojure/blob/master/mona-clojure.clj">source code with syntax highlighting</a> on github.<br /><br />The following is the <span style="font-weight: bold;">full</span> code listing for the <i>impatient</i> only.<br /><br /><pre name="code" class="python"><br />(import<br /> '(java.awt Graphics Graphics2D Color Polygon)<br /> '(java.awt.image BufferedImage PixelGrabber)<br /> '(java.io File)<br /> '(javax.imageio ImageIO)<br /> '(javax.swing JFrame JPanel JFileChooser))<br /><br />; ---------------------------------------------------------------------<br />; This section defines the building blocks of the genetic programs.<br /><br />; color :: Integer -> Integer -> Integer -> Integer -> Color<br />(defn color [red blue green alpha] {:type :Color :red red :blue blue :green green :alpha alpha})<br /><br />; point :: Integer -> Integer -> Point<br />(defn point [x y] {:type :Point :x x :y y})<br /><br />; polygon :: Color -> [Point] -> Polygon<br />(defn polygon [color points] {:type :Polygon :color color :points points})<br /><br />; draw-polygon :: Graphics -> Polygon -> Nothing<br />(defn draw-polygon [graphics polygon]<br /> (doto graphics<br /> (.setColor (new Color (:red (:color polygon)) <br /> (:blue (:color polygon))<br /> (:green (:color polygon))<br /> (:alpha (:color polygon))))<br /> (.fillPolygon (let [jpolygon (new Polygon)]<br /> (doseq [p (:points polygon)] (. jpolygon (addPoint (:x p) (:y p))))<br /> jpolygon)))<br /> nil)<br /><br />; ----------------------------------------------------------------------<br />; This sections defines helper functions.<br /><br />; random-double :: Double<br />(defn random-double<br /> "Returns a double between -1.0 and 1.0."<br /> []<br /> (- (* 2 (rand)) 1))<br /><br />; remove-item :: Sequence -> Integer -> Sequence<br />(defn remove-item<br /> "Returns a sequence without the n-th item of s."<br /> [s n]<br /> (cond<br /> (vector? s) (into (subvec s 0 n)<br /> (subvec s (min (+ n 1) (count s)) (count s)))<br /> (list? s) (concat (take n s)<br /> (drop (inc n) s))))<br /><br />; replace-item :: [a] -> Integer -> a -> [a]<br />(defn replace-item<br /> "Returns a list with the n-th item of l replaced by v."<br /> [l n v]<br /> (concat (take n l) (list v) (drop (inc n) l)))<br /><br />; grab-pixels :: BufferedImage -> [Integer]<br />(defn grab-pixels<br /> "Returns an array containing the pixel values of image."<br /> [image]<br /> (let [w (. image (getWidth))<br /> h (. image (getHeight))<br /> pixels (make-array (. Integer TYPE) (* w h))]<br /> (doto (new PixelGrabber image 0 0 w h pixels 0 w)<br /> (.grabPixels))<br /> pixels))<br /><br />; ----------------------------------------------------------------------<br />; This sections define the primitives of the genetic algorithm.<br /><br />; program :: S-Expression -> Maybe Integer -> Maybe BufferedImage -> Program<br />(defn program [code fitness image] {:type :Program :code code :fitness fitness :image image})<br /><br />; initial-program :: Program<br />(def initial-program (program '(fn [graphics]) nil nil))<br /><br />; program-header :: Program -> S-Expression<br />(defn program-header [p] (take 2 (:code p)))<br /><br />; program-expressions :: Program -> S-Expression<br />(defn program-expressions [p] (drop (count (program-header p)) (:code p)))<br /><br />; mutate :: a -> Map -> a<br />(defmulti mutate :type)<br /><br />; mutate :: Color -> Map -> Color<br />(defmethod mutate :Color [c settings]<br /> (let [dr (int (* (:red c) (random-double)))<br /> dg (int (* (:green c) (random-double)))<br /> db (int (* (:blue c) (random-double)))<br /> da (int (* (:alpha c) (random-double)))]<br /> (assoc c :red (max (min (- (:red c) dr) 255) 0)<br /> :green (max (min (- (:green c) dg) 255) 0)<br /> :blue (max (min (- (:blue c) db) 255) 0)<br /> :alpha (max (min (- (:alpha c) da) 255) 0))))<br /><br />; mutate :: Point -> Map -> Point<br />(defmethod mutate :Point [p settings]<br /> (let [dx (int (* (:x p) (random-double)))<br /> dy (int (* (:y p) (random-double)))]<br /> (assoc p :x (max (min (- (:x p) dx) (:image-width settings)) 0)<br /> :y (max (min (- (:y p) dy) (:image-height settings)) 0))))<br /><br />; mutate :: Polygon -> Map -> Polygon<br />(defmethod mutate :Polygon [p settings] <br /> ; mutate-point :: Polygon -> Map -> Polygon<br /> (defn mutate-point [p settings]<br /> (let [n (rand-int (count (:points p)))]<br /> (update-in p [:points n] (fn [point] (mutate point settings)))))<br /><br /> ; mutate-color :: Polygon -> Map -> Polygon<br /> (defn mutate-color [p settings] (assoc p :color (mutate (:color p) settings)))<br /> <br /> (let [roulette (rand-int 2)]<br /> (cond<br /> (= 0 roulette) (mutate-point p settings)<br /> (= 1 roulette) (mutate-color p settings))))<br /><br />; mutate :: Program -> Map -> Program<br />(defmethod mutate :Program [p settings]<br /> ; add-polygon :: Program -> Map -> Program<br /> (defn add-polygon [p settings]<br /> (assoc p :code <br /> (concat (:code p)<br /> [(list 'draw-polygon<br /> (first (nth (:code initial-program) 1))<br /> (polygon<br /> (color (rand-int 255) (rand-int 255) (rand-int 255) (rand-int 255))<br /> (vec (map <br /> (fn [n]<br /> (point <br /> (rand-int (:image-width settings))<br /> (rand-int (:image-height settings))))<br /> (range 5)))))])<br /> :fitness nil :image nil))<br /><br /> ; remove-polygon :: Program -> Map -> Program<br /> (defn remove-polygon [p settings]<br /> (let [n (rand-int (count (program-expressions p)))]<br /> (assoc p :code (concat (program-header p)<br /> (remove-item (program-expressions p) n))<br /> :fitness nil :image nil)))<br /><br /> ; mutate-polygon :: Program -> Map -> Program<br /> (defn mutate-polygon [p settings]<br /> (let [expressions (program-expressions p)<br /> n (rand-int (count expressions))<br /> target (nth expressions n)]<br /> (assoc p :code<br /> (concat (program-header p)<br /> (replace-item expressions<br /> n<br /> (list (nth target 0)<br /> (nth target 1)<br /> (mutate (nth target 2) settings))))<br /> :fitness nil :image nil)))<br /> <br /> (let [polygon-count (count (program-expressions p))<br /> roulette (cond<br /> (empty? (program-expressions p)) 4<br /> (>= polygon-count (:max-polygons settings)) (rand-int 4)<br /> :else (rand-int 5))]<br /> (cond<br /> (> 3 roulette) (mutate-polygon p settings)<br /> (= 3 roulette) (remove-polygon p settings)<br /> (= 4 roulette) (add-polygon p settings))))<br /><br />; fitness :: Program -> Map -> Program<br />(defn fitness [individual settings]<br /> (if (:fitness individual)<br /> individual<br /> (let [gen-image (new BufferedImage (:image-width settings)<br /> (:image-height settings)<br /> BufferedImage/TYPE_INT_ARGB)<br /> src-pixels (:source-pixels settings)]<br /> (apply (eval (:code individual)) [(. gen-image (createGraphics))])<br /> (def gen-pixels (grab-pixels gen-image))<br /> (loop [i (int 0)<br /> lms (int 0)]<br /> (if (< i (alength gen-pixels))<br /> (let [src-color (new Color (aget src-pixels i))<br /> gen-color (new Color (aget gen-pixels i))<br /> dr (- (. src-color (getRed)) (. gen-color (getRed)))<br /> dg (- (. src-color (getGreen)) (. gen-color (getGreen)))<br /> db (- (. src-color (getBlue)) (. gen-color (getBlue)))]<br /> (recur (unchecked-inc i) (int (+ lms (* dr dr) (* dg dg) (* db db )))))<br /> (assoc individual :fitness lms :image gen-image))))))<br /><br />; select :: [Program] -> Map -> [Program]<br />(defn select [individuals settings]<br /> (take (:select-rate settings)<br /> (sort-by :fitness<br /> (pmap (fn [i] (fitness i settings))<br /> individuals))))<br /><br />; evolve :: Map -> Nothing<br />(defn evolve [settings]<br /> (loop [i 0<br /> population (list initial-program)]<br /> (let [fittest (select population settings)<br /> newborns (map (fn [i] (mutate i settings)) fittest)]<br /> ((:new-generation-callback settings (fn [a b])) i fittest)<br /> (when-not (= (first population) (first fittest))<br /> ((:new-fittest-callback settings (fn [a b])) i fittest))<br /> (recur (inc i) (concat fittest newborns)))))<br /><br />; ----------------------------------------------------------------------<br />; This sections defines the graphical interface.<br /><br />; main :: Nothing<br />(defn main []<br /> (def file-chooser (new JFileChooser))<br /> (doto file-chooser<br /> (.setCurrentDirectory (new File "."))<br /> (.showOpenDialog nil))<br /> <br /> (let [jframe (new JFrame "Fittest Program")<br /> fittest (atom (list initial-program))<br /> image (ImageIO/read (. file-chooser (getSelectedFile)))<br /> settings {:image-width (. image (getWidth))<br /> :image-height (. image (getHeight))<br /> :source-pixels (grab-pixels image)<br /> :select-rate 1 :max-polygons 50<br /> :new-fittest-callback (fn [i f]<br /> (swap! fittest (fn [o n] n) f)<br /> (. jframe (repaint)))}]<br /> (doto jframe<br /> (.setSize (. image (getWidth)) (. image (getHeight)))<br /> (.add (proxy [JPanel] []<br /> (paint [g]<br /> (doto g <br /> (.setColor Color/white)<br /> (.fillRect 0 0 (. image (getWidth)) (. image (getHeight)))<br /> (.drawImage (:image (first @fittest)) nil 0 0)))))<br /> (.setVisible true))<br /> (evolve settings)))<br /><br />(main)<br /></pre>Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com602tag:blogger.com,1999:blog-7588060738595136253.post-79369092864715864552008-11-23T10:25:00.002-05:002008-11-23T10:48:57.925-05:00One-Time Pet Project<a style="font-weight: bold;" href="http://github.com/ynd/boni-asm/tree/master">Boni-Asm</a><br /><br />I just finished a new project. It's an <span style="font-weight: bold;">Assembler</span> that can easily support new architectures.<br /><br />I wrote it in Python for ease of development. I chose <a href="http://theory.stanford.edu/%7Eamitp/yapps/">Yapps</a> as a Parser Generator because it is the most Pythonic Parser Generator. The Yapps Grammar language is pretty easy to pick up, even though the documentation is a bit incomplete. Yapps produces LL(1) parsers so I had to be a little creative.<br /><br />Boni's best feature is the dynamicity of the code. The assembler doesn't depend on the format of the machine code being generated. That means Boni can be retargeted by changing one configuration file.<br /><br />I had a lot of fun writing it. I don't know if it'll ever be useful though. At least the very least it will show how Yapps is used.<br /><br />Anyway, have a look:<br /><a href="http://github.com/ynd/boni-asm/tree/master">http://github.com/ynd/boni-asm/tree/master</a>Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com7tag:blogger.com,1999:blog-7588060738595136253.post-9298962114171541162008-07-19T08:08:00.003-04:002009-05-28T10:06:06.963-04:00Object Oriented Programming is not Procedural programming with structures<span style="font-style: italic;">For beginners.</span><br /><br />Object Oriented Programming is not Procedural programming with structures. They are 2 different ways to think about programs. This is a brief explanation of why the two approaches are different.<br /><br /><br /><span style="font-weight: bold;">Procedural model</span><br /><br /><a href="http://en.wikipedia.org/wiki/Procedural_programming">Procedural</a> programs are a series of steps. It is the most natural and widespread style of programming. The first <a href="http://en.wikipedia.org/wiki/High-level_programming_language">HL</a> language - <a href="http://en.wikipedia.org/wiki/Plankalk%C3%BCl" title="Plankalkül">Plankalkül</a> - was a procedural language.<br /><br />I don't know why Procedural programming is natural... but think about the first program you were taught. Nope, not "Hello World!". More like the program to tie your shoes, or the program to use the big boy's potty. The program they taught you was a series of sequential actions - a procedure.<br /><br />We use Procedural programming all the time. <a href="http://www.wikihow.com/Bake-a-Cake">Cooking recipes</a> for example. Procedural programming is easier to grasp.<br /><br /><br /><span style="font-weight: bold;">The OO model</span><br /><br /><a href="http://en.wikipedia.org/wiki/Functional_programming"></a><a href="http://en.wikipedia.org/wiki/Object_oriented_programming">Object Oriented</a> programming shift the focus away from the procedure to the definition and combination of high-level constructs. These constructs are called Objects.<br /><br />Instead of being too theoretic, I'll jump into an example to illustrate why this is a major paradigm shift.<br /><br /><br /><span style="font-weight: bold;">Example: Procedural approach</span><br /><br />I found a <a href="http://dev-logger.blogspot.com/2008/07/ruby-programming-is-art.html">good snippet</a> to illustrate how they differ. Many thanks to Martin Carel.<br /><pre name="code" class="python"><br />#!/usr/bin/env python<br /># Thanks to Martin Carel from http://dev-logger.blogspot.com/<br /><br />import time<br />import urllib<br />from elementtree import ElementTree<br /><br />feed_link = "http://feeds.feedburner.com/37signals/beMH"<br />title, published_date = "", ""<br />TITLE_PATH = ".//item/title"<br />DATE_PATH = ".//item/pubDate"<br /><br />while True:<br /> feed = urllib.urlopen(feed_link).read()<br /> tree = ElementTree.fromstring(feed)<br /> fetched_title = tree.findtext(TITLE_PATH)<br /> fetched_published_date = tree.findtext(DATE_PATH)<br /><br /> if title != fetched_title:<br /> print fetched_title, fetched_published_date<br /> title, published_date = fetched_title, fetched_published_date<br /><br /> time.sleep(5 * 60)<br /></pre><br />Writing this procedure was straightforward. I simply listed the steps needed to get the desired result. I didn't spend a lot of time analyzing my problem.<br /><br /><br /><span style="font-weight: bold;">How am I going to write the OO program?</span><br /><br />First, I have to think about the task at hand. Analysis is important. You cannot have a good OO program without understand your problem space well.<br /><br />For example, I have to identify what concepts of the problem domain I will model as objects. Then I will define the relations between objects and what operations will be possible on them.<br /><br />Finally, I have to express the program as a combination of the building blocks I defined earlier.<br /><br /><br /><span style="font-weight: bold;">Example: Hybrid functional/OO approach</span><br /><pre name="code" class="python"><br />#!/usr/bin/env python<br /># Thanks to Martin Carel from http://dev-logger.blogspot.com/<br /><br />import time<br />import urllib<br />from elementtree import ElementTree<br /><br />class Feed:<br /> class Entry:<br /> def __init__(self, elem):<br /> self.title = elem.findtext("./title")<br /> self.last_updated = elem.findtext("./pubDate")<br /><br /> def __eq__(self, other):<br /> return True if self.title == other.title else False<br /><br /> def __init__(self, url):<br /> self.url = url<br /> self.entries = []<br /><br /> def fetch(self):<br /> feed = urllib.urlopen(self.url).read()<br /> tree = ElementTree.fromstring(feed)<br /> self.entries = [Feed.Entry(e) for e in tree.findall(".//item")]<br /><br /> def has_recent_post(self):<br /> old = self.entries[:1]<br /> self.fetch()<br /> return old != self.entries[:1]<br /><br /># High-level functionality<br />feed = Feed("http://feeds.feedburner.com/37signals/beMH")<br />while True:<br /> if feed.has_recent_post():<br /> print feed.entries[0].title, feed.entries[0].last_updated<br /> time.sleep(5 * 60)<br /></pre><br /><br /><span style="font-weight: bold;">Why is this better?</span><br /><br />You know instantly what the program does by looking at the high-level functionality. That's because I was able to match my program to the problem definition by defining the right constructs.<br /><br />The OO approach forces you to create black boxes. A black box is an abstract element that you can use through it's input and output without having to know it's implementation. Engineers use them everyday.<br /><br />Black boxes reduce complexity dramatically. It's easy to reason about them. First, each has an isolated and simple function. Second, the interactions between black boxes are explicit. They also reduce complexity by restricting the number of possible interactions. And since a black box can be made of other black boxes, they can organize your program into neat and coherent layers.<br /><br />Black box designs are easier to understand. You can even choose to know only the boxes and layers of boxes that matter to you. You cannot do the same with a procedural program because nothing is isolated into a component that you can understand <span>independently</span>. You always have to understand how everything interacts.<br /><br />The OO program is easier to extend because it has well defined extension points. New functionality can be added by adding methods to the class. And it can be used by using the method from the main program.<br /><br />Lastly, having high-level components allows you to perform high-level operations like late binding and reflection. This is the source of OOP's real power and prowess. It is a very wide and interesting topic so I won't cover that here.Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com6tag:blogger.com,1999:blog-7588060738595136253.post-11880807682034997112008-06-30T22:34:00.000-04:002008-06-30T23:11:17.304-04:00The difference between smalltalk and the rest<a href="http://en.wikipedia.org/wiki/Smalltalk">Smalltalk</a> programs are ecosystems.<br /><br />A program behaves like an ecosystem when the focus is put on run time - not compile time. This is a major shift.<br /><br />People coming from static languages complain that Smalltalk doesn't have Netbeans, Eclipse or whatever. Smalltalk - and potentially other dynamic languages - has something different.<br /><br />Smalltalk provides an environment where you can edit, run and analyze code in real time. Imagine being able to grow a program. Imagine being able observe it grow. Imagine being able to painlessly debug and analyze it. This is what it means to focus on run time.<br /><br />This is hard to understand if you're coding in a glorified notepad.<br /><br />When you're coding in Smalltalk your program is running persistently in the background. It is <span style="font-weight: bold;">alive</span>. Inspecting it is just a click away. When you create an object, you can actually right-click on it and get a list of it's methods. You can just as easily change the implementations of these methods. Without restarting anything.<br /><br />It's a major cultural shift. Smalltalk programmers never fight the compiler, they spend their time debugging their programs. This is a different way of developing a program.<br /><br />Don't trust me. <a href="http://www.youtube.com/watch?v=yH-ZSoRXx-c&feature=related">Take 2 minutes and see something interesting.</a>Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com4tag:blogger.com,1999:blog-7588060738595136253.post-83274308171831824892008-06-17T19:15:00.000-04:002008-06-25T18:51:38.897-04:00Here's why dynamic languages are slow and how to fix it<p>Dynamic languages are emerging as the Next Big Thing. They are known for making development faster, being more powerful and more flexible. Today, <a href="http://www.itasoftware.com/">more</a> <a href="http://www.python.org/about/success/usa/">and</a> <a href="http://www.python.org/about/success/">more</a> people are using them in production environments. However, one problem <a href="http://java.sys-con.com/read/193146.htm">stands in the way</a> of mass adoption: SPEED. There is an urban legend that dynamic programs are way slower than their static counterparts. Here's my take on it.</p><br /><span style="font-weight: bold;">Why are dynamic languages slow TODAY?</span><p>The purpose of a dynamic language is to have as few static elements as possible. The idea is that this offers more flexibility. For example, in Python method calls are never static. This means that the actual code that will be executed is known only at run time. This is what makes monkey patching possible. This is what allows you to have <a href="http://www.djangoproject.com/documentation/testing/">great unit testing frameworks</a>.</p><p></p><pre name="code" class="python"><br /># globals.py<br />A = 2<br /></pre><pre name="code" class="python"><br /># main.py<br />from globals import A<br />A = []<br /></pre>Dynamic languages leave as many decisions as possible to run time. What is the type of <span style="font-style: italic;">A</span>? You can only know for sure when the code runs because it can be changed at any point in the program.<br />The result is that it is <a href="http://www.iro.umontreal.ca/%7Efeeley/papers/ifl07-feeley.pdf">hard to analyse dynamic languages</a> in order to make optimizations. Compared to static languages - which offer plenty of opportunities for optimization - dynamic languages are hard to optimize. Thus their implementations are usually slow.<p></p><p>The problem with dynamic languages is that it isn't trivial to optimize an addition. You can hardly know what '+' will be binded to at runtime. You probably can't even infer the types of the operands. This is the result of <span style="font-style: italic;">mutation</span>. In Python, almost everything is mutable. This leaves few information the compiler can rely on.</p><br /><span style="font-weight: bold;">Does mutability hurt performance and why?</span><p>It can, depending on the case. Let me illustrate how by comparing the factorial function in C and Python. Don't think of this as a <a href="http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=gcc&lang2=python">benchmark</a>. This is just an example.</p><p>Compiling the factorial function in C with <a href="http://www.llvm.org/">LLVM-GCC</a> will generate efficient machine code.</p><pre name="code" class="cpp"><br />// Factorial in C<br />int fac(int n) {<br /> if (n == 0) return 1;<br /> return n*fac(n-1);<br />}<br />int main(){<br /> return fac(30);<br />}<br /></pre><pre name="code" class="cpp"><br />; Assembly generated by LLVM-GCC<br />_main:<br /> movl $1, %eax<br /> xorl %ecx, %ecx<br /> movl $30, %edx<br />.align 4,0x90<br />LBB1_1: ## bb4.i<br /> imull %edx, %eax<br /> decl %edx<br /> incl %ecx<br /> cmpl $30, %ecx<br /> jne LBB1_1 ## bb4.i<br />LBB1_2: ## fac.exit<br /> ret<br /></pre><p></p><p>The compiler was able to infer many properties from the source code. For example, it concluded that the <span style="font-style: italic;">fac</span> function referenced in <span style="font-style: italic;">main</span> was the <span style="font-style: italic;">fac</span> defined at compile time. This allowed the compiler to replace the assembly <span style="font-style: italic;">call</span> instruction with <span style="font-style: italic;">fac</span>'s code. The function was then specialized for the call site and thanks to static typing, the compiler was able to transform each arithmetic operations into direct machine instructions.<br />Can you notice the other optimizations?</p><p>Let's look at how CPython executes the factorial.</p><pre name="code" class="python"># fac.py<br />def fac(n):<br /> return 1 if n == 0 else n * fac(n -1)<br />fac(30)<br /></pre>First, <i>fac.py</i> is parsed and translated to <a href="http://en.wikipedia.org/wiki/Bytecode">bytecode</a> instructions. Then the bytecode instructions are interpreted by the <a href="http://www.devshed.com/c/a/Python/How-Python-Runs-Programs/">CPython Virtual Machine</a>.<pre name="code" class="python"><br /># CPython Bytecode for fac.py<br /># Think of this as an interpreted language which Python is translated into.<br /># See http://docs.python.org/lib/bytecodes.html<br /># fac<br />11 0 LOAD_FAST 0 (n)<br /> 3 LOAD_CONST 1 (0)<br /> 6 COMPARE_OP 2 (==)<br /> 9 JUMP_IF_FALSE 7 (to 19)<br /> 12 POP_TOP <br /> 13 LOAD_CONST 2 (1)<br /> 16 JUMP_FORWARD 18 (to 37)<br />>> 19 POP_TOP <br /> 20 LOAD_FAST 0 (n)<br /> 23 LOAD_GLOBAL 0 (fac)<br /> 26 LOAD_FAST 0 (n)<br /> 29 LOAD_CONST 2 (1)<br /> 32 BINARY_SUBTRACT<br /> 33 CALL_FUNCTION 1<br /> 36 BINARY_MULTIPLY<br />>> 37 RETURN_VALUE<br /># main<br />14 0 LOAD_GLOBAL 0 (fac)<br /> 3 LOAD_CONST 1 (30)<br /> 6 CALL_FUNCTION 1<br /> 9 RETURN_VALUE<br /><br /></pre><p></p><p>CPython could not inline the call to <i>fac</i> because this would violate the language's semantics. In Python, <i>fac.py</i> could be imported at run time by another module. It cannot inline <i>fac</i> into main because a sub-module could change the binding of <i>fac</i> and thus invalidate <i>main</i>. And because <i>main</i> doesn't have it's own copy of <i>fac</i>, the code cannot be specialized for this particular call. This hurts because it would be <a href="http://portal.acm.org/citation.cfm?id=277652.277743">very beneficial</a> to specialize the function for an integer argument.</p><p></p><p>Notice that there are no references to machine addresses. CPython adds a layer of indirection to access every object in order to implement the dynamism of Python. For example, <i>main</i> is found by a look-up in a table. Even constant numbers are found through look-ups. This adds a significant amount of slow memory read/writes and <a href="http://citeseer.ist.psu.edu/cache/papers/cs/32018/http:zSzzSzwww.jilp.orgzSzvol5zSzv5paper12.pdf/ertl03structure.pdf">indirect jumps</a>.</p><p></p><p>Python doesn't even contain any explicit hints you can give to help the compiler. This makes the problem of optimizing Python non-trivial.</p><br /><span style="font-weight: bold;">What about type inference?</span><p>The problem of type inference in dynamic languages remains unsolved. Type inference is a form of static analysis. Static analysis is the analysis of source code at compile time to derive some "truths" about it. You can imagine how this falls short for dynamic languages.<br /></p><p>Michael Salib attempted to solve this problem with <a href="http://www.salib.com/writings/thesis/thesis.pdf">StarKiller</a>. The compiler manages type inference by collecting more information than usual and using the CTA algorithm. Instead of compiling each module separatly, like most compilers, the whole program is analyzed and compiled in one pass. The knowledge of the complete program opens the door to more optimizations. The <span style="font-style: italic;">fac</span> function of the previous example can be specialized by Starkiller because it knows how it will be used.</p><p>Though the work seems very promising, it has three major flaws. First, the compiler accepts only a subset of the Python language. Advanced functions like <span style="font-style: italic;">eval</span> and <span style="font-style: italic;">exec</span> aren't supported. Second, whole-program analysis doesn't scale with bigger projects. Compiling 100,000 LOC would take a prohibitive amount of time. Third, the compiler violates Python's semantics by doing whole-program analysis. Like most dynamic languages, the import mechanism of Python is done at runtime. The language doesn't guarantee that the module available at compile time is the same as the module available at run time.</p><p>Read <a href="http://www.ocf.berkeley.edu/%7Ebac/thesis.pdf">this</a> for <a href="http://www.iro.umontreal.ca/%7Efeeley/papers/ifl07-feeley.pdf">more</a>.</p><br /><span style="font-weight: bold;">What about VMs?</span><p>Virtual Machines are a natural fit for dynamic languages. VM with JIT compilers are able to optimize a dynamic program without having to guess it's behavior in advance. This saves a lot of heavy lifting. Programs are optimized simply by observing their behavior while they run. This is known as <span style="font-style: italic;">dynamic analysis</span>. For instance, noticing that <span style="font-style: italic;">fac</span> is often called with an integer argument, the VM could create a new version of that function specialized for integers and use it instead.</p><p>In my <i>opinion</i> Virtual Machines are not a long-term solution.<br /></p><ol><li><a href="http://en.wikipedia.org/wiki/Self-hosting">Self-hosting</a> a VM <a href="http://codespeak.net/pypy/dist/pypy/doc/home.html">is</a> <a href="http://www.squeak.org/Features/TheSqueakVM/">prohibitive</a>.</li><li>A VM sets a limit on the kinds of programs you can make. No Operating Systems, no drivers, no real-time systems, etc.</li><li>Optimizing a program run through a VM is hard because you cannot know exactly what is going on behind the hood. There are many layers and many corners where performance can slip out.</li></ol><p>For most projects, these problems aren't an issue. But I believe their existence would restrain dynamic languages. They are enough to prevent a dynamic language from being a general purpose tool. And that is what people want: no restrictions, no <a href="http://theocacao.com/document.page/421">surprises</a>, pure freedom.</p><br /><span style="font-weight: bold;">How would I make them faster?</span><pre name="code" class="python"><br />from types import ModuleType<br />import re<br />declare(re, type=ModuleType, constant=True, inline=True)<br /></pre><p>A compiler helped by Static Annotations is the way to go. Please don't put all static annotations in the same bag. Static annotations like type declarations don't have to be as painful as JAVA's. Annotations are painful in Java because they are pervasive and often useless. They restrict the programmer. Programmers have to fight them. Annotations can be just the opposite. They can give the programmer more freedom! With them, programmers can set constraints to their code where it matters. Because they have the choice, static annotations become a tool that offers MORE flexibility.</p><p>A savvy programmer could reduce the dynamism of his code at a few key points. Just enough to allow type inference and the likes to do their job well. Optimizing some code would usually just become a matter of expressing explicitly the natural constraints that apply to it.</p><pre name="code" class="python"><br /># Just an example.<br />def fac(n):<br /> assert type(n) in [float, int]<br /> return 1 if n == 0 else n * fac(n -1)<br /></pre><p></p><p>There are a many ways to implement static annotations in dynamic languages. I believe the flexibility of dynamic languages can allow static annotations to be very convenient. How would you do it?</p>Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com92tag:blogger.com,1999:blog-7588060738595136253.post-24464095330108644912008-06-14T14:19:00.000-04:002008-06-16T12:12:51.572-04:00What everybody ought to know about RESEARCH<span style="font-style: italic;"></span><blockquote><span style="font-style: italic;">Why do so few scientists make significant contributions and so many are forgotten in the long run?</span></blockquote><span style="font-size:85%;"><a style="font-style: italic;" href="http://en.wikipedia.org/wiki/Richard_Hamming">Richard Hamming</a></span><span style="font-style: italic;font-size:85%;" > asked himself and some of the <a href="http://en.wikipedia.org/wiki/Bell_Labs">greatest scientists of the 20th century</a> this very question. In his classic "</span><span style="font-size:85%;"><a style="font-style: italic;" href="http://www.cs.virginia.edu/%7Erobins/YouAndYourResearch.html">You and Your Research</a></span><span style="font-style: italic;font-size:85%;" >" talk, he relates what led him to the discovery of the </span><span style="font-size:85%;"><a style="font-style: italic;" href="http://en.wikipedia.org/wiki/Hamming_code">Hamming Code</a></span><span style="font-style: italic;font-size:85%;" > and the </span><span style="font-size:85%;"><a style="font-style: italic;" href="http://en.wikipedia.org/wiki/Hamming_distance">Hamming Distance</a></span><span style="font-style: italic;font-size:85%;" > among other things. The following is my humble attempt to summarize it to make it more accessible.</span><br /><br /><span style="font-weight: bold;">1) Research is not just a matter of luck.</span> Consider Einstein for example. Can luck explain that he discovered Special Relativity and - 10 years later - the General Theory of Relativity? One after another, you <a href="http://en.wikipedia.org/wiki/Alan_Turing">see</a> <a href="http://en.wikipedia.org/wiki/Isaac_Newton">people</a> <a href="http://en.wikipedia.org/wiki/John_von_Neumann">setting</a> a pattern of Great Science.<br /><br /><span style="font-weight: bold;">2) Successful scientists are courageous.</span> Once you get your courage up and believe that you can do important problems, then you can. If you think you can't, almost surely you are not going to. Research is not easy. If you always give up early on, you won't get anywhere. Think and continue to think <a href="http://en.wikipedia.org/wiki/Charles_Darwin">any under circumstance</a>.<br /><br /><span style="font-weight: bold;">3) Don't work on big problems right away.</span> <a href="http://en.wikipedia.org/wiki/Riemann_hypothesis">Research is hard.</a> Expect to be paralyzed if you skip stepping stones to work a big problem. Build some background knowledge by working on smaller problems first.<br /><br /><span style="font-weight: bold;">4) Work hard.</span> Given two people of approximately the same ability with one working 10% more than the other, the latter will outproduce the former more than twice over the course of a lifetime. The more you know, the more you learn; the more you learn, the more you can do; the more you can do, the more the opportunity.<br /><br /><span style="font-weight: bold;">5) It's important to cultivate ambiguity.</span> Believe in you theory enough to push forward. Doubt it enough to notice the flaws and the errors. If you don't believe, you will never get started. If you don't doubt, you may lose a lot of time working on something wrong. Noticing and fixing flaws will make your theory stronger.<br /><br /><span style="font-weight: bold;">6) You have to want to do something significant.</span> To quote Pasteur, "<a href="http://en.wikipedia.org/wiki/Discoveries_of_anti-bacterial_effects_of_penicillium_moulds_before_Fleming">Luck favors the prepared mind</a>". You can't win Lotto without participating. If you never try to work on anything significant, the odds are against you. Newton used to say "If others would think as hard as I did, then they would get similar results". You have to try.<br /><br />If you enjoyed this, I recommend <a href="http://www.cs.virginia.edu/%7Erobins/YouAndYourResearch.html">the original talk</a>.Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com6tag:blogger.com,1999:blog-7588060738595136253.post-43765353348223637122008-06-13T18:10:00.000-04:002008-06-16T00:33:06.277-04:00The secret of the LLVM C bindingsEver wanted to use <a href="http://www.llvm.org/">LLVM</a> from C? Can't find any documentation? Welcome.<br /><br />Since I'm considering retargeting <a href="http://sourceforge.net/projects/clisp/">CLISP</a>'S JIT Compiler I've been experimenting with LLVM. LLVM is an optimizing compiler for a virtual instruction set. Technically, it is very interesting. And this year, with Apple and CLANG in the game, it seems to be here to stay.<br /><span style="font-size:180%;"><br /></span><span style="font-weight: bold;font-size:100%;" >A Factorial in C with LLVM</span><br />Let's make a factorial function using the C bindings of LLVM 2.3+.<br />The function we will describe in LLVM instructions is illustrated below.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWyoAzPAag8DIxJz_YKcNK_nHpc27WzSda9g00o3iR7pq54itATK8HtXBHwhCAnUnwUwHhaz9CYQzS7bDuaqxOQEe_VZKCiJa98YClmac49cUHko7u71kGvuLPE3vdoxJvpwOuciqXVZI/s1600-h/fac.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 282px; height: 349px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWyoAzPAag8DIxJz_YKcNK_nHpc27WzSda9g00o3iR7pq54itATK8HtXBHwhCAnUnwUwHhaz9CYQzS7bDuaqxOQEe_VZKCiJa98YClmac49cUHko7u71kGvuLPE3vdoxJvpwOuciqXVZI/s320/fac.png" alt="" id="BLOGGER_PHOTO_ID_5211503703711110722" border="0" /></a>I inserted the <span style="font-style: italic;">phi</span> instruction manually to make things more interesting.<br />Paste this in your favorite editor and save it as "fac.c":<br /><pre name="code" class="cpp"><br />// Headers required by LLVM<br />#include <llvm-c/Core.h><br />#include <llvm-c/Analysis.h><br />#include <llvm-c/ExecutionEngine.h><br />#include <llvm-c/Target.h><br />#include <llvm-c/Transforms/Scalar.h><br /><br /><br />// General stuff<br />#include <stdlib.h><br />#include <stdio.h><br /><br /><br />int main (int argc, char const *argv[])<br />{<br /> char *error = NULL; // Used to retrieve messages from functions<br /> LLVMModuleRef mod = LLVMModuleCreateWithName("fac_module");<br /> LLVMTypeRef fac_args[] = { LLVMInt32Type() };<br /> LLVMValueRef fac = LLVMAddFunction(mod, "fac", LLVMFunctionType(LLVMInt32Type(), fac_args, 1, 0));<br /> LLVMSetFunctionCallConv(fac, LLVMCCallConv);<br /> LLVMValueRef n = LLVMGetParam(fac, 0);<br /><br /> LLVMBasicBlockRef entry = LLVMAppendBasicBlock(fac, "entry");<br /> LLVMBasicBlockRef iftrue = LLVMAppendBasicBlock(fac, "iftrue");<br /> LLVMBasicBlockRef iffalse = LLVMAppendBasicBlock(fac, "iffalse");<br /> LLVMBasicBlockRef end = LLVMAppendBasicBlock(fac, "end");<br /> LLVMBuilderRef builder = LLVMCreateBuilder();<br /><br /> LLVMPositionBuilderAtEnd(builder, entry);<br /> LLVMValueRef If = LLVMBuildICmp(builder, LLVMIntEQ, n, LLVMConstInt(LLVMInt32Type(), 0, 0), "n == 0");<br /> LLVMBuildCondBr(builder, If, iftrue, iffalse);<br /><br /> LLVMPositionBuilderAtEnd(builder, iftrue);<br /> LLVMValueRef res_iftrue = LLVMConstInt(LLVMInt32Type(), 1, 0);<br /> LLVMBuildBr(builder, end);<br /><br /> LLVMPositionBuilderAtEnd(builder, iffalse);<br /> LLVMValueRef n_minus = LLVMBuildSub(builder, n, LLVMConstInt(LLVMInt32Type(), 1, 0), "n - 1");<br /> LLVMValueRef call_fac_args[] = {n_minus};<br /> LLVMValueRef call_fac = LLVMBuildCall(builder, fac, call_fac_args, 1, "fac(n - 1)");<br /> LLVMValueRef res_iffalse = LLVMBuildMul(builder, n, call_fac, "n * fac(n - 1)");<br /> LLVMBuildBr(builder, end);<br /><br /> LLVMPositionBuilderAtEnd(builder, end);<br /> LLVMValueRef res = LLVMBuildPhi(builder, LLVMInt32Type(), "result");<br /> LLVMValueRef phi_vals[] = {res_iftrue, res_iffalse};<br /> LLVMBasicBlockRef phi_blocks[] = {iftrue, iffalse};<br /> LLVMAddIncoming(res, phi_vals, phi_blocks, 2);<br /> LLVMBuildRet(builder, res);<br /><br /> LLVMVerifyModule(mod, LLVMAbortProcessAction, &error);<br /> LLVMDisposeMessage(error); // Handler == LLVMAbortProcessAction -> No need to check errors<br /><br /><br /> LLVMExecutionEngineRef engine;<br /> LLVMModuleProviderRef provider = LLVMCreateModuleProviderForExistingModule(mod);<br /> error = NULL;<br /> LLVMCreateJITCompiler(&engine, provider, &error);<br /> if(error) {<br /> fprintf(stderr, "%s\n", error);<br /> LLVMDisposeMessage(error);<br /> abort();<br /> }<br /><br /> LLVMPassManagerRef pass = LLVMCreatePassManager();<br /> LLVMAddTargetData(LLVMGetExecutionEngineTargetData(engine), pass);<br /> LLVMAddConstantPropagationPass(pass);<br /> LLVMAddInstructionCombiningPass(pass);<br /> LLVMAddPromoteMemoryToRegisterPass(pass);<br /> // LLVMAddDemoteMemoryToRegisterPass(pass); // Demotes every possible value to memory<br /> LLVMAddGVNPass(pass);<br /> LLVMAddCFGSimplificationPass(pass);<br /> LLVMRunPassManager(pass, mod);<br /> LLVMDumpModule(mod);<br /><br /> LLVMGenericValueRef exec_args[] = {LLVMCreateGenericValueOfInt(LLVMInt32Type(), 10, 0)};<br /> LLVMGenericValueRef exec_res = LLVMRunFunction(engine, fac, 1, exec_args);<br /> fprintf(stderr, "\n");<br /> fprintf(stderr, "; Running fac(10) with JIT...\n");<br /> fprintf(stderr, "; Result: %d\n", LLVMGenericValueToInt(exec_res, 0));<br /><br /> LLVMDisposePassManager(pass);<br /> LLVMDisposeBuilder(builder);<br /> LLVMDisposeExecutionEngine(engine);<br /> return 0;<br />}<br /></pre><br /><span style="font-weight: bold;font-size:100%;" >Compiling the code</span><br />Generating the object file is a no-brainer:<br /><pre name="code" class="cpp" cols="440"><br />gcc `llvm-config --cflags` -c fac.c<br /></pre>Linking is a little trickier. Even though you are writing C code, you <a href="http://www.parashift.com/c++-faq-lite/mixing-c-and-cpp.html">have to use a C++ linker</a>.<br /><pre name="code" class="cpp"><br />g++ `llvm-config --libs --cflags --ldflags core analysis executionengine jit interpreter native` fac.o -o fac<br /></pre>All set!Yann N. Dauphinhttp://www.blogger.com/profile/04848263488684342076noreply@blogger.com17