• entries
122
246
• views
89846

# Graphs

201 views

So this is going to be one of my most ontopic (with respect to the site) posts ever.

I originally began my project in C# but quickly hit its abstraction ceiling. Well, I did not actually hit it but thinking forward to what I wanted to do, I realized that I need the best abstractions that the CLI could provide. Good as C# is, it is still too similar to C++ and Java.

Whenever someone says .NET, people instantly think C#, which for people who enjoy exploring the outer edges of .NET (or more appropriately, the CLI) can be quite feather ruffling. With respect to programming, my project was began for three reasons: to rekindle my interest in programming, learn about .NET and the language independence it claims and to test its CLI claims. It has lived up to and beyond claims made in this area. Indeed Rebooted was suprised that I was able to get all the languages working cross platform - it was due to no special skill of mine but the incredible ease that which the CLI allows all those who obey its rules to interoperate. The languages need not know about each other so long as they speak the common tongue. Now, it is not completely trivial - there is still a need to design what classes you plan to expose outwards carefully, especially with respect to types (or enter typing hell - super nested generic classes), so they can be consumed without being choked on. Nonetheless the process is smooth and I have yet to feel the need to beat my computer with a bat while working on this project.

As stated in an earlier post and will be gone over in further detail in a future post, I have switched to Nemerle as the main vehicle for my engine for reasons due to its incredible macro system (lisp level, quotations, exposed compiler api) allowing it if i understand Apoch, to meet the linguistic requirements of a foo, OOP and ease of code organization, rich type system (perhaps overly so...despite .net) and is functional (despite .net). The last part is what I want to focus on in this post.

People wonder if you can write a game in a functional language. I say yes but not in the strict sense. I take the same stance of functional programming as the makers of OCaml where (loosely quoting) they state that functional programming is not so much about immutability and lack of state but rather a program that is more or less a composition of black box like functions that though they may contain some mutability internally, on the whole, the behaviour of the program is essentially functional.

Nonetheless it does not do to obsess over a paradigm at the expense of sensibility. Some problems are more tractible taken from an imperative stance while others are from a functional. That is why functional languages that mix this well allow for ease of concept -> code as smoothly as possible. What Nemerle does is mix the concepts OOP quite seamlessly with functional programming. This has the added advantage of not only allowing the abstractions of the functional paradigm but also the organizational benefits of OOP. However this post will not show much Nemerle syntax (due to its rich type code of Nemerle the stuff I will show required alot of upcasts and type constraints and other stuff with the IL code not as good as F# version and so it made alot more sense to keep it in F#).

By abstracting away, you reduce the number of steps that take you from concept idea to concrete code, allowing less mistakes and efficient implentation. It makes alot of sense to write an RPG in a functional language.

In fact it does not make sense to write an RPG in a language like C++. RPGs contain alot of concepts (quests, game-player interactions, conversations, magic, skills, vocations/jobs/class, pathfinding, ...) that are best represented with recursion, recursive data types and deconstructed with pattern matching.

I recently faced this when I decided to approach conversation in the game. Even C# did not have the appropriate constructs to do this most succintly. At first I thought to represent the conversations as trees but felt that they were not the most appropriate data structure. Thinking further, I realized that conversations are nothing more than directed graphs such that each node or vertex is either of type R (responses) or S (statements). Where for each R there is only one edge and each S has an edge to unique Rs (since if it does not then the S was not well formed). Each S has an edge to atleast one R node even if R is the empty node. By directed graph I mean a set (V,E) of vertices and edges with directed meaning that the edges are arrows:

I can think of no uses of the tools of graph theory with NPC conversing but if the need ever arises I will be sure to post on it. Nonetheless I set out to represent this concept in code. I realized that a graph could be treated as a list of vertices where each vertex is paired with a list of edges it points to. Hacking concepts out on the interactive top level of Ocaml i was able to come up with the following code:
let ins v g = (v , []) :: glet edges_to a b g =   let rec edg a b g g2 =      match g with        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g                   else edg a b g (l::g2)        | _ -> g    in edg a b g []let g1 = ins "Hello" []let g2 = ins "bye" g1edges_to "Hello" "bye" g2;;

The code is far shorter than the equivalent C# or C++ version would be. As well, by using the top level of OCaml I was able to accelerate my brainstorming and be assured that not only will I not have syntax errors when rewriting for the game, that it would work with no logical errors. As I stated earlier this did not translate well to Nemerle so I decide to do it in F#. However, to get it to communicate with other languages I had to rebrand it with .NET compliant classes.

The relevant F# code:
type 'a graph = ('a * 'a list) list let ins v g = (v , []) :: glet rec edg a b g g2 =      match g with        l :: g -> if fst l = a then ((a, b :: snd l) :: g2) @ g                   else edg a b g (l::g2)        | _ -> g         type 'a Graph = class 	new (a) = {graph_object = ins a [] }	val mutable graph_object: 'a graph 	member this.Insert_Edge (vertex_a, vertex_b) = this.graph_object <- edg vertex_a vertex_b this.graph_object []	member this.Insert (v)  = this.graph_object <- (v , []) :: this.graph_object	member this.List_Edges_To (v) = List.to_array (List.assoc v this.graph_object)end

Examples of usage:

The next post will not just be a test but will build converation around this and making accessing and listing much easier to the end user/me.

Nemerle is a nice enough language, but it fails one critical requirement of the Foo-language: the minimal abstraction is .Net, not the bare metal. Although P/Invoke within .Net is an excellent way to drop abstraction all the way to the OS/metal, it requires that you use a non-CLI language at some point. Yes, you can use C++/CLI if you need to share concepts from the .Net layer, but this goes back to the problem of languages having unequal footing: many .Net concepts do not exist in C++, and many C++ concepts do not exist in .Net. Since we've introduced two separate languages, we lose the benefits of building our entire abstraction stack in a single language. In a sense, we're using embedded languages again, which ventures into the same risks as DSLs in general.

Granted, it can be argued (correctly) that most software doesn't need a bare-metal baseline abstraction. The only real case where this matters is extreme domains where performance and hardware-access are critical, like 3D games. In these cases, the only real benefit of having a Foo bare-metal baseline is that the OS kernel and drivers themselves could be built in Foo dialects, allowing our abstraction-sharing benefits to work across an entire platform, and not just single applications. Obviously that's a bit of an ivory-tower ideal, but it isn't possible at all unless Foo inherently believes in bare metal.

But suppose the Below .NET layer 3D engine part was properly encapsulated such that it was perfectly partitioned and it could not understand constructs in your code but had to be talked down to. Suppose anytime we needed to talk to the machine we did this. Then this layer can easily be considered to be a special case of a base layer that which the .NET could be considered an entire massive layer above and which we have a sublayer that allows downwards communication to this base layer. arrgh im making no sense. what im trying to get at (which i feel instinctively) is that there is a style on a VM based language that has contructs to access the machine where this model is structurally equivallently (or very nearly so) to Foo - if this were topology Id say there was a homoemorphism between these two concepts.

I enjoyed this post quite a lot. It's nice to see more and more people doing interesting things on top of CLI.

I alway think a directed graph would be a good base for a conversation engine but when I start tinkering I find that's not what I want at all. Instead I usually find myself wanting some kind of domain level language.

There's usually a lot of conditional information. Only say X if you've killed the elf queen, or if it's raining, or if one of the characters has the orb of Jumogo. I also quite like to have non-deterministic elements, a bit player NPC might give you a little conversation about the weather, or a random bit of news, but he'll only talk about one of these each conversation you have with him. Sometimes you might want to lock off certain topics, until other topics have already been dicussed.

Quote:
 Original post by Balaam I enjoyed this post quite a lot. It's nice to see more and more people doing interesting things on top of CLI. I alway think a directed graph would be a good base for a conversation engine but when I start tinkering I find that's not what I want at all. Instead I usually find myself wanting some kind of domain level language. There's usually a lot of conditional information. Only say X if you've killed the elf queen, or if it's raining, or if one of the characters has the orb of Jumogo. I also quite like to have non-deterministic elements, a bit player NPC might give you a little conversation about the weather, or a random bit of news, but he'll only talk about one of these each conversation you have with him. Sometimes you might want to lock off certain topics, until other topics have already been dicussed.

thanks!

Yup I agree :) All that capability is definitely pivotal or what sorts of RPG do you have? But that is all covered and done easily in part 2. This was basically just the data structure to most easily represent conversations and will be built upon.

Ok, my thoughts.

Language features should be thought of in layers.
For example: functional -> message passing/reactive -> fully stateful. Use the simplest layer (functional being the simplest, stateful the most complex) that provides a clean solution to a problem. Don't write a lengthy purely functional component when just adding one updatable variable could greatly simplify your solution. Similarly, don't write an imperative algorithm that incrementally updates a collection of variables just to remember what it's doing from one loop to another when a clean functional solution would be better.
This is essentially what my idea of "functional programming" is.

On abstraction layers:
Since you have an interest it in, I'll mention that something I've been thinking about is how Category Theory can be applied to DSLs, with the languages corresponding to categories. I think this might be important for understanding how to best provide the ability to build the nessessary layers of abstraction (ie. what logic did for type systems).

Quote:
 Original post by Rebooted Ok, my thoughts. Language features should be thought of in layers. For example: functional -> message passing/reactive -> fully stateful. Use the simplest layer (functional being the simplest, stateful the most complex) that provides a clean solution to a problem. Don't write a lengthy purely functional component when just adding one updatable variable could greatly simplify your solution. Similarly, don't write an imperative algorithm that incrementally updates a collection of variables just to remember what it's doing from one loop to another when a clean functional solution would be better. This is essentially what my idea of "functional programming" is.

Fully agreed.

Quote:
 On abstraction layers: Since you have an interest it in, I'll mention that something I've been thinking about is how Category Theory can be applied to DSLs, with the languages corresponding to categories. I think this might be important for understanding how to best provide the ability to build the nessessary layers of abstraction (ie. what logic did for type systems).

Im feeling particularly dense (very much so) today but specifically how so? subcategories? Note too that category theory has already aided CS through topoi theory and monoids. the problem is i dont really understand what the issue with DSLs is. cant u just be careful? hehe i know n00bish. please clarify.

Quote:
 Original post by Daerax hehe i know n00bish

Nah you're quite an intelligent lad, you just need a gentle guide in the right direction [smile].

Quote:
 Original post by Daerax Im feeling particularly dense (very much so) today but specifically how so? subcategories?
Not subcategories, just an isomorphism between categories and languages. The analogy has been made by people because of how monads are used in Haskell to define the semantics of computations (exceptions, continuations, etc) and DSLs. There is a link between how categories describe independent classes of objects and how we want to describe independent languages and their semantics, laws, evaluation rules, whatever. Functors would correspond to translations between these languages.

Quote:
Original post by snk_kid
Quote:
 Original post by Daerax hehe i know n00bish

Nah you're quite an intelligent lad, you just need a gentle guide in the right direction [smile].

heehee thanks. Do you mean Haskell? I am already stretching myself too far learning too many concepts at once, Haskell seems like a very intimidating and large thing to tack onto the list which already contains Category Theory and Type Theory. I do enjoy the little sanity that I do have. But I do intend to learn it someday, it looks like it has taken the place of Lisp as the new hardcore hacker language to learn.

Quote:
Original post by Rebooted
Quote:
 Original post by Daerax Im feeling particularly dense (very much so) today but specifically how so? subcategories?
Not subcategories, just an isomorphism between categories and languages. The analogy has been made by people because of how monads are used in Haskell to define the semantics of computations (exceptions, continuations, etc) and DSLs. There is a link between how categories describe independent classes of objects and how we want to describe independent languages and their semantics, laws, evaluation rules, whatever. Functors would correspond to translations between these languages.

I do not quite understand what you mean but note that I only recently began studying category theory. I know that there is a category of languages - constructing categories is not so difficult if you understand your problem domain. a category is basically just a collection of objects with arrows, supporting composition, an identity notion and association of compositions of some functions f,g,h. Functional languages are instantly seen as a category.

I say subcategories because to become specific to languages perhaps you need to make certain restrictions such that you focus on certain subobjects in *your* category of F, functional languages by noting certain properties of your objects and arrows. You could then study isomorphisms between objects in F.

Nonetheless, despite my confusion, I wholly agree with your statements on category theory, I feel they are the most powerful tool for understanding invented yet by man and DSLs within a language certainly fall within the scope of their applicability.

---

Oh i get what you mean, you just threw me off when you said "an isomorphism between categories and languages", I was like but languages form a category..Anyways I guess it would be possible to carry languages to each other with functors but I feel that is overkill (for example there is a functor from the category of Languages to sets to discuss semantics more intuitively, language to language seems a bit unncessary) and may not even be possible since we want each DSL layer to be completely independent. Would it not be better to start from a more general category and then work downwards?

Quote:
 Would it not be better to start from a more general category and then work downwards?
Probably [smile]. I think category theory can be applied because of a link to category theory's key ideas, and because of the already existent link of monads in category theory and in Haskell.

Within the language we won't be interested in working with categories of course, but with these abstraction layers. Category theory could be applied to help us decide how to best represent and work with them. I said functor because I see Languages taking the place of Categories in our sub-theory.

Ah yes, Ive started to read that paper before, but have never completed it. Although a very good paper I disagree with it about the foundational abilities of category theory...that is why I decided to learn it in the first place. This person may not be farmiliar with Topoi. Just that ability to abstract is its greatest strength as a theory of theories, by removing all the fluff we might otherwise encounter, we may approach that notion of what a proof entails exclusive of all the drama that is within the internals of the mathematics.

Anyway, to point, what was confusing me was your terminology. I suppose when you say that we will not be working with categories I did not quite get your meaning. One way is what I suggest, by considering subcategories and isomorphisims of object but a certainly viable way but one which I feel would quickly get bogged down in details (my intuition only though) is where each language L, is constructed its own cantegory C(L) and we have some functor F : C(L) -> L which takes us from whatever abstractions specific to some category of ours to some other language. Again, I have never seen this in my neveulle studies of Categories. I am probably just being ignant though.

Something interesting about a certain type of categories called cartesian closed categories is the ability to recover your typed lambda calculus, T(L) as the internal language L of the category which was constructed from that very lambda calculus T(L) built over your theory on types. Indeed the internal language of any cartesian closed category is in fact a typed lambda calculus. Perhaps this may allow you to do what you wish?

Unfortunately for whatever reasons of insecurity computer scientists are more tight with information than mathematicians but you may start looking here:

Google search "lambek and scott cartesian closed categories". Lambek and Scott in their 1986 paper discuss the equivallence of languages with the framework of CCCs and typed lambda caluli.

I cant wait until I become fluent in this...So much power.

p.s. cant believe I never rated you, always assumed I already had!

Thanks, that uncovered tonnes of stuff I hadn't seen before about categorical semantics.

Something I read hinted that because the simply typed lambda calculus is the internal language of a cartesian closed category, in turn you can convert a program written in a lambda calculus to an equivalent program in a combinatory language via mapping between different categories supposedly with different corresponding internal languages. This is very close to what I imagined.