Hack Jam Log Book

7/28

2011-08-01T07:50:00.002-05:00

Hackjam was pretty fun this 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.

We also played with TheGun.exe 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.

Movie GUIs

2011-07-01T18:48:00.007-05:00

I went to Hackjam the first time in who knows how long and it was nice to see everyone again.

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.

My first step is to implement a clock applet resembling the screenshot from Darkstar. 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.

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.

I already have some experience with SDL so I am going to bark up that tree.

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!

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.

I am also listening to Voltaire right now. Background music, not advice.

Cheers!

EDIT: here is a great link to what I have accomplished thus far https://jonathanstone.homeip.net/darkstar.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.

silly shell tricks

2010-12-12T13:34:00.003-06:00

You can use 'tac' to implement a stack.

Red comes from stdin, black is stdout:

Instead of doing `factor`:

$ factor

33: 3 11

19: 19

27: 3 3 3

You can do this:

$ tac | factor

394

666

666: 2 3 3 37

19: 19

87: 3 29

394: 2 197

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:

$ echo "394 87 19 666" | factor | tac

666: 2 3 3 37

19: 19

87: 3 29

394: 2 197

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.

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):

$ echo "394 87 19 666" | factor | tac | rev

73 3 3 2 :666

91 :91

92 3 :78

791 2 :493

Clearly nonsensical. These filters are transitive however!

$ echo "394 87 19 666" | factor | tac | rev | tac | rev

394: 2 197

87: 3 29

19: 19

666: 2 3 3 37

and

$ echo "394 87 19 666" | factor | tac | rev | rev | tac

394: 2 197

87: 3 29

19: 19

666: 2 3 3 37

and

$ echo "394 87 19 666" | factor | tac | tac | rev | rev

394: 2 197

87: 3 29

19: 19

666: 2 3 3 37

and

$ echo "394 87 19 666" | factor | rev | tac | tac | rev

394: 2 197

87: 3 29

19: 19

666: 2 3 3 37

and

$ echo "394 87 19 666" | factor | rev | rev | tac | tac

394: 2 197

87: 3 29

19: 19

666: 2 3 3 37

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.

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: http://piratejon.com:8080/mirror.

sockets

2010-10-10T12:00:00.003-05:00

Hack Jam Log Book deserves a new post.

I have not been to hackjam in a while due to a great personal inconvenience in the tradeoff between space and time.

This has not limited my hacking however.

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.

There is no protocol.

This is not a lot different from telnet however it has even fewer features and capabilities.

It does however illustrate basic blocking sockets and select() in C.

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.

Code at http://jonathanstone.homeip.net:8080/chat

Direction: ncurses to solve dumb text entry problems, full Win32 support, and openssl for point-to-point encryption.

A Painted Blog

2010-03-29T17:54:00.002-05:00

I'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/

xkb and xmodmap: a big mess

2009-08-09T09:31:00.004-05:00

So I've convinced myself to try a new keyboard mapping; arensito is currently the only word that I can type quickly and accurately.

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.

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.

2. Speaking of xkb and evil, Mod_switch won't always work unless xkb is off. So in xorg.conf:


Section "InputDevice"
Identifier  "Keyboard0"
Driver      "keyboard"
Option      "CoreKeyboard"
Option      "XkbDisable" "true"
#    Option        "XkbRules" "xorg"
#    Option        "XkbModel" "latitude"
#    Option        "XkbLayout" "us"
EndSection

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:

export XKB_DISABLE=1

3. Edit .Xmodmap:


keycode 44 = j J plus
keycode 0x41 = Mode_switch
clear mod3
add mod3 = Mode_switch

(note that I use the spacebar as my Mode_switch; chances are you want someting different)

Mode_switch uses the third and fourth keysyms; 'j' and 'J' are the first and second, 'plus' is the third. space+j will return '+'.

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.

a lisp

2009-08-08T11:17:00.005-05:00

I'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.

I don't want a super-efficient language, or a minimal language, or a super-readable language. I want a language that is fun.

The most controversial way I can put it is probably also the best: there is a quote.

"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

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.

Clone of Existing Game with 3D Enhancement

2009-06-25T15:57:00.003-05:00

I have spent the past three HackJam sessions cloning the super-fun Flash game Boomshine, 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.

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.

I have never done 3D graphics before except in QBasic like ten years ago so this will be challenging and interesting.

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.

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.

Haskell -> Arc

2009-02-24T23:07:00.004-06:00

Lately, 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.

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.

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).

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.

Settling Down

2009-01-15T17:24:00.002-06:00

I 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, the AI Box game (careful with that box, son, there's a puma inside), writing a small RSS reader, and now, Functional Reactive Programming. FRP 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.

I'm dropping in to call a shot. For next week I'll have a simple FRP implementation of the Tron Lightbike game.

Merry Holidays, and Screen Capture Update

2008-12-27T00:55:00.009-06:00

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.

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.

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.

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.

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.

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:

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.
"checkerboard": the image will be divided checkerboard style into alternate squares, so that individual frames will appear as checkerboards, alternating background with foreground.
"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?

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.

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 n indicating whether the pixel should be present in frame n. 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.

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 :)

UPDATE: repository'd: http://piratejon.com/git?p=scrapture.git

Hack Jam: 3.12.08

2008-12-09T22:04:00.004-06:00

Topics of discussion: AI, NLP, Cantaloupe, Primes, and the possibility of being 4/9ths Asian.

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.

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.

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.

This brought to mind an interesting challenge --- writing code with write-or-die...

Breaking Screen Captures

2008-12-01T02:10:00.004-06:00

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.

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.

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.

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.

Write or Die: Now on Emacs!

2008-11-28T16:16:00.002-06:00

For those of you that write, or wish you wrote, or otherwise procrastinate while performing text-based activities, try out write-or-die. 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.

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.

Just paste the following into your init.el, and when the time comes, M-x write-or-die. When you have accomplished your goal, M-x no-more-die, and you're set.


(let ( (write-or-die-time ())
      (write-or-die-init ()) )

(defun write-or-die ()
 (interactive)
 (setf write-or-die-init (run-with-idle-timer 3 t 'w-or-die)))

(defun w-or-die ()
 (interactive)
 (kill-region (point-max) (- (point-max) 10))
 (setf write-or-die-time (run-with-idle-timer
            (time-add (current-idle-time)
         (seconds-to-time 3))
            ()
      'w-or-die)))

(defun no-more-die ()
      (interactive)   
      (cancel-timer write-or-die-init) 
      (cancel-timer write-or-die-time))

)

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.

MythTV

2008-11-26T20:19:00.002-06:00

For a quick breather away from the piano, I decided to set up a MythTV box.

For those of you who are unfamiliar, MythTV 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.

First of all, for those who are interested in different types of cards out there, here are the different terms that get thrown around:

* 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.
* ATSC = new, hip digital broadcast TV [officially taking off Feb 2009]
* 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.
* DVB = Digital Video Broadcast. DVB-T is terrestial, DVB-C is cable, DVB-S is satellite.

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:

http://www.mythtv.org/docs/mythtv-HOWTO.html#toc5 [Installing MythTV]
http://www.mythtv.org/wiki/index.php/Category:Video_capture_cards [Capture Cards]

There are a lot of pre-requisites, including some that aren't listed. The big one is of "Qt3MySQL" [why they don't list it as an actual pre-req, I don't know]. The ones listed in the tutorial include:
mysql, gcc, freetype2-devel, xorg-xserver-devel, qt-devel and lame.
Also required:
qmake, Xv, QT3MySQL, mplayer, ffmpeg, transcode, many others

Pro Tip!
If while making a program you get lines that show...
/usr/bin/ld: cannot find -lMERPMERP
collect2: ld returned 1 exit status

Do a search in your package manager for MERPMERP. Many times, that will resolve it and you can resume MAKEing your program.

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.

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.

As a last note, MythPlugins is worth installing at least for MythArchive. Unless you want to purchase a nice JBOD system for harddrives, install it and play around with the "Archive" [burns recorded shows to DVD]!

As I hear more about cards, plug-ins and more, I'll keep you posted.

Regards,

Brandon

Postscript Posters

2008-11-21T14:56:00.004-06:00

One 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?

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.

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
%%BoundingBox: x1 y1 x2 y2
So, you specify the lower-left and upper-right corners of the smallest rectangle that includes everything you want to be in the image.

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.

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:

.15 .15 scale

caused the graphics to follow to be drawn at the fifteen percent required to get them on the page.

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!

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.

Making posters is pretty cool and I think you should try it too.

Livescribe Pulse Hacking: The buisness already!

2008-11-18T19:58:00.004-06:00

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.

So now, it happens! Data is sent from the pen to my laptop, running Linux, via vibrating air! Doesn't it just put you at the edge of your seat?

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 bits per second, mind you. So it took something like a quarter of a minute just to send those two words.

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.

But what is currently killing me is (I believe) the period between 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.

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 playing. It is, uh ... not zero. And that of course makes the the whole in-between-tone period even HARDER to identify and cope with.

Short note. Hopefully have more time next week to discuss possible fixes for all these faults.

Word Mangling, Verb Conjugation, Concepts

2008-11-17T00:19:00.004-06:00

I'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 -> runneresque) and irregular verbs (eg. go, went, gone). Of course, just because the system can recognize words like filelike doesn't mean it can assign meaning to them, aside from the rather vague "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.

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 google's only showing grammar sites for at least the first 50 hits for "will have been being".

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:

"Alice believed Bob lied."

Pulling this apart, there's at least 6 concepts introduced here, each pronounable in the next sentence:

C1: the act of lying. "It's something we've all done."
C2: Bob. "He's been known to prevaricate."
C3: the event of Bob lying, in the past. "It's happened before."
C4: the act of (or quality of) belief in C3. "It's true of Eve as well."
C5: Alice. "She's not quick to trust."
C6: Alice holding a belief in C3. "It's because of their past."

This has been bugging me for the past week and a half or so. How many of those are conceived on first reading? C1 and C4 specifically: they're the hardest to pronounize in a non awkward way. Do the pronouns force a reevaluation of the sentence when the other four don't fit the pronoun?

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.

Makefile , Blink , and Software Controlled Buttons

2008-11-13T01:14:00.003-06:00

As promised, another update on the glorious piano project.

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.

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 .

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.

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.

More next time,

Brandon

Livescribe Pulse Modem Hack: The Fourier Transform

2008-11-12T15:30:00.005-06:00

So 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 interference.

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.

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 multiply, not add.

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 this for when your function imagination breaks down.

(In the meantime, we can examine a little math 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.)

But regardless of what the components are, they are sinusoidal --- and we already said that the average value of a sine is zero.

What happens, though, if we take two identical 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.

All of a sudden the average value is no longer zero!

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?

There's an insidious evil lurking behind this joy.

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 and phase shift. Shoot.

There is one hope, however: cosine. Cosine's already 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.

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.

That's it --- easy as pie, right?

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.

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!

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 without the use of Livescribe's desktop software.

So stay tuned.

No Hackjam 11.5.08

2008-11-06T23:20:00.003-06:00

No 11.5 hack jam; physical conditions were unfavorable (torrential rain).

I succeeded in all my calls for last week.

This week:

a post explaining the fourier transform, and how to use it.
the first bit actually transmitted from pen to computer by sound
another 10000 words of novel

NLP: Extracting Meaning from Noun Phrases

2008-11-03T23:34:00.003-06:00

Today we'll look at one way to build up a representation of noun phrases as logical statements (see the first post 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.


> module HackJamNLP2 where

First, we need to revisit and expand our grammar somewhat. This is still a simplified grammar relative to English taken as a whole.


> data NounPhrase     = ANoun Word
>                     | APronoun Word
>                     | Name Word
>                     | AdjectivesNoun [Word] Word
>                     | NPRelClause NounPhrase RelativeClause

> data RelativeClause = RelativeClause Word VerbPhrase

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.


> data PartOfSpeech = Noun | Verb | Adjective | Article | Pronoun
>                   | Adverb | QueryWord | Unknown
>                     deriving Eq

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.

Now let's update our logical notation.


> data LogicSentence = Atom ID [Term]
>                    | And LogicSentence LogicSentence
>                    | Implies LogicSentence LogicSentence
>                    | ForAll Term LogicSentence
>                    | Exists Term LogicSentence
>                    | MemberOf Term Term
>                      deriving Show
>
> data Term = Variable ID
>           | Set [Term]
>           | HigherOrder LogicSentence
>             deriving Show

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.

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.


> x                   = Variable "x"
> inContext           = Atom "in-context" [x]

> aSetWhere sent      = let s = Variable "s" in
>                       Exists s (ForAll x ((x `MemberOf` s) `Implies` sent))

aSetWhere defines a set where all it's members satisfy a given sentence.

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.

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.


> convertNounPhrase     :: NounPhrase -> [LogicSentence]
> convertNounPhrase (Name name)
>                       = [Exists x (Atom ("called-" ++ wordString name) [x])]

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.


> convertNounPhrase (ANoun n)
>       | partOfSpeech n == QueryWord
>                       = [Atom "speaker-asking"
>                               [HigherOrder (ForAll x baseSentence)]]
>       | isPlural n    = [ForAll x baseSentence, aSetWhere baseSentence]
>       | otherwise     = [Exists x baseSentence,
>                          ForAll x baseSentence,
>                          aSetWhere baseSentence]
>   where baseSentence  = Atom (wordString n) [x]

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.

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.

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.


> convertNounPhrase (APronoun n)
>                       = case wordString n of
>                               "I"       -> [Exists x (Atom "speaker" [x])]
>                               "you"     -> [Exists x (Atom "audience" [x])]
>                               otherwise -> [Exists x inContext]

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.

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.


> convertNounPhrase (AdjectivesNoun (adj:adjs) noun)
>       | isThe adj && isPlural noun
>                       = [ForAll x (inContext `And` (baseSentence adjs noun)),
>                          aSetWhere (inContext `And` (baseSentence adjs noun))]
>       | isA adj && isPlural noun
>                       = []
>       | isPlural noun = [ForAll x (baseSentence (adj:adjs) noun),
>                          aSetWhere (baseSentence (adj:adjs) noun)]
>       | isThe adj     = [Exists x (inContext `And` (baseSentence adjs noun))]
>       | isA adj       = [ForAll x (baseSentence adjs noun),
>                          Exists x (baseSentence adjs noun)]
>       | otherwise     = [Exists x (baseSentence (adj:adjs) noun)]
>   where
>       isThe adj       = wordString adj == "the"
>       isA adj         = wordString adj == "a" || wordString adj == "an"
>       baseSentence [] n
>                       = Atom (wordString n) [x]
>       baseSentence (adj:adjs) n
>                       = Atom (wordString adj) [x] `And` (baseSentence adjs n)

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.

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."

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 Akhmatova 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.


> convertNounPhrase (NPRelClause np (RelativeClause word vp))
>                       = [combineNVSents nSent (vSent (subjectOf nSent))
>                                       | nSent <- convertNounPhrase np, >                                         vSent <- convertVerbPhrase vp]

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:


> contrived           = [ prefix ++ suffix | prefix <- ["un", "im", "non"], >                                            suffix <- ["bad", "good", "ugly"] ]

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.)

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.

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.

=====


> data VerbPhrase = AVerb Word

> data Word = Word {
>               wordString    :: String,
>               partOfSpeech  :: PartOfSpeech,
>               isPlural      :: Bool
>             }

>
> type ID = String

> convertVerbPhrase     :: VerbPhrase -> [Term -> LogicSentence]
> convertVerbPhrase (AVerb v) = [\subject -> Atom (wordString v) [subject]]

> subjectOf             :: LogicSentence -> Term
> subjectOf (ForAll t _) = t
> subjectOf (Exists t _) = t

> combineNVSents        :: LogicSentence -> LogicSentence -> LogicSentence
> combineNVSents (ForAll t npDescription) vpDescription
>                    = ForAll t (npDescription `Implies` vpDescription)
> combineNVSents (Exists t npDescription) vpDescription
>                    = Exists t (npDescription `And` vpDescription)

Greetings

2008-10-31T22:54:00.002-05:00

This 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.

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].

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.

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:

* 100 x Small Raised Tactile Switches
* 3 x Atmega16 Microcontrollers
* 3 x 5 Volt VRMs
* 1 x JTAG-ICE-MKI programmer for said Atmegas
* 1 x "magical" breakout board from Sparkfun [SKU: BOB-00718 ] to turn signals into computer based serial.
* 1 x Jumperkit, including Capacitors, resistors, and some breadboards... various other sundry electronic components [Total cost so far, < $150 US].

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!

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:

avrdude
avr-libc-1.6.2
binutils-2.19.50
ddd [graphical gdb front-end, kinda nice since I'm not used to gdb]
gcc-4.3.2 for the AVR [you'll use --target=avr]
gdb-6.8 [for handyness]
gmp-4.2.2
mpfr-2.3.0
simulavr-0.1.2.5

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.

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.

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.

I will also post on some of my other projects as they happen.

Regards,

Brandon Bagwell

Words about Language

2008-10-31T20:50:00.004-05:00

I've had a pretty productive week with regards to my NLP project; I added an implementation of backward chaining inference, so now I can start playing with interpreting context and unifying concepts. With that built, I'm more or less back up to where I was with my first system, only with a code base that still has room to grow. I can ask simple questions, and so long as the knowledge base is in the right state, get yes or I-don't-know answers. Unfortunately, my approach right now is so general that if I mention two facts about a specific thing, say, emacs, the system won't make the assumption that I'm not talking about two different things, both called emacs.

Which brings me to my next target, context and pronouns. Pronouns are obviously a problem for computers; if I say "Bob threw a brick at the window, and it shattered," what shattered? It's easy for us to say that the window shattered, but we get that from our knowledge of the world, not from any particular structure in the sentence. I could also say "Bob threw a vase at the wall, and it shattered," and this time, with the same structure, "it" now refers to the object being thrown, the vase.

We know this from one of two ways, and I'm not sure which. We either know that a vase or window can shatter, whereas a brick or wall is not likely to, or we visualize the event and our internal model predicts which object shatters. Neither is particularly easy for a computer; the latter has obvious computational problems, the former requires a search through potentially large amounts of data.

For my first crack at it, I'll be keeping a list of 'things' that have been in context, attempting to unify objects referred to by pronouns until I don't end up with a conflict. I'm planning on limiting the domain of 'things' that can be discussed to something small, like the nature of files, programs, and directories, in what I'm sure will be a vain attempt to limit the size of the knowledge base that this approach will require.

In other news, my posts on the comprehension module are still coming, but writing them keeps taking longer than I expect. Just when I get into the flow of writing, I notice something I'm doing wrong and have to go fix it.

I've read two papers in the past week. Modeling Semantic Containment and Exclusion in Natural Language Inference, MacCartney and Manning covers using natural logic for modeling the semantics of language, and the successes and problems they've found there. Recognizing Textual Entailment Via Atomic Propositions, Akhmatova and Molla describes an approach using traditional logic (like you saw in my Haskell-laden post).

Livescribe Pulse Hacking I: The Frequency Domain

2008-10-31T00:21:00.010-05:00

One of the frustrating things about the exciting livescribe pulse is it's inability to communicate with linux. Even through virtualization of a windows machine, you'll be lucky to get a working system.

Another is the fact that, while programs build with the livescribe pre-release SDK can save files to the pen, they cannot send those files to the desktop machine --- the only way to interact with program data is through the pen.

Well, I say pooh to that: "Pooh!"

Since I was first able to program my livescribe pulse (in a rude rendition of 'hello, world'), I've been scheming on how to communicate with the pen through hackish means. While reverse engineering the livescribe communications protocol would have been the correct way to do it, I feared it was, and is, beyond my means and motivation. I concentrated instead on the other two ways the pen has of communicating: the screen and the speaker.

My original plan had been to use light sensors, an AVR, and a program that would flash the pen's OLED display in order to send data back to the desktop computer. While this is plausible, the narrow bandwidth of the light produced by the OLED display makes it difficult to sense --- and the communication would always be one way. Besides, special hardware would be necessary, and that would make the potential user base tiny: linux-using livescribe owners who have the knowledge and hardware to program microcontrollers.

No, there must be a better way; so we turn to the speaker. Most computer owners have a microphone on hand; and communicating via tones is a tried and true method. My path is clear: create a livescribe modem!

In order to recieve information, the computer must be able not just to record the sounds coming from the pen, but to analyze them. To write software that can do that, we must have a firm understanding of the frequency domain. (Prerequisites note: If you don't have a firm understanding of the concepts frequency, wavelength, and sinusoidal graphs, it's time for a trip to wikipedia.

The central nugget of the matter goes like this: any continuous, periodic function can be represented as an infinite sum of sines and cosines.

Give that a minute to sink in; any function that is continuous --- not differentiable, just continuous --- and periodic --- but the length of the period can be as long as you like --- will do. Square waves, sawtooths, Bart Simpson's hair; any arbitrary waveform can be represented by a simple sum of sines and cosines.

Wow.

You may be worried about that word 'infinite' up there. Luckily, it turns out that we can approximate our function with some finite number k sines and cosines; and that each time we increase k, the approximation becomes more accurate.

Now let's take a moment to remember what the time domain, looks like. Imagine a signal coming from your microphone. It is a long string of numbers, and each number indicates a magnitude of sound at a single point in time (which is to say, the difference in pressure on the front and rear surfaces of the microphone pickup). If we were to graph the sound of someone whistling by using the time as the independent variable, and magnitude as the dependent, we'd see a lovely sine wave --- the archetypal image of sound, in the time domain.

But there is another way of plotting the same sound. We said that any curve --- no matter how complex our time domain curve might be --- can be represented by a sum of sines and cosines, right?

And, hold on to your hats, we only need 2 numbers to define a sine wave: the frequency of the wave, and the amplitude. So we have lots of data points enumerated by two real numbers? That sounds like a graph. And indeed it is. If we graph frequency as the independent variable and amplitude as the dependent, we have arrived at a graph of our sound in the frequency domain.

For those of you still having a little trouble visualizing, here's what the sound of me whistling looks like in the time domain:

And here's what it looks like in the frequency domain:

See that big sharp spike there around 800Hz? That is the primary frequency of the whistle (772Hz: a G5 that's a little flat). All the other stuff is the shower, the refrigerator, the computer fan, the traffic outside, the wind, and so on; but remember we're measuring in decibels, so they are whole orders of magnitude less in amplitude than the whistle.

Most of you are probably yelling at the screen by now, asking me how on earth we're supposed to find these numbers. Where do we get this sum of sinusoids if all we're given is the time domain information? The empty-words answer is "The fourier transform." To understand that answer, we're going to have to go in a journey --- one that I'll leave to my next post.

Hack Jam: 10.29.08

2008-10-30T18:03:00.005-05:00

,Topics of discussion: AVR, NLP, and MLB.

Brandon finally received all the parts for his electric piano conversion, so we set about getting his AVR toolchain and JTAG programmer working. We had a discussion of how messy the current binutils/avr-gcc/avr-libc combination is --- it was one of the worst source builds I have have ever had to perform. It took me more than a day on my machine --- and Brandon sped through the process in just 6 hours on his.

For those of you out there that are receiving that relished error "illegal opcode movw for mcu avr3", there is hope! My recommendations are:

Remove all traces of avr-binutils. Kill them dead. Remnants of the latest release of binutils will wreak havoc when you try to work either with bleeding edge snapshots or older versions.
Forget the latest releases --- go back several stable versions of both gcc and binutils, to at least January 2008, or even back into 2007. (Your other option is to get bleeding edge snapshots, but I did not have any more success with these than with the latest releases.)
Download all the avr-gcc and binutils patches you can find from the date of release of binutils and gcc that you downloaded to the date of the next stable version; attempt to apply all of them. Don't worry if some fail --- just push ahead.
For the actual configuring, I recommend reading this page.
Make and install binutils.
Make and install gcc (fingers crossed!)
Only upon the successful completion of avr-gcc's install should you even worry about avr-libc.

Note that these are only hints. I am not attempting to give a full overview of what works --- but you'll save many headaches if you start with these steps.

On calling my shots:

You may have noticed the lack of posts. Surprise! I failed to meet both drawing post calls
I did program my livescribe. penlets.com was a major help
I did get a relatively detailed outline ready for nanowrimo

Score: 2/4.

For next week:

A post on my evil plans for communicating with linux from my livescribe pulse.
The beginning of a nano novel. Huzzah!

Pluralities and Progress

2008-10-25T11:36:00.002-05:00

I've been wondering for a while about how to deal with the meaning of plural nouns. In my last post I treated them as referring to all things of a type, as in "The rm program deletes files". But they can also refer to a set of things of a type, as in "Bob deleted files." There's an implied "some" in that second sentence; we know that Bob didn't delete all files everywhere. The tense of the sentence or passage helps quite a bit for determining which interpretation is more probable, but that approach is not ironclad. Contrast "Bob deleted files," with "Bob deleted his files." "His files" is a smaller set of things, one that Bob could conceivably delete all of. Unfortunately, the knowledge of files, the act of deleting, and Bob that we can use to differentiate the two situations come from prior knowledge. I'm hoping to use logical inference for disambiguation like this, but at the moment, I'm not optimistic about the size of the knowledge base that will be necessary.

In other news, I've been working on this long enough now that I'm going to start reading the literature. I'm probably way overdue on this step, having so far only read through what Russell and Norvig had to say about this in their book.

I met both of my goals for last week, though my recognition of plurality is a bit crude. I'm intending to revisit how I'm representing my dictionary soon, so I'll make it less crude then.

For this week, my goals are:

Build a simple logical inference framework
Read two papers on AI
Continue the NLP series with interpretation of verb phrases.

Hackjam 10.22.08

2008-10-23T12:29:00.003-05:00

Discussion topics: puzzles, communication, form/content interrelationships, the livescribe pulse, Steven Wright, logic puzzles, cellular automata.

We had a lengthy conversation on how art and communication can work together, and how they can work against each other. We came to no conclusions, but I thought it might be interesting to talk a little about how I think about the form/content interrelationship, and why it's so important to me in art critique and analysis. I'll do it a bit jesuitically, because I think art criticism is too often left too open to opinion --- let's all share the same language, shall we?

For the sake of brevity and generality, I will refer to a work of art as an artifact. The artifact is the actual painting, sculpture, poem, novel... even performance art leaves behind a temporal artifact, which is the primary means of the audience experiencing the piece.

The audience is anyone who comes in contact with the artifact. Note that this is distinguished from the intended audience, which are the people the artist expects or desires to come in contact with the artifact.

The content is the change in the audience caused by contact with the artifact. That is a trickier definition than is often put forward. This definition does not discriminate based on what the content is --- only where it comes from. What is worth taking away from this definition is that content can with a single thought be cleaved from intended content, just as audience and intended audience are distinct. As critics we are as much, if not much more, concerned with the content as with the intended content.

Finally, the hardest one. Form is the thingness of a thing. The form of a painting is the color, line, texture, surface, and technique used to paint it. The form of a poem is the prosody, the rhyme, the aural, temporal, and visual texture of the artifact. The context of the work (where, when, and how the audience comes in contact with it) is also a formal aspect. When we say "That's well made" we're discussing the form.

The relationship between from and content is of the utmost importance to the creation of a successful artifact. To understand why, we need to look even closer at what content is --- and more importantly where content is. "[...] content is the change in the audience caused by contact with the artifact." Content only exists when the artifact comes in contact with the audience. Without an audience, content cannot exist. How does the audience know what to do? How do they know how they are supposed to change in order to create the proper content? There is no "audience instruction manual," is there? How can the artist tell the audience what to do when they don't even know who the audience is?

There is only one way for the artist to communicate with the audience --- through the artifact itself; through it's form.

Guernica communicates the anguish of the bombing through line, shape, color, size, and context. Without performing a complete critique of the work (which you could find by doing this), we can see why the form is so important by performing a heavy-handed thought experiment. Can you imagine a photorealistic color image of an unhappy horse, that was, say, 8" by 10"? Compare that to the screaming animal in the center of Guernica (keeping in mind that the whole painting is more than 25 feet long). Would the content be the same? Or does the rough and broken line of the mother and child, the broken and offset curve of the bull's horns, the impossible jagged edge of the fallen sword, do they accomplish something that a different form could not, despite having the same intended content?

The relationship between form and content is impossible difficult, almost invisible, and it is what makes art art.

On calling my shots:

Last week I did get a post for makerfaire, I did not complete my post on drawing, but I did get some work on it done. It will go up this week. Score: 1/2.

This week I call:

Successfully programming the livescribe pulse with my own program
Completing my rough nanowrimo outline
Completing last weeks drawing post and adding another

NLP: Grammar Trees to Logical Statements

2008-10-22T17:36:00.004-05:00

I'm going to start a series of detailed posts about the comprehension module. This is the section that translates a grammar tree into a logical statement. For this discussion, we'll be looking at a simplified version of my simplified version of English grammar. We'll expand our grammar in future posts. Since I've started this post, I've improved my approach in this area as well, so you'll be seeing the evolution of this code, with a couple weeks lag time.

It also gives me an opportunity to introduce a bit of Haskell. I'll introduce you to Haskell just enough to understand what I'm doing. If you want to learn it well enough to use it, I suggest one of these fine tutorials.


> module HackjamNLP where

This post is written in literate Haskell. The lines begining with ">" are source lines, everything else is a comment. You can copy this post to a file and load it into an interpreter if you like.


> data Sentence = Declarative NounPhrase VerbPhrase
>
> data NounPhrase = ANoun Word
>                 | APronoun Word
>                 | Name Word
>
> data VerbPhrase = AVerb Word

What I'm doing here is defining three new types, Sentence, NounPhrase, and VerbPhrase, each with one or more type constructors. So a Sentence can be constructed with Declarative, a NounPhrase with ANoun, AProunoun, or Name, and VerbPhrase with Verb. Everything after the type constructor's name are the types each constructor requires to build a value of that type. In other code, here's a rough equivalent to Sentence's Declarative constructor in a bastard Java-like:


: Sentence Declarative(NounPhrase np, VerbPhrase vp) { ... }

So type constructors are like functions that return values of a given type (but more useful, as we'll see later).


> data Word = Word {
>               wordString    :: String,
>               partOfSpeech  :: PartOfSpeech,
>               isPlural      :: Bool
>             }

Here we see another syntax for declaring a data type. It is common to name the constructor for a type the same thing as the type itself when there is only one constructor for that type. The :: can be read as "has type", so we can reason that a Word is made of wordString of type String, a partOfSpeech of type PartOfSpeech, and isPlural of type Bool. Each of these identifiers is a function that can be applied to a Word to get it's corresponding field.

You've probably noticed that Haskell is case sensitive. Actually, the upper/lower case convention I'm using isn't convention at all; It's required by syntax. All types and type constructors (and names of modules, but I'm not going there) are required to be uppercase, everything else is must be lowercase.


> data PartOfSpeech = Noun | Verb | Adjective | Article | Pronoun
>                   | Adverb | Unknown

One last definition. Here I'm enumerating the types of speech that I'm using. This is the same syntax as before, except none of these have any parameters, and I compacted the formatting.

Now I can build Sentences out of Strings, PartOfSpeeches, and Bools. As a quick example, let's quickly build a Sentence representing "I win.":


> iWin = Declarative (APronoun (Word "I" Pronoun False))
>                    (AVerb (Word "win" Verb False))

Tada.

Again, we're going to take for granted that some other nice module has generated these grammatical trees for us. We should only be concerned with converting them to logical statements. First, we define a representation of logical statements. This representation won't describe all logical statements; I've left out constructors that I won't be using here to keep things simple.


> data LogicSentence = Atom ID [Term]
>                    | And LogicSentence LogicSentence
>                    | Implies LogicSentence LogicSentence
>                    | ForAll Term LogicSentence
>                    | Exists Term LogicSentence
>                      deriving Show
>
> data Term = Variable ID
>           | Set [Term]
>             deriving Show
>
> type ID = String

The [] brackets in [Term] indicate a list of that type, and the last line defines ID to be a type equivilant to a String.

The deriving statements for Term and LogicSentence tell the compiler to generate a default implementation of a class. In this case, we want these types to be instances of the Show class so we can convert them to strings and display them on our terminals. This default necessarily be pretty, as we'll see later. We could also have it derive other classes like Read (to convert strings to the type), Eq (equality), and Ord (ordering, i.e. less than, greater than). Think of derive as saying "You're so smart, Mr Compiler, I'm sure you can figure out this on your own."

Now we can start building LogicSentences.


> x = Variable "x"
> iWinLogic = Exists x ((Atom "speaker" [x]) `And` (Atom "win" [x]))

Here I've put And inside backticks to change it from a prefix operator (like "f" in "f(x,y)") to an infix operator (like "+" in "x + y"). The braces are back, and again they denote lists. [x] creates the list with x as it's only element.

We've arrived at the point where we can work on what we came here to do. We'll tackle a bit at a time, starting with converting just the noun phrase to a logical sentence.


> convertNounPhrase     :: NounPhrase -> LogicSentence

Here I've declared the type of something I'm calling convertNounPhrase. All this says is that it's a function that takes a NounPhrase and returns a list of LogicSentece. The compiler is smart enough that it could infer the type of the function on it's own, but it's common practice to specify it explicitly. There are two reasons for this. First, it serves to improve readability and provides documentation for the author. Second, it helps to locate compile errors by making sure the compiler arrived at the same type the author intended


> convertNounPhrase (Name name)
>                       = Exists x (Atom ("called-" ++ wordString name) [x])

Haskell is nice and lets us define functions in parts. Here we define the convertNounPhrase function when given a NounPhrase built with the Name constructor. This is called pattern matching, and it's wonderful for building functions like this cleanly. Haskell will try each definition of convertNounPhrase in the order defined until a match is found (if none are found, it throws an exception). Note that name here doesn't refer to the NounPhrase built with Name, but the word used to build Name with.

A name, by itself, indicates that there is something that is called by that name. In other words, our representation of "Adam" is: there exists some x such that called-Adam(x) is True. (++ is the concatenation operator, and strings are just lists of Chars, so that ("called-" ++ wordString n) buisness builds strings like "called-Adam".)


> convertNounPhrase (ANoun n)
>       | isPlural n    = ForAll x (Atom (wordString n) [x])

Besides specifying the manner in which a parameter is constructed, we can also place /guards/ in our pattern matches. This definition only matches Nouns built with a Word that satisfy isPlural. For the moment, we'll assume that no non-plural nouns without articles (the, a, an) are passed by the grammar tree builder.

The case statement draws near!


> convertNounPhrase (APronoun n)
>                       = case wordString n of
>                               "I"       -> Exists x (Atom "speaker" [x])
>                               "you"     -> Exists x (Atom "audience" [x])
>                               otherwise -> Exists x (Atom "in-context" [x])

I won't go into the syntax of case; I'm sure you can figure out how it works.

Note I'm leaving out a number of possibile pronouns here in the name of brevity.


> convertVerbPhrase     :: VerbPhrase -> (Term -> LogicSentence)

We're getting trickier here. convertVerbPhrase is a function that takes a VerbPhrase and returns a list of functions. These functions each take a Term and return a LogicSentence. In Haskell, all functions are curried, so I could remove the parentheses from this type definition if I wanted to. I'm leaving them in for readability.

Why do we want to return a function here? A verb phrase describes an action or relation. It needs the subject of the sentence to complete it's meaning. If I say "dances a jig.", it's not a complete sentence; there is an immediate question of "Who?". It needs the who for the full meaning.


> convertVerbPhrase (AVerb v) = (\subject -> Atom (wordString v) [subject])

We'll expand verb phrases soon, but for now, we'll just deal with a single verb. This definition shows the syntax for a lambda function: (\x -> ... ). When we apply a term to the result of convertVerbPhrase, that term will be used in place of subject.


> convertSentence       :: Sentence -> LogicSentence
> convertSentence (Declarative np vp)
>                       = let nounSentence = convertNounPhrase np
>                             subject = subjectOf nounSentence
>                             action = convertVerbPhrase vp
>                         in combineNVSents nounSentence (action subject)

Finally, the goal of the post. This demonstrates a let block. Those equal signs don't mean what they do in imperative programming. That is to say, we aren't evaluating convertNounPhrase np and storing the result as nounSentence, we are declaring that nounSentence is equivalent to convertNounPhrase np. We could have wrote this function as


> convertSentence2 (Declarative np vp)
>       = combineNVSents (convertNounPhrase np)
>                        (convertVerbPhrase vp
>                                           (subjectOf (convertNounPhrase np)))

So now we need to define subjectOf and combineNVSents, and we'll be done for now.


> subjectOf             :: LogicSentence -> Term
> subjectOf (ForAll t _) = t
> subjectOf (Exists t _) = t

Another feature of Haskell's pattern matching: we can tell the compiler that we don't care about some terms. "_" is a wildcard. It will match anything for that term.

Note that we don't have to define subjectOf for all possible Sentences. We'll accept a Exception if it's called for a Sentence it's not defined for. We're careful above to have convertNounPhrase only return these two types of sentences, precisely so this funtion will work.


> combineNVSents        :: LogicSentence -> LogicSentence -> LogicSentence
> combineNVSents (ForAll t npDescription) vpDescription
>                    = ForAll t (npDescription `Implies` vpDescription)
> combineNVSents (Exists t npDescription) vpDescription
>                    = Exists t (npDescription `And` vpDescription)

Nothing new here.

Now we can load this post into a Haskell interpreter (I'm using ghci) and try it out:


ghci> convertSentence iWin
Exists (Variable "x") (And (Atom "speaker" [Variable "x"]) (Atom "win" [Variable "x"]))

I win.

On Makerfaire

2008-10-22T15:54:00.006-05:00

Well, we a-traveled to Austin this past weekend to take part in MakerFaire.

Rather than show you photos of what was there, I thought I'd scan in some gestures from my sketchbook. Gesture drawing is something that we'll be coming to (eventually) in the how-to-draw posts, but for the moment, suffice it to say that gestural drawing is a way to capture a person or thing as quickly as possible; important in these circumstances because everyone was a-movin' and a-shakin'.

It's not a terribly long drive to Austin from here, but long enough that we drove well past sunset Friday night. I drew things in the dark. This is one place and time when your blind contour drawing is more than just an exercise. I particularly like this one, because it was drawn as we passed the truck; you can see I drew clockwise from the right, and by the time I got back around to the wheels, they were beside us instead of in front.

The next morning we grabbed coffee before heading out to the Faire; the fairground opened at 10:00, so we had plenty of time. Lisa had some trouble getting a truly dry cappuccino, but the wait staff was eager to remedy the problem. Scarily chipper. Really.

The human-sized mousetrap was impressive --- I got a front-row seat to the first run. This was just before the actual performance; the young man was about to make his stage debut as the strongest boy in the world. He did a fine job.

It was an interesting point, though, that very, very few of the performers at the faire were particularly good showmen. All the tech and engineering was excellent --- really neat --- but if you didn't already know how it worked and why it was so impressive, the presentation would have been a bit off-putting. Several performances had everything right and were just missing a P.T. Barnum to turn it into a real piece of buskering.

When hats were passed, I am sure that they suffered because of that.

There was a lot to see, and much of it is recorded elsewhere. I'm hoping more to capture the spirit of the place than give an exact recounting of what we saw. The highlights for me were the Mice Pace Maze --- a maze made entirely out of sound. I wished it had been much bigger; the concept is really lovely to me. Hats off the them. Cyclecide's guitar/bike machine was also much fun. I think my favorite part, though, was just wandering and listening to people talking, exchanging ideas, learning new skills, and building community. Many of my sketches were just people talking.

It's my hope that next year, that sense of community-building is enhanced. Many of the booth-persons stuck to such a rigid script that it was hard to get into a real conversation. The times when that shell cracked were far more exciting. A lot of time was spend chatting with the people willing to chat.

After Makerfaire on Saturday, we drove up to Dallas, where some of the group went clubbing. I wasn't that well aquainted with downtown Dallas, so I went for a walk. We agreed to meet back at a cafe where this man was on the wait staff.

It was pretty late. While I walked I spent some time thinking on what I had seen at makerfaire, and about the nerdy community in general. It has always been striking to me that only some people are interested in how things work, and that only some are interested in how they express themselves. Ti seems to me that whatever our occupations and whatever our interests, we should understand what we are doing, and do it with a practiced body and a focused mind. Even if you make washers in a nut-bolt-and-washer factory, you ought to make washer-making into an art. Make masterpieces of your life.

When I got tired of walking, I sat under an overpass for a while. Then it was time to head back to the cafe for hot chocolate.

After Dallas we did the Modern and the Kimbell in Fort worth. I might write another post about what we saw and said there, but I think I've said enough.

This was drawn while getting still more coffee, and wondering at how many people are apparently fueled entirely by the stuff.

I don't know whether I discovered anything new this weekend; but time will tell. As a church sign told me at 2:00AM, "This is a test, Joe Clifford."

More 10/15/08 Progress

2008-10-21T23:48:00.017-05:00

A decent week, if unnecessarily loaded down with homework... Also, it has become apparent that my neighbors expect life to stop for football games.

Motor Drivers:
I have become irritated with the motor driver offerings to the hobby community (and the educational community for that matter). Your choices? Realistically Pololu and IFI. This is unacceptable.

In response I have started designing motor drivers. Everything from the 10A range to 100-300A. Parts are on the way, samples have been shipped, and donations have been collected from friends. I hope to have at least one finished before the Spring semester. Units will be sold at a minimal markup; software and schematics will be made open source.

Underwater ROV:

Poured float from urethane foam to allow for near-neutral buoyancy and minimum compression at depth.
Finished modifications to propeller hubs and mounted fourth motor.

Linear Accelerator:

New coil tested. 3.5" long coil, 3 layers, 14awg tried as 1st stage. Resulting velocities were significantly less than the previous coil(4 layers, approx 2.5" long 14awg) which had achieved 6.5J Kinetic Energy at over 20m/s.
I must finish construction of a "V-switch" using 2 SCR banks. Held up by tight budget and lack of high current IGBT drive optoisolators.
Got the idea of expanding the V switch out to multiple legs and using either a longer coil or additional coils on the same stage(if that makes sense).

Centaur:
A late night wiring "correction" bypassed a voltage regulator, putting ~10VDC unregulated to the 5VDC "regulated" power bus. Casualties included two MaxSonar's. As a result, I will include a zener diode + fuse with any power bus containing valuable electronics on future projects. It was fortunate my GPS was not wired during the incident and the more than a dozen Dynamixel servos are rated to over 12VDC.

I made progress on a few other projects not deserving of their own section(at this time). My Matlab simulation of obstacle avoidance using RL is working with only 4 bit numbers. Prepare for a RL robot running no code. "Hard-wired for learning?" you ask... that's right. Also, I re-attached my other walker's(cricket?) head because it looked very depressing laying on the ground, connected only by its "spinal cord".

Calling Shots for 10/15

2008-10-16T21:02:00.004-05:00

My grade for last week's called shots: B-.

I did get them both, just not as thoroughly as I wanted. My post on "where I'm at" became part I, and I had some errors with generated parses. On the other hand, I did get some fodder for an upcoming post entitled "Computers say the darndest things."

For this week:

Subject Verb agreement. I'll be completely removing results for now where the subject and verb don't agree. I'll be bringing them back later on when I introduce scoring for results, because sometimes a person speak bad. In the meantime, I'm hoping to work with smaller, more manageable sets of parses while I work with other problems like relevance and context.
Further word shenanigans. Nouns can be adjectives: "clown car," "text file," and "blog post." Words can also be built from existing words as well: "bloggy," "blogger," and "bloggily" all communicate meaning, even if we've just invented the word "blog.
NLP, Part II

10.15.08 Hackjam

2008-10-15T23:42:00.002-05:00

Discussed physics, nanowrimo, a little haskell and a little C.

By discussing physics I mean I introduced the group to Fantastic Contraption, and very little got done ;). If you haven't played fantastic contraption, you ought to give it a try; it is a nice pure example of what engineering is. It's certainly better than forcing your kids to build yet another bridge --- there is other engineering in the world than bridge building!

We also got a few more heads interested in nanowrimo --- National Novel Writing Month. The goal is to write 50,000 words in the 30 days of November. It is an incredibly beneficial excersize. We talked about methods of writing --- whether to plan out each scene, or write as you fancy at the moment. I have written with very little planning the past three years, but failed to finish the past two. I'm going to try some more extensive planning this year and we'll see what happens.

This weekend: Makerfaire. I'll do my best to write a few posts from there.

On calling shots:

I made two of three of my shots for this week, and that ain't bad.

For next week:

Post on Makerfaire
Post another drawing excersize

And now off to bed.

On the Livescribe Pulse

2008-10-15T11:49:00.005-05:00

The Pitch

The Livescribe Pulse is an e-pen; it allows you to take notes while recording simultaneous audio, and then uplaod both the notes and the audio to your computer.

For instance, you're sitting in a hackjam, and someone says "Oh, a Lagrangian inverted hapgood might be able to solve that problem." You're scribbling math in your notebook as best you can, but you've never heard of a Lagrangian inverted hapgood (for good reason) --- so you make a little note: "soln?" and keep working.

Later, when you get back home, you tap "soln?" with the tip of your pen, and the disembodied voice of your friend repeats "Oh, a Lagrangian inverted hapgood might be able to solve that problem." You happily google the phrase and discover what you needed to know.

Much sillier, but also more fun, is the built in piano. With a few strokes of the livescribe, you can draw a single octave piano --- and then play it with the tip of the pen!

The Product:

The pen comes in a nice box of a reasonable size; inside is the pen, a simple manual (a single folded page), a carrying case for the pen, headphones, a lanyard for the pen, replacement ink cartridges, and a spiral-bound notebook.

The pen has only one button, which the manual explains should be pushed. The pen came charged, and turned on after about two seconds boot time.

Setting the date, and time is an amusing experience --- in the cover of the notebook is a page printed with a calculator and various function keys --- including a left/right handed switch to control the direction of the display (hooray!). The time and date are set by tapping the appropriate 'buttons' on this printed page.

A reasonable tutorial walks you through how to use the pen. At the bottom of each page of the notebook, there is a set of printed controls --- record, pause, stop, time, speed, and volume. Tapping on record begins recording, and anything you write (on any page of the notebook) is tied to what you record as you record. If you want to hear something again, just tap on the note (down to the individual stroke) and listen to exactly what was happening when you drew that line. Or, if you like, turn on the optional latency, and hear what happened starting 5 seconds before you put ink there.

The pen can perform calculator functions in two ways --- by using the scientific(ish) calculator in the front cover of the notebook, or by accessing the calculator function by drawing a 'nav plus' (a big + sign) anywhere in the notebook, starting the calculator, and then writing simple arithmetic: write "24*36=" and the pen's display will alert you that the answer is 864.

The handwriting recognition is quite good; I had no trouble with incorrect readings in the limited vocabulary that the pen currently uses.

The desktop application is another matter. It works only in windows (still no luck with virtualization for me, though some claim that VMWare does the trick). While one can export pages as PDFs, there is little opportunity to take the images or the sound out of the Livescribe program and use them. The search ability (which uses handwriting recognition to search a whole notebook of notes for key words) works fine --- not brilliantly, but just fine.

There is an online portion of the Livescribe application of which I cannot speak --- my native windows machine is not on the interwebs.

How it Works:

The pen's workings are rather clever. The pen contains an ARM9 processor, a OLED display, a pressure sensor, and an tiny infrared camera which points at the tip of the pen. Each page of each notebook (you can use as many as four at once) is printed with a pattern of tiny (.3mm) dots called the anoto pattern. Any five by five section of the anoto pattern (about 3mm^2) is uniquely identified by the pattern of dots. Capturing the pattern with the camera allows the pen to identify its location on a sub-mm level.

Everything else is just clever programming.

The Pros:

It does exactly what it says it does
Excellent on-pen interface.
HIGH wow factor
Large capacity (1 or 2 GB)
Audio is clear
Notes are legible
An on-pen application development suite is coming -- and is in pre-release now. <--- VERY exciting. Why I bought the pen.

The Cons:

Windows only
Desktop application is nearly useless. Good only for archiving notebooks you're replacing
Cost: $150-200 US
Battery life: 1-2days. Charge time: 1-2 hours.

What I Think Should Change:

I'd love to see .svg, jpg, and .png export of pages, and SOME kind of export of audio.

The pen is completely round. It rolls off of everything.

The pen has no cap --- only a full carrying case.

Livescribe is making a lot of vauge promises about applications (Spanish translation, full handwriting recognition) and coming-soon features (the ability to print your own paper --- notebooks are $5 apiece and up). From what I can tell, livescribe expects the Pulse to be able to heal the sick and expel daemons by the end of this year. But they have not released a timeline. Lots of big talk, but they won't say when it'll all actually be done. That's worrying me a lot guys. I'm happy enough to wait even a year for some of those abilities; just tell me that it's gonna take that long. Don't vaguely suggest that it might be done by this December.

There you have it. The Livescribe Pulse. Available online and at Target for ~$150 and $200, depending on memory capacity. Notebooks are 4 for $20.

Natural Language Processing - Part I

2008-10-14T22:20:00.001-05:00

I went to see Iron Man back in May when it came out. It was a fun movie and it definitely satisfied my inner comic nerd but the first words out of my mouth when we left the theater were, "I have some software to write." Since then, I've been working on a small portion of that software: a natural language interface for a computer, a sort of natural language shell.

The first stab was a naive one. It worked in a subset of english where every word had only one meaning and every sentence had only one possible parse. I thought I knew how bad of a limitation I had placed on myself, but I wanted to start building an approximate solution and get experience in the problem space. It turned out that I underestimated the limitations I was working under and had to abandon that approach sooner than I had hoped. Before I stopped, however, I had a system that I could make statements to, ask questions of, and even tell to launch programs, provided I was careful in my wordings.

One sentence would be read in at a time, parsed according to a BNF grammar, and classified as declarative, imperative, or inquisitive. Declarative sentences would be added to the knowledge base (KB). There was no validation on what was added; the system could be fed two inconsistent statements and it'd take both as gospel. Answering questions involved a search of the KB for an answer. Yes/no questions did a backward substituion search for satisfiability and "what is" questions searched for facts in the KB that answer the question. So given: "All men are mortal", and "Socrates was a man", it could answer the question "Was Socrates a mortal?" with "Yes." and "Who was Socrates?" with "A man." Imperative sentences were recognized, and if the verb of the sentence was "run" and the object a constant (names like "emacs" that weren't in the dictionary were treated as constants), it would try to run a program with that constant's name in the background.

Just over two months ago, I started from scratch. (I had been learning Haskell as I wrote the first system, so even the code that had reusable functionality was a mess.) Through the magic of Monads, the new parsing code is about 40% smaller and returns a set of all the interpretations for a sentence it can come up with. This set gets much larger than I expected. Just introducing the ability to interpret any word as a name explodes the number of possible responses. The program shows the sentence "Emacs is a program that opens text files" as having 23 unique parses. Now, there's a lot of those 23 that can be discarded through checking some form of subject verb agreement. What's left can even be ignored given a parse that assumes less names, so it looks like there's still a workable solution there. In the worst cases, the system will have to deal with a nondeterministic KB until either more context is available to make the sentence clearer, or the system can ask questions.

This is an interesting problem in a lot of ways. More next week.

More from 10/8/08

2008-10-11T12:22:00.002-05:00

Montana's still working on his grid evaluation computing thing. I've long forgotten what he calls it. From what I understand, he's got functions that evaluate constants, but realizes he needs functions that can evaluate references. It seems like he's making progress lately, so I'm hoping we can get him to post what he's up to.

So I'm working on a font based on my handwriting. It's something I've wanted for a while as a novelty item, but I've been pleased with how well it's working out. It's nice to have a font that my brain associates with drafts, notes to myself, and unfinished stuff. I'm hoping to have it in a usable state for the start of Nanowrimo so I can put it into an extended test.

I did not quite make my shot for the week. I made progress in the form of a couple of design breakthroughs, but not much in the form of code aside from recognizing plural forms of nouns, and even that was crude. I've got a three day weekend here, so I should do better this week.

My called shots for this week:

Most sentences converted to a (possibly large) set of possible logical meanings
A post describing where I'm at with this thing.

Drawing exersize

2008-10-11T10:46:00.007-05:00

I tried writing a few paragraphs about why I think people should learn to draw --- communicating ideas, self expression, recording memories --- and it seemed like so much fluff. It comes down to this: I bet you've said, "I wish I could draw."

Gaining the ability to draw realistically (and even photorealistically) is not hard ; you will need to devote some time to it, however. For this first exersize, you'll need to set aside 20-30 minutes of quiet time alone. I don't recommend music, and if there will be other people, avoid conversation. Alone is best.

You will also need a pen --- ballpoint is fine --- and a nice big piece of paper. You can do this on 8.5x11, but it's much more rewarding on big paper. I'll be doing my example on a page that's nearly 2'x3'.

Set up a comfortable place to sit; you'll want to be able to sit up pretty straight, and be able to reach your paper easily.

Enough preparation, eh? Read all the instructions first:

Place your pen in your writing hand and lightly touch the tip to the center of your paper.
Sit so that you face away from your paper, but your drawing hand can still comfortably reach the page. You should not be able to see it at all.
With your non-writing hand, make a nice relaxed shape; curl your fingers as if you're holding something, or pointing lightly. Just keep it very relaxed.
Now without looking at the paper, begin to draw your hand. Let your eye trace along the exterior outline, very slowly, taking in each bump and curve. As your eye moves, try and move your pen in the same way --- copying each little bump. When you've done the outline, then start working on the little grooves and interior lines.
Take the full 20-30 minutes and try and record every little detail. NO PEEKING. Please, I beg of you, resist the urge to look. Just let the pen move unobserved, and don't worry about the result. Chances are you'll be bored silly after about 10 minutes. Resist the urge to stop --- this is exersize! Keep pushing yourself to find new lines, new curves. Never stop drawing --- if you must, redraw the lines you've already done.

Go ahead. Do it! Reading what you were supposed to learn without doing the exercise is futile --- come back and read the rest when you're done.

Done? Good! Here's mine:A masterwork, no? If yours looks as little like a hand as mine does, I congratulate you --- you didn't peek even once! (Note that for clarity, after my 20 minutes were up I traced directly over the primary contours again --- the ones around my hand.) Right now you're probably despairing eve being able to draw --- and yelling at me about unreasonable constraints, ridiculous time limits, and difficult subject matters.

Tough beans.

There were several purposes to this exersize. None of those purposes was to make you look like Leonardo. Here are some reasons why I made you suffer through that:

Hand-eye coordination. If you can write, you have enough hand-eye coordination to draw. But learning to sync your hand to your eye when they are not pointed in the same direction is a little like patting your stomach and rubbing you head: not hard once you get the hang of it, but it takes a bit of time. You just spent 20 minutes forcing your hand to follow your eye.
Observation NOT classification. One of the greatest roadblocks to realistic drawing is labeling. As long as you continue to see a hand as four fingers and a thumb, you'll never draw it accurately. Blind contour drawing (which is what you just did) forces you to think in terms of lines and curves; you can't tell whether you're drawing a finger because you can't see what you're drawing. You can only concentrate on what the pen is doing right now.
Confidence. I know that that might seem paradoxical, to say you gained confidence from making such a godawful rendition of a hand --- but think of the last time you drew something. Did you use pencil? Did you erase much? How frustrated were you during the process --- and with the result? Now think about how you felt and thought during this drawing. You spent 20 minutes drawing a hand. I hope you felt relaxed during the process --- even meditative. You didn't erase once, because you were using pen, and you couldn't see what you were doing anyway. And you should feel good about your result, too. You drew in pen. You drew blind. And I bet there are recognizable bits in there, aren't there?

Try doing one of these a day for a few days. Don't worry about improvement --- just notice the calm, trance-like state that prolonged observation creates; during later exercises, you'll want to remember what that feels like.

[Note: for those of you who are looking up "blind contour" --- this exersize is a modified blind contour, because we are including many interior lines, which are not technically contours. Doing a pure blind contour is also worth a try, and is much faster. Do just what we did here, but only draw the outline --- no interior curves at all. It should only take a few minutes at most.]

Hack Jam: 10.8.08

2008-10-09T11:59:00.003-05:00

Discussion: typography, drawing, and the library of our dreams.

Font was on the table because Adam's been working on a font for the coming nanowrimo; for tasks of that nature, several of us use FontForge. Fontforge has a miserable interface; it's highly unintuitive, uses multiple windows that cannot be docked, and is all around a hassle to use. However, it is open source software -- and is pretty much the ONLY free or even reasonably cheap software that will allow you to make the most of what the TrueType and OpenType standard have to offer in terms of kerning pairs, ligatures, and hinting. Powerful but not agile or intuitive? The story of open source.

We also talked about how unfortunate it was that so few pieces of software allow for the use of these features even when they are included in a font; Adobe products remain nearly the only bastion of font flexibility --- outside, of course, the ever miraculous Latex.

I mentioned that I had offended an art student by mentioning that I thought it was worth any artist's time to learn to draw. In my opinion, the ability to communicate visually, to see objects with a draftsman's eyes, is enough excuse. But still further, it is expected of you --- if you say you're an artist, lay people assume that means you can draw. As Adam put it: "When someone asks 'Can you draw that?', 'No' is the boring answer." I brought up Betty Edwards' Drawing on the Right Side of the Brain which is a book of exersizes based on a neuro-psychological understanding of how draftsmen draw; I recommended her methods as pedagogical breakthroughs which ought to be applied but, at least in my experience, have not been.

On calling my shots:
I did not get the Livescribe working with virtualization; I did get the pen working on a native windows system, and it is recognized by a VirtualBox machine, but the LiveScribe Desktop installer throws an unrecoverable error when attempting to communicate with the pen. Will try VMPlayer.

This week I call several small things:

A post reviewing the Livescribe.
A post with a right-brained drawing excersize you can do at home
Screen-print a t-shirt for Maker faire.

Fastbootin' Linux

2008-10-03T23:41:00.005-05:00

A couple of links are in order regarding recent progress made in booting a linux system faster. Linux developers Arjan van de Ven and Auke Kok gave a presentation at the recent Linux Plumbers conference on booting an Asus eee pc in 5 seconds (video). That's five seconds to usable desktop with processor and disk idle, but no, that doesn't include bios posting. I'm not sure how long that is on a eee. Here's the most detailed article covering the presentation, and here's the ppt itself.

I've been playing around with some of the techniques they used this week. I had pruned my init scripts sometime last year to get a 15 second boot time, though that had climbed up to the 25 second range with my new laptop and new hardware. I've gotten it back down below 20 seconds by applying the available kernel patches in Arjan's fastboot .git tree and modularizing the non-critical part of my kernel. There's three major avenues to pursue to remove more time on my box. I still want to understand why there's a 3 second pause in the kernel loading process that wasn't there on my old laptop. There's a new X.org server that should improve startup time somewhat. I should be able to use super readahead to improve IO throughput in bootup (and possibly preload firefox as well?).

The presentation was done from systems installed with Fedora and Moblin. From what I read, these improvements will end up in most other distributions as well. The kernel patches may make it into 2.6.28 (earlyish 2009), the improvements made to X should make it into the next release of X.org.

I'm putting this all aside for a little while and get back to working on English language processing this weekend; I'll write up more about exactly what I'm doing with that soon. As a target for Wednesday, I'll commit to making significant progress, but I'm in an exploring stage, so I'm won't committing to what that will entail.

Hack Jam: 1.10.08

2008-10-02T00:34:00.005-05:00

Topics of discussion: the two envelope problem, the livescribe Pulse, slackware bootup times.

Adam brought up a neat examination of a mircocosm within the two envelopes problem:

Select a random number from the positive reals. Now select another. What are the chances that the second is greater than the first?

(Note that what follows is from my mouth -- it is not necessarily Adam's opinion or intention with this example.)

I see several resolutions to this problem. The first cheats, so we'll start there.

Make your first pick; call that number A. Due to the uncountably infinite nature of the reals, there are as many real numbers between zero and a as there are between A and the infinite (think of a function with a vertical asymptote, like tangent --- tan(x) for x from 0 to pi/4 maps to y from 0 to infinity). Therefore, it is equally likely that your next selection will be greater as it will be less --- any A divides R+ into two equal parts, so the answer to our original question is 1/2.

Why does this result cheat? Because the paradox returns if we change from R, the reals, to the natural numbers (1, 2, 3...). Then the infinity trick fails; there is only one number between 0 and 2, and still an infinite number between 2 and infinity.

We can also employ a different cheat --- redefining probability. Mathematicians that subscribe to "frequency probability" define probability as the number of occurances divided by the number of trials. If you flip a coin 100 times, and it comes up heads 57 times, then the probability of it coming up heads is .57. As the number of trials (flips) approaches infinite, then the frequency definition equates to the classical definition of probability. Using the frequency definition solves one big part of the paradox: the expected value of a random selection between one and infinity.

That expected value is infinite --- but no matter how many times you make the selection, your actual return will be a finite number --- 0% of your expected value. Even if you take billions of trials and average them, your actual return will never be infinite. It helps here to keep in mind that 'infinity' is not a number, it is a limit. Our random selection will not return 'infinity' no matter what; just very large numbers.

So how does frequency probability dissolve that paradox? By rejecting the problem definition. If you were able to to 10 trials of selecting a random natural (or real) number between zero and infinity, one of those selections would be the highest. As far as frequency probability is concerned, that number is the maximum possible value. The infinite never enters the equation; and if you change the infinity in the original problem to some number, the answer becomes easily 1/2.

This leads me to believe that the entire paradox stems from the even simpler problem: select a random positive natural number. Such a thing is certainly physically impossible, but I don't want to reject it just for that. But untli the paradox of expected value versus average return is resolved, I think that the original envelopes paradox is contained in many respects in this (admittedly more abstract) simpler question.

My updates:

In the last week I got Hack Jam Log Book up and running.

For next Wednesday, I call getting a livescribe Pulse running via virtualization on a linux box.