tag:blogger.com,1999:blog-43308155780908712422024-03-14T00:38:29.944-05:00A Partially Applied LifeJGhttp://www.blogger.com/profile/03743060905097691224noreply@blogger.comBlogger29125tag:blogger.com,1999:blog-4330815578090871242.post-812920263292616422013-10-30T15:14:00.000-05:002013-10-30T15:14:11.122-05:00OpenSCAD - 3-D modeling script language<p>
I had been looking for some easy-to-use 3-D CAD software which runs on Linux, and is preferably open-source. The goal is to design and build stuff like this <a href="http://www.diybookscanner.org/">Do It Yourself Book Scanner</a>, where all the pieces can be cut out of a 4x8ft sheet of plywood or maybe thick plexiglass.
<p>
I had initially passed over <a href="http://www.openscad.org/">OpenSCAD</a> because it seemed that it was more about assembling 3-D renderings from 2-D CAD files. However, I had cause to look at it again this week, and I like it a lot better this time.
<p>
The basic idea is that you create a script that draws out 3-D primitives (cube, sphere, cylinder, etc.) and add / subtract them to make objects. What follows is an example.
<p>
Here is a small module for a part.
<pre>
module flange() {
difference() {
translate([1,0,-1]) cube([8,4,2]);
translate([7,2,-1.1]) cylinder(h=2.2,r=1,$fn=100);
}
translate([-1,2,-1]) cube([2,2,2]);
translate([-3,0,-1]) cube([2,4,2]);
}
</pre>
<p>
Here's the code to actually call the module to render it.
<pre>
color("LightBlue") flange();
</pre>
<p>
And this is what it looks like:
<p>
<div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-jg9b2Tfkmo4/UnEMZ6DkcJI/AAAAAAAAAGc/5D2caT3d0bA/s1600/one_flange.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-jg9b2Tfkmo4/UnEMZ6DkcJI/AAAAAAAAAGc/5D2caT3d0bA/s320/one_flange.png" /></a></div>
<p>
The modules can be called multiple times, for example here to make interlocking parts:
<p>
<pre>
rotate(a=[180,-90,0]) translate([0,-4,0]) flange();
</pre>
<p>
Both of them rendered looks like this:
<p>
<div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-xMrfUX4uuuA/UnEMcnTFEoI/AAAAAAAAAGk/s1vsH7sz63c/s1600/two_flanges.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-xMrfUX4uuuA/UnEMcnTFEoI/AAAAAAAAAGk/s1vsH7sz63c/s320/two_flanges.png" /></a></div>
<p>
Where this is becoming handy (at least for me) is that I can create a module which renders the finished assembly, with all the component parts moved into the proper place for the design, similar to the above, and see how all the cut-out parts will fit together.
<p>
It is then easy enough to use the same components and have them all laid out in a single plane. I can then <a href="http://rasterweb.net/raster/2012/07/16/openscad-to-dxf/">convert the drawing to DXF</a>, open it in LibreCAD, set the actual dimensions, and go!
<p>
That is very neat. Overall, this is quite a different experience than what you get with a traditional CAD environment, but it more suits me as a programmer. Conditionals, math formulas, loops and such are possible with OpenSCAD, so that makes some kinds of designs much easier.JGhttp://www.blogger.com/profile/03743060905097691224noreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-79811205687968580252010-06-08T22:03:00.001-05:002010-06-09T11:00:33.999-05:00Writing Code on HandheldsI was emailling recently with someone about doing development on handheld devices. Not just writing software <i>for</i> handheld devices, but what it is like to actually write code <i>using</i> a handheld device as the development platform.<br /><br />What follows is a description of my mobile development environment, and the ups and downs of using current generation phones for software development. <br /><br /><hl><br />I've wanted a decent, portable Linux machine to do hacking on for a long time... dating back to the days when I was messing around with trying to get a cut-down version of Linux running on a HP 100 LX palmtop. And now I'm finally there.<br /><br />My current mobile phone is a HTC Dream (a.k.a. the T-Mobile G1). I actually bought the unlocked ADP1 version directly from Google. It is currently running a custom Android 1.5 firmware (cupcake). Since everything basically works (like phone calls), I haven't been on the upgrade treadmill... though I'll definitely upgrade to CyanogenMod CM6 when Android 2.2 (froyo) is released.<br /><br />For doing code development on this device, I'm using the excellent <a href="http://code.google.com/p/connectbot/">ConnectBot</a> as a local terminal program. This is far superior to the Google terminal.<br /><br />After partitioning an 8GB micro-SD card (2GB for FAT32, 6GB for ext2), I was then able to install Ubuntu Jaunty userland using <a href=" http://xdatap1.wordpress.com/2009/05/03/jaunty-under-android/">Paolo Sammicheli’s instructions</a>. So that gets you: Python and Lua, VIM, screen, ssh, rsync and GCC. A decent browser, always-on (if slow) Internet, WiFi, Bluetooth, expandable storage... and it makes phone calls too! How cool is that? <br /><br />I've been using Mercurial for my DVCS, but the Ubuntu packages weren't available. However, I was able to just download the source and run it on the G1 as well.<br /><br />For the code I write, I'm not accessing any of the phone's features, nor am I trying to make regular Android applications. If I were, though, there is the <a href="http://code.google.com/p/android-scripting/">Android Scripting Environment</a> available, through which you can also use <a href="http://www.lua.org">Lua</a>.<br /><br />As far as editing code on a small mobile device, the major pain points are exactly what you'd expect: screen size, keyboard, overall speed and storage.<br /><br />With ConnectBot, I can get a 80x22 terminal window... using a tiny font. So that's kinda OK. And using GNU screen here helps a lot by just being able to flip between my edit window and the compile / run window. <br /><br />But not having a browser window open on a 2nd monitor slows me down a lot. Sometimes I can get by with Lynx in another console window, but that isn't too fun.<br /><br />As far as the keyboard goes, the G1 is completely superior to any other phone keyboard I've ever seen. For starters, it has dedicated number keys, and the brackets, parens, and other ASCII symbols are all available with a single Fn button push. This is in marked contrast to other phone keyboards which would make typing code in any programming language much more painful.<br /><br />That said, the keyboard does slow me down. I don't type real fast (maybe 60 wpm normally), but the phone's keyboard slows me down enough to interfere with my thought processes.<br /><br />As far as speed goes, it is not too bad really. I don't do heavy number-crunching or work with large data sets, and Lua is one of the fastest scripting languages anyway. But if I do start dealing with large data sets, the phone will be unacceptably slow compared to a desktop.<br /><br />There are some new chips on the horizon (like Nvidia's dual-core Tegra 2) that should improve things considerably. I'd like to see that in somethine like the <a href="http://www.open-pandora.org/">OpenPandora</a> form factor (though I have issues with that particular product).<br /><br /><hl><br /><br />So how good is this platform really? Is the environment good enough for short edits, like fixing a bug?<br /><br />Yes, it definitely works fine for stuff like that. I do write short segments of code on it too, when I don't feel like breaking out the netbook. <br /><br />Do note that I only use VIM for code editing, which works way better for this handheld device.<br /><br />For instance, since I don't use 'find letter' commands in VIM, I've mapped 'f' to page down and 't' to page up. So I'm not hitting control key combinations very often. That is a two step process in the ConnectBot terminal program... you have to press the trackball button, and then 'f' for Ctrl-F. There is no dedicated ESC key either, that is mapped to a double press of the trackball button, which isn't too bad.<br /><br />If I was using Emacs or any other non-modal editor, code editing would be a lot more painful, and I'd have to rely on using the trackball to move the cursor around. And that would be very slow.<br /><br />Code editing in general is going to be a problem for any mass-market handheld device I'd expect. I've never seen one with a dedicated ESC key, Ctrl key, or (hah!) an Alt key (in the desktop keyboard sense). These devices are optimized for typing in plain text, not editing. And definitely not code editing.<br /><br />ConnectBot has other nifty features. For GNU Screen you can map the phone's camera button to 'Ctrl-A Space', to switch to the next terminal window. You can also map a short press of the right ALT key to be '/', and a short press of the right shift key to be Tab. So typing in paths and autocomplete are easy.<br /><br /><hl><br /><br />I've looked at some of the other Android phones that have keyboards, but most don't have dedicated number keys. Many also don't have some important symbols mapped to the alt-keys. Typically these symbols are missing: { } < > [ ] ~ _ \ Whereas the G1 has all of these as Fn-keys. It is probably possible to type in those symbols on other phones, but it may require a three key press combination. :-(<br /><br />The Motorola Android phones are examples of the ones that have less keys on their keyboards. And my co-workers tell me that typing on the Droid isn't that fun anyway, the keys are too close together. <br /><br />Other phones with possibly acceptable keyboards include the LG GW620 and the Samsung SPH-M900 'Moment'. I'm not sure what it takes to get root on those phones though. I bought the developer version of the G1, so it was easy to load custom firmware and get root.<br /><br /><hl><br /><br />So, in summary, if you're satisfied with the tools I normally use: GNU Screen, VIM, ctags, and command-line everything else, the G1 phone is about as good as it gets for ultra-portable hacking right now. With some practice, I've been about to get up to about 30wpm on the G1's keyboard for English text. <br /><br />My dream phone would have a slightly larger screen, about 4.2in. We don't have to go crazy-high resolution, WVGA would be fine. The keyboard could be a little bigger, with the keys spaced out a little more. But not too much! I still want to use just my thumbs, without having to stretch.<br /><br />More important though would be dedicated ESC, Tab, '/', Control and Alt keys. I can live with the symbols being Fn-key combinations. Other minor touches would include re-programmable shoulder buttons.<br /><br />More speed and storage would of course be welcome. Qualcomm has talked about dual-core 1+ GHz Snapdragons, so that would be excellent. I'd also want at least 512MB of RAM. Full support (and APIs) for OpenGL ES and OpenVG would make GUI applications real zippy.<br /><br />Designing that sort of thing is actually my day job too. But I can't justify the hundreds of thousands of dollars to just make one for myself. :-)Unknownnoreply@blogger.com6tag:blogger.com,1999:blog-4330815578090871242.post-20335943156527883802010-02-11T09:25:00.005-06:002010-02-11T09:39:56.692-06:00Lua for "Artificial Intelligence - A Modern Approach"I've started a Google code project for a Lua implementation of the algorithms from the Stuart Russell and Peter Norvig book <a href="http://aima.cs.berkeley.edu/">Artificial Intelligence: A Modern Approach</a>.<br /><br />I'm planning on working through the book, chapter by chapter, and creating Lua implementations of everything. In general, I'll try to stick to the spirit of the algorithms presented in the book, though there may be ways to implement them it in a more elegant and concise fashion using Lua's unique strengths.<br /><br />Emphasis too will be on code that is "production ready", meaning that it can be readily incorporated into other projects.<br /><br />The style of the code will vary. If it makes sense to use OO style, great. If functional seems a better fit, then I'll use that instead. I'm not as dogmatic about that kind of thing as I used to be.<br /><br />I'm using a <a href="http://mercurial.selenic.com/">Mercurial</a> repo, so if you'd like to contribute, just clone it and get going!Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-4330815578090871242.post-19402315614217427182009-11-25T06:17:00.001-06:002009-11-25T06:35:02.887-06:00SWIG and LuaSo I've been trying out SWIG with Lua recently. This was to wrap a 3rd party C library that I didn't have source for.<br /><br />The initial wrapping went pretty smoothly. The only problem was that the library had its own typedef of 'bool' as an unsigned char, but SWIG treated that as a syntax error. I had hoped to avoid making copies of the header files, but ended up doing that and so commented out the typedef.<br /><br />I was also a bit disappointed with the handling of some pointer types. Suppose you've got a function that takes a pointer to a double. I had expected that I could just call the wrapped Lua function with a Lua number and have that handled automatically. But I ended up declaring some pointer types, creating those C-based objects, and using those. There is some means with SWIG to declare pointer args, but I need to read that section of the docs again.<br /><br />Similarly, I wanted to just pass in a table of strings and have that automatically converted to 'char **', but that is not automatic either. So that code on the Lua side is klunky too. I'm not sure that can be fixed.<br /><br />I'll have to investigate luabind and toLua more.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-64411506875274310572009-10-23T17:23:00.004-05:002009-10-26T15:04:53.311-05:00List Library for LuaI've updated my <a href="http://home.xnet.com/%7Eansible/lua/list_library.lua">List Library for Lua</a> which is inspired by Haskell's Data.List library.<br /><br />I've had some interesting discussions about possibly specifying the arity of the list functions like for map() and filter(). Other implementations of these list functions take only one list, and any extra arguments are passed to the function called by map().<br /><br />This lead to me trying an implementation where the 2nd argument to map() was the arity of the function passed in, call it N. The next N arguments are lists to be iterated over, and any arguments beyond that are passed as-is to the function. A quick example can easily illustrate:<br /><br /><blockquote>function div(x, y) return x / y end<br /><br />map(div, 2, {99, 21, 6}, {11, 7, 3}) -> {9, 3, 2}<br /><br />map(div, 1, {99, 21, 6}, 3) -> {33, 7, 2}<br /></blockquote><br />Finally though I decided (at least for my own library) that explicitly specifying the arity was too cumbersome. If you need to a more sophisticated used is needed, some kind of wrapper for currying will be needed. Here's the 2nd use of map() above:<br /><br /><blockquote>map(function(x) return div(x, 3) end, {99, 21, 6}) -> {33, 7, 2}</blockquote><br /><br />Obviously this is a little clunky. If you're using <a href="http://metalua.luaforge.net/">MetaLua</a> lambda construct (or the power patch), this is considerably shortened:<br /><br /><blockquote>map(|x| div(x, 3), {99, 21, 6}) -> {33, 7, 2}</blockquote><br />I would really like the lambda construct accepted into mainline Lua.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-8456013761101228412009-10-10T04:55:00.002-05:002009-10-10T05:04:05.118-05:00Fortunately, I had another copy on my phone...This is just an amusing anecdote.<br /><br />I was trying to download and install Reuben Thomas' <a href="http://luaforge.net/projects/stdlib/">stdlib</a>. However, I'd been having problems actually downloading the file from LuaForge.<br /><br />However, since I had set up the same Lua development environment on my Android phone, and I had previously installed stdlib release 12 on that, I was able to just scp over the tar archive to my laptop.<br /><br />I'm still trying to remember how we all got by the the dark ages before we had the Internet. And phones that have gigabytes of storage. Seriously, what did I do before wireless LAN was widely available?Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4330815578090871242.post-76089876198933891732009-09-28T00:32:00.000-05:002009-09-27T04:38:04.033-05:00Resource Cleanup in LuaI recently got the <a href="http://www.lua.org/gems/">Lua Programming Gems</a> book, in part because I was interested in John Belmonte's chapter on Exceptions.<br /><br />Here's the scope function that John created for the GEM article. Please refer to that article for further explanation of the rationale.<br /><br />I've made some minor modifications to it to use the <a href="http://coxpcall.luaforge.net/">coxpcall function</a> from Kepler.<br /><pre><br />function scope(f)<br /> local function run(list, err)<br /> for _, f in ipairs(list) do f(err) end<br /> end<br /> local function append(list, item)<br /> list[#list+1] = item<br /> end<br /> local success_funcs, failure_funcs, exit_funcs = {}, {}, {}<br /> local manager = {<br /> on_success = function(f) append(success_funcs, f) end,<br /> on_failure = function(f) append(failure_funcs, f) end,<br /> on_exit = function(f) append(exit_funcs, f) end,<br /> }<br /> local old_fenv = getfenv(f)<br /> setmetatable(manager, {__index = old_fenv})<br /> setfenv(f, manager)<br /> local status, err = copcall(f)<br /> setfenv(f, old_fenv)<br /> -- NOTE: behavior undefined if a hook function raises an error<br /> run(status and success_funcs or failure_funcs, err)<br /> run(exit_funcs, err)<br /> if not status then error(err, 2) end<br />end<br /></pre><br />David Manura wrote a couple test scripts for his <a href="http://lua-users.org/wiki/ResourceAcquisitionIsInitialization">Resource Acquisition Is Initialization</a> proposal. Here they are modified for John's scope() function.<br /><br />This is a basic test:<br /><pre><br /><br />-- Define some resource type for testing.<br />-- In practice, this is a resource we acquire and<br />-- release (e.g. a file, database handle, Win32 handle, etc.).<br />local Resource = {}; do<br /> Resource.__index = Resource<br /> function Resource:__tostring() return self.name end<br /> function Resource.open(name)<br /> local self = setmetatable({name=name}, Resource)<br /> print("open", name)<br /> return self<br /> end<br /> function Resource:close() print("close", self.name) end<br /> function Resource:foo() print("hello foo", self.name) end<br />end<br /><br />local test3 = function()<br /> scope(function()<br /> local f = Resource.open('D')<br /> on_exit(function() f:close() end)<br /> f:foo()<br /> print("inside test3\n")<br /> error("oops")<br /> end)<br />end<br /><br />local test2 = function()<br /> scope(function()<br /> on_failure(function(e) print("leaving test2 ", e) end)<br /> local f = Resource.open('C')<br /> on_exit(function() f:close() end)<br /> test3()<br /> end)<br />end<br /><br />local test1 = function()<br /> local retval<br /> scope(function()<br /> local g1 = Resource.open('A')<br /> on_exit(function() g1:close() end)<br /> local g2 = Resource.open('B')<br /> on_exit(function() g2:close() end)<br /> print(copcall(test2))<br /> retval = 55<br /> end)<br /> return retval<br />end<br /><br />print ("test1 = ", test1())<br /></pre><br />And here's a more complex example using coroutines and a little argument-passing:<br /><pre><br /><br />-- Define some resource type for testing.<br />-- In practice, this is a resource we acquire and<br />-- release (e.g. a file, database handle, Win32 handle, etc.).<br />local Resource = {}; do<br /> Resource.__index = Resource<br /> function Resource:__tostring() return self.name end<br /> function Resource.open(name)<br /> local self = setmetatable({name=name}, Resource)<br /> print("open", name)<br /> return self<br /> end<br /> function Resource:close() print("close", self.name) end<br /> function Resource:foo() print("hello foo", self.name) end<br />end <br /> <br />local test3 = function(n)<br /> scope(function()<br /> local f = Resource.open('D' .. n)<br /> on_exit(function() f:close() end)<br /> coroutine.yield()<br /> f:foo()<br /> print("inside test3\n")<br /> coroutine.yield()<br /> error("oops happened in test3")<br /> print("this should not print\n")<br /> end)<br />end<br /><br />local test2 = function(n)<br /> scope(function()<br /> on_failure(function(e)<br /> print(coroutine.running(),<br /> "test2 failure ", e) end)<br /> local f = Resource.open('C' .. n)<br /> on_exit(function() f:close() end)<br /> test3(n)<br /> end)<br />end<br /><br />local test1 = function(n)<br /> local retval<br /> scope(function()<br /> local g1 = Resource.open('A' .. n)<br /> on_exit(function() g1:close() end)<br /> coroutine.yield()<br /> local g2 = Resource.open('B' .. n)<br /> on_exit(function() g2:close() end)<br /> coroutine.yield()<br /> print(coroutine.running(), "test2 = ", copcall(test2, n))<br /> coroutine.yield()<br /> retval = n * 100<br /> end)<br /> return retval<br />end<br /><br />local cos = {coroutine.create(test1), coroutine.create(test1)}<br />local retval, x<br />while true do<br /> local is_done = true<br /> for n=1,#cos do<br /> if coroutine.status(cos[n]) ~= "dead" then<br /> retval, x = coroutine.resume(cos[n], n)<br /> if retval and x then<br /> print("test1 =", x)<br /> end<br /> is_done = false<br /> end<br /> end<br /> if is_done then break end<br />end<br /></pre><br />So nesting the scope() call inside your regular function is a little clunky, but it's really not too bad. Lua's lexical scoping makes arguments to functions like test1() work they way you'd expect. <br /><br />I hope the Lua developers decide accept a syntax extension to make this nicer. However, I can definitely live with it the way it is now.<br /><br />I think some kind of scope management is necessary for reliable resource cleanup. The potential for bugs is too great otherwise.<br /><br />Since all the above code is pure Lua (including coxpcall), there's no reason not to use it for your next project!Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4330815578090871242.post-66209660205907702292009-08-21T11:12:00.007-05:002009-08-21T21:32:02.326-05:00Curses Library for LuaI've made a new release of Tiago Dionizio's <a href="http://www.t2-project.org/packages/lua-curses.html">Lua curses library</a>. The original download link is broken, so this is <a href="http://home.xnet.com/~ansible/lua/lcurses-0.2.zip">version 0.2</a>. The initial release was from 2004, and there doesn't seem to have been any updates since then. I've just made some minor updates so that it works with Lua 5.1. It has not be heavily tested yet, but some of the demos work. <br /><br />The fairly extensive documentation by Tiago is included in the archive file, though you should also refer to the standard curses documentation. I haven't tried it yet on Windows, but have on several version of Ubuntu Jaunty (32-bit x86, 64-bit x86, 32-bit ARM).<br /><br />I just found this out, that LuCI also includes a copy of lcurses. I'll need to investigate what changes they might have made.<br /><br />Edit: included original link, and info on LuCI.Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-4330815578090871242.post-21542832582445002052009-07-24T09:16:00.007-05:002009-07-30T19:24:45.512-05:00Lua, Javascript, and the Object Capability ModelI had mentioned <a href="http://www.lua.org/">Lua</a> to <a href="http://www.caplet.com/"> Mark S. Miller</a> in a private email message, and he asked me how similar it was to Javascript. I thought I'd turn the reply into a blog post along with a short discussion of the <a href="http://en.wikipedia.org/wiki/Object-capability_model">Object-Capability Model</a> as it relates to Lua.<br /><br />Let's run off a quick comparison with Javascript first. Similarities in both: imperative, dynamic typing, run-time eval, first class functions, inner functions, closures, variadic functions, exceptions and exception handling.<br /><br />Differences. Well, first off, Lua isn't an object-oriented language. However, you can implement OO programming with tables and meta-tables in Lua, so that is similar to Javascript's associative arrays which are used to implement objects. Notably though, it is possible to implement single-inheritance, multiple inheritance, and <a href="http://www.lua.org/pil/16.4.html">information hiding</a>.<br /><br />Of great concern to the obj-cap community is how well you can <a href="http://en.wikipedia.org/wiki/Object-capability_model#Loopholes_in_Object-Oriented_Programming_Languages">lock down the programming language</a>. Meaning that a particular piece of code only has access to the information and procedures that it really needs to do its job, and nothing further. This is related to the <a href="http://en.wikipedia.org/wiki/Principle_of_least_privilege">Principal of Least Authority</a>.<br /><br />I think this is an area where Lua really shines. It is easy enough to execute a function in a <a href="http://www.lua.org/pil/14.html">restricted environment</a>. So you can just take all the "dangerous" modules out of the function's global environment, and leave nothing, or put in place safe versions of things like 'print()'. Everything you use, from importing libraries to IO to C interfaces are accessed via functions in the global environment.<br /><br />Restricting execution time is also possible. For some game AI, I am exploring the use of the <a href="http://www.lua.org/manual/5.1/manual.html#3.8">Lua Debug Interface</a>. So you can set a limit on the number of bytecodes a Lua routine uses. There is some question as to whether this works properly with continuations. But even if it doesn't right now, it should be possible to fix that. I don't know if there are any explicit hooks to control the memory allocation at the level of functions, though you can restrict the amount of memory used at the thread level.<br /><br />So I haven't done a full analysis, but there does seem to be the potential to use Lua for object-capability security without any changes to the core language. It all depends on how you initialize it.<br /><br />Edit: Some discussion of all this is going on over on the <a href="http://www.eros-os.org/pipermail/cap-talk/2009-July/013043.html">cap-talk mailing list</a>.<br /><br />Edit 2: There seems to be some consensus that the o-cap model will probably work in Lua, with appropriate taming of the standard library. I think it is pretty neat that the core language seems to provide all we need to implement o-cap security without any drastic changes.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-92061612305365996772009-07-11T15:21:00.003-05:002009-07-11T15:48:29.360-05:00n-ary zip() and friends in LuaI've been implementing more list functions in Lua. <a href="http://home.xnet.com/~ansible/lua/list_library.lua">Source code here</a> has more comments embedded.<br /><br />The core of three of them (zip, map, filter) is zip_with_helper():<br /><br /><pre><br />function zip_with_helper(func, result_helper, ...)<br /> local results_l= {}<br /> local args = {...} -- a table of the argument lists<br /> local args_pos = 1 -- position on each of the individual argument lists<br /> local have_args = true<br /><br /> while have_args do<br /> local arg_list = {}<br /> for i = 1, #args do<br /> local a = nil<br /> a = args[i][args_pos]<br /> if a then<br /> arg_list[i] = a<br /> else<br /> have_args = false<br /> break<br /> end<br /> end<br /> if have_args then<br /> result_helper(func, arg_list, results_l)<br /> end<br /> args_pos = args_pos + 1<br /> end<br /><br /> return results_l<br />end<br /><br />function zip_helper(func, arg_list, results_l)<br /> table.insert(results_l, arg_list)<br />end<br /><br />function zip(...)<br /> return zip_with_helper(nil, zip_helper, ...)<br />end<br /></pre><br /><br />On the one hand, it is kind of distressing to see how many lines of code it takes to implement it in Lua compared to Haskell. However, these implementations of map(), filter() and zip() are n-ary functions. So if you add up all the code for Haskell's map(), zipWith() (which is map() using a two-argument function), zipWith3(), zipWith4(), etc. It doesn't look bad at all. In fact, there's a lot of repeated code on the Haskell side. Maybe Template Haskell can take care of that, I don't know.<br /><br />So with the hard part done, here's the code for map() and filter():<br /><br /><pre><br /><br />function map_helper(func, arg_list, results_l)<br /> table.insert(results_l, func(unpack(arg_list)))<br />end<br /><br />function map(func, ...)<br /> return zip_with_helper(func, map_helper, ...)<br />end<br /><br />function filter_helper(func, arg_list, results_l)<br /> local result = func(unpack(arg_list))<br /> if result then<br /> if #arg_list == 1 then<br /> table.insert(results_l, arg_list[1])<br /> else<br /> table.insert(results_l, arg_list)<br /> end<br /> end<br />end<br /><br />function filter(func, ...)<br /> return zip_with_helper(func, filter_helper, ...)<br />end<br /></pre><br /><br />In retrospect, I think I'll get rid of the named helper functions and used anonymous ones instead... at least for map() and zip().<br /><br />I've also figured out a n-ary version of unzip() as well:<br /><br /><pre><br />function unzip(...)<br /> local tables = {...}<br /> if #tables < 1 then<br /> return nil<br /> end<br /> local multi_return = #tables > 1<br /> if not multi_return then<br /> tables = tables[1] -- Given a table of tables, so unzip that.<br /> end<br /> local result_tables = {}<br /> local length = #tables<br /> if length < 1 then<br /> return nil<br /> end<br /> local width = #tables[1]<br /> if width < 1 then<br /> return nil<br /> end<br /> <br /> for i = 1, length do<br /> for j = 1, width do<br /> if i == 1 then<br /> result_tables[j] = {}<br /> end<br /> result_tables[j][i] = tables[i][j]<br /> end<br /> end<br /> <br /> if multi_return then<br /> return unpack(result_tables)<br /> else<br /> return result_tables<br /> end<br />end<br /></pre><br /><br />The fun thing with this is that you can give it three tables as arguments, or one table that holds the other tables. It doesn't matter... up to a couple thousand list entries. So yeah, I don't know how practical that actually is, but it is cool that it is possible at all.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-52328237397935688632009-07-09T21:23:00.005-05:002009-07-12T20:59:23.296-05:00Firefly + Virga?I was thinking recently about the combination of two very different SF universes: Whedon's Firefly / Serenity and <a href="http://karlschroeder.com/">Karl Schroeder's Virga series</a>. No, I am not completely insane. If you are familiar with both, please let me explain... <br /><br />The Firefly 'verse is (as explained in the movie) a single star system with dozens of habitable planets and hundreds of habitable moons. If you have taken a basic astronomy course, then you know how it is likely that there is only one planet (at best) in the "green zone". That is where water is liquid, so the planet is not too hot like Venus, nor too cold like Mars. You can't pack a bunch of planets into the green zone because they would perturb each other's orbits, at best flinging themselves out of the green zone, at worst into the sun or on collision course with something else. This all would occur shortly after the solar system itself formed, so you'd never see dozens of fully formed planets in the green zone in a mature star system.<br /><br />Even though I really enjoyed the series and the movie, Whedon's attention to scientific realism is almost non-existent. I realize that Whedon's goal is not plausibility, but to tell good / fun stories. But if a SF work is going to reach my highest regard, it has to take care of all the details I can think of.<br /><br />Karl Schroeder's Virga is basically a giant ball filled with atmosphere. There's a large central sun called Candesce (which is artificial) and a bunch of smaller ones. This large space is populated by humans living in free-fall (no gravity).<br /><br />Virga is apparently constructed with advanced molecular nanotechnology, which implies superhuman intelligences. These entities decided to make a zoo / game preserve and populate it with regular pre-singularity humans. Perhaps to see what kind of societies would form when living in a free-fall environment. And by interfering with the operation of electronics (a strong EMI field pervades Virga), their tech level is limited it about 1940's level, but without much electronics.<br /><br />At any rate, the Virga setting provides the environment and scale that is really needed for the Firefly 'verse. The towns and cities are days and sometimes weeks of travel between each other. The Firefly central planets have a mid-21st century tech level (at least in terms of computers and medicine) and the border moons have mostly 19th century tech, so the overall tech level is about right.<br /><br />Actually, with Virga you don't need the massive energy requirements for interplanetary travel (or more realistically Star Trek style interstellar travel). Jet powered vehicles of all sizes are used in Virga now.<br /><br />The Firefly computers and Internet (called the Cortex) are not really a problem, most of the shows don't revolve around that. With regards to electronics in general, we might decide to modify Virga's EMI field a bit. Maybe open up the lower frequency bands to allow at least AM radio and other primitive electronics to work. You definitely don't need to allow for high speed electronics. So no video calls, which would impact some scenes a little bit, but I don't think the overall story or pacing would be affected.<br /><br />You'd still have the Alliance and the core worlds (now just cities). The Alliance vs. the Browncoats is actually quite similar to the struggles of the large and small nations described in the Virga novels.<br /><br />What got me thinking about this combo of SF universes was really the Reavers. The idea that these ultra-savages still have enough discipline to run spaceships is absurd. If our own space exploration is a guide, then even with very highly trained and non-batshit-crazy personnel, there are plenty of opportunities for fatal accidents. In a more "realistic" SF universe, the Reavers would have killed off themselves immediately.<br /><br />However, in Virga, it works. The Reavers don't need to worry about atmospheric containment, complex navigation, really high energy systems (like nuclear fission / fusion reactors) and all that stuff. They could plausibly maintain (at least for a short while) 19th century level tech. Or heck, have them ride flying dragons or something.<br /><br />So if we wanted to re-do the episodes, we'd need to re-do a lot of the visuals, mostly the exterior shots and anything that takes place apparently on the surface of a planet. Instead of landing on planets you'd be docking in towns and such. For the outdoor scenes we need to invent some new kinds of wilderness that don't exist in Virga now. And I think we'd need flying zero-gee horses or something. The ships wouldn't have interior gravity, unless we spin them or something. Perhaps it would be better to re-shoot everything, or else make CG models of all the actors and do the whole thing that way.<br /><br />Episode-by-episode revision notes:<br /><br />Serenity (series pilot): Instead of cryo-sleep, maybe just have River in a drug-induced coma.<br /><br />The Train Job: Have it be a convoy instead. Paradiso could be a mining town next to a floating asteroid. They're not terraforming planets in general, but making new towns and "settling" chunks of matter (dirt, water, forests, etc.) floating about.<br /><br />Bushwhacked: Might still need "space suits" for warmth, the outer reaches of Virga get cold too.<br /><br />Shindig: Mostly the action takes place in town, so no major changes. Zero-gee cows or spin Serenity for artificial gravity?<br /><br />Safe: Just need to figure out what the village in the hills would be exactly... a small town wheel, or maybe the people are living out in the wilds.<br /><br />Our Mrs. Reynolds: Wagon pulled by horses may become a small ship pulled by flying animals. Have to change some details about the capture field, but that's not a big problem. Might need Serenity stuck in a jet-stream like current which keeps in on course with the capture field.<br /><br />Jaynestown: Giant clay asteroid next to the mining town.<br /><br />Out of Gas: Takes place in the cold outer area of Virga. Need to modify references to running out of air to be something else. Maybe just make it about not being able to go and hypothermia.<br /><br />Ariel: No advanced computer tech, so no fancy MRI w/ 3-D virtual interface. Have Simon find records of the mind-altering drugs and other procedures performed on River. Scale back the medical tech a bit in general.<br /><br />War Stories: Wilderness will need to be revised as usual. Wash flies Serenity to dock with Niska's town wheel at night, without the use of the jet engines... noise would alert the guards.<br /><br />Trash: The floating villas now don't need anti-gravity to float above a Virga-style ocean.<br /><br />The Message: This one is a problem, organ transplant and genetic engineering implies a higher level of tech than the proposed universe can allow. Need to have Tracy smuggle something else.<br /><br />Heart of Gold: The bordello is a small town wheel itself. Flying horses again.<br /><br />Objects in Space: Vacuum not a danger of course, though getting shoved off into open air without transport could easily be fatal. Though it worked out for Venera Fanning. <br /><br />Serenity (movie): Much more use of video that would need to be fixed. How to re-do the opening sequence? How does Mr. Universe figure out what triggered River? River managed to find a scrap from an old map that mentions Miranda. The crew try to look up Miranda in the latest set of paper encyclopedias. Mr. Universe may just have a big AM transmitter, though are people going to be convinced by an audio broadcast the way they might be for a video broadcast? Maybe have Serenity bring back more hard evidence from Miranda.<br /><br />So yeah, you'd have to re-shoot the whole thing, but the stories and characters would mostly be unchanged in the new setting. And make a whole lot more sense to boot.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-52516691140366862962009-07-08T17:45:00.004-05:002009-07-08T17:55:17.808-05:00map in LuaBeen looking at the <a href="http://lua-users.org/wiki/FunctionalLibrary">Functional Library for Lua</a> this week.<br /><br />The map() implementation only works for single-argument functions. Here's a version for multiple arguments:<br /><br /><pre><br />function map(func, ...)<br /> local newtbl = {}<br /> local tables = {...}<br /> local listpos = 1<br /> local have_args = true<br /><br /> while have_args do<br /> local arg_list = {}<br /> for i = 1, #tables do<br /> local a = nil<br /> a = tables[i][listpos]<br /> if a then<br /> arg_list[i] = a<br /> else<br /> have_args = false<br /> break<br /> end<br /> end<br /> if have_args then<br /> newtbl[listpos] = func(unpack(arg_list))<br /> end<br /><br /> listpos = listpos + 1<br /> end<br /> return newtbl<br />end<br /></pre><br /><br />It is a bit more complicated, but not too bad. If anyone has suggestions on how to make it shorter and more concise, I'd appreciate it. I'm glad to be able to implement it fairly easily, in some languages it can be quite a bother.<br /><br />I need to work out new version for the other functions like filter(), and post an updated version on the Lua users' wiki. foldl() might be a little interesting...Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-10760285601455737652009-07-06T16:38:00.004-05:002009-07-08T18:01:52.315-05:00New Battery for G1Just got a new 2600mAh battery for the G1. Now the phone is fat and heavy. :-)<br /><br />It should run over twice as long as the original 1150mAh battery, and not just because of the increased capacity. It has to do with the current draw in relation to the overall battery capacity. Even if we were drawing 300mA from each battery (for example) the larger battery is going to last a little longer than just the capacity difference would seem to indicate. Basically, you're not straining the battery as much.<br /><br />Hmmm... the battery only seems to be charging up to 3.91V, as measured by the phone. So it thinks it is only 91% charged. Edit: Nevermind, it came up to 4.178V and now says it is fully charged. Cool.<br /><br />If this seems to run well in the next couple weeks, I'll probably post a review on the site I purchased it from, as well as leave a comment here.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-62537585187958051002009-06-30T14:03:00.005-05:002009-06-30T17:19:51.480-05:00Lua on Java on DalvikVM on AndroidYes, you read that right.<br /><br />I was poking around with Lua implementations and ran across <a href="http://sourceforge.net/projects/luaj/">LuaJ</a>, which is an implementation of Lua written in Java.<br /><br />Well, after following <a href="http://davanum.wordpress.com/2007/12/04/command-line-java-on-dalvikvm/">Davanum Srinivas's instructions</a> on how to convert a standard JAR into one that can be installed in Android, I was able to get it to run Lua scripts inside the Android emulator.<br /><br />It shouldn't be too hard to write a regular Android application that would allow the user to type in Lua chunks and run them. I haven't seen much in terms of scripting capabilities for the Android platform... Lua would be a good fit for that.<br /><br />The only caveat is that the LuaJ implementation is generating and running Lua bytecodes in a Lua VM. Which is running on top of the Dalvik VM. So it is going to be crazy slow. It's kind of amazing that it runs at all, Google must have implemented a lot of the core Java stuff, including reflection.<br /><br />Now here's an interesting tidbit... The Dalvik VM is register based, as opposed to the stack based JVM. And the Lua VM is register based. So what are the possibilities for "native" (by this I mean Dalvik) code generation by the LuaC compiler?<br /><br />Does the Dalvik VM even support having some memory buffer contain some bytecode that it will then execute? Would we have to go through the filesystem instead (meaning generating a .dex archive or such)? Inquiring minds want to know.<br /><br />There seems to be a lot of potential in general for a decent scripting language on the Android platform.Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4330815578090871242.post-24915176690780064472009-06-23T09:42:00.003-05:002009-06-23T09:45:03.313-05:00ConnectBot issue fixedI mentioned having a problem with <a href="http://code.google.com/p/connectbot/">ConnectBot</a> previously. Downloaded the source, found the problem, submitted a patch, it was accepted, downloaded the development snapshot... and it works! Life is good.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-49339197141597079192009-06-22T08:08:00.006-05:002009-06-22T08:39:23.373-05:002009H1 UpdateHere's a semi-yearly update of what's going on in my tech life:<br /><br />Haven't been hacking any Haskell lately. It's a brilliant language, but one I never got comfortable enough with. We're trying to use Python for application and test script development at work, which is OK so far.<br /><br />I've been investigating <a href="http://www.lua.org/">Lua</a> a lot recently. We've experimented with it for a couple embedded projects so far. It is just about the only scripting language that will fit into small embedded platforms... everything else is just too hard to port. You can easily configure Lua to just include the parts you want. So for that reason alone, I think I'll be pushing for its use on future projects.<br /><br />The more I've learned about the design of Lua, the more I like it. The language itself has a lot of neat features. It is very compact, very Scheme-like. But better than Scheme in that its fundamental data structure is the <a href="http://www.lua.org/pil/2.5.html">table</a>, instead of a linked list. It has pretty good support for functional programming, tail call optimization, and coroutines too.<br /><br />The implementation is small enough to learn and hack easily. As opposed to GHC... Don't get me wrong, it is a phenomenal work, but if you've ever looked under the hood of that compiler... yikes.<br /><br /><hr /><br /><br />In other news I bought an Android Developer G1 phone. I've downloaded a <a href="http://jf.andblogs.net/"> popular community firmware</a>, and also loaded <a href="http://xdatap1.wordpress.com/2009/05/03/jaunty-under-android/">Ubuntu</a> on it. Still got some configuration issues to work out, and ConnectBot is giving me some problems while running VIM. Just have a 2.5G data service plan, which is a little pokey when out and about. But it's looking good so far.<br /><br />I've wanted a decent, portable Linux machine to do hacking on for a long time... dating back to the days when I was messing around with trying to get a cut-down version of Linux running on a HP 100 LX palmtop. And now I'm there... with the Ubuntu userland installed it has Python and Lua, VIM, screen, ssh, rsync and GCC. A decent browser, always-on (if slow) Internet, WiFi, Bluetooth, expandable storage... and it makes phone calls too! How cool is that?Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-36939657428491323652007-11-08T14:20:00.000-06:002007-11-19T15:18:32.577-06:00HSS: A Search for EqualityJust a few minor updates to the Haskell Spider Solitare code.<br /><br />In preparation for implementing a <a href="http://haskell.org/haskellwiki/Zipper_monad/TravelBTree"> Zipper and Travel B Tree</a> we need a way of detecting repeated game positions. The Travel B Tree we use will be almost the same, except that each interior node will also have a data value as well, just the leaves.<br /><br />I talk about the move tree for a given game being finite... but that is<br />not strictly correct. If you have a Jack, and there are two exposed Queens on the board, you can move the Jack back and forth between the two forever. So we're just going to look at the history and see if we're duplicating a position <br /><br />There are also a few other little cleanups in the code.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-58119985041091095172007-08-22T14:03:00.000-05:002007-08-23T15:39:43.438-05:00HSS: Generating moves<p>I've added some functions to generate all possible moves at a given board position for Haskell Spider Solitare (link to source code at right as usual). Here's the relavant bits:<br /></p><pre>--<br />-- generate list of all cards that could possibly be moved<br />--<br />movable [] _ _ = []<br />movable (x:xs) col row = if (c_cluster x) == 0<br /> then cur_nsm : movable xs col (row + 1)<br /> else []<br /> where<br /> cur_nsm = Normal_Spider_Move (Tableau_Location col row)<br /> (-1) -- not valid yet.<br /> Nothing<br /> (row + 1)<br /><br />all_movable sg = am_helper (tableau sg) 0<br /> where<br /> am_helper [] _ = []<br /> am_helper (x:xs) col = (movable x col 0) ++ am_helper xs (col + 1)<br /><br />--<br />-- see where they can move to<br />--<br />where_plays sg nsm = wp_helper nsm (tableau sg) 0<br /> where<br /> wp_helper _ [] _ = []<br /> wp_helper nsm@(Normal_Spider_Move from to _ _)<br /> (cur_col:rest_cols)<br /> colnum =<br /> (if ((t_col from) == colnum) ||<br /> (length cur_col) > 0 &&<br /> not (plays_on_match (from_card sg nsm) (head cur_col))<br /> then []<br /> else [nsm{sm_to = colnum}] ) ++ rest<br /> where<br /> rest = wp_helper nsm rest_cols (colnum + 1)<br /><br />where_plays_all nsm_list sg =<br /> foldr (++) [] (map (where_plays sg) nsm_list)<br /></pre>Comments: I need to settle down with the indentation, and pick either 4 or 8 and stick with it. I am at least trying to stick with 80 columns, which makes blog posting easier too.<br /><p>I'm not complely happy with the tableau data structure, which is just a list of lists of cards. See how I'm threading through the column number in movable and where_plays? I suppose I could replace that with something like: '<span style="font-family: courier new;">9 - (length xs)</span>', but that bothers me a little bit too. The whole integer indexes into lists bothered me a bit with the Common Lisp version too. Not that I'd know how I could change it.</p><p>As always, any comments on style, or suggestions to make the code shorter and more clear are welcome.<br /></p><p>Next task is to decide how to represent the entire tree of moves. I've just downloaded <a href="http://www.cs.cmu.edu/%7Erwh/theses/okasaki.pdf">Purely Functional Data Structures</a>[PDF] by Chris Okasaki, but I haven't dug into that yet. We will want to be able to move up and down through the tree easily.</p>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4330815578090871242.post-89607185130769131302007-08-10T05:59:00.000-05:002007-08-10T07:05:36.454-05:00HSS: 1.1 releaseThe 1.1 release of Haskell Spider Solitaire has been posted to the usual location (check the links to the right).<br /><br />The major change is switching the representation of the tableau. All the manipulation of the tableau occurs at the bottom of the board as the human player sees it. Previously, the data representation matched the screen presentation, and that meant manipulating the tails of each column (which are just lists). Following a suggestion by chessguy (thanks, if you're reading this) that has been reversed. So the bottom of each column as seen by the users is at the head of each column list.<br /><br />So the display of the board is slightly more complicated, but the internal mechanics of moving cards is simpler, and some helper functions have been eliminated.<br /><br />So the next task is to start exploring the move tree for a particular game. As part of that, I think we'll want to somehow create a hashtable for each board position encountered so far during a game. to prevent repeated positions. I suppose I could assign a number to each unique card, flatten the tableau and stock, and calcuate a hash based on that.<br /><br />While there are something on the order of 108! divided by 2^56 possible starting positions, and approximately that many possible board positions, you can only see a small fraction of those starting from a particular board position. I also don't know just how big a move tree is for a typical game either. A winning game can easily run 500 moves deep. And it is common to have 3 or 4 possible moves from a given position. But there are a lot of very quick dead-ends, and the deepest games are the winning ones... of which there may only be a low number of total solutions, and a low number of paths to each solution.<br /><br />I'm sure a mathematician could give accurate answers to at least some of these questions. Since I am not one, I'll turn to empiricism instead. This is where we generate thousands of games, and collect statistics.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-4330815578090871242.post-41844118679282863542007-06-06T14:05:00.001-05:002009-06-23T09:49:02.322-05:00Moving to MercurialThere's been a lot of discussion about version control lately, and here's my little contribution to it.<br /><br />I've selected <a href="http://www.selenic.com/mercurial/wiki/">Mercurial</a> for the DVCS at work, and that's what I'll be using for my personal projects too. Mostly because I'm not going to learn darcs as well.<br /><br />The other finalist was git. I was recently watching that Google Talk video featuring Linus Torvalds, and he made a lot of good points (even if you don't like him calling people and entire projects stupid).<br /><br />We were going to move to Subversion, just because it is the 'better CVS', but we haven't actually started implementing it yet. We aren't really pushing the limits of even CVS yet at work, but we'll be working on some much larger SW projects soon, so now's the time to switch.<br /><br />For the record, here's what swayed me for Mercurial: cross-platform support (runs on Windows), Trac integration, and written in Python (which will be used for a bunch of our other development tools). By most accounts, it is as fast as git, and doesn't have some of odd corner-case behavior of darcs (which will hopefully be fixed soon).<br /><br />I have run into one problem with Mercurial already. If you store a repository on a FAT filesystem (my flash drive), it apparently isn't compatible between Windows and Linux. :-(Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-4330815578090871242.post-20634026041777417712007-05-28T22:30:00.000-05:002007-05-28T22:50:54.305-05:00HSS: 1.0 ReleaseThe source for the latest version of the Haskell Spider Solitaire game is available for download to the right, as usual.<br /><br />There was quite a bit of re-factoring this time, trying to find a good home for all the different functions.<br /><br />There is also complete move validation now, and that all works correctly... I think. Fixed some bugs with foundation moves. Other improvements include being able to actually win the interactive game. And no, you don't get fireworks, though I suppose I could call that old BSD /usr/games program that does something similar.<br /><br />So anyway, since it basically works, let's call it release 1.0.<br /><br />Next major task is to be able to enumerate all the possible moves from an existing board position. Then we can start experimenting with a tree search to exhaustively try to solve a game. After that, scoring a particular board position... which is going to be a bit difficult.<br /><br />Misc TODO: Get started on QuickCheck.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-4330815578090871242.post-16269460957742692252007-04-26T13:34:00.000-05:002007-05-28T22:37:03.173-05:00HSS: quick update, and interesting papersHaven't done too much with Spider Solitare in Haskell lately. Added a help command and some other little nicities. Still need to finish the input and move validation.<br /><br />Been reading the <a href="http://www.cs.uu.nl/~johanj/publications/ComparingGP.pdf">Comparing Approaches to Generic Programming in Haskell</a> which has been interesting.<br /><br />Also, <a href="http://programming.reddit.com/info/1i5jv/comments/c1i88w">in a Reddit topic about Chicken Scheme</a> I discuss why I've settled on using Python for the majority of our development projects at my company. Even though I think Haskell is the bee's knees as far as expressiveness and concicseness goes.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-65188218787136887942007-04-15T22:21:00.000-05:002007-05-28T22:37:46.001-05:00HSS: Now barely useable!We (by we I mean me) are getting close to a 1.0 release for Spider Haskell. Download the source code at the right, as usual.<br /><br />Mostly just been working on the UI for playing a game on the console. There's barely any input validation. And there's no checking to see if a move is valid at all. So if you want to play, it is on the honor system.<br /><br />But, all the basics are there, if not completely tested. Undo was easy to implement, because we keep a list of all the previous game states. This was actually one of the stumbling blocks of the original CL version. Because that version was doing in-place modifications, it was a lot of work to implement the undo. We would look at the move history, and manually reverse it. So we had to do things like also keep track of any cards that were revealed by the move.<br /><br />The two codebases are now roughly the same size. However, there is some duplicated code in the CL version (was starting to re-organize the project before working on it), so that doesn't mean anything.<br /><br />To do: Do full command validation (don't want a String to Int conversion to blow up), and move validation. And maybe a little in-game help.<br /><br />And after that, we can start trying to solve Spider Solitare, once and for all. :-)Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-84290755969697246892007-04-07T21:32:00.000-05:002007-05-28T22:52:21.642-05:00HSS: Move ValidityMore code for the Spider Solitaire game in Haskell, download link at the right as usual.<br /><br />I haven't made a whole lot of progress, but I'm slowly churning through the functionality that was implemented in the Common Lisp version.<br /><br />Included with the current version is the calculation of 'card clusters' as I call them. Here's the important bits of that:<br /><br /><pre><br />-- card clusters<br />--<br />-- A cluster is a set of cards which may be moved at once. Like an 3, 2, 1<br />-- of clubs, for example.<br />--<br />-- In a column of the tableau, clusters are marked from 0 at the bottom<br />-- on up. So it is only valid to move cluster 0. But we keep track of the<br />-- other clusters in the column for strategic purposes.<br /><br />compute_cluster :: [Card] -> [Int]<br />compute_cluster [] = []<br />compute_cluster xs = reverse $ rv_cards (reverse xs) 0<br /> where<br /> rv_cards [] _ = []<br /> rv_cards [x] y = [y]<br /> rv_cards (x1:x2:xs) y = y : (rv_cards (x2:xs) new_y)<br /> where<br /> new_y = if (plays_on_match x1 x2)<br /> then y<br /> else y + 1<br /><br />-- True if c1 plays on c2, False otherwise<br />plays_on_match Card -> Card -> Bool<br />plays_on_match c1 c2 =<br /> case (plays_on c1) of<br /> Just x -> x == (c_value c2) && (c_suit c1) == (c_suit c2)<br /> Nothing -> False<br /></pre><br /><br />I've a bit of a dilemma as far as where to store data. In the CL version, what cluster a particular card was in card data structure itself. I'm debating if this is a good idea or not.<br /><br />So say we've just made a move, so we're creating a new instance of the Spider_Game data structure, which will have the modified column(s). Do we compute the new columns, and then create a new version of them with the clusters properly filled in? Seems a bit inefficient.<br /><br />And why exactly am I worried about efficiency at this point? Isn't premature optimization one of the great sins of a programmer?<br /><br />Side note, I realize there are issues with the layout of the site, and it doesn't work so hot when your pre-formatted text is 80 columns wide, and the blog itself only wants me to post 60-column wide text. I'll need to fix that.<br /><br />Edit: Trying out this really simple template, which allows wider columns for the blog post itself.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4330815578090871242.post-20175369283211884282007-03-28T21:00:00.000-05:002007-05-28T22:52:39.293-05:00HSS: Pretty Printing and some MovesMore code written supporting the pretty-printing of the playing board. Download link on the sidebar.<br /><br />Also started implementing some of the moves available. Here's the structure for that:<br /><br /><pre><br />data Tableau_Location = Tableau_Location { t_col :: Int, t_row :: Int }<br /> deriving Show<br /><br />data Spider_Move =<br /> Regular_Spider_Move {<br /> sm_from :: Tableau_Location,<br /> sm_to :: Tableau_Location,<br /> sm_revealed :: Maybe Tableau_Location, -- Card revealed, by<br /> -- the move, if any.<br /> sm_count :: Int -- number of cards moved<br /> }<br /> |<br /> To_Foundation_Move {<br /> sm_from :: Tableau_Location,<br /> sm_revealed :: Maybe Tableau_Location -- Card revealed, by<br /> -- the move, if any.<br /> }<br /> |<br /> Deal_From_Talon<br /> deriving Show<br /></pre><br /><br />I'd like to think of a better way to represent the move locations other than integers. Not that it can't be made to work, but using integers seems a little clunky with lists. I'm thinking of changing the tableau to be an array of lists instead.<br /><br />I haven't actually written the code yet to do the regular game moves, but I can tell it is also going to be a bit clunky. <br /><br />I should come clean here a little bit... There was a previous version of all this that I wrote in Common Lisp. I only got so far as allowing a human to play the game, there was no solving or AI implemented. <br /><br />So in part, I've been just re-writing that CL version in Haskell.<br /><br />However, part of the problem I ran into with that version is that I would have had to do major re-work in order to start implementing the AI. The CL version was written in a very imperative style, and I didn't keep around the old board after making a move. That made writing the undo logic a bit interesting, but I got that working OK.<br /><br />So anyway, we'll need to keep a more functional style anyway. We're going to have a massive tree of possible moves to keep track of, because there are usually a few possible moves for a given position. The trick, of course, is pruning the branches that will be unproductive.<br /><br />I think, if I'm doing things right, however, that we'll not be duplicating the card structures except for the ones we're modifying (turning face up, for example). And in a normal spider move, 8 of the 10 columns won't change, so that'll save some memory too.Unknownnoreply@blogger.com0