tag:blogger.com,1999:blog-40249340863956473482024-03-12T18:20:21.031-05:00Hack Jam Log BookUnknownnoreply@blogger.comBlogger42125tag:blogger.com,1999:blog-4024934086395647348.post-82880263876272949392013-07-19T21:19:00.001-05:002013-07-19T21:29:43.493-05:00Prolegomena to Any Future HackJam PostHi friends,<br />
<br />
Hacking and Jamming are alive and well in their various forms.<br />
<br />
Loki and I got FPGA dev kits a couple weeks ago and are giving a go at VHDL.<br />
<br />
I suppose I will make a nice note here when we have something to show off.<br />
<br />
Cheers,<br />
~js<br />
<br />Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-14643245578947447222012-07-18T23:01:00.001-05:002012-07-18T23:01:16.347-05:00annual updateI have been working with C++ quite a bit lately and had to deal with things like this:<br />
<br />
<div style="background-color: #444444; color: #cccccc; font-family: courier;">
<span style="font-size: x-small;">template < class List_entry><class list_entry=""></class></span><br />
<span style="font-size: x-small;"><class list_entry=""><br="">void List<list_entry><list_entry>< List_entry>::traverse(void (*visit)(List_entry &))<br />{<br /> Node<list_entry> *q;<br /><br /> for (q = head; q; q = q->next)<br /> (*visit)(q->entry);<br />}
</list_entry></list_entry></list_entry></br=""></class></span></div>
<br />
It was useful to invoke this method when I needed to print the contents of the list. I just passed in the name of a function like this:<br />
<br />
<div style="background-color: #444444; color: #eeeeee; font-family: courier;">
<span style="font-size: x-small;">void print_entry ( List_entry &e )</span><br />
<span style="font-size: x-small;">{</span><br />
<span style="font-size: x-small;"> std::cout << e << std::endl; </span><br />
<span style="font-size: x-small;">}</span></div>
<br />
I thought I could do a bit more advanced things by adding a void* argument, but there would be a little bit of work with that and it was not perfectly general.<br />
<br />
The notion of lambdas also occurred to me but I did not think too hard about it since they are still new in C++ so I was like ... meh.<br />
<br />
Then I kept thinking some more and I was like, uggh, the way I toss bits around, an additional arbitrary callback argument will be approximately as powerful as a temporary anonymous function, if not as syntactically pretty, and both of these are going to be more or less limited to doing only so much with the current object in the iteration.<br />
<br />
The potential versatility suggested by this kind of element-iterator with arbitary callback suggests interesting possibilities that, well, ought to be a lot easier! It would be great if I could call traverse on a binary search tree and have it generate a dot file representing the relationships between nodes so a computer program could draw them nicely for me. In fact that kind of thing seems like what any traverse method worth its salt ought to have been meant for. But it's unpleasant to do in a general way and without unnecessarily abusing global state! A callback with three parameters (parent, left, right) is one option, but I don't want to be bound to the number 3. Maybe I can just do (a, b, NULL) for a two-parameter version. But why stop there? How about vararg? Or maybe a vector of arguments? These all seem very unsatisfying and ad-hoc to me!<br />
<br />
It might be nice if some portion of the current stack frame could be made available to my callback function -- even in a safe and read-only way. I promise I do not want to break things, just know where I'm at so I can figure out where I'm going! Oughtn't there be a concise way to define a callback with read access to certain local variables belonging to the function invoking the callback?<br />
<br />
How can I achieve such a thing in C or C++? I mulled over this for several days, toying in my head with various unimplementable thoughts and vacillating over whether the idea itself was good or not, or whether I was already overlooking any useful language feature that made this easy as cake, or whether I had dug myself into a tarpit of hopelessly unimprovable design? A binary search tree could be drawn any number of ways, but, darnit, why not with such a traverse method as described above? No world can be a happy one that has factories where one robot tosses doodads onto a conveyor belt and another operates a claw to inspect each, one by one, without knowing anything of the status or history or progress of the doodad-loading operation; else that claw-bearing robot be an uninterestingly simple one, and the factory incapable of producing anything of value.<br />
<br />
I was completely flummoxed. This is so basic a need, and it tears at the fabric of my thoughts with such relentlessness, someone else must already have figured it out; I must rest my mind a short time before I drive myself crazier!<br />
<br />
Though I may have permitted my brain a brief respite from the harrowing, I could not fully abandon the matter, in spite of the mounting practical reasons to do so. Before I was prepared to abandon all responsibility and set forth once more and finally forever down this path to ultimate insanity, the notion was abruptly thrust into my consciousness to consider the bigger picture. Bigger than binary trees -- what of the general class of graphs? Here, my mind began to spin again. It would not cut it to just pass references to the parent, left, and right nodes. Total parameter variability was necessary to account for the diversity of graph representations and characteristics! In the same instant that it occurred to me that the entire state of the invoking function must be fully accessible to the callback, a sharp blow glanced off my lower abdomen and I landed on my back, striking my head on the asphalt. Dizzy, I wheezed through a scowl and by the time I had lifted my head up, a formation of one thousand diiqs and calcnerds had begun rapidly marching towards me, brandishing brightly colored pugil sticks. A dark horse with a confident gait followed. It was the general, Adam. The head of each of the two advancing columns set down his weapon and appeared on either of my shoulders. They leaned in close to my ears as if to whisper. I could not fret over the decision to listen to one or the other because they both shouted in unison, startling me further. My mind was blank from fear and as I groped for comprehension, they boxed my ears and while I reeled they fluttered up in front of me and mocked me with gestures I could barely make out through the taste of tears and snot. They flew off into the sunset together, the army marching along under them. Parentheses formed in their wake, and I could not tell if they were opening or closing.Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-70946262106030912192011-08-01T07:50:00.002-05:002011-08-01T08:05:41.767-05:007/28Hackjam was pretty fun <span style="text-decoration: line-through;">this</span> last week. I expressed some disdain for Lisp's single single quote quoting syntax, born mostly in my ignorance, and got some good feedback from the Lispers about how it is used and what it does. The "close" for the single single quote quote is whitespace which I had previously assumed but there are so many flavors it was hard to be certain.<br /><br />We also played with <a href="http://www.movsd.com/thegun.htm">TheGun.exe</a> which brings me no end of delight -- it does not have a config file, but its standalone configurator modifies the exe so that next time it runs the settings you configured are "default". "Played with" included loading it in Notepad.exe as well as vim and attempting to change some strings and observing it to fail loading, both in Windows 7 and Wine 1.32. Under Wine, at least, TheGun.exe would not save modifications to the very executable image responsible for the running process, but you could save them to a different file at least and run that, or attempt to. I suspect you probably just couldn't write to the exe of any running process. Near the top of the file there were some mentions of TheGun and I changed one to Horse and it would not load, sadly.Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-31514132125742771562011-07-01T18:48:00.007-05:002011-07-07T00:58:16.943-05:00Movie GUIsI went to Hackjam the first time in who knows how long and it was nice to see everyone again.<br /><br />I found accessmaincomputerfile.net the other day and was inspired to try my hand at some immersive or attention-grabbing GUI components. Movie GUIs are overkill and extreme and make "real" GUIs look like the 20th century -- the ones I get excited about anyhow. The other ones I get excited about are the ones that are too real such as Trinity+nmap or SunOS in the new Tron movie. These aren't very exciting to see on your normal computer though since, well, they already are on your normal computer.<br /><br />My first step is to implement a clock applet resembling the <a href="http://accessmaincomputerfile.net/photo/1280/1601273791/1/tumblr_lc0q3jfgng1qdhhtj">screenshot from Darkstar</a>. I am running XFCE4 in Arch right now so I am going to target this environment. Adam was very helpful to me in gathering some information and getting started on setting up the build environment and sharing his perspective on how it might work. I have successfully compiled the original clock applet now. There are five options, each of which is based from a .c file in the xfce4-panel source tree, so my intent is to add clock-darkstar.c as an important part of finagling a sixth option into the mix.<br /><br />After doing all this hard work I decided making a XFCE plugin did not really further my goals and it would probably be more fun and tasty to pursue another avenue that did not necessarily require XFCE for example.<br /><br />I already have some experience with SDL so I am going to bark up that tree.<br /><br />As much as I want to learn new things, what I really want is to have a sweet new Darkstar (1974) clock applet. Now I am abusing the term "clock" and "applet" since this beastmaster can be so much more! A clock for starters, but the view implies so many fiddly knobs! Every text field is completely configurable in a number of ways. Good grief I am already in over my head before I even hit the water!<br /><br />I am going to nuke my copy of the xfce4-panel out of spite and also to make sure I have a lot of headache to go through in case I forget that I am doing this with SDL and not making a xfce4 plugin.<br /><br />I am also listening to Voltaire right now. Background music, not advice.<br /><br />Cheers!<br /><br />EDIT: here is a great link to what I have accomplished thus far <a href="https://jonathanstone.homeip.net/darkstar.tgz">https://jonathanstone.homeip.net/darkstar.tgz</a>. <https: net="" tgz=""> Please kindly disregard the certificate error, thanks. You can build it with some normal command such as "make". Also you need to put a 639x359 darkstar_1974.bmp in the folder at runtime since I am NOT distributing that. I got mine from accessmaincomputerfile.net as linked above and converted it to bmp with such a command: "convert darkstar_1974.jpg darkstar_1974.bmp". The 20ms delay is necessary to make the thing not nom down on all the cycles. Experimenting with higher values resulted in even lower (<1%) CPU utilization but then I couldn't close the window because the events occuring during the wait cycle are not processed.<br /></https:>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-80654969173930934372010-12-12T13:34:00.003-06:002010-12-12T15:04:33.310-06:00silly shell tricksYou can use 'tac' to implement a stack.<div><br /></div><div>Red comes from stdin, black is stdout:</div><div><br /></div><div>Instead of doing `factor`:</div><div>$ <span class="Apple-style-span" >factor</span></div><div><span class="Apple-style-span" >33</span></div><div>33: 3 11</div><div><span class="Apple-style-span" >19</span></div><div>19: 19</div><div><span class="Apple-style-span" >27</span></div><div>27: 3 3 3</div><div><span class="Apple-style-span" >^D</span></div><div><br /></div><div>You can do this:</div><div>$ <span class="Apple-style-span" >tac | factor</span></div><div><span class="Apple-style-span" >394</span></div><div><span class="Apple-style-span" >87</span></div><div><span class="Apple-style-span" >19</span></div><div><span class="Apple-style-span" >666</span></div><div><span class="Apple-style-span" >^D</span></div><div>666: 2 3 3 37</div><div>19: 19</div><div>87: 3 29</div><div>394: 2 197</div><div>$</div><div><br /></div><div>What was reversed was the order of inputs sent to factor, not the output generated by factor. The effect is of course haveable a number of different ways:</div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | tac</span></div><div><div>666: 2 3 3 37</div><div>19: 19</div><div>87: 3 29</div><div>394: 2 197</div><div style="color: rgb(255, 0, 0); "><br /></div></div><div>and this is the same procedure however factor sees them in the order you typed them, not in their stack-reversed order. I think I can use this to my advantage someday, when I want a filter to see reversed input.</div><div><br /></div><div>You can also flip the output over the logical y = -x line using both tac and rev; this is also mostly JFF (just for fun):</div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | tac | rev</span></div><div><div>73 3 3 2 :666</div><div>91 :91</div><div>92 3 :78</div><div>791 2 :493</div></div><div><br /></div><div>Clearly nonsensical. These filters are transitive however!</div><div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | tac | rev | tac | rev</span></div><div>394: 2 197</div><div>87: 3 29</div><div>19: 19</div><div>666: 2 3 3 37</div></div><div><br /></div><div>and</div><div><br /></div><div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | tac | rev | rev | tac</span></div><div>394: 2 197</div><div>87: 3 29</div><div>19: 19</div><div>666: 2 3 3 37</div></div><div><br /></div><div>and</div><div><br /></div><div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | tac | tac | rev | rev</span></div><div>394: 2 197</div><div>87: 3 29</div><div>19: 19</div><div>666: 2 3 3 37</div></div><div><br /></div><div>and</div><div><br /></div><div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | rev | tac | tac | rev</span></div><div>394: 2 197</div><div>87: 3 29</div><div>19: 19</div><div>666: 2 3 3 37</div></div><div><br /></div><div>and</div><div><br /></div><div><div>$ <span class="Apple-style-span" >echo "394 87 19 666" | factor | rev | rev | tac | tac</span></div><div>394: 2 197</div><div>87: 3 29</div><div>19: 19</div><div>666: 2 3 3 37</div></div><div><br /></div><div>While I did not exhaust the combinations of two tacs and two revs, I feel confident knowing their properties that my conjecture holds, and I would even go so far as to say that any finite stream for which their exists sufficient RAM to process is preserved through arbitrary linear combinations of even counts of tacs and even counts of revs. A number of assumptions are of course depended upon: tac should require no more space than the streamed lines actually occupy and rev's space is constant in the number of lines and per-line, linear in the length. With clever stream pointer manipulation, both of these tools should not require to allocate additional space however.</div><div><br /></div><div>I have decided to run into a dense jungle banging on a drum and screaming DEATH TO MONKEYS!!! Here is a map of my progress: <a href="http://piratejon.com:8080/mirror">http://piratejon.com:8080/mirror</a>.</div>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-14225642396339803972010-10-10T12:00:00.003-05:002010-10-10T12:19:42.017-05:00socketsHack Jam Log Book deserves a new post.<div><br /></div><div>I have not been to hackjam in a while due to a great personal inconvenience in the tradeoff between space and time.</div><div><br /></div><div>This has not limited my hacking however.</div><div><br /></div><div>This weekend I made a great sockets program in C. It has the following features: if you run it with a certain set of flags it attempts to initiate a TCP connection with a specified host on the specified port. If you run it with a different set of flags it listens for a connection attempt on the specified port. These behaviors are meant to be used in a complementary way though you can do whatever you want with them really. After a connection is established, a message loop enters which polls both stdin and the established socket connection. Since my terminal is in some kind of cooked buffered line mode, it sucks when you are typing and the remote host sends a message, but fortunately nothing is lost except maybe the user.</div><div><br /></div><div>There is no protocol.</div><div><br /></div><div>This is not a lot different from telnet however it has even fewer features and capabilities.</div><div><br /></div><div>It does however illustrate basic blocking sockets and select() in C.</div><div><br /></div><div>It does not currently compile in Windows (maybe cygwin?) though it will soon enough -- a little WSAStartup() here and maybe some WSACleanup() there and some other smidgens and #ifdefs and we'll have it.</div><div><br /></div><div>Code at <a href="http://jonathanstone.homeip.net:8080/chat">http://jonathanstone.homeip.net:8080/chat</a></div><div><br /></div><div>Direction: ncurses to solve dumb text entry problems, full Win32 support, and openssl for point-to-point encryption.</div>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-56660485455220808882010-03-29T17:54:00.002-05:002010-03-29T17:54:59.137-05:00A Painted BlogI'm trying a little experiment; it's a blog that's painted on a 4'x8' piece of plywood; each new post is painted right on top of the last one, building up a visual history in layers of paint. Check it out at http://diiq.org/Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-11602899260837141382009-08-09T09:31:00.004-05:002009-08-09T13:03:24.220-05:00xkb and xmodmap: a big messSo I've convinced myself to try a new keyboard mapping; arensito is currently the only word that I can type quickly and accurately.<br /><br />I thought that I would take a moment to write down the steps that it took to get a mapping with an extensive and unusual Alt-gr map up and running (on Linux). What is available online is exceedingly unhelpfull.<br /><br />1. I used Mod_switch rather than ISO_level3_Shift. ISO is the 'correct' choice, but by default N and J cannot be level shifted; fixing that requires xkb, and xkb is evilly difficult to use.<br /><br />2. Speaking of xkb and evil, Mod_switch won't always work unless xkb is off. So in xorg.conf:<br /><pre><br />Section "InputDevice"<br />Identifier "Keyboard0"<br />Driver "keyboard"<br />Option "CoreKeyboard"<br />Option "XkbDisable" "true"<br /># Option "XkbRules" "xorg"<br /># Option "XkbModel" "latitude"<br /># Option "XkbLayout" "us"<br />EndSection<br /></pre><br />Make sure to comment out all the xkb rules. In .xsession or .xinitrc or wherever you put scripts that run before your X session starts:<br /><br /><pre>export XKB_DISABLE=1</pre><br />3. Edit .Xmodmap:<br /><pre><br />keycode 44 = j J plus<br />keycode 0x41 = Mode_switch<br />clear mod3<br />add mod3 = Mode_switch<br /></pre><br />(note that I use the spacebar as my Mode_switch; chances are you want someting different)<br /><br />Mode_switch uses the third and fourth keysyms; 'j' and 'J' are the first and second, 'plus' is the third. space+j will return '+'.<br /><br />Please understand that this is the wrong way to do this; the 'right' way is to use xkb. However, rolling your own xkb mapping is a major undertaking, while xmodmap is reasonably simple. Disabling xkb as I have done here is not reccomended generally, and can apparently cause problems if you use compositing. Nevertheless, this solution works for me.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-39448959243645798622009-08-08T11:17:00.005-05:002009-08-08T11:36:37.723-05:00a lispI'm working on designing a programming language. I am doing so because I want to do more of what I enjoy about programming. Boilerplate code does nothing for me. It is the beautiful code, the obvious-once-you-see-it-but-what-were-you-smoking-when-you-saw-it code, that makes me enjoy programming. I want a language that maximizes my experience of the numinous, a language that comes as close to the platonic program in my head as it can.<br /><br />I don't want a super-efficient language, or a minimal language, or a super-readable language. I want a language that is <span style="font-style: italic;">fun.</span><br /><br />The most controversial way I can put it is probably also the best: there is a quote.<br /><blockquote><br />"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." – Brian W. Kernighan</blockquote><br />My design philosophy is this: I want a language in which I can code as cleverly as possible. Because I enjoy it. To hell with anything else.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-7552644281997107372009-06-25T15:57:00.003-05:002009-07-15T19:25:41.110-05:00Clone of Existing Game with 3D EnhancementI have spent the past three HackJam sessions cloning the super-fun Flash game <a href="http://www.k2xl.com/games/boomshine/">Boomshine</a>, in C. The reason for doing this is because I would like to add a 3D extension to this game. I want the third dimension to be time. Right now the balls bounce about on a flat plane, and the progression of time from present to more present results essentially in a visual overwrite of the balls at their new space coordinates. Well, by using perspective, I want to draw a 3D representation of the balls so that you can see in a single glance where the ball started and where the ball will be after many units of time have passed and, up to pixellation, where the ball will be at every moment in between. To describe this further, let me explain that while the balls are just bouncing about on their original 2D plane, the 3D view will be essentially static because the balls' velocities are fixed. The 3D view can only change after the player drops his ball with the mouse, and the outcomes of the original balls interact with that which was not there before.<br /><br />I got the idea to do this from a discussion with Montana about "solving" the game -- i.e. figuring out where you could place your ball to ensure that you "won". He suggested something about Einstein's light cones and thus this idea was born.<br /><br />I have never done 3D graphics before except in QBasic like ten years ago so this will be challenging and interesting.<br /><br />Right now I have successfully cloned the behavior of the original game. The balls bounce, collide, grow, shrink and die predictably, and all parameters (initial size, color, growth rate, target growth size, waiting duration, shrink rate, and number of balls) are completely customizable within reasonable limits i.e. no negative radii.<br /><br />With regard to shininess, I hope to do some transparency/alpha blending so the balls don't just overlap, also when bouncing off the edges the sprites flicker because the collision logic is funky however they ultimately careen off at the correct angle and stop flickering when they get away from the edge. Also maybe sound at some point? However these are all ancillary to my chief interest, which is representing the time dimension spatially.Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-51556395522912409152009-02-24T23:07:00.004-06:002009-02-24T23:36:06.900-06:00Haskell -> ArcLately, Haskell's type system, powerful as it is, has been tending to get in my way. It worked fine when implementing chunks of natural language parsers, but when I went back to revise my design, I was having a horrible time. More recent toy projects such as the RSS reader or a simple graphical game have similarly made me grumpy.<br /><br />At the same time, compile time type checking has probably detected more than it's share of bugs in my code. It's a tradeoff. Whether it's a net win or loss is hard for me to say; I've done very little functional programming without strong typing. I don't like Java style strong typing, but the ML type system is a different beast. Having spent the better part of a year working in Haskell, I'm due to try a new programming language, so I'm going to move to Lisp for a while.<br /><br />Unfortunately for me, the essays that convinced me to finally a Lisp were on Arc, an arguably incomplete dialect. It has almost nothing in the way of libraries. After looking at Arc, though, Common Lisp looks warty and Scheme's lack of unhygenic macros is disturbing for a power language. So I'll start with Arc, though I may well have to move to Common Lisp if I get frustrated with what I can't do (though I do have something of a backup plan in the works for that; more on that later, if it comes to pass).<br /><br />Picking up on loose ends, blogwise, my tron lightbike FRP game fell apart when I had trouble working out a definition of the behavior of the walls trailing behind the players. I couldn't find a way to define a behavior that was a list of snapshots of another behavior at points dictated by a third behavior, and I couldn't help feeling that it was more natural to define it procedurally (though that may just be what I'm more used to). I ended up being frustrated enough that I put it down and never came back to it.Adam Heckhttp://www.blogger.com/profile/00716800125148427529noreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-59812307720673392932009-01-15T17:24:00.002-06:002009-01-15T17:33:45.172-06:00Settling DownI haven't posted in a while because I've been all over the map lately. Shiny objects that have occupied me include kernels, compilers, HTML engines, procedurally generated game content, PJ's scrapture program, <a href="http://yudkowsky.net/singularity/aibox">the AI Box game</a> (careful with that box, son, there's a puma inside), writing a small RSS reader, and now, Functional Reactive Programming. <a href="http://www.haskell.org/haskellwiki/Functional_Reactive_Programming">FRP</a> seems to be to event-driven programming what functional programming is to imperative programming. I'll talk more about that once I'm more confident that I've got my head around it.<br /><br />I'm dropping in to call a shot. For next week I'll have a simple FRP implementation of the Tron Lightbike game.Adam Heckhttp://www.blogger.com/profile/00716800125148427529noreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-23265021625121964022008-12-27T00:55:00.009-06:002008-12-31T16:18:37.596-06:00Merry Holidays, and Screen Capture Update<div>The Screen Capture dealio described in my last post is coming along. It presently displays two adjacent colored boxes: one solid foreground colored, and one mostly background colored but flickering to foreground color at a customizable rate of once per n frames; the foreground and background colors are also customizable.</div><div><br /></div><div>The least n for which the results are meaningful is, of course, 2, which means that during every 2nd frame the box is painted foreground colored while during all other frames the box is background colored. At this rate my naked, unaided eye can infer the foreground color with ease, though it's hard to say whether that is affected by the adjacent solid box -- this will have to be eliminated during future double-blind tests. Unfortunately the rapid cycling introduced some horizontal lines which were very unpleasant to look at and which will have to be dealt with effectively before useful conclusions can be drawn.</div><div><br /></div><div>Adam and Sam gave helpful insights on what was causing the unpleasant horizontal lines and how to cope with it. Presently the main drawing loop merely increments the frame index counter, wraps it to zero if necessary, and throws up the appropriate frame for the flickering side, and does this as quickly as possible. The horizontal line problem arises when the program writes to the colored box's memory location while that location is being read and updated by the display hardware. In order to get around this it is necessary to interrupt the flow of things and patiently wait for the vertical refresh to complete and then resume.</div><div><br /></div><div>A vertical refresh of 60Hz means, that 60 times per second the screen will be redrawn, and a higher FPS than that should make it always invisible. I think that because there is no computation or rendering or any complicated graphical processing, only blitting a small square that's already in memory, that it should not be hard to get better than 60 FPS, thereby making the refresh rate, and horizontal lines, appear invisible.</div><div><br /></div><div>Is this possible? The SDL trick of creating a double-buffered hardware surface and calling SDL_Flip() in the draw loop does not seem to have helped the horizontal line problem. So I'm looking into OpenGL to see if that will afford me the degree of control necessary to eliminate this problem. Sam suggested that because of various factors which I don't recall in their entirety, including but not limited to some things having to do with what the eye can keep together and how quickly the monitor updates, I would only be able to split it into about four frames before the image did not appear whole. Makes sense, if the images are too far apart (in time) then the eye may not unify them. This will of course be tested.</div><div><br /></div><div>Next up will be separating the target display image into nonoverlapping (and not necessarily continous) chunks, one on each frame. There are combinatorially many ways of splitting a fixed number of pixels onto a fixed number of frames. A few of the ways I'll be looking at are:</div><div><ul><li>random pixels: approximately (width*height)/n pixels will be pseudorandomly selected from the image and recorded to a frame with no repetition. Or some repetition but not in every frame? These are variables that will have to be examined for best output.<br /></li><li>"checkerboard": the image will be divided checkerboard style into alternate squares, so that individual frames will appear as checkerboards, alternating background with foreground.<br /></li><li>"radially chopping", or "pi cutting": from the center of the image outwardly drawn radii at regular (or irregular) angular intervals will determine where one region ends and the next begins. Again, one or more nonadjacent regions to a frame. No/some repetition?<br /></li></ul></div><div>The more I think about this, the more I think that the clearest aggregate image with the least information about the whole picture contained in a single frame will be had with random pixels and some repetition spread evenly enough so that most pixels that repeat do not appear next to other repeating pixels very often. For specific definitions of "most" and "very often" and "next to" and "evenly enough" and such.</div><div><br /></div><div>Jumping right ahead to implementation details ... assuming there to be an arbitrary upper limit on the number of frames that an image can be split into, and assuming that arbitrary upper limit may just happen to be equal to the size in bits of a single data register in the processor on the machine I've been doing all the development for this project on, and assuming that I want to implement several different ways of splitting images up into frames and that given this last assumption that I certainly do not want to duplicate a whole lot of code doing so but would much rather, say, pass an image to any one of several image-to-frames splitting routines which may exist at any point in time and to have those routines all return an efficient description of how that image should be split among any desired number of frames upto the arbitrary limit, I think that I can do this: create a "frame mask" of dimensions equal to that of the image whose elements are 32-bit integers, with bit 0 indicating whether the pixel should be present in frame 0, and bit <span class="Apple-style-span" style="font-style: italic;">n</span> indicating whether the pixel should be present in frame <span class="Apple-style-span" style="font-style: italic;">n</span>. The splitting routines would all be able to write this format quite easily, and the post-splitting frame-generating routine would have no trouble reading it at all. This also makes it easy to save particular random splittings that turn out to be favorable for later analysis or just to show your friends.</div><div><br /></div><div>Now, I'm done rambling. Sometime this year (2008) I'll get git setup on dreamhost and post the code for all to see. It's not pasted here because, frankly, in its current state, it's not very interesting :)</div><div><br /></div><div>UPDATE: repository'd: <a href="http://piratejon.com/git?p=scrapture.git">http://piratejon.com/git?p=scrapture.git</a></div>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-68582611687630204262008-12-09T22:04:00.004-06:002008-12-09T22:15:08.874-06:00Hack Jam: 3.12.08Topics of discussion: AI, NLP, Cantaloupe, Primes, and the possibility of being 4/9ths Asian.<br /><br />Just thought I'd dash out a quick note on what went on last week. PJ pulled off several examples of the ever-impressive trick: hacking with cat. That is to say, he wrote compilable c programs using cat, without re-writing. <br /><br />Those of us who use interpreted languages were perhaps nonplussed. He showed a clear and utter disregard for the fact that coding is supposed to be hard.<br /><br />However, I took back my own when the time came to sum an infinite series --- Lisp's native support for calculation with rational numbers allowed me thousands of digits accuracy without writing a bignum summer, making my solution only one line long.<br /><br />This brought to mind an interesting challenge --- writing code with write-or-die...Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-58195830848404329222008-12-01T02:10:00.004-06:002008-12-01T03:07:17.834-06:00Breaking Screen Captures<div>So my homie Nick had an interesting idea that I thought I would spend a bit of time exploring. The idea is to break the screen-capturability of an image by replacing it with several rapidly refreshing frames that appeared to the naked eye over time as a coherent image but which individually conveyed no useful information and rather appeared scrambled. So that under screen capture you get a single unrecognizable frame. If you take a digital video (i.e. rapid series of screen captures) you may still be able to view the image by playing the video. But you should not be able to extract the image by itself without some eyemulating algorithm, which we hope would be extremely difficult to compute.</div><div><br /></div><div>I think it would be quite possible to simply fraction the image into distinct geometric regions and display only part of the whole per frame, however it would be even easier to reassemble these than it was to separate them.</div><div><br /></div><div>So, this week I'll begin by writing some stuff that blits an array of same-size bitmaps in order to the same region of the screen. Then I'll experiment with colors -- what does a solid red region look like, and what does a "red emulated" region look like, side-by-side, even? Does the number and difference/sameness between frames needed to convey a solid color depend on the color being conveyed? Is it easier or harder to emulate two different colors simultaneously -- that is to say, does color A being adjacent to color B change the requirement for number and quality of frames needed to achieve emulation? How about dithering A and B, and with different sizes of blocks? Hopefully the answers to these questions will suggest a formula for easily deconstructing an image into frames that are not easily reconstructible except by the natural power of the unaided (or lens-aided) human eye. At first I will treat color. Next will come shape, and how different shapes in different colors can be contrived to emulate a target image. Finally I hope to make an arbitrary jpeg unscreencapturable without hiding it in a hardware buffer -- this is in the long-term of course.</div><div><br /></div><div>One application for this sort of technology is for controlling the shareability of images through websites or other software. In the past schemes have been implemented to disable mouse access of an image via Javascript or by otherwise manipulating the user-agent to act rather as the "content-provider-agent". I find this usage to be mostly heinous, but it is interesting nevertheless. More useful would be in CAPTCHA technology, where an algorithm might struggle to decode a series of frames that a human eye could read easily -- this may even lead to CAPTCHAs that are easier to read for humans but that bots could not reassemble into a coherent image, much less find the text in. This usage would be much less heinous, though it is still solving a problem that shouldn't exist. I think the most useful usage for this will be in elucidating characteristics of the human eye. And making fun of my colorblind friend Bob.</div>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-43713748665608481262008-11-28T16:16:00.002-06:002008-11-28T16:24:06.436-06:00Write or Die: Now on Emacs!For those of you that write, or wish you wrote, or otherwise procrastinate while performing text-based activities, try out <a href="http://lab.drwicked.com/writeordie.html">write-or-die</a>. It is a nice cattle prod; if you don't write for several seconds, it will punish you. I find that the Kamikaze mode is most effective --- the punishment is that it will delete words, bit by bit, until you begin to write again.<br /><br />However, I use emacs; and switching from my carefully-tuned text-editor extraordinaire to a javascript-based text-box is a bit of a disappointment. That's why I threw together this emacs version of write-or-die.<br /><br />Just paste the following into your init.el, and when the time comes, <span style="font-style: italic;">M-x write-or-die</span>. When you have accomplished your goal, <span style="font-style: italic;">M-x no-more-die,</span> and you're set.<br /><br /><pre><br />(let ( (write-or-die-time ())<br /> (write-or-die-init ()) )<br /><br />(defun write-or-die ()<br /> (interactive)<br /> (setf write-or-die-init (run-with-idle-timer 3 t 'w-or-die)))<br /><br />(defun w-or-die ()<br /> (interactive)<br /> (kill-region (point-max) (- (point-max) 10))<br /> (setf write-or-die-time (run-with-idle-timer<br /> (time-add (current-idle-time)<br /> (seconds-to-time 3))<br /> ()<br /> 'w-or-die)))<br /><br />(defun no-more-die ()<br /> (interactive) <br /> (cancel-timer write-or-die-init) <br /> (cancel-timer write-or-die-time))<br /><br />)<br /></pre><br />Possible improvements --- flashing colors, like the web-version has, to warn you of the time limit; word-by-word deletion, rather than 10 characters at a time; variable time limit; etc. But those can wait. Right now I need to write another 10,000 words.Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-35765831352054384182008-11-26T20:19:00.002-06:002008-11-26T20:55:54.493-06:00MythTVFor a quick breather away from the piano, I decided to set up a MythTV box.<br /><br />For those of you who are unfamiliar, <a href="http://mythtv.org/">MythTV</a> is the Linux DVR project. It also has a lot of optional plug-ins (installed seperately) for things like Weather, News, NetFlix queuing, etc. Not having a digital capture card makes my success thus far limited, but allow me to tell you what I have learned.<br /><br />First of all, for those who are interested in different types of cards out there, here are the different terms that get thrown around:<br /><br />* NTSC [in terms of broadcast] = analog/"your grandmother's television". Think the TV with two knobs, the first one you turn to "U" to make the second knob work.<br />* ATSC = new, hip digital broadcast TV [officially taking off Feb 2009]<br />* Clear QAM = The "free" broadcast channels your local cable provider gives out. Usually includes the ATSC channels in your area. For those who are interested, my research shows that Cox Cable has a whopping 6 Clear QAM channels available in Norman, OK.<br />* DVB = Digital Video Broadcast. DVB-T is terrestial, DVB-C is cable, DVB-S is satellite.<br /><br />With the basic terminology out of the way, have fun looking for good cards. Reviews are limited. You might enjoy these handy posts for tutorials on installing MythTV and selecting cards:<br /><br /><a href="http://www.mythtv.org/docs/mythtv-HOWTO.html#toc5">http://www.mythtv.org/docs/mythtv-HOWTO.html#toc5</a> [Installing MythTV]<br /><a href="http://www.mythtv.org/wiki/index.php/Category:Video_capture_cards">http://www.mythtv.org/wiki/index.php/Category:Video_capture_cards</a> [Capture Cards]<br /><br />There are a lot of pre-requisites, including some that aren't listed. The big one is of "<a href="http://rpmfind.net/linux/rpm2html/search.php?query=qt3-MySQL">Qt3MySQL</a>" [why they don't list it as an actual pre-req, I don't know]. The ones listed in the tutorial include:<br />mysql, gcc, freetype2-devel, xorg-xserver-devel, qt-devel and lame.<br />Also required:<br />qmake, Xv, QT3MySQL, mplayer, ffmpeg, transcode, many others<br /><br />Pro Tip!<br />If while making a program you get lines that show...<br /><strong>/usr/bin/ld: cannot find -lMERPMERP</strong><br /><strong>collect2: ld returned 1 exit status</strong><br /><strong></strong><br />Do a search in your package manager for MERPMERP. Many times, that will resolve it and you can resume MAKEing your program.<br /><br />Anyway, when you go to MAKE the program, assuming you have everything, it will take about 30+ minutes to compile with a pretty decent CPU, so I recommend a good lunch. <br /><br />Once everything is installed, run mythfilldatabase to populate your SQL backend with channel data from your card. If you don't like something you've done during the initial setup, don't worry... you can always run mythtv-setup again.<br /><br />As a last note, MythPlugins is worth installing at least for MythArchive. Unless you want to purchase a <a href="http://www.dell.com/content/products/productdetails.aspx/pvaul_md1000?c=us&l=en&s=bsd&cs=04">nice JBOD system </a>for harddrives, install it and play around with the "Archive" [burns recorded shows to DVD]!<br /><br />As I hear more about cards, plug-ins and more, I'll keep you posted.<br /><br />Regards,<br /><br />BrandonBrandon Bagwellhttp://www.blogger.com/profile/07241811394960939097noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-3646330125637374392008-11-21T14:56:00.004-06:002008-11-26T19:51:16.429-06:00Postscript PostersOne of the more exciting things you can do with Postscript is to make a poster -- vector graphics are sexy and you can easily make them as large or small as you want while the plotter or viewing device faithfully retains the original image's sharpness and definition. And bigger is always better: Why make a Rhode Island-sized poster when you can have Texas for the cost of a scaling factor?<br /><br />I set out to make a poster and found that although it was ultimately a straightforward task, I had to figure a few things out to get it to work.<br /><br />First, it was necessary for me to write the whole poster on a single 8.5x11 sheet. Apparently it is very hard to change the page size in postscript, so sticking with the default and specifying an appropriate bounding box worked best for me. The bounding box is done up by writing near the top of the file<br /><span style="font-family:courier;">%%BoundingBox: x1 y1 x2 y2</span><br />So, you specify the lower-left and upper-right corners of the smallest rectangle that includes everything you want to be in the image.<br /><div><br /></div><div>On my first try I simply drew my graphics at the intended poster size on the page -- all that was visible to me was the bottom corner of the page, while the majority of the graphics were plotted at coordinates not within the page size.</div><div><br /></div><div>Once I had everything looking the way I wanted it to I just had to issue the scale commands at the beginning of the file:</div><div><span style="font-family:courier;">.15 .15 scale</span></div><div>caused the graphics to follow to be drawn at the fifteen percent required to get them on the page.</div><div><br /></div><div>At that point I used the "poster" utility with a scaling factor of the inverse of the one I supplied to postscript -- here, 6.667 -- and piped the output to a new ps file. The new ps file went to ps2pdf, and the final product was the poster at the size I needed split over 40 8.5x11 pages. Cool beans!</div><div><br /></div><div>Ultimately I decided that what I did want was a whole poster and they are not that expensive so I will take the downscaled pdf to Kinko's and have them upscale it to poster size and print it for me.</div><div><br /></div><div>Making posters is pretty cool and I think you should try it too.</div><div><br /></div>Jonathan Wesley Stonehttp://www.blogger.com/profile/11821543582142009054noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-62130980925959373742008-11-18T19:58:00.004-06:002008-11-20T22:58:41.654-06:00Livescribe Pulse Hacking: The buisness already!Blah, blah, blah. Those of you who were up to date on your Fourier transform are now bored out of your mind --- and those of you who weren't are still wondering why I'm talking so much about it rather than about the pen.<br /><br />So now, it happens! Data is sent from the pen to my laptop, running Linux, via <span style="font-style: italic;">vibrating air!</span> Doesn't it just put you at the edge of your seat?<br /><br />The good news: "Hello, World!" did get from my pen to my desktop. The bad news: it did so at something like 8bps --- that's 8 <span style="font-style: italic;">bits</span> per second, mind you. So it took something like a quarter of a minute just to send those two words.<br /><br />Are improvements possible? Absolutely. I can increase my sampling rate (currently 8kHz, could easily be 16). I can increase the number of different frequencies to increase the per-unit-bandwidth.<br /><br />But what is currently killing me is (I believe) the period <span style="font-style: italic;">between </span>tones; not the tones themselves. There are two dangerous things that happen during the transition. One is that the Fourier analysis for time-bins which contain a frequency change have two peaks; this makes classifying those bins far more challenging, even classifying them as worthless and ignoring them.<br /><br />Second, and a little more worrying, is on the pen: the amount of time that passes between the current sound clip ending after I request that the next sound play, and the next sound actually <span style="font-style: italic;">playing</span>. It is, uh ... not zero. And that of course makes the the whole in-between-tone period even HARDER to identify and cope with.<br /><br />Short note. Hopefully have more time next week to discuss possible fixes for all these faults.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-4024934086395647348.post-19691703787973856472008-11-17T00:19:00.004-06:002008-11-17T00:29:34.957-06:00Word Mangling, Verb Conjugation, ConceptsI've been busy with mundane parts of the nlp system recently. In the past week, I rewrote about 90 percent of the word recognizer and grammar parser. The new word recognition allows extended forms of words (eg. run -> runner -> <span class="blsp-spelling-error" id="SPELLING_ERROR_0">runneresque</span>) and irregular verbs (<span class="blsp-spelling-error" id="SPELLING_ERROR_1">eg</span>. go, went, gone). Of course, just because the system can recognize words like <span class="blsp-spelling-error" id="SPELLING_ERROR_2">filelike</span> doesn't mean it can assign meaning to them, aside from the rather <span class="blsp-spelling-corrected" id="SPELLING_ERROR_3">vague</span> "has some properties a file has." Of course, that's all you or I get as well; it's an evocative word, used to convey a starting point rather than to nail down specific properties. Computationally, perhaps it could be used for something like linking a new concept to nod in an existing conceptual graph. I'll see how that can work as I continue to research and/or reinvent and/or borrow wheels.<br /><br />The upgrade to the grammar parser now recognizes as many different tenses, aspects, voices, and persons as I've found to exist so far, including some I'm somewhat dubious about. Is future perfect continuous passive ("will have been being eaten") for real? It may just be PageRank, but <span class="blsp-spelling-error" id="SPELLING_ERROR_4">google's</span> only showing grammar sites for at least the first 50 hits for "<a href="http://www.google.com/search?q=%22will+have+been+being%22">will have been being</a>".<br /><br />So now I'm back to where I thought I was two weeks ago, ready to start working on a new knowledge representation. And that brings me to this sentence:<br /><br />"Alice believed Bob lied."<br /><br />Pulling this apart, there's at least 6 concepts introduced here, each <span class="blsp-spelling-error" id="SPELLING_ERROR_5">pronounable</span> in the next sentence:<br /><br />C1: the act of lying. "It's something we've all done."<br />C2: Bob. "He's been known to prevaricate."<br />C3: the event of Bob lying, in the past. "It's happened before."<br />C4: the act of (or quality of) belief in C3. "It's true of Eve as well."<br />C5: Alice. "She's not quick to trust."<br />C6: Alice holding a belief in C3. "It's because of their past."<br /><br />This has been bugging me for the past week and a half or so. How many of those are <span class="blsp-spelling-corrected" id="SPELLING_ERROR_6">conceived</span> on first reading? C1 and C4 specifically: they're the hardest to <span class="blsp-spelling-error" id="SPELLING_ERROR_7">pronounize</span> in a non awkward way. Do the pronouns force a reevaluation of the sentence when the other four don't fit the pronoun?<br /><br />I've been cowardly and not calling shots for a while, so nothing to report there outside of the progress mentioned above. I've got just one called shot for the next week: research in the area of knowledge representation.Adam Heckhttp://www.blogger.com/profile/00716800125148427529noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-42506610483188309262008-11-13T01:14:00.003-06:002008-11-13T01:28:38.138-06:00Makefile , Blink , and Software Controlled ButtonsAs promised, another update on the glorious piano project.<br /><br />This week has mostly been about getting a good solid foundation for development. After some time, I managed to make my first Makefile specifically for the Atmega16 and my avr-toolchain. I also managed to test it both on my JTAG programmer, as well as Sam's STK500v2 which I'm still in possession of. <br /><br />Additionally, I spent a good deal of time trying to get a software controlled switch to work. Getting the code to compile and upload to the Atmega was simplified with my Makefile, for sure, but for some reason the silly microcontroller was resetting on me. The data sheet didn't seem to provide much help [I went through all of the RESETs listed, to no avail]. Sam suggested I research the internal pull-up resistors, but they seemed to hold the current around +3V, and also produce the same intermittent reset problem. I finally said enough was enough and decided to do external pull-up resistors. If you are interested, here is a site which shows the basic diagram of how to put a switch into a Microcontroller: http://www.micahcarrick.com/05-15-2006/avr-tutorial-switch-debounce.html . <br /><br />I've uploaded my sample code onto my website for now. You can find all of the available warez under http://brandon.bagwellonline.com/piano . Currently, you will find a simple "blink" program, a "swbutton" [which has a software-controlled button listed], the Makefile, and eventually an image of my JTAG programming breadboard. Hopefully, I will add more interesting pics as they become available, but with were the project is at the moment, all the fun will exist in the world of C, Assembly, and my head.<br /><br />Updates will be coming, though they will be slower since the end of the year is a busy time for me at work [everyone else is burning their vacation time]. Besides, I'm still catching up on Doctor Who and Business Week. <br /><br />More next time,<br /><br />BrandonBrandon Bagwellhttp://www.blogger.com/profile/07241811394960939097noreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-85610505816137019042008-11-12T15:30:00.005-06:002008-11-12T17:47:05.675-06:00Livescribe Pulse Modem Hack: The Fourier TransformSo we have a rough idea what the frequency domain looks like; now we need some way of actually transforming data in the time domain (raw from the microphone) into frequency domain data. We'll do that through the creative application of <span style="font-style: italic;">interference.</span><br /><br />For this trick to work, we must remember that the average value of a sinusoid is zero --- half the wave is positive, half the wave is negative, and it all cancels out nicely.<br /><br />The other thing we need to know is how sinusoids multiply. So imagine a sinusoid, plodding along; a nice, slow wave with a long wavelength. Now imagine a fast, short wave sinusoid right on top of it. For each point along the x-axis of our imaginary graph, multiply the value of the slow wave with the value of the fast wave; and take care --- I said <span style="font-style: italic;">multiply</span>, not add.<br /><br />If your imagination is in smooth working order, you might piece together that the result is a periodic, oscillating wave. If your imagination is exceptionally good, you might even be able to notice that this curve is made up of two summed sinusoidal components. Truth be told, my imagination didn't hold up to the strain --- now I've got to find a new one. I recommend <a href="http://www.e-tutor.com/et2/graphing">this</a> for when your function imagination breaks down.<br /><br />(In the meantime, we can <a href="http://crca.ucsd.edu/%7Emsp/techniques/latest/book-html/node77.html">examine a little math </a>and discover that the two components are, in fact, sine waves whose frequencies are the sum of our original two sine waves and their difference, respectively.)<br /><br />But regardless of what the components are, they are sinusoidal --- and we already said that the average value of a sine is zero.<br /><br />What happens, though, if we take two <span style="font-style: italic;">identical</span> sine waves, and multiply them? Every place that one is positive, the other is positive as well; a positive times a positive is another positive... and every place one is negative, the other is as well; negative times negative is also positive.<br /><br />All of a sudden the average value <span style="font-style: italic;">is no longer zero!</span><br /><br />More exciting still, the trick still works even when we use a sum of multiple sinusoids for our first wave --- if the sinusoid we're multiplying by is exactly the same frequency as one of the components of our first wave, then the average value of the product is non-zero --- and that value is proportional to the amplitude of the component wave. We've found a way to pick a single sine wave out of a sum of them! Our transform! Right?<br /><br />There's an insidious evil lurking behind this joy.<br /><br />Notice what happens when our two waves fall ninety degrees out of phase, so that the peaks of one wave occur simultaneous to the zeros of the other. When we multiply, BAM. another simple sine wave. That's no help --- its average is still zero. As it turns out, the average value of the product of same-frequency sines is not simply proportional to the amplitude of the original wave; it's proportional to the amplitude <span style="font-style: italic;">and phase shift</span>. Shoot.<br /><br />There is one hope, however: cosine. Cosine's <span style="font-style: italic;">already </span>ninety degrees out of phase with sine, right? So whenever multiplying by a sine wave results in a false negative, multiplying by a cosine will get a full-strength output.<br /><br />And sure enough, in combination, multiplying by sine, separately multiplying by cosine, and then adding the two results, negates the phase-based part of the new wave. Loverly. Here, we've invented the full form of the Fourier Transform (for that is indeed what it is): The amplitude of a given frequency component of a wave is equal to the average of the sum of a unit cosine at the given frequency times the original wave times a unit sine at the given frequency times the original wave.<br /><br />That's it --- easy as pie, right?<br /><br /><span style="font-size:78%;"><br />Well, no, actually. Nowadays, no one uses that kind of notation --- we transform everything into the complex domain before we even begin. Even worse, there are huge pitfalls as soon as you make the whole thing digital --- when you no longer have smooth curves but individual samples the whole mess gets much more involved, plus there's the issue of efficiency; the method we used is about as fast as a mole on a paddleboat. It can't even reach the pedals, poor thing.<br /></span><br /><br />The practical application of all this comes right back to the Livescribe pulse. You remember that, right? All this has been about that. What we have now is a way to determine which frequency dominates a given audio sample. By making the pen play individual, pre-chosen frequencies, we can send data from the pen's speaker, through the PC microphone, and then decode the sounds back into labeled frequencies. Peachy. Now all we need is a way to encode data as a list of frequencies, and we're all set!<br /><br />That will be the topic of my next post, where, with luck, I will be able to declare success in sending data from the pen to my PC <span style="font-style: italic;">without</span> the use of Livescribe's desktop software.<br /><br />So stay tuned.Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-91001108783705613242008-11-06T23:20:00.003-06:002008-11-12T17:34:24.239-06:00No Hackjam 11.5.08No 11.5 hack jam; physical conditions were unfavorable (torrential rain).<br /><br />I succeeded in all my calls for last week.<br /><br />This week:<br /><ul><li>a post explaining the fourier transform, and how to use it.</li><li>the first bit actually transmitted from pen to computer by sound</li><li>another 10000 words of novel<br /></li></ul>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4024934086395647348.post-35423429331941386472008-11-03T23:34:00.003-06:002008-11-12T17:34:46.149-06:00NLP: Extracting Meaning from Noun PhrasesToday we'll look at one way to build up a representation of noun phrases as logical statements (see the <a href="http://hackjam.blogspot.com/2008/10/im-going-to-start-series-of-detailed.html">first post</a> for an introduction to the problem space we're working in). Once again, I'll be using Haskell code derived from my current project to demonstrate exactly what I mean. One thing that has become more and more apparent to me as I progress is that this kind of representation of the meaning of sentences is the wrong way to go. As I describe the structure I've been using, we'll take a look at some concepts that are difficult to represent in ways that don't depend on the english meaning of predicates themselves.<br /><pre><br />> module HackJamNLP2 where<br /></pre><br />First, we need to revisit and expand our grammar somewhat. This is still a simplified grammar relative to English taken as a whole.<br /><pre><br />> data NounPhrase = ANoun Word<br />> | APronoun Word<br />> | Name Word<br />> | AdjectivesNoun [Word] Word<br />> | NPRelClause NounPhrase RelativeClause<br /><br />> data RelativeClause = RelativeClause Word VerbPhrase<br /></pre><br />A quick grammar refresher. Relative clauses are a kind of extra, descriptive, verb phrase. In the sentence, "He who smelt it, dealt it," the relative clause "who smelt it" modifies he.<br /><pre><br />> data PartOfSpeech = Noun | Verb | Adjective | Article | Pronoun<br />> | Adverb | QueryWord | Unknown<br />> deriving Eq<br /></pre><br />We're going to classify the words who what where why when and how as query words. In this naive system, the presense of a query word is going to set off the whole sentence as a question. So this system will flag "That's not how you do it," as a query. This is not a fatal flaw, but requires a bit of analysis to get around.<br /><br />Now let's update our logical notation.<br /><pre><br />> data LogicSentence = Atom ID [Term]<br />> | And LogicSentence LogicSentence<br />> | Implies LogicSentence LogicSentence<br />> | ForAll Term LogicSentence<br />> | Exists Term LogicSentence<br />> | MemberOf Term Term<br />> deriving Show<br />><br />> data Term = Variable ID<br />> | Set [Term]<br />> | HigherOrder LogicSentence<br />> deriving Show<br /></pre><br />From the definitions we used last time, we're adding some elements of higher order logic: sets and higher order terms. (Sets were in the last post but not used.) A number of concepts are much more natural to express in sets, and higher order terms are used sparingly to store meta information to pass on to a higher module, rather than passing around an extra structure to store intent, etc.<br /><br />One more thing before we get into the meat of this post. Let's define a couple shorthand notations for patterns that will show up a couple of times.<br /><pre><br />> x = Variable "x"<br />> inContext = Atom "in-context" [x]<br /><br />> aSetWhere sent = let s = Variable "s" in<br />> Exists s (ForAll x ((x `MemberOf` s) `Implies` sent))<br /></pre><br />aSetWhere defines a set where all it's members satisfy a given sentence.<br /><br />Throughout convertNounPhrase, which we are about to (re)define, the variable "x" will represent the current noun phrase. We can avoid clashes by being carefull to substitute variables whenever we add two noun phrases together. We'll do that in combineNVSents, another function from last time that we'll expand in just a bit, and we'll use that function in a general way anytime we're combining sentences.<br /><br />The first important change is that our convertNounPhrase will now return a list of LogicSentences, each representing a /possible/ interpretation of the given grammar parse.<br /><pre><br />> convertNounPhrase :: NounPhrase -> [LogicSentence]<br />> convertNounPhrase (Name name)<br />> = [Exists x (Atom ("called-" ++ wordString name) [x])]<br /></pre><br />The conversion of Names is unchanged from last time, except for wrapping the result inside a list. Something I didn't point out last time was the awkwardness here in mapping, say, "Bob" to "Ex called-Bob(x)". What this does is put information inside the name of the object /inside/ the name of the predicate. Unfortunately, there's no where else to put it. My first system used a Const type of Term, but that doesn't scale to any system where two different objects have the same name.<br /><pre><br />> convertNounPhrase (ANoun n)<br />> | partOfSpeech n == QueryWord<br />> = [Atom "speaker-asking"<br />> [HigherOrder (ForAll x baseSentence)]]<br />> | isPlural n = [ForAll x baseSentence, aSetWhere baseSentence]<br />> | otherwise = [Exists x baseSentence,<br />> ForAll x baseSentence,<br />> aSetWhere baseSentence]<br />> where baseSentence = Atom (wordString n) [x]<br /></pre><br />Here's the big reason why Higher order terms were added; it's much more elegant to state the meaning of a question to be "speaker-asking(q)" where q is a sentence describing what the question should answer, Jeopardy style, than to avoid higher oder terms and pass another parameter around all the functions.<br /><br />The case of a plural noun brings up our first ambiguous meaning. So what does a word like "potatoes" refer to? All potates, or some? Compare the sentences "Potatoes come from the ground," and "Bob had potatoes for breakfast." It's impossible to tell the meaning of "potatoes" without context, so all we can do here is shrug and let something downstream try to disambiguate the meanings.<br /><br />The last case is a bit odd. I haven't been able to come up with any sentence where it makes sense to use a sigular noun without an article outside of gems like "I can has cheeseburger?" Hopefully our parser throws out parses with this form when more correct parses are available, but if we are asked to convert the NounPhrase, we should do our best. Unfortunately in this case, our best is to throw all the possibilities out there.<br /><pre><br />> convertNounPhrase (APronoun n)<br />> = case wordString n of<br />> "I" -> [Exists x (Atom "speaker" [x])]<br />> "you" -> [Exists x (Atom "audience" [x])]<br />> otherwise -> [Exists x inContext]<br /></pre><br />Pronouns are the same as last time, just wrapped in lists. I'm still truncating this for brevity, but you can see here a good case for adding the meaning of at least some words into the Word type itself. We could define a "meaningOf" field for the Word type and use that instead of all these Atom clauses. This also allows an agent to modify the results it gets from this module by modifying its dictionary, rather than having to rewrite meanings built in here.<br /><br />And if we extend our definition of words to include the occasional phrase like "on fire", we can easily have the meanings of "on fire" and "aflame" be the same without any special cases.<br /><pre><br />> convertNounPhrase (AdjectivesNoun (adj:adjs) noun)<br />> | isThe adj && isPlural noun<br />> = [ForAll x (inContext `And` (baseSentence adjs noun)),<br />> aSetWhere (inContext `And` (baseSentence adjs noun))]<br />> | isA adj && isPlural noun<br />> = []<br />> | isPlural noun = [ForAll x (baseSentence (adj:adjs) noun),<br />> aSetWhere (baseSentence (adj:adjs) noun)]<br />> | isThe adj = [Exists x (inContext `And` (baseSentence adjs noun))]<br />> | isA adj = [ForAll x (baseSentence adjs noun),<br />> Exists x (baseSentence adjs noun)]<br />> | otherwise = [Exists x (baseSentence (adj:adjs) noun)]<br />> where<br />> isThe adj = wordString adj == "the"<br />> isA adj = wordString adj == "a" || wordString adj == "an"<br />> baseSentence [] n<br />> = Atom (wordString n) [x]<br />> baseSentence (adj:adjs) n<br />> = Atom (wordString adj) [x] `And` (baseSentence adjs n)<br /></pre><br />I've broken an adjective phrase into six different cases based on the article, if any, it begins with and the plurality of the noun. You can see that we ignore phrases like "a potatoes." Above I argued that we should try to find a meaning for anything we get, but here we've got contradictory indicators about the plurality of the term rather than some grammar abuse.<br /><br />One other part that was suprising to me was the seemingly contradictory interpretations of singular nouns preceeded by a or an. The first case is a sentence like "A book is written by an author," where the intent is to refer to all books through the idea of a book-ness. The second case is the intuitive one: "A book is misssing."<br /><br />You can also see that adjectives are treated the same way as nouns: as atomic sentences. "A big ant" becomes "big(x) & ant(x)," which is problematic. Through And-Elimination, we get "big(x)"; this ant is no longer big for an ant, it is just /big/. We could introduce big-relative-to-ants(x), or possibly "Ey average-ant(y) & big-relative-to(x, y)," neither of which is particularly appealing. It gets worse however. From the <a href="http://www.ics.mq.edu.au/%7Eelena/AkhmDrasALTA07.pdf">Akhmatova</a> paper I mentioned in my last progress posting: take the sentence "The gastronomic capital of France is Lyon." And-Elimination (and a proper interpretation of the rest of the sentence) will leave you with "The capital of France is Lyon." So adjectives are difficult to shoehorn in to logic like this, regardless of whether they are limiting or modifying the base noun.<br /><pre><br />> convertNounPhrase (NPRelClause np (RelativeClause word vp))<br />> = [combineNVSents nSent (vSent (subjectOf nSent))<br />> | nSent <- convertNounPhrase np, > vSent <- convertVerbPhrase vp] </pre><br />Moving on, the conversion of relative clauses is fairly straightforward, funny notation notwithstanding. This funny looking structure is the one bit of Haskell I decided to sneak in here. It's a list comprehension, and it's best explained via a contrived example. Let's say you wanted a list of strings that consisted of all possible combinations of a set of prefixes and suffixes. In Haskell, you could say:<br /><pre><br />> contrived = [ prefix ++ suffix | prefix <- ["un", "im", "non"], > suffix <- ["bad", "good", "ugly"] ] </pre><br />This creates a list of nine strings. Now compare that with definition for relative clauses above, and you can see that we are making all possible combinations of noun and verb phrases we can muster. (The definition of convertVerbPhrase from the last post returned only a single LogicSentence; here we're using one modified to return a list of Sentences.)<br /><br />That's it for this post. There are, of course, more types of noun phrases, but the pattern is the same for them: determine the proper representation in your scheme and add a case to convertNounPhrase to handle it. Verb phrases are trickier, and I hope to get to them soon.<br /><br />I'm including below the handful of defintions that were reused from last time, in case you want to refer to them (it also makes this post compile as well!). This includes the modified convertVerbPhrase and a new convertSentence that deals with convertNounPhrase and convertVerbPhrase returning lists. It should look familiar after the last example.<br /><br />=====<br /><pre><br />> data VerbPhrase = AVerb Word<br /><br />> data Word = Word {<br />> wordString :: String,<br />> partOfSpeech :: PartOfSpeech,<br />> isPlural :: Bool<br />> }<br /><br />><br />> type ID = String<br /><br />> convertVerbPhrase :: VerbPhrase -> [Term -> LogicSentence]<br />> convertVerbPhrase (AVerb v) = [\subject -> Atom (wordString v) [subject]]<br /><br />> subjectOf :: LogicSentence -> Term<br />> subjectOf (ForAll t _) = t<br />> subjectOf (Exists t _) = t<br /><br />> combineNVSents :: LogicSentence -> LogicSentence -> LogicSentence<br />> combineNVSents (ForAll t npDescription) vpDescription<br />> = ForAll t (npDescription `Implies` vpDescription)<br />> combineNVSents (Exists t npDescription) vpDescription<br />> = Exists t (npDescription `And` vpDescription)<br /></pre>Adam Heckhttp://www.blogger.com/profile/00716800125148427529noreply@blogger.com1tag:blogger.com,1999:blog-4024934086395647348.post-33872790547043381512008-10-31T22:54:00.002-05:002008-10-31T23:26:50.448-05:00GreetingsThis is my first blog post to this, or any other blog... so please bear with me as I gather up steam and learn the new format.<br /><br />For those of you who don't know me, I'm Brandon. Hello! I know there isn't much listed on my current project, so here is generally the gist... we got an old upright Lexington-brand piano free from some nice people who were cleaning their basement. The guys here were interested in getting a piano for the foyer, but didn't want to spend a lot [read "any"] money. As such, the piano is what you expect from a free piano. The word "totaled" comes to mind [and that of the piano tuner I had take a look at it].<br /><br />To make a long story short, being the group full of steam-punk, tinkering, tech heads that only the readers of this blog might enjoy, we decided to turn this 1940's upright piano into an electric keyboard. Perfect! Keeps a tune forever and maybe does other nice nifty things as well.<br /><br />Having never messed with embedded systems [or electronics even], it made process somewhat scary. However, it still had to be easier [and cheaper] than rebuilding normally. I got together with Sam [who is Fantastic in only ways Dr. Who can describe] and plotted the course. We purchased the following items:<br /><br />* 100 x Small Raised Tactile Switches<br />* 3 x Atmega16 Microcontrollers<br />* 3 x 5 Volt VRMs<br />* 1 x JTAG-ICE-MKI programmer for said Atmegas<br />* 1 x "magical" breakout board from Sparkfun [SKU: BOB-00718 ] to turn signals into computer based serial.<br />* 1 x Jumperkit, including Capacitors, resistors, and some breadboards... various other sundry electronic components [Total cost so far, < $150 US].<br /><br />The general goal is to have the microcontroller interpret the incoming signals from the various buttons, encode them into a long byte stream, send it over to a laptop running ALSA hidden in the piano cabinent and PRESTO! Electronic piano!<br /><br />As to installing the AVR Toolkit, I know that Sam mentioned how frustrating some things were. I am running Mandriva Linux 2008 on my devel-machine and installed the following packages to get everything working AOK:<br /><br />avrdude<br />avr-libc-1.6.2<br />binutils-2.19.50<br />ddd [graphical gdb front-end, kinda nice since I'm not used to gdb]<br />gcc-4.3.2 for the AVR [you'll use --target=avr]<br />gdb-6.8 [for handyness]<br />gmp-4.2.2<br />mpfr-2.3.0<br />simulavr-0.1.2.5<br /><br />Those are all of the packages that you truly need [plus their sub-dependencies, such as a YACC or a BISON... also a neat one called "m4" for gcc.<br /><br />With those installed, you should be good to go. However, I do want to draw this post to a close as otherwise it will be so long you might loose interest.<br /><br />I will post my Makefile and other "piano-warez" on my website or this blog for those who are interested. The Makefile is very basic, so remember, just because you graduate with a BS in CS does not make you a programmer. <br /><br />I will also post on some of my other projects as they happen. <br /><br />Regards,<br /><br />Brandon BagwellBrandon Bagwellhttp://www.blogger.com/profile/07241811394960939097noreply@blogger.com0