tag:blogger.com,1999:blog-77882844662979890642024-02-19T07:52:32.422-08:00directed procrastinationA blog about programming, mathematics, physics, and free software.Zachhttp://www.blogger.com/profile/08359986122518665758noreply@blogger.comBlogger60125tag:blogger.com,1999:blog-7788284466297989064.post-69651925987791135792022-07-01T23:43:00.000-07:002022-07-01T23:44:14.224-07:00Hacking the AstroAI DM6000AR<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyHiAwzHb9MuOKADXBMnuLjzU5WcROKgMgh8NqrUPMTxI18CMWImVcmTqM0hnPj8sDj7vdQICi0tjUVzGL56Ze2Zvx4ZOywo0B4UgJuIIWDqWBBWT4BwZBVv7muKUpKymWGlNYkW-q9iZza8xo_Ijo0VCpkWaHTbADrb9giaFbJLf-cuhrSjEa8Q/s4032/PXL_20220625_205209326.jpg" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="600" data-original-height="3024" data-original-width="4032" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyHiAwzHb9MuOKADXBMnuLjzU5WcROKgMgh8NqrUPMTxI18CMWImVcmTqM0hnPj8sDj7vdQICi0tjUVzGL56Ze2Zvx4ZOywo0B4UgJuIIWDqWBBWT4BwZBVv7muKUpKymWGlNYkW-q9iZza8xo_Ijo0VCpkWaHTbADrb9giaFbJLf-cuhrSjEa8Q/s600/PXL_20220625_205209326.jpg"/></a></div>
<p>
I long ago found <a href="http://www.kerrywong.com/2016/03/19/hacking-dtm0660l-based-multimeters/">this post about hacking digital multimeters</a> to access new
features and I have wanted to try it out for years now. In particular, Kerry Wong was able to enable the multimeter's serial output which is useful for data logging or otherwise injecting that data into some other computer. This is my attempt to
recreate the same hack. I don't have the same multimeter, and the chip on my multimeter isn't marked in
any way as a DTM0660L, but the package is the same and given the <a href="http://www.kerrywong.com/blog/wp-content/uploads/2016/04/DTM0660DataSheet.pdf">datasheet that
Kerry translated</a> and tracing out where some of the pins go, it really seems
like this is the same or a very similar chip.
</p>
<p>
First, I did some data gathering. Below are my composite photos of the board flipped and roughly persepctive corrected so that they roughly line up if you layer them in, say, Gimp.
It is 2-layer, has a processing chip and a 256-byte EEPROM. It also has several
unpopulated headers near the EEPROM (J1 and J3) and what looks to be an
unpopulated serial Rx/Tx header down by the beeper (J2). I soldered headers to
these after confirming that I can still close the case with them attached. I
used right angle pins for the serial header as I saw that I couldn't close the
case if I connected wires to a those.
</p>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgf0oQWMZ4WrlmNdfoIBUI0FHyTFGF4Uyutzrd-k_-6EEJ2d2h9rVeCTvPLRrm_fSOqhVDKI09Vmw5ZDv0U8rTnprT0tswuFiTsROg7QAQYcHRJBxaMf4X4MUJW74tDJrby6vvymFPBSrI27SmY9aJc7lmyqqSo_WmRJgm_OfDr658cu5R5f3G3iA/s1000/board-front-small.jpg" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="400" data-original-height="504" data-original-width="1000" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgf0oQWMZ4WrlmNdfoIBUI0FHyTFGF4Uyutzrd-k_-6EEJ2d2h9rVeCTvPLRrm_fSOqhVDKI09Vmw5ZDv0U8rTnprT0tswuFiTsROg7QAQYcHRJBxaMf4X4MUJW74tDJrby6vvymFPBSrI27SmY9aJc7lmyqqSo_WmRJgm_OfDr658cu5R5f3G3iA/s400/board-front-small.jpg"/></a></div><div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFEMzrMz3oedJ2dQwPPUf4pq4PZukAIlvIcVXen9PMuKtI6BjSNtrCggANsAxEnSWrL1u3FLV0gRJs99ZLbUE6N1f77ldom6VSMrlAk6zfbGhv-vks1TbukEFoxGEcGdoC9rjz9Z84_ZTZe5lx3oHGDf79forSGxQ0u3b-KbYIT4uqaBHhcyI1DA/s1000/board-back-small.jpg" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="400" data-original-height="504" data-original-width="1000" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFEMzrMz3oedJ2dQwPPUf4pq4PZukAIlvIcVXen9PMuKtI6BjSNtrCggANsAxEnSWrL1u3FLV0gRJs99ZLbUE6N1f77ldom6VSMrlAk6zfbGhv-vks1TbukEFoxGEcGdoC9rjz9Z84_ZTZe5lx3oHGDf79forSGxQ0u3b-KbYIT4uqaBHhcyI1DA/s400/board-back-small.jpg"/></a></div>
<p>
Note that you also need to worry about room on the other side of the board.
Immediately below J1 and J3 is the backlight for the LCD. After I soldered the
pin headers, I clipped the bottom pins flush with the board and then reflowed
each pin so the result is mostly flush and smooth. No need to worry about that
for the J2. It looks like J1 is a header for programming the main control chip.
J2, is for serial data out (and perhaps in). J3 is an EEPROM programming
header.
</p>
<p>
Used my <a href="https://www.amazon.com/HiLetgo-Analyzer-Ferrite-Channel-Arduino/dp/B077LSG5P2/">cheapo logic analyzer</a> with <a href="https://sigrok.org/wiki/Main_Page">Sigrok/PulseView</a> to capture some traffic
to/from the EEPROM.
</p>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKlK041LGWTpCDbxmMXN4y0ZszIUjTs7XC1NHiQsxVHHCsuQrE30g8zLiq6sT-ws7eTq32eGxTSxy9UGgvvphZSjtxs0Xm1cSRjpRJ3S7NRaSyyRLMwuurB7nS-kZ1BY64YoTTGzVHIMoajfXXQk0kBbOpnsVPGllZq4mbv7KF9ChGRmvSlJnuDA/s1033/eeprom-traffic.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="400" data-original-height="302" data-original-width="1033" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKlK041LGWTpCDbxmMXN4y0ZszIUjTs7XC1NHiQsxVHHCsuQrE30g8zLiq6sT-ws7eTq32eGxTSxy9UGgvvphZSjtxs0Xm1cSRjpRJ3S7NRaSyyRLMwuurB7nS-kZ1BY64YoTTGzVHIMoajfXXQk0kBbOpnsVPGllZq4mbv7KF9ChGRmvSlJnuDA/s400/eeprom-traffic.png"/></a></div>
<p>
In general I wanted to make sure we don't interfere with the meter reading from
the EEPROM. However, looking at when data is transferred, this isn't much of a
problem. Data is only read when you interact with the meter (i.e. pressing
buttons or changing the mode). The rest of the time, the I2C bus is completely
silent.
</p>
<p>
Used my <a href="http://dangerousprototypes.com/docs/Bus_Pirate">Bus Pirate</a> to dump the EEPROM in total. This is done by connecting
ground to the Bus Pirate (first pin to brown lead), connecting VCC from EEPROM
to the pull-up on the Bus Pirate (second pin to green lead), serial clock to
serial clock (third pin to purple), and serial data to the serial data (fourth
pin to gray).
</p>
<p>
In order to read from the device with the Bus Pirate, we need to use the funky
Bus Pirate command line scripting syntax.
</p>
<p>
My pin states look like this.
</p>
<pre class="example" id="org05101c4">I2C>v
Pinstates:
1.(BR) 2.(RD) 3.(OR) 4.(YW) 5.(GN) 6.(BL) 7.(PU) 8.(GR) 9.(WT) 0.(Blk)
GND 3.3V 5.0V ADC VPU AUX SCL SDA - -
P P P I I I I I I I
GND 0.00V 0.00V 0.00V 3.01V L H H H H
</pre>
<p>
You can then do a scan from the Bus Pirate to find the EEPROM using one of the
predefined I2C macros:
</p>
<pre class="example" id="org4c2e74b">I2C>(0)
0.Macro menu
1.7bit address search
2.I2C sniffer
I2C>(1)
Searching I2C address space. Found devices at:
0xA0(0x50 W) 0xA1(0x50 R)
</pre>
<p>
Very handy, that macro. We need to <i>write</i> the address to read from, then read 256 bytes (the size of
the EEPROM). First, write the address to read from by starting an I2C message
with '[', writing the I2C <i>write</i> address of the EEPROM, then writing the
address to read from (0 in this case), and finally close out the I2C message
with ']'.
</p>
<pre class="example" id="org74fa315">I2C>[0xa0 0]
I2C START BIT
WRITE: 0xA0 ACK
WRITE: 0x00 ACK
I2C STOP BIT
</pre>
<p>
Then we need to read the data. This time we write the <i>read</i> address, and read
a byte (and repeat that 256 times with ':256').
</p>
<pre class="example" id="org2e646af">I2C>[0xa1 r:256]
I2C START BIT
WRITE: 0xA1 ACK
READ: 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK
0xFF ACK 0x52 ACK 0x00 ACK 0x5E ACK 0x01 ACK 0x20 ACK 0xF5 ACK 0x03 ACK 0x06 ACK
0x20 ACK 0x38 ACK 0x18 ACK 0x44 ACK 0x02 ACK 0x6E ACK 0x4B ACK 0xC8 ACK 0xC8 ACK
0xFF ACK 0xFF ACK 0x14 ACK 0xFF ACK 0x40 ACK 0xFF ACK 0xF7 ACK 0x99 ACK 0xE7 ACK
0x7F ACK 0x64 ACK 0x00 ACK 0x96 ACK 0x00 ACK 0x00 ACK 0x80 ACK 0x82 ACK 0x80 ACK
0x62 ACK 0x80 ACK 0x0C ACK 0xE7 ACK 0x4E ACK 0x02 ACK 0x09 ACK 0x37 ACK 0xFA ACK
0x08 ACK 0x3A ACK 0x04 ACK 0x0B ACK 0xFA ACK 0x1A ACK 0x0A ACK 0x09 ACK 0xFC ACK
0x09 ACK 0x00 ACK 0x00 ACK 0x01 ACK 0x00 ACK 0x01 ACK 0x00 ACK 0x07 ACK 0x98 ACK
0x00 ACK 0x64 ACK 0x00 ACK 0x64 ACK 0x00 ACK 0x64 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK
0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0xC0 ACK 0x7F ACK
0x00 ACK 0x83 ACK 0x01 ACK 0x00 ACK 0x09 ACK 0x2B ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x0A ACK 0x80 ACK 0x00 ACK 0x80 ACK
0xFA ACK 0x86 ACK 0xE0 ACK 0x7C ACK 0x18 ACK 0x01 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x13 ACK 0x00 ACK 0x1B ACK
0x0E ACK 0x0C ACK 0x00 ACK 0x0B ACK 0x10 ACK 0x12 ACK 0x07 ACK 0x14 ACK 0x06 ACK
0x05 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x15 ACK 0x00 ACK 0x00 ACK 0x0F ACK 0x0D ACK
0x00 ACK 0x00 ACK 0x11 ACK 0x00 ACK 0x09 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x0A ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK
0x00 ACK 0x00 ACK 0x00 ACK 0x00 ACK 0x0D ACK 0x00 ACK 0x02 ACK 0x10 ACK 0x0D ACK
0x00 ACK 0x03 ACK 0x20 ACK 0x20 ACK 0x00 ACK 0x03 ACK 0x20 ACK 0x20 ACK 0x00 ACK
0x03 ACK 0x10 ACK 0x41 ACK 0x00 ACK 0x03 ACK 0x08 ACK 0x41 ACK 0x00 ACK 0x03 ACK
0x05 ACK 0x41 ACK 0x00 ACK 0x03 ACK 0x05 ACK 0x0D ACK 0x00 ACK 0x02 ACK 0x20 ACK
0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK
0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK 0x00 ACK 0x80 ACK
0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0xFF ACK 0x5A ACK 0xC7 ACK 0x4C ACK
0x0F ACK 0x0F ACK 0x92 ACK 0x00 ACK 0x00
NACK
I2C STOP BIT
</pre>
<p>
(Note that I broke the lines in the 'READ' output for readability). We can use
some standard tools to make this a bit easier to read. Passing through:
</p>
<pre class="example" id="org2be915d">sed 's/ACK//g' | xxd -r -p | xxd
</pre>
<p>
…produces…
</p>
<pre class="example" id="org3cdfd10">00000000: ffff ffff ffff ffff ff52 005e 0120 f503 .........R.^. ..
00000010: 0620 3818 4402 6e4b c8c8 ffff 14ff 40ff . 8.D.nK......@.
00000020: f799 e77f 6400 9600 0080 8280 6280 0ce7 ....d.......b...
00000030: 4e02 0937 fa08 3a04 0bfa 1a0a 09fc 0900 N..7..:.........
00000040: 0001 0001 0007 9800 6400 6400 6400 0000 ........d.d.d...
00000050: 0080 0080 0080 0080 0080 0080 0080 0080 ................
00000060: c07f 0083 0100 092b 0000 0000 0000 0000 .......+........
00000070: 0a80 0080 fa86 e07c 1801 0000 0000 0000 .......|........
00000080: 0000 0013 001b 0e0c 000b 1012 0714 0605 ................
00000090: 0000 0015 0000 0f0d 0000 1100 0900 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0a00 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: 0d00 0210 0d00 0320 2000 0320 2000 0310 ....... .. ...
000000d0: 4100 0308 4100 0305 4100 0305 0d00 0220 A...A...A......
000000e0: 0080 0080 0080 0080 0080 0080 0080 0080 ................
000000f0: 0080 ffff ffff ffff 5ac7 4c0f 0f92 0000 ........Z.L.....
</pre>
<p>
By the way, this is my first time using the Bus Pirate and I have to say that I like the scripting language/command interface. It certainly made this process much less painful than my original plan which was to use an arduino to interface with the IC. I can just interactively pull the data off the chip with no programming at all.
</p>
<p>
According to Kerry's notes, my EEPROM has some significant differences, but the basic structure seems pretty much the same. The data I want to change is in the last line there. In particular, I want to
change the value at 0xfa from 0x4c to 0x4e in order to enable RS232 output and
0xfc to 0x00 in order to disable backlight timeout (if I turn it on, I'll be
responsible to turn it off) but I'll leave the auto-power off timer at 15
minutes as I cannot tell you how often I don't turn off my meter and hear it
beeping from the other room.
</p>
<p>
As an aside, another hack that I found necessary with this meter is a mechanical one. I
stuck hot glue in the beeper as it was much too loud. Even with the glue in
place and the beeper sounding comically puny, I can still hear it from the other
room. At least this won't wake up the family in the middle of the night.
</p>
<p>
In order to actually write to the EEPROM, you need to pull the write protection
(WP) pin low. This pin is connected to the Rx pin in the serial header by the
beeper. So jump that over to ground somewhere. This brings up a worry I had
throughout this effort probably due to my relative inexperience with
electronics, how do I know that it is safe to connect two areas in a circuit?
If I connect two parts of the circuit which are held at different voltages, a
current will flow which could damage components. For instance, how do I know
that I can connect the Rx pin to ground? In this case we can guess it is
safe due to two observations:
</p>
<ol class="org-ol">
<li>The pin seems to be a receive pin, meaning it is set in input, or high impedance, mode. This means that the main IC is not driving this pin high.</li>
<li>The pin seems to be pulled high via a 10k resistor.</li>
</ol>
<p>
As for the other connections in the system, this EEPROM is an I2C device, which
means that the bus is all open-drain. This is an inherently safe bus as nothing
ever drives the bus high, it only pulls it low. Any non-zero voltage is due to
pull-up resistors on the bus.
</p>
<p>
Quick note, in case it isn't obvious (it wasn't to me at first), while it might seem tempting you cannot reliably probe around the multimeters circuitry using the meter itself... I learned that after many confusing measurements. You will
likely need a separate multimeter if you want to mess around with this. Luckily I had one, unluckily it is from circa 1980 with broken leads, so it is not a joy to use.
</p>
<p>
Getting back to it, we issue the commands to write our new configuration:
</p>
<pre class="example" id="orge01986b">I2C>[0xa0 0xfa 0x4e 0x0f 0x00]
I2C START BIT
WRITE: 0xA0 ACK
WRITE: 0xFA ACK
WRITE: 0x4E ACK
WRITE: 0x0F ACK
WRITE: 0x00 ACK
I2C STOP BIT
I2C>[0xa0 0xfa]
I2C START BIT
WRITE: 0xA0 ACK
WRITE: 0xFA ACK
I2C STOP BIT
I2C>[0xa1 r:256]
I2C START BIT
WRITE: 0xA1 ACK
READ: 0x4E ACK 0x0F ACK 0x00 ACK ....
NACK
I2C STOP BIT
</pre>
<p>
And… voila, it is done. Power cycle the unit but make sure to disconnect the
ground jumper to the Rx line or the multimeter will enter some kind of
calibration/test mode.
</p>
<p>
A quick check shows that if I hold the backlight button to turn it on, it stays
on for as long as I was willing to test it (several minutes). When I hold the
relative button which should activate serial output, I see different behavior which tells me that something changed,
but I cannot get any serial output still. With the previous value of 0x4c which
should disable UART output, pressing relative (even if attempting to hold the
button) the unit will beep immediately, setting relative mode at the key down
event. With the new value of 0x4e, it doesn't beep/set relative immediately,
and after about a second of holding it will beep and not set relative mode.
There is no indication on the LCD, but that might just be because there is no
spot for it. Whatever the case, I cannot see any data on any pin I probe. I
would expect it to be on the Tx pin but I only see 0 V on that pin. Of course
sigrok-cli doesn't have some magic in it to decode a steady 0 V into meaningful
data.
</p>
<p>
After 'enabling' UART output with a long press and a beep, I probed around on
the board to see if there was any steady stream of data anywhere, but saw
nothing on any pins. I also noted the disconnected solder bridge connected to
the Rx line. If I bridge that, it just pulls Rx low which will enable EEPROM
write and also force the weird calibration/test mode on startup. I don't think
that is useful for this.
</p>
<p>
Unfortunately, while the EEPROM change worked as it successfully changed the
behavior of the backlight, the ultimate goal of serial output failed. If anyone
reading this can see what I'm doing wrong or has some ideas of what to try,
please let me know. I would love to have this data for a project I'm working
on. Perhaps I'll just end up buying a DMM which has this feature already
enabled… but where is the fun in that? I also could decode the signals sent
to the LCD and turn that into data for a serial console to receive, but that
sounds like even less fun.
</p>
Zachhttp://www.blogger.com/profile/08359986122518665758noreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-23102071530161726022016-03-13T10:30:00.000-07:002016-03-13T10:32:15.093-07:007DRL Post Mortem<p>I have officially declared my attempt this year as a failure, but I was able to get quite far in this in spite of a major service interruption in the web services that I maintain (which soaked up about half the week to remedy) and a project due for an Android class I was taking (which took up a solid day of time). I was able to gain some shaky footing in the Godot engine and start to understand how you might make a game with it. </p><p>I think that while this attempt didn't get to the point of a playable game, it was a success in many ways and I think I'll keep at it and perhaps have something to demo at my next Indie Game Developer meet up. If I can get the basic mechanics of the game in place before then, even if it lacks the rogue-like aspects I wanted, I think that I will be pretty impressed with the accomplishments. Further, I'll have this project at a pausing point just in time for our development sprints using Unity3D. </p><p>However, the challenge is over and I wanted to put together a post about what I learned regarding this process. </p><div id="outline-container-orgheadline1" class="outline-2"><h2 id="orgheadline1">The Good</h2><div class="outline-text-2" id="text-1"><p>Using Godot it was very quick to get certain things up and running and even getting some of the behavior I wanted basically for free. That isn't even considering all of the things it gives me for free like handling input in a reasonable way, being portable to half a dozen platforms, and abstracting the graphics and sound to an easy to use interface. These tend to be things you get from any game engine, but it is important to note them here as they are something that Godot does pretty well. </p><p>Godot seems to be well thought out. No matter what exactly I want to do, there seems to be something in place to support that. This is pretty great feeling when you are coming from the world of either incomplete engines or building something by yourself. I feel like I'm programming, which is a good thing, but I also recognize that the scaffolding that they provide makes this all go much faster. Godot Script isn't that bad of a language and, while the text editor sucks and the developers seem to <a href="https://github.com/godotengine/godot/issues/1599">have something against embracing the one true faith</a>, it works well enough to limp through basic editing tasks. </p><ul class="org-ul"><li>I was able to get an avatar walking around the screen using keyboard for motion and mouse for looking/aiming.</li>
<li>I was able to get basic collision detection for the player with walls, enemies, objects in the levels.</li>
<li>I was able to use the collision system and ray casting to allow interaction of the player with elements in the level. For example, the player can open a chest, but only if they are standing facing it and within the range of their arm.</li>
<li>I was able to use the 2D light occlusion to provide line of sight out of the box.</li>
<li>I was able to get some of the visual feel I wanted by using a pixelating shader.</li>
<li>I was able to get some animations close to how I would like them (the walking and aiming animations) and incorporate some of the mechanics (such as movement while aiming is slowed).</li>
<li>I was able to use the navigation polygon facility in the engine to route enemies around the map.</li>
</ul><p>All in all, this got no where near a 'game', per se, but it did quickly become something where you could walk around and interact with things and it was clear how to move forward. </p></div></div><div id="outline-container-orgheadline2" class="outline-2"><h2 id="orgheadline2">The Bad</h2><div class="outline-text-2" id="text-2"><p>Most of the 'bad' things that happened were basically because I underestimated all of the work that goes into making a game. I knew I would underestimate it, but I think it bears mentioning anyway. </p><p>Even as your ideas start to gel in your head, implementing them in the editor is quite the bottleneck. I basically can't imagine a world where this won't be true, but it sure is aggravating. You have a vision, be it good or bad, but it takes time to get things out. For example, while the art was difficult to brainstorm (how do you make something scary from a top-down view), it was even harder to create somewhat decent sprites and to get them all exported from Inkscape to their separately moving components and then key frame the animations in Godot. Only then do you see that what you were trying to do actually doesn't achieve the effect you wanted, and you need to go back to the drawing board all over again. This iteration process takes a lot of time. </p><p>One limitation that Godot caused was that performance is somewhat suspect in the Godot engine. Very early in this process I needed to decide between making a 3D game and a 2D game. I felt that a 3D game would provide more flexibility in how the visuals would appear and would require less fiddly tweaking of animations. In 3D I wouldn't need to worry about splitting my sprites into separate pieces to key the animation, this would all be handled by the renderer. However, after playing with the 3D platformer demo, I was struck by how poorly it performed on my Intel graphics chip. Using the discrete card gave passable performance, but I was looking to make a lightweight game and this engine was struggling to run a demo on my system, so I chose to go the 2D route. This directed many of my decisions from then on… and it makes me wonder if they directed them in bad directions. </p><p>I think these are basic limitations of working with sprites. Not much to do about it. Godot has some functionality to render 3D models into 2D sprites, but I didn't experiment enough to know if that would work. I had limited time and a decision needed to be made. </p></div></div><div id="outline-container-orgheadline3" class="outline-2"><h2 id="orgheadline3">The Ugly</h2><div class="outline-text-2" id="text-3"><p>There were parts of Godot that are just awful, or at least awful from someone that approached it like I did. I thought that developing a game would be something like writing a program. It is not, or at least it is not if you are using Godot and probably any other engine with a GUI interface. </p><p>I develop software for a living. I might be doing all sorts of things with that software, automating processes on our servers, creating web pages, creating intricate back end networks, modeling complex systems, or scientific/data analysis, but I'm always writing code. As part of that I'm a bit of a snob when it comes with comes to how this should be done. When you develop code, you should be doing it with a text editor and a version control system. You develop by finding something you would like to change, making that change, and testing it to make sure it works (and potentially modify the change over several iterations), and the select those and only those changes to make a commit with at least a somewhat descriptive commit message to the repository. I pride myself on the fact that each commit only deals with one thing and it does it in a clear and concise of a way as possible. You can look at the code that was changed and it will only be code that relates to the purpose of the commit. </p><p>This mode of development is incredibly hard, if not impossible, when using Godot. </p><p>Adding a node to a scene generally changes many lines in the file. At minimum, because the nodes in the scene have an integer index, all later indexes are shifted. I have no idea why they have an integer index and they don't just use the location in the file, my guess is that they couldn't be bothered to write a decent parser for their text based scene format. </p><p>But that isn't the worst of it, general state of the editor window is also saved in the scene file. This includes things like the transformations (position, rotation, scaling) of all of the nodes even if those transformations are part of a animation. Seriously. If you advance the position in an animation, the new positions of the nodes is actually saved to disk! Why? Why not simply save the baseline transformation and then calculate the effective transformation using the animation and animation position before drawing? My guess is that they didn't think this through entirely. Whatever the case, I started getting into the habit of moving all of your animations back to 0 time before you make a commit in order to work around this. </p><p>The scene file also tracks metadata about the state of the editor, like what view is open, the 2D screen or the editor window. I think this is pretty dumb, but I think they are just following suit from Blender which does something similar if I recall correctly. </p><p>However, I will say that I think that this is just pretty difficult to do right. The point of the graphical interface is that it automates many menial tasks for you. Unfortunately, by covering up a bunch of menial tasks, the editor is quick to produce changes that are large and far reaching with the simple click of a button. I have opened a scene clicked the scene one time, and saw the diff of the file with what is in the repository develop hundreds of changes. In these cases I usually see no changes at all in the scene, nothing appears to be different in the editor, but it did something very significant to the file on disk. Invisible changes to your file are the root of many a head ache in software systems. All those times your spouse is tearing their hair out cursing at MS Word or Excel and trying to understand why everything looks the same but things are working differently, these invisible changes are often why. I want reproducibility. How can I get reproducibility if I can't even be sure of the contents of what is on disk? </p><p>This is not something that is in any way limited to Godot. Heck, it isn't even limited to graphical editors like Godot and Unity (or Inkscape and Blender, for that matter), it is something that you see in any editor that seeks to abstract some process so that the user doesn't need to worry about it. Even things like Eclipse or practically any 'enterprise' (a.k.a. bloated) IDE, tend to hide stray whitespace from the user which tends to encourage users to produce far from clean commit diffs (and causes good maintainers to reject their pull requests). </p><p>So, in total, I think that they need to seriously rethink their format for saving files. The new text based scene and resource files were advertised as a version control friendly format. I very much love the idea that there could potentially be a version control friendly format, and I think the great step forward they made here was making the format a human readable text format, but the goal of making the scenes and resources somehow source control friendly has simply not been met. </p><p>Update: After writing this, I think I have come to a 'solution' here. While far from my ideal solution, I'm simply not going to develop any Godot projects under source control. I am going to treat Godot as I would Inkscape or Blender, I'm going to treat it as a way to edit visual media and I'm not going to care what is going on under the hood in the file formats. </p><p>Perhaps I will put my scripts under source control, but for the rest of the project I am going to do something much simpler, I'm going to treat the entire thing as a black box and take periodic backups. I wrote a script that takes a backup of my working directory every 10 minutes (if changed) and thins out the old backups as I go (using rsync with hardlinking). This will be a better way to work on this. I don't get to keep track of changes, but at least I know I can restore a relevant previous version of the project if something goes wrong. If we are being honest, unless you can look at the content of each commit diff and understand what is happening, you basically have a file format that is a black box and you shouldn't attempt to use version control. I expect that I will be using a similar setup for my Unity3D projects. Perhaps some good has come of what I originally thought of as an unmitigated failure of the Godot engine. This was a hard lesson to learn and I feel a bit naked without a version control safety blanket, but I needed to realign my thoughts on how this sort of GUI based game development works. </p></div></div>Zachhttp://www.blogger.com/profile/08359986122518665758noreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-74212657342035863342016-03-06T12:15:00.000-08:002016-03-13T10:31:48.801-07:007DRL Announcement<p>I haven't used this blog in a long time and I find less and less time to do so. But I really want to have some public outlet for my ideas, I am going to start it again with something that will hopefully be fun… I'm going to take part in the 7 Day Rogue-like challenge. </p><p>This will not be my first attempt at something like this. In the past I have tried to take part in a game jam, but at the time I just didn't have the time. I'm not sure that I have more time this year, but the circumstances are different so I'm hoping that the outcome will be different as well. I have the opportunity to work on game development (for actual money) with a friend of mine and, while I'm not sure I want to be a professional game developer like he does, I want to support him in his endeavor. </p><p>I will use the 7 day rogue-like challenge to cut my teeth a bit in making games using more modern tools. In the past I have prototyped games using home made or half baked game "engines". This time I will be using an established game engine, Godot. This will mean I will need to adapt to their way of thinking in order to get things done, but it also means that I get the benefit of their architecture and design and I get to repurpose a lot of content to make this go faster. I'm hoping that after this experience, I will have a better understanding of what goes into making games on these game engine/IDE things. </p><p>I chose Godot because it is Free Software that runs well on GNU/Linux. It has plenty of warts and there are very capable proprietary competitors out there that run on GNU/Linux (mostly), but I'm going to learn Godot first and I'll learn those later. </p><p>So, without further ado, here is the announcement: </p><p>My entry into the 7 day rogue like will be a real-time dungeon crawler. It will be an action game where you attempt to descend into the depths of a dungeon to reach a final boss and defeat him/her. The main mechanic that I hope is somewhat interesting is that each floor of the dungeon will have a timer that starts the instant you get there. At some random amount of time after you reach a floor, gates will open and unleash a mobs of monsters to kill you. The goal here is to spend enough time on each floor to find the powerups, but get out of the floor before the mobs of monsters overpower you. </p><p>The vision I have for the game is a cyberpunk, horror setting. This is mostly because I've been playing some Shadowrun and, after finding it deeply unsatisfying, I started to wonder how I would do it better. </p><p>The visual style of the game is going to use pixelation to evoke the same kind of imaginative aspects that ascii art can produce (and to hide my lack of artistic prowess). This game will probably look more than a little bit like Teleglitch. </p><p>I have a bunch of other thoughts about this game, some of them jotted down, but I haven't put any code or art down yet. I started my attempt on March 5th, 2016 at 22:00 UTC. </p>Zachhttp://www.blogger.com/profile/08359986122518665758noreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-35617061448076459442014-09-30T19:16:00.000-07:002014-10-01T04:37:28.876-07:00Ubuntu Upgrade Woes<p>
I tried to upgrade to the newest LTS release last week. Let's get this out of
the way, <a href="https://xkcd.com/349/">relevant XKCD</a>. It took three solid, long days, which is more than anybody should ever be expected to spend installing an operating system for a desktop system (though I must admit that I spent a full week working through Linux From Scratch in my off time). All said and done, I was left with a (almost) fully functional Ubuntu installation, so I am pretty happy.
</p>
<p>
To put this in context, I have a whole bunch of rants about how much Ubuntu sucks filed away on my
computer, but this will probably be the first one that will actually see the
light of day. The only reason I bring it up is that it seems that I, sort of,
figured out why this was causing me problems and how to fix it. However, I
don't really know of a place to put this. I know what worked for me, but I
really don't understand it fully and I really don't think I am in the position
to give technical advice to anybody.
</p>
<p>
So, I'll get to the short of it with the hopes that anybody in my same shoes
that is frantically Googling about might land on this page. If you:
</p>
<ol class="org-ol">
<li>Are running Ubuntu (or probably any other GNU/Linux that supports EFI boot)
on a MacBook Pro (at least the 6,2 model, but perhaps others that
use hybrid video technology).
</li>
<li>Are having a tough time getting the Nvidia drivers to work (the install but
you end up with a blank screen on the next boot).
</li>
</ol>
<p>
You might be suffering from the same issue I had; you need to ensure that you
are booting in emulated BIOS mode rather than using Apple's EFI. For me, this
means that I need to hold the "Option Key" on boot and hand select the Ubuntu
drive, but Google says that there are other ways to do this.
</p>
<p>
It actually solves one of the big mysteries I've had since starting to use
Ubuntu on the Apple computers: the poor battery life in Ubuntu versus OS X (in
my and my friend's experience this basically cuts the idle lifetime by a factor
of two to three). At least one of the reasons for this poor battery life (and
perhaps the major contributor) is that the video card is stuck in the discrete
Nvidia GPU mode and never switches to the integrated i915 card.
</p>
<p>
This caught me by surprise as I wasn't aware that booting using different
methods would leave the hardware in different states (i.e. boot one way and the
system is stable and usable, boot another way and you will get crappy
performance at best and very likely an install that will crash every time it
tries to start Xorg). It is a shame that Ubuntu picks the unstable EFI way to
set up the booting process… however…
</p>
<p>
You really can't blame Ubuntu for their decision. Apple used a non-standard EFI
method for (at least) this series of MacBook Pros. They also used a
non-standard hybrid video technology based on Optimus but sufficiently different
that none of the bumblebee stuff works, yet. I think people are working on it and Youtube shows some videos with working proof-of-concept graphics switching, but it is a pretty old laptop so I'm not holding my breath.
</p>
<p>
As a side note, while the whole installation debacle should have soured me on
14.04, I have to say that it is extremely well polished compared to
12.04. Of course it could be better, but I absolutely love how Unity looks once
you install a few themes and fiddle with Unity Tweak Tool to bend it to your taste.
</p>
<p>
Also, I know many people that would ask, "was it worth it?" Is it worth it to work for three days to get a GNU/Linux installation up and running? Absolutely. I am vastly more productive when working within GNU/Linux. Should it have taken less time? Absolutely, and that is the real question to ask. Would another distribution provide similar features for much less investment?
</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-80165445435316684862014-04-01T12:31:00.001-07:002014-04-01T13:02:47.874-07:00Some Emacs hacks for GDB and other stuff<p>
I am fighting with GDB in Emacs today. Thought I would share a few hacks that
make things more livable. These get hackier as you go, so… be warned.
</p>
<p>
First, GDB in many windows mode makes a bunch of dedicated windows. This can be
pretty annoying. In fact, dedicated windows in general can be pretty annoying.
If I want to change the buffer of a window, don't you dare stop me. Emacs Wiki
has some <a href="http://www.emacswiki.org/emacs/GDB-MI">advice code</a> that allows you to disable the setting of dedicated windows
in GDB startup (bottom of the page). But to be clear, this is a problem with
the Emacs interface, not the GDB interface. The GDB interface has a good reason
to not want those buffers to change, and it is annoying to use it if they do
change. The problem is when I know that I really do want these to change but
Emacs makes me jump through hoops to do it. So, let's fix the underlying
problem. Here is a bit of code to add to your init files that will allow you to
change buffers even if they are dedicated.
</p>
<div class="org-src-container">
<pre class="src src-elisp">(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">undedicate-window</span> (<span style="color: #7aa6da;">&optional</span> window)
(interactive)
(set-window-dedicated-p (or window (get-buffer-window)) nil))
<span style="color: #969896; font-style: italic;">;; </span><span style="color: #969896; font-style: italic;">Removing annoying dedicated buffer nonsense</span>
(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">switch-to-buffer!</span> (buffer-or-name <span style="color: #7aa6da;">&optional</span> norecord force-same-window)
<span style="color: #c397d8;">"Like switch-to-buffer but works for dedicated buffers \(though</span>
<span style="color: #c397d8;">it will ask first)."</span>
(interactive
(list (read-buffer-to-switch <span style="color: #70c0b1;">"Switch to buffer: "</span>) nil 'force-same-window))
(<span style="color: #b9ca4a;">when</span> (and (window-dedicated-p (get-buffer-window))
(yes-or-no-p <span style="color: #70c0b1;">"This window is dedicated, undedicate it? "</span>))
(undedicate-window))
(switch-to-buffer buffer-or-name norecord force-same-window))
</pre>
</div>
<p>
I just set a global key binding of <code>(kbd "C-x b")</code> to <code>switch-to-buffer!</code>
(actually I use a global minor mode to keep track of all of my keybindings, but
the result is the same). This will now act exactly like <code>switch-to-buffer</code>
unless the window is dedicated, in which case it will ask if you want to
"undedicate" the window first. Now Emacs wont reuse these buffers willy nilly,
but you can still do what you think is best.
</p>
<p>
Second, dedicated windows are so convenient (now that they are convenient to
undedicate) that you might find that you want to start setting the dedicated
flag on random windows that you don't want Emacs to change. So here is a
function for that. If you want a dedicated completion window, well, just set it
on that window and you won't have to worry about it getting taken over by some
other Emacs pop-up.
</p>
<div class="org-src-container">
<pre class="src src-elisp">(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">toggle-window-dedication</span> (<span style="color: #7aa6da;">&optional</span> window)
(interactive)
(<span style="color: #b9ca4a;">let</span> ((window (or window (get-buffer-window))))
(set-window-dedicated-p window (not (window-dedicated-p window)))))
(global-set-key (kbd <span style="color: #70c0b1;">"C-x d"</span>) 'toggle-window-dedication)
</pre>
</div>
<p>
Third, I really hate that performing any act in GUD tends to make the source
buffer you are working with jump back to the execution point. This is a problem
if you are setting several breakpoints, or printing out several values from the
source file. Thus I came up with this hack (and this really is a hack) to make
this problem go away.
</p>
<div class="org-src-container">
<pre class="src src-elisp">(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">nice-gud-print</span> (arg)
(interactive <span style="color: #70c0b1;">"p"</span>)
(<span style="color: #b9ca4a;">save-excursion</span>
(gud-print arg)
(sleep-for .1)))
(global-set-key (kbd <span style="color: #70c0b1;">"C-x C-a C-p"</span>) 'nice-gud-print)
(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">nice-gud-break</span> (arg)
(interactive <span style="color: #70c0b1;">"p"</span>)
(<span style="color: #b9ca4a;">save-excursion</span>
(gud-break arg)
(sleep-for .1)))
(global-set-key (kbd <span style="color: #70c0b1;">"C-x C-a C-b"</span>) 'nice-gud-break)
(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">nice-gud-tbreak</span> (arg)
(interactive <span style="color: #70c0b1;">"p"</span>)
(<span style="color: #b9ca4a;">save-excursion</span>
(gud-tbreak arg)
(sleep-for .1)))
(global-set-key (kbd <span style="color: #70c0b1;">"C-x C-a C-t"</span>) 'nice-gud-tbreak)
</pre>
</div>
<p>
The <code>sleep-for</code> call is necessary to make <code>save-excursion</code> actually work. My
guess here is that GUD queues requests and then executes them later. So without
the sleep, my call to GUD returns, and with it the <code>save-excursion</code> environment
exits, long before GUD processes the command and then resets the view to the
execution point. Not pretty, but it works for me at least.
</p>
<p>
Lastly, I find that it is helpful to have a key binding for
<code>gdb-restore-windows</code>. This way you can easily jump to a particular window,
make the buffer full screen, and then return to the debugger view later.
However, if you like to use a vertically split screen like I do (i.e. you like
80 column width programs), it is often even better to have a toggle between just
the two center windows and the full debugger view. So, here is a function to do
that:
</p>
<div class="org-src-container">
<pre class="src src-elisp">(<span style="color: #b9ca4a;">defun</span> <span style="color: #e78c45;">gdb-windows-toggle</span> (<span style="color: #7aa6da;">&optional</span> full-restore)
(interactive <span style="color: #70c0b1;">"P"</span>)
(<span style="color: #b9ca4a;">let</span> ((window-tree (first (window-tree))))
(<span style="color: #b9ca4a;">cond</span> (full-restore
(gdb-restore-windows))
((and (listp window-tree)
(= (length window-tree) 5))
(<span style="color: #b9ca4a;">let</span> ((buffers (<span style="color: #b9ca4a;">if</span> (listp (fourth window-tree))
(mapcar 'window-buffer
(rest (rest (fourth window-tree))))
(list (window-buffer (fourth window-tree)))))
(first-selected (or (windowp (fourth window-tree))
(eql (first (window-list))
(third (fourth window-tree))))))
(delete-other-windows)
(<span style="color: #b9ca4a;">when</span> (> (length buffers) 1)
(split-window-horizontally))
(cl-loop for buffer in buffers
for window in (window-list)
do (<span style="color: #b9ca4a;">progn</span> (undedicate-window window)
(set-window-buffer window buffer)))
(<span style="color: #b9ca4a;">unless</span> first-selected
(select-window (second (window-list))))))
((or (windowp window-tree)
(and (= (length window-tree) 4)
<span style="color: #969896; font-style: italic;">;; </span><span style="color: #969896; font-style: italic;">horizontal split</span>
(not (first window-tree))
<span style="color: #969896; font-style: italic;">;; </span><span style="color: #969896; font-style: italic;">No further splits</span>
(windowp (third window-tree))
(windowp (fourth window-tree))))
(<span style="color: #b9ca4a;">let</span> ((current-buffers
(<span style="color: #b9ca4a;">if</span> (windowp window-tree)
(list (window-buffer window-tree))
(mapcar 'window-buffer (rest (rest window-tree)))))
(first-selected (or (windowp window-tree)
(eql (first (window-list))
(third window-tree)))))
(gdb-restore-windows)
(<span style="color: #b9ca4a;">let</span> ((windows (rest (rest (fourth (first (window-tree)))))))
(<span style="color: #b9ca4a;">when</span> (= (length current-buffers) 1)
(delete-window (second windows)))
(cl-loop for buffer in current-buffers
for window in windows
do (<span style="color: #b9ca4a;">progn</span> (undedicate-window window)
(set-window-buffer window buffer)))
(<span style="color: #b9ca4a;">if</span> first-selected
(select-window (first windows))
(select-window (second windows))))))
(t <span style="color: #969896; font-style: italic;">;; </span><span style="color: #969896; font-style: italic;">If all else fails, just restore the windows</span>
(gdb-restore-windows)))))
(global-set-key (kbd <span style="color: #70c0b1;">"C-c g"</span>) 'gdb-windows-toggle)
</pre>
</div>
<p>
That is long and ugly, and probably could be made much simpler, but it does the
trick and does it pretty well. Maybe if these really work out I can get someone
involved with Emacs to include some of these little hacks (cleaned up of
course). It would be nice to deal with the fact that GDB is fundamentally
broken for me right now, but… we'll see where those bug reports go.
</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-4484164120308063812014-01-13T21:08:00.003-08:002014-01-16T03:19:07.423-08:00Visualization of the Game of LifeWorking with visualization a bit today and needed a system to visualize, so I did the Game of Life and it turned out pretty, so I decided I should share.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/vsK69m7aqd4?feature=player_embedded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
The game is played in the XY plane. Older generations are moved down in
Z and their color is darkened by 20%. Each system is started with
random live and dead cells. The first runs are with free boundary
conditions while after around <a href="https://www.youtube.com/watch?v=vsK69m7aqd4&t=2m50s" target="_blank">2:50</a>
I switch to a toroidal system of size 20 in X and Y. You can clearly
see gliders at several places in the video, for instance there is one at
the <a href="https://www.youtube.com/watch?v=vsK69m7aqd4&t=2m0s" target="_blank">2:00</a> mark.<br />
<br />
If you care, the simulation and visualization were all done from inside a Lisp session and takes around 90 lines of code (including blank ones) to get this effect. The stuttering frame rate is due to the screen capturing software, RecordMyDesktop. I'm not sure how to do this better other than grabbing the frames from the OpenGL display buffer, writing them to a bitmap file, and making my own video with FFMPEG (which is what I do for presentations).<br />
<br />
I need to figure out how to make this a live wallpaper for my phone...Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-32069520549597122492013-10-25T17:42:00.000-07:002013-10-25T17:42:43.227-07:00CL-Libsvm Usage<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>CL-libsvm usage</title>
<!-- 2013-10-25 Fri 16:49 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
<meta name="generator" content="Org-mode"/>
<meta name="author" content="Zach Kost-Smith"/>
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
.title { text-align: center; }
.todo { font-family: monospace; color: red; }
.done { color: green; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.right { margin-left: auto; margin-right: 0px; text-align: right; }
.left { margin-left: 0px; margin-right: auto; text-align: left; }
.center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre.src {
position: relative;
overflow: visible;
padding-top: 1.2em;
}
pre.src:before {
display: none;
position: absolute;
background-color: white;
top: -10px;
right: 10px;
padding: 3px;
border: 1px solid black;
}
pre.src:hover:before { display: inline;}
pre.src-sh:before { content: 'sh'; }
pre.src-bash:before { content: 'sh'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-R:before { content: 'R'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-java:before { content: 'Java'; }
pre.src-sql:before { content: 'SQL'; }
table { border-collapse:collapse; }
td, th { vertical-align:top; }
th.right { text-align: center; }
th.left { text-align: center; }
th.center { text-align: center; }
td.right { text-align: right; }
td.left { text-align: left; }
td.center { text-align: center; }
dt { font-weight: bold; }
.footpara:nth-child(2) { display: inline; }
.footpara { display: block; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
/*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart The following is the entire license notice for the
JavaScript code in this tag.
Copyright (C) 2012 Free Software Foundation, Inc.
The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version. The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU GPL for more details.
As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.
@licend The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js">
<!--/*--><![CDATA[/*><!--*/
MathJax.Hub.Config({
// Only one of the two following lines, depending on user settings
// First allows browser-native MathML display, second forces HTML/CSS
// config: ["MMLorHTML.js"], jax: ["input/TeX"],
jax: ["input/TeX", "output/HTML-CSS"],
extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",
"TeX/noUndefined.js"],
tex2jax: {
inlineMath: [ ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],
skipTags: ["script","noscript","style","textarea","pre","code"],
ignoreClass: "tex2jax_ignore",
processEscapes: false,
processEnvironments: true,
preview: "TeX"
},
showProcessingMessages: true,
displayAlign: "center",
displayIndent: "2em",
"HTML-CSS": {
scale: 100,
availableFonts: ["STIX","TeX"],
preferredFont: "TeX",
webFont: "TeX",
imageFont: "TeX",
showMathMenu: true,
},
MMLorHTML: {
prefer: {
MSIE: "MML",
Firefox: "MML",
Opera: "HTML",
other: "HTML"
}
}
});
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<p>
At work we decided that we needed to use a bit of machine learning to automate a
problem. I recommended using LIBSVM as it very established (read old with many
bindings available). I decided to see what was involved in using it this
morning, but found that it took an embarrassingly long time to get it working
like I expected it to out of the box. This is my short-coming, I had forgotten
too much of the machine learning that I used to know. But this post will
hopefully help others get it working more quickly.
</p>
<p>
First, SVMs are pretty versatile, and there are a lot of choices that you can
make when you start using LIBSVM. It is often not clear what you should use for
what task, and I don't have the expertise to tell you what is best. For that
information, you should check out <a href="http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf">this guide by the library's author</a>. What I
will show here is a quick and dirty approach.
</p>
<p>
I will be using Gabor Melis' bindings for LIBSVM. They work well enough, but
they will issue many warnings when you load them up and use them as they use a
now deprecated syntax of CFFI. Just be aware.
</p>
<p>
We will be using a radial basis function (RBF) kernel to model the <a href="http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/a1a">"a1a"
training data</a> and <a href="http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/a1a.t">test data</a> that is available on the <a href="http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/">LIBSVM website</a>. Already
this is a bit odd, as the LIBSVM people have split their data such that ~5% is
in the training data set while ~95% is in the test data set. This is probably
due to the somewhat expensive nature of SVMs? But, whatever the case, we will
stick with it.
</p>
<p>
Here is a simple procedure to read in the data:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(ql:quickload '(<span style="color: #b0c4de;">:iterate</span> <span style="color: #b0c4de;">:cl-ppcre</span> <span style="color: #b0c4de;">:alexandria</span>))
(use-package <span style="color: #b0c4de;">:iterate</span>)
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">parse-data-file</span> (file)
<span style="color: #ffa07a;">"Read in a data-file, return list of target values with input as a sparse</span>
<span style="color: #ffa07a;">vector suitable for cl-libsvm."</span>
(iter (for line <span style="color: #b0c4de;">:in-file</span> file <span style="color: #b0c4de;">:using</span> 'read-line)
(collecting
(list (read-from-string line)
(<span style="color: #00ffff;">let</span> ((result nil))
(<span style="color: #00ffff;">ppcre:do-matches-as-strings</span> (match <span style="color: #ffa07a;">"\\w+:\\w+"</span> line)
(push
(apply 'cons (mapcar 'read-from-string
(<span style="color: #00ffff;">let</span> ((separator (position #\: match)))
(list
(subseq match 0 separator)
(subseq match (+ 1 separator))))))
result))
(coerce (reverse result) 'vector))))))
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">randomize-order</span> (data)
<span style="color: #ffa07a;">"Return a random permutation of the data."</span>
(alexandria:shuffle (copy-seq data)))
</pre>
</div>
<p>
The <code>parse-data-file</code> returns a vector where each element is a line in the data
file mapped into a list of the form <code>(target-val sparse-vector-input)</code>. A
sparse vector is a vector where each element is a cons cell containing an index
as its <code>car</code> and a value as its <code>cdr</code>.
</p>
<p>
We need to further divide the testing data so that we have a data set that we
can use to validate the parameters that the RBF SVM uses (the "validation" set)
while we use the rest of the test set to determine the accuracy of the model
(the "test" set). We could just cut the training data in half, but that would make our validation calculations very slow, and as we will see is a moment, this becomes the bottleneck of the calculation. I have chosen my validation set to be 2000 point. Whatever size you choose will be a trade off between accuracy and speed. Having 2000 points in your validation set is about my limit when it comes to playing around at the REPL (I would choose something higher if it showed benefits for the models accuracy). If we are dividing the data, we must first
first randomize it to ensure that no structure of how the data was collected shows up
in the analysis. This can be done with the <code>randomize-order</code> function above and
a couple calls to <code>subseq</code>.
</p>
<div class="org-src-container">
<pre class="src src-lisp">(<span style="color: #00ffff;">let</span> ((test-data (randomize-order (parse-data-file #p<span style="color: #ffa07a;">"~/Desktop/a1a.t"</span>))))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*validation-set*</span> (subseq test-data 0 2000))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*test-set*</span> (subseq test-data 2000)))
</pre>
</div>
<p>
Now, to get into the nitty-gritty of CL-Libsvm. First, you'll need to install
it, and it is not available in Quicklisp yet. So, clone it from Gabor's Git
repo. Naturally you will also need to have LIBSVM installed (you don't actually
need <code>libsvm-dev</code> or <code>libsvm-tools</code>, but why not have them anyway):
</p>
<div class="org-src-container">
<pre class="src src-sh"><span style="color: #b0c4de;">cd</span> ~/quicklisp/local-projects
git clone http://quotenil.com/git/cl-libsvm.git
<span style="color: #ff7f24;"># </span><span style="color: #ff7f24;">Install LIBSVM if needed</span>
sudo aptitude install libsvm3 libsvm-dev libsvm-tools
</pre>
</div>
<p>
CL-Libsvm is basically structured like LIBSVM, so the same documentation applies
here. We must first create a <i>problem</i> which contains inputs and the expected
outputs, then create a <i>parameter structure</i> that contains the parameters that
define how the SVM operates (numerical constants as well as the type of SVM and
kernel), and finally combine these two into a <i>model</i> which can be used to make
predictions.
</p>
<p>
This can be done easily enough for any particular RBF parameters \(C\) and
\(\gamma\).
</p>
<div class="org-src-container">
<pre class="src src-lisp">(ql:quickload <span style="color: #b0c4de;">:cl-libsvm</span>)
(<span style="color: #00ffff;">let</span> ((data (parse-data-file #p<span style="color: #ffa07a;">"~/Desktop/a1a"</span>)))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*problem*</span> (libsvm:make-problem (map 'vector 'first data)
(map 'vector 'second data))))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*parameter*</span> (libsvm:make-parameter <span style="color: #b0c4de;">:c</span> c <span style="color: #b0c4de;">:gamma</span> gamma))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*model*</span> (libsvm:train *problem* *parameter*))
</pre>
</div>
<p>
But we want to do this for many different values of \(C\) and \(\gamma\) in order to
find what parameters give us the best performance. We could do several things
to find the optimum values. We will be following the LIBSVM procedure and just
search the parameter space on a grid. We should note from the manual that it is
probably in our best interests to search in \(\log C\) and \(\log \gamma\).
</p>
<div class="org-src-container">
<pre class="src src-lisp">(<span style="color: #00ffff;">let</span> ((data (parse-data-file #p<span style="color: #ffa07a;">"~/Desktop/a1a"</span>)))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*problem*</span> (libsvm:make-problem (map 'vector 'first data)
(map 'vector 'second data))))
(<span style="color: #00ffff;">defparameter</span> <span style="color: #eedd82;">*optimization-grid*</span>
(iter <span style="color: #b0c4de;">:outer</span>
(for log-c <span style="color: #b0c4de;">:from</span> 1.5 <span style="color: #b0c4de;">:to</span> 3.5 <span style="color: #b0c4de;">:by</span> .1)
(iter (for log-gamma <span style="color: #b0c4de;">:from</span> -5 <span style="color: #b0c4de;">:to</span> -3.5 <span style="color: #b0c4de;">:by</span> .1)
(in <span style="color: #b0c4de;">:outer</span> (collecting
(list* log-c
log-gamma
(<span style="color: #00ffff;">let*</span> ((params (libsvm:make-parameter
<span style="color: #b0c4de;">:c</span> (exp log-c)
<span style="color: #b0c4de;">:gamma</span> (exp log-gamma)))
(model (libsvm:train *problem* params)))
(list (quality model *validation-set* log-c log-gamma)
model))))))))
</pre>
</div>
<p>
Note that there is a missing function here. We never defined quality. This
function is meant to take a model and some testing data and determine a measure
of how good the model is performing. For this I chose to use the <a href="https://en.wikipedia.org/wiki/Matthews_correlation_coefficient">Matthews
Correlation Coefficient</a> with the threshold for the prediction set to \(0.5\).
</p>
<div class="org-src-container">
<pre class="src src-lisp">(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">logistic</span> (x)
(/ (+ 1 (exp (- x)))))
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">quality</span> (model test-data log-c log-gamma)
<span style="color: #ffa07a;">"Use the Matthews Correlation Coefficient to measure how well the model does"</span>
(iter (for (target input) <span style="color: #b0c4de;">:in</span> test-data)
(<span style="color: #00ffff;">let</span> ((p (<span style="color: #00ffff;">if</span> (< 0.5 (logistic (libsvm:predict model input)))
1 -1)))
(<span style="color: #00ffff;">cond</span> ((and (= p 1) (/= target p))
(summing 1 <span style="color: #b0c4de;">:into</span> false-positives))
((and (= p -1) (/= target p))
(summing 1 <span style="color: #b0c4de;">:into</span> false-negatives))
((and (= p 1) (= target p))
(summing 1 <span style="color: #b0c4de;">:into</span> true-positives))
((and (= p -1) (= target p))
(summing 1 <span style="color: #b0c4de;">:into</span> true-negatives))))
(finally
(<span style="color: #00ffff;">let</span> ((quality
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Compute quality of model</span>
(<span style="color: #00ffff;">if</span> (= 0 (- (* true-positives true-negatives)
(* false-positives false-negatives)))
0d0
(/ (- (* true-positives true-negatives)
(* false-positives false-negatives))
(sqrt
(float
(* (+ true-positives false-positives)
(+ true-positives false-negatives)
(+ true-negatives false-positives)
(+ true-negatives false-negatives))
0d0))))))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Print some output so we know what it's doing</span>
(format
t <span style="color: #ffa07a;">"log-c = ~A, log-gamma = ~A~@</span>
<span style="color: #ffa07a;"> TP = ~A, TN = ~A, FP = ~A, FN = ~A~@</span>
<span style="color: #ffa07a;"> Quality = ~A~%"</span>
log-c log-gamma
true-positives true-negatives false-positives false-negatives
quality)
(<span style="color: #00ffff;">return</span> quality)))))
</pre>
</div>
<p>
When we put this all together and playing around with the ranges of the plots,
we get a plot that looks like this:
</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoEE3y3y6gisz3uE_JraJ85T7p72-Gr10g8zCuEulqwgLStzevA6H47IXbymCDzzl6yir0ZFVuZVRuKS4qYq1t4wkG0TmkOHOlGqzNjThO7tidKZMLdWoTvRQHaOBwyAawQGX8XO2Td0Zb/s1600/maps.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoEE3y3y6gisz3uE_JraJ85T7p72-Gr10g8zCuEulqwgLStzevA6H47IXbymCDzzl6yir0ZFVuZVRuKS4qYq1t4wkG0TmkOHOlGqzNjThO7tidKZMLdWoTvRQHaOBwyAawQGX8XO2Td0Zb/s640/maps.png" /></a></div>
<p>
From this we can tell that there is likely some kind of optimum around
\(\log C = 2.10\) and \(\log \gamma = -4.27\).
</p>
<p>
You might wonder how I was able to determine, looking at those blocky heat maps,
where that tiny maximum was. While you can do what LIBSVM docs suggest and move
to finer and finer grids to find optimal points, I find this pretty annoying,
and finicky. I opted to use some, as yet unreleased, bindings for the NLOpt
optimization library. With NLOpt we can do a global optimization followed by a
local optimization, which requires next to zero human intervention and finds a
pretty good optimum that I doubt I would be able to otherwise. (Small caveat here, it is entirely possible that the rough nature of my MCC heat map is merely an artifact of the small validation set size. I don't have the patience to test this for a silly example)
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Global optimization (better grab a snack)</span>
(nlopt:nlopt-apply
(<span style="color: #00ffff;">lambda</span> (log-c log-gamma)
(<span style="color: #00ffff;">let*</span> ((params (libsvm:make-parameter
<span style="color: #b0c4de;">:c</span> (exp log-c)
<span style="color: #b0c4de;">:gamma</span> (exp log-gamma)))
(model (libsvm:train *problem* params)))
(- (quality model *validation-set*))))
'(1 1)
<span style="color: #b0c4de;">:nlopt-gn-crs2-lm</span>
<span style="color: #b0c4de;">:lower-bounds</span> '(-5 -5)
<span style="color: #b0c4de;">:upper-bounds</span> '(7 7)
<span style="color: #b0c4de;">:abs-xtol</span> 1d-1)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Fit parameters = (2.071364331304816d0 -4.265683211751565d0)</span>
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Validation MCC = -0.5509856550306286d0</span>
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Local optimization (this should be quick)</span>
(nlopt:nlopt-apply
(<span style="color: #00ffff;">lambda</span> (log-c log-gamma)
(<span style="color: #00ffff;">let*</span> ((params (libsvm:make-parameter
<span style="color: #b0c4de;">:c</span> (exp log-c)
<span style="color: #b0c4de;">:gamma</span> (exp log-gamma)))
(model (libsvm:train *problem* params)))
(- (quality model *validation-set*))))
'(2.071364331304816d0 -4.265683211751565d0)
<span style="color: #b0c4de;">:nlopt-ln-bobyqa</span>
<span style="color: #b0c4de;">:lower-bounds</span> '(-5 -5)
<span style="color: #b0c4de;">:upper-bounds</span> '(7 7)
<span style="color: #b0c4de;">:abs-xtol</span> 1d-5)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Fit parameters = (2.096969188326027d0 -4.268553108908674d0)</span>
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Validation MCC = -0.5522135970232868d0</span>
(<span style="color: #00ffff;">let*</span> ((params (libsvm:make-parameter
<span style="color: #b0c4de;">:c</span> (exp 2.096969188326027d0)
<span style="color: #b0c4de;">:gamma</span> (exp -4.268553108908674d0)))
(model (libsvm:train *problem* params)))
(quality model *test-set*))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Test set MCC = 0.5497032935038368d0</span>
</pre>
</div>
<p>
This gives the optimum at \(C = 2.10\) and \(\gamma = -4.27\) and a Matthew's
Correlation Coefficient of \(0.55\) (measured against the test set, naturally).
</p>
</div>
</body>
</html>
Unknownnoreply@blogger.com5tag:blogger.com,1999:blog-7788284466297989064.post-19664145732685375082013-07-31T06:14:00.000-07:002013-08-02T16:12:33.940-07:00Rudel Survival Guide<div class="outline-text-2" id="text-1">
<p>
We are gearing up for our collaborative effort for ICFP and so I figured it
might be nice to write out a little "how to make it work" guide for Rudel, the
collaborative editing framework for Emacs. To get this out of the way first,
Rudel doesn't work out of the box. In order to use it, we had to hack a bit on
the source to correct what we can only guess are legitimate errors. That said,
I certainly don't have the expertise on the system in order to dictate the
correct way to solve these problem.
</p>
<p>
As a note, throughout this contest our setup will be:
</p>
<ul class="org-ul">
<li>Rudel v0.3
</li>
<li>Obby backend
</li>
<li>TCP transport
</li>
<li>Port 6522
</li>
<li>not using the built in Rudel/Obby encryption
</li>
<li>all connections must be tunneled over SSH (for encryption/access control)
</li>
<li>No global or user passwords
</li>
</ul>
<p>
The first step for using Rudel is to, naturally, install Rudel. If you have
Emacs v24, you may use the package manager via <code>M-x package-list-packages</code>.
This will make sure that it also gets any dependencies, however I don't think
there are any that aren't already part of Emacs. If you are not using Emacs
v24, you will need to install <code>package.el</code> (and this will actually be useful as
I believe it will have to track down some dependencies). This can be done like
this:
</p>
<div class="org-src-container">
<pre class="src src-sh"><span style="color: #b0c4de;">cd</span> .emacs.d
wget http://repo.or.cz/w/emacs.git/blob_plain/1a0a666f941c99882093d7bd08ced15033bc3f0c:/lisp/emacs-lisp/package.el
</pre>
</div>
<p>
Then from Emacs, <code>M-x load-file</code> that <code>package.el</code> file. Then you can use
continue as if you were using v24 (except where noted).
</p>
<p>
Rudel is available via the the Marmalade repository. In order to enable the
Marmalade repository, you should add something like this early in your <code>.emacs</code>
file:
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">(load "~/.emacs.d/package.el") ;; If not v24</span>
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Load up the new package manager</span>
(<span style="color: #00ffff;">require</span> '<span style="color: #7fffd4;">package</span>)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Add the Marmalade repo</span>
(add-to-list 'package-archives
'(<span style="color: #ffa07a;">"marmalade"</span> . <span style="color: #ffa07a;">"http://marmalade-repo.org/packages/"</span>) t)
(package-initialize)
</pre>
</div>
<p>
The install/compile should seemingly complete without any issues. (If you are
not on v24, then there might be an issue with package displaying the info page
of certain packages, Rudel amongst them. Instead of using <code>M-x
package-list-packages</code>, use <code>M-x package-install</code> and specify "rudel" when it
asks).
</p>
<p>
Now the <del>trouble</del> fun begins.
</p>
</div>
<div id="outline-container-sec-1-1" class="outline-3">
<h3 id="sec-1-1"><span class="section-number-3">1.1</span> We broke your Emacs</h3>
<div class="outline-text-3" id="text-1-1">
<p>
Try closing and restarting Emacs. On your next start, Emacs will fail to read
your <code>.emacs</code> file with an error like:
</p>
<blockquote>
<p>
Symbol's function definition is void: eieio-defclass-autoload
</p>
</blockquote>
<p>
This is because there are some bugs in Rudel that make it not load properly. My
solution is to not use the standard method of loading Rudel. The first order of
business is stopping it from loading the correct but broken way via the package
manager. Go into the shell and move the rudel directory somewhere where it
cannot be found by the package manager:
</p>
<div class="org-src-container">
<pre class="src src-sh"><span style="color: #b0c4de;">cd</span> .emacs.d
mv elpa/rudel-0.3 ./
</pre>
</div>
<p>
Now Emacs should read your <code>.emacs</code> without issue (because it no longer is
trying to load Rudel).
</p>
<p>
The next order of business, we want to be able to load and use Rudel. In order
to do this, we will run Rudel's compile script. Do a <code>M-x load-file</code> on
<code>.emacs.d/rudel-0.3/rudel-compile.el</code>. This will compile and generate some
files, most importantly for our purposes, it will generate <code>rudel-loaddefs.el</code>.
Perform a <code>M-x load-file</code> on <code>.emacs.d/rudel-0.3/rudel-loaddefs.el</code> and Rudel
should be operational. Try it out. Use <code>M-x rudel-host-session</code> to start a
session (protocol obby, transport tcp, port 6522). Then join that session via
<code>M-x rudel-join-session</code>. Try publishing a buffer with <code>M-x
rudel-publish-buffer</code>. This should all work.
</p>
<p>
We want to make this permanent, so we should add something like:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(load-file <span style="color: #ffa07a;">"~/.emacs.d/rudel-0.3/rudel-loaddefs.el"</span>)
</pre>
</div>
<p>
…to our <code>.emacs</code> file after the <code>(package-initialize)</code> statement.
</p>
<p>
Look, I know this is extremely hackish, but I think it will work for everybody.
It is the only way I have consistently been able to get things working.
</p>
</div>
</div>
<div id="outline-container-sec-1-2" class="outline-3">
<h3 id="sec-1-2"><span class="section-number-3">1.2</span> Joining and leaving sessions</h3>
<div class="outline-text-3" id="text-1-2">
<p>
So, as best I can see, this is the status of this functionality in Rudel: you
can join sessions and you can leave, but as far as the server cares, you can
never leave. This doesn't seem like too much of a problem at first, but here is
how problems start to manifest.
</p>
<ol class="org-ol">
<li>A username must be unique: This means that each time you log in, you have to
pick a unique name, not the one you used last time. This manifests as a lot
of "smithzv", "smithzv2", "smithzv3", etc. Luckily, you shouldn't be
disconnected often.
</li>
<li>A color must be unique at login time. This one isn't as bad as you can
change colors once you are in the session using <code>rudel-change-color</code>. This
means that a good practice is to log in and pick a garish and otherwise
infrequently used color and then immediately change it to something more
appropriate. No need to worry about conflicts after you have logged in.
</li>
</ol>
</div>
</div>
<div id="outline-container-sec-1-3" class="outline-3">
<h3 id="sec-1-3"><span class="section-number-3">1.3</span> Undo and Rudel</h3>
<div class="outline-text-3" id="text-1-3">
<p>
So, one of the biggest problems that I have with collaborative editing in Rudel
is that undo are treated very literally. I you undo, you implicitly expect it
to apply to your code. However, with Rudel, where someone could be editing
somewhere else in the file, undo is happy to go about undoing their work as they
type rather than the edits you just made.
</p>
<p>
The end result is that in a collaborative editing environment, undo is a very
dangerous thing; doubly so when undo means what it does in Emacs land (i.e. you
can redo by undoing an undo). Basically, if you are using Rudel, you probably
should not be using undo, at all. This is a pretty tall order if you have
deeply internalized undo into your editing commands (as I have).
</p>
<p>
In strikes me that a helpful heuristic would be to undo only within a region
that contains only your edits (or even using something like multiple-regions to
allow for undo of anything that you have edited but not things that others
have). This means that if you are the only person editing a buffer, undo works
exactly as expected, but if there are others editing the buffer, it will only
undo your edits. Note that this isn't always what you want.
</p>
<p>
However, I'm not sure that such a heuristic is possible (or more likely, it is
possible but is hard to do). I'll take a look. It seems that for safe, useful
undoing, you need to tell everybody that is working on that buffer that they
need to stop what they are doing so you may perform your undos.
</p>
<p>
I realize that other undo systems can be used with Emacs. For instance, there
is Undo-Tree. I am not sure how well these work (or really how they work).
Perhaps someone who is better versed in these tools can enlighten us.
</p>
</div>
</div>
<div id="outline-container-sec-1-4" class="outline-3">
<h3 id="sec-1-4"><span class="section-number-3">1.4</span> When things go wrong</h3>
<div class="outline-text-3" id="text-1-4">
<p>
There are times when, try as it might, Rudel screws up and the files become out
of sync. This happens fairly infrequently, thank goodness, but when it does,
Rudel does not handle this gracefully. There is no "resync" function that I can
see. This means that if you find that your buffer says one thing, but someone
elses says something else (this usually manifests a what looks like a typo, but
if you fix it, another person goes back and changes it back to its typo state),
you will have do something pretty drastic in order to get Rudel to work
correctly again. There are a couple of things that must work, but they both are
pretty annoying:
</p>
<ol class="org-ol">
<li>Ditch this buffer, have everybody unsubscribe, rename the buffer so it will
share under a different name, then republish. This way everything has
started fresh with this buffer.
</li>
<li>Restart the entire Rudel session.
</li>
</ol>
<p>
Of course, the first method is preferred to the second.
</p>
</div>
</div>
<div id="outline-container-sec-1-4" class="outline-3">
<h3 id="sec-1-5"><span class="section-number-3">1.5</span> Dealing with Annoying Colors</h3>
<div class="outline-text-3" id="text-1-5">
<p>
If you start using Rudel, sometimes a collaborator will
pick a color that doesn't work with your theme or general aesthetic. Luckily,
there is something you can do about it even if they refuse to change their color (or are perhaps away from keyboard), you can turn off all coloring by author.
Simply specialize the variable <code>rudel-overlay-author-display</code> (set it to <code>nil</code>)
and no more colors. This is pretty necessary right now because Rudel is ignorant of the difference between light and dark themes. Thus two locally appropriate choices might be completely inappropriate for the remote party.
</p>
</div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-9939113911961077082013-07-25T11:08:00.000-07:002013-07-30T11:02:54.073-07:00A Bit About Ubuntu Edge<p>
A couple days ago, Canonical announced a crowd funding campaign for the <a href="http://www.indiegogo.com/projects/ubuntu-edge">Ubuntu
Edge</a>, a phone sized device that is able to function as a phone but is firmly
designed to be a PC replacement. Just in case someone stumbles on this page
after finding such crappy reporting <a href="http://www.guardian.co.uk/technology/2013/jul/23/ubuntu-edge-crowdfunding-analysis">as this</a>, here is the deal with Ubuntu Edge
as I see it: The Ubuntu Edge is about shaping the future.
</p>
<p>
Now, it is no secret that I like Canonical, one of the only companies fighting
for (and throwing money at) GNU/Linux on the desktop. Frankly, despite recent
missteps in quality control and their tendency to not go with 100% Free
Software, I think they are doing more for the Free Software Movement than
basically anybody else out there. But I have to say that Ubuntu Edge, and it's
associated crowd funding campaign, is a particular point of brilliance for the
company.
</p>
<p>
Canonical has been working for the last few years on something they call
converged computing. The idea is to have every consumer electronic centered
around a screen controlled on a very fundamental level by one device (one device
that happens to run nearly 100% Free Software). As most of you are aware, every
piece of consumer electronics out there has a small, typically underpowered,
computer in it. The Ubuntu Edge vision is to take all of those computers out of
the electronics and simply have the manufacturers build screens with an HDMI
port and power supply attached. For all of the computation, something like the
Ubuntu Edge will handle it.
</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQzh1Os5Oudk_fmK4Txl9BY7-3eiRO-YWIXGDlYcEmDvssqIgQu8cQVaMbHqht_ZFLzluK45EJLx4SjBs4bNw9AxRKfPX7KV-CXAOIlNswF4c4n2KH5DHshLhVunboOD4PuwnBvzK7Q614/s1600/TOTAL_RECALL_ASH_THORP_WEB_70_71_906.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQzh1Os5Oudk_fmK4Txl9BY7-3eiRO-YWIXGDlYcEmDvssqIgQu8cQVaMbHqht_ZFLzluK45EJLx4SjBs4bNw9AxRKfPX7KV-CXAOIlNswF4c4n2KH5DHshLhVunboOD4PuwnBvzK7Q614/s320/TOTAL_RECALL_ASH_THORP_WEB_70_71_906.jpg" /></a></div>
<p>
The way I see Canonical's end game vision is something much like the technology
seen in the <a href="http://www.imdb.com/title/tt1386703/">Total Recall remake</a> from a few years ago. In this movie, people
have technology that they carry with them (actually implanted inside their body)
and may use any piece of glass as a display for that technology by pressing
their hand against it. Canonical's vision is similar. Computational devices
will be mobile, private, secure, personal device that you carry with you while displays
will be stationary, plentiful, pseudo-public devices you hook into when needed. In such
a world, every hotel room you rent, every office, every coffee shop table, and every room in your house will
have a display and input devices (keyboard and mouse, or touchscreen) and a
cradle to place your "phone" into. The way I see Ubuntu Edge is the way it is
presented, as a taste of the future.
</p>
<p>
But that is not entirely fair. There is one place where the Ubuntu Edge fits
perfectly in the current world. If you have a computer at home and a computer
at work (or if you have one laptop that you use for both and you lug it back and
forth), the Ubuntu Edge makes a lot of sense for you. You should think of the
Ubuntu Edge as a PC tower and UPS that fits in your pocket. There is no need to
sync between different disk drives because you bring your drive with you. If
you have ever emailed a file to yourself, or left your computer on at home so
that you would have SSH access to it in case you needed it, or if you simply
have so much data that you cannot store it in something like Dropbox or some
analogous cloud file storage, an Ubuntu Edge like system is a great fit. In
addition, there is no need to worry about software differences between your
applications and files (no Excel 07 can't read Excel 09 XML files file problems)
or incompatibilities during software development because you bring the hardware
and software with you. If you have ever wasted a few hours or days configuring
a new computer or tweaking a computers configuration, Ubuntu Edge seems like a
useful platform. Canonical isn't the first company to sniff around this idea,
but they seem to be the closest to actually achieving this.
</p>
<p>
An extra benefit of something like Ubuntu Edge is that it solves many problems
that people that value freedom, privacy, and freedom from vendor lock-in have
felt mounting. Ubuntu Edge resonates very well with us freedom loving people as
it is a solution that is centered around a well standardized interface. It
means that anybody can use this with whatever device they like. It is of course
not lost on me that this device will be close to a completely freedom respecting
device. There will probably be proprietary device drivers, but I expect that
user land will be Free as in Freedom. This also resonates with us people that
support competition in the market. Any time we have a technology where any new
inventor can enter the market and leverage it for their invention, my free
market loving self smiles a little bit. Standardized interfaces are great for
competition (e.g. see the Internet).
</p>
<p>
Even further, this also resonates very well with us privacy loving people and
people that haven't drank the "cloud" Kool-Aid. The current solution to the
woes of syncing multiple computers (be they PCs, tablets, phone, or whatever) is
to have something like Dropbox shuffle files around. This is actually a pretty
crappy solution, if we are being honest. Don't get me wrong, it is good for the
world we have constructed, but it is far from optimal. For example, on any
system that I am familiar with, it is not possible to sync installed
applications via something like Dropbox.
</p>
<p>
Of course there is nothing wrong with cloud services in principle, and in many
instances they are extremely convenient for transferring files to friends. I'm
not proposing that we move away from Internet services in total, but I think
there is an argument to be made for only using Internet services for things that
need to be Internet services. The problem is that cloud services are run by
corporations and corporations only have allegiances to their share holders and,
if required by law, the government that they operate under. In addition, in the
world we currently live in corporations tend to also have a disturbing level of
control over "mobile" devices. In this data syncing/sharing scheme there are
many points of weakness when it comes to privacy. By buying into the "cloud",
we have transitioned from the normal state where files that are not shared with
others are basically safe into a world where our files are more vulnerable (to
either attackers, corporations, or government agencies) because we have
implicitly shared them in order to sync them. Something like Ubuntu Edge is a
way out of this, it is a solution for many of the problems that the cloud was
designed to solve. If my files are local (i.e. they are in my pocket) and third
party devices that I interact with are nothing more than a screen with no
general purpose processing capabilities, I have much less to worry about.
</p>
<p>
All of these aspects packed together makes this a pretty awesome project. But
now the brilliant part. By making this a crowd funding campaign, Canonical has
made it clear to the consumers what is possible. I have been hearing rumblings
about a system like this for years, but perhaps the ordinary people out there
have not. This is certainly a way to get the word out. On the flip side, this
tells the manufacturers that there are people that are willing to pay money for
something like this. Just the fact that this crowd funding campaign existed,
regardless of whether it is actually funded, will affect the trajectory of
technology in the future. This is a win-win scenario and it is brilliant, pure
and simple. I would love to see Canonical make their goal and make their phone,
but in my estimation, they have already changed the world for the better.
</p>
<p>
So, no, buying an Ubuntu Edge isn't the best fit for everyone (but to be honest,
neither is a tablet, which try as you might, is a poor platform for anything but
consuming information). Ubuntu Edge doesn't fit in perfectly with the world as
it is. It isn't even designed to fill a gap, or at least not a gap that exists
today. It is designed to be that device that is necessary to make the future
that many of us envision come true. That said, it is priced competitively for
the package that they promise and, for people that lug a laptop back and forth
from work or for people that have a two or more computers that they struggle to
keep in sync (e.g. me), this will be a useful device right now. If I had
$700-830 to spend on a speculative device, I would. The real question is
whether they can actually deliver what they promise.
</p>Unknownnoreply@blogger.com6tag:blogger.com,1999:blog-7788284466297989064.post-83842540247327058732013-07-07T13:16:00.000-07:002013-07-07T13:59:13.427-07:00Automatic Binding Generation With Verrazano<p>
<a href="http://common-lisp.net/project/fetter/">Verrazano</a> is a library for automatically creating Foreign Function Interface
(FFI) bindings for Common Lisp. It is easy to use, as long as it works, and it can save you a
lot of busy work. However, it is not well documented, and the documentation
that is available is incorrect. Hopefully this post will help out people that
don't want to figure it out themselves (including myself in 3 months).
</p>
<p>
As a sample of how to use Verrazano, I'm going to generate a set of bindings for
the <a href="http://ab-initio.mit.edu/wiki/index.php/NLopt">NLopt library from our friends over at MIT</a>. This library is a great tool
for optimization, whether it be minimization/maximization, fitting, or any
optimization as it is very flexible in the constraints that the problem can
have. It puts many of the optimization facilities in GSL to shame. I first
started using it because of its derivative free local optimization routines and
really went on to appreciate it when I realized I needed non-trivial constraints
on the parameters in my model fits (GSL can't even handle trivial ones, really).
</p>
<p>
Up until now, I have been using some hand crafted bindings. This library is
pretty small, so it actually isn't much of a burden to maintain for my purposes.
But let's see how to generate them with Verrazano. We will use the function
<code>generate-binding</code> which takes a list which represents a <i>backend</i>. The only
backend available right now is CFFI, which just happens is a good portable FFI,
so this is okay. To generate the NLopt bindings:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(generate-binding
'(<span style="color: #b0c4de;">:cffi</span>
<span style="color: #b0c4de;">:package-name</span> <span style="color: #b0c4de;">:nlopt-cffi-bindings</span>
<span style="color: #b0c4de;">:input-files</span> (<span style="color: #ffa07a;">"nlopt.h"</span>)
<span style="color: #b0c4de;">:gccxml-flags</span> <span style="color: #ffa07a;">"-I /usr/local/include/"</span>))
</pre>
</div>
<p>
After this, we have a file called "nlopt-cffi-bindings.lisp". These represent a
very low-level interface for the library. It basically gets you to the level of
functionality you would have if programming in C. As such, this could be used
as is, but that wouldn't be very Lispy, would it? I wrapped some of these
utilities and will later post my end results as a proper set of Lispy bindings
on GitHub.
</p>
<p>
This is already very useful, but Verrazano can do much more.
</p>
<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2"></span> Generating GSL Bindings</h2>
<div class="outline-text-2" id="text-1">
<p>
There are already several GSL bindings available for CL (I even have my own
private library that I like). The most popular, and deservedly so, is GSLL.
The shear level of completeness is inspiring considering Liam wrote the bindings
by hand (an admirable amount of work, but in my opinion a bit wasteful). One
thing I don't like about GSLL is that it feels like it was brought just to the
point of usefulness, but no further. Coding with GSLL feels like you are coding
in C. This has changed a bit recently, with the introduction of Antik, but the
library is still more difficult to use than my hand rolled GSL library (in fact,
perhaps I'm dumb or something, but I have yet to actually productively used GSLL
in a project for work or otherwise).
</p>
<p>
But never mind all that, let's make our own:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(generate-binding
(list
<span style="color: #b0c4de;">:cffi</span>
<span style="color: #b0c4de;">:package-name</span> <span style="color: #b0c4de;">:cffi-gsl-bindings</span>
<span style="color: #b0c4de;">:input-files</span> (mapcar #'namestring (directory #p<span style="color: #ffa07a;">"/usr/include/gsl/*.h"</span>))
<span style="color: #b0c4de;">:gccxml-flags</span> <span style="color: #ffa07a;">"-I /usr/include/gsl"</span>
<span style="color: #b0c4de;">:standard-name-transformer-replacements</span>
`(,(cl-ppcre:create-scanner <span style="color: #ffa07a;">"(^gsl_?)"</span>) <span style="color: #ffa07a;">""</span>)))
</pre>
</div>
<p>
This basically looks like the example above but with a few things added. First,
we are including all of the GSL header files. Also, we use the
<code>:standard-name-transformer-replacements</code> option to remove the prefix on GSL
functions using a regular expression. If you are familiar with C, you know that
this prefix is necessary because the C programming language doesn't have a way
to divide the symbol namespace. This means that without these prefixes the
likelihood of a name collision is very high. In Common Lisp we don't have to
worry about this because we have a package system.
</p>
<p>
However, when you run the command above, you get an error and the bindings were
not generated. This is because GSL changed some naming conventions a while back
and we need to explicitly define that we want to use the new (non-backwards
compatible) functions by passing an extra argument to GCCXML. We need to pass
<code>-D GSL_DISABLE_DEPRECATED</code> to GCCXML. Well, let's try it again:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(verrazano:generate-binding
(list
<span style="color: #b0c4de;">:cffi</span>
<span style="color: #b0c4de;">:package-name</span> <span style="color: #b0c4de;">:cffi-gsl-bindings</span>
<span style="color: #b0c4de;">:input-files</span> (mapcar #'namestring (directory #p<span style="color: #ffa07a;">"/usr/include/gsl/*.h"</span>))
<span style="color: #b0c4de;">:gccxml-flags</span> <span style="color: #ffa07a;">"-I /usr/include/gsl -DGSL_DISABLE_DEPRECATED"</span>
<span style="color: #b0c4de;">:standard-name-transformer-replacements</span>
`(,(cl-ppcre:create-scanner <span style="color: #ffa07a;">"(^gsl_?)"</span>) <span style="color: #ffa07a;">""</span>)))
</pre>
</div>
<p>
Bingo, this time it worked. If we look at the binding file we see that
basically all of the stuff is there that we want. However there is a bunch of
stuff that we don't care about and, quite frankly, probably doesn't work.
Indeed, if you define the library and attempt to load that file, then you will
get several errors. Also, the file is some 30 thousand lines long, making it
difficult to track them all down.
</p>
<p>
The errors seem to come in a few different flavors. First, sometimes Verrazano
will find a type that that it doesn't know how to deal with. These are
associated with comments in the generated source file that look like:
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;;; </span><span style="color: #ff7f24;">No entry found for gccxml type "long double" in *GCCXML-FUNDAMENTAL-TYPE->CFFI-TYPE*</span>
</pre>
</div>
<p>
Indeed, long doubles are typically seen as an extension to C and not standard or
necessarily available on every platform, and is certainly not available in CFFI
(maybe someday?). The best way to get around this is to not include those
headers that provide long double support in GSL. But even that doesn't clear it
all up. It turns out that if you also exclude <code>gsl_sys.h</code>, <code>gsl_complex.h</code>,
<code>gsl_types.h</code>, <code>gsl_test.h</code>, and <code>gsl_version.h</code> then it clears all of these
errors up. Which brings up two points:
</p>
<ul class="org-ul">
<li>If there is an error, it might show up as a comment in the generated source
file without so much as a warning at the REPL. This is weird, but it is the
way things are right now. These will typically manifest as errors at load
time.
</li>
<li>Only include the headers that you really need. The headers that we ended up
removing turned out to be ones that we really didn't want or need in the first
place. It takes some time up front to pick the right header files, but it can
save you a pain later.
</li>
</ul>
<div class="org-src-container">
<pre class="src src-lisp">(verrazano:generate-binding
(list
<span style="color: #b0c4de;">:cffi</span>
<span style="color: #b0c4de;">:package-name</span> <span style="color: #b0c4de;">:cffi-gsl-bindings</span>
<span style="color: #b0c4de;">:input-files</span> (remove-if (<span style="color: #00ffff;">lambda</span> (x)
(or (ppcre:scan <span style="color: #ffa07a;">"gsl_sys\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_complex\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_types\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_version\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_test\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"long_double\\.h$"</span> x)))
(mapcar #'namestring (directory #p<span style="color: #ffa07a;">"/usr/include/gsl/*.h"</span>)))
<span style="color: #b0c4de;">:gccxml-flags</span> <span style="color: #ffa07a;">"-I /usr/include/gsl -DGSL_DISABLE_DEPRECATED"</span>
<span style="color: #b0c4de;">:standard-name-transformer-replacements</span>
`(,(cl-ppcre:create-scanner <span style="color: #ffa07a;">"(^gsl_?)"</span>) <span style="color: #ffa07a;">""</span>)))
</pre>
</div>
<p>
Now we run into the next error, case sensitivity. Apparently Verrazano isn't
really designed to handle cases where a function has multiple identifiers that
differ by nothing more than case. Seems like a bad programming practice, but
GSL does it, and Verrazano screws it up, so we have to work around it. One
place where this seems appropriate but unfortunate is with the Bessel functions
where the cylindrical functions are written as upper case letters (J, K, I, and
Y) and the spherical functions are written as lower case (j, k, i, and y). We
can deal with it by adding a new translation rule:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(verrazano:generate-binding
(list
<span style="color: #b0c4de;">:cffi</span>
<span style="color: #b0c4de;">:package-name</span> <span style="color: #b0c4de;">:cffi-gsl-bindings</span>
<span style="color: #b0c4de;">:input-files</span> (remove-if (<span style="color: #00ffff;">lambda</span> (x)
(or (ppcre:scan <span style="color: #ffa07a;">"gsl_sys\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_complex\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_types\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_version\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"gsl_test\\.h$"</span> x)
(ppcre:scan <span style="color: #ffa07a;">"long_double\\.h$"</span> x)))
(mapcar #'namestring (directory #p<span style="color: #ffa07a;">"/usr/include/gsl/*.h"</span>)))
<span style="color: #b0c4de;">:gccxml-flags</span> <span style="color: #ffa07a;">"-I /usr/include/gsl -DGSL_DISABLE_DEPRECATED"</span>
<span style="color: #b0c4de;">:standard-name-transformer-replacements</span>
`(,(cl-ppcre:create-scanner <span style="color: #ffa07a;">"(^gsl_?)"</span>)
<span style="color: #ffa07a;">""</span>
,(cl-ppcre:create-scanner <span style="color: #ffa07a;">"bessel_(zero_)?([jkiy])"</span>)
<span style="color: #ffa07a;">"spherical_bessel_\\1\\2"</span>)))
</pre>
</div>
<p>
This will translate the lower case Bessel functions of the form
<code>gsl_sf_bessel_j</code> into <code>gsl_sf_spherical_bessel_j</code> while leaving
<code>gsl_sf_bessel_J</code> alone.
</p>
<p>
The much more troubling situation is when GSL uses both <code>N</code> and <code>n</code>, or <code>F</code> and
<code>f</code>, in a single functions argument list. This cannot work, as I'm sure is
clear as day. In order to fix this, I needed to actually hack on
Verrazano a bit. I had to change the <code>write-cffi-function</code> function from it's
current version to:
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">From...</span>
(<span style="color: #00ffff;">do-arguments-of-function</span> (argument node)
(incf index)
(<span style="color: #00ffff;">if</span> (typep argument 'gccxml:ellipsis)
(write-string <span style="color: #ffa07a;">"common-lisp:&rest"</span>)
(bind ((argument-name (aif (name-of argument)
(transform-name (name-of argument) <span style="color: #b0c4de;">:variable</span>)
(format nil <span style="color: #ffa07a;">"arg~A"</span> index)))
(argument-type (type-of argument)))
(push argument-name previous-args)
(pprint-newline <span style="color: #b0c4de;">:fill</span>)
(format t <span style="color: #ffa07a;">" (~A "</span> argument-name)
(write-cffi-type argument-type)
(format t <span style="color: #ffa07a;">")"</span>))))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">...to...</span>
(<span style="color: #00ffff;">let</span> ((previous-args nil))
(<span style="color: #00ffff;">do-arguments-of-function</span> (argument node)
(incf index)
(<span style="color: #00ffff;">if</span> (typep argument 'gccxml:ellipsis)
(write-string <span style="color: #ffa07a;">"common-lisp:&rest"</span>)
(bind ((argument-name (<span style="color: #00ffff;">if</span> (and (name-of argument)
(not (member (name-of argument)
previous-args
<span style="color: #b0c4de;">:test</span> #'equal)))
(transform-name (name-of argument) <span style="color: #b0c4de;">:variable</span>)
(format nil <span style="color: #ffa07a;">"arg~A"</span> index)))
(argument-type (type-of argument)))
(push argument-name previous-args)
(pprint-newline <span style="color: #b0c4de;">:fill</span>)
(format t <span style="color: #ffa07a;">" (~A "</span> argument-name)
(write-cffi-type argument-type)
(format t <span style="color: #ffa07a;">")"</span>)))))
</pre>
</div>
<p>
This change keeps track of what symbols we have already used in the argument
list and replace it with a generic argument of the form "arg<n>". This gets rid
of the last error that stops this file from loading. Now we can load this file
and, again, we are basically where we would be if were a C programmer, but we
can work from Lisp to build a good interface on top of this set of generated
bindings. This brings up another point:
</p>
<ul class="org-ul">
<li>Verrazano is not production ready; it is hacker ready. Verrazano is useful
because it is a tool that developers use every once in a while for generating
bindings. It is not ready for every end user to use.
</li>
</ul>
<p>
Okay, so we have something that will load. However, you may have noticed that
there are crap-load of warnings that are produced when those bindings are
loaded. These warnings are regarding a pretty new improvement to CFFI. Not so
long ago, if you wanted to pass a structure to a function using CFFI, your only
option was to pass it by address. If you needed to pass it by value you were
out of luck. Luckily basically nobody uses pass by value, but it is a little
limiting. Now CFFI supports this, so you need to specify structs by <code>(:struct
struct-name)</code> and pointers to structs as <code>(:pointer (:struct struct-name))</code>. In
order to fix this we are going to have to do a bit more hacking, but for now
these are just warnings.
</p>
<p>
If you have been perusing the generated bindings, you may be wondering what all
these weird functions that Verrazano is making are coming from. Some of the
functions look good, but some seem very odd, for instance
<code>_ZN17gsl_vector_ushortaSERKS_</code>. These functions look very odd and they show up
because Verrazano is, fundamentally, a tool for making C++ bindings, not C
bindings. It is interpreting these header files as C++ header files. It
doesn't offer a "assume this is C" option. This isn't Verrazano's limitation,
really, the <a href="http://comments.gmane.org/gmane.comp.compilers.gccxml/619">GCCXML people are not interested in working with anything but C++</a>.
Often this doesn't matter as C++ is mostly a superset of C. However, there are
differences. One difference is that when it sees structs, it has to assume that
these are C++ sturcts, which are basically classes in C++ with all of their
members public by default. This means that there will be a bunch of code that
is generated by Verrazano like constructors, destructors, and comparison
operators that have special GCC style <a href="https://en.wikipedia.org/wiki/Name_mangling#How_different_compilers_mangle_the_same_functions">"mangled" names</a>. These symbols are
actually not in the library at all as a simple <code>nm -D /usr/lib/libgsl.so.0</code> will
demonstrate. I suppose that these don't really do much harm, and I don't know
how to get rid of them at the time short of post-processing the file and
removing them. Plus we may want them if we are linking against a library with a
C++ interface some day. At least Verrazano seems kind enough to place all these
oddities at the end of our bindings file.
</p>
<p>
To prove that this works:
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Define our library and use it (stolen from GSLL)</span>
(<span style="color: #00ffff;">cffi:define-foreign-library</span> libgslcblas
(<span style="color: #b0c4de;">:darwin</span> <span style="color: #cd5c5c;">#+ccl #.</span>(ccl:native-translated-namestring
(gsl-config-pathname <span style="color: #ffa07a;">"libgslcblas.dylib"</span>))
#-ccl #.(gsl-config-pathname <span style="color: #ffa07a;">"libgslcblas.dylib"</span>))
(<span style="color: #b0c4de;">:cygwin</span> <span style="color: #ffa07a;">"cyggslcblas-0.dll"</span>)
(<span style="color: #b0c4de;">:unix</span> (<span style="color: #b0c4de;">:or</span> <span style="color: #ffa07a;">"libgslcblas.so.0"</span> <span style="color: #ffa07a;">"libgslcblas.so"</span>))
(t (<span style="color: #b0c4de;">:default</span> <span style="color: #ffa07a;">"libgslcblas"</span>)))
(cffi:use-foreign-library libgslcblas)
(<span style="color: #00ffff;">cffi:define-foreign-library</span> libgsl
(<span style="color: #b0c4de;">:darwin</span> <span style="color: #cd5c5c;">#+ccl #.</span>(ccl:native-translated-namestring
(gsl-config-pathname <span style="color: #ffa07a;">"libgsl.dylib"</span>))
#-ccl #.(gsl-config-pathname <span style="color: #ffa07a;">"libgsl.dylib"</span>))
(<span style="color: #b0c4de;">:cygwin</span> <span style="color: #ffa07a;">"cyggsl-0.dll"</span>)
(<span style="color: #b0c4de;">:unix</span> (<span style="color: #b0c4de;">:or</span> <span style="color: #ffa07a;">"libgsl.so.0"</span> <span style="color: #ffa07a;">"libgsl.so"</span>))
(t (<span style="color: #b0c4de;">:default</span> <span style="color: #ffa07a;">"libgsl"</span>)))
(cffi:use-foreign-library libgsl)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Load the bindings</span>
(load #p<span style="color: #ffa07a;">"gsl-cffi-bindings.lisp"</span>)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Define our callback function</span>
(cffi:defcallback csin <span style="color: #b0c4de;">:double</span>
((x <span style="color: #b0c4de;">:double</span>)
(params <span style="color: #b0c4de;">:pointer</span>))
(<span style="color: #00ffff;">declare</span> (ignore params))
(float (sin x) 0d0))
(<span style="color: #00ffff;">let</span> ((workspace (gsl-cffi-bindings:integration-workspace-alloc 10)))
(<span style="color: #00ffff;">unwind-protect</span>
(<span style="color: #00ffff;">cffi:with-foreign-objects</span> ((gsl-fn '(<span style="color: #b0c4de;">:struct</span>
gsl-cffi-bindings:function-struct))
(result <span style="color: #b0c4de;">:double</span>)
(abs-error <span style="color: #b0c4de;">:double</span>))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Setup the GSL function object</span>
(setf
(cffi:foreign-slot-value
gsl-fn '(<span style="color: #b0c4de;">:struct</span> gsl-cffi-bindings:function-struct)
'gsl-cffi-bindings:function)
(cffi:callback csin))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Call the quadrature routine</span>
(gsl-cffi-bindings:integration-qag
(cffi:mem-aptr
gsl-fn '(<span style="color: #b0c4de;">:struct</span> gsl-cffi-bindings:function-struct))
0d0 (/ pi 2d0) 1d-10 1d-5 10
(cffi:convert-to-foreign <span style="color: #b0c4de;">:gsl-integ-gauss-61</span> 'gsl-cffi-bindings:.-155)
workspace result abs-error)
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Return the result and estimate of the error of the result</span>
(values (cffi:mem-ref result <span style="color: #b0c4de;">:double</span>)
(cffi:mem-ref abs-error <span style="color: #b0c4de;">:double</span>)))
<span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">Clean up</span>
(gsl-cffi-bindings:integration-workspace-free workspace)))
==>
1.0
1.1102230246251565e-14
</pre>
</div>
<p>
It may be ugly, but it works. Note that everything here translates pretty
directly to the C code you would write to do this using GSL. In the future
we'll explore how to make this a bit easier to use.
</p>
<p>
Till next time.
</p>
</div></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-51623547097308032222013-06-23T09:40:00.000-07:002013-06-24T01:16:27.174-07:00Calculating Fibonacci Numbers<p>
Yeah, I know, it's been done, it's boring, nothing new to see here. I
understand, this is probably all known, but I just wanted to show this.
</p>
<p>
As I'm sure you are all aware, the Fibonacci sequence can be defined
recursively via the equation:
</p>
<p>
\[
F(n) = F(n-1) + F(n-2)~~~~~~~F(n) = n~~\forall~~n \in \{0, 1\}
\]
</p>
<p>
Now, this is fine and good, but if you translate this formula into a recursive
algorithm in the most naive way possible, it is also extremely computationally
expensive. The fact that each number requires the knowledge of the two previous
numbers means that a naive algorithm to compute this function runs in
exponential time. The Lispy way (IMHO) to deal with this exponential explosion is to
use memoization as a dynamic programming method. This will cache the previous
results and turn this function into a linear time algorithm. Another common way
to compute this is to run through the entire sequence until you get the value
you are looking for. This also runs in linear time but (usually) with a smaller
constant factor and has constant space requirements. Unfortunately, it requires a substantial change from the
intuitive description of the problem, making the code much harder to understand,
which is why I don't like it as much as the memoized recursion. However, in the
name of clarity when exploring the complexity, I will be using the "sum up from
the base case method".
</p>
<p>
But, anyway, my point was that you can easily write a linear time Fibonacci number calculator. That is what we would say under normal circumstances, but this isn't really
true, or rather, it is only true if you assume constant time multiplication.
For large \(n\), it becomes clear that this algorithm is not, actually, linear.
This is because it takes \(O(N)\) time to add two \(N\) digit numbers, and because
at least some of the numbers that we wish to add are of order \(F(n)\) (which have
\(O(\log F(n)) \sim O(n)\) digits), we see now that the actual time is more like
\(O(n\log F(n)) \sim O(n^2)\). This might seem a bit surprising, but look and see
for yourself.
</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguaSW-J2mR5nID4uw6Hj3ZldCLg0P3GqqFsylOQbcOpVtJ3e3mB2l9pA04L_rQFtf_9ULDaaGYole9rztcRCfCbUDQygawjdzGnTwXjsjEHCX4eGpeSPmWzuTj3-yucTW2erBwWqmhLkSz/s1600/fib-time-scaling.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguaSW-J2mR5nID4uw6Hj3ZldCLg0P3GqqFsylOQbcOpVtJ3e3mB2l9pA04L_rQFtf_9ULDaaGYole9rztcRCfCbUDQygawjdzGnTwXjsjEHCX4eGpeSPmWzuTj3-yucTW2erBwWqmhLkSz/s400/fib-time-scaling.png" /></a>
<p>A quadratic fit to the time scaling of the Fibonacci sequence generator function</p></div>
<p>
But, if we are willing to throw clarity out the window all together, we can also
use a different technique to compute the number. We can use the closed form
solution to the Fibonacci sequence, Binet's formula (<a href="https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression">all of this is from
Wikipedia</a>):
</p>
<p>
\[
F(n) = \frac {\psi^n - \phi^n}{\psi - \phi}
\]
</p>
<p>
…where…
</p>
<p>
\[
\psi = \frac{1+\sqrt 5}{2} \\
\phi = \frac{1-\sqrt 5}{2}
\]
</p>
<p>
And, because \(\psi = -\phi^{-1}\), we can simply say:
</p>
<p>
\[
F(n) = \frac {\phi^n - (- \phi)^{-n}}{\sqrt 5}
\]
</p>
<p>
Now, I hear you thinking, these aren't going to work if you actually want the
exact number, because these have nasty things like \(\sqrt 5\) and and \(\phi^{-n}\)
in them. And you would be correct that this is not something that you can
simply type into any programming language and expect a valid number back. But
the fact of the matter is, these formulas are actually correct, it is the
language and the language's insistence that computation on general real numbers
be performed using approximate floating point arithmetic that causes such an
issue in the first place. If, however, we were to turn to the venerable <code>bc</code>,
an arbitrary precision calculator that is already on your computer if you have a
UNIX like operating system, then we can try it out for various \(n\) by setting
the precision to a "high enough" value (the <code>scale</code> variable sets how many
decimal digits of precision you have).
</p>
<div class="org-src-container">
<pre class="src src-sh"><span style="color: #eedd82;">scale</span>=100
phi = (1+sqrt(5))/2
define fib (n) {
(phi^n - (-phi)^(-n))/sqrt(5) }
<span style="color: #87cefa;">fib</span>(5)
4.999999999999999999999999999999999999999999999999999999999999999999<span style="color: #ffa07a;">\</span>
9999999999999999999999999999999988
<span style="color: #87cefa;">fib</span>(10)
54.99999999999999999999999999999999999999999999999999999999999999999<span style="color: #ffa07a;">\</span>
99999999999999999999999999999999728
<span style="color: #87cefa;">fib</span>(100)
354224848179261915074.9999999999999999999999999999999999999999999999<span style="color: #ffa07a;">\</span>
999999999999999999999999999999981555491928230697552907
<span style="color: #87cefa;">fib</span>(200)
280571172992510140037611932413038677189524.9999999999999999999999999<span style="color: #ffa07a;">\</span>
99999999999999999999999999999997069407044903016136967720432076973572<span style="color: #ffa07a;">\</span>
3021244
<span style="color: #87cefa;">fib</span>(400)
17602368064501396646822694539241125077038438330449219188672599289657<span style="color: #ffa07a;">\</span>
5345044216019674.999999999999996317359669914941458065726733504366353<span style="color: #ffa07a;">\</span>
6782163342769596482054432795143577733011851910134
<span style="color: #87cefa;">fib</span>(500)
13942322456169788013972438287040728395007025658769730726410896294832<span style="color: #ffa07a;">\</span>
5571622863290691557658876222517646901.483330817850463056986072289669<span style="color: #ffa07a;">\</span>
50027087266539483120658105031310816022996182603489404860217143670694<span style="color: #ffa07a;">\</span>
09
</pre>
</div>
<p>
We see that as the numbers are computed in the most significant digits, the
error accumulates in the least significant. Once the error meets the important
numbers, which has happened at the 500<sup>th</sup> Fibonacci number, we have reached
the point where we actually don't know if the last digits are correct or not.
At that point we need to increase the scale and try again.
</p>
<p>
Also, if you try this at home, you will find that the computation takes longer
for larger values of \(n\), despite this being a closed form expression. This
isn't really surprising, the closed for expression may seem magical, but it
still needs to be implemented with algorithms that multiply, divide,
exponentiate, and "square root" very large or very precise numbers. More on
this later.
</p>
<p>
Incidentally, the CLISP implementation of Common Lisp also has arbitrary
precision arithmetic and can be used to perform the same calculation much faster
(also, you can also do this in other imps with some success using rational
numbers if you take the time to write a <code>sqrt</code> function that will return a
rational approximation of the square root to within the needed accuracy). If
you try this at home using CLISP, note that the <code>scale</code> value in <code>bc</code> designates
decimal digits while <code>(long-float-digits)</code> in CLISP designates binary digits
(i.e. the CLISP one needs to be larger for the same precision. For example,
CLISP needs a value of 3322 to give around 1000 decimal digits of precision).
</p>
<div class="org-src-container">
<pre class="src src-lisp">(setf (long-float-digits) 350)
(<span style="color: #00ffff;">let</span> ((phi (/ (+ 1 (sqrt 5L0)) 2L0)))
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">fib</span> (n)
(/ (- (expt phi n) (expt (- phi) (- n)))
(sqrt 5L0))))
(fib 100)
3.542248481792619150750000000000000000000000000000000000000000000000000\
000000000000000000000000000000000005L20
(fib 200)
2.805711729925101400376119324130386771895250000000000000000000000000000\
0000000000000000000000000000000000084L41
(fib 400)
1.760236806450139664682269453924112507703843833044921918867259928965753\
4504421601967500000000000000000000109L83
(fib 500)
1.394232245616978801397243828704072839500702565876973072641089629483255\
7162286329069155765887622252129412605L104
</pre>
</div>
<p>
This works okay, but we have to constantly check to make sure that we haven't
run out of precision in our number. We can fix this by computing the number of
significant digits needed to accurately compute \(F(n)\) by first computing an
approximate \(F(n)\) with floating point numbers and using that approximate value
as a guess of how many \(b\)-ary digits you need in have by taking the \(\log_b\).
</p>
<div class="org-src-container">
<pre class="src src-lisp">(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">fib-approx</span> (n)
(<span style="color: #00ffff;">let</span> ((phi (/ (+ 1 (sqrt 5d0)) 2d0)))
(/ (- (expt (float phi 0d0) n) (expt (- (float phi 0d0)) (- n)))
(sqrt 5d0))))
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">fib</span> (n)
(setf (long-float-digits) (max 64 (round (* 1.5 (log (fib-approx n) 2)))))
(<span style="color: #00ffff;">let</span> ((phi (/ (+ 1 (sqrt 5L0)) 2L0)))
(nth-value 0 (round (/ (- (expt phi n) (expt (- phi) (- n)))
(sqrt 5L0))))))
(fib 5)
5
(fib 100)
354224848179261916032
(fib 1000)
43466557686937456435688527675040625802564660517371780402481729089536\
55541794905189040387984007925516929592259308032263477520968962323987\
33224711616429964409065331879382989696499285160037044761377951668492\
28875
</pre>
</div>
<p>
However, this only really works up to the point when the double floats start to
overflow (Fibonacci numbers less than around 300 digits). After that our fast
approximation no longer works as the Fibonacci numbers are too big to fit into
any machine sized number. Is there a way to just get an approximate ballpark
figure for the size of a Fibonacci number without actually calculating it? Yes.
All we need to do is look at the what is important in the equation when \(n\) is
large. If \(n\) is large, \((-\phi)^{-n}\) is extremely small since \(\phi^{-1}\) is
smaller than 1. This means that we can approximate the large \(n\) Fibonacci
numbers as:
</p>
<p>
\[
F(n\gg 1) = \frac{\phi^n}{\sqrt 5}
\]
</p>
<p>
Now, we know that the number of \(b\)-ary digits in a number is roughly equal to
the \(\log_{b}\) of the number. This means that the number of digits in a large
Fibonacci number is:
</p>
<p>
\[
\log F(n \gg 1) = \log \phi^n - \log \sqrt 5 = n\log\phi - \log\sqrt 5
\]
</p>
<p>
Adding this to our Fibonacci number calculator:
</p>
<div class="org-src-container">
<pre class="src src-lisp">(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">log-fib-approx</span> (n <span style="color: #98fb98;">&optional</span> (base 2))
(<span style="color: #00ffff;">let</span> ((phi (/ (+ 1 (sqrt 5d0)) 2d0)))
(- (* n (log phi base)) (log (sqrt 5) base))))
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">fib</span> (n)
(setf (long-float-digits) (max 64 (round (* 1.5 (log-fib-approx n 2)))))
(<span style="color: #00ffff;">let</span> ((phi (/ (+ 1 (sqrt 5L0)) 2L0)))
(nth-value 0 (round (/ (- (expt phi n) (expt (- phi) (- n)))
(sqrt 5L0))))))
(fib 5)
5
(fib 100)
354224848179261915075
(fib 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417\
94905189040387984007925516929592259308032263477520968962323987332247116164\
2996440906533187938298969649928516003704476137795166849228875
(fib 10000)
33644764876431.......84058580903081179711592936853976188104504236323110912
</pre>
</div>
<p>
At this point, we might ask how all this compares to calculating the number via
the recurrence equation? On the one hand, using intelligent algorithms we have
found an \(O(n^2)\) time algorithm based on the recurrence relation. On the
other, it isn't totally clear what the scaling behavior of the proposed closed
form algorithm is. In the Binet's formula based method, we have (roughly in
order carried out in the calculation):
</p>
<ol class="org-ol">
<li>An arbitrary precision square root
</li>
<li>An fixed to arbitrary precision addition (adding one to a value)
</li>
<li>An arbitrary precision to fixed division (divide by two)
</li>
<li>Two arbitrary precision exponentiations
</li>
<li>An arbitrary precision subtraction
</li>
<li>An arbitrary precision division
</li>
</ol>
<p>
Looking at this list, the obvious prime suspects for the bottleneck are the
square root and the exponentiation, but let's look at each. Wikipedia tells me
that multiplication and division have the same complexity lower bounded with
\(O(N\log N)\) (probably) and that addition and subtraction run in \(O(N)\) time.
</p>
<p>
Using simple divide and conquer exponentiation gives an \(O(N\log N \log n)\) time
scaling for exponent \(n\). The only thing that is left is the scaling of the
square root. Looking through the GMP docs tells me that this can be done in
\(O(N\log N)\) time (again assuming the Schönhage-Strassen conjecture for
multiplication). This means that the most expensive part of the calculation is
the exponentiation, at \(O(\log F(n)\log \log F(n) \log n)\) time. What
does that mean for our algorithm?
</p>
<p>
The Fibonacci sequence grows in an exponential manner. This is clear from
recurrence, \(F(n+1) = F(n) + F(n-1) \sim 2F(n)\). Roughly speaking, increasing
\(n\) by a constant factor has the effect of <i>multiplying</i> \(F\) by a constant
factor, which is basically the definition of "exponential". But, in our
complexity, We are taking the \(\log\) of that number, which "undoes" the
exponential function. More concretely, we actually calculated a large \(n\)
approximation of \(\log F(n)\) above, which turned out to scale linearly with \(n\).
All of this boils down to the relationship I mentioned before: \(O(\log F(n))
\sim O(n)\). Thus, we expect this calculation to be \(O(n (\log n)^2)\), whereas
the complexity for the recurrence based results took \(O(n^2)\). This result
demonstrates that Binet's formula is, in fact, an asymptotic winner in this
computational contest. When you plot the timing data, it seems very linear (I
certainly cannot seem to resolve the \((\log n)^2\) portion of the scaling
behavior).
</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipNXeWb5NlUv4VlfUDfp6iObEREg7Ylhy6TzLw3deqORqQ2sXGQQH9so1DqeQtQRJOCYnJjyyUXEsQESSziqZQmFE83_YtpAkyzgSPVdvJ7A9lc9ef5dgqkvSlOL-lo8yS4Qb6K0CSp-Hm/s1600/binet-fib.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipNXeWb5NlUv4VlfUDfp6iObEREg7Ylhy6TzLw3deqORqQ2sXGQQH9so1DqeQtQRJOCYnJjyyUXEsQESSziqZQmFE83_YtpAkyzgSPVdvJ7A9lc9ef5dgqkvSlOL-lo8yS4Qb6K0CSp-Hm/s400/binet-fib.png" /></a></div>
<p>
If you are actually interested in calculating Fibonacci numbers very quickly and
are using CLISP, then it is probably a safe bet to use the Binet's formula
method rather than the more intuitive algorithm even for small numbers. On
CLISP, the differences in run times are around two orders of magnitude faster
than the intuitive method (although it seems to be much less predictable in
terms of run time in any particular run, my prime suspect on this is the GC).
Using SBCL (a much more sophisticated compiler), the intuitive algorithm runs
significantly faster than on CLISP, but still is no match for Binet's method
(on CLISP).
</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-31177684594745117092013-06-06T15:44:00.000-07:002013-06-11T05:54:32.801-07:00Some Customizations to W3m-Mode<div id="content">
<p>
For many tasks, I find that it is easier to use a text mode browser in
Emacs than it is to use an external browser. This is clearly the case when you
would like to copy some text from a web page into an Emacs buffer, like when you are grabbing code examples from a manual or tutorial. One of the
main uses I have of this is to quickly browse the Common Lisp Hyperspec. I have
found that W3m and W3m-Mode is quite good for these tasks. W3m is a text mode
browser that exists independently from Emacs. W3m-Mode is a mode that connects
to W3m, sends requests from Emacs to the external process, and receives the
output and displays it in an Emacs buffer. <i>Edit: If you want to set Emacs up to use this browser, or any browser, customize the <code>browse-url-browser-function</code> variable.</i>
</p>
<p>
Of course W3m won't work with a lot of "modern" websites, anything that uses
Flash (of course), or anything that utilizes Javascript extensively. Even with
all of those barriers, it works surprisingly well because much of the
information that is out there on the Internet (and most of the information that
I consume using this browser) is actually just text. Further, thanks to HTML5
and the return of the separation of content (HTML) and design (CSS) many
websites can be rendered usefully in text.
</p>
<p>
However, as much as I have learned to like W3m-Mode, there are some annoying
aspects of the mode that are the default. Namely, I would like to be able to
move through the buffer with the standard directional keys, as well as switch
tabs in the way that most other browsers do via "C-<tab>", and move forward and
backward in history via "M-<right>" and "M-<left>", respectively. With a little
help from the Emacs folks on <a href="http://www.reddit.com/r/emacs/comments/19lfk3/an_emacs_web_browser/c8p43n8">/r/emacs</a>, here are some bindings that will set this
up for you.
</p>
<div class="org-src-container">
<pre class="src src-lisp"><span style="color: #ff7f24;">;; </span><span style="color: #ff7f24;">W3m for browsing</span>
(<span style="color: #00ffff;">defun</span> <span style="color: #87cefa;">w3m-mode-options</span> ()
(local-set-key (kbd <span style="color: #ffa07a;">"<left>"</span>) 'backward-char)
(local-set-key (kbd <span style="color: #ffa07a;">"<right>"</span>) 'forward-char)
(local-set-key (kbd <span style="color: #ffa07a;">"<up>"</span>) 'previous-line)
(local-set-key (kbd <span style="color: #ffa07a;">"<down>"</span>) 'next-line)
(local-set-key (kbd <span style="color: #ffa07a;">"M-<left>"</span>) 'w3m-view-previous-page)
(local-set-key (kbd <span style="color: #ffa07a;">"M-<right>"</span>) 'w3m-view-next-page)
(local-set-key (kbd <span style="color: #ffa07a;">"C-<tab>"</span>) 'w3m-next-buffer)
(local-set-key (kbd <span style="color: #ffa07a;">"q"</span>) 'bury-buffer))
(add-hook 'w3m-mode-hook 'w3m-mode-options)
</pre>
</div>
<p>
That last <code>local-set-key</code> is to rebind the "q" key. By default, "q" tells
W3m-Mode to kill all W3m sessions and close the window. This isn't the right
thing to do for a couple of reasons. First, if I want to kill all W3m sessions,
I will do so by killing the buffer (which will kill the sessions). I don't need
a separate key for that. Second, closing windows without the user expressly
asking for a window to be closed is not good Emacs interface style. The correct
thing to do is to go away (whatever that means) and leave the window to be
filled with another buffer. The only exception to the rule is popup windows,
windows that are meant to be extremely short lived (less than a minute) and
which created the window in which the reside. W3m is most definitely not a
popup window. Looking at this, I felt that the best solution is to map "q" to
<code>bury-buffer</code> and leave it at that.
</p>
<p>
There are a few other bindings that are different from the standard key bindings
that a browser uses, including making a new tab and kill that tab. These exist
and are reasonable (they fit in with the standard Emacs user interface), just
check the help for W3m-Mode via "C-h m".
</p>
</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-77778042780390230412013-06-01T19:41:00.000-07:002013-06-01T19:41:03.469-07:00A Multiple Cursor Trick and an Improvement<div id="content">
<p>
I have been baking, in the back of my mind, a way to make multiple cursors more
powerful. What I wanted was a way to move through a buffer, and mark certain
places where I want to place my multiple cursors, and then make my changes. I
think this idea is basically baked enough to reveal that… it is not actually
necessary to modify the multiple-cursors library to achieve this goal.
</p>
<p>
If you want to do this, you can simply insert a sequence of characters that is
unique at each point that you wish to place a cursor (something that you would
never use, like some crazy Unicode character, say "ಠ<sub>ಠ</sub>", you just have to find
an easy way to insert it into the buffer). Then, select that tagging sequence
and use <code>mc/mark-all-like-this</code> and edit away. This actually works in a pinch.
For instance, you can do things like this:
</p>
<center>
<iframe width="420" height="315" src="http://www.youtube.com/embed/Ch09Vvg30Oc" frameborder="0" allowfullscreen></iframe>
</center>
<p>
However, I guess that this is slightly more hackish than I like, so I came up
with a new, better method. What I decided would be pretty awesome is to have
multiple-cursors be able to mark spots off the top of the mark ring (either via
popping or just walking the mark ring). I defined a function <code>mc/mark-pop</code> that
will just this. I use the suggested multiple cursors and expand region key
bindings and bound <code>mc/mark-pop</code> to "C-S-p" (which makes sense on a Dvorak
keyboard layout, if you use Qwerty, you might use "C-?"). This means that you
can do some pretty awesome stuff like this:
</p>
<center>
<iframe width="420" height="315" src="http://www.youtube.com/embed/uyBEZS24QRs" frameborder="0" allowfullscreen></iframe>
</center>
<p>
I have submitted a <a href="https://github.com/magnars/multiple-cursors.el/pull/80">pull request to Magnars</a> which has been accepted. This is
still a bit inconvenient to use, but it has promise for being an excellent
building block for future multiple cursor editing tricks.
</p>
</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-57617507220227043192013-05-29T16:47:00.000-07:002013-05-29T16:47:34.144-07:00Hunting Firefox Bugs: Hang On Focus<div id="content">
<p>I am just putting this here so that this might show up a bit easier in a Google
search. I recently figured out a solution (sort of) to one of these nagging
issues that I have been facing for a long time. The issue is that sometimes
Firefox gets in a state where it hangs for a few seconds, pegging the CPU,
whenever the window comes into focus (i.e. you click on it). This means it is
very difficult to switch back and forth between Firefox and another window.
This was a mystery for a long while. However, I found these <a href="https://bugs.launchpad.net/ubuntu/+source/firefox/+bug/964584">two bug</a> <a href="https://bugs.launchpad.net/libdbusmenu/+bug/801699">reports today</a>. The earlier bug was reported around two years ago, and they supposedly
pushed a fix around 8 months ago, but it is still biting (me) today.
</p>
<p>
This seems to actually be a limitation of the current implementation of the
global menu in Ubuntu. This works via DBUS, which apparently isn't very
efficient at populating large menus. Firefox has a bookmarks menu which means
that having many entries in your bookmark database will cause Firefox to hang as
that menu is populated. This was actually pretty difficult to figure out as the
behavior is intermittent. Often Firefox would work as expected, but sometimes
this hanging would start and it would persist until reboot of the entire system
(restarting Firefox is not enough). I now suspect that this state is triggered
by setting a bookmark, but I am unsure.
</p>
<p>
Anyway, the fix here is to not use bookmarks too heavily. If you delete all of
your bookmarks this problem will go away, and this is just what I did (after I
saved them to disk). That said, this really puts me, and people who browse the
Web like I do, in a predicament.
</p>
<p>
When I find an article or web page that I am interested in, I cannot usually
read it when I find it. So, I like to store it for future consumption. For
this purpose, I used to use tabs, but as everybody knows, this will bog your
computer down as most browsers attempt to keep them in RAM. Firefox, fairly
recently, started releasing them from memory after they haven't been used, which
helps matters (unfortunately they made the, IMHO, stupid decision to completely
reload on restore rather than cache to disk). But, even with this memory
friendly behavior from Firefox, it will still routinely bloat to greater than
1GB of resident RAM and needs to be restarted (presumably so that the tabs will
be flushed out of RAM). And before the "Firefox is just making efficient use of
memory" people show up, Firefox is not making good use of memory if it causes my
computer to hang for 30+ seconds when switching windows that have nothing to do
with Firefox (which it does in certain extreme cases), or if it causes Compiz,
Xorg, or my entire computer to crash (which happens every once in a while and
correlates so strongly with Firefox memory consumption that I have to suspect it
as a culprit).
</p>
<p>
To combat this, a while ago I started categorizing pages I find as I want to
read this within a week or I want to read sometime later in the future. The
ones I want to read within a week I keep as tabs and the ones that I want to
read sometime in the future I set a bookmark to find it easily later. I figured
that bookmarks should take practically no resources to hold other than a bit of
disk space. With this bug, however, setting bookmarks on interesting pages
isn't really a good option either. This means that I now have my bookmarks in a
separate HTML and JSON file while I try to come up with a better solution.
</p>
<p>
I suppose that this isn't an issue with Chromium or Chrome as those don't use
the global menu for bookmarks (they have a separate menu right of the address
bar).
</p></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-12309984981507459402013-05-23T05:42:00.000-07:002013-05-23T05:42:29.012-07:00Quickly Searching For a String in a Buffer
<div id="preamble">
</div>
<div id="content">
<p>So this is a bit embarrassing that I have never seen this solution before, but I
recently saw this problem in a Coursera lecture.
</p>
<blockquote>
<p>Given a buffer sequence of length \(N\) and a query sequence of length \(m\), find
all occurrences of the query in the buffer.
</p>
</blockquote>
<p>
The most transparent way to solve this problem is to search each starting
position in the buffer for the query string. This is clearly \(O(N*m)\) (for
small \(m\), that is. It is really around \(O((N-m)*m)\). However, in big \(O\)
fashion, we normally say \(O(N)\) and leave it at that).
</p>
<pre class="src src-lisp">(<span class="org-keyword">defun</span> <span class="org-function-name">get-string</span> (i length buffer)
<span class="org-doc">"Extract the string without any copying or memory use."</span>
(make-array length
<span class="org-builtin">:element-type</span> 'character
<span class="org-builtin">:displaced-to</span> buffer
<span class="org-builtin">:displaced-index-offset</span> i))
(<span class="org-keyword">defun</span> <span class="org-function-name">naive-search</span> (query buffer)
<span class="org-doc">"Find all occurrences of query in buffer."</span>
(iter (for i <span class="org-builtin">:to</span> (- (length buffer) (length query)))
(<span class="org-keyword">when</span> (equal query (get-string i (length query) buffer))
(collect i))))
</pre>
<p>
Although this all pretty silly, as Common Lisp has a sequence search built in
called <code>search</code>. In addition, it also has third party libraries that can do
string searches and much more:
</p>
<pre class="src src-lisp"><span class="org-comment-delimiter">;; </span><span class="org-comment">Can't get much simpler than...</span>
(<span class="org-keyword">defun</span> <span class="org-function-name">search-search</span> (query buffer)
<span class="org-doc">"Find all occurrences of query in buffer."</span>
(iter
(for i <span class="org-builtin">:initially</span> (search query buffer <span class="org-builtin">:start2</span> 0)
<span class="org-builtin">:then</span> (search query buffer <span class="org-builtin">:start2</span> (1+ i)))
(<span class="org-keyword">while</span> i)
(collect i)))
<span class="org-comment-delimiter">;; </span><span class="org-comment">If you are using strings, regular expressions are pretty versatile.</span>
(ql:quickload <span class="org-builtin">:cl-ppcre</span>)
(<span class="org-keyword">defun</span> <span class="org-function-name">regex-search</span> (query buffer)
<span class="org-doc">"Find all occurrences of query in buffer."</span>
(<span class="org-keyword">let</span> (acc)
(<span class="org-keyword">ppcre:do-matches</span> (start end
query buffer
(reverse acc))
(push start acc))))
</pre>
<p>
The interesting part of these is that they are probably much smarter than my
naive implementation. Besides being highly tuned, they also most likely use
parts of previous failed matches in subsequent matches, which means that they
might run in \(O(N)\) time (i.e. no \(m\) factor).
</p>
<p>
The point is that either way I do this it would take \(O(N)\) time to simply
search the text for the value in the most naive way possible. In the lecture,
however, they stated that you could sort the data and then perform a bisection
search. I was taken aback as it seemed to me that you cannot sort a body of
text without screwing up the order, which is needed because we are actually
interested in matching a sequence of characters in a larger sequence.
</p>
<p>
The way we can do this, "sort the sequence" and keep the sequence in order, is
to sort a different buffer that holds the indexes into the sequence. Sorting
takes \(O(N\log N)\), so a single search should actually take longer to compute,
but once you have the indexing you can perform subsequent searches (with the
same length or shorter queries) in \(O(\log N)\). In order to accommodate this
usage pattern, I have included an ad-hoc, manual, partial memoization mechanism.
I return the computed sorted indexes (along with the maximum length of a valid
query) as a second return value and take them as an optional argument (I use a
class here so that the printed value doesn't flood your terminal). If you pass
invalid cache parameters, the function detects this and recomputes.
</p>
<pre class="src src-lisp"><span class="org-comment-delimiter">;; </span><span class="org-comment">Define a container for our cache</span>
(<span class="org-keyword">defclass</span> <span class="org-type">cache</span> ()
((max-length <span class="org-builtin">:initarg</span> <span class="org-builtin">:max-length</span> <span class="org-builtin">:accessor</span> max-length)
(buffer <span class="org-builtin">:initarg</span> <span class="org-builtin">:buffer</span> <span class="org-builtin">:accessor</span> buffer)
(indexes <span class="org-builtin">:initarg</span> <span class="org-builtin">:indexes</span> <span class="org-builtin">:accessor</span> indexes)))
(<span class="org-keyword">defun</span> <span class="org-function-name">indexed-search</span> (query buffer <span class="org-type">&optional</span> cache)
<span class="org-doc">"Find all occurrences of query in buffer."</span>
<span class="org-comment-delimiter">;; </span><span class="org-comment">Extract (or compute) the cache</span>
(<span class="org-keyword">destructuring-bind</span> (max-query-length sorted-indexes)
(<span class="org-keyword">if</span> (and cache
(eq buffer (buffer cache))
(<= (length query) (max-length cache)))
(list (max-length cache) (indexes cache))
(list (length query)
(stable-sort (iter (for i <span class="org-builtin">:to</span> (- (length buffer) (length query)))
(collect i <span class="org-builtin">:result-type</span> vector))
#'string<
<span class="org-builtin">:key</span> (<span class="org-keyword">lambda</span> (i) (get-string i (length query) buffer)))))
(<span class="org-keyword">labels</span> ((bisection (lo hi)
<span class="org-comment-delimiter">;; </span><span class="org-comment">A simple bisection search</span>
(<span class="org-keyword">let</span> ((mid (floor (+ lo hi) 2)))
(<span class="org-keyword">cond</span> ((= lo hi) lo) <span class="org-comment-delimiter">; </span><span class="org-comment">we have either found the first match or</span>
<span class="org-comment-delimiter">; </span><span class="org-comment">there are no matches</span>
((string<= query (get-string (aref sorted-indexes mid)
(length query) buffer))
(bisection lo (min mid (- hi 1))))
(t (bisection (max mid (+ lo 1)) hi))))))
<span class="org-comment-delimiter">;; </span><span class="org-comment">Perform the search and return the index and cache</span>
(values (iter (for i <span class="org-builtin">:from</span> (bisection 0 (length sorted-indexes)))
(<span class="org-keyword">while</span> (string= query (get-string (aref sorted-indexes i)
(length query) buffer)))
(collect (aref sorted-indexes i)))
(make-instance 'cache <span class="org-builtin">:max-length</span> max-query-length
<span class="org-builtin">:buffer</span> buffer
<span class="org-builtin">:indexes</span> sorted-indexes)))))
</pre>
<p>
And indeed, after the \(O(N\log N)\) preprocessing, this runs in \(O(\log N)\) time.
The timings work out that the initial sort takes a very long time (presumably
due to poor performance in <code>string<=</code> for lexical order), but the subsequent
queries are basically instantaneous (too fast to measure even for large buffer
sequences). So, while you probably don't want to use this for normal searches,
you might want to do this if you need to make many queries (of a limited length)
on a immutable sequence, and it could result in a huge performance increase.
</p>
<p>
Well, I guess this just serves as a reminder that I still have a lot of basic
stuff to learn. However, after writing this up, I doubt that I will forget
it…
</p></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-75775170143350125092013-05-16T06:13:00.000-07:002013-05-16T06:13:02.120-07:00ICFP Contest 2013 Anyone?As you may have seen on Reddit this morning, <a href="https://research.microsoft.com/en-us/events/icfpcontest2013/">Microsoft Research has put up an ICFP placeholder page</a>. This might seem a bit premature, but I would like to have some Common Lisp friends (new and old) to partake in ICFP this year, so I am getting started early.<br />
<br />
The contest seems to be starting August 8th sometime and should run for the next 72 hours. If you are at all interested in programming Common Lisp on a team ICFP attempt, please comment below, or email, or whatever your favorite method of communication.<br />
<br />
This year I have a few new tools that should work better than <a href="http://directed-procrastination.blogspot.com/2012/07/adventures-in-collaborative-coding-with.html">last</a> <a href="http://directed-procrastination.blogspot.com/2012/07/icfp-2012-post-mortem.html">year</a>, including a way that spectators can follow along without video streams that are susceptible to crappy resolutions (anyway, I now know someone that works on the YouTube team at Google, so he could probably get the old setup to work better). I plan to post on those tools later to try and drum up interest as the contest approaches.Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-7788284466297989064.post-42039573967901614712013-05-15T10:16:00.000-07:002013-05-15T10:16:40.914-07:00What is wrong with Python strings?This is a micro-rant about Python. If this isn't your thing, please excuse this post. I have been trying to use Python in order to become more employable (well more employable for the sort of places I would like to work). Here are a few grievances I have found. These complaints are, I suspect, actually about the default Python behavior. That doesn't actually diminish the criticisms much, however, as they are definitely barriers to entry. For some of these things I have still not been able to find a way around them, which makes them pretty serious.<br />
<ol>
<li>Python actually only allows ASCII characters? Really?!? If you include some odd (or not so odd) character like a lambda, it will choke. If this doesn't seem like a big deal to you, you have clearly never dealt with any language other than English, nor have you dealt with the various fancy forms of punctuation. You can instruct Python to accept a different encoding by putting a magic comment at the beginning of your source file that looks like "# coding: <encoding>". As a reference, the last time this was an issue in any Lisp I tried, was around 5 years ago with CLISP (a fairly out of date Lisp at the time) and it was remedied shortly after.</li>
<li>What is going on with your string type? If I index into the string type, I can land in the middle of a multi-byte character. The very fact that this is possible is evidence that this string type is fundamentally screwed up.</li>
<li>Why is the printed representation of a Unicode string unreadable? Seriously, we have terminals that can handle pretty much anything that you can throw at them, why print a bunch of line noise instead of the actual character?</li>
<li>What is wrong with the way you output in Python? Why is it that I get an encoding error when I try to pipe or redirect output from my program to another program and a non-ASCII character is encountered? I have no idea what is going on here, or how to get around it. This is, quite possibly the biggest hiccup in terms of productivity. I cannot even send my output to a file or to less in order to carefully review the output. How hard is it to dump the output of a program into a file? In the case of pipes, you might think that this is a shortcoming of the pipe itself, or of the program on the other side of the pipe, but this is not the case. I routinely pipe all sorts of crazy text through pipes and to shell commands without any problems; whatever the issue is, it is rooted in Python.</li>
</ol>
In Lisp (my usual language of choice), a string is a vector of characters, not ASCII bytes or a vector of data that might be interpreted as characters, which I imagine is the primary shortcoming in Python here. Including encodings other than ASCII seems to have been an afterthought, an ugly thing that was bolted on to make the language work with text that wasn't ASCII. Why Python didn't decide at conception to do away with the idea of that a string is a sequence of bytes, I have no idea. It seems like Python wanted to be a high level language, but stopped short of actually making it there, at least in the way strings are handled. They seem to have the basic building blocks of a proper string type, but stupidly set the default behavior to only deal with ASCII strings, which is basically backwards, IMO.<br />
<br />
People say (and I believe) that Common Lisp is simultaneously the highest level and lowest level programming language you will ever use. In Lisp you can write code that is so abstracted you have have no idea of what code is actually being passed to the CPU, much less the data-structures or memory usage. But, in the same program, you can write code that translates directly to machine instructions in a predictable way (or even put inline C or assembly). Because of its high level nature, I have never had to worry about strings with odd characters in them; they just work. And, because of its low level nature, it is simple to convert strings down to ASCII when you have to, which is a very rare need in my experience. You would think that Python, whose earliest versions where a full 5 years after the most recent standardization of Lisp (coming up on 20 years since then), would have done this better.<br />
<br />
I could actually go on and on about things that I perceive Python sucking at, for instance the fact that there is a REPL but no iterative development, or the fact that the error messages I get are basically garbage (however, Lisp is not that much better in this regard), or the fact that you must explicitly have a "return" statement on your functions, and of course, of course, the accursed whitespace dependence (which isn't actually annoying because of the whitespace, but because I actually have to tab around to get the correct indentation level in Emacs). But those things are probably just matters of taste, something that usually works out with time. The string handling in Python, however, is basically inexcusable.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-7788284466297989064.post-14318583618060839452013-04-26T09:22:00.000-07:002013-07-12T22:35:10.599-07:00Rogoff, Reinhart, and Research: Four Questions<i>First, this is not a post about economists or about how we need more stimulus spending or something like that. This is actually about software, primarily. So, be not afraid fiscal conservatives. If you </i>are<i> interested in the economics, Krugman's articles and blog entries make up a pretty thorough analysis of the whole ordeal.</i><br />
<br />
This has been irking me for the last week or so. From <a href="https://www.nytimes.com/2013/04/19/opinion/krugman-the-excel-depression.html">Krugman's article in the NY Times</a>:<br />
<blockquote class="tr_bq">
Finally, Ms. Reinhart and Mr. Rogoff allowed <a href="http://www.peri.umass.edu/236/hash/31e2ff374b6377b2ddec04deaa6388b1/publication/566/">researchers at the University of Massachusetts</a> to look at their original spreadsheet — and <a href="http://www.nextnewdeal.net/rortybomb/researchers-finally-replicated-reinhart-rogoff-and-there-are-serious-problems">the mystery of the irreproducible results was solved</a>.
First, they omitted some data; second, they used unusual and highly
questionable statistical procedures; and finally, yes, they made an
Excel coding error. Correct these oddities and errors, and you get what <a href="http://www.oecd-ilibrary.org/economics/public-debt-economic-growth-and-nonlinear-effects_5k918xk8d4zn-en">other researchers have found</a>:
some correlation between high debt and slow growth, with no indication
of which is causing which, but no sign at all of that 90 percent
“threshold.” </blockquote>
After reading about this a bit, as a person that performs publicly funded research for a living (at least right now) I find myself with four questions. First...<br />
<br />
<span style="font-size: large;"><i>Why are you using Excel for important, presumably mathematically involved, statistical work?</i> </span><br />
<br />
Now this is a minor issue, more of just a curiosity really<i> </i>and a particular pet peeve of mine:<i> </i>Excel is a spreadsheet program. It is meant for things like making invoices, calculating grades, and balancing your check book, and even for those purposes it is not the best tool for the job. Each of those tasks have specialized programs written expressly for them. Excel is a "jack of all trades" sort of program, which is good (I tend to like those types of programs), but if your profession is to run statistics on data, is that the tool you should use? We have tools that are designed specifically for statistical analysis. We even have tools that look basically exactly like Excel but have a bunch of statistical tools built in as well.<br />
<br />
Yes, Excel can be used for more complicated things. I knew a guy who used Excel to perform a discrete element method calculation of the heat flow throughout the complex geometry of an internal combustion engine. It worked, but it is not what Excel is meant to do. I'll even go so far is say that you should not use Excel to solve PDEs in complicated geometries; just a blanket no, don't do it. Excel is certainly Turing complete, that doesn't mean that you should use it for everything. I can use <a href="https://www.sharelatex.com/blog/2012/04/24/latex-is-more-powerful-than-you-think.html#.UXlR-kmxi0w">LaTeX to compute as well</a> (TeX is also Turing complete), but I would never use it for something that wasn't document formatting.<br />
<br />
Should you use tools for things that they are not intended to be used for? Sure, if the tool is well suited for that task. Sometimes tools are well designed and they can be used for tasks that the designers never intended them for, sometimes <a href="http://www.developerfusion.com/article/84374/solving-sudoku-with-sql/">wildly</a> <a href="http://directed-procrastination.blogspot.com/2011/06/syncing-emacs-with-google-documents.html">outside</a> the <a href="https://github.com/yhvh/go-svg-mode">target</a> <a href="https://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming#History_of_TMP">use case</a>. This usually falls under what we would call a <i>hack</i>. Should you use hacks routinely in your professional code? Probably not.<br />
<br />
Perhaps I am off base. I'm not a statistician or an economist, perhaps the mathematics/calculations involved in economics is so brain-dead simple that Excel or a pocket calculator is the perfect tool for the job.<br />
<br />
<span style="font-size: large;"><i>Why is it that the simple coding error resonates so well with the public whereas the<span style="font-size: large;"> general </span>bad <span style="font-size: large;">statistics</span> falls flat?</i></span><br />
<br />
The answer (<a href="http://krugman.blogs.nytimes.com/2013/04/20/the-good-glitch/">which Krugman draws attention to elsewhere</a>) is actually pretty obvious, one is embarrassing because people understand it and have probably made a similar mistake themselves while the other is considered complicated. Thus, people tend to give a pass on the latter. There is also the fact that the coding error resonates better with the media. It is a much easier story to tell, and media outlets routinely talk to the lowest common denominator (how else are you going to make money on the news?). <br />
<br />
My understanding is that the paper did some pretty sketchy things regarding selecting what data to include and what to exclude in their analysis. There was also some pretty bad logic involved as well: the paper was published based on a correlation found in some data but never made a causality argument. I think that this is actually pretty common in social sciences, but data mining for correlations and then never attempting to figure out the reason behind them is a pretty shoddy research method.<br />
<br />
Of all of the errors that seem to have gone into this research, the error in the spreadsheet seems to be the least offensive. That is until you consider my next question.<br />
<br />
<span style="font-size: large;"><i><span style="font-size: large;">W</span>hy did this take so long to uncover?</i></span> <br />
<br />
The answer to this is almost certainly the fact that the code that was used for these calculations was not made available to the public. This was a contentious result and others have attempted and failed to reproduce the results. This is exactly the time when having source available to others would have helped this dispute get resolved much faster.<br />
<br />
I know that there are people that don't share my opinion that Free/Libre Software is (to first approximation) always to be preferred over proprietary alternatives, but there are places where it is wholly inappropriate to use proprietary software. Perhaps the most important place for Free/Libre Software is the source code and interpreters/compilers for that source code that is used in public research. Note that I'm not talking about Open Source development; we are talking about the freedom to inspect the code, use it in your own research, and distribute it to others, not a development model, though that might be a good fit for some projects.<br />
<br />
In my opinion, and hopefully more and more researchers share this opinion, this research is flawed largely because it is not available for inspection. It is not available for inspection for two reasons: 1) Excel, the interpreter, is not Free Software nor gratis, and 2) the Excel document that they performed the calculation in was not made immediately available. Though, to their credit, it was made available to another researcher upon request and Excel is widely used and has several Free Software spreadsheet programs that very likely would run these files. Think of how much better things would have been if the files were posted where anybody could get at them on a whim rather than by request. Anybody could execute them without buying a software license (due to gratis software) and understand what is happening in the software (freedom 1) and have the right to pass on altered versions to other researchers (freedom 2 and 3).<br />
<br />
In addition, the proprietary nature of Excel causes concern as well as there may be internal errors in Excel that invalidate user programs that are correct. I should point out that errors within Excel itself become more and more likely as you start using Excel for things that it really wasn't made for, like advanced statistical analysis/modelling. <br />
<br />
Thus, I think that people performing public research should publish any associated code to the public. And yes, I know that this is a scary prospect. I recently found an error in some code that I had written for a paper after it had been submitted to a journal. I had neglected to initialize a floating point variable in my program. Luckily, it did not effect the end result, and I really appreciate the luck in being able to fix this before someone else found it. If I am honest to myself, I am grateful that I didn't get caught making a huge mistake; I am grateful that I avoided shame, and that I got to analyze the situation and (if it had been necessary) get a head start on damage control.<br />
<br />
But scary as it is, let's face it, the right thing to do for the advancement of research is to have open access of source code to other researchers and have that source code licensed in such a way that others can use it in their work. After all, what is worse, your work misleading people for years before it goes down in flames, or someone pointing it out early before anything bad happens? More eyes mean errors get caught faster, even if some of those eyes are out to completely discredit your work; perhaps even more so when this is the case.<br />
<br />
<i><span style="font-size: large;"><span style="font-size: large;">Do we <span style="font-size: large;">n</span>eed<span style="font-size: large;"> a </span></span>"<span style="font-size: large;">Free<span style="font-size: large;">/Libre<span style="font-size: large;"> Re<span style="font-size: large;">search" Movement?</span></span></span></span></span> </i><br />
<br />
When pondering this last question, I initially thought that it might be useful to define a sort of "Free/Libre Research" movement, where publications themselves and all source code and data associated with it are made available to the public (or at least the portion of the public that funded the research) at approximately the cost required to package and deliver it if not free and can be freely reused in derivative work. There are hints of this happening, particularly in the field of Computer Science. After some thought, I realized that such a movement shouldn't actually be necessary.<br />
<br />
Defining such a movement is akin to saying that we want to do scientific research, i.e. we should be doing it this way already. These conditions I've described in a so called "Free/Libre Research" movement clearly falls under the very definition of scientific research. It is all part of reproducibility (i.e. have other researchers attempt to reproduce your results) and falsifiability (allowing other researchers to potentially challenge your hypothesis). And, while it is not absolutely necessary to provide source to people in order to maintain reproducibility and falsifiability, shouldn't we be actively trying to make the scientific process work better rather than hindering it?Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-30537363819534158582013-04-10T05:26:00.000-07:002013-06-01T01:46:31.573-07:00Programming Competition News<p>If you are into programming, and programming competitions, and programming in Lisp, three things that are probably highly correlated with the readership of this blog, then this is probably of interest to you. The <a href="http://lispinsummerprojects.org/">Lisp in Summer Projects</a> competition (previously named "Lisp in Small Projects") has been announced and is slated to run from the end of June to the end of September. This probably encompasses ICFP this year, but what is one weekend out of three months? </p>
<p> This looks like a very fun activity and I very much plan to take part if time permits (alas, time is always the enemy). There is something to be said for long term programming competitions. <a href="http://directed-procrastination.blogspot.com/2012/07/icfp-2012-post-mortem.html#sec-3_1">As I have written before</a>, programming in the extreme short term, while fun, tends to breed certain otherwise undesirable development habits. This competition will promote a better development style. </p>
<p> In other awesome (semi) news, <a href="https://www.hackerrank.com/">HackerRank</a>, a website that is about solving fun programming tasks, has allowed Lisp submissions for a few months now. They allow you to submit programs that will be compiled and executed using a relatively recent version of SBCL (v1.0.55, I think). I have been fairly silent about this in the past as I have been working on something that should make HackerRank a whole lot more fun for us Lispers and a post about why it is necessary in the greater scheme of things, which I will be posting shortly. I just need to test it a bit first. But as it stands, you can use Lisp, and some of there tasks are, indeed, fun (they tend to be under the Artificial Intelligence category). There are also fairly boring problems (which tend to be under Algorithm Challenges, though still some good stuff there) and the extremely silly category of Code Golf (which has taught me that Lisp is a relatively verbose language, and that I am more than okay with that). </p>
<p> To people that are "working through Project Euler", unless you are a mathematician by trade, HackerRank is probably a much better use of your time if you are interested in improving your programming skills for the real world in any language. </p>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-61711273878921764142013-02-05T07:36:00.001-08:002013-02-05T07:36:33.264-08:00And So It Came To Be<p>Some time ago Denis Budyak <a href="http://lists.common-lisp.net/pipermail/iterate-devel/2012-October/000707.html">posted</a> on the Iterate devel mailing list regarding a patch that would allow Iterate to use keyword symbols for drivers and clauses. The Iterate devel mailing list was in general, and the current maintainer in particular, very quiet regarding this matter, scarily so, even. But I and one other user spoke out that we thought this was a bad idea. This is not exactly a consensus, but here were the basic arguments. Denis wanted to patch Iterate such that this was valid syntax. </p>
<pre class="src src-lisp">(iterate
(<span class="org-builtin">:for</span> (x y) <span class="org-builtin">:in</span> seq)
(<span class="org-builtin">:while</span> (some-predicate-p y))
(<span class="org-builtin">:collect</span> (list (f x) (g y))))
</pre><p> This removes one of the common annoyances that new users of Iterate have to grapple with; the <code>iterate</code> package exports a lot of symbols with very common names. For instance, people often times implement their own <code>while</code> macro as part of an introductory text. Iterate has its own while loop macro and this leads people to complain that they cannot have their <code>homebrew:while</code> and <code>iterate:while</code> imported into the same package (why they don't complain about other symbol names conflicts is a bit lost on me, I remember writing my own <code>with-gensyms</code> that I was relatively proud of). This patch would be a way around this. </p>
<p> My argument for not doing this was primarily that it would bifurcate the method by which Iterate is extended. For those that are not aware, Iterate is a DSL like Loop, but it is not as disjoint from standard Lisp as Loop is. Iterate is fairly transparently built out of standard Lisp macros and functions and, as such, Iterate is extended by writing standard Lisp macros and functions. Because of this "Lispy" design, symbols are not just syntactic markers for the DSL, they actually have meaning in the Lisp system at large. In this framework, the package system gives us the benefits of a divided name-space (as much benefit as it can give until the nickname business is figured out). </p>
<p> But in the end, I had to admit that this change wasn't likely to actually break anything so long as the original syntax was still allowed. I still oppose this change on the basis that it would muddy the waters of extension, raising the predefined drivers and aggregation clauses like <code>for</code>, <code>while</code>, and <code>collect</code> to a higher, irreplaceable status. For example, this would mean that I couldn't redefine the <code>for</code> driver. Even with all of this in consideration, I had to admit, this was a weak argument and these problems would never actually come up. Turns out, I was wrong. </p>
<p> Let's say, for instance, we find something that is more or less a bug in <code>iterate:for</code>. Let's say we find something that is basically just not the way that it should be done. For instance, why doesn't <code>for</code> accept normal <code>destructuring-bind</code> style argument lists? </p>
<p> The <code>destructuring-bind</code> construct will take apart a lambda list like the ones used in the <code>defmacro</code> forms. The <code>destructuring-bind</code> construct is a basic part of Lisp. And yet this will produce an error in standard Iterate: </p>
<pre class="src src-lisp">(iterate
(for (x <span class="org-type">&rest</span> y) in-sequence #((1 2) (3)))
(for (<span class="org-type">&key</span> (a 3) b) in '((<span class="org-builtin">:a</span> 1 <span class="org-builtin">:b</span> 2) (<span class="org-builtin">:b</span> 3)))
(collect (list x y a b)))
</pre><p> That just seems like it should work. Not only does it seem like it should work, it would be pretty darn useful if it did work. For instance, it would be easier to use lists as general purpose data containers because we can use keyword meta-data without an extra <code>destructuring-bind</code> cluttering the code. We can also use optional bindings, something that shows up a lot in the destructuring I do. This method of destructuring is inherently more powerful than the facility that Iterate currently has and it's more consistent with standard Lisp syntax. </p>
<p> This brings me to the point. Iterate has a defined <i>built in</i> behavior which I don't agree with. To me this feels like a bug, something that should be fixed. However, this fix is <i>not</i> compatible with the current behavior. One of the interesting aspects of Common Lisp is that any enhancement at all is usually not backward compatible because errors have a defined run time consequence. This means that there is a pretty good argument to not "fix" this. This seems at first like an impasse, and it would be if we were using Loop or a version of Iterate with the proposed patch. The extensibility of Iterate can save us here. </p>
<p> To summarize my options, I could: </p>
<ol>
<li>Patch my local Iterate so this works. This means that my code will not work with anybody else's version of Iterate. This is a non-option really. </li>
<li>Write a patch and petition the Iterate developers and community at large to accept this change. This is more attractive, but still deeply flawed. First, because errors have defined run-time behavior in Common Lisp, this is technically an incompatible change. Second, seeing as the maintainer didn't even weigh in on the previous discussion, I don't hold high hopes that any patch would be accepted in a timely manner. </li>
<li>Or, simply replace the <code>for</code> driver with <a href="https://github.com/smithzvk/destructuring-bind-iterate">my own</a>. </li>
</ol>
<p> This last option means I am able to make the change I want without approval from a community or maintainer (which may or may not be absent) and am able to do so in a completely portable, completely backward/forward/concurrently compatible way. With this method, I can make the change and start using it immediately in my own code. Meanwhile, I can publish the change and the maintainer can contemplate the benefits of such a change, and the community can make the decision for their selves on an individual by individual basis. In order to use it, just <code>(shadowing-import smithzv.destructuring-bind-iterate::for)</code>, or when you define your package: </p>
<pre class="src src-lisp">(<span class="org-keyword">defpackage</span> <span class="org-type">my-package</span>
(<span class="org-builtin">:use</span> <span class="org-builtin">:cl</span> <span class="org-builtin">:iterate</span>)
(<span class="org-builtin">:shadowing-import-from</span> <span class="org-builtin">:smithzv.destructuring-bind-iterate</span> #<span class="org-builtin">:for</span>))
</pre>
<p> If you want both behaviors, simply use <code>smithzv.destructuring-bind-iterate</code> which will import the new macro under the name <code>dfor</code>. Further, if the maintainer ever wanted to include this in Iterate, they have a working implementation that can be easily adapted to their code. </p>
<p> I am able to do all this because of the framework of extension that the proposed patch would uproot, or at the very least weaken. With the built-in macros and functions in Iterate implemented as keyword symbols, it would be impossible to create a drop-in replacement like this. I guess that in the end, this is the best argument I have as to why this change shouldn't be made. </p>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-72094866309016012542013-01-17T07:35:00.000-08:002013-01-17T07:35:12.992-08:00Soft-Semicolons: A little Emacs hack<p>I have been waging an all out war against the "Shift" key. I find that for programmers these keys, and in particular the left shift key, are used way too much. In my case, this overuse (paired with the common use of control key modifiers and the fact that my keyboard only has a control key on the left side) produced some <a href="http://directed-procrastination.blogspot.com/2011/06/emacs-pinky.html">numbness in my left pinky</a>. This has since been eliminated via removing most of the "shifting" I do on a daily basis by using the Programmers Dvorak keyboard layout. In the process of doing this, however, I realized how annoying and disrupting it is to actually type a shift+key sequence in general. I realized that the annoyance of typing a colon before a symbol is one of the primary reasons that I tend to use the slightly problematic standard symbol notation in Loop or Iterate: </p>
<pre class="example">(loop for i below 10 by 2 collect i)
(iter (for i below 10 by 2)
(collect i))
</pre><p> …rather than the more syntactically and stylistically pure keyword notation: </p>
<pre class="example">(loop :for i :below 10 :by 2 :collect i)
(iter (for i :below 10 :by 2)
(collect i))
</pre><p> So, partly as an exercise in Emacs Lisp and partly just to scratch this personal itch, I decided to modify Emacs behavior in order to make colons very cheap to type. One option is to switch the semicolon and colon on your key map. This makes semicolons more expensive to type, with would be a pretty big loss for C coding where semicolons are much more common than colons. This might lead to the unfortunate situation where your key bindings are not the same between different modes (first layer colons in Lisp, first layer semicolons in C). This is a pretty messy solution. </p>
<p> What I really wanted was to have certain semicolons be converted to colons in certain situations. For instance, if I write a semicolon and then follow it with text (with no whitespace in between), it is very likely that I am trying to write a keyword, so I would like the preceding semicolon to be converted into a colon. </p>
<pre class="example">;keyword -> :keyword
</pre><p> But it is certainly the case that if I write a semicolon, then whitespace, then some text, I am trying to write a comment. In this case I want to leave the semicolon alone. </p>
<pre class="example">;; Some comment -> ;; Some comment
</pre><p> Naturally, since this is a little hack to save using the shift key, I would like these conversions to be transient, i.e. they only attempt to convert the semicolons if the very next character decides it. For instance, if I move the cursor to the front of some semicolons and start typing, those semicolons should be unaffected (the '_' marks the cursor): </p>
<pre class="example">_
;;
;;_
;;some text -> ;;some text
</pre><p> There were a few ways I could think about doing this, but the aim is to be unobtrusive. My solution was to rebind the semicolon key and have it read the characters and commands you give until you give one that isn't "type a semicolon", in which case it decides if it should convert the semicolons it typed on not. This is based very closely on the code in kmacro, namely the function <code>kmacro-end-and-call-macro</code>, which uses the same mechanism to temporarily bind a key (typically "e") to repeat the macro you just performed. </p>
<pre class="example">(defcustom *soft-semicolons-also-convert-on* '(9 tab)
"This variable marks characters that will trigger semicolon
conversion in addition to the non-whitespace printable
character requirement.")
(defcustom *soft-semicolons-dont-convert-on* '(?( ?))
"This variable allows you to exclude certain characters from
triggering conversion.")
(defun soft-semicolons (arg)
"Type semicolons like normal expect if they are immediately
followed by a non-whitespace character, in which case convert all
of the consequtive semicolons you were typing into colons."
(interactive "p")
(let ((keep-going t)
(start-point (point)))
(insert 59)
(while keep-going
(let ((event (read-event)))
(cond ((equal 59 event)
;; A Semicolon, insert and keep going
(clear-this-command-keys t)
(insert 59)
(setq last-input-event nil))
((member event *soft-semicolons-dont-convert-on*)
;; For these special cases, don't do any conversion
(setq keep-going nil))
;; A non-whitespace printable character or something in
;; *soft-semiclons-also-convert-on*
((or (member event *soft-semicolons-also-convert-on*)
(and (integerp event)
;; See if this is a printable character
(aref printable-chars event)
;; Rule out whitespace characters (which might also be
;; printable)
(not (member event '(9 10 13 32)))))
(let ((length (- (point) start-point)))
(delete-region start-point (point))
(insert-char 58 length))
;; ...and exit...
(setq keep-going nil))
;; Exit on anything else
(t (setq keep-going nil)))))
;; Push any residual command back onto unread-command-events to be read and
;; processed
(when last-input-event
(clear-this-command-keys t)
(setq unread-command-events (list last-input-event)))))
</pre>
<p> Ironically enough, Common Lisp is one of the only languages I can think of where this soft-semicolon thing interferes with standard syntax. Logical pathname namestrings use semicolons as the delimiter between directories. These directories are necessarily whitespace dependent, and this means that this little hack will make it very annoying to insert logical pathname namestrings. I have never used a logical pathname, I'm pretty sure I never intend to, so I guess this isn't a huge concern for me. </p>
<p> I threw the <a href="https://gist.github.com/4556707">code</a> up on Github in case you'd like it. This is one of my first forays into Emacs Lisp coding, so I am even more grateful than usual for any comments on how this is implemented or how it could be implemented in a better way. </p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-25969813622901320482012-12-16T21:45:00.001-08:002012-12-23T16:38:45.913-08:00A Flat Dark Theme for Unity/Gnome 3I care a fair amount about the style and visual nature of my environment, not only from an appreciation of nice things, but also from a utilitarian standpoint. I use Unity and up until today, have been using a theme called <a href="http://gnome-look.org/content/show.php?content=146290">Zukitwo</a>, in particular the "brave" version of that theme. I used this as it was reasonably dark and stylish. Today I switched to a darker theme (the windows contents are actually dark), and one that I think I like a bit better, <a href="http://gnome-look.org/content/show.php/Boje_1.0.3?content=155857">Boje</a>. If you actually kind of like the minimalist thing that Google has been doing with their websites ever since Plus came out, and you would like a dark version of that style for your Unity/Gnome3 desktop, Boje might work well for you.
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipJaxzzstNprxq75fvHuVLsO1RT4Lh_7ya-Fr7s7NkRpQpy2dxDQBY8nwJZ8EXb5_lx7dPglWst-i-rRla-tnS5HHzV5WfbtKFXM4VT084pjMArVKtfwZFOlMuKYBUIYnqj0RKgJ7amaqO/s1600/Screenshot+from+2012-12-16+15%253A07%253A40.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="250" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipJaxzzstNprxq75fvHuVLsO1RT4Lh_7ya-Fr7s7NkRpQpy2dxDQBY8nwJZ8EXb5_lx7dPglWst-i-rRla-tnS5HHzV5WfbtKFXM4VT084pjMArVKtfwZFOlMuKYBUIYnqj0RKgJ7amaqO/s400/Screenshot+from+2012-12-16+15%253A07%253A40.png" /></a></div>
All you need to do is download the theme, extract it into the ".themes" folder in your homespace. Then you can select it using the Advanced Settings program under the theme option on the side-bar. Set the GTK+ and Window theme to Boje. Once you have done this your computer will, more or less, honor this theme. Technically, this will only apply for GTK apps, but luckily most applications that you encounter are GTK applications.
There is one hiccup that I've found, however. Firefox, for whatever reason, uses the system theme to color certain elements of web pages. Specifically, when using Firefox, input forms (e.g. text boxes, radio buttons, drop-down selectors) will have the background color of the system theme and, to make matters worse, tend to have the web sites text color. This means that many sites will have black bars on them which are actually search fields. You can type in them and they do what they are supposed to do, but you cannot see the text and they look ugly, which is more than a little bit annoying.
To fix this (at least partially) Firefox allows you to insert overriding CSS style into the pages you visit via a file <tt>~/.mozilla/firefox/yourprofile.default/chrome/userContent.css</tt>. If you edit this and insert a few styles that request that <a href="http://ubuntusatanic.org/forum/comments.php?DiscussionID=106&page=1">Firefox use white backgrounds on text fields this will make pages at least render readably.</a> This is a general problem with dark themes and Firefox and really should be fixed.
<br/><br/>
<h2>What About The Rest Of The World?</h2>
There is one issue with all this, while <i>you</i> might enjoy a dark theme, the rest of the world seems to have decided on bright backgrounds (something about thinking they look simple, or clean, or minimal). When you combine that with the fact that probably more than half your time is going to be spent in a browser window, you are going to be staring at and interacting with a lot of brightly themed interfaces anyway. But there is something we can do; we can extend our little hack for Firefox above to all web content and do it for Chrome as well using Stylish.
<a href="https://addons.mozilla.org/en-US/firefox/addon/stylish/">Stylish</a> is an extension for Firefox and Chrome/Chromium that allows users to fiddle with CSS styles (and perhaps more) on web pages that you visit. Think of it as a limited version of <a href="https://addons.mozilla.org/en-US/firefox/addon/greasemonkey/">GreaseMonkey</a> that is geared towards tweaking the visual style of pages. With Stylish installed you just click a button when you encounter a page that you don't like and find a style that fixes what bugs you. There are over 41,000 user submitted styles <a href="http://www.userstyles.org">out there</a>, but importantly they don't usually work forever (pages constantly change and the Stylish scripts will need to be tweaked). This means that the vast majority of these actually don't work completely. It is a process of trial and error, but it is easy to turn off malfunctioning style scripts. I guess I feel that they are worth the effort as they are exactly the best possible solution to this problem if they work, and sometimes they do. They allow you to do the following:
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgt-dW_L0ZthJhErrNyTfbm4Gg5Z6_5zpF0iUArZAeKwxiCcdEfcp6Wxu2kVSiEnT7alMtqDr2MSMHPCo3FOIj5ttye8P9-cAz3435RLKeHWzPypGuJwZiplEx3aCUBwrCEgeV_abZtEF8T/s1600/reddit-with-stylish.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="267" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgt-dW_L0ZthJhErrNyTfbm4Gg5Z6_5zpF0iUArZAeKwxiCcdEfcp6Wxu2kVSiEnT7alMtqDr2MSMHPCo3FOIj5ttye8P9-cAz3435RLKeHWzPypGuJwZiplEx3aCUBwrCEgeV_abZtEF8T/s400/reddit-with-stylish.png" /></a></div>
<br/><br/>
<h2>When all else fails</h2>
I find that it is good to have a quick and dirty method to save your eyes if you have a non-GTK app or your Stylish script is broken or things are just generally not working. For this, I use Compiz's "Negative" plugin which you can configure using Compiz Configuration Settings Manager or <tt>ccsm</tt>. This plugin allows you to invert the video on a per window basis at the press of a key chord. I have bound "Super-n" to this functionality. This is far from ideal. This inverts all video which mean that all of the colors are screwed up when we use it, which makes video and images look like crap. But it is a useful fall-back method.
<p><i>Update: </i>Firefox can really look the part if you install the <a href="https://addons.mozilla.org/en-us/firefox/addon/bright-aero/">"Dark Bright-Aero"</a> theme.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-7788284466297989064.post-18816546770554991182012-11-01T22:41:00.000-07:002012-11-01T22:44:58.068-07:00No More Coursera Starter KitI just finished the latest Coursera assignment minutes before the deadline (a deadline that was extended due to Hurricane Sandy). The assignment was not hard, but it certainly was time consuming. Clearly I will be unable to put out a starter kit in any timely manner. But, more importantly, I realized something when working through the assignment, this code that they have offered is a mess. The act of porting this to stuff to Common Lisp would be a nightmare. It is much better to rewrite the stuff. The problem with this is that the actual assignments more or less require you to use the Octave code as it does things like sample from a random distribution. It would be annoyingly difficult to guarantee that any code I wrote would sample the distribution the same way, especially since they use a built in MatLab/Octave routine. I would have to research what PRNG Octave uses and likely implement it and make sure to seed it with whatever Octave is using.<br />
<br />
The other thing I realized when working with the perceptron code is that writing starter code sucks for the programmer. Writing code that has trivial pieces missing from it on purpose is not how I want to spend my time. Creating teaching materials requires a crazy amount of prep-time and I don't care enough about education to spend all that time and, in the end, am left with nothing but a classroom exercise that cannot even be used for tinkering at the REPL.<br />
<br />
This has lead me to the decision to stop my already feable attempts to maintain a Common Lisp port of the neural network starter code. However, I still find that porting code is extremely useful in making sure you understand the concepts involved in the code. I have always felt that once I could write the code for something, I tend to truly understand it. So I will be taking the provided code from the course as a starting point and creating my own neural network related code, closely in parallel with the course, in Common Lisp. I will not be leaving out the missing pieces as they do in the class.<br />
<br />
I have decided that this won't really violate any rules of the course. Looking at my perceptron code and the code that was released by the class organizers I doubt that any person would see one as derivative to the other if they didn't already know I was working off the other. Further, I doubt that any person that couldn't answer the questions in the programming assignments using the MatLab code could look at my code and identify the pieces that needed to be ported back. And it isn't as if executing the Lisp code will help them at all. As I said, I doubt I could actually write code that would give the correct numerical answers for the homework even if I wanted to because of the MatLab/Octave heavy emphasis in the provided code. I was able to just barely do it in the perceptron case and it probably took about half the development time to figure out how I would load the MatLab data and exactly match their form of the learning algorithm.<br />
<br />
If you are following this work, I will probably stay on the same git repository for a while, but might switch to another more appropriately named one in due time. Hopefully I will have a little toy neural network library to play with in a few weeks.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-28921515762181372982012-10-19T13:48:00.000-07:002012-10-19T13:50:28.158-07:00Neural Networks, Coursera, and Common LispThere is a <a href="https://class.coursera.org/neuralnets-2012-001/class/index">course</a> offered on machine learning using artificial neural networks offered at <a href="https://www.coursera.org/">Coursera</a> this "semester". I am taking it and it is my first class I have taken with Coursera. I have forgotten how nice it is to learn a new subject.<br />
<br />
Besides the fact that artificial neural networks have always interested me, one of the reasons I decided to take this class is to become somewhat fluent in Python, which for some reason I thought would be one of the supported languages. Turns out it isn't, but no matter. Python is popular enough that <a href="https://github.com/davidandrzej/py-coursera-neural">someone will always port to Python</a>.<br />
<br />
I figure I might as well do the same for <a href="https://github.com/smithzvk/cl-coursera-neural">Common Lisp</a>. This is very late for the first assignment, and I make no promises that it will be more timely in the future. I decided not to do a line by line porting of the Octave or Python code to Lisp because, well that's just not how we Lispers do things. It is cleaner in its current form, but harder to prove correct at a glance. Also, I will be using some packages that I have been working on but are not officially released, such as my <a href="https://github.com/smithzvk/ZGnuPlot">zgnuplot</a> library. I have been using this plotting library with in-house code for a long time, but it is still pretty rough around the edges and the interface is still in flux (hopefully headed towards something a bit better). But whatever, it's out there, feel free to do what you will with it.<br />
<br />
Note to people that might fork this, the rules on Coursera (well, at least this course) is that you shouldn't post solutions. So don't work off this repo, plug your solution into it, and publish it online. You should probably work in a private branch that you don't publish to Github.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7788284466297989064.post-42286724272254099642012-09-25T12:26:00.000-07:002012-10-02T06:50:34.797-07:00Stallman on Steam on GNU/Linux<p>In July, Valve announced that they were in the process of <a href="http://blogs.valvesoftware.com/linux/steamd-penguins/">porting Steam and a handful of games to GNU/Linux</a>. Shortly after, Stallman put forward <a href="https://www.gnu.org/philosophy/nonfree-games.html">this statement</a> on the benefits of porting Steam to GNU/Linux. In this delightful and surprising opinion statement, he argues that the gains of video game loving people switching their OS, the foundation of all of the their computation, to a Libre alternative displaces the damage done by Steam moving to GNU/Linux. Now, we should all note that while Stallman can give his opinion until he is blue in the face and it doesn't necessarily mean anything. GNU/Linux is Libre Software and, by the definition of Libre Software, has nothing to say about what software can or cannot be run on the system.<sup><a class="footref" name="fnr.1" href="#fn.1">1</a></sup> Be that as it may, Stallman's opinion does hold some weight for some for the community. </p>
<p> What is interesting is that this is a huge departure from the opinions Stallman typically expresses. From what I've seen, Stallman has never been one for compromise when it comes to Libre Software, even when that compromise would almost certainly result in benefit to the Libre Software community. As an example, you can listen to <a href="https://www.youtube.com/watch?v=radmjL5OIaA">Bryan Lunduke and Chris Fisher's conversation with Stallman</a> on the "GNU/Linux Action Show." <a href="http://lunduke.com/">Lunduke</a>, who dominated the discussion, was looking for tips on how he could transition from a proprietary software developer into a Libre Software developer. In particular, he was looking for information on how he could do this and still support his family. Now, I'm not claiming that Lunduke is a programming superstar, or that Lunduke's software is so great that having it released as open source is a clear and substantial benefit for the community. I don't really know what effect his software would have for anybody. I will say that having a guide of how to transition to Libre Software development, even if only partially, would be a great help to the community, and reiterating the message of the Free Software Movement to any captive audience is likewise a benefit. Stallman's response was implicitly that that an independent developer (i.e. someone that makes their living selling digital copies of their software) simply cannot currently support themselves with Libre Software development. What he <i>actually</i> said, however, was that Lunduke should seek a new career. Specifically, his point seemed to be that comparing the viability of "for profit" Libre Software development to proprietary software development was a futile exercise since proprietary development is unethical and akin to "burglary". It might or might not make you money, but it should not be done for ethical reasons. While I agree with the gist of the statement, arguing with extremes like comparing a relatively minor restriction of people's freedom to something like burglary is frowned upon by most people. More to the point, I feel that many more minds can be won over when an understanding and softer, but still firm, voice is used. I invite you to watch the whole interview, as infuriating as it is. By the way, if you come off thinking that this Lunduke fellow was treated unfairly and that Stallman is a d-bag, you might watch the following week's episode where Lunduke throws a multitude of <i>ad hominem</i> attacks against Stallman, which will probably make you reassess where the d-baggery lies. </p>
<p> I bring up all of this so that the context is clear of what Stallman's opinion of compromise has been in the past. This opinion on Steam seems nearly 180 degrees out of phase from the standard Stallman opinion. It is not that I see this as antithetical to the advancement of Libre Software, quite the contrary as I will argue, but I do see it as not keeping with Stallman's usual position on the mixing of Libre and proprietary software, much less DRM laden software. It should not be lost on us that Steam is perhaps the most visible DRM peddling marketplace in existence today. <i>This</i> is the software that Stallman is tacitly <i>ok</i> with. </p>
<p> I wonder if this is a change in Stallman's strategy for promoting Libre Software usage. I wonder if he now sees more benefit performing a bit of social engineering rather than just leading by example. At the very least, for people that say that Stallman is not able or not willing to compromise or see the bigger picture (which I have been guilty of a few times) this should demonstrate otherwise. Whatever the reason behind this change of opinion, tone, or otherwise, I think that this is a good thing that hopefully we will see more of. </p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1">A Libre Software ecosystem </h2>
<div class="outline-text-2" id="text-1">
<p> I think that Stallman might be understating some of the indirect benefits of having Steam on GNU/Linux. Windows dominates the computing world because it has many users. It has those users because it has developers writing software. It of course has those developers writing software because it has all those users, who are willing to pay money. This self-sustaining ecosystem is something to be sought in the Libre Software world. Anything that can be used to bootstrap this, should be sought out. And yes, this means that people in the Libre Software world will need to get used to the idea of paying for what they want if the desire this kind of ecosystem.<sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup> This is not difficult to work out. A developer only has so much time, some of this time needs to be used to make money to live, thus if they can make money developing free software there will be more free software. This is the reason I feel that the funding problem is the number one problem to tackle for the Free Software Movement.</p>
<p> The problem is, an ecosystem takes a long time to build up <a href="http://thenextweb.com/mobile/2012/09/04/rim-announces-free-blackberry-10-app-submissions-guarantees-youll-earn-10k-make-1k/">unless you are willing to pump vast amounts of money into it</a>, and maybe it doesn't grow even if you do. It takes a long time to build, but what if you can have an already established ecosystem migrate to you? Valve has been relatively candid about their <a href="https://encrypted.google.com/search?q=Valve+windows+8">dislike of the direction that Microsoft is headed in</a>, and who could blame them? There are some shaky decisions coming out of Microsoft and things are probably going to get much worse before they get better (if they do). I am expecting a pretty large exodus of users fairly soon. </p>
<p> The question becomes, where will these users go? Presumably, many will switch to OS X. However, as many have noted, Apple has some quite disturbing opinions (along with the track record to back it up) about what rights the users and developers of software for their iOS should have. When these <a href="http://www.cultofmac.com/107445/apple-will-murder-os-x-and-replace-it-with-ios-on-all-macs-starting-in-2012-report/">limitations by Apple land on OS X</a>, I expect that it will very likely discourage many Windows users from moving to that OS. This is made all the more troubling when you see Microsoft starting to tread down the same path Apple travelled as they seek to regain some of their lost market share and profits. These kinds of decisions by the major players in the field are a strong incentive for diversifying your product to a stable, yet non-restrictive OS. </p>
<p> Thus Valve decided to port Steam to GNU/Linux. I think the motivation of Valve's decision is just plain business sense. They want to buy some "Windows and Microsoft falls apart and not everybody likes Apple" insurance. This is a good way to hedge their bets on where their users will end up and ensure a longer life should Microsoft continue to make poor decisions. Further, they will have a substantive advantage over late comers to the GNU/Linux platform if it does indeed become popular amongst gamers. But the reasons for their decisions aren't what I am focusing on; I am interested in what effect we should expect for Libre Software. </p>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2">The benefit and harm of Steam on GNU/Linux </h2>
<div class="outline-text-2" id="text-2">
<p> In a <a href="http://directed-procrastination.blogspot.com/2012/04/kickstarter-video-games-and-gnulinux.html">recent post</a> (see the last section), I made a particularly <a href="http://esr.ibiblio.org/?p=4371">Raymond-esque argument</a> that the importance of having something be Libre is directly proportional to how important that software is to your life and livelihood.<sup><a class="footref" name="fnr.3" href="#fn.3">3</a></sup> I concluded that proprietary video games are "ok" so long as they don't come with even a hint of DRM. Because of this "no DRM" standard, I will most likely never pay any money for any software sold via Steam, nor do I think anybody should for that matter, though I know and accept that many will. </p>
<p> The point is, once you accept this argument for proprietary games and <i>proprietary</i> stops being your cut-off for completely unacceptable, you start seeing shades of gray and you will most likely come to the conclusion that <i>proprietary may be bad, but DRM is worse</i>. It is a matter of degree. DRM in software marks that extra step past software that is merely proprietary but non-abusive to something which is, in fact, abusive. DRM is in its very essence not in the users best interest, the epitome of an anti-feature. In addition, DRM is very often more abusive than the original authors intended it to be, hurting "legitimate users" as well as copyright infringers. DRM is almost by definition the act of <i>abusing</i> the proprietary nature of the application in order to actively restrict a user's freedom in a very overt and measurable way. DRM is <i>the actual boogie man</i>, or one of them, that the FSF has been warning about for all these years. Here he is, in the flesh, right where we can all see him. </p>
<p> This makes me wonder if this move by Stallman is a bit more diabolical than it initially seems. I suspect that if there is one place where proprietary software is unlikely to "teach users that the point is not freedom," video games are it. To the average user, a video game is a piece of software that is the epitome of luxury. From a practical point of view, a video game is only as good as the art that goes into it, and from Stallman's point of view, Libre art is of much lower priority than Libre Software (which I agree with). What I think might be the ultimate result of DRM video games in GNU/Linux is a better appreciation and understanding of the main goals of freedom in Libre Software rather than an erosion of these ideals. </p>
<p> By letting the boogie man run around your town and terrorize your citizens, it often has the result of people increasing their support for the white knights that have devoted their life to protecting users from that boogie man. What better way to ensure a boogie man that will be noticed but not cause too much damage than to let in DRM, which is today basically synonymous with proprietary software abuse, but only in video games, which are hugely popular but basically synonymous with luxury? We may even get a few new white knights out of it. When these new GNU/Linux users boot up and find a wealth of software, in fact an entire operating system, all of which is devoid of DRM, lock-in, and excessively high pricing, they might, <i>just might</i>, start to associate proprietary with restriction, DRM, and "annoying to use" while, at the same time, start to associate Libre/Free/Open Source with freedom and, <i>gasp</i>, "easy to use." In fact, if we <a href="http://www.xonotic.org/">continue</a> to <a href="http://wildfiregames.com/0ad/">produce</a> these <a href="http://ufoai.org/wiki/index.php/News">pretty</a> <a href="http://www.warsow.net/">impressive</a> <a href="http://freegamer.blogspot.com/">Libre video games</a>, people might start to wonder what they need Steam for at all. </p>
<p> <i>And if Steam isn't overtly abusive? What if people accept it and like it?</i> You don't get this effect I describe, true, but you still have Stallman's original point: more users of Libre Software means more freedom for users. You alse get more people familiar with developing for GNU/Linux and, arguably, increase the pool of developers that might write Libre Software in their free time. More or less, this is a win however you cut it, but it might be a bigger win than Stallman lets on. </p>
</div>
</div>
<div id="outline-container-3" class="outline-2">
<h2 id="sec-3">The year of the GNU/Linux Desktop? </h2>
<div class="outline-text-2" id="text-3">
<p> I know, this has been speculated about to death. But with MS actively imploding under user disappointment and Apple encroaching further and further on users' freedoms, there could very likely be a sizable of portion of the community that is just lost enough to jump to Ubuntu or similar. </p>
<p> The upshot of all this is that GNU/Linux is actually is a very good position to accomplish at least Torvald's initial dream, a sizable install base for Linux based systems on the desktop/laptop, and a large part of the FSF's goal, to get more people using more Libre Software. I know it has been said before, but right now I see a possible inflection point. If Microsoft continues to tank on their desktop/laptop software (which seems very likely), Apple continues to make their desktop/laptop computing environment more like the restrictive iOS,
GNU/Linux gets Steam and game developers start to develop for GNU/Linux, and
provided we find a good way to financially support Libre Software, there is a
very good chance for a vast increase of the install and developer share. This
increase will, at the very least, increase the number of users that have control
over their own computers even if there will be a few, non-essential, pieces of
software that will be out of their control due to DRM. Stallman is correct to
encourage Valve's port of Steam to the GNU/Linux platform.
</div>
</div>
<div id="footnotes">
<h2 class="footnotes">Footnotes: </h2>
<div id="text-footnotes">
<p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> It should also be noted that prior to fairly new positions by Apple in their iOS, this would be a silly thing to even bother to say. Before that it would be considered financial suicide to do so. Thank you, Apple…
</p>
<p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> That is not to say that I don't see the great benefit in having Libre Software also be gratis, but these ideas are not totally at odds with one another.
</p>
<p class="footnote"><sup><a class="footnum" name="fn.3" href="#fnr.3">3</a></sup> I actually have walked back my opinion a bit. I got to thinking about my sister, who sees video games as a social tool. As a social tool, this now becomes an important part of her life. I would wager that there are many people out there just like my sister. It would be arrogant of me to argue that just because I find something to be "purely a luxury" means that this is true for everyone. If I wish others to respect my opinions on what is important enough to be Libre Software, I should respect that others might find something I think of as non-essential as important enough as well.
</p>
</div>
</div>
Unknownnoreply@blogger.com0