Posted by Daniel Lyons
Sat, 19 Jan 2008 04:44:00 GMT
I somehow find myself participating in a game design group called “Etherware.” I’m not quite sure how, but at any rate, we’re discussing how to implement magic in a video game. Most video games implement magic as a list of pre-defined spells. This is very constricting.
My first reaction was, of course, that to make it better is to make it a language, and now we’re actually talking about making a programming language designed around a particular task and trying to find a compelling UI for it that doesn’t resemble programming.
We’ve identified so far four different “languages”: wand waving, rune cutting, verbal incantations and potion crafting. I haven’t read Harry Potter all the way through so I’m probably omitting several.
Jesse mentioned that he always prized the “true name” concept from various magic systems: that once you know someone or something’s true name, you have power over it.
A “true name” is just a string that can be used as an address. There are a number of ways to deal with this, probably the easiest one is just to make a hash and use that. It occurred to me that the number of objects in any game will be prohibitively large, and anyway, what do you do if the gamer creates new objects?
An easy solution to this problem is to use the memory address encoded in hex. But that’s not very user-friendly, or very pronounceable. Plus they tend to be quite large. On the other hand, you have encodings like base-64 which use the alphabet. Base-64 isn’t very pronounceable either, though. You could take the alphabet as-is and use it to encode numbers under base 26.
On the other hand, there are other types of orthographies, such as a syllabary, in which every possible syllable is enumerated. It wouldn’t work with English because of the vast quantity of dipthongs and consonant combinations, but it works quite well for Japanese, which has two syllabaries, katakana and hiragana. There happen to be around 115 distinct symbols in katakana. So, you can encode any number in Romanized katakana by removing any duplicate sounds, assigning an order to the orthographs, and converting the number to base 115. If you do, you’ll get something like this:
>> 12983.to_name
=> "ryavu"
>> 6.to_name
=> "ki"
>> 12983923239823.to_name
=> "megomeagyubika"
Converting back is easy if you’ve ever implemented atoi() in C:
>> "ryakujani".name_value
=> 33155983
>> "kyu".name_value
=> 53
>> "aeiouaeiou".name_value
=> 7158386439867648320
The latter example there is to illustrate the point that, just because it always works, doesn’t mean it always makes something that would be a word. I haven’t computed the probability, but it’s roughly the probability of a number showing up all 9’s. I expect it to be particularly rare because base 115 can represent numbers with a pretty high compression ratio. The set of three syllable words is 1,520,875 in size. There are 5 vowels out of 115, which means there are 60 ways to choose three vowels in a row, so 60 / 1,520,875 = 0.00395%, AKA not very likely. But still can happen.
Of course, there is already a swell system built into every language and every program of uniquely identifying an object. The memory address! And it happens to be a number. In Ruby, you can get at it with Object#object_id and convert back to the object with the please-don’t-use-me method ObjectSpace#_id2ref. Which means you could also have this:
>> h = {:this => "that", :name => 48}
=> {:this=>"that", :name=>48}
>> h.magic_name
=> "vachugyuku"
>> "vachugyuku".object
=> {:this=>"that", :name=>48}
Works with everything in Ruby, for free. Oh, is that a class?
>> Numeric.magic_name
=> "weseke"
>> "weseke".object
=> Numeric
Yeah, I think it is!
I’m pretty proud of the code. It’s BSD-licensed, so feel free to borrow it. Feedback appreciated!
Tags games, linguistics, programming, ruby | no comments
Posted by Daniel Lyons
Sat, 08 Dec 2007 23:48:00 GMT
“GWT 1.5, due in the first quarter of 2008, will produce “better” JavaScript code than manual programming by the industry’s best and brightest – in terms of speed, size and manageability of code. GWT 1.5 is also expected to improve compilation of Java code.”
—Google’s next web toolkit thinks it’s better than you
Let’s try that claim again with some different technologies. “gcc will produce ‘better’ assembly code than manual programming by the industry’s best and brightest—in terms of speed, size and manageability of code.” The claim sounds pretty unlikely, don’t you think? How are you going to do better than manual human intelligence on all three fronts that matter? But something is missing. What language are we compiling from and to?
GWT is in the somewhat ironic position of compiling Java to JavaScript. By analogy, this is like saying you can compile from C to Lisp and produce better Lisp than experts could—in terms of speed, size and manageability. Does that seem likely? Then how, pray tell, could someone compile from a language that lacks full closures and prototyping OO to one that does, improving all three of those things at the same time? For that matter, when has compiled code ever been smaller than manually written code?
I don’t know anyone using GWT, because the only people who would use it would already be using Java and I don’t know anyone doing serious web development in Java. Web development is hard in a way that precludes clunky languages (but not stupid ones like PHP).
It reminds me of the other night when my room mate David Baird and I were talking about simplicity. To some idiots, MySQL is simpler than PostgreSQL. This claim is bizarre to me, since MySQL’s source is 10 MB larger compressed, MySQL deviates intentionally and insanely from the SQL standard, and MySQL includes a variety of obnoxious features that no true database would provide. Yet it is considered simple and “industry standard.”
Half of it is from The Rise of Worse is Better, MySQL chooses to make the implementation simpler than the interface, whereas PostgreSQL prizes the interface more. Why else would MySQL’s SQL syntax change with every release, while PostgreSQL’s remains the same? But this doesn’t explain the absurd notion of table types, which only MySQL has.
There is another dichotomy here, between differing conceptions of simplicity. Which of these is simpler?
sum = foldr (+) 0
Or:
int sum(list_t list) {
sum = 0;
for (cur = list; cur != NULL; cur = cur->next)
sum += cur->value;
return sum;
}
There are at least three different ways of looking at this:
- “You’re comparing apples to oranges! Unfair!”
- “The C version is simpler because it’s closer to what’s really happening.”
- “The Haskell version is simpler because it’s closest to the concept.”
People who fall under category one are the kind of people who say things like “it doesn’t matter what language you choose to implement something in, because they’re all Turing-complete.” It only doesn’t matter if the time it takes to write, the experience of writing it, the quantity and severity of the bugs introduced while writing it and the human resources required to write it don’t matter. I think a lot of people say this because they don’t want to get into a religious war about language—it’s a cop-out.
What I’m really interested in is what happens to people to make them fall under category 2 or 3. I think this quote from Alan G. Carter’s Why No-One’s Noticed This Before may be the essence of it:
“We don’t miss what we haven’t got, and this can lead to seeing things in profoundly different ways. A person who frequently does juxtapositional thinking is aware of the importance of self-consistency in their thinking. If something doesn’t “hang together”, they know they have made an error. Often they use self-consistency as the basis of their thinking, deducing that something must be missing, and then being able to find it. A person who is rarely if ever in a position to do juxtapositional thinking, will not consider or expect self-consistency in this way. Their view of reality is therefore fragmented. If they don’t require their understanding to hang together, they develop the idea of “mere facts”. What are facts? What do they prove? Nothing! Instead they use their focussed attention to concentrate on compliance with a proceduralism, and they don’t let mere facts get in the way. They certainly don’t trust their own good senses.”
Look again at PostgreSQL. It assumes that the database is there to alleviate certain burdens. It provides you with SQL. At that point, the database’s job is complete and it is up to you to learn SQL. Learning SQL may imply learning the theory of relational databases. PostgreSQL isn’t there to hold your hand and help you do this. If it takes you 30 minutes to write an SQL statement, well, that’s how long it takes you to write it. People in category 3 don’t mind, because they’d rather have one comprehensive solution for their data situation that hangs together.
Look at MySQL again. Table types aren’t part of data management, they’re a leaky abstraction, an exposure of low-level details. MySQL’s query planner also sucks compared to PostgreSQL’s. Perhaps most damningly, MySQL doesn’t support two of the three fundamental set operations (INTERSECT and MINUS/EXCEPT). If you were modeling a relational database on set theory, you probably would have started there.
Yet MySQL is full of tiny details meant to “helpfully simplify” some aspect of databases. Such as the TIMESTAMP type. There is no other type in MySQL which is defined as equivalent to some other type plus some behavior. There is no other type in MySQL defined so, nor in all of PostgreSQL, defined in terms of behavior (when you UPDATE a row with a TIMESTAMP column, the TIMESTAMP column receives the current time even if you didn’t specify that it should be modified). However, I haven’t ever seen someone intentionally use the TIMESTAMP feature for what it’s there for, just people stumbling onto it and realizing that a whole bunch of data they thought they had has actually been obliterated. It doesn’t hang together.
David and I concluded that there is a kind of simplicity which requires learning and a kind of simplicity which attempts to avoid it. Some people find the thought of recursion and higher-order functions a lot less simple than for loops. And yet, for loops become more sophisticated in mundane languages with each successive one.
There are people who find the REPL a horribly frightening place. Look at the complete lack of “noise” in the Haskell code. It’s nothing but you, G-d and the problem. There is no public static void main. There is a desire to be typing while programming, and in plenty of languages you have to push this edifice of text around before you can begin to get anything done. There is a sensation of programming when really you’re doing nothing. You can reason operationally and have the appearance of getting things done. Somebody wrote an API for making new table types in MySQL. I have no doubt this is far simpler than improving the query planner. Someone else contributed a BerkDB table type for MySQL. I have no doubt this was fairly simple. But why would you? This is problem avoidance, but adds so many megabytes to the source code, which nobody even actually uses. There is a digital artifact to this lack of interest in actually getting anything done.
People use ActiveRecord to avoid learning SQL and relational database theory. Yet, I know plenty of people who have not studied relational database theory but who understand it anyway. A lot of people start out making tables that aren’t normalized. After a while they start to use joins. Eventually they acquire the insights, usually after not very long, say a year or two, and then they are as good as someone who has studied it. After a while they begin to be annoyed with MySQL. ActiveRecord is there to make dealing with the database more like dealing with Ruby. As long as everything is in one language, it should hang together better. But of course, ActiveRecord is built for MySQL primarily, but with an eye to portability. The advanced database users grow annoyed at it because it also represents problem avoidance.
The GWT is a lot like ActiveRecord. It wants to mitigate some problem which isn’t, in reality, a problem. It’s a nightlight. When you look at my Rails code, you see a lot of me manually executing SQL. This practice is encouraged by the books and DHH and many other Rails users do this. However, it ties you to a particular database—PostgreSQL in my case. Is your database a problem, or a solved problem? GWT is saying JavaScript is a problem, do you think JavaScript is a problem?
I can certainly look at Ruby and SQL and say, both of these things are great. I have some trouble looking at JavaScript and turning in revulsion, asking for Java to come and mitigate the pain.
Tags gwt, haskell, java, javascript, programming, rails, ruby, sql | 5 comments
Posted by Daniel Lyons
Thu, 20 Sep 2007 07:14:00 GMT
For a good time, please read a very twisted analysis of the benefits of performing poorly. (To my new anal-retentive readers: you try and figure out this guy’s name, and then I’ll cite it).
I have some remarks on Reddit which I’m proud enough of that I thought I’d share them with you sharks here. I wonder if the author has really listened to his own argument. I find it somewhat lacking in the “holding water” department:
“If you know the language to be dog slow any way, you’re much less likely to waste your time on the pointless microoptimizations that geeks so love…”
I think this one works equally well in reverse: if you know the language is already quite fast, you’re much less likely to waste time on pointless micro-optimizations that geeks so love. In fact, if your language is dog slow, there are probably more optimization opportunities than there are if it’s already quite fast, as a matter of diminishing returns.
“The fact that non-standard library code is inherently somewhat inferior adds further incentive to attempt community wide standardization…”
This fails rather spectacularly to explain why the Common Lisp standard includes such a huge standard library. Consider the inverse argument: “the fact that your library code runs as well as built-in code removes incentive to use the standard library.” In the magical imaginary world I pretend to live in, people apply appropriate abstractions without much regard for the performance—abstractions that perform radically poorly being considered inappropriate, I guess—but I would never imagine sitting on my hands, wondering whether or not I can “afford” the overhead of a function call.
“Python’s very slowness represents part of its competetive edge over languages that are in some ways better engineered and more capable…”
What is this, things that are poor in one area tend to be good in others?
I could only consider agreeing if somehow it were a zero-sum equation: all languages have equal amounts of effort applied to them, and some of it goes to performance. But it’s not a zero-sum equation, languages receive differing amounts of attention to different strengths for different reasons. Moore’s law and the rapidly increasing demand for programming alone have enabled Python to compete against a language three times older, better designed, implemented and specified.
Actually, no, that’s flat-out nonsense.
“I’d not be suprised if on the whole it greatly increases programmer productivity and results in clearer and more uniform code…”
I would tend to expect uniformity from any language which syntactically enforces it. :)
I certainly would not expect a poorly-performing program to go through as many stages of evolution as a rapid program. You have to factor in the compilation phase—but one usually doesn’t compile in-development Lisp programs while working on them. They evolve much more organically, because there’s not necessarily a separation between development and testing, whereas in Python there is to a larger extent. Supposing the compile-time differences are negligible (which, they are, if you are careful) I have a hard time believing that Python programs running more slowly permits more evolution to take place.
“Also, since only builtins have reasonable performance there’s added motiviation to become very familiar with the available builtins and far less temptation to roll one’s own version of say dict.setdefault (even if it it sucks)...”
I think the existence of sucky built-ins like setdefault contradicts the point about the quality of the standard library. From where I’m sitting, the quality of the standard library is a function of backwards-compatibility more than community involvement. Lisp has a larger, somewhat clunkier one because it is much older. Ruby’s library is much cleaner because it went through a lot of life without having to worry about backwards compatibility very much. Io is doing even better, having been designed by language aesthetes like Steve Dekorte who are familiar with a lot of good and bad APIs, and who aren’t afraid to break backward compatibility to make a global improvement in expressiveness.
This article nicely dovetails with an argument my friend Pi has been having with various cornholes on IRC about Python and Ruby. Ruby’s standard library is just plain nicer. Which do you prefer, based on your gut instinct:
foo.bar.baz.split.collect { |x| x.bazzle }.join(' ')
Or this:
' '.join([ bazzle(x) for x in string.split(foo.bar()) ])
Hell, for good measure, let’s toss in some Haskell:
unwords $ map bazzle $ words $ foo bar
I’m talking about your aesthetic reaction here. Your artistic reaction. You know which of these you prefer. You want the agglutinative glory of Ruby or the isolating awesome of Haskell. Follow your eyeballs on the above Python example. Compare to Ruby and Haskell. Your eyes hop around on the Python, trying to figure it out. Haskell and Ruby, your eyes slide across from left to right. You feel like you’re reading a language, not decoding one.
As an aside, slap the next person you meet who, ignorant of Haskell, rants about static typing. They’ve never used it, they have no idea what they’re talking about. They’re actually giddy or incensed about type annotations and other forms of busy-work. Don’t put up with it.
Tags haskell, languages, programming, python, ruby | 4 comments
Posted by Daniel Lyons
Sun, 01 Jul 2007 18:27:00 GMT
Last week I got somewhat acquainted with Cake. I have to admit, any framework is better than no framework, but this framework isn’t a lot better than no framework. I have heard good things about symfony but haven’t given it a shot. If I’m doing PHP, I’d rather be using Voltaire.
Since it’s trying to do for PHP what Rails does for Ruby, it’s probably fair to compare code side-by-side. Ruby:
@users = User.find(:all)
PHP:
$this->set('users', $this->User->findAll());
Hmm. I would have expected that to look more like this:
$users = User::findAll();
And then some view code:
<% for user in @users %>
<tr>
<td><%= user.name %></td>
</tr>
<% end %>
And in PHP:
<? foreach ($users as $user): ?>
<tr>
<td><?= $user['User']['name'] ?></td>
</tr>
<? endforeach; ?>
Hmm. I would have expected that to look more like this:
<? foreach ($users as $user): ?>
<tr>
<td><?= $user->name ?></td>
</tr>
<? endforeach; ?>
Tags cake, php, rails, ruby | 6 comments
Posted by Daniel Lyons
Tue, 15 May 2007 04:23:00 GMT
It seems a little petty to want something other than Cocoa/Objective-C on your Mac, since it’s light years beyond the dreams of most other platforms. Still, one desires to do as little work as possible. The “joys” of manual garbage collection and a poor iteration interface are going to be that much harder to bear knowing that they’re going to go away with the introduction of Objective-C “2.0” and Leopard.
I remembered F-Script. I was hoping that I would see a simple way to write a whole app in F-Script and deliver it as a standalone executable, NIBs and all, but I haven’t run into that yet. I hope it’s out there though, that would be a lot simpler than using Objective-C. I think this would be a really enjoyable development environment.
Interestingly, I found a way to do this with Ruby and Ruby-Cocoa using the newcocoa gem. Unfortunately, it didn’t look like it was going to make a universal binary, because I’ve got MacPorts installed. I might go back to that though, because that would be a lot better for application deployment. It seemed to do everything with NIBs properly and all that jazz. On the other hand, it opens up the delivering the source-code with the product problem.
For fun, I thought I would look for a Haskell binding. I don’t remember it before, but apparently there is this HOC (Haskell Objective-C) binding. It hasn’t been developed for a while, but it’s worth looking into. The mailing list is largely dead but according to the most recent post in March, it’s working still. I didn’t see if it uses NIBs and everything.
Now that would be awesome.
Tags cocoa, f, haskell, osx, ruby, script | 1 comment
Posted by Daniel Lyons
Mon, 07 May 2007 03:00:00 GMT
Not sure if anyone else uses Terminal on their Mac as much as I do, but if you do, and if you have RubyOSA installed, you may find this utility handy:
#!/usr/bin/env ruby
require 'rbosa'
OSA.app('Terminal').do_script('cd ' + ENV['PWD'])
It just runs another Terminal with the same current working directory. I called it clone.
Tags osx, ruby | 1 comment
Posted by Daniel Lyons
Thu, 03 May 2007 18:55:00 GMT
checkedSubjects = function() {
return <%= Subject.find(:all).collect{|i| i.id}.inspect %>.select(function(id){
return $F('lesson[subject[' + id + ']]') == 'on';
});
}
Is that more disgusting because there’s generated code in the JavaScript or more disgusting because HTML doesn’t let you work with controls in a nice way?
Tags javascript, ruby | no comments
Posted by Daniel Lyons
Fri, 27 Apr 2007 17:02:00 GMT
Let’s talk about things you never want to hear a language implementor say.
“Koichi decided to use native thread for YARV. I honor his decision. Only regret I have is we couldn’t have continuation support that used our green thread internal structure.”
—Matz
Oh, great! We get native threads finally!
“It doesn’t mean that every Ruby thread runs in parallel. YARV has global VM lock (global interpreter lock) which only one running Ruby thread has.”
—Koichi
So picture this if you can. I make 100 threads, each one doing some independent task. On Ruby 1.8 and below, each of those “threads” is really just an execution context that the language manages for me. Only one runs at a time and they only use one of my processors.
Well, we all hate green threads! So under Ruby 1.9 and above, if you make 100 threads, you get 100 threads in your OS. Each one running, potentially, on a different processor. But only one running at any given time!
And there are people who aren’t willing to use Haskell because STM is “immature?” This is fucking ridiculous.
“Parallel computing with Ruby is one of my main concern. There are some way to do it, but running Ruby threads in parallel (without Giant VM Lock) on a process is too difficult to support current C extension libraries because of their synchronization problems.”
—Koichi
Tags programming, ruby | no comments
Posted by Daniel Lyons
Sun, 11 Mar 2007 08:36:40 GMT
I just stumbled onto the best Fibonacci sequence implementation in Ruby, and at the same time, fell on a cool technique for lazy-esq programming. I’m sure somebody else has found this by now, but it’s news to me.
Anyway…
$FIBONACCI = Hash.new { |cache, n| cache[n] = cache[n-1] + cache[n-2] }
$FIBONACCI[1] = 1
$FIBONACCI[2] = 1
def fib(n)
$FIBONACCI[n]
end
A quick test reveals it’s a lot faster than the naive recursive implementation, but it retains most of the same flavor. Actually this is nicer. I got a result after a tiny fraction of a second for n = 100 with the Hash implementation, versus the CPU starting to warm up and me killing it after about 10 seconds with the naive verson.
Tags programming, ruby | no comments
Posted by Daniel Lyons
Wed, 22 Nov 2006 08:33:00 GMT
If you are interested in implementing quicksort in any reasonable language from scratch, you may not want to read this post.
I had some fun making this post but by all means draw your own conclusions and ignore my commentary.
The OO Languages
Io
List quicksort := method(
(self isEmpty) ifTrue(return List clone) ifFalse(
first := self first
rest := self slice(1)
below := Quicksort quicksort(rest select(i, i < first))
above := Quicksort quicksort(rest select(i, i >= first))
return below appendSeq(list(first) appendSeq(above))
)
)
I’ll be honest: this one took the longest and was the hardest to write. Additionally, it is the not very aesthetically pleasing (though moreso than any of the other OO languages), and I still don’t understand how Io knows when to execute a given piece of code (look at the select portion). It also was pretty unreadable until I separated the above and below variables out. I also didn’t understand why I needed return but it seemed to break the code to not have it there.
That said, it is very whitespacey, which is worth points in my book. This is the implementation I’m the least confident of. Io has changed a lot since I last was using it, and I never became very proficient at it.
Python
def quicksort(l):
if l == []:
return []
else:
x, xs = l[0], l[1:]
return quicksort([ i for i in xs if i < x ]) + \
[x] + quicksort([ i for i in xs if i >= x ])
For some reason, the list comprehensions didn’t do it for me this time. I preferred them in the functional languages where there seems to be less overhead. The parallel assignment helped a bit, but the lack of pattern matching was pretty annoying.
Ruby
def quicksort(l)
if l == [] then
[]
else
x, *xs = l
quicksort(xs.select { |i| i < x }) + [x] +
quicksort(xs.select { |i| i >= x })
end
end
It feels a little tidier than Python. The select was a little tidier than the equivalent list comprehension in Python, and seems to get right to the point a little better whereas with the list comprehension, the meaningful portion is in the if conditional on the far right.
I prefer the x, *xs = l notation, because it reminds me of pattern matching in the functional languages.
The Functional Languages
Haskell
module Quicksort where
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
++ [x] ++
quicksort [ i | i <- xs, i >= x ]
quicksort [] = []
Well, you’d expect a winner, and lo, it is a winner.
Erlang
-module(quicksort).
-export([quicksort/1]).
quicksort([H|T]) ->
quicksort([ X || X <- T, X < H ])
++ [H] ++
quicksort([ X || X <- T, X >= H ]);
quicksort([]) -> [].
Looks just like the Haskell to me, albeit with Prolog-esque syntax. But I like Prolog, so that’s worth a couple points. :) Tie with Haskell.
OCaml
let rec quicksort = function
| (x::xs) ->
(quicksort (List.filter (fun i -> i < x) xs))
@ [x] @
(quicksort (List.filter (fun i -> i >= x) xs))
| [] -> []
;;
Naturally, a bit of OCaml noise enters the picture. No nice list comprehension syntax so we get to use the old-fashioned filter function. However, it’s still quite small. I think it is very readable, I’m just wondering whether OCaml is going to wind up being the functional language I use the least.
Lisp
(defun quicksort (l)
(cond
((null l) nil)
(t (let ((x (car l))
(xs (cdr l)))
(concatenate 'list
(quicksort (remove-if #'(lambda (i) (< x i)) xs))
(cons x nil)
(quicksort (remove-if #'(lambda (i) (> x i)) xs)))))))
Wow. That’s… so ugly. By far the wordiest functional language. I could have done it without the let block though, in which case it looks like this:
(defun quicksort (l)
(cond
((null l) nil)
(t (concatenate 'list
(quicksort (remove-if #'(lambda (i) (< (car l) i)) (cdr l)))
(cons (car l) nil)
(quicksort (remove-if #'(lambda (i) (> (car l) i)) (cdr l)))))))
How unpleasant. I would have expected Lisp to do better. Oh well.
Tags erlang, haskell, io, languages, lisp, ocaml, programming, python, ruby | 12 comments
