4Clojure: For the Win

(for [x (range 40)
    :when (= 1 (rem x 4))]
    x)

x is assigned the range of integer values from 0-39. x is finite so the for stops evaluating when x is fully consumed.
On each iteration the remainder of x/4 is compared to 1 and if they are equal the body is evaluated (which is just x).

(for [x (iterate #(+ 4 %) 0)
    :let [z (inc x)]
    :while (< z 40)]
    z)

x is assigned a lazy sequence of all the multiples of 4 (iterate from 0 applying +4 at each step using an anonymous function). x is infinite so the for is terminated with :while
Each iteration of the for symbol z is assigned x+1.
While z is less than 40 the body is evaluated (which is just z) and the for loop terminates when z >= 40.

(for [[x y] (partition 2 (range 20))]
    (+ x y))

The range from 0-20 is split into segments of 2 numbers. One segment deconstructed into x and y per iteration of the for. The sequence is finite so the for terminates when the full sequence is consumed.
x and y are added as the body of the for.

Each of these results in the same output (a list of each multiple of 4 incremented by 1 up to 37) just by a different mechanism. For my money the first option is probably the best combination of concise and obvious.

Clojure for macro keywords

These docs weren't incredibly helpful in figuring out the difference between :when and :while.
The examples
(for [x [1 2 3]
  y [1 2 3]
  :while (<= x y)
  z [1 2 3]]
  [x y z])
and

(for [x [1 2 3]
  y [1 2 3]
  z [1 2 3]
  :while (<= x y)]
  [x y z])

come close to exposing the difference, but what should really be stated explicitly somewhere is that :while stops attempting to evaluate at the first false result whereas (almost said while there >.> ) :when continues to try to evaluate after the false.

(for [x [1 2 3]
  y [1 2 3]
  :while (= x y)
  z [1 2 3]]
  [x y z])
;;([1 1 1] [1 1 2] [1 1 3])
(for [x [1 2 3]
  y [1 2 3]
  :when (= x y)
  z [1 2 3]]
  [x y z])
;;([1 1 1] [1 1 2] [1 1 3] [2 2 1] [2 2 2] [2 2 3] [3 3 1] [3 3 2] [3 3 3])

Perhaps I'm dense but this wasn't immediately obvious to me.

Edit: Or perhaps I should have actually read. Example 8 is pretty explicit. >.<

7L7W Week 2: Io Day 2 round 2 continued>Toddling

I should probably check to see if something has defined the sum slot on Number and List first, but... let's start this simple.

Number sum := method(call target)
List sum := method(
total := 0;
foreach(val, total = total + val sum)
)

Io> a := list(list(1, 2, 3), list(1, 2, 3))

==> list(list(1, 2, 3), list(1, 2, 3))

Io> a sum

==> 12

As the title suggests, I think I'm getting used to this now. This may not be exactly how it should be done, but it was ridiculously easy to implement (even with accidental recursion >.> ). Implementing a sum method on two base prototypes of the language leaves me a touch uneasy but these are additions to the prototypes rather than redefinitions. If I were going to try this in production code of some sort I would need to either use a less generic slot name or properly check for an existing sum slot on both prototypes.

... Also it strikes me that the question was to write a program, not a method on the List prototype. Oh well. Nobody is grading this but me.

The averaging problem was pretty straightforward but I had some confusion around the select message. Mostly because I saw a reference in the programming guide to a method ISNUMBER() which doesn't appear to actually exist anywhere? Or at any rate I couldn't find it so I had to do this:

List myAverage := method(

values := call target select(v, v type == "Number");

if(values size == 0, Exception raise("No Number in target List"));

values reduce(+) / values size

)

Unlike the summing problem this solution will not handle multidimensional arrays. I could swap the reduce message for the sum method defined above but I'd have to handle n-dimensionality in the select message at the top of the method as well.

... I was going to finish day 2 today and post this. Actually I was hoping to post this yesterday but it has not been a very good week for side projects. Unfortunately it's going to have to wait. It might have to wait until the weekend. I want to get this posted at least and I'll try to get day 2 finished before Monday.

7L7W Week 2: Io Day 2 round 2>Finding my feet

I might be getting the hang of this.
recursiveFibonacci := method(n, 
if(n == 0, 
0,
if(n == 1,
1,
recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2)
)
)
)

loopedFibonacci := method(n,
nSub1 := 0;
currentN := 1;
for(i, 1, n, 
currentN = currentN + nSub1;
nSub1 = if(i == 1, 0, currentN - nSub1))
currentN
)

Number recursiveFibonacci := method( 
if(call target == 0, 
0,
if(call target == 1,
1,
((call target - 1) recursiveFibonacci) + ((call target - 2) recursiveFibonacci)
)
)
)

Number loopedFibonacci := method(
nSub1 := 0;
currentN := 1;
for(i, 1, call target, 
currentN = currentN + nSub1;
nSub1 = if(i == 1, 0, currentN - nSub1))
currentN
)

Do I get double bonus points? Hm, no, probably not. It's not exactly a stretch to move from a parameter to calling the message target is it? These seem pretty self explanatory to me (Fib numbers aren't a new science after all) but I can't help feeling like it could be done better.

Division by zero? Sure, let's break basic math... >.<

Number divide := Number getSlot("/")
Number / = method(n,
if(n == 0,
0,
call target divide(n)
)
)

I did cheat a bit. StackOverflow pointed me in the right direction.

And it's bedtime now. I'll get the rest of the self study done tomorrow (with a grain of salt). So progress has definitely slowed in my 7(3!) week journey. However it's also getting more interesting so assuming there's a correlation between difficulty and interest... yeah.
Then again it may be due to my lack of cohesive sleep schedule (have I mentioned lately that ridiculous software installs suck?) which sadly will only get worse. There's another install this weekend (end of year compliance, yippee) then a family vacation (meaning all my wife's immediate family, which is neither vacation nor particularly conducive to any kind of study) right after Christmas... which is itself a disruption. Then of course there's the end of the year, which is another all-nighter (I've really got to streamline the end of month process)... I probably could have started this at a better time of year. Then again interrupted progress is better than sitting around playing video games or trying to study something that has gotten stale and boring. Maybe I'll take a break from 7L7W after week 2 and get back to some C#. Play the flipflop game with them. Or maybe not. Since I'm playing dablling all over the place maybe I'll crack that LISP book back open. I'm not sure the original  rationale for shelving it still holds. Ah, the possibilities.

Also, the song that's been driving me today like Paul Revere on speed. That's good stuff there. I must recant my uninformed, juvenile opinions of rap. I clearly had an insufficient sample size to base opinion on.

7L7W Week 2: Io Day X>Digging in

Feeling almost human again after my weekend. Serious 2 week prep & 4 hour imp software updates suck. Moving right along.

Let me try to break this down.

Io> test := method(stuff, stuff println)

==> method(stuff,

    stuff println

)

Io> test("Hello World")

Hello World
==> Hello World

Io> 

Interesting things are happening here. First I'm creating a slot in the Lobby...

Io> Lobby slotSummary

==>  Object_0x5bc8c0:

  Lobby            = Object_0x5bc8c0

  Protos           = Object_0x5bc860

  _                = "Hello World"

  exit             = method(...)

  forward          = method(...)

  set_             = method(...)

  test             = method(stuff, ...)

Io>

called test. But... I'm already ahead of myself. >.<

The method() block is sent as a message to the := assignment operator which becomes setSlot("test", method ... ) via a macro creating a slot in the Lobby and loads the method message into it. setSlot()sends the method block as a message, I think, and so the Lobby outputs the method with ==>.

In the next line I craft a message test and give it the string "Hello World" as an argument. This message is sent to the Lobby, where everything eventually lands I guess? It's the default evaluation context when there's no other object to catch the message. The Lobby responds to the test message with its test slot.

The Lobby's test slot is a method block that sends the println message to the first message argument (any additional arguments are ignored and generate no errors that I can see, coder beware). So a println message is sent to my "Hello World" object causing it to print to output. The "Hello World" message also gets sent on to the Lobby which outputs it with ==>.

That's a lot to follow in two lines of code. Time to take another hack at day 2.

Point of interest: the Lobby slot _ seems to contain whatever message was last output by Lobby via ==>. I could stand to learn the terminology for that. But I wonder how long it would take to crash the runtime by repeatedly sending Lobby slotSummary >.>

7L7W Week 2(early): Io Day 2>Empty tank

I followed the day's section but I didn't internalize it. Something is missing in my understanding and I don't have enough energy left in me today to chase it down. I'll have to go over it again tomorrow, assuming I get a chance to.

I like Io. It's different in a way that demands that I reshape the way my thoughts flow. In the same way that learning to use Suprtool for ETL processing required a more-than-evolutionary change in thinking from using SQL-like languages. I enjoy twisting my brain into different shapes like this.

7L7W Week 2(early): Io Day 1>Scrumptious

Now this, this is something that looks exciting on day1. Yes, it's actually even easier to blow your foot off with a single line of code than in Ruby (Object clone := "hosed" indeed!) but for that only slighter greater power you get an incredibly flexible language. The syntax is extremely small and there seems to be only a very limited number of concepts to grok. No doubt the libraries are an even bigger elephant to devour than in most languages, or at any rate an even higher priority, simply because Io doesn't seem to have much in the way of plumbing available in the base language (file handling? don't see it yet) Even so... I think I'll spend some time with this one and see how it fits. Probably after this 7 weeks course is done in... oh at this rate about 3 weeks.

Enough prologue. Io is ridiculously tricky to search for on Google so I'm dropping links to my 'Find' results.

• Examples: 
• Github gist, though some of them seem to be broken
• This blog post may not be the type of 'example' Mr Tate was thinking of, but it's going on my 'to be read' list anyway.
• Tutorials on the official language site
• Community: There's an official mailing list, twitter, and IRC channel. No idea how active they are. Otherwise, Stack Overflow is all I could find.
• Style guide: This wikibooks entry looks decent. No idea if there's anything more canonical. I'm not terribly perturbed about style right at the moment though. If I stay in Io long enough to have to find more resources I expect I'll find style canon alongside those searches.

Amusingly, many of my searches related to Io have turned up blogs of people, like me, working and blogging their way through this book. I find that quite amusing, though it highlights an apparent lack of external resources.

Anyway. On with the show. 'Answers'

• 1+1 runs, 1+"one" does not. 1 is a Number type and "one" is a Sequence type. Sequences don't respond to the + operator. On the other hand, an object can be assigned to any other object at will and according to the Io programming guide even inheritance can be changed at runtime. Which, it seems, would make Io very weakly typed.
• Everything is true. The cake is always honest. Unless cake := false clone or cake := nil clone. For proofs:
• true and 0
• ==> true
• true and ""
• ==> true
• true and nil
• ==> false
• true and false
• ==> false
• <Object> slotNames or perhaps <Object> proto slotNames. You can also send the slotSummary message to an object if you also want to know what's in each slot.
• = is assignment to a slot. := creates and assigns a slot (no unassigned variables, ever?) ::= creates and assigns a slot and defines an accessor method set<slotname>() in the object where <slotname> is the name of the slot with an upshifted first letter (existing catpitals are unchanged, only the first letter is upshifted).

So. Do:

• doFile("filename") filesystem context is where the Io binary is executed from, rather than where it resides. This can also be sent like any other message to an object.
• Execute the code in a slot given its name... I interpret that as 'how do you eval() a string'. Which is as so:

Bond := Object clone

Bond martini ::= nil
Bond orderMartini := "setMartini(\"shaken, not stirred\")"

Bond slotSummary

Bond doString(Bond orderMartini)

Of course he might just have meant Bond setMartini("shaken, not stirred") or in words, send the slot name as a message to the object in order to execute the code in the slot. In fact, that's probably the simple answer that was being looked for. I tend to overcomplicate >.>

So far so good. I'm quite a bit more excited by Io than Ruby on D1.

7L7W Week 1: Ruby Day 3>40 ct rubies

Hm. Only 3 days? That's not a week; things were just getting interesting.
module ActsAsCsv
  def self.included(base)
    base.extend ClassMethods
  end
  
  module ClassMethods
    def acts_as_csv
      include InstanceMethods
    end
  end
  
  module InstanceMethods
    attr_accessor :headers, :csv_contents

    def initialize
      read
    end

    def read
      @csv_contents = []
      file = File.new(self.class.to_s.downcase + '.txt')
      @headers = file.gets.chomp.split(', ')
    
      file.each do |row|
        @csv_contents << row.chomp.split(', ')
      end
    end
    
    def each
      @csv_contents.each do |row|
        yield(CsvRow.new(@headers, row))
      end
    end

  end
end

class CsvRow
  def initialize(headers, row)
    @data = Hash[headers.zip(row)]
  end
  
  def method_missing name, *args
    puts @data[name.to_s]
  end
end

class RubyCsv
  include ActsAsCsv
  acts_as_csv
end

m = RubyCsv.new
puts m.headers.inspect
puts m.csv_contents.inspect
puts "============================"

class Day3Csv
  include ActsAsCsv
  acts_as_csv
end

m = Day3Csv.new
puts m.headers.inspect
puts m.csv_contents.inspect
puts "----------------------------"

m.each {|row| puts row.one}

It doesn't look like much (and my additions to the book's template are probably quite poorly written or idiosyncratic) but there's some interesting metaprogramming going on. Including ActsAsCsv causes the class method self.included to execute with the including class as the parameter. In this case the including class is extended with the ClassMethods module which defines a single method, acts_as_csv, on the class.

Later in the CsvRow class we include ActsAsCsv and then call the acts_as_csv method. This, I guess, occurs at instantiation which means the specific instance of the CsvRow class gains the InstanceMethods module included by acts_as_csv rather than at the class level though in this case it applies to all instances. The InstanceMethods module defines methods which create the behavior of a CSV file. At multiple points the cascade of includes and method definitions is open to tinkering, conditional method inclusion or definition &etc. It's just gotten interesting, and now this 'week' is done. Maybe I'll study Ruby more later.

7L7W Week 1: Ruby Day 2>Take 2

Reading through the 3rd day's treatment and I decided to go back over this exercise from day 2.
This is better. I'm still not entirely convinced.
class Hash
  def each_hash
    h = self
    h.each do |element|
      yield({element[0] => element[1]})
    end
  end
end
class Tree
  attr_accessor :children, :node_name

  def initialize(name, children=[])
    if name.is_a?(String)
      @node_name = name
    elsif name.is_a?(Hash)
      @node_name = name.keys[0]
      name[@node_name].each_hash {|trunk|
        children << Tree.new(trunk)
        }
    end
    @children = children
  end
  
  def visit_all(&block)
    visit &block
    children.each {|c| c.visit_all &block}
  end
  
  def visit(&block)
    block.call self
  end
end

familyTree = Tree.new({'grandpa' => {'dad' => {'child 1' => {}, 'child 2' => {}}, 'uncle' => {'child 3' => {}, 'child 4' => {}}}})
puts "Visiting a node"
familyTree.visit {|node| puts node.node_name}
puts

puts "Visiting entire tree"
familyTree.visit_all {|node| puts node.node_name}

The notion of editing the base class at will and indeed the basic predefined classes/types, while apparently being an integral part of Ruby's design, doesn't come easily. And still this solution requires testing the type of the incoming parameter, making Ruby's blasé treatment of types rather dubious. Or, I'm doing it wrong™ which is also quite possible seeing as this is exactly the 3rd day I've done anything in Ruby.

What I've done here is basically the same as a C# extension method. What gives me the 'icks' is the notion of directly altering Hash.each to do what I wanted it to do. It seems that you can't scope the changes so it's a global edit of the existing class. Great power, &etc, plus TDD, but if anyone comes along later to update the script and tries to do anything with a hash while those changes are in effect it's going to bite them in the tail.

I think I'm feeling a tension between reducing failures and productivity at the cost of stability. It's hard to decide where the sweet spot is there. That's interesting since I spent a good bit of time developing in PHP which is pretty loosely typed.

7L7W Week 1: Ruby Day 2>A spoonful of sugar

I feel like I must be missing something. Because this:
class Tree
  attr_accessor :children, :node_name
  def initialize(name, children=[])
    if children != []
      @node_name = name
    elsif name.is_a?(Hash)
      @node_name = name.keys[0]
      name[@node_name].each {|trunk|
        children << Tree.new(trunk)
        }
    elsif name.is_a?(Array)
      @node_name = name[0]
      name[1].each {|trunk|
        children << Tree.new(trunk)
        }
    end
    @children = children
  end
  
  def visit_all(&block)
    visit &block
    children.each {|c| c.visit_all &block}
  end
  
  def visit(&block)
    block.call self
  end
end

looks ridiculous. The main problem seems to be that name[@node_name].each is giving me arrays instead of hashes. Which means I have to account for another type that I can't readily predict in advance... which seems to end up being the bane of dynamically typed languages. Yesyesyes ducktyping, &etc. I can't access elements in a hash the same way I access elements in an array so that's not really applicable here.

On the other hand,
i=0
File.open("data.txt", 'r') do |file|
  file.each do |line|
    i += 1
    puts "#{i} #{line}" if /dialog/ =~ line
  end
end
puts "----------------------------"
puts "Searched #{i} lines of file."

was relatively easy. Except for the false start with File.foreach which didn't seem to actually be giving me full lines from the file. Looked like it was giving me strings the size of some internal read buffer. Frankly, I expect enumerating a file to give me each line. Maybe it was user error.

Still. I'm not particularly impressed with Ruby. It feels a lot like working in PHP 8 years ago. Only with anonymous functions. Day3 is subtitled 'Serious Change' so maybe that'll be interesting.

7L7W Week 1: Ruby Day 1> Hellooooo Ruby

Somehow I was expecting more... wow factor? For as popular as Ruby is and for the kudos it gets it really doesn't, yet, feel more natural or seamless to me. Maybe I've spent too much time with 'harder' or 'crustier' or 'more obtuse' languages to get it. /shrug

Maybe day 2 will have more excitement; I will endeavor to be open minded about it until at least day 5.

Seven Languages in Seven Weeks

Go.

Land of Lisp chapter 8

In chapter 8 we build a Wumpus-style game. And if you recognize that reference then you must be at least as old as I am and allow me to reassure you that this will not be the basic Wumpus of yesteryear.

No, we're making Grand Theft Wumpus! Grand Theft Wumpus includes a few twists on the traditional Hunt the Wumpus game. The story is different but I'm not going to get into it. Buy the book for that. Suffice to say that you have one bullet, you're looking for the Wumpus, there are Glowworm Gangs that will mug you and ditch you elsewhere, and there are police checkpoints around town that end the game for you. Exciting!

The GlowWorm Gangs (GWG) are at random nodes in our game graph (yes, we're going to leverage that again) and the police blockade random edges. You can see GWG lights from one node away, you can hear sirens on the nodes to either side of a checkpoint, and the Wumpus has left a trail of blood that is visible in any node (bizarrely enough) up to 2 nodes away from himself. As the player you can move around town dodging checkpoints and exploring the randomized terrain and when you think you have the Wumpus pinpointed you charge in with your last bullet and win or lose based on your deductive reasoning.

That's the basic mechanics. Of course, the code involves rather more complexity than that so let's get started. First we have some basic parameters and helper functions.

The game's operating parameters appear first (the book helpfully forgets to include the *player-pos* parameter which made a nice troubleshooting exercise). random-node just returns a random number between 1 and the node max (*node-num*) inclusive. edge-pair returns a list of edges that describe a two way path. We'll use this because the game world is going to be an undirected graph meaning we need the edges defined in both directions. Finally we have make-edge-list which gets us to our first interesting (sort of) bit. Here we use a loop to collect a bunch of edge pairs between random nodes and then append them all into a single list.

Let's take a look at the structure of loop since it appears to be a bit awkward. The spec (google CLISP hyperspec) is dense with meaning and utility but in this chapter we only use it with two 'name clause's. We use a loop for and a loop repeat. loop for is your basic for loop with a defined index variable and a range for that variable over which the code block executes.

loop repeat just repeats the code block for the specified number of times.


You may have noticed the collect symbol in there. Based on my understanding of the spec (minimal I assure you) that's called the main-clause of the loop and in this case is an accumulation-clause, sub category list-accumulation, called collect. How that differs from append, collecting, or etc as referenced in the spec I wish I knew. Suffice that it will give us a list of edge pair lists, as in (((1 . 2) (2 . 1)) ((2 . 3) (3.2))), which is sort of what we want. Except that's nested deeper than is practical so we use apply to append all these sub lists into a single list like ((1 . 2) (2 . 1) (2 . 3) (3.2)) which is more readable to boot.

Now you might note that make-edge-list repeats the loop for *edge-num* iterations and creates a random path each time. The astute observer will note that this will likely leave many nodes inaccesible from some or all other nodes; in short it makes islands. It also creates some duplicate edges. We'll handle the duplicates in a later function. Right now we need to get the islands bridged.

First I'm going to blast a lot of code out in order to make what might be a philosophical point.
Our island prevention code:


That's a lot of pretty dense code. I'm discovering that when I read Lisp I have to read it from the inside out. But when coming up with the algorithm it has to be written from the outside in. Which, actually, puts me in mind of a time reversible process. Once the code is written if you want to understand it you have to perform the process in reverse. Maybe I'm just clueless. Moving along. Let's look at that again with some things brought out. Unfortunately I have yet to find a way to force custom highlights into a gist, so we're stuck with basic styles for this block.

[
(defun direct-edges (node edge-list)
  (remove-if-not (lambda (x)
                    (eql (car x) node))
                 edge-list))

(defun get-connected (node edge-list)
  (let ((visited nil))
       (labels ((traverse (node)
                  (unless (member node visited)
                     (push node visited)
                     (mapc (lambda (edge)
                              (traverse (cdr edge)))
                           (direct-edges node edge-list)))))
               (traverse node))
        visited))

(defun find-islands (node edge-list)
  (let ((islands nil))
     (labels ((find-island (nodes)
                (let* ((connected (get-connected (car nodes) edge-list))
                       (unconnected (set-difference nodes connected)))
                  (push connected islands)
                  (when unconnected
                    (find-island unconnected)))))
        (find-island node))
     islands))

(defun connect-with-bridges (islands)
  (when (cdr islands)
    (append (edge-pair (caar islands) (caadr islands))
            (connect-with-bridges (cdr islands)))))

(defun connect-all-islands (nodes edge-list)
  (append (connect-with-bridges (find-islands nodes edge-list)) edge-list))
]

Now first allow me to apologize for eyestrain. I tried to pick colors that weren't too garish or hard to read against the background without spending a lot of time on it. I'm not here to make beautiful copy. If you can get past that though you'll see the patterns. Each function has its color and every function scoped inside it has a washed out color in the same shade (I'm sure my use of terms would make any artist cringe, sorry). That lets me see recursion, as well as the flow of the code at a glance. I swear someone has to have put this kind of functionality in an IDE somewhere but I'll be boogered if I can find it (no; I'm not interested in learning emacs (which from all descriptions is the panacea of programs though I don't really know if it can do this); one heavy duty learning project at a time, go away). But to the point examining the code highlighted this way it's pretty easy to see what does what.

connect-all-islands is clearly top of the heap, it calls connect-with-bridges but that function doesn't go anywhere else (except itself ;) )so we follow find-islands. It creates a find-island function that calls get-connected. get-connected defines traverse which, in addition to being recursive, calls direct-edges which is the end of the line. direct-edges is the most interior function so we'll start there and work our way back up the heap. Perhaps I'm just bad at reading code or don't have enough practice with Lisp but this is the way my brain has to work in order to grok it for some reason. Turns out the order the functions appear in the book are inside to outside but I didn't know that when I first looked at the code and, if you've worked on enough code from other people, you can't expect that to be the case in any given set of code. Anyway.

In direct-edges we find all the edges in a list that start from a particular node. The lambda function compares the car of the given edge, x, and returns truth if it's the same as the node parameter the function was called with. remove-if-not deletes any item from edge-list that returns false from the lambda.

In get-connected we build a list of visited nodes. We define a function traverse which we the call recursively against each node linked to the node parameter in the edge-list parameter. At each node we first push it onto the visited list (which acts as progress tracking, return value, and recursion limiter because the unless form controls the recursion of traverse by testing the node against existence in visited) then we map traverse across the cdr of the list of edges provided by direct-edges for the given node. In the end we return everything we've accumulated in visited.

Allow a brief interlude here to define a few new language functions. let* works precisely like let except it allows references to other variables within the variable definition form. So

will run fine (returning 8) while

will cause a parse error (specifically that variable a has no value, though it's clearly defined right there). It's important to note that order in let* matters. The variable still has to be defined before you reference it.

We'll also use set-difference which simply takes two lists and returns what is in the first list but not the second.

Without further delay the find-islands function defines a function find-island. Allow me to make another aside. I deplore the use of plurality to differentiate the interior function from the outer function, even though it makes semantic sense, because it makes it damnably confusing to read properly at a glance unless they're highlighted like above. This gets even worse when you realize that the variables node and nodes act precisely the same here. node is one of the parameters of the outer function and nodes is the parameter of the inner function. Compounding your confusion would be the fact that node is fed to find-island in the body of the outer function causing significant (for me at least, maybe I'm a dunce) mental dissonance between giving a singular variable with a single node (assuming the semantics of the variable name are to be trusted! which in fact they aren't as we'll see shortly) in it to a plural variable which (semantically) should expect to receive a list of multiple nodes. Which taken together becomes a big jumbled mess of functions and variables that all look alike. Makes it a serious task to make sense of when it's not really that complicated. Now all this is probably just a failure of my intelligence. But for me, it reads a lot better like so:


Now we have, semantically, find-islands which defines explore-island which gets all the interconnected nodes in a given 'island' and then recurses on the nodes that aren't in that 'island' (thus 'exploring' the unexplored-nodes). This is perhaps a little sparser but I can grok it easier; in particular the differentiation of the names is critical to my understanding. Now, a more detailed deconstruction.

The find-islands function defines a function explore-island which uses get-connected to find the list of nodes that can be reached from the car of the parameter unexplored-nodes and put them in the connected variable. Then (using the magic of let*) we get the set-difference of unexplored-nodes and the nodes connected to this 'island'. Those nodes are still not 'explored' so we recurse them back into explore-island after pushing this 'island' (connected) onto the islands variable declared at the top of find-islands. In the end we have a list of lists of connected nodes. A list of islands, if you will, which we return.

Now the connect-with-bridges function which just takes a list of islands (notice a relationship there?) and builds a bridge between the first two. The logic is simple, even if the code looks a bit confusing at first. First look inside the append form at one of the two parameters. We'll start with the edge-pair since it's the easier one. It gets the first node in the first island in the input parameter and makes edges with the first node in the first island in the tail of the parameter. Confused? Read the c*r's backwards. (caadr islands) takes the tail (d) of islands (the second through nth term), gets the first (a) term (or island) and pulls the first (a) term, or node, off of it. Similarly for caar. The second term in append recurses into connect-with-bridges using the tail of the input parameter. Since we've recursed we need to look at that when form now. That just causes recursion to end when the function only gets a list of one island (there aren't any more islands to connect to, obviously). At which point we start returning the appended lists back up the recursion chain until at the end we have a list of bridge edges that will join all the islands given in the parameter.

Finally, the connect-all-islands function takes a list of nodes and their edges, uses find-islands to get the list of islands, gets a list of bridge edges by feeding that to connect-with-bridges, and then appends those bridges to the input edge list outputting a list of edges that will reliably connect every node together by at least one path. Phew. That feels a lot more complicated than it really is. But if you grok all that at once then I think we're well on our way to 'learning' Lisp (said by a raw neophyte so take it for what it's worth).

We are not, however, done with the hard work of the chapter. Next we need to convert our raw edge data into an alist. We'll also add the police roadblocks, since those exist along the edges rather than in the nodes. Here's another code dump.

This is somewhat less complicated than the last batch. Starting with edges-to-alist (which is the most interior function in this batch) we take a list of edge pairs and convert it to, apropo to the function name, an associative list of nodes and destinations. The last line in the function generates a list of the nodes that act as the starting point of each edge (which is effectively all nodes since the list is an undirected graph; so I'm not sure if there's a purpose to this as opposed to simply making a list of the integers from 1-*node-num*). Duplicates are removed (which is all remove-duplicates does by the way) and the resulting list is mapped by the lambda function. Within the lambda we find another mapcar which creates a list of the unique edges in the full edge list which start from the node given to the lambda. The mapping function for this interior mapcar is another lambda which creates a list of the destinations (the cdr) of the edge given to the lambda. The list result from the interior mapcar is then consed onto the original node. The reulsting list returned by the outermost mapcar (and thus the function) looks like ((1 (2) (4)) (2 (1) (3)) (3 (4) (1)) (4 (1) (3)) for a circular map with nodes 1, 2, 3, 4 in sequence.

The add-cops function takes an alist of edges (coincidentally of the type created by edges-to-alist ;) ) and a list of edges in which there will be cops (this list is generated by the outer make-city-edges function which we'll get to next, it's an edge in the format (x . y)). The outer mapcar just feeds the alist to the lambda and returns a list of the results. The logic all occurs within the lambda mapping function. First t declares node1 and node1-edges variables by breaking up the alist element it's given by the mapcar form. The interior mapcar then takes node1-edges and maps another lambda across it. This interior lambda first declares node2 as the car of the edges it's given (recall that our alist looks like ((1 (2) (4))... so the mapcar is looking at ((2) (4)...) and thus the interior lambda gets (2) which it needs to pull out of the list in order to operate on). The destination node (node2) and the start node from the outer lambda (node1, which is still in scope) are then converted via edge-pair (which you'll recall from earlier takes two nodes and creates an edge cons in both directions between them) and the intersection function is used to see if either of edge in the pair appears in the list of edges-with-cops (using the equal function as per the :test keyword since these we're comparing conses). if the intersection function returns anything at all then the node2 (the edge destination) is consed to 'cops to flag that destination. Otherwise the original edge (as it was given to the lambda in a list) is returned. In either case the resulting list (either of the destination or destination plus flag) is consed back onto the original node and the resulting alist returned to the outer mapcar. The result of the whole function looks like ((1 (2 'cops) (4)) (2 (1 'cops) (3)... which we can then parse for cops pretty easily by getting (cdr (assoc destination (cdr (assoc start edges)))). From the inside out that's getting the the current node from the edge list, getting the destinations from that node, getting a specific destination from from the list of destinations, then looking for a cdr in the destination's list (which would be our cop flag if it exists).

And now the outermost function in this clump of functionality, where we finally bring connect-all-islands and make-edge-list into the mix. The make-city-edges function uses let* to define a variable nodes as a sequential list of all nodes in the game, pass nodes to connect-all-islands to put a list of edges in edge-list and finally uses remove-if-not to generate a list of edges with cops using a lambda function that randomly returns true at a frequency modulated by *cop-odds*. Then it runs the edge-list through edges-to-alist which is returned to add-cops which returns the final output of the whole function. Basically, all this function does is figure out where the cops go and orchestrate the dance of other functions.

So now we have all the edges ready. We also need to put together the actual nodes since they'll have some context associated with them. What context? Well there's presence of the wumpus or GWG for starters but we also will need to indicate proximity to cops, GWGs, and the wumpus using sirens, lights, and blood respectively. While we could, technically, calculate proximity to these things at each move that would be an pointless load on processing since
1) Blood spreads out by two moves which increases the search range dramatically
2) The proximity search would either have to be completed at each move or a map kept up with in memory and if we're going to do that we might as well preload it all since...
3) It only takes a few bytes of memory and doesn't dramatically slow down game initialization.

So let's build an alist of nodes which includes all the localized context of each node. For starters we'll make a couple of helper functions.


neighbors just returns a list of the nodes neighboring the given node (isn't there another function that does this up there somewhere? I'm not sure now... Damn, this post is too long). It conveniently discards the COPS data. within-one just takes two nodes and checks for the second node in the neighbors of the first.

within-two first checks within-one. If that comes up false it gets all the neighbors of the first node and uses a lambda to check if the second node is within-one of them. If any of them are then some evaluates to true.

Now for the core of our node alist construction.


First a let form assigns the wumpus to a random node and as many GWGs as the game is configured to use are given random nodes and accumulated into a list. Now the guts of the make-city-nodes function is a loop that accumulates the output of two cond forms, and a when form. This is actually relatively easy to see from the code; the first cond returns '(wumpus) if you're in the same node with him, '(blood) if you're within two nodes, or nothing. The second returns '(glow-worm) if you're in a node with the GWG and '(lights!) if you're within one node of a GWG. Finally if there's a cdr in one of the destinations in the edges alist (which you'll recall from above will be our cops flag) the when will return '(sirens). All of this is appended into a list beginning with the node number.

Our play space is complete! Huzzah! Fire up the game and let's have a go at it! What's this? Where's the health bar? These graphics suck! Who wrote this piece of ... oh right. Derp! We seem to have forgotten the UI... back to the interpreter! The new-game function is quit basic.


First things first the find-empty-node utility function does just that. There's a risk here of infinite recursion though if there are too many GWGs or cops. Basically it looks for a node with no cdr in the node map so if every node has a flag of some sort then...

new-game itself simply uses the existing functions to set up some globals. It's mostly self explanatory. *visited-nodes* is just a list of nodes we've been in to save the state of the current game. draw-city just uses our existing Graphiz functions to draw the full map of the city. What's this? draw-known-city is undefined!


Ah, there it is. Glad to see it's back on the map. So the draw function here simply leverages Graphiz again. Of more import are the two helpers. known-city-nodes uses mapcan which appends the outputs of the mapping function together into a list. It maps across *visited-nodes* and the lambda function gets the edge destinations. So we end up appending together a list of all visited nodes and the destinations adjacent to them. The duplicates are removed and then this list is fed into the other lambda which gets the listed nodes directly from *congestion-city-nodes* and appends a * to the current player position or a ? to any node that hasn't been visited yet; this allows our map of the known city to include edges to places we haven't been because the nodes need to be there for the graphing utility while also being visually unambiguous. You could accurately call the ? the "Wumpus Fog of War™".

known-city-edges works similarly. The inner mapcar pulls the edge destinations for a visited node and if the destination is in the visited list it sends the whole thing to be consed to the original node. If it hasn't been visited then it makes a list of the destination's car and just sends that. This allows COPS flags to appear on edges that you've seen both sides of.

So much for our graphics (megatextures eat your heart out, these grafixs easily scale to any resolution!). Now we need to be able to control movements within the game world.


Three simple functions. They both call the same helper function, charge just sets a flag to indicate that we're going to charge instead of just walk.

handle-direction attempts to get the pos (the node we're going to) out of the possible destinations for the player's postion in *congestion-city-edges*. If it can't then edge is false and it outputs the error. Otherwise it calls this function:


The first thing that happens is we get the player's current position into node and then we check to see if 1. there's a GWG there and 2. we haven't been there before. If both of those are true then has-worm is true (even if there's a GWG, they only mug you once; you don't look that wealthy). With those variables set we pushnew the position onto *visited-nodes*, update the current position parameter, and redraw the map of the known city. Next we check for changes in the game status. The cond checks for cops on the edge you followed which ends the game, then for the wumpus (and prints a message based on the charging flag). If the wumpus wasn't there but you were charging then you waste your last bullet. Finally, if there is a GWG in the new node it moves us to a random new position. It should be pointed out that the recursive call to handle-new-place here sends nil for the edge parameter which, by nature, fails the cop and wumpus checks above.

Now ideally when the game is over we'd set some kind of ending condition but, in this case, we'll just print some messages and go on taking input. So technically winning and losing is a bit pointless. Hey, this isn't a triple A game we're making here; it's a language demo. As for playing, it's a bit fiddly. Open the known city map PNG file created by Graphiz in your browser. Yes, that's your graphics. Now enter (walk #) or (charge #) at the REPL and reload the image in your browser. Yeh, I said it's fiddly didn't I? I also said it isn't intended to be AAA right? I'm sure I said that somewhere...

That concludes this (rather long) post. If you think it took you forever to read I'm afraid it took me even longer to write it (week long interruptions are horrible). The code files are at...
grapher.lisp
GrandTheftWumpus.lisp

You'll want to do the following:

to get things running (using the correct paths of course).

Land of Lisp chapter 7

So a while back I mentioned needing a drip-feed of neurochemical triggers in the form of a productivity chart. I'm now 2 weeks late on a promise. Call it supporting evidence. So moving right along.

Chapter 7 covered more interesting list structures than have been used so far. It also comes across as quite dry so I'm liable to not spend much time in spots.


We start with dotted lists and pairs. A dotted list is simply a list that isn't terminated with nil. If we go back to thinking of Lisp lists as similar to a linked list structure a dotted list would be the same as plugging a data value into the last pointer in the chain. Which would be fugly in a linked list but works out alright for Lisp. Incidentally the dot notation used to print these lists

can also be used as a replacement for cons as in (1 . ( 2 . 3)) or for a common list as in (1 . (2 . (3 . nil))). I would assume using one form over the other would be a matter of taste and convention. The use of dotted lists regularly in code is supposedly uncommon however the book does state that running across such lists happens often which is quite contradictory and I'm not sure which side of the tale to believe. Either way I'll know what I'm looking at when I meet one. There is a relatively standard usage though in concisely describing pairs of things.

Additionally circular lists are discussed; these are simple enough to me that I'll gloss over them. Basically, the cdr of the final cons cell points back to one of the prior cells in the list. You could, if you felt like it, craft a very complex list using a combination of circular references. You'd also confuse the hell out of the interpreter unless you warned it that you were going to by issuing (setf *print-circle* t) which basically tells it to take a little longer in the print routine to make sure it doesn't get stuck printing in a loop.

Association lists (or alists) are also discussed which is, predictably, a list of pairs though presumably it's a list of keys consed to values which could themselves be further lists. Discussed here is a list of dot pairs. This is a convenient structure but apparently becomes inefficient when the list grows beyond a few items. Finally it discusses tree structures in data which we've already been using to some extent. If you've been watching you can see that Lisp lists are adept at handling trees as each branch basically has a symbol by which it can be referenced in the car of its cons cell. If I rip an example straight from the book

we can see this clearly. The *house* is composed of walls, windows, and roof. Each of which is a symbol identifying a list of its component parts.

The last half of the chapter covers Graphviz which takes formatted text input and generates image graphs based on the data. This is largely just data format manipulation code that takes the node and edge parameters defined for the wizard game and converts it to text output properly formatted for Graphviz. I'm not going to discuss this because it's largely boring; feel free to dissect the code linked below. Just as a clarification, data conversion is at the root of the beginning and ending of every program. It is vitally important, clearly, and a topic worthy of understanding. However the majority of the code I'm skipping is just string manipulation. Not only is it a thoroughly understood form of data manipulation it is, in my opinion, extremely dull; like a video game played 4 or 5 times already becomes dull in a vaguely interesting way. I'm going to cover new topics and functions introduced here but I won't be bothered with the boring details because I want my life to be more than vaguely interesting.

What I will discuss is new functionality. The substitute-if function

feeds each item in the target through the predicate-function and when true it substitutes the subvalue and returns the final result. This is demonstrated to work on lists and strings though I suspect it works on lists and a string is simply silently converted to a list of chars and back again.

The complement higher order function returns a function that basically inverts a predicate function. So

returns a function (which could be fed to another higher order function or presumably used in lambda) that returns the opposite of the alphanumericp function (which appropriately enough returns true when given an alphanumeric character). So in short, the function provided by complement above would return false when given [a-zA-Z0-9] and true for any other character.

A noteworthy concept on display in this chapter is the use of side effects. In each of the functions created to reformat the data we aren't really concerned about the output of the function itself. Instead the functions print the data to the console using princ and the output is ignored. This allows us to have greater control of what gets generated and easily review and debug that output. In the final function we'll simply capture the console output to a file. This runs against functional programming style as it relies on side effects. I honestly don't care; it works, it's clean, it facilitates code reuse (which we'll see in a minute) and I'm not religious about programming technique.

Once we've created all the functions required to reformat the data into a Gaphviz format we need to run that data through a Graphviz converter. The following function handles that task.

This gets interesting. Firstly, there's that thunk parameter. What a funny name for a symbol. According to Wikipedia (clearly the authority in computer science studies >.> ) thunks were invented by Peter Zilahy Ingerman and the term was arrived at because it's 'the past tense of think at two in the morning.' Which I can entirely believe. I'm not a hardcore compsci major but I'll do my best to take a whack at describing these, if only to help solidify my own understanding. Also called suspensions these functions offer a means of controlling the timing of evaluation of computations. Why this might be important (beyond deep efficiency mining) isn't readily apparent to me. The book makes the case that wrapping the graph->dot function inside a thunk delays the computation and allows the dot->png function to capture its output but I would argue that the same effect would be had if you simply plopped the function directly into the dot->png function as in this code

That gets you precisely the same output via the same methods. So it seems to me that what the thunk amounts to in this usage is to blackbox the creation of the data processed by the dot->png function. This is something I definitely understand and it allows us to plug any function name we want into the code above provided that the function outputs to console and (preferably) generates data parseable by the Graphviz 'dot' command. This also gets us off the hook for not actually outputting the correct data from the function directly. We use the thunk as a nullary (parameterless) function and ignore its output relying solely on the side effects of the function and the use of global values to perform the computations required.

Now, some less crunchy aspects of the function. The with-open-file function is very similar to let in that it defines a symbol to be used in the following forms.

The symbol becomes a stream variable (glossed over here) which is then available within the with-open-file form to be written to. In the usage above we very cleverly redefine the *standard-output* global stream variable (which is coincidentally the default stream for Lisp printing functions) to point to a file which is opened in write mode (:direction :output) and overwrites any existing file (:if-exists :supersede). Thus all the prints done from within the thunk (which we execute with funcall) are written to the file filename due to the dynamic value of *standard-output* from within the with-open-file form.

Now would be a good time for a quick interlude on keywords. These are symbols prepended with a colon as in :if-exists. These might be thought of as constants (though I'm unsure of the accuracy of the comparison to a C constant). They have an inherent value and that value is themselves and cannot be changed.

These are used in a number of functions to define various options such as file open modes. Options that might otherwise be incomprehensible strings of apparently arbitrary characters (yes, I'm looking at you Perl).

The last part of the chapter discusses the functions for generating an undirected graph. The siginifcant difference here is that the uedges->dot function uses maplist instead of mapcar which (as you might expect from the mnemonic) executes a function across a list (map) but instead of sending each car it sends the remaining list at each iteration (car vs list). Then the lambda function uses unless to skip any edges that are repeated later. The end result is that only the last direction of an edge gets printed but since the different directions of travel are meaningless in this context that's what we want.

The code for this chapter is at:
grapher.lisp
TheWizardAdventureGame.lisp


You'll want to do the following:

to get things running (using the correct paths of course).