Metacircular evaluator

Every culture have their own rites of passage. Recently I passed one of those, as I wrote my own lisp interpreter. I chose to write on with Hy, as that is a language I currently enjoy most. I also found certain satisfaction in writing an interpreter with a language that closely resembles the language the interpreter is supposed to be working with. There are many lisps in the world and this one isn’t particularly special. But the goal wasn’t about creating something spectacular. The goal was to write a complete interpreter, learn while doing so and appreciate the elegance of the eval-apply – loop. I mostly following the excellent SICP lecture from 1986 by Gerald J. Sussman. There’s a little bit code here and there (most notably the reader part) that I crafted, instead of following what he was explaining.

Normally, people under 40 and who don’t have several children are advised to be careful. If they’re really worried, they should leave. Because there’s a certain amount of mysticism that will appear here which may be disturbing and cause trouble in your minds.

Continue reading

Composition in functional programs

For the longest time I have been pondering how to structure functional program in a way it is not inflexible and rigid. With object oriented languages I can always make simple objects and compose those together to form more complex; however, I didn’t really know how to do that with functional programs, until I did some reading/watching of excellent Structure and Interpretation of Computer Programs. Turns out that the composition with functional programs is as easy as with object oriented. Instead of building objects, I should build basic functions and combine them to more complex one.

For Herculeum I wanted to write two different types of artificial intelligence (more like automatons though): one that would make rats to walk alongside the walls and one that would make fire beetles to patrol in the center of rooms. Both of them share quite a deal of functionality: moving to area to patrol and walking around there. Finding the area to patrol is different in details, but similar in broader scale.

So, I ended up with a general routine looking like this:

(with-decorator logged
  (defn patrol [is-patrol-area start-patrol ai action-factory]
    "routine to make character to patrol area"
    (let [[future-location (new-location ai.character (second ai.mode))]]
    (often (if (and (can-walk? ai action-factory (second ai.mode))
		    (is-patrol-area ai.character.level 
				    (first future-location)
				    (second future-location)))
	     (walk ai action-factory)
	     (if (is-patrol-area ai.character.level
				  (first ai.character.location)
				  (second ai.character.location))
	       (do (start-patrol ai)
		   (wait ai))
	       (walk-random-direction ai action-factory)))
    (wait ai)))))

The nifty trick here is that I’m passing in two functions: is-patrol-area and start-patrol. There first one is used to identify if a given location is a area that should be patrolled. The second one is used to transition into patrolling mode (probably could use the same function with a little bit tinkering).

After writing that, it was easy to write versions for rats and fire beetles:

(def patrol-room (partial patrol is-open-space? start-patrolling-room))

(def follow-wall (partial patrol is-next-to-wall? start-following-wall))

Here I’m defining two new functions: patrol-room and follow-wall. They are created by making partial function of patrol and supplying the functions that can be used to identify when the creature has arrived area to be patrolled and another one used to transition into patrol mode. Since two out of four parameters are already given, the resulting signature is as if they would have been defined as:

(defn patrol-room [ai action-factory] ...)

(defn follow-wall [ai action-factory] ...)

Now I have two functions with identical signatures, but with unique behaviour. In the same way I can define other aspects of AIs and build more complex functions from simpler ones, while reusing the common logic.

edit: well, identical except names. But the name does not matter that much, since the functions can be passed as parameters to other functions, that end up calling them by using the parameter name and not the definition name.