tag:blogger.com,1999:blog-55222302626494471432024-03-06T19:34:21.425-08:00stuffVishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.comBlogger30125tag:blogger.com,1999:blog-5522230262649447143.post-45912125998253305262013-11-20T21:34:00.000-08:002013-11-20T21:34:21.185-08:00The many faces of nameless chunks of code in Ruby<div dir="ltr" style="text-align: left;" trbidi="on">
The internet is littered with posts about the differences between blocks/procs and lambdas. But when experienced programmers first encounter this topic, they have several questions about it and hence finding themselves having to read several posts or threads. I'm going to try to summarize the answers to several related questions here.<br /><br />At a very high level as far as the philosophy behind the design of the language goes, there is a question of why there are different ways to do things. One of the guiding principles at play is that <a href="http://stackoverflow.com/questions/6401361/in-ruby-theres-more-than-one-way-of-doing-the-same-thing-what-does-this-mea">there is more than one way to do everything</a>. So if it makes sense to have two different approaches to do something that are convenient in different contexts, then both approaches often exist so that you have the more convenient option at hand.<br /><br />Another important guiding principle that's a part of ruby is <a href="http://en.wikipedia.org/wiki/Principle_of_least_astonishment">the principle of least astonishment.</a> I'm just mentioning it here but I'll talk about why its relevant further down.<br />
<br />
On a mechanical level it's important to understand the differences between lambdas and blocks/procs. <a href="http://awaxman11.github.io/blog/2013/08/05/what-is-the-difference-between-a-block/">Here is one source</a>. The important differences are argument checking, and the behavior of return, break and continue. It's important not only to understand how they are different, but that there are things you can do with lambdas that you cannot do with blocks and there are things you can do with blocks that you cannot do with lambdas. <br />
<br />
The next thing to understand is what they are.<br />
<br />
<ul style="text-align: left;">
<li>Lambdas are lambdas just like you see in most other languages where anonymous functions exist. It's a closure that you can pass around as a parameter or return and then call. </li>
<li>Blocks are something completely new. They are a syntactic construct, not first class objects. At a superficial level they behave like lambdas (with the restrictions that they can only be the last parameter and so on) and the differences between blocks and lambdas have been described above.</li>
<li>Procs is like an object representation of a Block. You use a proc when you'd like to accept a block and then do something funky with it. The real decision api wise that you must make is whether you want to accept a lambda or accept a block. Procs are what you get when you peek under the hood and decide that you really need to something a little more unusual.</li>
</ul>
<div>
People who are used to lambdas find blocks and procs inelegant and confusing. Inelegant because there already is a mechanism to pass closures around. Confusing because it has unusual semantics. Once you have internalized what they are and what they can do differently, it's easy to see that these differences at times make certain things possible that would not have been possible otherwise. </div>
<div>
<br /></div>
<div>
But let's talk about this being confusing and the principle of least surprise. The reason that this seems confusing is because it's not how closures in other languages behave. But the principle of least surprise has never been about compatibility with concepts from other languages. All that the POLA says is that once you understand how something works and how to think about it, apis will ideally behave in a non-surprising manner. It does not imply that you will not have to learn how ruby works. What it DOES imply though is that there is a conceptual model that can be used to understand blocks that is different from the conceptual model people use for lambdas. One where the behavior of return in blocks is not confusing at all.</div>
<div>
<br /></div>
<div>
The way to think about blocks is that the code inside a block belongs to the function in which it is defined, and hence the semantics of the code internally should behave exactly as it would if it were outside the block. A block is not a function that you are passing in ... that's a detail of how it's implemented. A block is a chunk of code that is from your function that executes when the method you call chooses to activate it. And since its a chunk of code from your function, the return statement continues to behave the way it would behave if it were not inside the block. Code inside the block should not be thought of as special from code outside. It just happens to run at a time that's not of your choosing. it's a different mental model. <br /></div>
<div>
Continue and break are special keywords for code inside a block that break out of the block and break out of the function that took the block respectively. This makes them consistent with loops. Since blocks are often used as iterators, break and continue behave just the same inside iterators and regular loops.</div>
<div>
</div>
<br />
<br /></div>
Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com2tag:blogger.com,1999:blog-5522230262649447143.post-60699563669580192412010-10-31T11:37:00.000-07:002010-10-31T12:51:19.910-07:00Introducing StepRewrite (aka I finally understand macros)<div style="text-align: justify;">So it's finally done! I could probably do a bit more, but for the moment it's working and packaged! For a while now, I've been writing about a problem <a href="http://blog.vishnuiyengar.com/2010/09/lipstick-for-evented-programming-pig.html">I want to solve</a>, and discovering the <a href="http://blog.vishnuiyengar.com/2010/10/changing-rules.html">tools</a> to solve it. Of course it's also a problem that may not really exist, but fuck it! To really understand the motivations behind this thing I've built, follow those links above, but here is the short version. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I said that Evented IO makes you write ugly code, just to sequence a bunch of operations. I figured out that the only way to be able to sequence code normally but run it in an evented IO environment is to use macros and actually rewrite code. So I wrote <a href="http://github.com/pathsny/step_rewrite">step_rewrite</a> (which has obtained that name since it was born out of an unholy union of <a href="http://github.com/creationix/step">step.js</a> and <a href="http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBIQFjAA&url=http%3A%2F%2Fgithub.com%2Fraganwald%2Frewrite&ei=RbnNTO3UIJKCvgOFo_TwDw&usg=AFQjCNHEdCj3kgPEyN_ecvkUcEjXdM28Dg">rewrite</a>). If you install, it you can write code like this</div><script src="http://gist.github.com/656984.js?file=step_rewrite.rb"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">that behaves as if it was written like this. </div><script src="http://gist.github.com/656984.js?file=original.rb"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">This doesn't mean that you are forced to (or should in fact) write <b>every</b> block in this manner. It's meant to be used only when the blocks exist purely to sequence the rest of the method to occur inside a callback. i.e. when you really <b>do</b> intend what the first piece of code implies. That you have a series of operations that should occur one after another, and it just so happens, that they perform IO. (if you squint really hard, you can pretend the &_ bits are invisible). </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So step_rewrite, Can be used either, as a function that takes a block to eval, or as a fuction that takes a block to define a method. It rewrites the code and converts every function call taking a special callback, followed by some other code into a form where the function now receives a block with the rest of the code in the block. </div><script src="http://gist.github.com/656984.js?file=hunter_rewritten.rb"></script><div style="text-align: justify;">becomes</div><script src="http://gist.github.com/656984.js?file=hunter_original.rb"></script><div style="text-align: justify;">for situations where you intend the former but your environment requires code to do the latter. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">It also converts return values into block arguments. So that</div><script src="http://gist.github.com/656984.js?file=hunter_2_rewritten.rb"></script><div style="text-align: justify;">becomes</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/656984.js?file=hunter_2_original.rb"></script><div style="text-align: justify;">This is acceptable for the most part because using &_ has made <i>hunter.kill</i> the last statement in it's block. So anything it returns will be the return value of its block. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Of course this abstraction is leaky. There are a lot of complicated situations where you have to be aware of what the converted code will look like. I just hope that 80-90% of the time, you can be oblivious to it. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">This works using the <a href="http://rubyforge.org/projects/parsetree/">ParseTree gem</a>. ParseTree converts code into <a href="http://en.wikipedia.org/wiki/S-expression">S-Expressions</a>, the language of macros. Here are some examples of S-expressions. </div><script src="http://gist.github.com/656984.js?file=s-expression.rb"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Given the S-expression, I can now manipulate it. Chopping out bits, wrapping it in other pieces. The resulting S-expression is converted back into Ruby using <a href="http://seattlerb.rubyforge.org/ruby2ruby/">Ruby2Ruby</a> and I'm done :).</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/656984.js?file=ruby2ruby.rb"></script><div style="text-align: justify;">So yeah, what I <b>really</b> do is convert an S-Expression of the first form to the second form. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I'm excited about this because I finally understood what the whole macro thing was about. I've always heard that it was about extending the language itself. But I never really got it. It seemed to me that anything I wanted to do, could either be implemented using good old fashioned meta programming, or was not possible even <b>with</b> macros. I could not see this middle ground of extending the language without writing a full fledged parser. But now I finally see it :)</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Lastly, it looks like <a href="http://www.neilmix.com/narrativejs/">Narrative.js</a> does something similar to what I was trying to do. It contains a full javascript parser, so its a bigger project. I need to look at it to see if it converts code into a similar form, and if so how it overcomes various problems that I have because of leaky abstractions. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com1tag:blogger.com,1999:blog-5522230262649447143.post-40624677213027815552010-10-20T00:36:00.000-07:002010-10-20T01:08:02.581-07:00Silly Mistake<div style="text-align: justify;">So recently I stumbled across this webcomic <a href="http://nonadventures.com/">Wonderella</a>, which is awesome! After I read a few pages, I decided to do what I do with all webcomics I like, ... download the whole thing. Because I can't stand that 30 second - 1 minute wait between pages. Previously, I used to do this sort of thing with wget, and try to discover the rule, and invariably there would be some complication or the other.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Then I wised up and started using <a href="http://mechanize.rubyforge.org/mechanize/">Mechanize</a>, which made things a breeze. And sometimes I've started multiple threads/processes and somehow allocated tasks to the threads so that the whole download happen faster. But this time I thought, "<i>I've been thinking and <a href="http://blog.vishnuiyengar.com/2010/09/lipstick-for-evented-programming-pig.html">writing</a> about evented I/O a bit now, someone on the <a href="http://nodejs.org/">Node.js</a> irc channel had mentioned he used node.js for http scraping, why not try the same.</i>" </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I decided to use it with <a href="http://rubyeventmachine.com/">EventMachine</a> because that way I could also test my new work in progress (then), <a href="http://github.com/pathsny/step_rewrite">pet project</a>. (which I'm going to write about soon). So I started reading about EventMachine and used <a href="http://hpricot.com/">hpricot</a> for the html parsing. In 30 minutes I had the script ready and I had tested bits of it. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I asked it to just get the first four comics from the <a href="http://nonadventures.com/archive/">archive</a> page, and it worked. So I did it <b>again</b>, this time asking it to get the <b>entire thing</b>. But, nothing happened!! Nothing was downloaded. Little print statements let me know that it had correctly parsed the archives page and was going after the right pages, but nothing! I let it run for a while, but still nothing :/. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">It took me a while to realize, I had been <b>solving the wrong problem</b>. I wanted to do things in parallel. But my bottleneck, wasn't how much memory I could afford on my machine. This is where evented I/O helps you. My bottleneck, was how many connections the webserver would allow me to make. I was attempting to download all the comics simultaneously, and that didn't work. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So like yeah, funny story :/. I just redid it with mechanize and it was delicious. Here is the code if anyone is curious what EM code looks like.</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/635993.js?file=wonderellla_with_eventmachine.rb"></script><div style="text-align: justify;"> </div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com1tag:blogger.com,1999:blog-5522230262649447143.post-25779594622629393112010-10-03T05:12:00.000-07:002010-10-03T07:15:50.491-07:00Changing the Rules<div style="text-align: justify;">Evented programming with <a href="http://en.wikipedia.org/wiki/Asynchronous_I/O">nonblocking I/O</a> is the new black. In evented I/O systems, every single I/O operation (or at least the expensive ones) all take callback functions, and execute asynchronously so that your code does not block on I/O. It either continues on, or it sleeps to allow a different request a chance. The main purpose of these systems is, without really getting into concurrency or threads, people can parallelize a system that spends a fair amount of time on I/O and handle several independent requests simultaneously.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Every time an I/O operation starts, the system registers your callback and continues on. Once the Input or Output operation is completed, the callback executes. So <b>every time</b> you intend to do any input or output operation, you put the code that's meant to execute <b>after it is done</b>, in the callback. But, this means, that in any interesting program, a large part of it is going to be spent in nested callbacks. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Let's look at the sample piece of code I've been playing around with. Except I'm going to use Ruby without Event Machine and mimic some code I've seen in node.js (node has non blocking operations for everything, so it should be easier to follow). For anyone who hasn't read this before, this code writes <i>hello</i> to file, appends to it with <i>world</i> and then reads the last line. Every thing I/O takes a callback. Writefile, read, write, close etc</div><div style="text-align: justify;"><script src="http://gist.github.com/600550.js?file=node%20code%20in%20ruby.rb"></script><br /></div><div style="text-align: justify;">Notice that the primary purpose of callbacks here, is not, as is customary, to jiggle the stuff in the middle of an algorithm. This is not the <a href="http://en.wikipedia.org/wiki/Strategy_pattern">strategy pattern</a>. It's far more low level than that. It's one of the <a href="http://cnx.org/content/m19628/latest/">three fundamental control structures in programming</a> (Sequence, Selection, Iteration). Callbacks here are to sequence your operations. By using a callback, you are sequencing operations so that whatever is inside the callback happens after the current operation. And it can make your code a bit hard to follow. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Programming languages, have had from day one, a way to sequence operations. You just put the operations down one after the other, and that's the sequence they occur in. We could imagine a magical programming language which has all the power of languages we currently use and love, with special support for evented IO. So I can mark those calls as special but still sequence operations normally and allow the compiler or interpreter to understand that some operations are to be executed only after this async one returns. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><a href="http://github.com/creationix/step">Step.js</a> was a library that tried to solve this problem, so I ported it to Ruby. It takes a series of lambda's as input, and executes them so that each subsequent one is executed when the previous callback returns. Basically, it sequences them correctly. This is what the same code looks like with step in Ruby (<i>cb</i> is chosen as a magic variable to indicate that &cb is where the callback to each function would normally be passed). </div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/600550.js?file=naive%20step%20usage.rb"></script><div style="text-align: justify;">Firstly, it has a bug. <i>close</i> doesn't really work because the file has gone out of scope. The file handle is not being passed on by write. Secondly, it's pretty ugly. Lambda, lambda, lambda ... If only I could take a bunch of code without them being wrapped in lambdas and sequence them correctly. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">While Ruby allows for a lot of meta programming and building DSLs, this problem seems unsurmountable, unless we change the syntax of the language itself. Unless we invent our own control structures that do what we ask them to and extend the language. What we need are <b>macros</b>.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">A <a href="http://en.wikipedia.org/wiki/Macro_(computer_science)">macro</a> is something that allows you to automagically expand something preselected into a sequence of operations. Excel and Word had macros. Games have macros. It usually expands out into a larger body of code and prevent you from having to type it out. Like you could imagine a macro that contains two or three operations that always occur together. You might want to allow for variable substitution in your macro so that it's actually useful.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The macro is read by some macro interpreter or compiler, it modifies the code, and then the regular interpreter or compiler reads your code. But, how powerful should your macro system be. At first, you might decide to keep complexity low, only allow templating. So that for example you could have a macro that given the name of a loop variable, generates code to run throught its items and do some operation (in case your programming language of choice doesnt already support this). Later you might want rudimentary branching so that you can, for example, change the code that is executed in development mode to make for easy debugging. Or looping support to generate repetitive code. Before you know it, you have a whole other programming language. In which case why not allow your programming language of choice itself to be your macro language? So if you use C, use the full power of C in your macros. If you use Ruby, use the full power of Ruby in your macros.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Lisp does that. Lisp gives you access to your parsed code in the form of <a href="http://en.wikipedia.org/wiki/S-expression">S-expressions</a> and allows you to modify or generate S-expressions before it executes this code. It's built into the language. And it works really well because the language itself has support for it. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Now Ruby and Javascript have always had eval. You could load your source and modify it. But the effort of parsing such code is large, and you don't want to work at the level of strings. Which is why I got really excited when I saw this <a href="http://www.infoq.com/presentations/braithwaite-rewrite-ruby">awesome video</a> by Reginald Braithwaite. Where he built some macros in Ruby. Using the <a href="http://github.com/seattlerb/parsetree">ParseTree</a> project to parse ruby and get S-expressions (which can then be modified) and <a href="http://seattlerb.rubyforge.org/ruby2ruby/">Ruby2Ruby</a> which takes S expressions and generates Ruby code. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So my next step is to rewrite Step using macros so that you can sequence code the usual way, but allow it to work on an evented IO system.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Lastly, let me leave you with a joke. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">A drunk loses the keys to his house and is looking for them under a lamppost. A policeman comes over and asks what he’s doing.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">“I’m looking for my keys” he says. “I lost them over there”.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The policeman looks puzzled. “Then why are you looking for them all the way over here?”</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">“Because the light is so much better”. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com6tag:blogger.com,1999:blog-5522230262649447143.post-16559944923188397042010-09-30T10:48:00.000-07:002010-09-30T21:11:53.581-07:00Node.js means having to put your toys back in the closet after you're done :(<div style="text-align: justify;">When I was first exposed to Ruby and how easy it was for functions to accept blocks and how ubiquitous such functions were, I was delighted that for example </div><div style="text-align: justify;"><i>File.open {|file| foo(file); bar; baz; qux;}</i></div><div style="text-align: justify;">would let me do a bunch of operations on a file and not have to worry about closing the file. This was similar to how cool it was to move from C++ to C# the first time and stop worrying about memory. This was how things should be. </div><div style="text-align: justify;">And then recently <a href="http://stackoverflow.com/questions/3538156/file-i-o-in-every-programming-language">this</a> post on <a href="http://stackoverflow.com/">Stack Overflow</a> led me to this code sample in <a href="http://nodejs.org/">Node.js</a>. The code is opening a file and appending the word <i>world</i>. </div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/568279.js?file=node_inner.js"></script><div style="text-align: justify;">I have to remember to close the file!! In a language that allows functions to be passed as parameters, I have to remember to close the file. How much does that suck? My colleague, <a href="http://piecesofrakesh.blogspot.com/">Rakesh Pai</a>, a node.js fan, suggested that maybe this is because this is a low level api, and high level apis will take care of this problem. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">But on thinking about it, this may not happen. I mean I could imagine a <i>fs.append </i>function that takes a file and some text, appends it and then calls the callback, but not something that gives you access to a file object to play with. </div><div style="text-align: justify;">Or maybe fs.open could take 2 functions. One meant to be executed after opening the file, and a second to be executed after closing the file. But this will probably cause a lot of scoping grief. So maybe the first function will have to return an array of variables that then become available to the second one?</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So it's possible this never happens. If this is the case, is it possible that the file will not be closed for a long time? I mean if your code is something like </div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/568279.js?file=node_download_the_internet.js"></script><div style="text-align: justify;">Then, wouldn't your workers hang on to the file handle for an awfully long time? Even though it isn't being used? Since the file is trapped in that closure there, there's no way out unless my runtime has analyzed my code and seen that I will never use file from this point on. <b>Not even via an eval</b>. I can't see the GC or whatever figuring this out. How about if say as a good programmer, I do this.</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/568279.js?file=node_download_the_internet_2.js"></script><div style="text-align: justify;">Now can it figure it out, since I haven't passed file to my <i>doJob</i> function. Does that mean that in this scenario I'm safe? I assume it will since file isn't trapped in a closure here. But I don't know how the v8 GC works. But in the previous scenario, it feels to me like it will not be able to detect my intention, so we'll have to be a bit more careful programming with node.js</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Edit: From <a href="http://tuxychandru.blogspot.com/">tuxychandru's</a> comment, I realised that I may not have been very clear. I wasn't just whining about some api requiring people to do work. I understand that there will always be low level api's that require more care. I was saying that in some ways node is being positioned as an answer to the programming ills for certain kinds of problems. I was saying that it looks like the paradigm has resulted in a new <i>solved</i> problem returning. That as part of everyday programming, cleaning up is required. </div><div style="text-align: justify;"> </div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com5tag:blogger.com,1999:blog-5522230262649447143.post-62463335660222628222010-09-28T00:22:00.000-07:002010-09-28T01:39:16.041-07:00Naive Implementation of Step.js in Ruby<div style="text-align: justify;">I wrote about <a href="http://github.com/creationix/step">step.js</a> <a href="http://blog.vishnuiyengar.com/2010/09/lipstick-for-evented-programming-pig.html">here</a> and <a href="http://blog.vishnuiyengar.com/2010/09/all-together-now.html">here</a>, since I thought it was really cool. I've built a naive implementation in Ruby. To demonstrate the usage, imagine the same set of functions that node provides existed in Ruby. So this is how code would be written both in the serial and parallel cases.</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/600550.js?file=naive%20step%20usage%20in%20ruby.rb"></script><div style="text-align: justify;">Ruby uses <i>self</i> unlike the <i>this</i> in javascript. But <i>self</i> is lexically scoped, whereas <i>this</i> is dynamically scoped. So here I have chosen to have the caller decide the name of the magic variable (<i>cb</i> in the example above) and use instance_exec to make it happen. There's no real advantage to this approach though, since existing references to self will still break. </div><div style="text-align: justify;">I call it a naive implementation because I've made assumptions that are true in the node environment, but not necessarily in a random piece of ruby code. Hence, there are some issues. But first, here is the code itself.</div><script src="http://gist.github.com/600550.js?file=naive%20step%20definition%20ruby.rb"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So what are the problems?</div><div style="text-align: justify;"><ul><li>The serial implementation has a bug when you want have to a callback function receiving a parameter that is needed by it and the functions further down. Since scopes are nested by default in Javascript or Ruby, the intermediate functions dont pass them through. If you see the first example I wrote, or in the ruby example today, it actually has this bug. <i>File.open</i> provides a <i>file</i> handle meant to be used by <i>writeFile</i> and <i>close</i>. I didn't realize this was a problem until my ruby code broke. The javascript implementation has the <b>same</b> bug, and I don't think it can be fixed.</li><li>The parallel implementation works by incrementing a counter every time someone requests the parallel callback and executes the next function only when the counter is zero. This might work in a node style environment where any callback can execute ONLY after the current code completes executing. So the counter starts decrementing only after it has been incremented completely. Which means that if the IO functions I use came from <a href="http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBIQFjAA&url=http%3A%2F%2Frubyeventmachine.com%2F&ei=iaGhTIyGMI62vQOn7fzzAw&usg=AFQjCNEHkCbj5M77UPlZDPlDirpHOxV9Hw">Event Machine</a> may work. But sync calls masquerading as async will break since they will execute the callback right away. So the counter starts decrementing immediately and the next callback will execute several times. This is the same implementation in the original javascript, but it is not a bug there since the node environment has no sync I/O. One of the reasons node gets more love than Event Machine.</li><li>At the end of it, this is as ugly as the javascript implementation. You have to wrap everything in a lambda call. It will be interesting if we could do better than that. </li></ul><div>On a side note, I looked at the implementation of step after I implemented mine in ruby. Tho original implementation chose a more procedural style for the main piece, whereas I chose a more functional style. But it feels as if the procedural is easier to understand. The eyes of everybody I show my code to seem to glaze over the bit where I do a fold over the list of lambdas I get as the second parameter to step. What do you think? </div><div>Of course all this goes out the window when I get to the parallel method where I have to maintain state externally. I have no idea how to do that in a more functional style. Any inputs would be cool :). </div></div><div style="text-align: justify;"><br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com1tag:blogger.com,1999:blog-5522230262649447143.post-8272524388061802792010-09-15T09:04:00.000-07:002010-09-15T09:07:58.285-07:00Beware ActiveSupports Default Autoload MechanismBy default active_support sets its dependency loading mechanism to load rather than require. We're working on a non rails app with datamapper and some models add before :create hooks. If you dont take care, these models are loaded twice and the hooks are added twice which can result in strange behaviour.<div><br /></div><div>So remember to do this <i>ActiveSupport::Dependencies.mechanism = :require</i></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com1tag:blogger.com,1999:blog-5522230262649447143.post-29538688187757240492010-09-12T14:11:00.000-07:002010-09-13T03:57:05.953-07:00All Together Now<div style="text-align: justify;"><a href="http://blog.vishnuiyengar.com/2010/09/lipstick-for-evented-programming-pig.html">Last time</a>, I talked about the Step.js library and how it helped make code look better when using the evented programming paradigmn. However, the first time I complained about the ugliness of code, the <a href="http://blog.vishnuiyengar.com/2010/07/my-biggest-peeve-with-event-driven.html">problem I highlighted</a> was different. The problem was having multiple actions occur simultaneously and to continue once they are all done.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Let's take the example of loading a bunch of files, reading the contents and printing out the largest one. (it's a stupid example, I know, but the core of it is loading up a bunch of files before continuing. What's done with them is irrelevant. When I needed to do this I was caching a bunch of templates for a templating library.). Either because we are obsessive micro-optimizers or because the call is very slow (maybe the drive is on the network somewhere), we decide we want to load the files in parallel. </div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/576870.js?file=para_1.js"></script><div style="text-align: justify;">So why am I complaining? Firstly it's a lot of code. The problem is simple enough that I shouldn't have to write so much code. Secondly I had to maintain state in a scope outside the load function. I could trap it in a closure, but it's still annoying. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><a href="http://piecesofrakesh.blogspot.com/">Rakesh Pai</a>, a big fan of and contributor to tho Dojo project pointed out that Dojo's style of doing evented programming is in a way better suited to both this problem and the previous one than the default. Anything asynchronous in dojo always returns a Deferred object, which has a method called "<i>andThen"</i> . So you can do things like <i>fs.writeFile(path, data).andThen(function(){fs.readFilepath)})</i> ... and so on. More importantly, a bunch of deferreds can be placed in a <a href="http://docs.dojocampus.org/dojo/DeferredList">Deferred List</a> and treated as one. Which means you can attach an event to be fired when all of them complete.<br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I think this too is a bit too wordy for me, but maybe it works in the entire dojo ecosystem as it is consistent with everything else. After all, Consistency is valuable for more than just <a href="http://en.wikipedia.org/wiki/Consistency_(database_systems)">databases</a> and <a href="http://en.wikipedia.org/wiki/Consistent_hashing">hashing schemes</a>. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">But let's see how step.js can help solve this problem. </div><div style="text-align: justify;"><script src="http://gist.github.com/576870.js?file=para_2.js"></script><br /></div><div style="text-align: justify;">Now that is so much nicer. No state maintenance, just pass in a function that executes multiple functions that take this.parallel as a callback and at the end we get all the results lumped together. The example is only marred by the stupid semantics of "<i>this"</i> in javascript (I call another function on array, so I'm forced to alias this. But without that magic, the library wouldn't work at all, so it's the price we pay.) and because for some retarded reason the arguments array is not a real array in javascript so I have to slice it in.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So there you have it, Step.js to write nicer code.</div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-71058104906689443762010-09-07T11:18:00.000-07:002010-09-12T22:54:12.156-07:00Lipstick For the Evented Programming Pig<div style="text-align: justify;"><a href="http://blog.vishnuiyengar.com/2010/07/my-biggest-peeve-with-event-driven.html">Previously</a>, I have complained about how ugly code ends up looking with the evented programming paradigm. A pattern that might became vitally important for performance reasons, but nevertheless makes for super ugly code. I came across another similar issue recently, courtesy of a certain Stack Overflow <a href="http://stackoverflow.com/questions/3538156/file-i-o-in-every-programming-language/">post</a> meant to demonstrate File I/O in every programming language. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The problem is to write "Hello" to a file, append "World" to the file and then to print onto the screen the last line of the file. (which ends up being "World" ... SHOCKU). I've stolen the solution from <i>node.js</i>, everyone's new favorite technology that will save the world. </div><script src="http://gist.github.com/568279.js?file=node_hello_1.js"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Ugly, ugly, ugly code. Kill it with fire!! Now to be fair, this is partly because the node apis are quite low level. We might be able to look forward to an <i>fs.append</i> method someday for example. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">I've heard people argue that it's just a matter of getting used to it ... I acknowledge that this is true. But it is true of all sorts of ugly code that adds a little more mental effort every time you parse it. I mean code I used to write back in college had high Cyclomatic complexity and could be difficult to follow deep inside a nested method. But back then I was a whiz at following it. I just didn't see a problem. But the truth is it took me a little effort whenever I read or modified it. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">This is important because we all know that "code is read more often than it is written" right? So while you may get used to reading large, complex blocks of nested code, it takes its toll on you. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">So the obvious <b>next</b> step is to start naming pieces of your code and pulling it out. Something like this.</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/568279.js?file=node_hello_2.js"></script><div style="text-align: justify;">Better, but still a bit ugly. But more importantly it forces you to write your code literally <b>backwards</b>. I'm sure you could find ways to prevent that backward effect locally, but it will remain an effort. The Stack Overflow post has something similar but that at least nicely breaks it up into composable pieces. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The other day I was discussing the same issue with <a href="http://piecesofrakesh.blogspot.com/">Rakesh Pai</a>, and <a href="http://finalprefix.com/">Joel</a>. What such code would look like ideally. We played "what if?". What if we could modify javascript however we saw fit and wrote sequential code that was converted by a machine to trivially nested code. Afterall programming languages are for people not machines. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Suppose say I could pass '...' to a function and that meant "take the next function and pass it as a callback to this one". And say '...' on a seperate line means that the remaining code below that line is a callback. So we get this.</div><div style="text-align: justify;"><br /></div><script src="http://gist.github.com/568279.js?file=node_hello_3.js"></script><div style="text-align: justify;">Now this, is <b>much</b> better. It might be highly impractical, but something on those lines might work if we could change javascript as we saw fit. (say we had macros for example). I have grouped the lines of code into sections that might ideally become methods. (well basically we could create our append method there). </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">However, while we cannot change javascript, at least javascript has first class functions. So a library called <i>step.js</i> makes something similar possible. Take a look at the same solution with step.js.</div><script src="http://gist.github.com/568279.js?file=node_hello_4.js"></script><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Its pretty close to what we had, though there is a great deal of cruft with all those function wrappers. I mean, it's pretty much the same problem that you have with ruby. The only way to pass code around to be executed later is as a lambda. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Still its way better than what we started with. This compares quite nicely with our previous code. Except everything needs a function wrapper and the magic variable used is by clever use of "this". But I think given the popularity of node.js, step.js might be very useful to organize and improve readability of code. And if some effort is put into also making it easy to debug, it might be used all over the place.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Edit: I forgot to link to the library last time. <a href="http://github.com/creationix/step">Get Step.js Here.</a></div><div style="text-align: justify;"><br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com3tag:blogger.com,1999:blog-5522230262649447143.post-67749274171872963182010-07-31T00:21:00.000-07:002010-09-07T11:05:15.448-07:00My Biggest peeve with event driven programming<div><br />is having to build constructs like this.<br /></div><br /><script src="http://gist.github.com/501891.js"> </script><br /><div><br />I need to load a bunch of templates up and then perform the rest of my actions. Event Driven programming frees you from excessively specifying order in code. Overdoing the Sequence bit in <a href="http://blog.objectmentor.com/articles/2010/07/05/software-calculus-the-missing-abstraction">Sequence, Selection and Iteration</a>. Except when you really need sequence, the code becomes messy. The sad part is this isn't even a great solution since it loads files one at a time. Ideally you wanna parallelize this.<br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com5tag:blogger.com,1999:blog-5522230262649447143.post-58001874828888060742010-04-05T23:13:00.000-07:002010-04-05T23:48:37.020-07:00Generalized Expression Simplification in SICP?<p align="justify">A couple of colleagues of mine from work and me have been working our way through <a href="http://mitpress.mit.edu/sicp/">SICP</a>. So far thing's have been pretty good but we recently came across a series of exercises on "interval arithmetic". The basic idea was to be able to construct a term as an interval of uncertainty (represented as a tuple (a,b)) meant for use in engineering calculations. Subsequently to define a series of arithmetic operations (+, -, * /) that operate on intervals and create new intervals with different uncertainties.</p><p align="justify">After a few such problems, it is brought to our attention that if an expression is written in two different forms, the value obtained can be different. For example (1/R1 + 1/R2) could also be written as ((R1 + R2)/R1R2) and these yield different values. The problem is clearly that all the operations we have defined increase the uncertainty and if an expression is written in a manner that results in more operations we should expect more uncertainty. In fact, as this gist demonstrates, (R2 - R1 + R1) can result in something more uncertain than R2 by itself. </p><div align="justify"><script src="http://gist.github.com/357296.js"></script></div><p align="justify">Exercise 2.16 asks us to attempt to write the package in a way so that rewriting an expression in a different form will still yield the same answer. The key to this seems to be a combination of </p><ul align="justify"><li>Some generalized method to simplify expressions.</li><li>A method of identifying if two intervals are the same.</li></ul><div align="justify"><br /></div><p align="justify">I initially interpreted the second point as being a way to check if two intervals are equal. But that's a mistake. Two intervals might be equal because they represent the same concept, or because they are two different terms with the same uncertainty and value. For example, if I was building a circuit with resistors, and I happen to use two resistors with the same rating (same value and error), they would still not be identical elements in the circuit. I wouldn't be able to "cancel them out". One of them might have an actual value that is on one side of the interval of uncertainty and the other might be on the opposite end. </p><p align="justify">The only way to identify if two intervals are the same would be if I redefine my constructor to create with each such tuple, an object id that is meant to be unique. Now if two intervals have the same object id, I'd know that they were in fact the same. An extremely simplistic method to generate such an object id might be to use a random number between one and one billion. </p><p align="justify">However, I have no idea how to even begin approaching the first problem. Such a thing would be trivial if the only allowed operations were addition and subtraction. (I could simply collect all the same terms and find their coefficients). Or only multiplication and division. But, with all four, I don't know where to start. So if anyone has some insights or resources, please do share them with me.</p>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com6tag:blogger.com,1999:blog-5522230262649447143.post-11300926491444104952010-03-21T21:33:00.000-07:002010-03-21T22:05:12.272-07:00ActiveSupport and json pure hate each other :(<div align="justify">See</div> <br /><script src="http://gist.github.com/339802.js"></script><br /><p>The sad thing is the DataMapper serializer DM_types seems to depend on json_pure and I've got active support all over the place.</p>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com3tag:blogger.com,1999:blog-5522230262649447143.post-61374838555501754392010-03-20T00:35:00.000-07:002010-03-22T03:07:32.465-07:00Fixing a datamapper bug<p align="justify"><a href="http://datamapper.org/">DataMapper</a>, a ruby ORM, has become fairly popular of late. I ran across an extremely annoying bug yesterday. This explains the bug and a fix.</p><p align="justify">DM allows you to make updates to the database in a manner that includes a where clause. This could mean efficiency wins or concurrency wins. So for example if I have a payment model and a payment moves from pending to say success or failure, I might have code that looks like this.</p><div align="justify"><br /><script src="http://gist.github.com/338536.js?file=dm+bug+simple+example.rb"></script><br /></div><p align="justify"><br />The problem with this is if I have multiple threads, processes w/e and I want to make sure the same payment is never updated twice. I shouldn't have one thread/process mark it a success and a different thread/process mark it a failure subsequently. The previous code is susceptible to race conditions. Ideally I'd like to write one line of SQL that says update the payment where status is pending. Then I'd write this.<br /></p><div align="justify"><br /><script src="http://gist.github.com/338538.js?file=dm+bug+better+collection+update%21+example.rb"></script><br /></div><p align="justify"><br />This actually does only fire a single query which is an update clause with an inner where clause. I've appended to the gist the relevant line from the log file. This is because I've used update! instead of update. </p><p align="justify">The bug occurs when the status field is one of the more complex datamapper types like say enum. I've created an example which reproduces the error.<br /></p><div align="justify"><script src="http://gist.github.com/338532.js"></script><br /></div><p align="justify"><br />The first part of the test using update succeeds, but the second one with update! fails. It turns out superman is still in limbo! The reason for this is the Collection class in the DM module has a bug. The update! method has the following piece of code. Below that compare with similar code from the private _update method of the Resource class<br /></p><script src="http://gist.github.com/338541.js"></script><p align="justify"><br /><p align="justify">The difference is that in one case the code says <em>property.valid?(value)</em> and in the other case, it (correctly) says <em>property.valid?(property.get!(model_instance))</em> . This difference is important for special types like Enums. When I say <em>update!(:status => :alive)</em>, a new model instance is created and the modified properties are asked to validate the values being inserted to verify that they are sane.</p><p align="justify">So a property of type <em>Enum[:dead, :alive, :limbo]</em> is asked to validate the value being inserted. The value being inserted is <em>:alive</em>, but the underlying primitive value stored is 1 (since <em>:alive</em> is the 2nd field in a 0 based array). So<em> property.valid?(1) </em>is being checked, which is obviously false. </p><p align="justify">In the second case, <em>property.get!(model_instance)</em> would actually return <em>:alive</em>. So <em>property.valid?(:alive)</em> is checked, which is true. </p><p align="justify">Now obviously there's a fair amount of indirection going on here for whatever reason. Anyway this is the quickfix I used to monkey patch my Collection class and move on.</p><script src="http://gist.github.com/338549.js"></script><p align="justify">Anyway it would be nice if the behavior of _update and update! could be moved to a single place so here is a proposed change.<br /></p><script src="http://gist.github.com/339102.js"></script>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-46577597979821794572010-02-14T21:34:00.000-08:002010-02-14T22:02:40.554-08:00Sudoku solver, alternate optimization strategy, final<div align="justify">I had <a href="http://blog.vishnuiyengar.com/2009/11/sudoku-solver-remembering-past.html">written about optimising the sudoku solver</a> by remembering moves made in the past. Another strategy that I had tried parallely was to do a short-circuit evaluation. Each iteration of the solver is about searching all the empty cells to find the list of acceptable moves and then choosing the cell with the least moves. However, clearly a cell with zero options means that it's time to backtrack. Clearly instead of continuing to search the list of cells, that's a place to jump out of a search. Similarly a cell with one option means that there is only one option so I might as well make that move.</div><div align="justify"><br /></div><div align="justify">I experimented with a short circuited search where I jumped out the minute I found something with some "n" moves and I varied "n" from upwards. It turned out the best option was to jump out when I had zero or one option. Sadly this optimisation only gives me a factor of 3 improvement, and doesn't stack much with the previous one. </div><div align="justify"><br /></div><div align="justify">Anyway the whole code is available at github -> <a href="http://github.com/pathsny/Sudoku-Solver">http://github.com/pathsny/Sudoku-Solver</a></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com1tag:blogger.com,1999:blog-5522230262649447143.post-4442884107244512582010-02-09T08:35:00.000-08:002010-02-08T12:47:55.145-08:00... Okay 3, 2, 1 Let's Jam. Quicksilver, Ruby and Mac OSX<a href="http://en.wikipedia.org/wiki/Quicksilver_%28software%29"> QuickSilver</a> is an application launcher for Mac OS that is very popular productivity enhancer. It's extensible through a ton of plugins. But it also allows people to launch custom scripts, which allow people to quickly script any action they commonly perform. I first saw the possibilities when I read <a href="http://www.macosxtips.co.uk/index_files/run-applescripts-with-keyboard-shortcuts.html">this article</a>. Some of those scripts were quite useless to me, but there are a few I end up using all the time. Like shortcuts to turn my wireless radio off when Im not online and wanna save power. So this is about 3 QuickSilver scripts I recently wrote<br /><br />Initially I wrote a few of them in applescript, but when I wanted to write the script to "automatically pastie my code", I decided it would be easier to use a language I'm more comfortable with. I found a ruby-applescript bridge, so I decided to go with ruby. The bridge is obtained by installing the rb-appscript gem. You can find on these scripts on Github at <a href="http://github.com/pathsny/QuickSilver">http://github.com/pathsny/QuickSilver</a><br /><br />I also attempted a "maximise" script based on <a href="http://http//www.macosxhints.com/article.php?story=20051227001809626">this article.</a> Sadly it just doesn't work :/. It's always incredibly slow the first time you launch it.Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-41361860135540855122010-01-10T04:23:00.000-08:002010-01-10T04:57:59.316-08:00Programming Async code in a Sync style using Laziness and Functional patterns<div style="text-align: justify;">The first time I came across some common idioms of functional programming happened when I was working with .NET and came across the List methods. The findAll and ForEach methods. For me it was a revelation. I kept rewriting all the code on the project I was on, using these idioms.<br /></div><br /><div style="text-align: justify;"> Since functional languages were popular at that point of time and I discovered that such languages were where this idea had sprung from,, I decided to start learning Haskell. I'm still learning it, but one interesting thing about Haskell was that it is the Laziest functional language. Everything was automatically lazy and strictness had to be enforced somewhere when you really needed. Like say in the IO monad where you say when you want to print something, you mean like right now! So if I had to print the first 5 even natural numbers greater than some x, I could write this. (Warning: horribly contrived example and code).</div><pre style="font-style: italic;"> f x = take 5 $ dropWhile (<x) $filter even [1..] </pre><div style="text-align: justify;"> Notice the infinite list of natural numbers there? The reason this works is because Haskell is lazy. What really happens here is that when I print the output of that, the print function asks take 5 to return output. take 5 asks dropWhile to return 5 items. dropWhile asks filter to return items until it finds an item that is greater than x and then asks for the next and then filter asks the infinite source for even items and keeps doing so until dropWhile is satisfied. The realization here is that on the left side we have a source, on the right side is a sink. Everything else is a component meant to build a pipeline. Something about the system knows that this system's flow is governed by the sink, and so the pipeline components all pull output until the sink is satisfied. The idea is that I can write more idiomatic code and use things like infinite lists when I want to. .NET had done the same thing with the IEnumerable stuff from 3.5. So I could now write</div><div><t></t><pre style="font-style: italic;">InfiniteList.FindAll(Even).SkipWhile(y => y > x).Take(5)</pre><div style="text-align: justify;"> I recently read about another realization. Another common pattern while programming is an event based system. Like a web application waiting for requests from someone. A Javascript function that makes an ajax call and displays the output on the screen and so on. Specifically, an async system where you wait for events to pour in and for each event you go on to perform some actions.<br /></div><div style="text-align: justify;"><br /> So imagine I had a system where I go on to call some number generator which dials up a service halfway across the world. the service spews out natural numbers. I want to register a callback function which waits for numbers, ignores the odd ones. Maintains a flag so it knows at least one such number has been greater than x and then gives me the next 5 numbers before swallowing them. (yeah I know, incredibly useful). Since this deals with state, let's do this in some imperative ruby style language. Typically I might have to say</div><pre style="font-style: italic;"><br />def handler(n)<br />return if n % 2 == 1<br />@skip = false if n > x && @skip<br />return if @skip<br />@num_returned = 0 unless @num_returned<br />return if @num_returned > 5<br />@num_returned += 1<br />puts n<br />end<br /><br />numbercaller(handler)<br /></pre><br /><div style="text-align: justify;"> The beautiful functional style code has morphed to something so ugly all because I switched from pull to push async. But it's not hard to recognize that this problem is very very similar to the one I was previously solving. All that changed was the source here controls when stuff goes through the pipeline instead of the sink. So with the right tools I should be able to use the same pipeline tools as before and have the language features just switch the flow control around. Numbercaller should present the same interface as an iterable system, allowing me to use the same pipeline components, but should push stuff through the pipeline instead. I should be able to use not just each, but also map, dropWhile, take and so on. It's just a different take on Laziness Or as the article I'm going to link you to put it, the Observable pattern and the Iterable pattern are virtually the same thing. You can read all about it <a href="http://themechanicalbride.blogspot.com/2009/07/introducing-rx-linq-to-events.html">here</a>. The Rx (Linq to Events).<br /></div><br /><div style="text-align: justify;"> Truth be told, I'm a little nervous about this pattern. It's a new abstraction and like all abstractions it has the potential to be leaky. Imagine we managed to implement this on some Javascript ajaxy interface. On the click of some item I want to make an ajax call. I want the result of the Ajax call to update some div.<br /><br /><pre style="font-style: italic;">button.onClick = function(){<br />AjaxUpdater.update(url,function(response){<br /> html = process(response)<br />$("blah").innerHtml = html<br />})}<br />doSomethingElse();<br /></pre><br />Now with the new realization we have we'd like to write.<br /></div><br /><pre style="font-style: italic;">responses = button.clickEvents.each(AjaxUpdater(url).map(process)).flatten<br />responses.each(function(html){$("blah").innerHtml = html})<br />doSomethingElse()<br /></pre><div style="text-align: justify;"> Now, the important point here is that the first two lines need to happen at some random time in the future, and in fact repeatedly each time I get a response. But doSomethingElse needs to happen right away without waiting for click events to occur. Since the abstraction hides the fact that this event appears at some time in the future and potentially infinite times, it might mean that I accidentally make some event occur with every click? It might mean buggier code, or some unfortunate performance implications. It might simply mean we need much smarter interpreters. The reactor pattern (non-blocking io). has become very popular of late. It involves converting a lot of operations that are traditionally treated as synchronous, such as writing to disk, or making a blocking call for data without which you cannot proceed, to asynchronous. It has some very interesting implications and provides considerable performance advantages. This pattern might make writing code with the reactor pattern as idiomatic as code which treats these operations as synchronous.<br /></div><pre style="font-style: italic;"><br /></pre></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com3tag:blogger.com,1999:blog-5522230262649447143.post-69951785176188261782009-11-16T05:03:00.000-08:002009-11-16T05:23:53.912-08:00Sudoku Solver - Remembering The Past<div style="text-align: justify;"> The <a href="http://pathsny.blogspot.com/search/label/Sudoku">sudoku solver</a> is fairly fast and seems to be doing all the right things. By choosing the cells with the least options the number of useless moves has been reduced considerably. However, there is a fair amount of rework thats currently going on. Every time the state of the game is analyzed, the entire board is scanned to find all possible numbers that can be stored in each empty cell. Once a single cell is filled a new iteration begins. Again, this analysis is repeated by scanning the whole board. But, human's don't do that!<br /><br /> Once I've decided what numbers are playable in each empty cell. I don't repeat this exercise everytime I fill up an empty cell. Most empty cells are not affected by any single cell being filled. If I fill a cell that used to be empty, the only empty cells that are affected are cells that shared a row, column or block with the filled cell. So between iterations, if the analysis of the game was to be saved, I could quickly obtain an analysis for the next iteration by slightly modifying the analysis of the previous iteration. OfCourse this is going to take considerably more code to do, but it should show significant improvements.<br /><br /> Now unfortunately I haven't saved the results of running all this on the machine I used when I first started blogging all this. So the times I paste will not be comparable but will have to be scaled a bit. So Ill repost the highlights of previous runs.<br /><br /><span style="font-style: italic;"> Analyzer::Simple ran 5 puzzles in 3.115519 seconds with 107442 moves and 107168 rollbacks </span><br /><span style="font-style: italic;"> Analyzer::LeastChoicesFirst ran 5 puzzles in 0.412483 seconds with 631 moves and 357 rollbacks</span><br /><br /> So last time we saw an improvement of a factor of ten. And now, here is the result of the latest change.<br /><br /><span style="font-style: italic;">Solved simple with 45 moves and 0 rollbacks in 0.035017 seconds</span><br /><span style="font-style: italic;">Solved hard with 83 moves and 29 rollbacks in 0.010338 seconds</span><br /><span style="font-style: italic;">Solved evil with 217 moves and 161 rollbacks in 0.024111 seconds</span><br /><span style="font-style: italic;">Solved escargot with 217 moves and 159 rollbacks in 0.023176 seconds</span><br /><span style="font-style: italic;">Solved other_hard with 69 moves and 8 rollbacks in 0.009236 seconds</span><br /><br /><span style="font-style: italic;">Analyzer::StorageBasedLeast ran 5 puzzles in 0.102331 seconds with 631 moves and 357 rollbacks </span><br /><br /> That's a speed up of about 4 times. This is pretty good. As always the code follows. Notice that this time my analyzer actually has to expose read attributes so that the state can be preserved from one iteration to the next. This series of posts is nearly done. I have one more post which will follow where I'll also link to the entire code on github.<br /></div><br /><br /><pre style="font-size: x-small;"><br />class StorageBasedLeast < Base<br /> attr_reader :cells_with_values, :cell, :value<br /><br /> def initialize(game, analyzer=nil)<br /> @cells_with_values = find_cells_with_values(game, analyzer)<br /> @cell, @possible_values = cells_with_values.min{|pair_1, pair_2| pair_1[1].length <=> pair_2[1].length}<br /> end<br /><br /><br /> def each<br /> @possible_values.each do |value|<br /> @value = value<br /> yield @cell, value<br /> end<br /> end<br /><br /> def find_cells_with_values(game, analyzer)<br /> return game.empty_cells.collect{|cell| [cell, possible_values(game, cell)]} unless analyzer<br /> cells_with_values = analyzer.cells_with_values.reject{|pair| pair[0] == analyzer.cell}<br /> neighbours = game.neighbour_indices(analyzer.cell)<br /> cells_with_values.collect do |pair|<br /> values = neighbours.include?(pair[0]) ? pair[1] - [analyzer.value] : pair[1]<br /> [pair[0],values]<br /> end<br /> end<br />end<br /></pre>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-62898699544326554692009-11-13T04:50:00.000-08:002009-11-16T03:14:35.257-08:00Highlights that impressed me from the video on the Go languageGo is a new programming language developed by google and a lot of big names and you can find out all about it on it's wikipedia page <a href="http://en.wikipedia.org/wiki/Go_%28programming_language%29">here</a> or on it's website <a href="http://golang.org/">here</a>, or you could watch the hour long video <a href="http://www.youtube.com/watch?v=rKnDgT73v8s">here</a> on youtube.<br /><br />Anyway here are the highlights I got out of that video. I'll still need to read what's on the website to understand the language better, but it does raise my interest now. They wanted quick build times, better support for concurrency and a mixture of the advantages of static and dynamically typed languages. So here they are in no particular order.<br /><ul style="text-align: justify;"><li>Very fast compilation. Im guessing on large codebases this can make a big enough difference. It's interesting anyway.</li><li>Adding methods to anything. To investigate<ol><li> Does this mean I can add methods to any existing type?</li><li>Does this mean I can add methods to an instance of a type?</li><ol><br /></ol></ol></li><li>Automatically implemented interfaces. This is kinda cool actually. An interface is declared as a bunch of behavior and anything which exhibits this behavior now implements that interface. Which kinda gives you a duck typing like thing. implements as a keyword does not even exist.</li><li>Unicode characters can be used in variables. π = 3.14159 is valid code.</li><li>Making code async is trivial. Declare a function and just type go <function name>. The function executes in an async manner. Apparently whatever threading like thing they've used is very efficient because they demonstrated launching about 100,000 of these goroutines and they all executed in a matter of seconds.</li><li>Erlang style, you create channels for communications. Channels can carry anything including other channels. You drop stuff into channels and pull them out of channels. This makes writing multi-threaded or client server apps look very simple. To investigate<ol><li>How easy is it to distribute this over a network? Can I just toss a bunch of goroutines onto other machines?</li></ol></li><li>Closures, which should make a lot of people very happy.</li><li>Reflection. To investigate</li><li>Dynamic types. To investigate<ol><li>What is this? Is it like .NET? </li><li>Can I call any method on it? </li><li>Does it automatically implement all interfaces?</li></ol></li><li>10-20% slower than compiled C code. That's quite impressive.</li><li>ARM compiler. <ol><li>huh? Does this mean people can use go to write code for phones and mp3 players?</li></ol></li><li>Automatic memory management. There's talk about a concurrent gc.<br /></li><li>Some important libraries apparently already exist like for html templating and testing.</li><li>There was something about slices and arrays and maps. Need to investigate further to see if they have anything cool. Like the select, map, reduce type operations on slices or arrays?<br /></li></ul>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com5tag:blogger.com,1999:blog-5522230262649447143.post-9831100046592737122009-09-19T08:54:00.000-07:002009-09-20T20:46:34.680-07:00Ruby 1.9 is way faster than Ruby 1.8.6<div align="justify"> I got a chance to test it. Its actually true. I'm on OSX so I used mac ports to install ruby1.9 parallel to 1.8.6. Since I use TextMate for development, heading to preferences -> Advances -> Shell variables and setting TM_RUBY to the actual location of the Ruby 1.9 binary. My Sudoku solver previously had the following results.<br /></div><br /><br /><pre style="font-size: x-small;"><br />Analyzer::Simple ran 5 puzzles in 5.524553 seconds with 107442 moves and 107168 rollbacks<br />Analyzer::ConstraintsChecking ran 5 puzzles in 37.719066 seconds with 36202 moves and 35928 rollbacks<br />Analyzer::LeastChoicesFirst ran 5 puzzles in 0.745781 seconds with 631 moves and 357 rollbacks<br /></pre><br /><br /><div style="text-align: justify;"> Here are the same results of the same runs with Ruby 1.9.</div> <br /><pre style="font-size: x-small;"><br />Analyzer::Simple ran 5 puzzles in 3.905158 seconds with 107442 moves and 107168 rollbacks<br />Analyzer::ConstraintsChecking ran 5 puzzles in 25.035866 seconds with 36202 moves and 35928 rollbacks<br />Analyzer::LeastChoicesFirst ran 5 puzzles in 0.527032 seconds with 631 moves and 357 rollbacks<br /></pre><br /><br /><div style="text-align: justify;"> Now ideally it should be twice as fast but my machine is loaded up with a lot of open tabs :/. But still yeah Ruby 1.9 better!</div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-87222394340687342992009-09-12T21:56:00.000-07:002009-09-13T11:19:19.069-07:00DEADBEEF for the CAFEBABE : (otherwise known as) The Great Choose Your Own Crc32 Adventure<div align="justify"> Ever since people have been transmitting information, there have been mechanisms to ensure that the transmission was successful and the received information was what was transmitted. On the internet at various layers you have some amount of redundancy and error checking. One such popular approach of verifying transmissions or data is the <a href="http://en.wikipedia.org/wiki/Checksum">checksum</a>. One really popular checksum is the <a href="http://en.wikipedia.org/wiki/Cyclic_redundancy_check">Cyclic Redundancy Check (CRC)</a>. Various CRC's are used in a variety of places like reading from cds, verifying that a zip or a rar archive has been opened correctly or transmitting files.</div><div align="justify"><br /></div><div align="justify"> For a long time, I've been involved in fansubbing anime and distributing it online. Before bittorrent, which now allows people to almost broadcast files and involve many people in the effort, it was necessary for people to distribute files one at a time. People used to distribute files on irc, host it on websites and ftps. Very often you'd have received a file as the tenth or even the hundredth person in the chain. There was always a small chance of corruption and over time you were quite likely to receive a file that was corrupt. In order for people to ensure that the file they received was accurate, the practice was for the group to publish the CRC32 of the files they released. A crc32 was really convenient. It was an 8 character hexadecimal string, which means it's easy for humans to read. But if your file was corrupted, there was only a 1 in 2^32 chance that you wouldn't know about it. Fairly good odds.</div><div align="justify"><br /></div><div align="justify"> Ofcourse, the crc32 is not a cryptographic hash. It's possible to reverse it or to create junk which has the same crc32. The idea was not to prevent sabotage, but accidental errors. Since crc32 was reversible, anarchriz wrote an <a href="http://www.woodmann.com/fravia/crctut1.htm">article</a> about how to reverse a crc32. In around 2002 or 2003 there was a brief fad in the fansubbing community. Someone had written a small program to modify files to make sure it had any chosen crc. So groups would modify and release files with crcs they thought would look cool. </div><div align="justify"><br /></div><div align="justify"> Last year (2008), the group I'm a part of, <a href="http://www.live-evil.org/">Live-Evil</a>, thought we'd release an old show called <a href="http://anidb.net/perl-bin/animedb.pl?show=anime&aid=153">Kimagure Orange Road</a>. <a href="http://www.animenewsnetwork.com/encyclopedia/people.php?id=74743">Ken Hoinsky</a> our fearless leader though it would be fun to sort of do a retro thing. One of the ideas we had was a custom crc for each episode. The first episode would be abcb0001, the next abcb0002 and so on. (The ABCB coffee shop is a big part of KOR). He managed to dig up anarchriz's document so we started poring over it. It looked doable, but we didn't want to do the work of actually writing this code and testing it. Surely it had already been done. We couldn't find the code that had been used previously. But we did find this article by <a href="http://blog.w-nz.com/archives/2005/07/15/reversing-crc/">Bas Westerbaan</a> where he had implemented this algorithm in python. Perfect! So we downloaded it and ... it didn't work.</div><div align="justify"><br /></div><div align="justify"> That was odd. We'd patch files according to the documentation, but when we checked the crc of the file it was not what we'd tried to patch it to. So I started looking at this code to see if it was easier to make it work rather than write my own. Turned out there was a small mistake. We fixed it and the code worked fine. So after communicating this back to Bas, we were merrily on our way. Each episode of KOR has since had crcs of the form abcbxxxx.</div><div align="justify"><br /></div><div align="justify"> I've put together a tool in python to take a file and patch it to whatever crc you choose. I first tried to write a pure python crc calculator, but it was uber slow on large files. Looking around I found that most people delegate the crc calculation bit to C. So I downloaded this open source python project called <a href="http://cfv.sourceforge.net/">cfv</a> and lobotomized it heavily to the point where all it does is calculate crc and nothing else. I wrote a small python script to call both the cfv script and bas's crc reversal script and patch any given file to any crc you choose. Now, how does the patching work? It calculates what sequence of 8 bytes should be appended to the given file so that the crc is whatever crc you have chosen. Most media files like movies, music even pdfs ignore any garbage at the end. So all it does is append a few junk bytes to the end. </div><div align="justify"><br /></div><div align="justify"> To use it you just pick a fun sounding crc. (Canonical examples are DEADBEEF and CAFEBABE). Run it like so. <em>python crcFilePatcher.py --file=MovieName --newcrc=deadbeef. </em>I've pushed all the files onto github <a href="http://github.com/pathsny/Crc-Patcher/tree">here</a>. Have fun :)</div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com4tag:blogger.com,1999:blog-5522230262649447143.post-47402740676294006652009-09-07T02:47:00.000-07:002009-09-09T00:54:17.419-07:00Buggy Symbol to Proc Implementation<div align="justify"> </div><div align="justify"> Ruby 1.9 seems to have introduced symbol to proc into the core language itself. I'm not sure whether this is implemented natively or as Ruby code, so if anyone knows that, please do let me know. For people who don't know what symbol to proc is (which is, I suspect, a very small part of the ruby community), click <a href="javascript:toggle('buggysym')">here</a></div><div id="buggysym" style="display:none;font-style:oblique;font-family:arial;font-size:small;"><br /><div align="justify"> Symbol to proc, was a really interesting feature that was built into the Symbol class in ruby that really helped right very idiomatic code. You're probably aware that Ruby allows you to pass blocks of code around and a lot of core objects in ruby accept blocks as part of their methods. So for example if you had a list of integers and you wanted to make them all positive you'd write <span style="font-style:italic;">[1,-3,5].map{|i| i.abs}</span></div><div align="justify"> </div><div align="justify"> The map method on arrays takes a block. It passes each element in the block and expects you to return to it something else. So it creates a new array where for each element you get a corresponding new element. The way you choose to do so is what your block decides. Clearly there are a lot of very complex things you can do, but very often what you want to do is as simple as in this example. You just want to call some function on each object in the array. the to_proc method in Symbol allowed you to write code like this instead <em>[1,-3,5].map(&:abs)</em>. So map expected a block. The & in the argument being passed indicated a block followed the &. But instead what followed was :abs, which is a symbol. But the default to_proc method added to symbol is enough to do the right thing.</div><br /><div align="justify"> Naturally, when I first heard of this like a lot of people I was really curious about how it worked. And there are tons of people who have written about it. Most of us have tried it and seen how it works.<br /></div></div><br /><div align="justify"> Recently I was doing something on irb 1.8 and I missed having symbol to proc around. Rather than <em>require</em> ActiveSupport, the gem which includes this enhancement to symbol, I just googled for the code and found <a href="http://blog.hasmanythrough.com/2006/3/7/symbol-to-proc-shorthand">this</a>, which was the first hit in google when I searched for "symbol to proc". I pasted the code into irb and continued ... and then I suddenly faced a strange error.</div><br /><pre style="font-size: x-small">class Symbol<br />def to_proc<br />Proc.new { |obj, *args| obj.send(self, *args) }<br />end<br />end<br />>> [[1],[-3,4]].map(&:size)<br />ArgumentError: wrong number of arguments (1 for 0)<br />from (irb):58:in `size'<br />from (irb):58:in `send'<br />from (irb):58:in `to_proc'<br />from (irb):71:in `map'<br />from (irb):71<br /></pre> I was quite mystified by this error. Now this does not happen when you use the symbol to proc implementation currently in Rails (listed below), or the Ruby 1.9 implementation.<br /><br /><pre style="font-size: x-small">class Symbol<br />def to_proc<br />Proc.new { |*args| args.shift.__send__(self, *args) }<br />end<br />end<br /></pre> Modifying the buggy symbol to proc implementation a bit, we get more insight into the problem.<br /><br /><pre style="font-size: x-small">class Symbol<br />def to_proc<br />Proc.new { |obj, *args| puts "obj is #{obj}"; puts "args has #{args.size} elements"; obj.send(self, *args) }<br />end<br />end<br />>> [1,-3,4].map(&:abs)<br />obj is 1<br />args has 0 elements<br />obj is -3<br />args has 0 elements<br />obj is 4<br />args has 0 elements<br />=> [1, 3, 4]<br />>> [[1],[-3,4]].map(&:size)<br />obj is 1<br />args has 0 elements<br />obj is -3<br />args has 1 elements<br />ArgumentError: wrong number of arguments (1 for 0)<br />from (irb):58:in `size'<br />from (irb):58:in `send'<br />from (irb):58:in `to_proc'<br />from (irb):71:in `map'<br />from (irb):71<br /></pre> Notice how in the second case, obj seems to be not the array, but the head of the array. And the remaining elements have become arguments. I'm not sure if the symbol to proc implementation on that page was always wrong, or if ActiveSupport once had a buggy implementation that was subsequently fixed. One thing I've been unable to do is to write some sample code to recreate the problem without using symbol to proc at all. Just writing a couple of functions with varargs and invoking them with array arguments. If anyone is able to construct such an example, that would be great. <a href="http://m.onkey.org/2007/6/30/let-s-start-with-wtf">Here</a> is an additional issue with symbol to proc (performance related). And <a href="http://lukeredpath.co.uk/blog/optimising-symbol-to_proc.html">here</a> is a workaround.Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com4tag:blogger.com,1999:blog-5522230262649447143.post-46628344465008527392009-09-04T14:10:00.000-07:002009-09-04T15:13:14.566-07:00The Primitive Obsession in Ruby aka Don't make EVERYTHING an Object<p align="justify"> When I was playing around with the <a href="http://pathsny.blogspot.com/search/label/Sudoku">sudoku solver</a> I fell into several traps. One of these was a little insidious. Back in the day, I thought EVERYTHING had to be represented as an Object. (yes, I know everything in ruby IS an object, I just mean you don't have to create your own class for every concept). So one of the first objects I built was a position object. Every cell had a position and a value. So position was a little object with an x and a y value, representing it's coordinates. It could give me positions of neighbouring cells, so that was it's behaviour. </p><p align="justify"> Now, one of the simplest methods of crafting the solver is to say, pick a cell, find all empty neighbours, and then figure out what to play in them. So I had some code of the form <em>cell.position.neighbours.select(&:empty)</em>. But I had defined neighbours as row positions + column positions + block positions. So I was bound to end up with a lot of duplicate positions. This wasn't a problem per se, but it was bound to slow down the solver. So I decided to make it <em>cell.position.neighbours.select(&:empty).uniq.</em> But ofcourse, this didn't work. I had to make sure that 2 positions were actually equal if they had the same value. That was simple, we've all seen it in basic textbooks.</p><br /><pre style="font-size: x-small"><br />class Position<br /> def ==(other)<br /> other.equal?(self) || (other.instance_of?(self.class) && other.x == @x && other.y == @y)<br /> end<br /><br /> def hash<br /> @x*29 + @y<br /> end<br />end<br /></pre><br /><p align="justify"> <br /> But that didn't work. Turned out there is == for equality, but there is also eql?. Which is used in arrays and hashes while comparing objects. (The use case for eql? being different from == seems <a href="http://www.wellho.net/mouth/985_Equality-in-Ruby-eql-and-equal-.html">obscure</a>, but it apparently ensures that 17 == 17.0 but 17 is not eql? 17.0).Anyway, that was easily fixed. I just had to override eql? and call ==<br /></p><br /><pre style="font-size: x-small"><br />class Position<br /> def eql?(other)<br /> self == other<br /> end<br />end<br /></pre><br /><p align="justify"> Well it worked, but ... holy crap. Performance was abyssmal. Earlier Ive posted solver times as being in the order of several seconds. But initially the solver took several minutes. It took nearly 20 minutes with the constraints checking solver. I was quite shocked. So I tried various tricks including profiling the code, and it turned out MOST of the time was spent in uniq ... and withing that in my eql? definition. Redefining eql? killed the system. So I ended up modifying my objects so that I could depend on pure reference equality and suddenly everything was blazingly fast again. Later ofcourse, I got rid of position. But the lesson I took away was, don't override eql? and == in Ruby, unless you have a damn good reason.<br /></p>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com0tag:blogger.com,1999:blog-5522230262649447143.post-48535781232860581932009-08-31T22:06:00.000-07:002009-09-02T13:39:42.030-07:00hasOwnProperty to the rescue<script type="text/javascript">Object.prototype.baz='baz';function show(divId, thingy){div = document.getElementById(divId); div.innerHTML += thingy + "<br/>";};function ownExplode(divId, thingy){for (item in thingy){show(divId, item);}};function ownExplode2(divId, thingy){for (item in thingy){if (thingy.hasOwnProperty(item)){show(divId, item);};}};</script><br /><div style="text-align: justify;"> Turns out the solution of how you can use objects as hashes and still introduce behavior in stuff like Object.prototype is to always check a method called "hasOwnProperty". This specifically tells you that a property on an object is its own and not derived from it's prototype. For example, let's say we have<br /></div><br /><br /><pre style="font-size: x-small"><br /> Object.prototype.baz = 'baz'<br /> function explode(divId, thingy){<br /> for (item in thingy){<br /> show(divId, item);<br /> }<br /> };<br /></pre><br /><div id="hasOwnProperty_1"><input value="What do you see if you explode {foo: 'bar'}" onclick="ownExplode('hasOwnProperty_1',{foo: 'bar'})" type="button"><br /></div><br /><div style="text-align: justify;"><br /> So we can't just use for ... in. But instead<br /></div><br /><pre style="font-size: x-small"><br /> function ownExplode(divId, thingy){<br /> for (item in thingy){<br /> if (thingy.hasOwnProperty(item)) <br /> show(divId, item);<br /> }<br /> };<br /></pre><br /><div id="hasOwnProperty_2"><input value="What do you see if you explode {foo: 'bar'}" onclick="ownExplode2('hasOwnProperty_2',{foo: 'bar'})" type="button"><br /></div><br /><div style="text-align: justify;"><br /> and there we go. There is a small price to pay in terms of ugliness, but in return, we can add stuff to Object.prototype with impunity<br /></div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com2tag:blogger.com,1999:blog-5522230262649447143.post-56618977145607120182009-08-30T00:19:00.000-07:002009-08-30T02:09:28.749-07:00Whoops, associative arrays? You mean Object?<script type="text/javascript">function show(divId, thingy){div = document.getElementById(divId); div.innerHTML += thingy + "<br/>";};function explode(divId, thingy){for (item in thingy){show(divId, item);}};</script><br /><div align="justify"> <a href="http://pathsny.blogspot.com/2009/08/why-you-should-not-add-stuff-to.html">Last post</a> I mentioned that extending Array breaks javascript associative arrays. But as <a href="http://pathsny.blogspot.com/2009/08/why-you-should-not-add-stuff-to.html#comments">Daniel Bodart</a> pointed out and can be confirmed <a href="http://andrewdupont.net/2006/05/18/javascript-associative-arrays-considered-harmful/">here</a> and <a href="http://blog.persistent.info/2004/08/javascript-associative-arrays.html">here</a>, there's no such thing as an associative array. It's just a javascript object. It's only for historical reasons that Array has been used for this purpose. When I was first reading about javascript I remember reading about arrays and associative arrays and it stuck in my head. I never realised that these were just objects that just happened to be using Array. </div><div align="justify"> There is one surprising thing about this though. Calling <span style="font-style:italic;">for a in b</span> on an <span style="font-style:italic;">array</span> or <span style="font-style:italic;">Array.prototype</span> does not reveal length or any of the inbuilt properties or fuctions. </div><br /><div id="ass_array_1"><input type="button" value="What does Array.prototype['length'] contain" onclick="show('ass_array_1',Array.prototype['length'])"><br /></div> <div id="ass_array_2"><input type="button" value="What does for (item in Array.prototype) show(item) reveal" onclick="explode('ass_array_2',Array.prototype);"><br /></div><br /><div align="justify"> Length is missing from the list of properties. And so are all the other predefined properties. But this is true of all Objects. In a similar vein <span style="font-style:italic;">Object.prototype.constructor</span> reveals Object, but dumping everything in <span style="font-style:italic;">Object.prototype</span> does not reveal the constructor property. </div><br /><div align="justify"> I guess this makes it clearer. Associative arrays being a special javascript construct is some sort of useful fiction that's used as a teaching aid. Once it's discarded you see that adding special methods to Array only breaks a misuse of Array. On reflection my continuing to believe Associative Arrays were a special construct is akin to learning all the laws of physics and still believing in Santa Claus. I guess the question now is, how do you add methods to Object.prototype without breaking the simple hash usage? </div>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com2tag:blogger.com,1999:blog-5522230262649447143.post-79623408749930978972009-08-29T04:35:00.000-07:002009-08-30T02:10:04.158-07:00why you should not add stuff to Array.prototype in javascript<script type="text/javascript">Array.prototype.eachIndex = function(func){for (item in this)func(item); };function bar() {a = [1,2,3];div = document.getElementById('foo');a.eachIndex(function (i){div.innerHTML += ' ' + i + ' : ' + a[i] + "<br/>"});}</script><br /><p>Why should methods not be added to the Array prototype in Javascript? The main reason is they break associative arrays, those where the index you use does not need to be a number, but could be anything. Kinda like a hash. </p><p>With an associative array you can do stuff like</p><br /><pre style="font-size: x-small">for (item in array)<br /> alert(array[item])<br /></pre><br /><br /><p>Methods added to arrays prototype will show you up in the for a in b call. Here's an example<br /></p><br /><br /><pre style="font-size: x-small"><br />Array.prototype.eachIndex = function(func) {<br />for (item in this)<br />{<br /> func(item)<br />}<br />}<br /><br />function bar() {<br />a = [1,2,3]<br />div = document.getElementById('foo')<br />a.eachIndex(function (i){div.innerHTML += ' ' + i + ' : ' + a[i] + "<br /><br />"})<br />}<br /></pre><br /><input type="button" value="click here" onclick="bar()"><br /><div id="foo">Whats in a?<br /></div><br /><br /><p>So there, I hope you've learnt your lesson!! Ofcourse you could decide associative arrays are pointless and I can manage with javascript objects thank you very much :). Did you notice peek which has been added to the array, presumably by blogger?</p>Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.com4