tag:blogger.com,1999:blog-215002372024-03-12T22:48:39.153-04:00Praise, Curse, and RecurseOn programming and programming languages: because there has got to be a better way.Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.comBlogger89125tag:blogger.com,1999:blog-21500237.post-11081817293959965962013-08-20T21:40:00.002-04:002013-09-13T10:53:59.624-04:00Arduino, Day 2: the Most Minimal Scripting Language, or, Reifying Frozen Functions for Fun<i>Planet Haskell readers might want to skip this one.</i>
<p>Recently I've been thinking about the possibilities offered by embedded interpreters. This is becoming a common design pattern in commercial software -- games written in C++ embedding Lua, for example, or Python for graphical user interfaces, or occasionally Scheme, or even the JVM. However, adapting an existing full-blown scripting language won't necessarily fly on a small system. What if you have a DSP, with nothing resembling a *nix-like operating system -- no standard C library, or almost none, no POSIX-like APIs, etc.</p>
<p>Well, there are smaller languages. I've done a little research recently and come across some very small, cut-down implementations of Scheme or other Lisp dialects, or even a tiny BASIC, and languages like Forth can be very small.</p>
<p>But what if we have a <i>really</i> tiny chip? What if the SRAM budget we had to implement our embedded language was, say, not 2 MiB, or even 2 KiB, but 200 bytes?</p>
<p>The Arduino Uno R3 uses an <a href="http://en.wikipedia.org/wiki/ATmega328">ATmega328</a> microprocessor. It's considered an 8-bit chip. Calling chips 8-bit, 16-bit, 32-bit, 64-bit, etc. can be a little confusing these days, because a lot of chips can operate on several different data sizes, but this chip has 8-bit registers, so we'll consider it to be primarily an 8-bit part. It has 32 KiB of onboard flash memory to hold your program (it is persistent across power cycles). 32 KiB can hold a moderately complex compiled program. But as for RAM -- the working memory for computation in progress and run-time state -- it
has only 2 KiB, a mere 2048 bytes. That's less RAM than the first computer I owned, which was a Radio Shack TRS-80 Model 1, with 4 KiB, although I did work with some smaller computers -- for example, a KIM-1. And presumably we don't want to use all our SRAM to implement our small scripting language itself; the scripts need to have some functions to call.</p>
<p>A microcontroller like this is designed to run simple programs. It's designed to be "bomb-proof" -- hard to fry with stray excess voltage. It has a low pin count -- miniscule, compared to the processors in my desktop and laptop machines -- and it has a number of built-in peripherals designed for digital I/O. It's a pretty cool chip -- these Arduinos have taken off among electronics hobbyists and are part of the whole "maker" movement because they exist in a sort of power per dollar sweet spot. If you fry the chip itself, you can replace it for a couple of dollars; if you fry the whole board, you're only out a few more.</p>
<p>What they aren't, though, is very well-suited for the modern programming model that assumes a very capable operating system, dynamic linking, dynamic allocation using <b>malloc</b> or <b>new</b>, and container objects created using class libraries like the STL (don't get me wrong, the STL is impressively efficient, but it just isn't designed to work around a very tiny memory model). So the Arduino's GCC toolchain doesn't even attempt to provide, say, <b><vector></b>.</p>
<p>So what would an embedded scripting language for the Uno R3 look like? Well, for one thing, the Arduino doesn't come with a file system to speak of. You can buy a "shield" of some time that provides a controller and a slot for a memory card, but this isn't included with the basic bard. So you can't count on a user's ability to place a script in a text file and update just that script in order to change the program's behavior, although I might do some experiments along those lines. Without something like that, you have to use the toolchain -- compiling your program and downloading it with <b>avrdude</b>. You can't count on files, but you have strings -- C-style strings, in the form of arrays of bytes. So you could implement a small BASIC or Scheme interpreter that executed a program contained in a C string. I will do some experiments along those lines too, if I can, especially if I can force the strings to live in the 32 KiB flash, which I think is possible, rather than the 2 KiB SRAM.</p>
<p>But what if you want something even simpler? What if pretty much any sort of interpreter looked like it was going to be too heavyweight for your purposes, using too much SRAM -- too much space for tables, and too much stack? Is there something even simpler you can do?</p>
<p>There is. You can write a "script" that consists of a series of objects, using some tricks I'll demonstrate. This is very definitely a work in progress; it has some rather extreme design compromises. In particular, it isn't at all friendly to the "script" author. If there is a typo, the compiler can't provide a very novice-friendly error message. It seems a little sadistic to inflict this sort of hair-shirt discipline on hobbyists, but let's consider it a thought experiment, exploring a a couple of implementation options.</p>
<p>I'm going to build my "scripting language" up in reverse; instead of showing you the syntax of the "scripting language" first, I'll show you the constructs I'm using to implement it, we'll and arrive at the syntax last. But first I need to explain some of the less common things I'm doing with the implementation.</p>
<p>Let's say I want to easily differentiate a set of overloaded functions, each of which is specialized on a single parameter type. (I won't explain why quite yet, but it will make sense later). What's the best way to do that? How about with a set of <b>typedef</b>'ed types, or enum types to distinguish them?</p>
<p>C++ and C are <i>weakly typed</i>, at least in places. Although the C++ class system can enforce strong typing, when working with POD (plain old data) types and particularly the <b>typedef</b> and <b>enum</b> keywords, typing isn't strongly enforced. What do I mean by that? Well, <b>typedef</b> and <b>enum</b> allow you to write code that looks superficially like it is strongly typed:</p>
<pre>typedef int special_int;
void handle( int a );
void handle( special_int a );</pre>
<p>But on my compiler, if I provide the functions to match these prototypes, and call them:</p>
<pre>int handle_param_1 = 0;
special_int handle_param_2 = 0;
handle( handle_param_1 );
handle( handle_param_2 );</pre>
<p>The compiler complains that I'm redefining <b>handle</b>. The compiler won't (and can't) really make use of it to provide type safety, because it's not really a distinct type, but a <i>type alias</i> -- that is, really just a nickname, more for documentation purposes than anything else; the compiler doesn't really see the alias as a distinct type at all.</p>
<p>In the case of enums, using enum can make your code more self-documenting, and it appears that I can reliably overload functions using specific enum types, which the compiler keeps distinct:</p>
<pre>typedef enum { red, green, blue } color;
typedef enum { salty, sweet, sour } flavor;
void handle( color a );
void handle( flavor a );</pre>
<p>But if there is no overloaded function with a parameter that exactly matches the enum type, C++ will happily <i>promote</i> the enum type to an <b>int</b>, or apply a <i>standard conversion</i> to turn it into a <b>float</b> -- so type-safety is potentially compromised again here. If you forget to provide an overloaded <b>handle</b> method that accepts your enum type, but there exists one that takes a single float parameter, the compiler will call that one, without a whisper of warning. Types don't get much weaker than that! (All right, yes they do, but let's not get into a sideways rant about PHP or Perl).</p>
<p>The very latest versions of C++ do provide a new "enum class" feature that gives one more control over enumerated types and allows the more powerful class type system to kick in and keep things straight, but it isn't widely used yet, and I'm not sure the compiler I have available for Arduino supports it. So, at least for today, we'll leave it out.</p>
<p>There <i>is</i> a tweak that makes this quite easy, though. In C++, a <b>struct</b> is actually a class whose members are all public by default. And it's possible to create an empty struct, with no data members. This gives me something I'll call it a <i>type tag</i> (I could call it a <b>typeType</b> in honor of the old AppleEvent manager's descriptor type, but let's not), and I'll call an <i>instance</i> of it a <i>type token</i>. They will let me reliably overload functions, since it uses C++ class types, designed for greater type safety and strictness than C's "plain old data" types.</p>
<p>Let's briefly review structs, in case you need a review: in C, <b>struct</b>s are in their own namespace, but they can be <b>typedef</b>'ed into the common namespace:</p>
<pre>struct s_tag { int m1, float m2 };</pre>
<p>You can instantiate a struct in C like this:</p>
<pre>struct s_tag s1;</pre>
<p>But you can't say:</p>
<pre>s_tag s1;</pre>
<p>Unless you've used the typedef trick:</p>
<pre>typedef struct s_tag s_type;
s_type s2;</pre>
<p>These are used together so frequently that the C syntax supports wrapping the type definition and <b>typedef</b> up together:</p>
<pre>typedef struct s_tag { int m1; float m2 } s_type;</pre>
<p>So what is the point of that <b>s_tag</b>? Well, it is mostly vestigial, but it has one important use; it is the only way you can declare a struct that is self-referential. This is imperative when declaring a tree or list of struct types, if you are going to take advantage of type-checking, instead of mashing everything through void pointers and unsafe casting to get it back to the type you need. So,</p>
<pre>typdef struct s_tag { int m1; float m2; s_tag *next_p } s_type;</pre>
<p>and not:</p>
<pre>typedef struct s_tag { int m1; float m2; s_type *next_p } s_type;</pre>
<p>because the latter would require a forward reference to an incomplete type, and there's no way to specify that. Of course, it doesn't seem that unreasonable these days to ask a compiler to keep track of incomplete things as it goes and make sense of them in a later pass, but back in the day machines were smaller and slower, and so we have that vestigial struct tag.</p>
<p>And in C++, designed to maintain as much compatibility with C as possible, there are (of course) some subtle <a href="http://stackoverflow.com/questions/612328/difference-between-struct-and-typedef-struct-in-c/612476#612476">complications</a> that can come into play, but that's basically how structs work.</p>
<p>In case you're curious, yes, there's a similar "enum tag" for enums, and you can refer to enum types in the <b>enum</b> namespace. I haven't see this sort of thing much in real-world code. There's yet another namespace for <i>unions</i>, and unions are structs as well in C++ -- we'll take advantage of that later. But moving on, let's define some type tags:</p>
<pre>typedef struct {} step_1_tt;
typedef struct {} step_2_tt;
typedef struct {} step_3_tt;</pre>
<p>And here are some "type tag" instances:</p>
<pre>static steps::step_1_tt step_1_tt_i;
static steps::step_2_tt step_2_tt_i;
static steps::step_3_tt step_3_tt_i;</pre>
<p>The empty struct isn't standard C (although I think GCC allows it as an extension), but it is allowed in C++. In standard C there is a similar trick where you can declare a pointers to incomplete (that is, forward-declared) struct types (does that let you use self-reference in structs without using the vestigial tag? I'll have to look into that. There's a lot to know for such a seemingly simple language feature!)</p>
<p>Now, we need to be able to distinguish our tiny scripting language "tokens," and for that we use an enumeration. (We could do this with subtypes, as well, and maybe I'll consider that for later, but for now we'll do it this way). We'll define several types that correspond to functions:</p>
<pre>typedef enum
{
step_type_1,
step_type_2,
step_type_3,
} step_e;</pre>
<p>Next up, we want to define the functions. This is pretty basic. We could do it with function pointers, of specific function pointer types, and I might explore that later, but for now we'll refer to a hard-coded set of actual functions. Here they are, simple placeholders that print their arguments, for testing:</p>
<pre>void step_func_a( signed long );
void step_func_b( unsigned long );
void step_func_c( signed short );
void step_func_a( signed long p1 )
{
std::cout << "step func a with param" << p1 << "\n";
}
void step_func_b( unsigned long p1 )
{
std::cout << "step func b with param" << p1 << "\n";
}
void step_func_c( signed short p1 )
{
std::cout << "step func c with param" << p1 << "\n";
}</pre>
<p>So those are the functions we can call from our "scripts." But what about the parameters? We'll use unions. This is unsafe, in the sense that the type system will not keep us safe, and we'll have to use some extra bookkeeping have to make sure we decode parameters the same way they were encoded. Because a <b>union</b> in C++ is also a class, we can provide constructors for our union type, and even overload them, to handle the different types that might be passed in:</p>
<pre>union step_param_u
{
step_param_slong slong_param;
step_param_ulong ulong_param;
step_param_sshort sshort_param;
step_param_ushort ushort_param;
step_param_schar schar_param;
step_param_uchar uchar_param;
// We could add more here, for any parameter types we need
// to store and reconstitute later
step_param_u() : slong_param( 0 ) {};
step_param_u( signed long p1 ) : slong_param ( p1 ) {};
step_param_u( unsigned long p1 ) : ulong_param ( p1 ) {};
step_param_u( signed short p1 ) : sshort_param( p1 ) {};
step_param_u( signed char p1 ) : schar_param( p1 ) {};
};</pre>
<p>One of those union objects will represent one parameter. Let's wrap that all up with a struct that will embody a "frozen function call" with up to 3 parameters. We could extend that if we need more.</p>
<p>There's a sort of type-system hole in that we don't have a safe, distinguishable way to represent a null parameter -- that is, one that wasn't provided -- and so there's not quite a sensible default constructor for <b>step_param_u</b>. We could use subclasses of our "frozen function call" to represent function calls with no parameters, one parameter, two parameters, three parameters, etc. so that we don't have to represent the idea of an unused parameter at all, but this results in an explosion of types (and I'm not even really taking return values into account at all, at this point; our scripting language uses a completely imperative paradigm). Maybe the number of unique parameter and return value combinations is not that large in practice, but for now let's just get a simple thing working:</p>
<pre>struct step_s
{
step_e step_type;
step_param_u param_1;
step_param_u param_2;
step_param_u param_3;
step_s( step_1_tt, signed long p1 ) :
step_type( step_type_1 ),
param_1( p1 )
{};
step_s( step_2_tt, signed long p1 ) :
step_type( step_type_2 ),
param_1( p1 )
{};
step_s( step_3_tt, signed short p1 ) :
step_type( step_type_3 ),
param_1( p1 )
{};
};</pre>
<p>And now for a trick to create our so-called. We turn things that look like function calls into actual constructor calls by adding a parameter. For this quick-and-dirty prototype, I'll use some macros:</p>
<pre>#define MAKE_SEQUENCE(p1) step_s const p1[]
#define step_call_type_1(p1) step_s(step_1_tt_i,p1)
#define step_call_type_2(p1) step_s(step_2_tt_i,p1)
#define step_call_type_3(p1) step_s(step_3_tt_i,p1)</pre>
<p>Is it raw and wriggling, precious? Make sure you understand what's going on here: these macros turn function-call-like syntax into constructor calls by passing our type tokens to select a matching overloaded constructor. Of course, the compiler is looking at the preprocessed code, which can make error messages harder to understand. I sometimes have to ask the compiler to generate preprocessor output to diagnose a problem, but a beginning Arduino programmer using the IDE won't even have a way to generate the preprocessor output.</p>
<p>And so here is an example of our tiny "scriping language" -- a sequence of steps to take, in reality function calls to make:</p>
<pre>sequence(sequence_1) =
{
step_call_type_1(-50101),
step_call_type_2(0xDEADBEEF),
step_call_type_3(-32767)
};</pre>
<p>And that's our syntax.</p>
<p>Wait, really? Yes. That's a little script. That's why I call it the "most minimal" scripting language.</p>
<p>That actually turns into an array definition, with an implict (not explicitly declared) size, and an initialization list. Note that the ability to include constructor call expressions in an array initialization list is a newer feature of C++. Older compilers won't be able to handle the syntax at all. To support an older compiler we'd have to do some kind of post-definition assignment, which might require something like calling a variadic function with a list of macro invocations, and that could get really ugly really fast. Er, that is, even uglier than what we're already doing.</p>
<p>So how do we execute that script? Well, we need another bit of macro magic to find the length of a sequence:</p>
<pre>// Length of a sequence; see Imperfect C++, the book by Matt Wilson, or his blog post:
// http://blog.imperfectcplusplus.com/2010/06/imperfect-cinventions-dimensionof.html
#define SEQUENCE_LENGTH(seq) (sizeof(seq)/sizeof(0[(seq)]))</pre>
<p>And now we have all we need to write a function that runs a sequence. How about this, as the simplest thing that can work:</p>
<pre>static void run_sequence( step_s const p1[], int const seq_len )
{
for ( int seq_idx = 0; seq_idx < seq_len; seq_idx++ )
{
p1[seq_idx].invoke();
}
}</pre>
<p>Where <b>invoke</b> is a method of <b>step_s</b>:</p>
<pre>void invoke() const
{
switch( step_type )
{
case step_type_1:
step_func_a( param_1.slong_param);
break;
case step_type_2:
step_func_a( param_1.ulong_param);
break;
case step_type_3:
step_func_a( param_1.sshort_param);
break;
}
}</pre>
<p>Well, actually, we need this, too, so a particular instance can be sized at compile time:</p>
<pre>#define RUN_SEQUENCE(p1) run_sequence(p1,SEQUENCE_LENGTH(p1))</pre>
<p>And then I can just execute <b>RUN_SEQUENCE(sequence_1)</b>.</p>
<p>Note that invoke assumes that the entire set of functions we might want to invoke from our script is known. This could be extended in some fashion -- breaking it down into a system library and a user library, allowing the user to add macro definitions to create new usable "statements" to use in our scripts. This would involve a more generic way to represent steps, using function signature-specific subclasses, or a predefined set of supported function pointer types. I think that function pointers can be cast to function pointers of different types, and that might get us part of the way there, but I see an explosion happening somewhere, either in the <b>switch</b> statements in <b>invoke</b> or in subclasses. it doesn't seem easy to really capture everything we might need at compile time. A function invocation in C isn't something that supports much in the way of compile-time introspection -- there's no standard facility to look up its arity, its number of parameters, and their types; we aren't working with S-expressions here. Even gruesome hacks involving variable-length argument lists won't let us really work this out for a general case, as far as I know, and I don't think template metaprogramming can entirely remedy this, although there might be some neat tricks to minimize the code we have to write.</p>
<p>Some extensions to our "scripting language" are clearly possible: for example, our language could be extended to include labels, goto, counters, and even conditional branching, fairly easily -- it's just that all of those items would look like function calls and be macro invocations that boiled down to overloaded constructor calls to some single struct or class type, or different struct or class types that have a single base class so that we can treat them uniformly. Essentially, we're implementing a script without ever parsing the text of our scripting language, per se, and that's what keeps it tiny.</p>
<p>The <b>run_sequence</b> function would need a little more complexity. In fact it could run multiple sequences in multiple threads -- there exist solutions for cooperative multi-tasking on Arduino. To my taste the ones I've seen so far are all still too heavyweight. I'm even tempted to implement a preemptive solution, so that a thread that is executing a delay can't delay the other threads. This may be a topic of some ongoing research, aka "playing," as my time allows.</p>
<p>Next time, if I can work something out, I'll consider some template-based ideas and whether they buy us anything useful. As always, I welcome your comments.</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-59927578307822397792013-08-14T01:16:00.000-04:002013-08-14T01:16:09.111-04:00Arduino, Day 1<p><i>Warning for Planet Haskell readers: imperative content! (Or, I tried to get GHC working in 2048 bytes of RAM but didn't get very far...)</i></p>
<p>A friend of mine sent me a <a href="https://www.sparkfun.com/products/11575">RedBoard</a> and asked me to collaborate with him on a development idea. So I'm playing with an Arduino-compatible device for the first time. I've been aware of the Arduino devices, and the maker... erm, what, "movement?" But just never got one. There were various reasons -- one was that after writing embedded code all day, what I've wanted to do with my time off is not necessarily write more embedded code. Another was that they are very small. But I'm always interested in learning something new, or maybe something quite old -- maybe a board designed specifically for hobbyists might help me revive some of my childhood interest in electronics.</p>
<p>So, I downloaded the Arduino IDE and checked that out a bit. There are some things about the way it's presented that drive me a little batty. The language is C++, but Arduino calls it the "Arduino Programming Language" -- it even has its own language reference page. Down at the bottom the fine print says "The Arduino language is based on C/C++." Ummm. What?</p>
<p>That really makes me mad. First, it seems to give the Arduino team credit for creating something that they really haven't. That team deserves plenty of credit -- not least for building a very useful library -- but they did not, repeat, did not, invent a programming language.</p>
<p>Second, it fails to give credit (and blame) for the language to the large number of people who actually designed and implemented C, C++, and the GCC cross-compiler running behind the scenes, with its reduced standard libraries and all. Of course, it's not that the Arduino team was really trying to hide the fact that there's an open-source compiler inside, but calling it the "Arduino Programming Langage" obfuscates this reality, at the very least.</p>
<p>And third, it obfuscates what programmers are actually learning -- specifically, the distinction between a <i>language</i> and a <i>library</i>.</p>
<p>That might keep things simpler for beginners but this is supposed to be a teaching tool, isn't it? I don't think it's a good idea to obfuscate the difference between the core language (for example, bitwise and arithmetic operators), macros (like <b>min</b>), and functions in the standard Arduino libraries. The Arduino documentation muddles this distinction. But it's important -- for one thing, errors in using each of these will result in profoundly different kinds of diagnostic messages or other failure modes. It also obfuscates something important for experts. That something is "which C++ is this?"</p>
<p>C++ has many variations now. Can I use enum classes or other C++11 features? I don't know, and because of the facade that Arduino is a distinct language, it is harder to find out. They even have the gall to list <b>true</b> and <b>false</b> as constants. Sure, they are constants, but that doesn't mean C and C++ have an actual, useful Boolean type. In fact, they can't, for reasons of backwards compatibility. And if there's one thing C and C++ programmers know, and beginners need to learn quickly, it's that logical truth in C and C++ is messy and requires vigilance. I would hate to have to explain to a beginner why testing a masked bit that is not equal to one against <b>true</b> does not give the expected result.</p>
<p>Anyway, all that aside, this is C++ where the IDE does a few hidden things for you when you compile your code. It inserts a standard header, <b>Arduino.h</b>. It links you to a standard <b>main()</b>. I guess that's all helpful. But finally, it generates prototypes for your functions. That implies a parsing stage, via a separate tool that is not a C++ compiler. If that very thought doesn't cause your brow to furrow, you don't know much about C++.</p>
<p>But let's talk about plugging in the Redboard. On my Mac Pro running Mountain Lion, the board was not recognized as a serial device at all. There's some kind of workaround for this but I just switched over to Ubuntu 12.04 on a ThinkPad laptop. The IDE works flawlessly. I tried to follow some directions to see where the code was actually built by engaging a verbose mode for compilation and uploading, but I couldn't get that working. So I decided that the IDE was obfuscating more than helping, and ditched it.</p>
<p>This was fairly easy, with the caveat that there are a bunch of outdated tools out there, and outdated blog posts explaining how to do it. I went down some dead ends and rabbit holes, but the procedure is really not hard. Ultimately, I used <b>sudo apt-get install</b> to install <b>arduino-core</b> and <b>arduino-mk</b>.</p>
<p>There is now a common <b>Arduino.mk</b> makefile in my <b>/usr/share/arduino</b> directory and I can make project folders with makefiles that refer to it. To make this work I had to add a new export to my <b>.bashrc</b> file, <b>export ARDUINO_DIR=/usr/share/arduino</b> (your mileage may vary depending on how your Linux version works, but that's where I define additional environment variables).</p>
<p>The Makefile in my project directory has the following in it:</p>
<pre>BOARD_TAG = uno
ARDUINO_PORT = /dev/serial/by-id/usb-*
include /usr/share/arduino/Arduino.mk</pre>
<p>And that's it. Nothing else. Everything else is inherited from the common Arduino.mk. I can throw <b>.cpp</b> and <b>.h</b> files in there and <b>make</b> builds them and <b>make upload</b> uploads them using the amusingly named utility <b>avrdude</b> (the name stands for AVR Downloader/UploaDEr... er, Dude, that's OK, you can just call it AVRDUDE because you're into AVR chips and you wrote it, that's good enough...</p>
<p>If you have trouble with the upload (wait, is this an "upload" or a "download?" I always thought of "down" as being "downstream" from the bigger computer/data store/ocean to the smaller computer/pond -- like from the Internet to your computer -- but I guess you can call it whatever you want) you might take a look at your devices. A little experimentation (listing the contents of <b>/dev</b> before and after unpluging the board) reveals that the RedBoard is showing up on my system as a device under <b>/dev/serial</b> -- in my case, <b>/dev/serial/by-id/usb-FTDI_FT232R_USB_UART_A601EGHT-if00-port0</b> and <b>/dev/serial/by-path/pci-0000:00:1d.0-usb-0:2:1.0-port0</b> (your values will no doubt vary). That's why my <b>Makefile</b> reads <b>ARDUINO_PORT = /dev/serial/by-id/usb-*</b> -- so it will catch anything that shows up in there with the <b>usb-</b> prefix. Of course, if your device is showing up elsewhere, or you have more than one device, you might need to tweak this to properly identify your board.</p>
<p>When you look at the basic blink demo program in the Arduino IDE, you see this, the contents of an <b>.ino</b> file (except that I have removed the comments):</p>
<pre>int led = 13;
void setup() {
pinMode(led, OUTPUT);
}
void loop() {
digitalWrite(led, HIGH);
delay(1000);
digitalWrite(led, LOW);
delay(1000);
}</pre>
<p>The Makefile knows how to build an <b>.ino</b> file and inserts the necessary header, implementation of <b>main</b>, and generates any necessary prototypes. Here's what the file looks like to the compiler (and if you want to build this code with <b>make</b> as a <b>.cpp</b> file, it needs to look more like this):</p>
<pre>#include <Arduino.h>
int led = 13;
void setup() {
pinMode(led, OUTPUT);
}
void loop() {
digitalWrite(led, HIGH);
delay(1000);
digitalWrite(led, LOW);
delay(1000);
}
int main(void)
{
init();
#if defined(USBCON)
USBDevice.attach();
#endif
setup();
for (;;) {
loop();
if (serialEventRun) serialEventRun();
}
return 0;
}</pre>
<p>And there it is -- C++, <b>make</b>, and no IDE. Relaxen and watchen <a href="http://en.wikipedia.org/wiki/Blinkenlights">Das blinkenlights</a>!</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-19447265917621788352013-07-17T15:52:00.000-04:002013-07-17T15:53:30.978-04:00The Polar Game in Haskell, Day 7: Towards a GUI, Continued<p>So, trying wxHaskell. First, I want to try removing everything that might be left over from yesterday's experiments:</p>
<pre>Pauls-Mac-Pro:~ paul$ brew list
gettext libffi pkg-config xz
Pauls-Mac-Pro:~ paul$ brew uninstall gettext libffi pkg-config xz
Uninstalling /usr/local/Cellar/gettext/0.18.3...
Uninstalling /usr/local/Cellar/libffi/3.0.13...
Uninstalling /usr/local/Cellar/pkg-config/0.28...
Uninstalling /usr/local/Cellar/xz/5.0.5...
Pauls-Mac-Pro:~ paul$ port installed
The following ports are currently installed:
libiconv @1.14_0 (active)
pkgconfig @0.28_0 (active)
Pauls-Mac-Pro:~ paul$ sudo port uninstall pkgconfig libiconv
---> Deactivating pkgconfig @0.28_0
---> Cleaning pkgconfig
---> Uninstalling pkgconfig @0.28_0
---> Cleaning pkgconfig
---> Deactivating libiconv @1.14_0
---> Cleaning libiconv
---> Uninstalling libiconv @1.14_0
---> Cleaning libiconv</pre>
<p>Then install wx: I'm attempting the directions <a href="http://www.haskell.org/haskellwiki/WxHaskell/MacOS_X">here</a>.</p>
<b>brew install wxmac --use-llvm --devel</b>
<pre>brew install wxmac --devel
Warning: It appears you have MacPorts or Fink installed.
Software installed with other package managers causes known problems
for Homebrew. If a formula fails to build, uninstall MacPorts/Fink
and try again.</pre>
<p>(There shouldn't be any libraries or binaries in the various paths to interfere, so I'll ignore this). And it seemed to succeed. So, next step from the instructions above: <b>Check your path to make sure you are using your wxWidgets and not the default Mac one. The command <b>which wx-config</b> should not return the file path /usr/bin/wx-config</b> (On my system it returns <b>/usr/local/bin/wx-config</b>). Next, <b>cabal install wx cabal-macosx</b>. That chugs away for a while and I see an unnervingly large number of warnings, but it builds. And then, I saved <a href="https://raw.github.com/jodonoghue/wxHaskell/master/samples/wxcore/HelloWorld.hs">this file</a> as hello-ex.hs and <b>ghc --make HelloWorld.hs</b> and <b>macosx-app hello-wx</b> and <b>./hello-wx.app/Contents/MacOS/hello-wx</b> and the result runs and I get a window, although it pops up off the bottom of my primary display, and the application's main menu does not seem to render its menu items quite right (they say "Hide H" and "Quit H" instead of the application name). But still -- promising!</p>
<p>So -- some code. To facilitate working with a GUI module in a separate <b>.hs</b> file I am now calling the core logic <b>ArcticSlideCore.hs</b>. and that file begins with <b>module ArcticSlideCore where</b>. I don't have very much working yet, but here's what is in my <b>ArcticSlideGui.hs</b> file so far. First I define my module and do my imports:</p>
<pre>module Main where
import Graphics.UI.WX
import ArcticSlideCore</pre>
<p>Then I define some bitmaps. For purposes of experimentation I made <b>.png</b> files out of the original Polar game's CICN resources. I want to redraw them -- first, to avoid blatant copyright infringement and second, to make them bigger. But temporarily:</p>
<pre>bomb = bitmap "bomb.png"
heart = bitmap "heart.png"
house = bitmap "house.png"
ice = bitmap "ice_block.png"
tree = bitmap "tree.png"</pre>
<p>While they are game tiles as such, there are icons for the penguin facing in the four cardinal directions and icons for a breaking ice block and exploding bomb that were used in original animations:</p>
<pre>penguin_e = bitmap "penguin_east.png"
penguin_s = bitmap "penguin_south.png"
penguin_w = bitmap "penguin_west.png"
penguin_n = bitmap "penguin_north.png"
ice_break = bitmap "ice_block_breaking.png"
bomb_explode = bitmap "bomb_exploding.png"</pre>
<p>I noticed that wxHaskell's <b>Point</b> type operates in reverse. I'm accustomed to C arrays where the higher-rank indices come first (so y, x or row index, column index for tile positions), but points are backwards. My icons are 24x24 pixels, so I rearrange and scale them like so:</p>
<pre>posToPoint :: Pos -> Point
posToPoint pos = ( Point ( posX pos * 24 ) ( posY pos * 24 ) )</pre>
<p>Now, some convenience function for drawing bitmaps based on Tile type or based on a wxHaskell bitmap. These are two more cases where I was not sure of the type signature, so I wrote the functions without them:</p>
<pre>drawBmp dc bmp pos = drawBitmap dc bmp point True []
where point = posToPoint pos
drawTile dc tile pos = drawBmp dc bmp pos
where bmp = case tile of Bomb -> bomb
Heart -> heart
House -> house
Ice -> ice
Tree -> tree</pre>
<p>GHCI says:</p>
<pre>Prelude Main> :t drawBmp
drawBmp
:: Graphics.UI.WXCore.WxcClassTypes.DC a
-> Graphics.UI.WXCore.WxcClassTypes.Bitmap ()
-> ArcticSlideCore.Pos
-> IO ()</pre>
<p>That boils down to <b>drawBmp :: DC a -> Bitmap () -> Pos -> IO ()</b>, and the signature for DrawTile similarly boils down to <b>drawTile :: DC a -> Tile -> Pos -> IO ()</b>. Thanks, GHCI!</p>
<p>Next, I need a view method. This is just a placeholder test to verify that I can draw all my icons in the bounds where I expect them:</p>
<pre>draw dc view
= do
drawTile dc Bomb ( Pos 0 0 )
drawTile dc Heart ( Pos 0 1 )
drawTile dc House ( Pos 0 2 )
drawTile dc Ice ( Pos 0 3 )
drawTile dc Tree ( Pos 0 4 )
drawBmp dc penguin_e ( Pos 1 0 )
drawBmp dc penguin_s ( Pos 1 1 )
drawBmp dc penguin_w ( Pos 1 2 )
drawBmp dc penguin_n ( Pos 1 3 )
drawBmp dc ice_break ( Pos 0 23 )
drawBmp dc bomb_explode ( Pos 3 23 )</pre>
<p>Now, my <b>guy</b> function is where things get interesting and wxHaskell shows off a little. I read this <a href="http://legacy.cs.uu.nl/daan/download/papers/wxhaskell.pdf">paper</a> that talks about some of the layout options and other tricks of the wxHaskell implementation, and discovered that this maps really nicely to defining my window in terms of a grid of icons. <b>space 24 24</b> returns a layout item of the appropriate size, and <b>grid</b> returns a layout item when given spacing values (I want the icons touching, so I use 0 0) and a list of lists for rows and columns. To generate the proper structure of 4 rows of 24 columns I just take what I need from infinite lists: <b>take 4 $ repeat $ take 24 $ repeat $ space 24 24</b> Oh, that's nifty!</p>
<pre>gui :: IO ()
gui
= do f <- frame [text := "Arctic Slide"]
t <- timer f [ interval := 250
]
set f [ layout := grid 0 0 $ take 4 $ repeat $
take 24 $ repeat $ space 24 24
,bgcolor := white
,on paint := draw
]
return ()</pre>
<p>And finally, main:</p>
<pre>main :: IO ()
main
= start gui</pre>
<p>To build this for use as a MacOS X GUI app I just do <b>ghc --make ./arcticSlideGui.hs</b>, and if it compiles properly then <b>macosx-app arcticSlideGui; ./arcticSlideGui.app/Contents/MacOS/arcticSlideGui</b> and I have a little GUI window:</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4G2hah5QxixySIS8B_kSpqaao48zb1JqfwoQY7JMA2mu949uJ7-rTQPu8BdClD_S5SQo7xHjlg7CSueJ0_YXAGKHFVd0RuvGpMSwn5vaux-B1h2SpIOuHd6QvbL3X2WvAAd8r/s1600/arctic-slide-gui-test-1.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4G2hah5QxixySIS8B_kSpqaao48zb1JqfwoQY7JMA2mu949uJ7-rTQPu8BdClD_S5SQo7xHjlg7CSueJ0_YXAGKHFVd0RuvGpMSwn5vaux-B1h2SpIOuHd6QvbL3X2WvAAd8r/s400/arctic-slide-gui-test-1.tiff" /></a></div>
<p>Sweet! Now I've got some more thinking to do. There's some plumbing that needs to get hooked up between the core game logic and the GUI layer. The core game logic is mostly factored the way I want it to be -- it gets a world and a penguin move and returns an updated world -- but I need to do a little more than just map the tiles to a series of drawTile calls. I might want to support timed sequences of changes to the GUI representation of the board -- for example, smooth sliding of game pieces and smooth walking of the penguin. The <b>draw</b> method should draw the board pieces and the penguin all at once, with no redundancy if possible. Sound effects would be nice. Animation for crushing an ice block and blowing up a mountain would be nice. I've got some ideas along these lines based on event queues and a timer, and some other pieces of sample code I've been looking at.</p>
<p>Meanwhile, if any of you would like to take a crack at redrawing the graphics, please be my guest. It would be nice if the replacement icons would fit on an iPhone or iPod Touch. 48x84 is just a little bit too big -- 48 pixels by 24 icons is 1152 pixels, and the iPhone 4 and 5 screens are 640x960 and 640x1136. 40 pixels wide would fit perfectly on an iPhone 4. Note that the icons don't actually have to be square -- there is room to spare vertically. It might be nice, though, to leave room for a few extra rows, to support game boards that break out of the original 4-row height.</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com2tag:blogger.com,1999:blog-21500237.post-53242388223177901572013-07-16T17:47:00.000-04:002013-07-16T17:50:00.196-04:00The Polar Game in Haskell, Day 6/12: Towards a GUI, Continued<p>OK, so when I left off last time, I was running into a gruesome link error. I found <a href="http://stackoverflow.com/questions/2726248/ghc-6-12-and-macports">this Stack Overflow thread</a> and the first accepted answer fixed the problem. However, it seems that the answer may be to avoid MacPorts versions of the libraries I need. So I'm going to attempt to clean that all out and use Homebrew. So, first:</p>
<pre>sudo port -fp uninstall --follow-dependents installed</pre>
<p>And then I'm manually cleaning out some of the stuff mentioned <a href="http://superuser.com/questions/367434/how-do-you-remove-macports-and-all-the-packages-it-has-installed">in this article</a>.</p>
<p>Next, I'm removing this from my .profile (hey, I'm so pleased that it is clearly marked!</p>
<pre># MacPorts Installer addition on 2013-07-16_at_11:57:13:
adding an appropriate PATH variable for use with MacPorts.
export PATH=/opt/local/bin:/opt/local/sbin:$PATH
# Finished adapting your PATH environment variable for
use with MacPorts.</pre>
<p>Now to install Homebrew:</p>
<pre>ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go)"</pre>
<p>I ran brew doctor and wow, I have a mountain of warnings. I got rid of most of them except for several about "unbrewed" things -- static libraries, .la files, and dylibs in /usr/local/lib. I get a warning about MacGPG2 but that seems to be fixed by upgrading to the current version. So now I'm trying cabal install --reinstall gtk, and I get:</p>
<pre>Configuring gtk-0.12.4...
setup: The pkg-config package gthread-2.0 is required but it could not be
found.</pre>
<p>And so, attempting to follow the directions <a href="http://www.haskell.org/haskellwiki/Gtk2Hs/Mac">here</a>:</p>
<pre>brew install glib cairo gtk gettext fontconfig</pre>
<p>...and that actually crashes. I get "confest cannot be opened because of a problem." In the console log:</p>
<pre>Process: conftest [12844]
Path: /private/tmp/*/conftest
Identifier: conftest
Version: 0
Code Type: X86-64 (Native)
Parent Process: sh [12843]
User ID: 501
Date/Time: 2013-07-16 15:42:18.117 -0400
OS Version: Mac OS X 10.8.4 (12E55)
Report Version: 10
Crashed Thread: 0
Exception Type: EXC_BREAKPOINT (SIGTRAP)
Exception Codes: 0x0000000000000002, 0x0000000000000000
Application Specific Information:
dyld: launch, loading dependent libraries
Dyld Error Message:
Library not loaded: /usr/local/lib/libintl.8.dylib
Referenced from: /private/tmp/*/conftest
Reason: no suitable image found. Did find:
/usr/local/lib/libintl.8.dylib:
no matching architecture in universal wrapper
/usr/local/lib/libintl.8.dylib:
no matching architecture in universal wrapper</pre>
<p>And I get an error about "GLib requires a 64 bit type." I also had to do some manual clean-out of some files that had the wrong permissions and were interfering with installing pkgconfig. I found a number of people reporting this problem, but none of the solutions they outlined seemed to work for me. So... what else can I try?</p>
<p>There's this: <a href="http://www.haskell.org/haskellwiki/Gtk2Hs/Mac#GTK.2B_OS_X_Framework">http://www.haskell.org/haskellwiki/Gtk2Hs/Mac#GTK.2B_OS_X_Framework</a></p>
<p>OK! Deep sigh... let's try this!</p>
<pre>Pauls-Mac-Pro:Downloads paul$ sh ./gtk-osx-build-setup.sh
Checking out jhbuild (07b5a7d) from git...
Cloning into 'jhbuild'...
remote: Counting objects: 37027, done.
remote: Compressing objects: 100% (14715/14715), done.
remote: Total 37027 (delta 28610), reused 28612 (delta 22178)
Receiving objects: 100% (37027/37027), 7.27 MiB | 2.27 MiB/s, done.
Resolving deltas: 100% (28610/28610), done.
Switched to a new branch 'stable'
Patch is empty. Was it split wrong?
If you would prefer to skip this patch, instead run "git am --skip".
To restore the original branch and stop patching run "git am --abort".
Installing jhbuild...
gnome-autogen.sh not available
yelp-tools not available
Configuring jhbuild without autotools
Now type `make' to compile jhbuild
Installing jhbuild configuration...
Installing gtk-osx moduleset files...
PATH does not contain /Users/paul/.local/bin, it is recommended that you add that.
Done.</pre>
<p>Ummm... OK, wow, that installed source in my home directory build tools in a <i>hidden</i> directory (prefaced with a period) under my home directory. There are warning notes about how the build process conflicts with MacPorts and fink. There's also a note that says "Note: jhbuild requires Python 2.5 to unpack tar files" (of course it does... that's the simplest and most system-compatible way to unpack tar files, right?) Ugh. Anyway... in <b>~/Source/jhbuild</b> I type <b>~/.local/bin/jhbuild bootstrap</b> and it builds about a bazillion things including <b>cmake</b>. (Talk amongst yourselves, this is going to take a while... time for another snack...)</p>
<p>That seemed to work. And so: <b>~/.local/bin/jhbuild build meta-gtk-osx-bootstrap</b> and <b>~/.local/bin/jhbuild build meta-gtk-osx-core</b>. Somewhat to my shock, everything succeeded! I tried to build gimp, but that failed with "we require Pango with the optional support for Cairo compiled in," and I don't want to go too far down that rabbit hole, so I gave up on that. So let's see if I can make that work with GHC. The next step is package-config. Which requires glib. Ummm, wait a minute... oh, crap. That's still broken with homebrew. Ummm. What about package-config from MacPorts, which the instructions for GTK OSX warned me about? Sure, let's try it, what the hell... after all, I've wasted nearly a full day already... so, <b>sudo port selfupdate</b>, <b>sudo port install pkg-config</b>... that seemed to work. So then we download the Gtk2HS tarball... ummm, the link from the instructions is broken. Ummm... from SourceForge <a href="http://sourceforge.net/projects/gtk2hs/">here</a>... but that version is looking much older than the one described <a href="http://projects.haskell.org/gtk2hs/archives/2012/11/21/new-gtk2hs-0124-release/">here</a>. I'm getting a bad feeling about this. But anyway... 0.10.1 it is! Configure away!</p>
<pre>checking for pkg-config... /opt/local/bin/pkg-config
checking pkg-config is at least version 0.9.0... yes
checking for GLIB... no
configure: error:
The development files for the glib-2.x library were not found.
Perhaps you need to install glib or glib-devel</pre>
<p>Huh. Well. It's just about the end of my work day; I've got to go downstairs and help my wife get dinner ready. Ummm. So! I hope you've enjoyed this tutorial on how to use the GTK GUI library in Haskell! Please join me next time when I perform brain surgery on myself using a hacksaw, a folding mirror, and a bottle of Scotch!</p>
<iframe width="560" height="315" src="//www.youtube.com/embed/usAXHygEQJU" frameborder="0" allowfullscreen></iframe>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com4tag:blogger.com,1999:blog-21500237.post-2991890375709925942013-07-16T14:11:00.002-04:002013-07-16T14:35:19.290-04:00The Polar Game in Haskell, Day 6: Towards a GUI<p>So, I have some time today to program and I want to see how far I can get in starting to develop a GUI for my game, incomplete as it is. Can I get a window displayed and reacting to mouse or keyboard events, and drive the game logic with it?</p>
<p>I came across the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.8446&rep=rep1&type=pdf">FranTk -- A Declarative GUI Language for Haskell</a> (PDF file link) by Meurig Sage and it looked interesting, so I considered trying FranTk. However, that led to broken links. Moving on...</p>
<p>Let's see if I can get somewhere with FG. That needs gtk2hs. Hmmm... cabal update, cabal install gtk2hs-buildtools, cabal install gtk.</p>
<pre>[1 of 2] Compiling Gtk2HsSetup
( Gtk2HsSetup.hs, dist/setup-wrapper/Gtk2HsSetup.o )
[2 of 2] Compiling Main
( SetupMain.hs, dist/setup-wrapper/Main.o )
Linking dist/setup-wrapper/setup ...
Configuring cairo-0.12.4...
setup: The program pkg-config version >=0.9.0 is required but it
could not be found.
Failed to install cairo-0.12.4</pre>
<p>I tried downloading pkg-config-0.28 source from <a href="http://pkgconfig.freedesktop.org/releases/">here</a> and that got me as far as running ./configure --prefix=/usr/local/ and seeing:</p>
<pre>configure: error: Either a previously installed
pkg-config or "glib-2.0 >= 2.16" could not be found.
Please set GLIB_CFLAGS and GLIB_LIBS to the correct
values or pass --with-internal-glib to configure to use
the bundled copy.</pre>
<p>So I tried ./configure --prefix=/usr/local/ --with-internal-glib and that seemed to go OK; I was able to do make, make check -- one failure out of 25 tests in "check-path" -- and sudo make install. Back to cabal install gtk == nope.</p>
<pre>Configuring cairo-0.12.4...
setup: The pkg-config package cairo-pdf is required but it
could not be found.
Failed to install cairo-0.12.4
Configuring glib-0.12.4...
setup: The pkg-config package glib-2.0 is required but it
could not be found.
Failed to install glib-0.12.4
cabal: Error: some packages failed to install:
cairo-0.12.4 failed during the configure step. The exception was:
ExitFailure 1
gio-0.12.4 depends on glib-0.12.4 which failed to install.
glib-0.12.4 failed during the configure step. The exception was:
ExitFailure 1
gtk-0.12.4 depends on glib-0.12.4 which failed to install.
pango-0.12.4 depends on glib-0.12.4 which failed to install.</pre>
<p>OK... so I guess it's time to install MacPorts because the Cairo page suggests using it to install cairo. I know there are competing tools -- fink and Homebrew and I've used both of them at some point, years ago, but removed them, for reasons I can no longer remember... I think it had something to do with the way they insisted on installing things under /opt and it was clear to me if they would interfere with each other. But anyway, I'll try the MacPorts installer for 2.13 for Mountain Lion... and then sudo port install cairo... oh, wow, it's installing the universe... bzip2, zlib, libpng, free type, perl5, python27... oh, the humanity...</p>
<p>OK, where are we... oh, cabal install gtk again. "The pkg-config package cairo-pdif is required but it could not be found." Let's try glib again.</p>
<pre>Pauls-Mac-Pro:Gitit Wiki paul$ sudo port install glib2
---> Computing dependencies for glib2
---> Cleaning glib2
---> Scanning binaries for linking errors: 100.0%
---> No broken files found.</pre>
<p>But cabal install gtk is still broken. Is there a MacPorts version of gtk2? Yes, apparently OH GOD IT'S BUILDING THE WHOLE WORLD...</p>
<p>(Musical interlude...)</p>
</p>But then cabal install gtk seems to go OK. A lot of deprecated function warnings. Another twenty minutes go by... what was I doing again? You know, I'm getting all confused, why don't I start with gtk2hs because <i>Real World Haskell</i> uses it... I need to sudo port install glade3... and OH GOD IT'S BUILDING THE WHOLE WORLD AGAIN... aaand welcome to hour three of "The Polar Game in Haskell, Day 6: Towards a GUI..."</p>
</p>OK, glade and glade3 don't have any executables in my path. Oh, it's glade-3, how silly of me, even though the port is called glade3. And it says Gtk-WARNING **: cannot open display:. Oh yeah, it's X-Windows JUST SHOOT ME IN THE GODDAMN FACE... oh, I mean now I will happily go down another rabbit hole, thank you sir may I have another? So... the older X server is not supported in Mountain Lion anymore but there's something called XQuartz. XQuartz-2.7.4.dmg... "you need to log out and log back in to make XQuartz your default X11 server." Oh, thanks, I'll just close these FOURTEEN browser tabs, SEVEN bash terminal sessions, and other apps... you know, it's time for a food break anyway...</p>
<p>...aaand we're back. It launches, but I get "an error occurred while loading or saving configuration information for glade-3. Some of your configuration settings may not work properly." There's a "Details" button:</p>
<pre>Failed to contact configuration server; the most common
cause is a missing or misconfigured D-Bus session bus daemon.
See http://projects.gnome.org/gconf/ for information. (Details -
1: Failed to get connection to session: Session D-Bus not running.
Try running `launchctl load -w
/Library/LaunchAgents/org.freedesktop.dbus-session.plist'.)
Failed to contact configuration server; the most common cause
is a missing or misconfigured D-Bus session bus daemon. See
http://projects.gnome.org/gconf/ for information. (Details -
1: Failed to get connection to session: Session D-Bus not running.
Try running `launchctl load -w
/Library/LaunchAgents/org.freedesktop.dbus-session.plist'.)
Failed to contact configuration server; the most common cause
is a missing or misconfigured D-Bus session bus daemon. See
http://projects.gnome.org/gconf/ for information. (Details -
1: Failed to get connection to session: Session D-Bus not running.
Try running `launchctl load -w
/Library/LaunchAgents/org.freedesktop.dbus-session.plist'.)
Failed to contact configuration server; the most common cause
is a missing or misconfigured D-Bus session bus daemon. See
http://projects.gnome.org/gconf/ for information. (Details -
1: Failed to get connection to session: Session D-Bus not running.
Try running `launchctl load -w
/Library/LaunchAgents/org.freedesktop.dbus-session.plist'.)
Failed to contact configuration server; the most common cause
is a missing or misconfigured D-Bus session bus daemon. See
http://projects.gnome.org/gconf/ for information. (Details -
1: Failed to get connection to session: Session D-Bus not running.
Try running `launchctl load -w
/Library/LaunchAgents/org.freedesktop.dbus-session.plist'.)
</pre>
<p>Gaaah! Well, OK, I can do that... and I'm able to edit a little file. Now to look at some tutorials. I get 404s on http://www.haskell.org/gtk2hs/docs/tutorial/glade/ and also http://dmwit.com/gtk2hs/%7C -- ooof. My first attempt at adapting a little code from <i>Real World Haskell</i> -- not going so well. This tutorial is still available: <a href="http://www.haskell.org/haskellwiki/Gtk2Hs/Tutorials/ThreadedGUIs">http://www.haskell.org/haskellwiki/Gtk2Hs/Tutorials/ThreadedGUIs</a> but as to how useful it is... I'm gonna have to get back to you on that. There's also this tutorial: <a href="http://home.telfort.nl/sp969709/gtk2hs/chap2.html">http://home.telfort.nl/sp969709/gtk2hs/chap2.html</a> so I can create a little GTK GUI entirely in code rather than using a Glade file. Something like this:</p>
<pre>import qualified Graphics.UI.Gtk
main :: IO ()
main = do
Graphics.UI.Gtk.initGUI
window <- Graphics.UI.Gtk.windowNew
Graphics.UI.Gtk.widgetShowAll window
Graphics.UI.Gtk.mainGUI</pre>
</p>Aaand I get an immediate segmentation fault. Hmmm. I think I read about running with "-threaded..."</p>
<pre>Pauls-Mac-Pro:arctic-slide-haskell paul$ ghci -threaded
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help
Warning: -debug, -threaded and -ticky are ignored by GHCi</pre>
<p>OK, how about GHC?</p>
<pre>Pauls-Mac-Pro:arctic-slide-haskell paul$ ghc basic-gui.hs -threaded
[1 of 1] Compiling Main ( basic-gui.hs, basic-gui.o )
Linking basic-gui ...
Undefined symbols for architecture x86_64:
"_iconv", referenced from:
_hs_iconv in libHSbase-4.5.0.0.a(iconv.o)
(maybe you meant: _hs_iconv_open,
_base_GHCziIOziEncodingziIconv_iconvEncoding6_info ,
_hs_iconv , _base_GHCziIOziEncodingziIconv_iconvEncoding4_closure , _base_GHCziIOziEncodingziIconv_iconvEncoding3_info ,
_base_GHCziIOziEncodingziIconv_iconvEncoding5_closure ,
_base_GHCziIOziEncodingziIconv_iconvEncoding6_closure ,
_base_GHCziIOziEncodingziIconv_iconvEncoding3_closure ,
_base_GHCziIOziEncodingziIconv_iconvEncoding2_closure ,
_base_GHCziIOziEncodingziIconv_iconvEncoding2_info ,
_base_GHCziIOziEncodingziIconv_iconvEncoding5_info ,
_base_GHCziIOziEncodingziIconv_iconvEncoding7_closure ,
_hs_iconv_close ,
_base_GHCziIOziEncodingziIconv_iconvEncoding7_info )
"_iconv_close", referenced from:
_hs_iconv_close in libHSbase-4.5.0.0.a(iconv.o)
(maybe you meant: _hs_iconv_close)
"_iconv_open", referenced from:
_hs_iconv_open in libHSbase-4.5.0.0.a(iconv.o)
(maybe you meant: _hs_iconv_open)
"_locale_charset", referenced from:
_localeEncoding in libHSbase-4.5.0.0.a(PrelIOUtils.o)
ld: symbol(s) not found for architecture x86_64
collect2: ld returned 1 exit status</pre>
<p>Hmmm. It seems like this might take longer than I thought...</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-85172814131597435212013-07-12T18:17:00.000-04:002013-07-12T18:23:24.078-04:00The Polar Game in Haskell, Day 5 3/4: a Bug Fix and liftM<p>Jeff Licquia has been playing further with the code and so have I. He discovered a bug in the version I posted in yesterday's installment (my bad). In slide' I neglected to call slide' in the recursive version of slide' but called the existing non-monadic slide. In other words, I had:</p>
<pre>slide' ( t : Empty : ts ) = noscore ( Empty : ( slide ( t : ts ) ) )</pre>
<p>The problem here is that we'll add nothing to the accumulated score, and proceed into a chain of function invocations that handle ordinary lists. So the score increase that should happen at that point never happens:</p>
<pre>*Main> runWriter $ collide' [Heart, House]
([Empty,House],Sum {getSum = 1})
*Main> runWriter $ collide' [Heart, Empty, House]
([Empty,Empty,House],Sum {getSum = 0})</pre>
<p>Oops. Yeah, that's a bug. Note that the compiler can't catch this because it's doing what I've asked; there are not actually any type conflicts. The monadic slide' returns the type it is supposed to return, but in building up the "payload, the <b>[ Tile ]</b> part of <b>ScoreTracker [ Tile ]</b>, the code fails to continue to build up the state. Let this be a lesson to me -- leaving around the previous version of a function, when I'm testing a new one can be hazardous!</p>
<p>So, we can just fix that by calling slide', right?</p>
<pre>slide' ( t : Empty : ts ) = noscore ( Empty : ( slide' ( t : ts ) ) )</pre>
<p>Um, not so much:</p>
<pre>arctic-slide.hs:52:49:
Couldn't match expected type `[Tile]'
with actual type `ScoreTracker [Tile]'
In the return type of a call of slide'
In the second argument of `(:)', namely `(slide' (t : ts))'
In the first argument of `noscore', namely
`(Empty : (slide' (t : ts)))'</pre>
<p>Oh... yeah. There's that. We want to continue building up the monadic version of the list, but the <b>(:)</b> just takes a regular list. Now it's all complicated! But really there's a simple solution. I'll quote Jeff for a while, since he explained it so well to me. I have not quoted his code <i>exactly</i>, but the ideas are the same:</p>
<blockquote>...the straightforward fix fails, because <b>slide'</b> returns a <b>ScoreTracker</b>, not a <b>[ Tile ]</b>. So the fix is a little more complicated. Since <b>slide'</b> returns pretty much exactly what we need, we can start with just that:</blockquote>
<pre>slide' ( t : Empty : ts ) = slide' ( t : ts )</pre>
<blockquote>That's not quite right; we just dropped a tile. To get it back, remember that everything is a function, including the : operator [and so it is easily composed with other functions -- PRP]. That means we can create a function that prepends an Empty element to a list...</blockquote>
<pre>prefix_empty :: [ Tile ] -> [ Tile ]
prefix_empty ts = Empty : ts</pre>
<blockquote>So why would we do this? Because we need to take ScoreTracker into account. Here Haskell provides a function called "liftM", which takes a normal function and "lifts" it into a monad. So:</blockquote>
<pre>prefix_empty_st :: ScoreTracker [ Tile ] -> ScoreTracker [ Tile ]
prefix_empty_st = liftM prefix_empty</pre>
<blockquote>will give us a function with the type <b>ScoreTracker [ Tile ] -> ScoreTracker [ Tile ]</b>, which is what we want. (Technically, that's not true; it gives us <b>Monad m => m [ Tile ] -> m [ Tile ]</b>. But that's just a generic version of what we want, which works with <b>ScoreTracker</b>, <b>Maybe</b>, or lots of other monads).</blockquote>
<p>So now we have this:</p>
<pre>slide' ( t : Empty : ts ) = prefix_empty_st $ slide' ( t : ts )</pre>
<p>Which doesn't use <b>score</b> or <b>noscore</b> -- it just builds up the list, still in a monadic context, preserving whatever score changes might be applied by the function invocations it makes. And actually since we're not going to use the prefix functions elsewhere, they don't really earn their keep, and we can just write:</p>
<pre>slide' ( t : Empty : ts ) = liftM ( Empty : ) $ slide' ( t : ts )</pre>
<p>Note the partial application of <b>(:)</b> by binding it to only one parameter before we pass it to <b>liftM</b> -- we're creating a new version of <b>(:)</b> that only takes one argument instead of two.</p>
<p>Jeff went on to identify a second bug, basically caused by the same problem in a collide' function also calling slide instead of slide'. A quick fix is to make that collide' function look like the slide' function we just fixed. But then, why not define one in terms of the other?</p>
<pre>collide' ( t : Empty : ts ) | movable t = slide' ( t : Empty : ts )</pre>
<p>Let's go back a bit and reconsider -- when I was using a special value for Edge, the logic for slide and collide was considerably simpler (although it did not work right). Here it is today:</p>
<pre>slide' :: [ Tile ] -> ScoreTracker [ Tile ]
slide' ( Ice_Block : ts ) | ( null ts ) || ( blocking $ head ts ) =
noscore ( Ice_Block : ts )
slide' ( t : Empty : ts ) = liftM ( Empty : ) $ slide' ( t : ts )
slide' ( t : ts ) | ( null ts ) || ( blocking $ head ts ) =
collide' ( t : ts )
collide' :: [ Tile ] -> ScoreTracker [ Tile ]
collide' [] = noscore []
collide' ( t : ts ) | fixed t = noscore ( t : ts )
collide' ( Bomb : Mountain : ts) = noscore ( [ Empty, Empty ] ++ ts )
collide' ( Heart : House : ts ) = score ( [ Empty, House ] ++ ts )
collide' ( Ice_Block : ts ) | ( null ts ) || ( blocking $ head ts ) =
noscore ( Empty : ts )
collide' ( t : ts ) | ( movable t ) && ( ( null ts ) ||
( blocking $ head ts ) ) = noscore ( t : ts )
collide' ( t : Empty : ts ) | movable t =
slide' ( t : Empty : ts )</pre>
<p>Erm. I'd no longer call that elegant, beautiful code. For one thing, I have to wrap it brutally to fit into my Blogger text window. That's not just annoying when dealing with Blogger -- it suggests that the lines are too long for easy reading even if they aren't wrapped. And here's what Jeff's version looks like today -- he's implemented his own way to structure the code with guards:</p>
<pre>slide :: [ Tile ] -> ScoreTracker [ Tile ]
slide [] = noscore []
slide ( t1 : t2 : ts )
| t1 == Ice_Block && blocking t2 = noscore ( t1 : t2 : ts )
| blocking t2 = collide ( t1 : t2 : ts )
| otherwise = do
ts' <- slide ( t1 : ts )
return ( Empty : ts' )
slide ( t : ts )
| t == Ice_Block = noscore ( t : ts )
| otherwise = collide ( t : ts )
collide :: [ Tile ] -> ScoreTracker [ Tile ]
collide [] = noscore []
collide ( t1 : t2 : ts )
| ( t1, t2 ) == ( Bomb, Mountain ) = noscore ( Empty : Empty : ts )
| ( t1, t2 ) == ( Heart, House ) = score ( Empty : House : ts )
| t1 == Ice_Block && blocking t2 = noscore ( Empty : t2 : ts )
| movable t1 && blocking t2 = noscore ( t1 : t2 : ts )
| movable t1 = do
ts' <- slide ( t1 : ts )
return ( Empty : ts' )
| otherwise = noscore ( t1 : t2 : ts )
collide ( t : ts )
| t == Ice_Block = noscore ( Empty : ts )
| otherwise = noscore ( t : ts )</pre>
<p>And I like that -- using the separate functions for both slide and collide only to handle the <b>structurally</b> different versions -- empty list, list with at least two items, list with at least one item -- and the <i>guards</i> to handle when we differ by value. It is, I think, more readable than mine. I was a little freaked out by the use of <b>do</b> and <b><-</b> in the middle of a function outside of main, but I'll think on that some more. I have not quite satisfied myself that it is perfectly correct, but then, I haven't really convinced myself that mine is correct either. So I have more to do on that front!</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com1tag:blogger.com,1999:blog-21500237.post-54353445422692528722013-07-11T19:22:00.003-04:002013-07-12T18:22:17.486-04:00The Polar Game in Haskell, Day 5 1/2: Refactoring with a Monad<p>The job search has eaten my brain for the last few days -- have I mentioned yet that I need a job? Oh, yes, I believe I may have -- but I'm taking some time to press on with my Haskell larnin', especially since I've been getting great, helpful feedback.</p>
<p>The first thing I did was make some minor fixes to the list implementation, as suggested by Jeff. It's working now and my version looks like this:</p>
<pre>next_board_list :: BoardList -> Pos -> Dir ->
( Bool, BoardList )
next_board_list board pos dir =
let ( penguin_moved, updated_view_list ) =
step_list $ view_list board pos dir
in ( penguin_moved, update_board_from_view_list
board pos dir updated_view_list )
apply_view_list_to_row :: [ Tile ] -> Int -> Bool -> [ Tile ] -> [Tile]
apply_view_list_to_row orig pos True update =
take ( pos + 1 ) orig ++ update
apply_view_list_to_row orig pos False update =
( reverse update ) ++ ( drop pos orig )
apply_view_list_to_rows :: BoardList -> Int -> Int -> Bool -> [ Tile ]
-> BoardList
apply_view_list_to_rows orig row pos is_forward update =
take row orig ++
nest ( apply_view_list_to_row ( orig !! row ) pos
is_forward update ) ++
drop ( row + 1 ) orig
where nest xs = [xs]
update_board_from_view_list :: BoardList -> Pos -> Dir -> [ Tile ]
-> BoardList
update_board_from_view_list board pos dir updated_view_list
| is_eastwest = apply_view_list_to_rows board
( posY pos ) ( posX pos )
is_forward updated_view_list
| otherwise = transpose ( apply_view_list_to_rows ( transpose board )
( posX pos ) ( posY pos )
is_forward updated_view_list )
where is_forward = elem dir [ East, South ]
is_eastwest = elem dir [ East, West ]</pre>
<p>This code is on <a href="https://github.com/paulrpotts/arctic-slide-haskell">GitHub</a> here.</p>
<p>Now, it turns out that Jeff did more than suggest a refactoring -- he actually did something I haven't quite gotten my head around yet, which is to refactor my code to use a monad for managing some of this task. He forked my code in his own GitHub repo <a href="https://github.com/licquia/arctic-slide-haskell">here</a> and sent me some notes to share on my blog. Here's part of what he said:</p>
<blockquote>The way I got my head wrapped around monads was to think of them as "important stuff to do, but not the point". You need to do some housekeeping that's important, but it's not the reason you're writing this function.
The classic example is division. You're writing a math library, and you need to implement division. Division by zero is something you need to deal with sanely, but it's not the point; you're writing the function because you want to divide by things that aren't zero.
So, to handle the zero case, you return a Maybe instead of a simple number. Only now you can't just add numbers together with division, because you're dealing with Maybes, not numbers. So you end up implementing addition with Maybes, except that makes no sense, as adding never fails, and people using your math library get annoyed because now *they* have to deal with division-by-zero errors even when they're not dividing, and it's a mess.
Except -- Maybe is a monad. So you skip all that mess, implement division with a Maybe, everything else without, and use the cool monad and functor features of the language to bridge the gaps.
The same pattern exists with scorekeeping. A lot of the functions in your code need to keep track of the score and occasionally award points, but scores aren't "the point" of, say, collide. And when you start thinking about all the places you need to worry about scores, you start seeing scorekeeping infect all kinds of weird places in your code. I think you even mentioned having to "uglify" your code with scorekeeping in your blog post.</blockquote>
<p>Yes, yes, yes -- mainly the chain of function invocations that handle generating the next board, down to the <b>collide</b> calls. Because it's only at the point where a heart disappears that we can decrement the heart count. Without state, I can't make this a global state. In a purely function form, I have to "thread" the indication that the heart count should be decreased through the whole chain of function signatures, which now all have to return an extra thing.</p>
<blockquote>So, minimize the ugly with monads. Just do what you need to do to pass around the score, and deal with it when it's appropriate. (In my implementation, that was in next_world).
The Writer monad is perfect for the job. It uses a monoid, which is a fancy ways of saying "something that knows how to grow". Lists are monoids, because you can append to them. Numbers are monoids, because you can add and multiply them. And so on.
What the Writer monad does is take care of the adding part. You just return the thing you're working with, and the monad tacks it on using the monoid. Specifically, with scorekeeping, you just note how many points each individual action takes, and the monad does the adding together. When you finally deal with the score in next_world, you get all the accumulated points in one tidy variable.</blockquote>
<p>OK, cool... let's see what he came up with!</p>
<pre>import Control.Monad.Writer
...
-- Keep track of the score with a writer monad
type ScoreTracker = Writer ( Sum Int )</pre>
<p>OK, let me pause there and see if I can make sense of that. <i>Learn You a Haskell</i> <a href="http://learnyouahaskell.com/for-a-few-monads-more">says</a></p>
<blockquote>Whereas Maybe is for values with an added context of failure and the list is for non-deterministic values, the Writer monad is for values that have another value attached that acts as a sort of log value. Writer allows us to do computations while making sure that all the log values are combined into one log value that then gets attached to the result.</blockquote>
<p>OK, I think I get that -- in <i>Learn You</i> it is used for implementing logging, not scoring of a game, but it seems like it could be generalizable. The example given does this just kind of thing I was mentioning -- makes a simple function return a tuple to pass both the actual interesting return value and the log string, or in our case I think we want a score. <i>Learn You</i> continues:</p>
<blockquote>When we were exploring the Maybe monad, we made a function applyMaybe, which took a Maybe a value and a function of type a -> Maybe b and fed that Maybe a value into the function, even though the function takes a normal a instead of a Maybe a. It did this by minding the context that comes with Maybe a values, which is that they are values with possible failure. But inside the a -> Maybe b function, we were able to treat that value as just a normal value, because applyMaybe (which later became >>=) took care of checking if it was a Nothing or a Just value.
In the same vein, let's make a function that takes a value with an attached log, that is, an (a,String) value and a function of type a -> (b,String) and feeds that value into the function. We'll call it applyLog. But because an (a,String) value doesn't carry with it a context of possible failure, but rather a context of an additional log value, applyLog is going to make sure that the log of the original value isn't lost, but is joined together with the log of the value that results from the function.</blockquote>
<p>Oooh, again, that sounds very promising. So I'm convinced that <b>Writer</b> is the right abstraction here. The values that <b>Writer</b> gets are <b>Sum</b> and <b>Int</b> -- <b>Sum</b> is our monoid, <b>Int</b> is a type we're going to use to accumulate the updated score. (To go along with the Polar game logic, I think there really should ultimately be two scores -- one should be the heart count for a given board, which decrements, and gets tested against zero to indicate board completion, and the other should be a level, which increments as the player moves through the levels, but never mind that for now).</p>
<p>Jeff then came up with:</p>
<pre>noscore :: a -> ScoreTracker a
noscore x = writer (x, Sum 0)
score :: a -> ScoreTracker a
score x = writer (x, Sum 1)</pre>
<p>Two functions, <b>noscore</b> and <b>score</b>. I think these are both monadic <b>return</b> -- injecting a value, passing it to the next step while applying the sum operation. So let's see how he uses it. here's my <b>slide</b> function:</p>
<pre>slide :: [ Tile ] -> [ Tile ]
slide ( Ice_Block : ts ) | ( null ts ) || ( blocking $ head ts ) =
( Ice_Block : ts )
slide ( t : Empty : ts ) =
( Empty : ( slide ( t : ts ) ) )
slide ( t : ts ) | ( null ts ) || ( blocking $ head ts ) =
collide ( t : ts )</pre>
<p>I'm not going to take Jeff's current version, because he's restructured it a bit using guards, which obscures just the differences due to the use of the ScoreTracker, but here's a version that does the same thing. We don't have to explictly construct the return tuples:</p>
<pre>slide' :: [ Tile ] -> ScoreTracker [ Tile ]
slide' ( Ice_Block : ts ) | ( null ts ) || ( blocking $ head ts ) =
noscore ( Ice_Block : ts )
slide' ( t : Empty : ts ) =
noscore ( Empty : ( slide ( t : ts ) ) )
slide' ( t : ts ) | ( null ts ) || ( blocking $ head ts ) =
collide ( t : ts )</pre>
<p>And this doesn't actually compile. Note that collide doesn't handle the monad -- the compiler warns us as Jeff described:</p>
<pre> Couldn't match expected type `ScoreTracker [Tile]'
with actual type `[Tile]'
In the return type of a call of `collide'
In the expression: collide (t : ts)
In an equation for slide':
slide' (t : ts)
| (null ts) || (blocking $ head ts) = collide (t : ts)</pre>
<p>That seems pretty clear -- so I have to fix it up the same way:</p>
<pre>collide' :: [ Tile ] -> ScoreTracker [ Tile ]
collide' [] = noscore []
collide' ( t : ts ) | fixed t =
noscore ( t : ts )
collide' ( Bomb : Mountain : ts) =
noscore ( [ Empty, Empty ] ++ ts )
collide' ( Heart : House : ts ) = score ( [ Empty, House ] ++ ts )
collide' ( Ice_Block : ts ) | ( null ts ) || ( blocking $ head ts ) =
noscore ( Empty : ts )
collide' ( t : ts ) | ( movable t ) && ( ( null ts ) ||
( blocking $ head ts ) ) = noscore ( t : ts )
collide' ( t : Empty : ts ) | movable t =
noscore ( Empty : ( slide( t : ts ) ) )</pre>
<p>And slide' should call <b>collide'</b> instead of <b>collide</b>, of course. So once this is compiled and loaded into GHCI, we can play with it and compare it to the original <b>collide</b>:</p>
<pre>*Main> :t collide'
collide' :: [Tile] -> ScoreTracker [Tile]
*Main> :t collide
collide :: [Tile] -> [Tile]
*Main> collide [ Bomb, Mountain ]
[Empty,Empty]
*Main> collide [ Heart, House ]
[Empty,House]
*Main> collide' [ Heart, House ]
<interactive>:23:1:
No instance for (Show (ScoreTracker [Tile]))
arising from a use of `print'
Possible fix:
add an instance declaration for (Show (ScoreTracker [Tile]))
In a stmt of an interactive GHCi command: print it</pre>
<p>Er, yeah. The result is not printable, but can we see its type?
<pre>*Main> :t ( collide' [ Heart, House ] )
( collide' [ Heart, House ] ) :: ScoreTracker [Tile]</pre>
<p>In fact, we can. So there might be an easy way to make the monadic type printable -- <b>deriving ( Show )</b> doesn't work -- but first, how do we extract the values? Well, we get back the return value of the whole chain from <b>runWriter</b>:</p>
<pre>*Main> runWriter $ collide' [Heart, House]
([Empty,House],Sum {getSum = 1})</pre>
<p>What's the type? It's just a tuple:</p>
<pre>*Main> :t ( runWriter $ collide' [Heart, House] )
( runWriter $ collide' [Heart, House] ) :: ([Tile], Sum Int)
*Main> fst $ runWriter $ collide' [Heart, House]
[Empty,House]
*Main> snd $ runWriter $ collide' [Heart, House]
Sum {getSum = 1}</pre>
<p>Anyway, I think my mind is blown enough for today. I'm going to stop there. Jeff has made some other modifications to my code here and there -- modifications that improve the clarity -- but I'll have to get back to those. I'm off to read the monad tutorials again, and maybe understand them better this time!</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com3tag:blogger.com,1999:blog-21500237.post-74844657791045352992013-07-02T19:25:00.000-04:002013-07-03T02:35:41.814-04:00The Polar Game in Haskell, Day 5: Array v. List<p>So, a little more progress in learning me a Haskell: I've managed to implement the board using an immutable array. There's good news and bad news here. If you're an old hand at functional programming, you probably know all this and more, but I needed to do a little thinking on purely functional data structures. I have not really been satisfied with the amount of code necessary to manage my 2-D board in a list. I spent some time doodling some possible alternative implementation before concluding that purely functional data structures -- in which nodes are never mutated -- are hard. Anything I might be accustomed to doing with double or multiply-linked lists is pretty much a washout, since you can't ever share structure. In fact, I think one data structure I came up with might not be constructible at all without being able to mutate links between nodes. So I'm starting to understand why the tutorials all advise me to stick with lists.</p>
<p>Nevertheless, this is a small problem, and efficiency is not my biggest concern, at least not in the learning phase. I wanted to figure out how to use an immutable array. The tutorials have not been very satisfying. They seem to assume that anything this trivial is too trivial to demonstrate. But here's what I did.</p>
<p>First, the type of an array in Haskell encodes the number of dimensions and the node type, but not the size. You set that when you call the constructor. Here's a 2-D array type for my board:</p>
<pre>type BoardArray = Array ( Int, Int ) Tile</pre>
<p>I specified some bounds:</p>
<pre>max_row :: Int
max_row = 3
max_col :: Int
max_col = 23</pre>
<p>And I should point out one of the fundamental problems with using arrays: it's very easy to kill your program by exceeding the array bounds. There is a similar problem with <b>head</b>, but when writing functions with pattern-matching and guards there are pretty accepted conventions for dealing with empty lists. I suppose one could use guard patterns on all array accesses, but it starts to seem a little silly.</p>
<p>The next thing is that a given array works with some auxiliary types. The <b>//</b> operator takes an array and a list of tuples and builds a new array with updated content. The type of that list of tuples is this:</p>
<pre>type TileAssocList = [ ( ( Int, Int ), Tile ) ]</pre>
<p>For accessing multiple items in an array, the <b>range</b> method builds lists of indexing tuples. The syntax to range requires tuples of tuples, with the parentheses piling up, so I wrapped it up in a function:</p>
<pre>make_2d_range :: Int -> Int -> Int -> Int -> [ ( Int, Int ) ]
make_2d_range y0 x0 y1 x1 = range ( ( y0, x0 ), ( y1, x1 ) )</pre>
<p>So how does that work? It just iterates coordinates, permuting from higher indices to lower, like so:</p>
<pre>*Main> make_range 0 0 0 1
[(0,0),(0,1)]
*Main> make_range 0 0 1 3
[(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3)]</pre>
<p>For this problem domain, I need to know how reversed ranges work. For example, when the penguin is facing West, I want to build a range and a list of tiles in reverse index order. Can range do that for me?</p>
<pre>*Main> make_range 0 23 0 0
[]</pre>
<p>Ah... no. I guess that would have been too easy. So I'll have to account for those cases specially. Here's a function to get the penguin's view out of a 2-D array of tiles, in the form of a tile association list I can use to create a freshly created "modified" array (it's not really modified, but a new one is created with the updates from that list applied):</p>
<pre>view_array :: BoardArray -> Pos -> Dir -> TileAssocList
view_array board pos dir =
let row = ( posY pos )
col = ( posX pos )
coord_list = case dir of
East -> if ( col == max_col )
then []
else make_2d_range row ( col + 1 ) row max_col
South -> if ( row == max_row )
then []
else make_2d_range ( row + 1 ) col max_row col
West -> if ( col == 0 )
then []
else make_2d_range row 0 row ( col - 1 )
North -> if ( row == 0 )
then []
else make_2d_range 0 col ( row - 1 ) col
tile_assoc = zip coord_list ( map ( (!) board )
coord_list )
in case dir of
East -> tile_assoc
South -> tile_assoc
West -> reverse tile_assoc
North -> reverse tile_assoc</pre>
<p>That's not so bad. The key to this function is the <b>!</b> operator -- this gets a tuple and an array and returns an element -- and I zip the elements up with their coordinate tuples. Note that a lot of the bulk of this function is handling the edge cases, because we don't want to apply an out-of-range coordinate tuple to <b>!</b>. There may still be a shorter, clearer implementation possible. By comparison, here's a list-of-lists version factored a bit using currying to make it as self-documenting as I could get it -- note the use of <b>id</b> to let me return a general function as <b>orient</b>. I'm sure it doesn't impress FP whizzes, but I'm kinda proud of it -- I feel like I'm starting to use Haskell a little more idiomatically:</p>
<pre>view_list :: BoardList -> Pos -> Dir -> [Tile]
view_list board pos dir =
let row = ( posY pos )
col = ( posX pos )
transposed = elem dir [ South, North ]
reversed = elem dir [ West, North ]
orient | reversed = reverse
| otherwise = id
trim = case dir of
East -> drop ( col + 1 )
South -> drop ( row + 1 )
West -> take col
North -> take row
extract | transposed = ( transpose board ) !! col
| otherwise = board !! row
in orient $ trim $ extract</pre>
<p>Testing <b>view_list</b>:</p>
<pre>*Main> view_list init_board_list (Pos 0 0) East
[Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Tree,Empty,Empty,Empty,Empty,Empty,Ice_Block,Empty,Empty]
*Main> view_array init_board_array (Pos 0 0) East
[((0,1),Empty),((0,2),Empty),((0,3),Empty),((0,4),Empty),
((0,5),Empty),((0,6),Empty),((0,7),Empty),((0,8),Empty),
((0,9),Empty),((0,10),Empty),((0,11),Empty),((0,12),Empty),
((0,13),Empty),((0,14),Empty),((0,15),Tree),((0,16),Empty),
((0,17),Empty),((0,18),Empty),((0,19),Empty),((0,20),Empty),
((0,21),Ice_Block),((0,22),Empty),((0,23),Empty)]</pre>
<p>Now we can write <b>step</b>. Here's the list version I've presented before:</p>
<pre>step_list :: [Tile] -> ( Bool, [Tile] )
step_list [] = ( False, [] )
step_list ts = if walkable (head ts) then ( True, ts )
else ( False, collide ts )</pre>
<p>The array version is a little more complicated, because I want to strip the list I pass to <b>collide</b> down to just a list of tiles, in order to retain that clean logic for dealing with just a list of tiles. So I unzip my coordinate tuples from my tiles, get a potentially updated tile list, and zip it back together. That complicates it a bit, like so:</p>
<pre>step_array :: TileAssocList -> ( Bool, TileAssocList )
step_array [] = ( False, [] )
step_array tile_assoc = if ( walkable $ head tile_list )
then ( True, tile_assoc )
else ( False, zip coord_list
( collide tile_list ) )
where ( coord_list, tile_list ) = unzip tile_assoc</pre>
<p>I'm going to have to uglify my nice collide method a bit because I need to return at least one additional value -- indicating whether <b>collide</b> consumed a heart, so that we can keep score of the game.</p>
<p>Next up, you can see the array and list solutions start to diverge hugely. It's hard to merge the list-based board back together with the potentially updated tile list to create the next immutable list-based board. My original method was pretty hideous. With Jeff's refactoring it's still a lot of code. (Note: I don't have this completely working yet; I'm getting a run-time error about bad patterns I haven't quite figured out yet):</p>
<pre>next_board_list :: BoardList -> Pos -> Dir -> ( Bool, BoardList )
next_board_list board pos dir =
let ( penguin_could_move, updated_view_list ) =
step_list $ view_list board pos dir
in ( penguin_could_move, update_board_from_view_list
board pos dir updated_view_list )
apply_view_list_to_row :: [Tile] -> Int -> Bool -> [Tile] -> [Tile]
apply_view_list_to_row orig pos True update =
take ( pos + 1 ) orig ++ ( init update )
apply_view_to_row orig pos False update =
( reverse ( init update ) ) ++ ( drop pos orig )
apply_view_list_to_rows :: BoardList -> Int -> Int ->
Bool -> [Tile] -> BoardList
apply_view_list_to_rows orig row pos is_forward update =
take row orig ++
nest ( apply_view_to_row ( orig !! row ) pos is_forward update ) ++
drop ( row + 1 ) orig
update_board_from_view_list :: BoardList -> Pos -> Dir ->
[Tile] -> BoardList
update_board_from_view_list board pos dir updated_view_list
| is_eastwest = apply_view_list_to_rows board
( posY pos ) ( posX pos )
is_forward updated_view_list
| otherwise = transpose ( apply_view_list_to_rows ( transpose board )
( posX pos ) ( posY pos )
is_forward updated_view_list )
where is_forward = elem dir [ East, South ]
is_eastwest = elem dir [ East, West ]</pre>
<p>By comparison, the array is much more suited to create an updated version of itself, given a list of elements to update. This is handled by the <b>//</b> function, in this simple function to create the next board in array form, called from <b>step_array</b>:</p>
<pre>next_board_array :: BoardArray -> Pos -> Dir -> ( Bool, BoardArray )
next_board_array board pos dir =
let ( penguin_could_move, updated_view ) =
step_array $ view_array board pos dir
in ( penguin_could_move, board // updated_view )</pre>
<p>I like that -- it looks like we're working with the data structure rather than against it, although the overhead to manage the ranges and lists still feels to me more complicated than it should be. That complexity carries over elsewhere: for example, pretty-printing the array requires that range logic again. In fact I wind up just wrapping up and re-using the logic to pretty-print the list, so you can see how much additional code I needed:</p>
<pre>pretty_tiles :: [Tile] -> String
pretty_tiles [] = "\n"
pretty_tiles (t:ts) = case t of
Empty -> "___"
Mountain -> "mt "
House -> "ho "
Ice_Block -> "ic "
Heart -> "he "
Bomb -> "bo "
Tree -> "tr "
++ pretty_tiles ts
pretty_board_list :: BoardList -> String
pretty_board_list [] = ""
pretty_board_list (ts:tss) = pretty_tiles ts ++ pretty_board_list tss
split_tile_list :: [ Tile ] -> [ [ Tile ] ]
split_tile_list [] = []
split_tile_list ts = [ take tiles_in_row ts ] ++
( split_tile_list $ ( drop tiles_in_row ) ts )
where tiles_in_row = max_col + 1
pretty_board_array :: BoardArray -> String
pretty_board_array board = pretty_board_list split_tiles
where full_range = make_2d_range 0 0 max_row max_col
all_tiles = map ( (!) board ) full_range
split_tiles = split_tile_list all_tiles</pre>
<p>As an aside, it seems like there ought to be at least one standard list split function, but it looks like folks don't really agree on how it should work</p>
<p>So there it is -- the array is kind of a mixed blessing here. I haven't done any large-scale profiling on it, to determine if the need to generate a whole new array each pass is a big loss, compared to the potential structure-sharing in the list implementation. It simplifies some of the code dramatically, while adding a layer of dealing with ranges and lists of tuples everywhere -- as soon as we want to pull items out of the array, or merge them back in to a new array, we're dealing with lists again. Still, given the ugliness of the list merge code, it seems like the more natural choice for this kind of small game board data structure.</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com8tag:blogger.com,1999:blog-21500237.post-2855852854549178782013-06-29T15:03:00.002-04:002013-06-29T15:12:22.222-04:00The Polar Game in Haskell, Day 4 1/2: Folding a Penguin<p>So, just a quick update today. While I was cooking bacon this morning I looked at comments and tried to implement an idea I had last night. Roland suggested I could get rid of <b>Edge</b>. I had already been asking myself this. Using a special flag value for the edge-of-board case came from the Objective-C version where I wanted to avoid reading tiles outside the bounds of the board array. When using lists there is a built-in termination condition, so Edge is gone completely.</p>
<p>Roland also suggested a simplified next_ppos, like so:</p>
<pre>next_ppos :: Pos -> Dir -> Pos
next_ppos pos dir = Pos ( posY pos + fst step ) ( posX pos + snd step )
where step = delta dir
delta East = ( 0, 1 )
delta South = ( 1, 0 )
delta West = ( 0, -1 )
delta North = ( -1, 0 )</pre>
<p>So that's in there now. Thanks, Roland!</p>
<p>The next thing I wanted to do is get rid of that ugly test code with all the nested calls to next_world. I was re-reading <i>Learn You a Haskell</i> and it occurred to me that this sort of thing -- distilling a list -- is what <i>folds</i> are for. And then, a minute later, that I don't actually want to <i>fold</i> the worlds down to one final world -- I want to capture all the intermediate worlds as we process a list of moves. And that's what a <i>scan</i> is for. So we're conducting surveillance on the penguin as he goes about his business. GHCI tells me that the type of <b>scanl</b> is <b>(a -> b -> a) -> a -> [b] -> [a]</b>. So I'm calling it with a function that takes a <b>World</b> and a <b>Dir</b> and returns a <b>World</b>. That's the <b>(a -> b -> a)</b> part. Then it gets an initial <b>World</b>, that's the <b>a</b>, and a list of elements of type <b>Dir</b>, that's the <b>[b]</b>, and returns a list of elements of type <b>World</b>, that's <b>[a]</b>.</p>
<pre>moves_to_dirs :: [(Dir, Int)] -> [Dir]
moves_to_dirs [] = []
moves_to_dirs (m:ms) = replicate ( snd m ) ( fst m ) ++ moves_to_dirs ms
moves_board_1 = [(East,21),(South,2), (East,3),(North,2),(West,2)]
move_sequence :: [(Dir,Int)] -> [World]
move_sequence repeats = scanl next_world init_world steps
where steps = moves_to_dirs repeats
main :: IO ()
main = do
mapM_ putStrLn pretty_worlds
where worlds = move_sequence moves_board_1</pre>
<p>And that gives me the whole shebang, ending in:</p>
<pre>penguin @: Pos {posY = 0, posX = 22}, facing: West, hearts: 3
tr __________________________________________tr _______________ic ______
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________
penguin @: Pos {posY = 0, posX = 21}, facing: West, hearts: 3
tr __________________________________________tr ic _____________________
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________</pre>
<p>Oh, if you just want to see the final result, foldl will work here. Their types are identical, except that foldl returns a single <b>a</b> (in this case, a <b>World</b>) instead of a list of elements of type <b>World</b>. So a function to make use of that just returns a single <b>World</b>, but everything else is the same. Like so:</p>
<pre>move_sequence' :: [(Dir,Int)] -> World
move_sequence' repeats = foldl next_world init_world steps
where steps = moves_to_dirs repeats</pre>
<p>And then I can display both:</p>
<pre>main :: IO ()
main = do
mapM_ putStrLn pretty_worlds
putStrLn pretty_final_world
where worlds = move_sequence moves_board_1
final_world = move_sequence' moves_board_1
pretty_worlds = map pretty_world worlds</pre>
<p>I like it -- examples of fold and scan that are a little more complex than the usual textbook examples. Personally I'd rather read more of those and less about how we can implement some simple math operation that can be trivially implemented in a dozen other, more readable ways.</p>
<p>Oh, and it's not thoroughly tested or finished by any means, but if you'd like to play with this code, it's on github now: <a href="https://github.com/paulrpotts/arctic-slide-haskell">https://github.com/paulrpotts/arctic-slide-haskell</a>. Comments are welcome as always.</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com3tag:blogger.com,1999:blog-21500237.post-6603684213994369382013-06-28T16:07:00.003-04:002013-06-28T16:07:51.863-04:00The Polar Game in Haskell, Day 4<p>OK, things are getting meaty: I've made some minor modifications to <b>World</b>:</p>
<pre>data World = World { wBoard :: Board, wPenguinPos :: Pos,
wPenguinDir :: Dir, wHeartCount :: Int }
deriving (Show)</pre>
<p>This extracts the sequence of tiles in front of the penguin, for various directions, from a nested list representation of the board:</p>
<pre>view :: Board -> Pos -> Dir -> [Tile]
view board pos East = ( drop ( posX pos + 1 ) $
board !! ( posY pos ) ) ++ [Edge]
view board pos South = ( drop ( posY pos + 1 ) $
( transpose board ) !! ( posX pos ) ) ++ [Edge]
view board pos West = ( reverse $ take ( posX pos ) $
board !! ( posY pos ) ) ++ [Edge]
view board pos North = ( reverse $ take ( posY pos ) $
( transpose board ) !! ( posX pos ) ) ++ [Edge]</pre>
<p>I have fleshed out slide and collide after some testing; I haven't tested all my known cases yet. Maybe tomorrow. Here is how I create the initial world:</p>
<pre>init_world :: World
init_world = ( World init_board ( Pos 0 0 ) South 3 )</pre>
<p>South because in the south-facing representation, the penguin's face is visible (although of course I don't have a GUI yet).</p>
<p>A little utility function for clarity:</p>
<pre>nest :: [a] -> [[a]]
nest xs = [xs]</pre>
<p>And now, deep breath, the logic to build the next board out of the current board combined with a replaced list of tiles that may have been changed due to object interaction. It gets pretty ugly here when we're undoing the appending of Edge with init, and undoing the reversing that view has done when looking North and West, and working with the transposed board for North and South. There are some extra line breaks in there that are not in the working code. I have an issue with my <b>let</b> clauses not compiling correctly if I break the lines. I'm sure there's a prettier workaround, and I will look that up, but after going down a rabbit hole of Haskell syntax, I have timed out for today and right now I'm just happy it runs:</p>
<pre>next_board :: Board -> Pos -> Dir -> ( Bool, Board )
next_board board pos East =
let ( penguin_could_move, updated_view ) =
step $ view board pos East
in (
penguin_could_move,
take ( posY pos ) board ++
nest (
( take ( posX pos + 1 )
( board !! ( posY pos ) ) ) ++
( init updated_view ) ) ++
drop ( posY pos + 1 ) board )
next_board board pos South =
let ( penguin_could_move, updated_view ) =
step $ view board pos South
in (
penguin_could_move,
transpose (
take ( posX pos ) ( transpose board ) ++
nest (
( take ( posY pos + 1 )
( ( transpose board ) !! ( posX pos ) ) ) ++
( init updated_view ) ) ++
drop ( posX pos + 1 ) ( transpose board ) ) )
next_board board pos West =
let ( penguin_could_move, updated_view ) =
step $ view board pos West
in (
penguin_could_move,
take ( posY pos ) board ++
nest (
( reverse ( init updated_view ) ) ++
( drop ( posX pos )
( board !! ( posY pos ) ) ) ) ++
drop ( posY pos + 1 ) board )
next_board board pos North =
let ( penguin_could_move, updated_view ) =
step $ view board pos North
in (
penguin_could_move,
transpose (
take ( posX pos ) ( transpose board ) ++
nest (
( reverse ( init updated_view ) ) ++
( drop ( posY pos )
( ( transpose board ) !! ( posX pos ) ) ) ) ++
drop ( posX pos + 1 ) ( transpose board ) ) )</pre>
<p>That... seems like way too much code, and I would like to kill it in favor of using a real array type -- soon. The tutorials were pretty insistent that I try to use lists. I'm pretty sure this is not what they meant. I will say that I was really impressed, writing this, how much of it worked the first time, as soon as I got it past the compiler. But that doesn't necessarily mean this is the best possible design for this code.</p>
<p>Anyway, updating penguin pos:</p>
<pre>next_ppos :: Pos -> Dir -> Pos
next_ppos pos East = ( Pos ( posY pos ) ( posX pos + 1 ) )
next_ppos pos South = ( Pos ( posY pos + 1 ) ( posX pos ) )
next_ppos pos West = ( Pos ( posY pos ) ( posX pos - 1 ) )
next_ppos pos North = ( Pos ( posY pos - 1 ) ( posX pos ) )</pre>
<p>And, updating the world. I had a similar problem with the line-broken <b>let</b> clause here:</p>
<pre>next_world :: World -> Dir-> World
next_world old_world move_dir =
let ( can_move, board ) = next_board ( wBoard old_world )
( wPenguinPos old_world ) ( wPenguinDir old_world )
in
if ( move_dir /= wPenguinDir old_world )
then ( World ( wBoard old_world ) ( wPenguinPos old_world )
move_dir ( wHeartCount old_world ) )
else ( World board
( next_ppos ( wPenguinPos old_world )
( wPenguinDir old_world ) )
( wPenguinDir old_world )
( wHeartCount old_world ) )</pre>
<p>Now, some pretty-printing, since it gets pretty tedious to visualize the board from reading the dumped-out list in GHCI:</p>
<pre>pretty_tiles :: [Tile] -> String
pretty_tiles [] = "\n"
pretty_tiles (t:ts) = case t of
Empty -> "___ "
Mountain -> "mtn "
House -> "hou "
Ice_Block -> "ice "
Heart -> "hea "
Bomb -> "bom "
Tree -> "tre "
Edge -> "### "
++ pretty_tiles ts
pretty_board :: Board -> String
pretty_board [] = ""
pretty_board (ts:tss) = pretty_tiles ts ++ pretty_board tss
pretty_world :: World -> String
pretty_world world =
"penguin @: " ++ show ( wPenguinPos world ) ++
", facing: " ++ show ( wPenguinDir world ) ++
", hearts: " ++ show ( wHeartCount world ) ++
"\n" ++ pretty_board ( wBoard world )</pre>
<p>And here's where the rubber meets the road -- or, rather, fails to. I need state, at least simulated state. I messed with state monads for a while but I'm not quite ready. I will tackle that another day. I messed with trying to capture a list in a closure and append a series of successive worlds to it but while that would work fine in Scheme, Lisp, or Dylan I realized that in Haskell I was just fighting the entire language design. So I gave in and did this stupid thing for now, just so I could see my world updating and start to validate that all the tile interactions on the board work:</p>
<pre>main :: IO ()
main = do
putStrLn "ArcticSlide start"
let world0 = init_world
putStrLn $ pretty_world world0
-- 21 East
let world5 = next_world ( next_world ( next_world ( next_world (
next_world world0 East ) East ) East ) East ) East
let world10 = next_world ( next_world ( next_world ( next_world (
next_world world5 East ) East ) East ) East ) East
let world15 = next_world ( next_world ( next_world ( next_world (
next_world world10 East ) East ) East ) East ) East
let world20 = next_world ( next_world ( next_world ( next_world (
next_world world15 East ) East ) East ) East ) East
let world21 = next_world world20 East
putStrLn $ pretty_world world21
-- 2 South
let world23 = next_world ( next_world world21 South ) South
putStrLn $ pretty_world world23
-- 3 East
let world26 = next_world ( next_world (
next_world world23 East ) East ) East
putStrLn $ pretty_world world26
-- 2 North
let world28 = next_world ( next_world world26 North ) North
putStrLn $ pretty_world world28
-- 2 West
let world30 = next_world ( next_world world28 West ) West
putStrLn $ pretty_world world30</pre>
<p>That is far from what I'd like to be doing eventually with managing game moves, and I still haven't put in any handling for the heart count, but it works:</p>
<pre>ArcticSlide start
penguin @: Pos {posY = 0, posX = 0}, facing: South, hearts: 3
tr __________________________________________tr _______________ic ______
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________
...
penguin @: Pos {posY = 0, posX = 22}, facing: North, hearts: 3
tr __________________________________________tr _______________ic ______
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________
penguin @: Pos {posY = 0, posX = 21}, facing: West, hearts: 3
tr __________________________________________tr ic _____________________
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________
</pre>
<p>Aaaand... the penguin has pushed the ice block in the upper right to the west, and it has slid west and become blocked by the tree. That's... good, right? My brain is a little fried. All that to update a game board. I need a break, and maybe a stiff drink. I'm going to have to fortify myself before I successfully tackle the state monad. But I am determined!</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com3tag:blogger.com,1999:blog-21500237.post-10445685640395706142013-06-27T21:12:00.000-04:002013-06-29T22:48:02.432-04:00The Polar Game in Haskell, Day 3<p>More phone interviews, more coding. On my laptop, amidst a gaggle of fighting children, during a thunderstorm, with our basement flooding, with the kind assistance of some friendly commentors, a little more progress. Let's change <b>Pos</b></p>
<pre>data Pos = Pos { posY :: Int, posX :: Int }
deriving (Show, Eq)</pre>
<p>And define a game world:</p>
<pre>data World = World { board :: Board, penguinPos :: Pos,
penguinDir :: Dir,
heartCount :: Int } deriving (Show)</pre>
<p>It was painful, took an embarrassingly long time, and this can't possibly be how I want to keep it indefinitely, but I finished <b>slice</b> which treats a list of lists of tiles like a 2-dimensional array and gives us what the penguin sees before him, looking in a given direction:</p>
<pre>slice :: Board -> Pos -> Dir -> [Tile]
slice board pos East = ( drop ( posX pos ) $
board !! ( posY pos ) ) ++ [Edge]
slice board pos South = ( drop ( posY pos ) $
( transpose board ) !! ( posX pos ) ) ++ [Edge]
slice board pos West = ( reverse $ take ( posX pos + 1 ) $
board !! ( posY pos ) ) ++ [Edge]
slice board pos North = ( reverse $ take ( posY pos + 1 ) $
( transpose board ) !! ( posX pos ) ) ++ [Edge]</pre>
<p>Let's just leave that as it is for now and use it, with the intent of replacing it with a real array of some sort later on. I still have to figure out how to merge a modified penguin track with an unmodified board to create the next state of the entire board... that's not going to be pretty, but it's doable.</p>
<p>So, one of the things I really love about Haskell is that once you get these pieces, they really do start come together nicely. Let's go ahead and define the first board. I could make it from the strings or a run-length encoding or something, but for now let's just bite the bullet and build the list the hard way:</p>
<pre>get_initial_board :: [[Tile]]
get_initial_board = [[Tree,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Tree,Empty,Empty,
Empty,Empty,Empty,Ice_Block,Empty,Empty],
[Tree,Empty,Bomb,Empty,Mountain,Empty,
Heart,Ice_Block,Heart,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,
Tree,Empty,Empty,Tree,Empty,Empty],
[Tree,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Heart,Empty,
Empty,Empty,Mountain,House,Empty,Empty],
[Tree,Tree,Empty,Empty,Empty,Empty,
Tree,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty]]
penguin_view :: Board -> Pos -> Dir -> [Tile]
penguin_view board pos dir = drop 1 $ slice board pos dir</pre>
<p>So now we can actually start doing stuff with this. Here's what's in front of the penguin when he looks at the board from different points, in different directions:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s1600/level_1_blown_up.tiff" imageanchor="1"><img border="0" height="120" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s640/level_1_blown_up.tiff" width="512" /></a>
<pre>*Main> penguin_view get_initial_board (Pos 0 0) East
[Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Tree,Empty,Empty,Empty,Empty,
Empty,Ice_Block,Empty,Empty,Edge]
*Main> penguin_view get_initial_board (Pos 0 0) South
[Tree,Tree,Tree,Edge]
*Main> penguin_view get_initial_board (Pos 0 0) West
[Edge]
*Main> penguin_view get_initial_board (Pos 0 0) North
[Edge]
*Main> penguin_view get_initial_board (Pos 3 21) North
[House,Tree,Ice_Block,Edge]</pre>
<p>Fun! Tomorrow, if I can manage it... an updated world.</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-59170166501406702632013-06-26T16:59:00.000-04:002013-06-26T17:22:19.895-04:00The Polar Game in Haskell, Day 2<p>Another short day since I had several phone interviews. Thanks to the folks who left comments!</p>
<p>I got a little further today; I feel like I'm starting to understand Haskell's data handling a little bit better. It's a cliché but I think the hard part is un-learning, and understanding what something like this <i>doesn't</i> do. So here's where it stands now -- not finished by any means, but coming along, with painful slowness as I continue to learn:</p>
<pre>data Dir = North | East | South | West
deriving (Show, Eq)
data Pos y x = Pos Int Int
deriving (Show, Eq)
-- N.B.: capitalization of initial letters in posY, posX is
-- semantically important!
posY ( Pos y x ) = y
posX ( Pos y x ) = x
data Tile = Empty | Tree | Mountain | House | Ice_Block |
Bomb | Heart | Edge deriving (Show, Eq)
-- Different types of tiles have different properties in
-- different interaction contexts:
-- The penguin can walk through empty tiles or trees (forest)
walkable :: Tile -> Bool
walkable t = ( t == Empty ) || ( t == Tree )
-- But everything except empty tiles will block sliding objects
blocking :: Tile -> Bool
blocking t = ( t /= Empty )
-- A subset of tiles are movable (and will slide until blocked)
movable :: Tile -> Bool
movable t = ( t == Bomb ) || ( t == Heart ) || ( t == Ice_Block )
-- A subset of tiles aren't movable; note that this set
-- overlaps blocking and that Tree is both walkable and fixed
fixed :: Tile -> Bool
fixed t = ( t == House ) || ( t == Mountain ) || ( t == Edge )</pre>
<p>That all should be fairly non-controversial, I think. The predicate approach to classifying tiles in different contexts may actually make more sense in Haskell, given that I can then use these predicates as guards. The replacement for a simple struct, <b>Pos</b>, still feels awkward -- I haven't really dug into whether it could be improved with record syntax, or some other technique. For now it's there because it works.</p>
<p>All the beginner tutorials say "don't use arrays, don't use arrays, don't use arrays!" At least not until I reach the stage where I need to optimize the implementation. So I'll try that. Let's try a list, and I'll extract "slices" from it, lists starting at a given <b>Pos</b> going in one of four different directions. Eventually I want the slice function to terminate the slices with <b>Edge</b> tiles that aren't actually stored in the list. So... I have to think about this some more, but here's a single case, sort of taken care of:</p>
<pre>type Board = [[Tile]]
slice :: Board -> Pos y x -> Dir -> [Tile]
slice board pos East = drop ( posX pos )
$ head $ drop ( posY pos ) board
slice _ _ _ = error "slice: not handled yet!"</pre>
<p>I don't have <b>slide</b> finished, but here's a version of collide that works, at least a little:</p>
<pre>collide :: [Tile] -> [Tile]
collide (t:(Empty:ts)) | movable t =
[Empty] ++ collide (t:ts)
collide (Bomb:(Mountain:ts)) = [Empty, Empty] ++ ts
collide (Heart:House:ts) = [Empty, House] ++ ts
collide (_) = error "collide: unexpected case!"</pre>
<p>The nested pattern <b>(Bomb:(Mountain:ts))</b> was sort of a flash of inspiration -- but it appears that maybe both this version and the <b>(Heart:House:ts)</b> version work the same -- I think -- so perhaps it's kind of pointless. It seemed to go along with the "destructure it the way you would structure it" idea, although I would normally not build a list out of cons cells unless it was irregular in some way.</p>
<p>Here's the penguin step function, returning True if the penguin can move onto the tile at the head of the list:</p>
<pre>step :: [Tile] -> ( Bool, [Tile] )
step [] = error "step: empty list!"
step ts = if walkable (head ts) then ( True, ts )
else ( False, collide ts )</pre>
<p>And there's a move, which "absorbs" the case where the penguin is turned to face a different direction. It's not really done; the idea is that it will give back the board, basically generating a new world. For now we kind of punt on the question of how to rebuild the board out of the existing board and the modified "slice" -- and so the I just return a list as the first element of the tuple. In the first case where the penguin hasn't moved, that doesn't actually make sense, but it satisfies GHC for now (wow, she's kind of a harsh mistress, but you've got to love those thigh-high black leather boots!)</p>
<pre>move :: Board -> Pos y x -> Dir -> Dir ->
( [Tile], Pos y x, Dir, Dir )
move board pos move_dir penguin_dir =
if move_dir /= penguin_dir
then ( head board, pos, move_dir, move_dir )
else ( collide $ slice board (Pos 1 0) penguin_dir,
pos, penguin_dir, penguin_dir )
</pre>
<p>Boy, that's tuple-icious... not sure I like it, but it's a start. So:</p>
<pre>*Main> walkable Tree
True
*Main> :t Pos
Pos :: Int -> Int -> Pos y x
*Main> let slice = [Heart, House]
*Main> collide slice
[Empty,House]
*Main> let slice = [Bomb, Empty, Mountain]
*Main> collide slice
[Empty,House]
*Main> let board = [[Empty, Tree, Empty, Edge],
[Bomb, Empty, Mountain, Edge]]
*Main> move board (Pos 1 0) West East
([Empty,Tree,Empty,Edge],Pos 1 0,West,West)
*Main> move board (Pos 1 0) East East
([Empty,Empty,Empty,Edge],Pos 1 0,East,East)</pre>
<p>More tomorrow if I can manage it! Oh, and it's here, such as it is: <a href="https://github.com/paulrpotts/arctic-slide-haskell">https://github.com/paulrpotts/arctic-slide-haskell</a></p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com9tag:blogger.com,1999:blog-21500237.post-75269657784145820002013-06-25T20:24:00.000-04:002013-06-25T20:26:21.980-04:00The Polar Game in Haskell, Day 1<p>So if you've been following recent posts, you know I've been messing with the logic for a simple sliding-tile game. In my last post I took some designs refined via a side trip into Dylan and brought them back into Objective-C, making them a little more idiomatic by pruning my tile classes that didn't hold their weight, and compensating for Objective-C's very limited method dispatch options.</p>
<p>But in addition to learning Objective-C, and Apple's APIs for writing an app, I'm also trying to further my knowledge of Haskell, which is somewhere just beyond "utter newbie." So I'm going to try to implement the game logic in Haskell, too. Since the game is decidedly stateful, there is a certain impedance mismatch here, at least with respect to the early chapters in most of the tutorials and guides. But I'm told that Haskell also makes a great imperative programming language, so let's give it a shot. And along the way I can try to mold my understanding of stateful versus imperative a little more.</p>
<p>For day one, which was a shorter-than-usual day, I did not get into the state monad or how to model mutation of a 2-D array yet. I wanted to consider whether I could model the tile classes the way I could in Dylan, and do something useful in them. It occurred to me that each move of the penguin, and all the subsequent actions including possibly pushing an object, possibly a collision, possibly an object sliding frictionlessly as long as it can and then another collision, actually takes place in a 1-dimensional vector, not a 2-dimensional array. So it might be interesting to handle a penguin move by extracting a vector (in the form of a list) from the array, and replacing it with an updated list.
<p>I haven't worked that all out yet but here is the bare beginning of my experimentation. There's a way to represent tiles:</p>
<pre>data Tile = Empty | Tree | Mountain | House | Ice_Block |
Bomb | Heart | Edge
deriving (Show)</pre>
<p>Part of the confusion of learning Haskell is that, semantically, this isn't quite the equivalent of a set of enumerations, or of a set of class declarations. From what I can tell, this is more like a list of singleton factories -- constructors, where I've also derived them from Show, sort of the equivalent of mixing in a base class. But this is all an approximation, and Haskell is <i>quite</i> different than the other languages I'm most familiar with.</p>
<p>My next thought was that I wanted to be able to declare "base classes" so that, for example, I could have a Walkable class that comprised Empty and Tree. In Dylan I would do this by using classes, but there is different way: declaring a <b>type-union</b> of singletons. I think that this Haskell solution is more like the <b>type-union</b>. I looked in vain for an explicit type union. Instead I found <b>class</b> (which, in Haskell, does not correspond to a class in the sense that I'm used to, of a template for a run-time object that consists of data members and methods to operate on it, but a <i>typeclass</i>, something I clearly need to study more):
<pre>class Walkable a where
walkable :: a -> Bool</pre>
<p>And then this: which boils down to, I think, a function to determine whether a Tile is an instance of a Walkable typeclass:</p>
<pre>instance Walkable Tile where
walkable Empty = True
walkable Tree = True
walkable _ = False</pre>
<p>Now I can write something like this (just a vague thought-in-progress at the moment):</p>
<pre>slide :: [Tile] -> [Tile]
slide [] = error "slide empty list!"
slide (t) = error "single item list!"
slide (Empty:ts) = ts ++ slide ts
collide :: [Tile] -> [Tile]
collide [] = error "traverse empty list!"
collide [Edge] = [Edge]
collide (Empty:ts) = ts
collide (Bomb:Mountain:ts) = [Empty, Empty] ++ ts
collide (Heart:House:ts) = [Empty, House] ++ ts
step :: [Tile] -> Bool
step [] = error "step: empty list!"
step (t:_) = if walkable t then True else False</pre>
<p>Then after sticking in a dummy main I can load this into GHCI and interact with it a little:</p>
<pre>*Main> :t Tree
Tree :: Tile
*Main> step [Mountain, Empty, Empty, Tree, Edge]
False
*Main> step [Tree, Empty, Empty, Tree, Edge]
True
*Main> collide [Heart, Mountain]
*** Exception: arctic-slide.hs:(22,1)-(26,47): Non-exhaustive patterns in function collide
(Um, yeah, OK, I have work to do there)
*Main> collide [Heart, House]
[Empty,House]
*Main> slide [Empty, Empty, Empty, Empty, Mountain]
*** Exception: single item list!</pre>
<p>Anyway, that's not exactly what I want to do -- really, I want the functions to actually return a new list of the same length, so I'll have to build it up as I recurse down the list -- maybe in the List monad? But it's a start on the whole basic concept of matching on the "types" of my tiles in a "vector," such as it is. That whole bit with <b>walkable</b> -- which I admit I don't quite understand yet -- seems like far too much conditional logic when I really just want to pattern-match on a type union of Tile. In other words, I want to write something like this (not valid Haskell):</p>
<pre>union Walkable = Empty | Tree
step (Walkable:_) = True</pre>
<p>That's a small example, but I have several other type union classes I need to use to categorize the tiles, so I have an incentive to make that as clear and simple as possible. It seems like I'm still fighting with Haskell's idioms here. Clearly, as they say, more research is needed...</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com5tag:blogger.com,1999:blog-21500237.post-82819175031802293562013-06-24T18:53:00.000-04:002013-06-24T20:32:54.398-04:00Objective-C, Day 6 (Back from Dylan-land)<p>I've been a little sick -- maybe something in our water, because our tap water started tasting like hose water -- but it seems to be clearing up. There's nothing like having flu-like symptoms to celebrate the first couple of days of summer! But I'm more-or-less back on my feet, although still a little queasy. Yesterday the weather station closest to our home in Saginaw hit 93, "feels like 100" with the humidity. I know that's nothing compared to some of the folks out west, but it came on us pretty fast, and I'd happily trade 100 in the low-humidity desert for 90 in Saginaw. I've got the A/C unit set up in the home office, since we finally need it, and I'm pressing on with my re-engineering of the old Mac Polar game.</p>
<p>The Dylan implementation I discussed last time helped focus my thinking about, if not the optimal, at least a fairly clear model for implementing game piece behavior. It also clarified what I should do with game objects in Objective-C, and that is "nothing." The "model" class still deserves to live, but the tile pieces just don't derive any benefit from being classes. The two main reasons are (1) Objective-C doesn't really support static methods in the sense that C++ does, and (2) Objective-C's dispatch mechanism isn't sophisticated enough to help us significantly save on "code to find code." So the tiles will be represented by plain old data, and we'll dispatch on their "types" with plain old logic.</p>
<p>The Dylan code has a small infrastructure of helper functions for accessing, filling, and logging the board state. I won't include all of it, because most of what it does is pretty clear from the function name, but there are functions like this:</p>
<pre>define method getTileAtPos( model :: <model>, pos :: <pos-or-false> ) =>
( tile :: <tile> )
if ( pos )
getTileAtXY( model, pos.y-idx, pos.x-idx );
else
$the-edge;
end if;
end;
define function getAdjacentPos( pos :: <pos>, dir :: <dir> )
=> ( pos-or-false :: <pos-or-false> )
let y-offset :: <integer> = 0;
let x-offset :: <integer> = 0;
if ( dir == #"east" )
x-offset := 1;
elseif ( dir == #"south" )
y-offset := 1;
elseif ( dir == #"west" )
x-offset := -1;
elseif ( dir == #"north" )
y-offset := -1;
end if;
let new-y-idx :: <integer> = pos.y-idx + y-offset;
let new-x-idx :: <integer> = pos.x-idx + x-offset;
if ( ( ( new-y-idx >= 0 ) & ( new-y-idx < $board-dim-y ) ) &
( ( new-x-idx >= 0 ) & ( new-x-idx < $board-dim-x ) ) )
make( <pos>, y-idx: new-y-idx, x-idx: new-x-idx );
else
#f
end if;
end;
define method penguinPush( model :: <model> )
=> ( result :: <boolean> )
let target-pos :: <pos-or-false> =
getAdjacentPos( model.penguin-pos, model.penguin-dir );
let target-tile = getTileAtPos( model, target-pos );
pushTile( model, model.penguin-dir, target-pos, target-tile );
end;
define method penguinMove( model :: <model>, dir :: <dir> )
if ( model.penguin-dir ~= dir )
model.penguin-dir := dir;
format-out( "Penguin changed dir to %S\n", dir );
force-output( *standard-output* );
else
if ( penguinPush( model ) )
format-out ( "Penguin moved to %d, %d\n",
model.penguin-pos.y-idx, model.penguin-pos.x-idx );
force-output( *standard-output* );
end if;
if ( model.heart-count == 0 )
format-out( "Heart count reached zero, level cleared!\n" );
force-output( *standard-output* );
end if;
end if;
end;
define method penguinMoveTimes( model :: <model>, dir :: <dir>,
times :: <integer> )
for ( count from 1 to times )
penguinMove( model, dir );
end for;
end;
define method describe-tile( tile :: <tile> ) => ( str :: <string> )
case
( tile == $the-empty ) => "___ ";
( tile == $the-tree ) => "tre ";
( tile == $the-mountain ) => "mtn ";
( tile == $the-house ) => "hou ";
( tile == $the-ice-block ) => "ice ";
( tile == $the-heart ) => "hea ";
( tile == $the-bomb ) => "bom ";
otherwise => "??? ";
end case;
end method;
define method describe-board( model :: <model> )
for ( y-idx from 0 below $board-dim-y )
for ( x-idx from 0 below $board-dim-x )
format-out( "%S",
describe-tile( model.board[ y-idx, x-idx ] ) );
end for;
format-out( "\n" );
end for;
force-output( *standard-output* );
end;</pre>
<p>In Objective-C, I'm going to get rid of the singletons and tile classes altogether. They will live on in the comments, to clarify what the pseudo-object-dispatch is doing, and vestigially in the code. The board will have the same internal representation as the raw strings of data taken from the original Polar game resources. I'll keep my three main methods from the Dylan code -- pushing a tile, colliding, and sliding -- but these will be single Objective-C methods rather than multi-methods. The tiles are just chars:</p>
<pre>#define POLAR_DATA_LEN_Y 4 // 4x24 grid
#define POLAR_DATA_LEN_X 24
#define POLAR_DATA_NUM_LEVELS 6 // In the original game
typedef char tile_t;
enum {
polar_tile_empty = '0',
polar_tile_tree,
polar_tile_mountain,
polar_tile_house,
polar_tile_ice_block,
polar_tile_heart,
polar_tile_bomb,
polar_tile_last = polar_tile_bomb
};
/*
Not part of the level data; an extra flag value representing
edge of board
*/
#define polar_tile_edge 'X'
typedef const char polar_level_array_t[POLAR_DATA_NUM_LEVELS]
[POLAR_DATA_LEN_Y]
[POLAR_DATA_LEN_X];
typedef char polar_board_array_t[POLAR_DATA_LEN_Y]
[POLAR_DATA_LEN_X];
extern polar_level_array_t polar_levels;</pre>
<p>Why use <b>#define</b> for array indices and our tile pieces instead of <b>const int</b> and <b>const char?</b> Because using a const integral variable (yeah... a "const variable...") to dimension an array, or represent a case value for a switch statement, is <a href="http://stackoverflow.com/questions/3988122/static-const-int-not-good-enough-for-array-size">still not standard C</a> everywhere, although it is a common extension to allow the compiler to treat it as so in contexts like this. Enum works fine with characters. Oddly, I have a build issue when using enum values to define the array boundaries. I haven't figured out quite what that is all about -- I think it may be a Clang bug. But I'll worry about that later.</p>
<p>In the implementation file:</p>
<pre>polar_level_array_t polar_levels =
{
{
"100000000000000100000400"
"106020545000000000100100"
"100000000000000050002300"
"110000100000000000000000"
},
// Etc., for the other five levels
}</pre>
<p>The model class gets one as a member:</p>
<pre>@interface ArcticSlideModel : NSObject
{
polar_level_array_t board;
pos_t penguinPos;
dir_e penguinDir;
int heartCount;
}</pre>
<p>We'll work ourselves down from the external API to the associated implementation:</p>
<pre>
// The external API
- (void)penguinMoveDue:(dir_e)dir;
- (void)penguinMoveNTimes:(int)n
due:(dir_e)dir;</pre>
<p><b>penguinMoveNTimes:due:</b> calls <b>penguinMoveDue:</b> which calls <b>penguinPushDue:</b>. In Dylan:</p>
<pre>define method penguinPush( model :: <model> )
=> ( result :: <boolean> )
let target-pos :: <pos-or-false> =
getAdjacentPos( model.penguin-pos, model.penguin-dir );
let target-tile = getTileAtPos( model, target-pos );
pushTile( model, model.penguin-dir, target-pos, target-tile );
end;</pre>
<p>That's not strictly translatable to C, since we're taking advantage of a <b>type-union</b> to retrieve the position or <b>#f</b> with <b>getAdjacentPos</b>. This usage extends to the lower levels of the implementation, though, so for now we're going to continue to allow getAdjacentPos to return position values that are invalid, and explicitly check for them so we don't read or write at non-existent array indices.</p>
<pre>pos_t getAdjacentPos( pos_t original_pos, dir_e dir )
{
pos_t updated_pos = original_pos;
int y_offset = 0;
int x_offset = 0;
switch ( dir )
{
case dir_east:
x_offset = 1;
break;
case dir_south:
y_offset = 1;
break;
case dir_west:
x_offset = -1;
break;
case dir_north:
y_offset = -1;
break;
default:
NSLog( @"getAdjacentPos: invalid dir %d", dir );
}
updated_pos.y_idx += y_offset;
updated_pos.x_idx += x_offset;;
return updated_pos;
}</pre>
<p>We rely on posValid to explicitly check for invalid tile cases:</p>
<pre>BOOL posValid( pos_t pos )
{
return ( ( ( pos.y_idx >= 0 ) &&
( pos.y_idx < POLAR_DATA_LEN_Y ) ) &&
( ( pos.x_idx >= 0 ) &&
( pos.x_idx < POLAR_DATA_LEN_X ) ) );
}</pre>
<p>That should be pretty non-controversial. Note that BOOL in Objective-C is not a real type; it's just a #define and a typedef based on char_t. So don't get a <a href="http://blog.bignerdranch.com/564-bools-sharp-corners/">false sense of security</a> -- it has the same problems that fake bool types always have, and always will have, in straight C.</p>
<p>Anyway, we can now implement our pushTile function. Here is the Dylan:</p>
<pre>
define generic pushTile( model :: <model>, dir :: <dir>,
pos :: <pos-or-false>, target-tile :: <tile> );
// Handle walkable (empty or tree tile). The penguin
// is allowed to move onto this tile (indicated by
// returning #t).
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos>, target-tile :: <walkable> )
=> ( result :: <boolean> )
model.penguin-pos := target-pos;
#t;
end;
// Handle movable (bomb, heart, ice block) -- call
// collide which specializes in various combinations.
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos>, target-tile :: <movable> )
=> ( result :: <boolean> )
let next-pos :: <pos-or-false> =
getAdjacentPos( target-pos, dir );
let next-tile = getTileAtPos ( model, next-pos );
collide( model, dir, target-pos, target-tile,
next-pos, next-tile );
#f;
end;
// Handle fixed (house, mountain, edge) -- do nothing.
// The GUI might play a "fail" beep.
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos-or-false>, target-tile :: <fixed> )
=> ( result :: <boolean> )
#f;
end;
</pre>
<p>Doing all our own dispatch logic, here is a single method in Objective-C:</p>
<pre>- (BOOL)pushTile:(tile_t)target_tile
due:(dir_e)dir
at:(pos_t)target_pos
{
switch ( target_tile )
{
/*
Handle the "walkable" cases. The penguin is allowed to move
onto these tiles, indicated by returning YES
*/
case polar_tile_empty: /* FALL THROUGH */
case polar_tile_tree:
NSLog( @"pushTile: walkable\n" );
self->penguinPos = target_pos;
return YES;
/*
Handle "movable" cases. Call collide which specializes in
various combinations.
*/
case polar_tile_bomb: /* FALL THROUGH */
case polar_tile_heart: /* FALL THROUGH */
case polar_tile_ice_block:
NSLog( @"pushTile: movable\n" );
{
pos_t next_pos = getAdjacentPos( target_pos, dir );
/*
Note that next-pos can be invalid, which results
in the special "edge" tile value.
*/
tile_t next_tile = [ self getTileAtPos:next_pos ];
[ self collideTile:target_tile atPos:target_pos
due:dir withTile:next_tile
atSecondPos:next_pos ];
}
return NO;
/*
Handle "fixed" cases. Do nothing; the GUI might play
a "fail" beep.
*/
case polar_tile_mountain: /* FALL THROUGH */
case polar_tile_house:
NSLog( @"pushTile: fixed\n" );
return NO;
default:
NSLog( @"pushTile: unexpected tile value %d\n",
target_tile );
return NO;
}
}</pre>
<p>And as in the Dylan version, for interesting interactions this method defers to another method:</p>
<pre>- (void)collideTile:(tile_t)first_tile
atPos:(pos_t)first_pos
due:(dir_e)dir
withTile:(tile_t)second_tile
atSecondPos:(pos_t)second_pos
{
BOOL empty = ( second_tile == polar_tile_empty );
/* Blocking includes the special edge tile value */
BOOL blocking = ( second_tile != polar_tile_empty );
BOOL mountain = ( second_tile == polar_tile_mountain );
BOOL house = ( second_tile == polar_tile_house );
BOOL ice_block = ( first_tile == polar_tile_ice_block );
BOOL bomb = ( first_tile == polar_tile_bomb );
BOOL heart = ( first_tile == polar_tile_heart );
BOOL movable = ( ice_block || bomb || heart );
if ( bomb && mountain )
{
/*
When a bomb meets a mountain, both bomb and mountain blow up
*/
NSLog( @"collideTile: bomb / mountain\n" );
[ self setTile:polar_tile_empty AtPos:first_pos ];
[ self setTile:polar_tile_empty AtPos:second_pos ];
}
else if ( heart && house )
{
/*
When a bomb heart meets a house, we are closer to winning
*/
NSLog( @"collideTile: heart / house\n" );
[ self setTile:polar_tile_empty AtPos:first_pos ];
[ self decrementHeartCount ];
}
else if ( ice_block && blocking )
{
/*
When an ice block is pushed directly against any
blocking tile (including the board edge), it is destroyed.
*/
NSLog( @"collideTile: ice block / blocking\n" );
[ self setTile:polar_tile_empty AtPos:first_pos ];
}
else if ( movable )
{
if ( empty )
{
/*
A movable tile pushed onto an empty tile will slide
*/
NSLog( @"collideTile: movable / empty: start slide\n" );
[ self slideTile:first_tile atPos:first_pos due:dir
toTile:second_tile atSecondPos:second_pos ];
}
else if ( blocking )
{
/*
When a generic movable piece meets any other
blocking pieces not handled by a special case
above, nothig happens; it stops. Maybe play
a "fail" beep.
*/
NSLog( @"collideTile: movable / blocking\n" );
}
}
}</pre>
<p>This could have been written with a bunch of ugly, redundant-looking <b>switch</b> statements, but the duplicated cases and defaults just don't seem as clear to me as making flags that precisely describe the nature of the "double dispatch" going on. In this program, having to spell out the logic (using code to find code) is not really onerous. But the problem comes, of course, in code where we keep having to add special cases. I could refactor this method to call some smaller methods but that doesn't seem like a real win. In the Dylan implementation if I wanted to add another special interaction, it might only require adding another generic function. That's assuming my whole class hierarchy didn't change.</p>
<p>Finally, the slide method:</p>
<pre>- (void)slideTile:(tile_t)first_tile
atPos:(pos_t)first_pos
due:(dir_e)dir
toTile:(tile_t)second_tile
atSecondPos:(pos_t)second_pos
{
BOOL empty = ( second_tile == polar_tile_empty );
/* Blocking includes the special edge tile value */
BOOL blocking = ( second_tile != polar_tile_empty );
BOOL ice_block = ( first_tile == polar_tile_ice_block );
BOOL movable = ( ice_block ||
first_tile == polar_tile_bomb ||
first_tile == polar_tile_heart );
if ( ice_block && blocking )
{
// A specific movable tile, ice-block, meets a
// blocking tile; don't call collide since the behavior
// of a sliding ice block is different than a pushed ice
// block. It just stops and doesn't break.
NSLog( @"slideTile: ice block / blocking\n" );
}
else if ( movable && empty )
{
// A movable tile interacting with an empty tile --
// move forward on the board and call slide again.
NSLog( @"slideTile: movable / empty\n" );
pos_t third_pos = getAdjacentPos( second_pos, dir );
tile_t third_tile = [ self getTileAtPos:third_pos ];
[ self setTile:polar_tile_empty AtPos:first_pos ];
[ self setTile:first_tile AtPos:second_pos ];
[ self slideTile:first_tile atPos:second_pos due:dir
toTile:third_tile atSecondPos:third_pos ];
}
else if ( movable && blocking )
{
// A movable tile meets a blocking tile: call collide to
// handle heart/house, bomb/mountain, edge of world, etc.
NSLog( @"slideTile: movable / blocking\n" );
[ self collideTile:first_tile atPos:first_pos due:dir
withTile:second_tile atSecondPos:second_pos ];
}
}</pre>
<p>That's the bulk of it. Here's an excerpt from the log as it finishes up the first level:</p>
<pre>ArcticSlide[2279:c07] penguinPush: tile at 2, 5 pushed
ArcticSlide[2279:c07] pushTile: walkable
ArcticSlide[2279:c07] Penguin moved to: 2, 5
ArcticSlide[2279:c07] Penguin direction changed to EAST
ArcticSlide[2279:c07] Penguin moving EAST
ArcticSlide[2279:c07] penguinPush: tile at 2, 6 pushed
ArcticSlide[2279:c07] pushTile: movable
ArcticSlide[2279:c07] collideTile: movable / empty: start slide
ArcticSlide[2279:c07] slideTile: movable / empty
ArcticSlide[2279:c07] collideTile: heart / house
ArcticSlide[2279:c07] Heart count reached zero, level cleared!
ArcticSlide[2279:c07] ArcticSlideModel board state:
tre__________________________________________treice_____________________
tre_________mtn_______________________________________tre______tre______
tre____________________________________________________________hou______
tretre____________treice________________________________________________
</pre>
<p>I'll put in logic to play the remaining levels soon, as additional test cases.</p>
<p>Note that I kept the recursive call to slideTile. It's not an idiom commonly used in C and Objective-C. We only recurse when the moving tile traverses more than one empty tile, and so never more than 23 times. I like to write algorithms recursively when possible while sketching out code. If direct recursion like that is <i>verboten</i>, it can be removed. I don't think my compiler is optimizing it out. But the termination logic now starts to look redundant:</p>
<pre>else if ( movable && empty )
{
while ( NO == blocking )
{
pos_t third_pos = getAdjacentPos( second_pos, dir );
tile_t third_tile = [ self getTileAtPos:third_pos ];
[ self setTile:polar_tile_empty AtPos:first_pos ];
[ self setTile:first_tile AtPos:second_pos ];
first_pos = second_pos;
second_pos = third_pos;
second_tile = third_tile;
blocking = ( third_tile != polar_tile_empty );
}
if ( ice_block )
{
NSLog( @"slideTile: ice block / blocking\n" );
}
else
{
[ self collideTile:first_tile atPos:first_pos due:dir
withTile:second_tile atSecondPos:second_pos ];
}
}</pre>
<p>And if I don't want to call back into methods in my own call chain at all -- that is, if I have to give up calling <b>collideTile</b>, well, I could do that but it would involve putting copying of the logic from collideTile into this method, and by that point this method will be badly breaking the "DRY" (Don't Repeat Yourself) axiom, so it might be clearer to turn <b>collideTile</b> and <b>slideTile</b> into one method.</p>
<p>Anyway, the heat is building up in my office and it is about dinnertime. I think it's time to move on to some user interface, so the app can actually be played on an untethered iOS device. I also am still struggling a bit to get going on a Haskell implementation. I know it can be done -- people describe Haskell as a good imperative language too, for modeling state as safely as possible -- but let's just say that the chapters and examples I'm reading haven't quite "gelled" in my brain. I still feel like someone studying a foreign language who can read it and understand it when spoken, but not speak it yet -- especially the Monadic dialects. But I'm still working on that.</p>
<p>UPDATE: I have put the source on GitHub, such as it is -- for now, ignore the license text; I need to pick an actual license. See: <a href="https://github.com/paulrpotts/arctic-slide-ios">https://github.com/paulrpotts/arctic-slide-ios</a></p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-32772158429771347132013-06-20T00:44:00.003-04:002013-06-24T20:34:05.828-04:00Dispatch for the Polar Game in Dylan<p>So with some assistance from the folks on the Dylan Hackers mailing list I got enough clues to press on and get my Dylan implementation of the Polar game working, at least up through the end of the first board. I haven't verified that every possible tile interaction works yet, but it's a start. This seems like a silly problem, but it interests me because of several problems. Dispatch (or simulated dispatch) is "double dispatch," based on the types of two different objects interacting. The breakdown of how to categorize the classes of objects isn't 100% clear -- there is some overlap that I can't seem to eliminate, and the compiler has to decide what methods constitute the most specific match. And finally, the logic does not seem easily fixed in either classes representing the tiles, or a single class representing the board.</p>
<p>If I wrote it in C, the tile classes pretty much wouldn't exist; they'd exist only as flag enumerations in an array of tiles, and the code would consist mostly of <b>switch</b> or <b>if-else</b> logic that did the "double dispatch" in a fixed, predictable order, without relying on the compiler very much. Objective-C, again mostly C with a thin layer for representing classes, doesn't really give these classes enough features to make them worthwhile, so I will probably just keep the board (the model in the model/view/controller) and treat the tiles like I would in plain old C. But in Dylan they have an interesting life in terms of how they can be used to organize the code -- using generic functions -- so that I'm doing less writing of "code to find code" -- that is, code to look at run-time identity of objects and "manually" dispatch on it.</p>
<p>Here are the tile classes:</p>
<pre>define abstract class <tile> ( <object> ) end;
define abstract class <blocking> ( <tile> ) end;
define abstract class <walkable> ( <tile> ) end;
define abstract class <movable> ( <blocking> ) end;
define abstract class <fixed> ( <blocking> ) end;
define class <bomb> ( <movable> ) end;
define class <heart> ( <movable> ) end;
define class <ice-block> ( <movable> ) end;
define class <house> ( <fixed> ) end;
define class <mountain> ( <fixed> ) end;
define class <edge> ( <fixed> ) end;
define class <tree> ( <blocking>, <walkable> ) end;
define class <empty> ( <walkable> ) end;</pre>
<p>Oy, is that a pain to replace all the angle brackets with HTML entities... there must be a better way in Blogger! Anyway, these tile classes have no state -- in Dylan, no slots -- and are used in my program solely for their types. Edge does not actually appear on the board, but is used internally when the penguin or another moving object attempts to interact with the edge of the board. We treat this just like another blocking object, as if the board was surrounded by immovable, inert objects.</p>
<p>Diagramatically, like so:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEXY1K4h0jVKTn9TyXZNsI9yvZA8BbZOnlzyeIvRUCfS6qTl57WjsYielGNTUX8MVYa57W1SPTka3Ce0YkRoTuRvEQT0KayviuPjXqf-ZN5J8etL4JIl_YIC1amDXhox7X8_kq/s1600/tile-classes-v2-75-percent.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEXY1K4h0jVKTn9TyXZNsI9yvZA8BbZOnlzyeIvRUCfS6qTl57WjsYielGNTUX8MVYa57W1SPTka3Ce0YkRoTuRvEQT0KayviuPjXqf-ZN5J8etL4JIl_YIC1amDXhox7X8_kq/s1600/tile-classes-v2-75-percent.png" /></a>
<p>There did not seem to be one absolute best way to represent these classes. I want to organize their abstract base classes by behavior, but their behavior does not break down with complete consistency -- for example, tiles with trees are "blocking" with respect to sliding objects, except for the penguin. The ice block is "blocking" except for the case where the penguin pushes it and it is not adjacent to an empty tile -- then it is crushed. Bombs and hearts seem to have the same interactions with mountains and houses whether they traverse an empty tile by sliding first across one or more empty tiles, while ice blocks behave differently -- if they slide first and then collide with a blocking object, they are not destroyed, they just stop. So the groupings of the concrete classes isn't going to be able to coherently divide up all their possible behaviors.</p>
<p>The scheme I settled on for object interactions involves three layers, in the form of three generic functions. The first represents interactions of the player's "avatar," the penguin, with tiles:</p>
<pre>define generic pushTile( model :: <model>, dir :: <dir>,
pos :: <pos-or-false>, target-tile :: <tile> );
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos>, target-tile :: <walkable> )
=> ( result :: <boolean> )
model.penguin-pos := target-pos;
#t;
end;
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos>, target-tile :: <movable> )
=> ( result :: <boolean> )
let next-pos :: <pos-or-false> =
getAdjacentPos( target-pos, dir );
let next-tile = getTileAtPos ( model, next-pos );
collide( model, dir, target-pos, target-tile,
next-pos, next-tile );
#f;
end;
define method pushTile( model :: <model>, dir :: <dir>,
target-pos :: <pos-or-false>, target-tile :: <fixed> )
=> ( result :: <boolean> )
#f;
end;</pre>
<p>Dylan doesn't strictly require that I define the generic function before defining methods for it; if I just start writing methods with the same name, it will assume that I mean them to be associated with a generic function. But defining the generic function first has a benefit -- the compiler will tell me whether my methods make sense, in that their parameters are all strictly the same type or a more specific subclass of the types mentioned in the <b>define generic</b> statement. Note that <b><pos-or-false></b> is a type union of a simple <b><pos></b> class with singleton( #f ). The generic uses that type union, but one of the methods are more specific: they require an actual <b><pos></b> instance and will not accept #f.</p>
<p>The first method handles the case where the penguin is pushing a <b><walkable></b> tile, and returns false to indicate that the penguin position can be updated. The pos must not be <b>#f</b>. The second method handles pushing any <b><movable></b> tiles. And the third handles the <b><fixed></b> tiles. Between the three methods, you might notice that they cover all the leaf classes (all the instantiable classes) in the graph above, in 3 separate groups with no overlapping. You could shade in the leaf nodes covered by the three different methods with three different colors, going from the abstract classes mentioned downward, and all the leaves would all be colored and none would be colored more than once:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQ41rZkG-POPMMaaOOOJMyfQ3nFqHWk7adV_nqhWxa3NSx_fMSiqVzobLpLBMlJPjUCxnCj6foZFMeU85asVJcSea2ldu6f8UauaJrfvfdfgvoShwj9B8Gdd07Av_6IG8r3uia/s1600/tile-classes-v2-color-1-75-percent.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQ41rZkG-POPMMaaOOOJMyfQ3nFqHWk7adV_nqhWxa3NSx_fMSiqVzobLpLBMlJPjUCxnCj6foZFMeU85asVJcSea2ldu6f8UauaJrfvfdfgvoShwj9B8Gdd07Av_6IG8r3uia/s1600/tile-classes-v2-color-1-75-percent.png" /></a>
<p>So on the tile parameter, the coverage of the concrete classes is complete and the dispatch algorithm should not have any difficulty. Combined with the position parameter, though, the situation is slightly trickier. At runtime, a caller could call <b>pushTile</b> with <b>#f</b> for <b>pos</b> and <b><empty></b>; or <b><bomb></b> for <b>tile</b> and the dispatcher would, correctly, throw up its hands at this point and say that there was no applicable method. I could have defined a more general method to handle this case, but I didn't -- there shouldn't ever be an empty or bomb tile without a corresponding valid position, since they are real tiles on the board, and I want the runtime to help me catch that case if it ever happens. Similarly, I could have defined a method that handled <b><blocking></b> or <b><tile></b> as part of this generic function but the whole point is that I don't know what to do with those more general classes here.</p>
<p>So, you may notice that the middle <b>pushTile</b> method calls <b>collide</b> with a second tile and position, adjacent to the first in a specified direction. That generic function looks like this:</p>
<pre>define generic collide( model :: <model>, dir :: <dir>,
tile-1-pos :: <pos>, tile-1 :: <movable>,
tile-2-pos :: <pos-or-false>, tile-2 :: <blocking-or-empty> );
define method collide( model :: <model>, dir :: <dir>,
movable-pos :: <pos>, movable-tile :: <movable>,
next-pos :: <pos>, next-tile :: <empty> )
slide ( model, dir, movable-pos, movable-tile,
next-pos, next-tile );
end;
define method collide( model :: <model>, dir :: <dir>,
ice-block-pos :: <pos>, ice-block-tile :: <ice-block>,
icebreaking-pos :: <pos-or-false>,
ice-breaking-tile :: <blocking> )
setTileAtPos( model, ice-block-pos, $the-empty );
end;
define method collide( model :: <model>, dir :: <dir>,
heart-pos :: <pos>, heart-tile :: <heart>,
house-pos :: <pos>, house-tile :: <house> )
setTileAtPos( model, heart-pos, $the-empty );
decrementHeartCount( model );
end;
define method collide( model :: <model>, dir :: <dir>,
bomb-pos :: <pos>, bomb-tile :: <bomb>,
mountain-pos :: <pos>, mountain-tile :: <mountain> )
setTileAtPos( model, bomb-pos, $the-empty );
setTileAtPos( model, mountain-pos, $the-empty );
end;
define method collide( model :: <model>, dir :: <dir>,
movable-pos :: <pos>, movable-tile :: <movable>,
blocking-pos :: <pos-or-false>, blocking-tile :: <blocking> )
end;</pre>
<p>You might notice that before long you hit yet another method call you haven't seen before -- slide. This is, as you might guess, yet another generic function. (Doesn't this program every get around to <i>doing</i> anything? In fact it does, but this is the often-paradoxical-seeming logic of object-oriented design -- individual methods that seem too small and simple to get anything done can actually get a lot done together, especially when aided by a smart dispatcher that eliminates most of the need to write "code to find code."</p>
<p>The type-union <b><blocking-or-empty></b> allows us to specify, for our generic function, as tight a class as possible out of two otherwise disjoint sections of our class diagram. We don't have to loosen the type specification needlessly by using <b><tile></b>, which would allow <b><walkable></b> as a valid class for this parameter. Meanwhile, we can loosen <b>tile-2-pos</b> so that we make our intention to allow <b>#f</b> explicit here.</p>
<p>The methods break down as follows. The first one handles any movable tile that is moving onto an empty tile, by calling a slide method to be defined later. The second one is a special case to handle the crushable <b><ice-block></b> class -- if it is pushed into the world edge, or any other object, it is destroyed (replaced with <b>$the-empty</b> class instance). The third and fourth methods handle specific interactions between hearts and houses, and bombs and mountains. And finally, to handle the case where the penguin pushes a heart against a mountain, or a bomb against the edge of the world, we have a less specific method that dispatches on <b><movable></b> and <b><blocking></b>. This prevents the runtime from generating an error in this case, but also gives us a place where we could generate some kind of feedback to the user, like a special sound to indicate failure.</p>
<p>The breakdown of instantiable tile classes here is much more complex, especially given that we are dispatching on two class parameters drawn from the same hierarchy. We could try coloring them by using two copies of the diagram:</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjLmZgQZZPU-sKghOc86e2DrHi3yFZ7gC22nBOZE64IR8JnBDLBdOZSp6EKnw041v6vHIDs3MMe9zhntTCxcuCfYOgSMI8wuw3bD6k2xu9kI2hSDbPAZILU36A_AR17KHEeL0H/s1600/tile-classes-v2-double-dispatch-2-75-percent.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjLmZgQZZPU-sKghOc86e2DrHi3yFZ7gC22nBOZE64IR8JnBDLBdOZSp6EKnw041v6vHIDs3MMe9zhntTCxcuCfYOgSMI8wuw3bD6k2xu9kI2hSDbPAZILU36A_AR17KHEeL0H/s1600/tile-classes-v2-double-dispatch-2-75-percent.png" /></a></div>
<p>Err, that's pretty, but is it helpful? I'm using colors and borders to indicate that classes are handled by specific methods, but the main thing I hope I'm illustrating is that, unlike with the first generic function, in this one there is significant overlap between the classes handled by the different methods. This is where the dispatch mechanism really has to shine. There is an ordering that makes sense from my point of view, and that is one in which the most specific matching method will be called. However, as you can see, quantifying "most specific" may be slightly complex when dispatching on more than one class parameter, throwing in type-unions for fun. Fortunately this code is now working, but while I was developing it I became familiar with a warning message in Open Dylan that says something like "the method dispatch handling this set of classes is determined by arbitrary and capricious rules" -- indicating that the dispatch logic is still considered a work in progress. I was concerned that the current version of the Open Dylan compiler wasn't quite solid enough to make this work, but it does seem to work. The backup plan was to dispatch entirely on type-unions made up of different sets of singletons, but that is longer and obscures what is meant by the abstract classes.</p>
<p>I won't go to the trouble to do the same diagram on my slide method, but that code looks like this:</p>
<pre>define generic slide( model :: <model>, dir :: <dir>,
movable-pos :: <pos>, movable-tile :: <movable>,
next-pos :: <pos-or-false>, next-tile :: <blocking-or-empty> );
define method slide( model :: <model>, dir :: <dir>,
movable-pos :: <pos>, movable-tile :: <movable>,
next-pos :: <pos>, next-tile :: <empty> )
let next-next-pos :: <pos-or-false> =
getAdjacentPos( next-pos, dir );
let next-next-tile = getTileAtPos( model, next-next-pos );
setTileAtPos( model, next-pos, movable-tile );
setTileAtPos( model, movable-pos, $the-empty );
slide( model, dir, next-pos, movable-tile ),
next-next-pos, next-next-tile );
end;
define method slide( model :: <model>, dir :: <dir>,
movable-pos :: <pos>, movable-tile :: <movable>,
next-pos :: <pos-or-false>, next-tile :: <blocking> )
collide( model, dir, movable-pos, movable-tile,
next-pos, next-tile );
end;
define method slide( model :: <model>, dir :: <dir>,
ice-block-pos :: <pos>, ice-block-tile :: <ice-block>,
next-pos :: <pos-or-false>, next-tile :: <blocking> )
end;</pre>
<p>Aaaand that's pretty much the whole of the logic for handling interaction between the penguin and the various tiles. Note that we call ourselves recursively. It looks kind of like we have no termination condition! Except note that the method isn't calling itself, it's doing the same method dispatch that found it in the first place. When we come to a termination condition for our recursions, we'll actually call a different method of the same generic function -- most likely the third one, where a sliding object encounters a blocking object. That condition can include hitting the edge of the board. And fortunately -- we already have logic for that, mostly -- in our collide generic function! So sliding hearts and bombs are handled just the same as if they were pushed instead of ending a slide.</p>
<p>There's a slightly tricky part where we want to bind up the next tile beyond the two tiles we were dispatched on, then perform two set operations to move the currently sliding tile, then dispatch on the starting tile at its moved position. To figure that out I had to draw some bits of the game board with circles and arrows (but not a paragraph on the back of each one to be used as evidence against me). (If you don't get that reference, either you're too young or I'm too old!)</p>
<p>This is not the whole program, obviously, but these are the key methods for encoding the collisions between tiles. If you'd like to play with the whole program, you might come and join the <a href="https://lists.opendylan.org/mailman/listinfo/hackers">Dylan Hackers mailing list</a>, or leave me a note. If there is interest I'll publish it, here or elsewhere. I am now curious as to how a similar set of overlapping dispatches -- via pattern matching, perhaps? -- might look in Haskell. I might try to write that next. If you've got an idea about the clearest and most idiomatic way to do it, I welcome your comments.</p>
<p>UPDATE: the code, such as it is, is on GitHub. Ignore the license for now; I have to decide on an actual license. See: <a href="https://github.com/paulrpotts/arctic-slide-dylan">https://github.com/paulrpotts/arctic-slide-dylan</a></p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-82400940915286885022013-06-16T21:09:00.000-04:002013-06-16T21:44:44.457-04:00Objective-Dylan, or Perhaps Subjective-C?<p>Yesterday my wife took the kids with her on an overnight trip to Ann Arbor so I've had a bit of extra quiet time. How am I making use of this bounty? Getting on with some minor home repairs? Cleaning my office from top to bottom? Er, no... porting the game logic I've written so far in Objective-C back to Dylan, so that I can do some more thinking about it.</p>
<p>So after a phone job interview yesterday (which went well, I thought -- I'm optimistic about this possibility!) I started working on this task, and then about twelve hours later, around 2 a.m., I had the basic setup and population of the game board working. It's embarrassing to admit how long it took. I started on my Mac, and when I began encountering constant runtime errors switched over to my Ubuntu box, thinking that the Mac version of Open Dylan might just be broken (it isn't; I got the identical behavior on the Linux build). I finally figured out workarounds -- it's funny how taking a break clears my head far better than pressing on ever does -- then read a little Gene Wolfe (I'm working my way through <i>In Green's Jungles</i>, one of his books I've repeatedly tried and failed to finish), and fell asleep with no children in the bed to kick or otherwise interfere with a good night's sleep. I'm back up this morning, had a bath, and I'm drinking a large coffee with soy creamer and stevia and trying to hold off on a lunch break until I have some more done. It's about 10 a.m. and I'm expecting my family back in about six hours, so the race is on!</p>
<p>This has taken far longer than I hoped; I lost quite a bit of time stumbling across things in Open Dylan that still seem just plain broken. I had to start working on a smaller and smaller program to figure out exactly what was broken. These things I've flagged in comments, as places where, basically, I wish Dylan worked a certain way, and it doesn't. I may just be asking for something that doesn't quite match the original spec or isn't quite possible, but I'll share those with the Dylan Hackers team and see if it seems like I can help with them. The biggest thing that was broken, though, was me -- my brain, that is -- since it's been a long time since I've worked with Dylan's <b>type-union</b> and <b>singleton</b> pseudo-classes and I had forgotten the details. The compiler was not a big help with this, since it is such a <i>dynamic</i> language and leaves an awful lot of things to the runtime to figure out, which it does by throwing an error message that may or may not help much. The documentation is a bit scanty, but it does contain everything you need to know, if you re-read and squint at the scanty examples that are out there hard enough.</p>
<p>The good news is that the port is working and I'd like to share it. Dylan is still up there with Scheme (and now Haskell) as one of my favorite languages for <i>designing</i> programs -- yes, even though Dylan is quite old as languages go. I like to see what it can do especially with generic functions and its sophisticated model for object-oriented <i>dispatch</i>. I've been a little stymied as to how to express the design best in Objective-C. If it was a complicated game design, I wouldn't feel bad about having a program that looked complex. But it's really an elegantly simple game, and so I feel like the implementation should reflect that. My Objective-C implementation has been feeling more and more bloated and pointlessly complex, although it works, so my thought was to get it down to a simple implementation that takes full advantage of Dylan's object-oriented programming features, largely borrowed from CLOS, and then port that back to Objective-C, adding whatever minimalist support is needed to fake up some of the features that Dylan gives me that Objective-C doesn't have. This might be by way of also writing a Haskell or Scala implementation later, for yet more learning and language comparison, although really what I should focus on is getting the iOS GUI up and working so that I have something to show people.</p>
<p>Anyway, I've got a Dylan program that plays the Polar game, using singletons to represent tile types, and methods dispatched on singletons to handle specific kinds of collisions. The classes -- which are empty, pretty much used <i>only</i> for their usefulness as types, for driving dispatch -- are like so:</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7D2WAGbLpOaAhSU3YjKxSWCQFVR8xFbxfZMe542gXhZ-4TtP0gd10PsI8MLhrXgUSCljM002GyfxfJIUmbYpHzFD4wTWnz6HtUsJiEFSQyJ3Q5p3Hk67O_R9NvCilEvs5ZXpk/s1600/tile-classes-75-percent.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7D2WAGbLpOaAhSU3YjKxSWCQFVR8xFbxfZMe542gXhZ-4TtP0gd10PsI8MLhrXgUSCljM002GyfxfJIUmbYpHzFD4wTWnz6HtUsJiEFSQyJ3Q5p3Hk67O_R9NvCilEvs5ZXpk/s1600/tile-classes-75-percent.png" /></a></div>
<p>In Dylan you can create some instances, and create something called a <b>type-union</b>, which is something that is a type, I think, but not a class. You can use it to define a slot type or a parameter type. But you can't make one:</p>
<pre>define constant $the-bomb = make(<bomb>);
define constant $the-empty = make(<empty>);
define constant $the-heart = make(<heart>);
define constant $the-house = make(<house>);
define constant $the-ice-block = make(<ice-block>);
define constant $the-mountain = make(<mountain>);
define constant $the-tree = make(<tree>);
define constant <tile-or-false> = type-union(
singleton( $the-bomb ), singleton( $the-empty ),
singleton( $the-heart ), singleton( $the-house ),
singleton( $the-ice-block ), singleton( $the-mountain ),
singleton( $the-tree ), singleton( #f ) );</pre>
<p>And eventually dispatch on singletons -- meaning that a given method will be called with it is called with references to the exact objects that you specify:</p>
<pre>define method collide( model :: <model>, dir :: <dir>,
heart-pos :: <pos>, heart-tile == $the-heart,
house-pos :: <pos>, house-tile == $the-house )
format-out( "collide: $the-heart / $the-house\n" );
setTileAtPos( model, heart-pos, $the-empty );
model.decrementHeartCount();
end;</pre>
<p>That gives you an idea of how some of the code in the Dylan program is organized. I have it mostly working, however, I'm not going to present the full code quite yet because I have a crashing bug, and I haven't yet been able to figure out if it is a dumb mistake on my part or a compiler or runtime bug in Open Dylan. I've also asked the Dylan hackers to take a look at my design and see what they think -- if they can find, as I put it, "a simpler design struggling to get out." Which is always the challenge, when trying to write not just functional, but <i>model</i> code, isn't it?</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-28105580682293197852013-06-07T19:17:00.000-04:002013-06-14T14:58:44.638-04:00Objective-C, Day 5<p>(Warning: non-FP content). (I've been including this for the benefit of any "Planet X" aggregators who are including my feed, where X is a functional language like Haskell. I'm assuming you've got that by now and either don't care or are unsubscribing/ignoring this series if it bothers you. I expect to get back to more functional language code at some point, maybe even implementing the same problem. But I dabble in different languages and sometimes the digressions go on for a while...)</p>
<p>So, today's topic is <b>dispatch</b>. I'm starting to design and implement the logic for pieces interacting on the board. The key in object-oriented designs is always to determine who (which object) manages which state. The design I've come up with is a sort of hybrid design, where position on the board is not actually a property of the board tiles. Instead, there's a board which keeps track of them. The instances of, say, a tree on the board don't have any unique state, so I'm not instantiating different objects for each one; they all point to a singleton (which I should properly enforce with a singleton factory method at some point).</p>
<p>There are trade-offs. On paper, my design involved adding a "push" method to the classes for tile pieces. In a language like Dylan, this "push" method would be a generic function, and dispatch on multiple parameter types, so that I could write some very short methods and use the method dispatcher, instead of explicit <b>if-then</b> or <b>switch</b> logic to find the right bit of code at run-time according to the types of the interacting objects (either their literal types or an enum, or some such). I could even do this in C++ because it has method overloading based on the parameters -- as long as this is <a href="http://stackoverflow.com/questions/6897662/matching-an-overloaded-function-to-its-polymorphic-argument">based on their static type known at compile-time</a>. Which... isn't true in this case. I miss Dylan's generic function dispatch! <a href="http://stackoverflow.com/questions/2286312/method-overloading-in-objective-c">Objective-C is a underpowered</a> in this respect even compared to C++. For example, I'd like to be able to write methods like this for the bomb class (this is pseudocode):</p>
<pre>bomb::push(mountain)
{
// blow up the mountain
}
bomb::push(empty)
{
// slide the bomb onto the tile
}</pre>
<p>But I can't. I can't just use the class construct to organize methods to call without an instance -- there doesn't seem to be the equivalent of C++ static methods. There also is no equivalent of a pure virtual function; I can't declare the need for a push() method in the common base class of the tile pieces and have the compiler demand that I implement in any subclasses to make them instantiable. The closest I can come, I think, is to create a method that generates an error if it itself is called instead of being overridden in a subclass. That seems to lack semantic clarity. So maybe I could do this, with <a href="http://en.wikipedia.org/wiki/Double_dispatch">double dispatch</a>, but it doesn't seem worth the trouble for a small number of collision behaviors, when the behavior isn't simply supported by the language. I keep telling myself "thin layer on top of C... thin layer on top of C..."</p>
<p>So last night I had my Mac running upstairs in the office, and I used my iPad downstairs to connect to it via VNC, and write some code, running it on the iPad simulator, which I then viewed and controlled with a real iPad (mad scientist laugh). It needs a little tweaking this morning but here's more-or-less what I came up with. Note that I have started using some different naming conventions for file-scope and local variables. I'm not sure they are very standard Objective-C but they are closer to what I've grown comfortable with over the years in C and C++.</p>
<pre>typedef struct {
int x_idx;
int y_idx;
} pos_t;
typedef enum {
dir_east,
dir_west,
dir_south,
dir_north
} dir_e;
// A straight C function to return a pos_t updated with a dir_e;
// the result may be out of bounds
pos_t getUpdatedPos( pos_t original_pos, dir_e dir );
BOOL posValid( pos_t pos );
static const int board_width = 24, board_height = 4;
// The short board design is part of what makes it so
// easy to get sliding objects stuck against the edges
// of the world or in corners where you can't get the
// penguin avatar around to the other side to push them.
// We could consider a bigger board later and maybe
// implement the original puzzles surrounded by water,
// or something like that.
// Equivalent of C++ class forward declaration
@class ArcticSlideTile;
@class ArcticSlideBomb;
@class ArcticSlideEmpty;
@class ArcticSlideHeart;
@class ArcticSlideHouse;
@class ArcticSlideIceBlock;
@class ArcticSlideMountain;
@class ArcticSlideTree;
@interface ArcticSlideModel : NSObject
{
ArcticSlideTile* board[board_height][board_width];
}
- (id)init;
- (id)initWithLevelIndex:(int)level_idx;
- (NSString*) description;
- (ArcticSlideTile*)getTileFromPosition:(pos_t)pos
inDirection:(dir_e)dir;
- (void)setTileAtPosition:(pos_t)pos
to:(ArcticSlideTile*)type;
@end
@interface ArcticSlideTile : NSObject
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
@end
@interface ArcticSlideBomb : ArcticSlideTile
// Bombs can be pushed and will slide until they hit an
// object and stop. If the object is a mountain, both bomb
// and mountain are destroyed. If another object hits a bomb
// it stops (I think -- I'm not sure it is possible to set
// up a board such that you can slide something into a bomb).
// push is called when the penguin pushes against a tile.
// It returns YES if the penguin can move onto the tile with
// this action. This is only ever the case for a tree or empty
// tile.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideEmpty : ArcticSlideTile
// The penguin can always step onto an empty tile
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (BOOL)slideFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideHeart : ArcticSlideTile
// When a heart hits a house the heart disappears (getting
// all the hearts into the house is how you win the game).
// Otherwise they cannot be destroyed, and slide like other
// slidable items.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideHouse : ArcticSlideTile
// Houses cannot be pushed and stop other objects except
// hearts. When a heart hits a house the heart disappears
// (getting the hearts into the house is how you win the game).
// So the model should keep track of the number of hearts
// on the board and trigger a "win the level" behavior when
// the last heart is removed.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideIceBlock : ArcticSlideTile
// Ice blocks can be pushed and will slide until they hit
// an object and stop. If they are pushed directly against
// an object they will be crushed (there should be an animation)
// and disappear.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideMountain : ArcticSlideTile
// Mountains cannot be moved and are destroyed by bombs.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end
@interface ArcticSlideTree : ArcticSlideTile
// Trees cannot be pushed or destroyed and stop all sliding
// objects, but the penguin avatar character can walk through
// them.
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir;
- (NSString*) description;
@end</pre>
<p>Here's part of the implementation. It seems way too wordy; I need to rethink the amount of code required for each step. At the least, some refactoring seems to be in order. As I mentioned earlier, I'm not sure the tile classes are really earning their keep. I got rid of the singleton instantiation machinery but now there are order of initialization dependencies. I'll need to do further thinking as I consider what communication needs to happen between the "model" part and "controller" part -- how to interact with the GUI, how to indicate that tiles need to be redrawn, or animated transitions should play, or sound effects should play, or that the score is changed, and what to do when a level is completed. There is lots more to think about for such a simple little game! And of course I haven't really even begun to implement the "view" parts.</p>
<pre>static ArcticSlideEmpty* empty_p;
static ArcticSlideTree* tree_p;
static ArcticSlideMountain* mountain_p;
static ArcticSlideHouse* house_p;
static ArcticSlideIceBlock* ice_block_p;
static ArcticSlideHeart* heart_p;
static ArcticSlideBomb* bomb_p;
static ArcticSlideModel* model_p;
pos_t getUpdatedPos( pos_t original_pos, dir_e dir )
{
pos_t updated_pos = original_pos;
int x_offset = 0;
int y_offset = 0;
if ( dir_east == dir )
{
x_offset = 1;
y_offset = 0;
}
else if ( dir_west == dir )
{
x_offset = -1;
y_offset = 0;
}
else if ( dir_north == dir )
{
x_offset = 0;
y_offset = -1;
}
else if ( dir_south == dir )
{
x_offset = 0;
y_offset = +1;
}
updated_pos.x_idx += x_offset;;
updated_pos.y_idx += y_offset;
return updated_pos;
}
BOOL posValid( pos_t pos )
{
return ( ( ( pos.x_idx >= 0 ) ||
( pos.x_idx < board_width ) ) ||
( ( pos.y_idx >= 0 ) ||
( pos.y_idx < board_height ) ) );
}
@implementation ArcticSlideTile
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir
{
// Should be implemented in subclass
return NO;
}
@end
@implementation ArcticSlideBomb
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir
{
// Penguin has pushed bomb in the given direction.
// Get our own position:
pos_t bomb_pos = getUpdatedPos( pos, dir );
// What are we being pushed into?
ArcticSlideTile *target_tile_p =
[model_p getTileFromPosition:bomb_pos
inDirection:dir];
if ( nil == target_tile_p )
{
// Edge of the world. TODO:
// queue a "boop" sound effect
}
else if ( mountain_p == target_tile_p )
{
// bomb pushed into mountain
// TODO: queue animation of bomb moving onto
// mountain, animate explosion
// remove bomb and mountain
pos_t new_bomb_pos = getUpdatedPos( bomb_pos, dir );
[model_p setTileAtPosition:new_bomb_pos
to:empty_p];
new_bomb_pos = getUpdatedPos( new_bomb_pos, dir );
[model_p setTileAtPosition:new_bomb_pos
to:empty_p];
}
else if ( empty_p == target_tile_p )
{
// TODO: queue bomb moving into space
pos_t new_bomb_pos = getUpdatedPos( bomb_pos, dir );
// Set bomb at new position
[model_p setTileAtPosition:new_bomb_pos
to:bomb_p];
// Remove bomb from old position
[model_p setTileAtPosition:bomb_pos
to:empty_p];
// Bombs will continue to slide until stopped
ArcticSlideTile *target_tile_p =
[model_p getTileFromPosition:new_bomb_pos
inDirection:dir];
while ( empty_p == target_tile_p )
{
// TODO: animate bomb moving into space
pos_t new_bomb_pos = getUpdatedPos( bomb_pos, dir );
// set bomb at new position
[model_p setTileAtPosition:new_bomb_pos
to:bomb_p];
// remove bomb from old position
[model_p setTileAtPosition:bomb_pos
to:empty_p];
}
if ( mountain_p == target_tile_p )
{
// bomb pushed into mountain
// TODO: queue animation of bomb moving
// onto mountain, animate explosion
// remove bomb and mountain
[model_p setTileAtPosition:new_bomb_pos
to:empty_p];
new_bomb_pos = getUpdatedPos( new_bomb_pos, dir );
[model_p setTileAtPosition:new_bomb_pos
to:empty_p];
}
}
// The penguin cannot actually move in this turn
return NO;
}
- (NSString*) description
{
return @"Bomb ";
}
@end
@implementation ArcticSlideEmpty
- (BOOL)pushFromPosition:(pos_t)pos inDirection:(dir_e)dir
{
// If the penguin pushes onto an empty tile, he can always
// move there
return YES;
}
- (NSString*) description
{
return @" ";
}
@end</pre>
<p>I'm leaving out unfinished tile classes for clarity, but here is the model implementation:</p>
<pre>@implementation ArcticSlideModel
- (id)init
{
// Initialize the global tile objects. I messed around
// with singleton factory methods for creating a single
// instance of each of these and accessing it everywhere
// but the resulting code was too wordy to justify this.
empty_p = [[ArcticSlideEmpty alloc] init];
tree_p = [[ArcticSlideTree alloc] init];
mountain_p = [[ArcticSlideMountain alloc] init];
house_p = [[ArcticSlideHouse alloc] init];
ice_block_p = [[ArcticSlideIceBlock alloc] init];
heart_p = [[ArcticSlideHeart alloc] init];
bomb_p = [[ArcticSlideBomb alloc] init];
self = [super init];
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
board[idx_y][idx_x] = empty_p;
}
}
return self;
}
- (id)initWithLevelIndex:(int)level_idx
{
self = [self init];
// Lookup table to decode the original Polar resource
// data as strings
ArcticSlideTile *
polar_data_tile_map[POLAR_DATA_NUM_TILE_VALS] =
{
empty_p, tree_p, mountain_p, house_p, ice_block_p,
heart_p, bomb_p
};
if ( level_idx > ( num_polar_levels - 1) )
{
NSLog(@"initWithLevelIndex: bad level_idx %d!\n",
level_idx);
}
else
{
unsigned int level_data_idx = 0;
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
int polar_data_tile_val =
polar_levels[level_idx]
[level_data_idx] - '0';
if ( ( polar_data_tile_val < 0 ) ||
( polar_data_tile_val >
polar_data_max_tile_val ) )
{
NSLog(@"tile value %d out of range!\n",
polar_data_tile_val );
self = nil;
}
else
{
board[idx_y][idx_x] =
polar_data_tile_map[polar_data_tile_val];
level_data_idx++;
}
}
}
}
return self;
}
- (ArcticSlideTile*)getTileFromPosition:(pos_t)pos
inDirection:(dir_e)dir
{
pos_t updated_pos = getUpdatedPos(pos, dir);
if ( posValid( updated_pos ) )
{
return board[updated_pos.y_idx]
[updated_pos.x_idx];
}
else
{
return nil;
}
}
- (NSString*)description
{
NSMutableString *desc_str =[[NSMutableString alloc]init];
[desc_str appendString:@"ArcticSlideModel board state:\n"];
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
[desc_str appendString:[board[idx_y][idx_x]
description]];
}
[desc_str appendString:@"\n"];
}
return desc_str;
}
- (void)setTileAtPosition:(pos_t)pos to:(ArcticSlideTile*)type
{
board[pos.y_idx][pos.x_idx] = type;
}
@end</pre>
<p>It's not much yet, and it doesn't have any kind of user interface outside of <b>NSLog</b>, but my code will successfully respond to moving the penguin through trees, through open space, and pushing a bomb, which then moves into an open space, continues to slide until it comes up against a mountain, and destroys the mountain. I'm driving this with a test method like this:</p>
<pre>NSLog(@"%@\n", model_p);
// Penguin starts at 0,0, on a tree tile
pos_t penguin_pos = { 0, 0 };
// Walk the penguin south onto another tree tile
ArcticSlideTile* tile_p =
[model_p getTileFromPosition:penguin_pos
inDirection:dir_south];
NSLog(@"Penguin is facing: %@\n", tile_p);
BOOL allowed = [tile_p pushFromPosition:penguin_pos
inDirection:dir_south];
NSLog(@"Penguin allowed: %s\n", ( allowed ? "YES" : "NO" ) );
tile_p = [model_p getTileFromPosition:penguin_pos
inDirection:dir_south];
penguin_pos = getUpdatedPos(penguin_pos, dir_south);
NSLog(@"Penguin is facing: %@\n", tile_p);
// Walk the penguin east onto an empty space
tile_p = [model_p getTileFromPosition:penguin_pos
inDirection:dir_east];
NSLog(@"Penguin is facing: %@\n", tile_p);
allowed = [tile_p pushFromPosition:penguin_pos
inDirection:dir_east];
NSLog(@"Penguin allowed: %s\n", ( allowed ? "YES" : "NO" ) );
tile_p = [model_p getTileFromPosition:penguin_pos
inDirection:dir_east];
penguin_pos = getUpdatedPos(penguin_pos, dir_east);
// Try walking into a bomb, which should slide
// and blow up a mountain
tile_p = [model_p getTileFromPosition:penguin_pos
inDirection:dir_east];
NSLog(@"Penguin is facing: %@\n", tile_p);
allowed = [tile_p pushFromPosition:penguin_pos
inDirection:dir_east];
NSLog(@"Penguin allowed: %s\n", ( allowed ? "YES" : "NO" ) );
NSLog(@"%@\n", model_p);</pre>
<p>I'll think on this whole model of updates some more. Maybe it can be even simpler. And I have to consider how the penguin state will be managed, including its orientation (in the original, the penguin can face in the cardinal directions). Should I preserve that in a touch-driven game user interface?</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-17402628221734084722013-06-06T15:06:00.001-04:002013-06-06T19:46:52.418-04:00Objective-C, Day 4<p>(Warning: more non-FP content)</p>
<p>It's time to get the board representation filled out with a real board. I've only got a couple of hours left before I have to pack up my computer to leave my Undisclosed Location, but let's see if I can get a little more done. Let's review what level 1 looks like:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s1600/level_1_blown_up.tiff" imageanchor="1"><img border="0" height="120" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s640/level_1_blown_up.tiff" width="512" /></a>
<p>
Level layouts are taken from the original Macintosh Polar game created by Go Endo. These were originally MacOS resources of type 'STGE.' Let's see if we can decode them. Using ResEdit, the raw data for 'STGE' resource ID -16000 looks like:</p>
<pre>0x0000 0x0000 0x0003 0x0001
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0001 0x0000
0x0000 0x0000 0x0000 0x0000
0x0004 0x0000 0x0000 0x0001
0x0000 0x0006 0x0000 0x0002
0x0000 0x0005 0x0004 0x0005
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0001 0x0000 0x0000
0x0001 0x0000 0x0000 0x0001
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0005
0x0000 0x0000 0x0000 0x0002
0x0003 0x0000 0x0000 0x0001
0x0001 0x0000 0x0000 0x0000
0x0000 0x0001 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000 0x0000
0x0000 0x0000 0x0000</pre>
<p>There are 99 16-bit values. My best guess is that this corresponds to the 24x4 grid (96 board positions) plus 3 extras for some kind of of header of footer data (maybe the total number of hearts is indicated, for example). There are 7 unique values, so it seems extremely likely that they correspond almost exactly to our eight different tile types, with zero representing a blank space. But the counts of each type don't _quite_ match up. The first board has 8 trees, 1 bomb, 2 hearts, 2 ice blocks, 2 mountains, 3 hearts, 1 house, and 1 penguin (there is always 1 penguin), while this 'STGE' resource has: 9 ones, 2 twos, 2 threes, 2 fours, 3 fives, and 1 six. The counts are very close, so this has to represent level 1, and the the 5 almost certainly represents a heart, but I'm not clearly seeing the layout. The first vertical column goes penguin, tree, tree, tree. I don't quite see a pattern that looks like that, but resources -1599 and -15996 give me a hint that the "extra" data is at the front: they contain 0x0007 and 0x0008 as their third values. Those don't appear anywhere else so they probably don't indicate tiles. So let's try rearranging resource -16000 without the first 6 bytes, remove redundant zeroes for clarity, and looking at the values aligned by groups of 24 instead of 4:</p>
<pre>1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 0 0
1 0 6 0 2 0 5 4 5 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 2 3 0 0
1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</pre>
<p>There's the board. The left column is actually all trees -- when the board first appears, the penguin is hiding a tree. There are actually nine trees. So the encoding looks like so: empty space = 0, tree = 1, mountain = 2, home = 3, ice block = 4, heart = 5, and bomb = 6. The penguin doesn't have a value, but his starting position is probably represented by the first two values, (0,0), most likely encoded as row index, column index to correspond to row-major indexing, and there are 3 hearts to count down as the game is solved.</p>
<p>Can we validate this with the second board? Yes, it looks like there's a 4 indicating 4 hearts. In all the boards I've seen so far (the first four), the penguin is in the upper left. The fifth resource has 0, 1 for its first two values, so I'm guessing I can confirm the encoding of the penguin's position if and when I get to that stage.</p>
<p>And now to come up with a quick way to populate the board in my code. As I'm still a complete n00b in Objective-C, and on the general principle that there's no real need to make this any more clever or less obvious than it has to be, let's just use a string with the data from the resource. Let's add an init method to the interface for the model class:</p>
<pre>- (id)initWithLevelIndex:(int)level_idx;</pre>
<p>And here is some data, and an initializer method:</p>
<pre>static const int num_polar_levels = 1;
static const int polar_data_len = 96;
static const int polar_data_num_tile_vals = 7; // 0-6 inclusive
static const int polar_data_max_tile_val = 6;
static const NSString *polar_levels[num_polar_levels] =
{
@"100000000000000100000400" \
@"106020545000000000100100" \
@"100000000000000050002300" \
@"110000100000000000000000"
};
- (id)initWithLevelIndex:(int)level_idx
{
// Call our own basic initializer. This will
// result in redundant setting of board values,
// but maybe I will clean that up later.
self = [self init];
// A simple lookup table to decode the original
// Polar resource data as strings
ArcticSlideTile
*polar_data_tile_map[polar_data_num_tile_vals] = {
empty, tree, mountain, house,
ice_block, heart, bomb };
if ( level_idx > ( num_polar_levels - 1) )
{
NSLog( @"initWithLevelLayout: level %d out of range!\n",
level_idx );
self = nil;
}
else
{
const NSString* level_str = polar_levels[level_idx];
unsigned int level_data_idx = 0;
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
NSRange range = NSMakeRange(level_data_idx, 1);
const NSString * item_str =
[level_str substringWithRange: range];
int polar_data_tile_val = [item_str intValue];
if ( polar_data_tile_val >
polar_data_max_tile_val )
{
NSLog(@"tile val %d out of range!\n",
polar_data_tile_val );
self = nil;
}
else
{
board[idx_y][idx_x] =
polar_data_tile_map[polar_data_tile_val];
level_data_idx++;
}
}
}
}
return self;
}
</pre>
<p>Hmmm, that seems overly complicated. There probably is a better, more idiomatic Objective-C way to use NSStrings for that, but I'm tempted to just write it with a basic C string. Using NSString objects in this context didn't even really help me catch bugs or avoid crashes, since I had forgotten to initialize a heart object and the result was hitting a nil object pointer at runtime and crashing, pretty much the same result as dereferencing a null pointer in straight C except with a better error logged. I'm a little disconcerted by Objective-C's inability to allocate objects on the stack, but that comes down to the aforementioned "thin veneer" over C. I don't really care about the overhead in using method dispatch in this simple piece of code operating on such a small amount of data, but I do care about simplicity. Just to compare, here's a more straightforward C implementation of that inner loop:</p>
<pre>static const char *polar_levels[num_polar_levels] =
{
"100000000000000100000400"
"106020545000000000100100"
"100000000000000050002300"
"110000100000000000000000"
};
int polar_data_tile_val = level_str_p[level_data_idx] - '0';
if ( ( polar_data_tile_val < 0 ) ||
( polar_data_tile_val >
polar_data_max_tile_val ) )
{
NSLog(@"polar data tile value %d out of range!\n",
polar_data_tile_val );
self = nil
}</pre>
<p>Maybe the lesson here is "use Objective-C objects only when objects are a win."</p>
<p>I'm going to continue with this project, developing the code to handle the interactions of objects on the playing field and eventually the user interface. However, now that my week away from home is done, I might not be able to make progress very quickly. Stay tuned -- I'll post what I can, when I can. As always, if you have any comments or questions, I'm happy to have feedback.</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-40747337246186863652013-06-05T01:05:00.001-04:002013-06-05T14:29:19.127-04:00Objective-C, Day 3<p>(Warning: non-FP content)</p>
<p>So, this is day 5 in my Undisclosed Location and I haven't gotten much done -- I'm still engaged in a job search, and spent about eight hours working on a "take-home test" for an employer (with a few interruptions), and I'm pursuing more leads, and I'm trying to socialize with my hosts occasionally, so there are some distractions. But I've got enough information to go on to start implementing something original.</p>
<p>What I want to implement is a small game. I'll get as far as I can in the back-end code today (the Model and Controller parts of the MVC "trinity") and we'll see just how productive I really am in Objective-C. I read most of Objective-C Programming by Aaron Hillegass last night -- it's a very quick read for someone well-versed in C, and it reiterates parts of the iOS Programming book. I haven't covered protocols, categories, blocks, or run loops, but I think I can get by without those things for now.</p>
<p>Many years ago there existed on old-school MacOS a small game called "Polar." It was a very simple game, written by a guy (Go Endo) who was probably a student at the time, but I was fond of it -- fond enough to save it for 23 years, with the intention of studying its design and re-implementing it in the future. (In fact, I've saved a lot of old bits and bobs like this). I made notes of how to beat the first 3 levels (it was one of those "incredibly simple game play, but maddeningly tricky" games), drew out the levels, made notes on how the objects behaved, etc. I haven't been able to run that game for a long time, but today I just got it working under SheepShaver. Here's what level 1 looks like (blown up a bit):</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s1600/level_1_blown_up.tiff" imageanchor="1"><img border="0" height="120" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXJ41mNchHHe6v6tn_E0B3t4rHIl7mjTvm02l_TBz8T90o_jK5pcWej_XXqyIkbm0vHjdgIn8IbsZzdjx5LfBftpqVYZ0OAIYkT_E70oNTemtYLkigF0mUqAiEkdhhtuW30Xp9/s640/level_1_blown_up.tiff" width="512" /></a>
<p>The penguin is your avatar. The rest of the objects are ice blocks, trees, hearts, bombs, mountains, and houses. The world is a sheet of ice. You can walk around on the ice. You can walk through trees. Some objects (trees, mountains, and houses) can't be moved. Bombs, hearts, and ice blocks move without friction -- if you push them, they will keep going until they hit the edge of the world or another object. If an sliding ice block hits another object, it stops. If you push it against another object, it crumbles and disappears. The penguin can walk through trees, but other objects can't. Bombs will blow up mountains when they slide into them. Everything else simply stops them. The goal of the game is to slide all the hearts into a house (cute, huh?) But because the ice is frictionless, it's incredibly easy to get objects stuck against walls or corners where you can no longer move them the way you need to. So you have to carefully plan out your moves, and if you get stuck, there's an option to start the level over.</p>
<p>I should mention that the original game had a copyright notice (1990), and was shareware ($2.00). I can't remember if I ever sent the author $2.00. I'm not sure how he would feel about me taking apart and trying to re-implement his game, or whether he'd try to assert that copyright prevented me from doing so, but I'll assume he's a nice guy and wouldn't care as long as I don't charge for it, and go ahead, on the theory that easier to ask forgiveness than permission. I was not able to find him online -- maybe "Go Endo" was a pseudonym?</p>
<p>Back in 1991 I came up with a C++ class design (actually, it doesn't quite look like C++; I think it was written using THINK C's object-oriented extensions, which are sort of lost in the mists of time to me -- what is that <b>indirect</b> keyword? What did <b>#pragma options(virtual)</b> do? I don't remember for sure, but let's see if we can come up with an Objective-C implementation. The objects, other than the penguin, which can face in different directions, don't seem to have any real distinct properties except for their locations in the board, so I'm tempted not to take the obvious route and implement a board full of instances of the objects. I'm more inclined to just define a class for the board, and let it encapsulate most of the game logic. For the objects themselves, I'd like to just make references (pointers) to their classes (the class object) rather than putting them in a container. That's apparently not really possible -- there are no predefined singletons for the class objects that are accessible at run-time the way there are for NSNull. So I have to make some (sort of) singletons.</p>
<p>Here's what I've got today:</p>
<pre>@interface ArcticSlideTile : NSObject
// Not necessarily useful yet, but I am guessing it might
// be helpful to have a separate base class at some point.
@end
@interface ArcticSlideTileStateless : ArcticSlideTile
// In implementation, there will be a single shared instance.
@end
@interface ArcticSlideBomb : ArcticSlideTileStateless
// Bombs can be pushed and will slide until they
// hit an object and stop. If the object is a mountain,
// both bomb and mountain are destroyed and
// there should be an animation. If another object
// hits a bomb it stops (I'm not sure you can test this
// combination in the original game with the board layouts
// available
- (NSString*) description;
@end
@interface ArcticSlideEmpty : ArcticSlideTileStateless
// The penguin can walk on empty space. Pushable objects
// on empty space are on ice and they slide until something
// stops them.
- (NSString*) description;
@end
@interface ArcticSlideHeart : ArcticSlideTileStateless
// When a heart hits a house the heart disappears (getting
// all the hearts into the house is how you win the game).
// Otherwise they cannot be destroyed, and slide like other
// slidable items.
- (NSString*) description;
@end
@interface ArcticSlideHouse : ArcticSlideTileStateless
// Houses cannot be pushed and stop other objects
// except hearts. When a heart hits a house the heart
// disappears (getting the hearts into the house is
// how you win the game). So the model should keep track
// of the number of hearts on the board and trigger a
// "win the level" behavior when the last heart is
// destroyed.
- (NSString*) description;
@end
@interface ArcticSlideIceBlock : ArcticSlideTileStateless
// Ice blocks can be pushed and will slide until they
// hit an object and stop. If they are pushed directly
// against an object they will be crushed (there should
// be an animation) and disappear.
- (NSString*) description;
@end
@interface ArcticSlideMountain : ArcticSlideTileStateless
// Mountains cannot be moved and are destroyed by bombs.
- (NSString*) description;
@end
@interface ArcticSlidePenguin : ArcticSlideTile
// The penguin is the avatar. It has the special
// quality of being able to face different directions
// in the original game, although that's because you
// can click near him to turn him and make him walk in
// different directions. In a touchscreen implementation
// I'm not sure how this should be implemented -- maybe
// he can slide in discreet steps. The penguin has the
// ability to walk through trees. We might want to
// implement this temporary state using using an
// "override" object reference in the model. Sliding
// objects might be implemented the same way.
typedef enum {
north, south, east, west
}penguinDirection_e;
@property penguinDirection_e facing;
- (NSString*) description;
@end
@interface ArcticSlideTree : ArcticSlideTile
// Trees cannot be pushed or destroyed and stop
// all sliding objects, but the penguin avatar
// character can walk through them.
- (NSString*) description;
@end
static const int board_width = 24, board_height = 4;
// The short board design is part of what makes it
// so easy to get sliding objects stuck against the
// edges of the world or in corners where you can no longer
// get around to the other side to push them. We could
// consider a bigger board later and maybe implement the
// original puzzles surrounded by impassible water.
@interface ArcticSlideModel : NSObject
{
ArcticSlideTile* board[board_height][board_width];
}
- (id)init;
- (NSString*) description;
@end
@implementation ArcticSlideTile
{
}
@end
@implementation ArcticSlideTileStateless
{
}
@end
@implementation ArcticSlideBomb
- (NSString*) description
{
return @"Bomb";
}
@end
@implementation ArcticSlideEmpty
- (NSString*) description
{
return @"Empty";
}
@end
@implementation ArcticSlideHouse
- (NSString*) description
{
return @"House";
}
@end
@implementation ArcticSlideIceBlock
- (NSString*) description
{
return @"Ice Block";
}
@end
@implementation ArcticSlideMountain
- (NSString*) description
{
return @"Mountain";
}
@end
@implementation ArcticSlidePenguin
- (NSString*) description
{
return @"Mountain";
}
@end
@implementation ArcticSlideTree
- (NSString*) description
{
return @"Tree";
}
@end
@implementation ArcticSlideModel
{
ArcticSlideBomb *bomb;
ArcticSlideEmpty *empty;
ArcticSlideHeart *heart;
ArcticSlideHouse *house;
ArcticSlideIceBlock *ice_block;
ArcticSlideMountain *mountain;
ArcticSlidePenguin *penguin;
ArcticSlideTree* tree;
}
- (id)init
{
bomb = [[ArcticSlideBomb alloc] init];
empty = [[ArcticSlideEmpty alloc] init];
heart = [[ArcticSlideHeart alloc] init];
house = [[ArcticSlideHouse alloc] init];
ice_block = [[ArcticSlideIceBlock alloc] init];
mountain = [[ArcticSlideMountain alloc] init];
penguin = [[ArcticSlidePenguin alloc] init];
tree = [[ArcticSlideTree alloc] init];
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
board[idx_y][idx_x] = empty;
}
}
return self;
}
- (NSString*)description
{
NSMutableString *desc_str =
[[NSMutableString alloc]init];
[desc_str appendString:@"ArcticSlideModel board state:\n"];
for ( unsigned int idx_y = 0;
idx_y < board_height; idx_y++ )
{
for ( unsigned int idx_x = 0;
idx_x < board_width; idx_x++ )
{
[desc_str
appendString:[board[idx_y][idx_x] description]];
[desc_str appendString:@" "];
}
[desc_str appendString:@"\n"];
}
return desc_str;
}
@end
</pre>
<p>My quiet time at my undisclosed location ends tomorrow. I'm not sure I'll be able to get back to this for a few days. I haven't gotten nearly as much done with this as I've hoped. I've been distracted by a lot of job-search things. But hey, it's a start!</p>
Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-8397989279329461072013-06-03T22:57:00.001-04:002013-06-04T10:35:51.102-04:00Objective-C, Day 2<p>(Warning: non-FP content)</p>
<p>So today I'm working on chapter 3 in <i>iOS Programming</i>. This is about memory management. I have vague memories of manual reference-counting using retain and release in earlier experiments with Objective-C, but this book teaches ARM (Automatic Reference Counting). You enable ARM when you configure an XCode project of iOS.</p>
<p>The idea behind object references (well, pointers in iOS) and trees of objects and their owners is not new to me. And here they they still do not clarify whether a statement like <b>items = nil</b> actually invokes runtime behavior to destroy objects. I believe it does not. When I override a <b>dealloc</b> method to log, I see that the <b>dealloc</b> methods are called when the curly brace at the end of @autoreleasepool is reached. This makes sense, as in C it is the point where variables go out of scope. So reference-counting bookkeeping must be invoked then. It does not seem to be possible to step in with the debugger at this point to view what is happening, though -- Apple's Objective-C runtime is proprietary software.</p>
<p>We next get into weak references. There's a <b>__weak</b> specifier that can appear as part of an object pointer declaration, and <i>iOS Programming</i> says that "an interesting property of weak references is that they know when the object they reference is destroyed... the [parent object] automatically sets its [child object] instance variable to <b>nil</b>." I'm going to have to read more about that. I really wish this book were more precise in its language. There's another specifier, <b>__unsafe_unretained</b>, which is not set -- and so a pointer to a destroyed object could still be dereferenced. I suppose I should just be happy that this works and use it, but I'm the type to want to know what is going on at the register level. Apparently ARC (the "automatic" in reference-counting) is all due to some amazing work done in clang, where the static analysis actually figures out all the possible points of object creation and deletion and can wrap up your reference-counting for you. That seems like a great development -- because I've never quite liked how garbage collectors (at least, those without hardware support), no matter how efficient they are, had to actually be implemented, looking at dumb machine pointers. It seems to me that there could be room in purely-GC'ed languages for this kind of static analysis. But I haven't thought very hard about that yet.</p>
<p><i>Properties</i> seem to be a shorthand, asking the compiler to provide getters and setters. There's a great example as to how much code this can eliminate. There's a strange wart in that we are asked to specify (nonatomic) in every property, because that is not the default setting. Presumably this is to support multiple threads accessing the object. Again, a dark corner to look into.</p>
<p>For a little refresher, I took a break by reading the first few chapters of Brad Cox's book. He outlines his vision of a software IC, along the lines of a hardware C, that would support reusability primarily through late binding, limited interfaces, and wrapping up functionality with data so that clients don't have to write the operations on an object's data type. It's an interesting vision.</p>
<p>Cox writes of early Objective-C:</p>
<blockquote>Objective-C adds precisely one new data type, the object, to those C provides already, and precisely one new operation, the message expression.</blockquote>
<p>Cox's book indicates that early versions of Objective-C used an intermediate preprocessor step, between the C macro-preprocessing step and the regular C compiler. If you are my age you might recall that, early on, C++ was treated similarly, with a program called <a href="http://en.wikipedia.org/wiki/Cfront">CFront</a>. This is no longer the case with either Objective-C or C++, although this approach lives on in tools like <a href="http://en.wikipedia.org/wiki/Qt_(framework)">Qt, with its Meta Object Compiler</a>, or moc).</p>
<p>Cox describes the pragmatic design of Objective-C:</p>
<blockquote>One of Objective-C's key features is that it is always possible to bypass the object-oriented machinery to access an object's private information directly. This is one of a hybrid language's greatest theoretical weaknesses and one of its greatest pragmatic strengths. Low-level code is often best developed in a conventional manner, exploiting static binding to obtain high machine efficiency and strong type checking. Conversely, user-level code is often best written as objects. It is important that these levels interface smoothly and efficiently.</blockquote>
<p>There is an interesting passage about object identifiers. In a slight muddling of his earlier statement he writes that "objects are identified by a new Objective-C data type called an id, or object identifier." In practice, though, this isn't really a new data type <i>per se</i>. The address (a pointer to) an object is this identifier. The veneer over C is so thin that, he writes, it would have been perfectly feasible to implement the dynamic message sends using straightforward C language calls like <pre>reply = _msg_(aReceiver, "aMessage", argument1, ...)</pre> (I assume he'd use C's <a href="http://en.wikipedia.org/wiki/Varargs.h#.3Cvarargs.h.3E">variable-length argument list</a> mechanism here), but for efficiency he wanted to avoid string comparison in the dispatch mechanism. Cox was quite aware of the reaction that messages like [anObject do:arg1 with:arg2] would inspire in C programmers, writing "the convention seems strange to those accustomed to conventional function call syntax, and frankly, I find it a mixed blessing."</p>
<p>In this formulation, Objective-C classes were still objects, and class methods were called "factory methods" (but I'm peeking ahead a number of pages, so there might be some differences from their current incarnation), as distinct from instance methods. Cox writes "...the programmer conceives the initial object... the loader gives it life by installing it in memory... this is done once for each class in the system. These primal objects are called factory objects... every factory's name is published in a global variable."</p>
<p>Cox is a very thoughtful writer and he presents a minimalist view of what an object-oriented language requires in order to provide the most basic advantage of OOP. He writes:</p>
<blockquote>One last time: the only substantive difference between conventional programming and object-oriented programming is the selection mechanism. This is not to minimize its importance, but to demystify what is basically a very simple notion. Its significance is that it moves a single responsibility across the boundary between the consumer of a service and the supplier of that service. In conventional programming, the consumer is responsible for choosing functions that operate properly on the data managed by that service. The selection mechanism moves that single responsibility off the consumer and onto the supplier. In this small change lies all the power of the technique.</blockquote>
<p>That really caused me to, as they say, nearly drop my monocle. Could this really be where most of the advantage, such as it is, imperfectly realized, understood, and applied, of OOP comes from?</p>
<p>The mainstream business world got C++ instead, a mash-up of C and <a href="http://en.wikipedia.org/wiki/Simula">Simula</a>, and then Java instead, <a href="http://www.infoworld.com/d/developer-world/java-becoming-new-cobol-204">the Cobol of object-oriented programming languages</a>. I was not pleased. As I consider my career I also consider which implementation languages I should focus my efforts on, for the next decade. After exposure to Haskell it's hard to believe that, ultimately, functions -- without explicit state -- won't prove to be a cleaner reusable element than classes, whatever kind of binding they use. And don't get me wrong -- I like classes. I'm pretty certain that I'll still be writing C code, at least occasionally, in ten years. I'd prefer to be writing less C++. But what I'd really like is to move on -- to pick a "<a href="http://skillsmatter.com/podcast/agile-testing/bobs-last-language">last programming language</a>." Objective-C isn't that, for me -- it's too imperative, and can't truly be made safe, just <i>safer</i>. I'm enjoying it in this context, but would Objective-C even be an viable option outside of the Apple ecosystem? It doesn't seem to have gained much adoption. The state of GnuStep doesn't seem terribly robust. And so my career-long quest for a Better Way continues, while at the same time trying to gain facility with all the Good Ways along the way.</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0tag:blogger.com,1999:blog-21500237.post-3403107382803692192013-06-02T12:40:00.000-04:002013-06-04T10:30:36.429-04:00Objective-C, Day 1<p>(Warning: more non-FP content).</p>
<p>So I'm in an undisclosed location away from home specifically to spend a few quiet days focusing on programming. I had a goal to teach myself enough iOS programming to get a small demo app submitted to the app store by the end of the week. I'm not sure I'll manage that, but I'm learning. I have 3 relevant books with me: <i>iOS Programming: The Big Nerd Ranch Guide (Third Edition, Second Printing, August 2012)</i>, by Joe Conway and Aaron Hilegass; <i>Objective-C Programming: The Big Nerd Ranch Guide (Second Printing, January 2012)</i>, by Aaron Hillegass; and a much older book, <i>Object Oriented Programming: An Evolutionary Approach</i> (Reprinted with corrections August 1986), by Brad J. Cox. Brad Cox is the guy who created Objective-C, and although the language he describes in his book is not the same as modern Objective-C, I thought it might give me some insight into the language design. I own, but did not bring with me, a number of books on Smalltalk including the "blue book" (<i>Smalltalk-80: The Language and its Implementation</i> by Adele Goldberg and David Robinson). I wish I had brought it! But on the other hand, maybe it's best that I not go too far down a rabbit hole into the history of programming languages and the way language constructs are adopted over time by other languages -- even though it's one of my favorite subjects.</p>
<p>So far, I've worked through a few chapters of each. I'm not really here to write reviews of the books; let's just say they have their various strengths and weaknesses. But here are some thoughts on the process so far.</p>
<p>1. Learning Objective-C is a little frustrating (that's good, actually -- most languages are a LOT frustrating to learn).</p>
<p>1a. One of the fundamental strengths of C, as a kind of portable assembly language, is that almost everything about the behavior of your program is right on the surface. I don't mean that there aren't sometimes surprising behaviors. But as far as the usage of memory and the order of execution, C is pretty easy to reason about, with a few minor exceptions (for example, the switch statement implies that <a href="http://en.wikipedia.org/wiki/Switch_statement#Compilation">the compiler may create conditional tests whose order and number don't match exactly what is indicated in your source code</a>).</p>
<p>1b. Objective-C hides some functionality in a way that C programmers may find disturbing. Those coming to it from another language might not even notice that this is an issue, since they might expect that the runtime is doing a lot of implicit things. Or they might not think about it at all.</p>
<p>1c. The syntax of Objective-C is a weird mash-up of Smalltalk and C. It has strange aesthetics.</p>
<p>1d. Nevertheless, it is pretty clear that Objective-C is an enormously pragmatic and highly successful language. Therefore, from the perspective of a language designer or someone who studies the history and design of programming languages, it would be an enormous mistake to dismiss it because of its hybrid design. By all accounts it is an extremely productive language once a certain level of expertise is achieved.</p>
<p>2. These books are not necessarily written for someone who knows other languages (such as C and C++) well, and that is also frustrating.</p>
<p>2a. The <i>iOS Programming</i> book uses language imprecisely here and there and it is driving me to distraction.</p>
<p>2b. This is not necessarily their fault; terminology is often only precise <i>within a specific domain</i> and has imprecise meaning or different meaning outside of that domain.</p>
<p>3. Now, some details.</p>
<p>3a. The sentence "The class acts as a factory that creates instances of that class." This needs a little unpacking. The language of "factories" seems to <a href="http://www.oodesign.com/factory-pattern.html">come from design patterns</a> and is also big <a href="http://en.wikipedia.org/wiki/Factory_method_pattern">in .NET and enterprise-y Java</a> as the concept of a factory method. But this sentence actually buries a few surprises for C++ programmers. The first is that classes are objects -- they actually have a distinct run-time representation. And instances have a different run-time representation than classes. This seems reminiscent of the concept of prototypes in languages like NewtonScript, Self, and Omega, where objects can inherit from other objects, but it is different as well, since in NewtonScript a prototype is just another instance of a fundamental container data structure, a frame. I'm not sure yet whether in Objective-C you can create a class at runtime, but I wouldn't be surprised.</p>
<p>3b. From Smalltalk: a method call is triggered by sending an object a message. This implies more run-time overhead than a function call, even a virtual function call from C++, although no doubt this has been highly optimized in the runtime. A message-sending expression can return a value. So, for example, it seems to be idiomatic Objective-C to create an object with a statement like</p>
<pre>Object *obj = [[Object alloc] init]</pre>
<p>This wraps up quite a bit of behavior: Object is used as a type for a simple pointer variable obj, and also as a reference to the runtime Object class object. Sending Object the alloc message returns a new instance of an object, which can then be used as the receiver for the nested message send, sending it the init message, which returns its receiver.</p>
<p>3c. This "message" is a distinct thing, and seems to either be the same as or closely related to a "selector." Syntactically a selector is something like "methodNamePart1:argument1Name:argument2Name" and a selector like this is compatible with a message-sending statement like "[receiver methodNamePart1: argument1Name: argument1 argument2Name: argument2]." This implies (but I have not seen clearly explained, yet) that the compiler has to break all that down and keep track of it. <i>iOS Programming</i> mentions "arguments interposed into the selector." This seems to be similar to using required keyword arguments as in Dylan which, I think, borrowed the idea from CLOS. I think the packed string with colon-separated selectors might be an innovation in Objective-C; I'm not certain.</p>
<p>3d. <i>iOS Programming</i> mentions that an expression like <b>obj_p = nil</b> "destroys the object and sets its instance variable to nil." If this is accurate, and they don't just mean that the object is "cut loose," this implies hidden run-time behavior that I would like to see explained much more fully.</p>
<p>3e. Sending a message to nil is apparently a no-op at run-time. This scares me a bit; won't that tend to hide a situation where we might actually <i>want</i> a crash?</p>
<p>3f. I like the extensions to printf format strings: %@ representing "any object," producing a string generated by calling the object's <b>description</b> method.</p>
<p>3g. I'm not sure I understand the need for NSNull, if the compiler can already wrap special run-time behavior around <b>nil</b>. But I don't claim to understand everything yet.</p>
<p>3e. Instance variables are not included in class objects. That's... interesting. It sounds a bit like how static methods and fields in a C++ class are available without creating an instance.</p>
<p>3f. Getters and setters are not created for you, and by convention (which can be important, apparently, for compatibility with code that uses introspection) are called <b>set+instance var name</b> and <b>the instance var name</b>. I have a great distaste for different things that have the same name.</p>
<p>3g. Some interesting bits and pieces to digest further, later: instance methods; initializers; <b>id</b>, <b>isa</b>, <b>self</b>, <b>super</b>, and the "designated initializer." <i>iOS Programming</i> talks about the importance of the designated initializer for some time, which is a shame because it also doesn't seem to explain in any way how you designate an initializer.</p>
<p>3h. Class names seem to be all in one namespace -- in other words, I don't see evidence of a real module system. I know from watching this process in other languages that it can be very difficult to retrofit a language with a module system later.</p>
<p>That's about all I've got for now. I'm sure it will make more sense as I press on, for better or worse!</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com5tag:blogger.com,1999:blog-21500237.post-35195546306636384372013-05-31T17:24:00.002-04:002014-12-05T16:32:44.953-05:00An Interesting Interview Question<p>(Warning: some non-FP content!)</p>
<p>So yesterday I had a job interview for a developer position and I got the chance to put my money where my mouth is, so to speak, about my C and C++ programming skills. I was asked to write 3 functions given specifications including their prototypes, and to review a piece of C++ sample code. The interviewers left me alone with some paper for fifteen minutes or so.</p>
<p>There were four tasks. I scrambled around at the first one, started down a blind alley, started to get nervous, realized I was getting nervous, and decided to move on to the next questions and come back to the first question if I could. So I'll reveal that one last.</p>
<p>The second task was to write a "population count" -- to count the one bits in an unsigned char. This is a common operation in real-world code that operates on packed data structures such as tries. I chose a very simple lookup-table approach, with a table to look up values nybble-wise. Easy-peasy. The function itself then becomes a one-liner. "Full marks," as they say in some countries.</p>
<p>The third task was to write a function that tests whether the CPU it is running on is big-endian, or little-endian. If you don't know what that means, I'm not going to explain it in great detail here, but it refers to the way that the individual bytes of multi-byte values are laid out in memory. You can write quite a bit of code without running into endian problems, but it becomes an issue if you need to exchange data over a network or across a bus between processors that store their data differently. Fortunately I have written quite a few drivers, so this one was also easy.</p>
<p>The last task was to find errors and questionable practices. There were a lot of them -- I marked up my page with <a href="http://www.osnews.com/story/19266/WTFs_m">several "WTFs?"</a> They weren't all errors that a compiler would complain about. Fortunately I've studied C++ extensively -- I used to subscribe to <i><a href="http://en.wikipedia.org/wiki/C%2B%2B_Report">C++ Report</a></i> -- and I was able to talk about several design issues, ranging from the lack of a virtual destructor in a base class to failure to properly implement the necessary constructor, copy constructor, and assignment operator. There was a problem with a const method. There was a pointer aliasing problem. There were a few other small issues I did not notice. I missed an issue: dynamic_cast can return NULL. I missed this because I have never had to use that sort of run-time introspection in C++, although one of my interviewers pointed out how it can be useful and necessary for adding test functionality to a framework. Overall, I think I got most of the credit for this one.</p>
<p>The first task, the one I botched, was to write a function to reverse a standard null-terminated C string, in place. Wow, the world loves nothing more than to humble us now and then, doesn't it?</p>
<p>Right off the bat, I became confused because of the prototype for the function. The question indicated that the first parameter would be a pointer to a zero-terminated string, but the second parameter was to be a size_t type -- a buffer size. I suppose this is analogous to the standard C library routines <b>strn*</b>, which are safer versions of the old <b>strcpy</b>, <b>strlen</b>, etc. These versions take a number indicating how far the function can travel in memory before bailing out -- giving a sort of "backup plan" in case the incoming string is not properly null-terminated. These are certainly better than the old functions that can rip through memory, or leave your code vulnerable to a variety of stack-smashing and buffer-overflow exploits. But to me there's something inherently horrible about a function with such a contradictory "contract" -- it is designed in such a way that it will <i>hide</i>, or at least give safe harbor, to bugs in the code that calls it. It has the information it needs to report that it has been called with an unterminated string, but there is no provision to return an error code, and the assignment did not indicate what I should do if the incoming string is not terminated. Presumably I'm not supposed to crash the computer -- although with no way to return an error, forcing a crash immediately is really the safest possible option!</p>
<p>The "safer" standard library function <b>strnlen</b> receives a value telling it how many characters it should count before it bails out, and returns a value indicating how many characters it actually counted. If you get back the same number you provided, it means that the incoming string is not properly null-terminated. You can (and hopefully will) do something with that information. But the "safer" <b>strncpy</b> doesn't provide any indication that it has been handed a source string that isn't null-terminated, and so can leave the destination filled with an unterminated string. That's inherently unsafe. The prototype given makes this function a little like <b>strncpy</b>.</p>
<p>So while my brain was chewing on all that in the background, I started trying to get something down on paper, writing a shell for the function, to dispose of some possible error conditions first. And I confused myself further.</p>
<p>In the bad old days, <b>size_t</b> was not guaranteed to be unsigned, so it was possible that the provided buffer size could be less than zero. That's not the case in standard C, but I coded to test for it anyway. Most compilers would tell me that I was testing for a condition that can't happen, fortunately.</p>
<p>Next, I tested for whether I could bail out early -- whether the provided buffer size value is less than or equal to 1. I'm not sure if this would be a performance win -- it depends a lot on the sizes of the string that the function will be given. But I wanted to show that I was at least thinking about these different possible cases.</p>
<p>And then it was time to write the meat of the function. I had my heart set on writing a recursive solution. Why? To show off, maybe, even though this isn't actually a very practical solution in C. But more likely, because I've gotten used to reversing lists in languages like Scheme and Haskell that use Lisp-style lists. Which... are not at all like plain old arrays of bytes. But I was determined. To show that I was at least aware that recursive functions can fail when they use too much stack space, invented a constant, MAX_STACK_SPACE_ALLOWED, and made sure my buffer size didn't exceed it. So then I had several error-checks and had filled most of the page. There was nothing else I could do but write the recursive helper function to reverse the string.</p>
<p>And I realized that it has been a long time since I wrote something like that in plain C I was still chewing over what to do with the buffer length parameter, and wondering if I was missing something fundamental about the problem. And so I panicked and bailed out, feeling really stupid. Stupid brain! How could you let me down like that?</p>
<p>I had some more time to think about it today, and play around with some code, and think about the "contract" for the function and just why I got stuck. The idea behind a recursive reverse of a list is that you recurse to the end of the list, and then build up a list of the elements in reverse order as the recursion "unwinds." In Scheme, something like this:</p>
<pre>(define (my-reverse lat)
(if (null? lat)
'()
(append (my-reverse (cdr lat)) (list (car lat)))))</pre>
<p>C doesn't do the data-structure bookkeeping for you. Recall that we're supposed to the reverse <i>in place</i>. This solution starts with an empty list and creates new cons cells to add to it. And of course a list doesn't look like a primitive string of bytes. So I've got to get my head back in the C game.</p>
<p>As a warmup, let's write a recursive solution that uses an auxiliary buffer for the output, because that sounds easier to me. First, I want a routine to handle some special cases, which will then call a recursive function. It is at this point that I have to figure out what I'm going to do with an unterminated string. My answer: I'm going to terminate it. You're terminated, sucker. Yes, I'm going to overwrite a character of the data you passed me. Dude, where's my data? No, DUDE! Where's my string terminator?</p>
<p>Is that the right answer? I don't know. Actually, I'm pretty sure that this is <i>not</i> what the guys that gave me the task had in mind. In retrospect I think it probably would have made more sense to just use strnlen to get a "working length," and just reverse that many characters. But I think the bigger problem is that asking for a function with that prototype is <i>asking the wrong question</i>. It's a guaranteed "WTF?" for <i>someone</i>. Anyway, here's the "preamble" error-checking code as I wrote it today, for working with a function that returns the reversed string in an auxiliary data buffer:</p>
<pre>void ReverseString( char *str_p, size_t buffer_size )
{
if ( NULL == str_p )
{
printf( "NULL pointer!\n" );
return;
}
else
{
unsigned long len = strnlen( str_p, buffer_size );
if ( buffer_size == len )
{
str_p[buffer_size - 1] = '\0';
len--;
printf( "Terminating your string for you!\n" );
}
/* Recursive with an auxiliary array */
char *str_out_p = (char *)( malloc( buffer_size ) );
if ( NULL == str_out_p )
{
printf( "malloc failed!\n" );
return;
}
else
{
strncpy( str_out_p, str_p, buffer_size );
printf( "Before: %s\n", str_p );
ReverseStringAuxHelper ( str_out_p, str_p );
printf( "After: %s\n", str_out_p );
free( str_out_p );
}
/* This doesn't actually meet the requirements... */
}
}</pre>
<p>So let's write ReverseStringAuxHelper now. Something like this:</p>
<pre>void ReverseStringAuxHelper( char *str_out_p, char *str_in_p )
{
/* Do some setup, and call a recursive helper */
}</pre>
<p>Our basic strategy for recursive calls is clear: we want to call ourselves on a shorter substring of the input string, until we hit a NUL. And then... build up the data to return. But how do we do that? As we "unwind" the call stack, we will have a series of pointers to characters in the input string, in reverse order. But we want to write them into the outgoing string in <i>forward</i> order. To keep track of the index into the auxiliary data structure we could use a global (a file-scope variable, maybe declared <b>static</b>). Gag me with a spoon. No, let's use a local. You can't nest functions in C; you don't have lexical closure. But we can do something like this (get your barf bags ready):</p>
<pre>void ReverseStringAuxHelper( char *str_out_p, char *str_in_p )
{
char *str_out_walking_p = str_out_p;
ReverseStringAuxRecursive
( &str_out_walking_p, str_in_p );
}</pre>
<p>We can pass the address of the local pointer variable, to allow the recursive function to <i>modify</i> it -- so it can use the pointer, and increment its value. The recursive function now has a prototype that looks like this:</p>
<pre>void ReverseStringAuxRecursive( char **str_out_p_p,
char *str_in_p );</pre>
<p>Note the double-asterisks: a pointer to a pointer. And now the whole function:</p>
<pre>void ReverseStringAuxRecursive( char **str_out_p_p,
char *str_in_p )
{
if ( '\0' != *str_in_p )
{
ReverseStringRecursiveAuxHelper( str_out_p_p,
str_in_p + 1 );
**str_out_p_p = *str_in_p;
*str_out_p_p += 1;
}
}</pre>
<p>Good heavens. That is.. inelegant. In C++ we could do that by reference, at least, which would clean the appearance of the pointer expressions, but that really just sweeps it under the rug. It works, but can we do better? In fact, after sleeping on it for a while, I woke up abruptly with a prettier solution in my head. The key insight was realizing that there is no good reason I can't recurse with two parameters that are each changed to bring us closer to the terminating condition. We have already calculated the length of the string, so why don't we use that to figure out the terminating condition?</p>
<pre>void ReverseStringAux2Recursive( char *str_out_back_p,
char *str_in_fwd_p, char *str_in_term_p )
{
if ( str_in_fwd_p < str_in_term_p )
{
*str_out_back_p = *str_in_fwd_p;
ReverseStringAux2Recursive( str_out_back_p - 1,
str_in_fwd_p + 1, str_in_term_p );
}
}</pre>
<p>The idea here is that we will recurse on the input string, walking forwards through it and ending when we reach a supplied end pointer, and copying characters into the output string walking backwards. It's tail-recursive, which is nice (I'll talk about that a little more later). We could let the function write the terminating NUL by changing the test to read</p>
<pre>if ( str_in_fwd_p < str_in_term_p )</pre>
<p>But if we did that, we'd wind up writing a terminating NUL <i>before</i> the first character in the output string. We don't want to do that, so we need a special case for this. Let's just let our helper function do it.</p>
<pre>void ReverseStringAux2Helper( char *str_out_p,
char *str_in_p, unsigned long len )
{
/*
The caller must guarantee that the
output string can hold len + 1 chars
*/
ReverseStringAux2Recursive( &str_out_p[len - 1],
str_in_p, &str_in_p[len] );
/* Write the terminator in the output string */
str_out_p[len] = '\0';
}</pre>
<p>That doesn't look too bad. We make use of the fact that we've already calculated the length of the string. Now, that we've figured out how to do this with two changing pointers, can we do that in place? Yes, we can:</p>
<pre>void ReverseStringInPlaceRecursive( char *fwd_p,
char *back_p )
{
if ( fwd_p < back_p )
{
char temp = *fwd_p;
*fwd_p = *back_p;
*back_p = temp;
ReverseStringInPlaceRecursive(fwd_p + 1,
back_p - 1);
}
}
void ReverseStringInPlaceHelper( char *str_p,
unsigned long len )
{
ReverseStringInPlaceHelper( str_p,
&str_p[len - 1] );
}</pre>
<p>That's longer, but most of the body of the recursive function is just devoted to swapping characters using a temp value, before the tail recursion. But what's going on with</p>
<pre>if ( fwd_p < back_p )</pre>
<p>? Well, I'm glad you asked. Note that we're swapping characters. We walk along the string, going backwards, swapping characters from the front of the string, going forwards. But then a funny thing happens. The pointers meet in the middle, and cross. In other words, you want "ABC" to become "CBA" but if you don't stop the reversing process at "B", the left and right sides of the string are swapped again, giving you "CBC." The resulting string is <i>palindromic</i> -- it reads the same forward as backwards -- and so reversing it again leaves it unchanged -- but that's not what you want. Run this in an interactive debugger if you can -- it's interesting to watch. Well, if you like that sort of thing. It might help if I give you a picture:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZBG-Tw201PN0aissvrH7KacZer0r-sTqvbz6HerxbEeehzyOJjJg1rac41-It2sxqAMeuj8RUTUL9iOgqpYY7TqaVNONs_LSAyZMcJ4nFFY3bivVtBy-3Zejp-Z9OKDMv9SMj/s1600/recursive_string_reverse_diagram.png" imageanchor="1"><img border="0" height="512" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZBG-Tw201PN0aissvrH7KacZer0r-sTqvbz6HerxbEeehzyOJjJg1rac41-It2sxqAMeuj8RUTUL9iOgqpYY7TqaVNONs_LSAyZMcJ4nFFY3bivVtBy-3Zejp-Z9OKDMv9SMj/s640/recursive_string_reverse_diagram.png" width="500" /></a>
<p>By the way, both the recursive reverse in place and the second recursive reverse to an auxiliary string have a subtle bug. Can you spot it? I'll come back to that later at the end of this post.</p>
<p>Anyway, pretty as that in-place solution is, we probably don't really want a recursive solution in C. The biggest reason is that although I hear some C compilers now will optimize tail recursion into simple iteration, they aren't required to do it. I've heard that GCC can do it, but I wasn't able to figure out how to get my setup (LLVM GCC 4.2 with XCode 4.6.2) to do the optimization, as far as I could tell. So I'd say you definitely can't count on it, and so a big string might blow up your stack.</p>
<p>So what about an iterative solution? There are a few options, but a basic pointer math approach is very idiomatic C, and it looks very similar to the recursive solution, even if walking a pointer backwards seems a little odd and hazardous:</p>
<pre>char *fwd_p = str_p;
char *back_p = &(str_p[len - 1]);
while ( fwd_p < back_p )
{
char temp = *fwd_p;
*fwd_p = *back_p;
*back_p = temp;
fwd_p++;
back_p--;
}</pre>
<p>That's not a complete function. Here's a complete function with a test routine. This version is written without the buffer size parameter of the original spec. You'll need to include assert.h, string.h, and stdio.h</p>
<pre>/* in-place reverse with two pointers */
void ReverseStringWithPointers( char *str_p )
{
/*
There are several conditions that would induce us to exit
early. A null pointer is the most obvious one.
*/
if ( NULL == str_p )
{
return;
}
else
{
/*
A zero-length string is the next
*/
if ( '\0' == *str_p )
{
return;
}
else
{
/*
Assume the string is properly terminated; find the end
*/
char *back_p = str_p + 1;
while ( '\0' != *back_p)
{
back_p++;
}
/* Leave back_p pointing to the last character before the terminator */
back_p--;
while ( str_p < back_p )
{
char temp = *str_p;
*str_p = *back_p;
*back_p = temp;
str_p++;
back_p--;
}
}
}
}
char const *one_char_str = "1";
char const *two_char_str = "12";
char const *three_char_str = "123";
int main(int argc, const char * argv[]) {
/* Put these in writable storage */
char writable_one_char_str[2];
char writable_two_char_str[3];
char writable_three_char_str[4];
strcpy( writable_one_char_str, one_char_str );
strcpy( writable_two_char_str, two_char_str );
strcpy( writable_three_char_str, three_char_str );
ReverseStringWithPointers( NULL );
ReverseStringWithPointers( writable_one_char_str );
ReverseStringWithPointers( writable_two_char_str );
ReverseStringWithPointers( writable_three_char_str );
assert( 0 == strncmp( writable_one_char_str, "1", 1 ) );
assert( 0 == strncmp( writable_two_char_str, "21", 2 ) );
assert( 0 == strncmp( writable_three_char_str, "321", 3 ) );
return 0;
}</pre>
<p>That's probably a preferred interview solution for the "standard" in-place string reverse without the buffer size parameter. It illustrates how idiomatic C pointer math is; it's idiomatic because it expressive and it works. It is probably one of the biggest reasons for C's longevity.</p>
<p>So, any other ideas for implementing the string reverse? Well, for the core logic you can use array indexing like so:</p>
<pre>for ( unsigned long idx = 0; idx < ( ( len / 2 ) - 1 ); idx++ )
{
unsigned long rev_idx = len - 1 - idx;
char temp = str_p[idx];
str_p[idx] = str_p[rev_idx];
str_p[rev_idx] = temp;
}</pre>
<p>But that is actually problematic for some string lengths. If len is less than two, dividing it by two to find the array's halfway point yields zero, and when you subtract one, you'll have an underflow, giving a very large positive number for your array index, giving undefined befhavior (if you're lucky, you'll get an immediate crash). This approach can be rehabilitated by screening the early return conditions.</p>
<p>Oh, there's another little trick you can do. I'll leave it to you to figure this one out, if you haven't seen it before. Instead of using a temporary variable to swap the characters, you could do this:</p>
<pre>str_p[rev_idx] ^= str_p[idx];
str_p[idx] ^= str_p[rev_idx];
str_p[rev_idx] ^= str_p[idx];</pre>
<p>And there, dear reader, I will leave you for today. I hope you found this interesting and maybe learned something. I did. Maybe you can see why my brain locked up -- I didn't want to write a function with that prototype; it it seems to contradict itself as far as whether it should be safe, or just efficient. Wanting to write a recursive solution was a secondary issue. Oh, and of course let's not forget that this is the wrong solution for modern strings -- for any Unicode types. It only works for old-school strings of bytes.</p>
<p>Don't get me wrong -- I'm not actually complaining about the interview question. It's a great interview question, because it looks easy but it should <i>also</i> bring up a lot of safety and design issues in the programmer's head. I've been humbled just a bit. I've been reminded that while I've spent years writing code that uses STL and reference counting and nice, modern features of C++ and more modern libraries, I've forgotten just a bit how <i>low-level</i> C often turns out to be. I should never do that, because of course sometimes you have to debug all that nice, modern code, and remember what is going on underneath. Had I been asked to write the solution in a simple assembly pseudo-code, I would have had to come up with an iterative solution immediately, although I'm not sure I would have been able to work out the pointer-crossing problem in the interview setting. Recursion is almost certainly the wrong way to go in C, but maybe you can see why I was drawn to the idea, especially of writing the reversed string to a second buffer. It's funny how a relatively simple problem in C can be so "interesting." May we one day no longer live in such interesting times...</p>
<p>FOLLOWUP: I got feedback that the interviewers were quite pleased with both my performance and attitude. I actually sent them the source code for my experiments today, too, with some comments, in case they have anything to add. I screwed that up again, though, because the first version had a crashing bug, so I sent another one, and that still didn't have the most elegant form of the recursive functions. And, a couple of the solutions have that subtle bug I mentioned earlier. What is the subtle bug?</p>
<p>Obviously, it is a bug to write past the end an array in memory -- whether we're talking about an array allocated dynamically on the heap, on the stack, or in static storage, like a global variable. You can't guarantee that this bug will be caught -- it could be symptomless, just silently corrupting some other variable in your program. And obviously it is a similar bug to write before the beginning of an array. But did you know it is a bug to <i><a href="http://stackoverflow.com/questions/16234626/pointer-comparisons-with-one-before-the-first-element-of-an-array-object">calculate the address</a></i> of an item before the first item, even if you never use it to write to the array?</p>
</p>The C standard guarantees that you are allowed to <a href="http://stackoverflow.com/questions/988158/take-the-address-of-a-one-past-the-end-array-element-via-subscript-legal-by-the">create the address of an extra array element past the end of your array</a>. Reading or writing at this location is "undefined behavior" -- that is, very bad. But there is no such guarantee for creating a pointer <i>to an array element at index -1</i>, even if you don't read or write it. See also <a href="https://www.securecoding.cert.org/confluence/display/seccode/ARR30-C.+Do+not+form+or+use+out+of+bounds+pointers+or+array+subscripts">this CERT coding guideline</a>.</p>
<p>There are several places in our recursive code where that is actually a concern. If we have a zero-length string, our calculated <i>len</i> is zero. Every place where we use len should be inspected. For example, in <b>ReverseStringAux2Helper</b>, I pass the value <b>&str_out_p[len - 1]</b>. This gives me the address of the last writable character in the output array. But for a zero length string, this will result in calculating the address of the character before the first character of the output string.</p>
<p>The rationale for this, I believe, goes something like this. On an arbitrary computer running your C program, you don't actually know what your memory addresses look like, at the hardware level. C has to cover a lot of weird and arcane and now-deceased architectures: segmented pointers, odd pointer sizes, architectures where different types of addresses have different numbers of bits, architectures where only address registers can hold addresses and they aren't the same size as any other type, etc. What if you're running this on a small processor, and it just so happens that the array in question was started at hardware address zero? Calculating the address of element -1, in an unsigned pointer type, would "underflow" into a large number. I don't specifically know of an architecture where just storing that number in an address register or in memory will really crash, but there could be one, or at least could have been one. And the designers of the C standard wanted to make sure that C was as portable as possible.</p>
<p>The logic in <b>ReverseStringAux2Recursive</b> determines that there is nothing to do, and so we don't write to that address, but it is still illegal. To be strictly scrupulous about observing the standard, logic should be changed so that in the case of the zero length string, we don't get to the point where we calculate the address of that non-existent element. This also happens in the code where we calculate the length of a string and determine if it needs to be forcibly terminated -- in the case of a specified buffer length of zero, <b>len</b> underflows. A zero-length string can't be a valid string. I really do need to avoid this case entirely. I also need to think hard about the string size that is specified as one character, which can become a zero-length string if we forcibly terminate it. So the wrapper logic, given my chosen strategy of terminating unterminated strings, needs to look something like this:</p>
<pre>void ReverseString( char *str_p, size_t buffer_size )
{
if ( NULL == str_p )
{
printf( "ReverseString: received NULL pointer!\n" );
return;
}
else if ( 0 == buffer_size )
{
printf( "ReverseString: received buffer_size 0!\n" );
return;
}
else
{
/*
strnlen returns the number of characters before
the NUL or the provided maximum. If we get back
the maximum, assume the string is NOT terminated.
*/
unsigned long len = strnlen( str_p, buffer_size );
if ( buffer_size == len )
{
/*
Forcibly terminate the incoming string,
consider its length to be one shorter, log a
problem, and continue
*/
str_p[buffer_size - 1] = '\0';
len--;
printf( "ReverseString: no termination found!\n" );
/*
If our adjusted string length is zero, don't
continue because some of our algorithms that
create pointers to the first character before
the terminator will generate a pointer to an
array item at index -1, an invalid operation
per the C standard
*/
if ( 0 == len )
{
printf( "After termination, len is 0!\n" );
return;
}
}
/*
There is really nothing we need to do to reverse
a string of length 1, but rather than rule that out
here, we let our algorithms handle that case to
exercise their boundary conditions.
*/</pre>
<p>This is another case where the two parameters, the string pointer itself and the <b>buffer_size</b>, can contradict each other, with results that are complicated no matter what you do.</p>
<p>What happens if we don't forcibly terminate incoming strings that aren't terminated within <b>buffer_size</b> chars, but just reverse <b>buffer_size</b> chars? Well, the preamble code is a little different. Here's a version of the whole function that does that. The reversal algorithm in this version isn't very efficient -- it copies bytes twice, and it allocates extra storage. But efficiency wasn't mentioned in the task description, and I think it is correct, at least for this interpretation of how to deal with strings that aren't terminated within buffer_length chars. It also seems like something I might have had a better chance of getting right on paper, quickly, when put on the spot.</p>
<pre>void ReverseStringFinal( char *str_p, size_t buffer_size )
{
/*
We take the buffer_size parameter to mean
that we shouldn't touch more that buffer_size
bytes, even if the string is longer.
There are several error conditions that really
should trigger failure, returning some kind of
error code, but the spec doesn't give us that
option.
*/
if ( NULL == str_p )
{
return;
}
else
{
/*
strnlen will return buffer_size if it
doesn't find a terminator before counting
buffer_size characters.
*/
unsigned long len = strnlen( str_p, buffer_size );
/* I'd like to use max(), but it is not standard C */
unsigned long working_len = 0;
if ( len < buffer_size )
{
working_len = len;
}
else
{
working_len = buffer_size;
}
if ( working_len < 2 )
{
/*
Reversing a string of 0 or 1 character
is a no-op
*/
return;
}
else
{
/*
An inefficient but simple solution using a
temporary buffer
*/
char *temp_buf_p = (char *)
( malloc( working_len ) );
if ( NULL == temp_buf_p )
{
return;
}
else
{
/* Copy chars backwards */
for ( unsigned long idx = 0;
idx < working_len; idx++ )
{
temp_buf_p[ working_len - 1 - idx] =
str_p[idx];
}
/* Copy forwards into original buffer */
for ( unsigned long idx = 0;
idx < working_len; idx++ )
{
str_p[idx] = temp_buf_p[idx];
}
/*
Don't write a null; only touch
the chars in the working length.
*/
free( temp_buf_p );
}
}
}
}</pre>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com1tag:blogger.com,1999:blog-21500237.post-50846425457656171352013-03-08T22:31:00.000-05:002013-03-09T10:36:08.342-05:00Scala, Day One<p>I am beginning an investigation of Scala. I have been a little bit disdainful of languages implemented on the JVM – but some of that disdain goes back to some impressions gained with much, much earlier versions of the JVM, plagued with various memory leaks. And I’m not a big fan of Java, having used it in anger enough to get to know its downsides in depth. But – the JVM seems to have improved considerably, and I shouldn’t blame the JVM for Java. As someone who has been pushing for the use of advanced languages in real, commercial projects my whole career, the only thing I regret about this is that despite my interest in languages like Haskell, I’ve rarely been able to use them “in anger” (that is, in a real, shipping product), at my day job. But that may be changing. It looks like Scala might just be, if not the one and only, at least <em>an</em> acceptable, practical Haskell.</p>
<p>So, I downloaded the Scala 2.10.0 binary distribution onto my Mac running MacOS X 10.8.2 (the latest update to Mountain Lion). I stuck the scala-2.10.0 directory into /Library/Scala/ and after a little sudo ln -s action to make symlinks to the binaries, I was in business, with no apparent issues.</p>
<p>There’s a free O’Reilly book online: <a href="http://ofps.oreilly.com/titles/9780596155957/IntroducingScala.html"><em>Introducing Scala</em></a>, so I am starting there. I also downloaded my “free” copy of <em>Scala for the Impatient</em> but it signed me up for a mailing list, appeared in my Downloads folder as a .pdf.flv file (WTF?), and launching that opens up Adobe Media Player, produces an error message, then demands that I update Adobe Air. (It turns out it’s actually a PDF. I have no idea why that happened). So I’m printing out the first 32 pages of that book as well, and I’ll read it tonight.</p>
<p>The introductory material in the O’Reilly text is quite interesting. I like the strong, static typing of variables. It’s something I like about Haskell. Except, of course, the Haskell doesn’t have variables. I like the “everything’s an object” – that’s Dylan. I like “everything has a value” – that’s Scheme. I like functional programing and object-oriented programming, both… so, in theory, Scala and I should get along quite well.</p>
<p>Here’s the first bit of sample code in the O’Reilly book:</p>
<pre><code>class Upper {
def upper(strings: String*): Seq[String] = {
strings.map((s:String) => s.toUpperCase())
}
}
val up = new Upper
Console.println(up.upper("A", "First", "Scala", "Program"))</code></pre>
<p>The first thing I notice is that this code uses names that differ only in capitalization (<strong>Upper</strong> and <strong>upper</strong>). The <strong>upper</strong> method has nearly the same name as the class, and it’s not a constructor (following the C++ convention). This reminds me immediately of the style that Apple’s WebObjects used for Java code. It was very common to see code like this in WebObjects sample code:</p>
<pre><code>Person person = person();</code></pre>
<p>or even</p>
<pre><code>Person person = (Person) objects().objectForKey("person");</code></pre>
<p>WebObjects was incredibly powerful and you could get some cool things up and running with it very easily, but code like that always made me cringe. I thought one of the goals of Scala was to get away from Java’s overly-wordy syntax? But that looks like mostly a coding convention thing; let’s hope they don’t use redundant-looking names frequently.</p>
<p>Anyway, the class definition</p>
<pre><code>class Upper {
def upper(strings: String*): Seq[String] = {
strings.map((s:String) => s.toUpperCase())
}
}</code></pre>
<p>doesn’t look too bad. It’s all in one place – no separate header like C++, and that code will execute without requiring any boilerplate module or namespace definitions or importing any standard modules. Classes have methods, unlike Dylan where they only have slots and are operated upon by specialized generic functions. (I really liked that paradigm, by the way, which Dylan borrowed from CLOS, but it seems to be out of fashion now. (Another note to self: does Scala support generic functions?)</p>
<p><strong>Upper</strong> looks like a class with one method, <strong>upper</strong>, with a parameter called <strong>strings</strong>. (Why is it a class if it has only one method? Shhh, it’s just an introductory example. Move on!). I’m assuming <strong>String*</strong> is a type. But what is the significance of the asterisk in the type name? Is that a naming convention, indicating it is a general base class for strings, or does it indicate some kind of regular-expression-based pattern matching on type name? (Because that might be… well, weird?)</p>
<p>Ah… the book says that <strong>String*</strong> – that must be a type name – indicates a variable-length list – that is, you can provide any number of strings, including an empty list. So, a typed list (lists in old-school Lisp or Scheme are polymorphic and can contain objects of any type, but this has implementation consequences, requiring tagged or “boxed” data and a lot of runtime checks, while old-school Java’s lack of polymorphic containers was a headache for other reasons). The type of <strong>strings</strong> inside the method body is array of strings.</p>
<p>OK, I get that. In Haskell if I was writing a recursive algorithm that operated on a list, I’d probably pattern-match in order to specialize on the empty list (not take its tail, for example). But presumably if we aren’t doing some kind of guarding up front, it means we won’t be executing any operations on that list that fail catastrophically if the list is empty.</p>
<p>It looks to me like <strong>Seq[String]</strong> is a a return type – the specification of return types is sort of Dylanesque. Here’s a method definition in Dylan:</p>
<pre><code>define method square-list (numbers :: <list>) => (out :: <list>)
map(method(x) x * x end, numbers);
end;</code></pre>
<p>Note the type of the incoming parameters and the return value is <strong><list></strong> (a type name can contain punctuation in Dylan). In Scala, is <strong>Seq[String]</strong> an arbitrary name for a type, where the brackets mean something to the reader, or does that bracket syntax mean something to the compiler? (Note to self…)</p>
<p>Oh, the book says that <strong>Seq[String]</strong> is a parameterized type, like a generic type or instance of a type class. I think I get that, although I will no doubt need to study what Scala is doing with generic types much more thoroughly.</p>
<p>Next, I notice that we’re defining the function body with</p>
<pre><code>def upper(strings: String*): Seq[String] = {
strings.map((s:String) => s.toUpperCase())
}</code></pre>
<p>in a pattern that looks to me like:</p>
<pre><code>def name( parameter names and types ): return type or types = {
body
}</code></pre>
<p>That <strong>= { body }</strong> looks a little bit odd, but it raises some interesting possibilities (what if we don’t assign a function body?) I would also like it if the return type could have a name like the incoming parameters do; in Dylan you can do that, although since the name isn’t bound to anything in the method itself or in the calling method, it is strictly for documentation purposes.</p>
<p>The book tells me that the <strong>=</strong> is present because a function definition doesn’t have to be wrapped in brackets, and so it prevents some syntactic ambiguity. All right, I can live with that for now. Also, “functions are values.”</p>
<p>Moving on to</p>
<pre><code>strings.map((s:String) => s.toUpperCase())</code></pre>
<p>At first glance, I have to say I’m not entirely clear on what the <strong>=></strong> is doing. Is it some kind of “apply?” This line looks needlessly complicated. In Haskell, I would try to write this in a point-free style without naming any variables, just composing functions. In Haskell, the standard <strong>toUpper</strong> function does not take strings, but characters. If it did take strings, we could just write the function like so:</p>
<pre><code>upper = map toUpper</code></pre>
<p>In Haskell, strings are defined as lists of characters, so we can still compose it like so:</p>
<pre><code>upper = map ( map toUpper )</code></pre>
<p>and that works fine. Stick the following lines in a file load it into GHCi:</p>
<pre><code>import Data.Char
pfupper = map ( map toUpper )</code></pre>
<p>then type</p>
<pre><code>pfupper ["These", "are", "Haskell", "strings"]</code></pre>
<p>I get back</p>
<pre><code>["THESE","ARE","HASKELL","STRINGS"]</code></pre>
<p>But in Scala’s world everything is an object, and the functions we’re dealing with here are methods. I’ll grit my teeth a bit at the loss of elegance. Maybe we can get it back later – there’s a chapter on functional programming. For now, let’s press on and see how the book explains it.</p>
<p>Breaking down the method body, the outer expression, <strong>strings.map()</strong>, is just a call to the <strong>map</strong> method of the strings parameter. Strings is a list or array or some such, and mapping a data structure like that is a common operation in functional programming. Instead of passing a data structure to a method, we pass a method to a method of the data structure. That method is then called for each element, and the results are returned in a fresh list.</p>
<p>Oh, and since everything has a value, and functions or methods in this paradigm typically have the value of their last (or only) expression, there’s no <strong>return</strong> statement. That’s like Scheme or Dylan; no big deal.</p>
<p>What is up with that argument, <strong>(s:String) => s.toUpperCase()</strong>? Mr. Book says that this a <em>function literal</em>. I think that means it’s what Schemers call a <em>lambda</em>. In Haskell, we could do this with a lambda that looked something like:</p>
<pre><code>\ s -> map toUpper s</code></pre>
<p>putting it into a function gives us</p>
<pre><code>lupper ss = map (\ s -> map toUpper s) ss </code></pre>
<p>And that works just like the point-free version did.</p>
<p>Anyway, all that Scala syntax is slightly off-putting, although new languages usually are. Syntax is both unimportant and the biggest source of frustration when adapting to a new language, especially when it’s your nth language, for some moderately large n; I keep falling into trying to write Haskell, or trying to write Scheme, or trying to write Dylan, or trying to write NewtonScript…</p>
<p>But wait, the book provides a simplified version:</p>
<pre><code>object Upper {
def upper(strings: String*) = strings.map(_.toUpperCase())
}
println(Upper.upper("A", "First", "Scala", "Program"))</code></pre>
<p>That transforms</p>
<pre><code>strings.map((s:String) => s.toUpperCase())</code></pre>
<p>into</p>
<pre><code>strings.map(_.toUpperCase())</code></pre>
<p>That makes it a little more “point-free” since we don’t specify a name and type for the parameter to our lambda express. I’ll have to read up a little more about the underscore. It seems to be indicating that we should call the <strong>toUpperCase()</strong> method on <em>whatever</em> unnamed object comes into the lambda. We let the compiler deal with the type-checking.</p>
<p>That seems promising. Getting rid of the type and the name allows us to think a little more functionally. Note that this is very different than the Haskell undercore, which is used for pattern-matching. Maybe we should call it the “whatever” operator? Or the “let the compiler worry about it” operator? Hmmm… I’ll have to think about that some more.</p>
<p>So, what else is going on here? <strong>object</strong> defines a <em>singleton</em>… nice. Design patterns ahoy! (Yet another note to self – can you inherit from an object instance, as in Omega, or Self, or NewtonScript, or specify inheritance only from a class?) The return type of <strong>upper</strong> is inferred, not explicit. We don’t need the braces for a method that is only one expression.</p>
<p>More tomorrow! (Or maybe Monday.)</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com2tag:blogger.com,1999:blog-21500237.post-21124541652272507392009-09-09T23:44:00.003-04:002013-07-23T15:56:55.915-04:00MacPorts, Snow Leopard, and GHC == Sadness<p>Wow, it has been a long time since I've had anything to say on this particular blog. Another baby (we're at four now) will do that to a guy, I guess.</p>
<p>I was going to do a little exploratory coding tonight, and so installed XCode, then MacPorts, then tried to install GHC. MacPorts tells me (after installing most of the components) that "ghc is not yet supported on Mac OS X 10.6.x (SnowLeopard)."</p>
<p>I know it hasn't been out very long, but the APIs have supposedly been frozen since May, so I'm a bit surprised.</p>
<p>I guess I'll see if the package installer works, but I was hoping to go a little more cutting-edge.</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com8tag:blogger.com,1999:blog-21500237.post-39595060178332889922008-11-17T17:31:00.001-05:002013-07-23T15:55:40.459-04:00Reading Real World Haskell<p>I've sort of let this blog lie fallow while my attention was distracted by having a new baby, playing shiny guitars, twittering, making podcasts and YouTube videos, and other distracting things.</p>
<p>I am excited to see that <i>Real World Haskell</i> has gone to press, and so I am reading the electronic edition while waiting for the print edition to arrive. I had read some of the draft chapters, but it has changed considerably!</p>
<p>For those interested, I recorded audio during the birth of my newest child, Joshua Gregory Potts, born just under three weeks ago. I am turning this into a series of podcasts along with the tweets I sent out during the birth. I won't spam you with a lot of links, but here is a link to <a href="http://generalpurposepodcast.blogspot.com">The Potts House General Purpose Podcast</a>. Over on <a href="http://geeklikemetoo.blogspot.com">Geek Like Me Too</a> you can find baby pictures, some serious and some silly.</p>
<p>I am learning to live with sleep deprivation again! So, these days, Twitter seems like a more appropriate medium for the short attention span which is pretty much all I'm capable of at the moment. If you are so inclined, you can find me on twitter as "paulrpotts."</p>Paul R. Pottshttp://www.blogger.com/profile/04401509483200614806noreply@blogger.com0