« More On Allocation | Main | So Why Do I Like The Name 'Torpex' So Much? »

August 28, 2006

Comments

Bryan McNett

Scheme is only loosely functional, but "functional programming" may not be what you really want, anyway. You may simply want a higer-level language than C++.

How familiar are you with the most popular high-level languages, Python and Perl?

As languages they are roughly equivalent. Python has cleaner syntax, but Perl has better libraries and text wrangling.

I programmed the prototype for USM's stateless particles in Perl, with direct calls to OpenGL. Because Perl is a high-level language, opening up a window to let users rewrite "shaders" during runtime was "trivial."

Greggman

As you probably know the Crash Bandicoot series 1, 2 and 3 (not Crash Team Racing) and the Jak and Daxter series were written in a dialect of lisp called GOAL (Game Oriented Assembly Lisp)

http://www.gamasutra.com/features/20020710/white_02.htm

I only worked with it for 6 months so I'm not the guy to be asking really. Maybe I never grokked it perfectly but to be honest I never found it to be all that.

What I did I learn? I leared that C++ metaprogramming sucks ass. In Lisp you have the entire language to create metacode instead of the crap that is C++ template hack-arounds.

As an example one of the things I used it for was to create a particle system. The system needed input and for cache reasons that input needed to be in memory order. Basically you could set things like velocity, acceleration, color. So, you'd do something like this

(def-particle-gen myparticle (
(particle-color 1 0 0)
(particle-vel 0.0 1.0 0.0)
(particle-accel 0.0 -0.01 0.0)))

Even though there were 32 or so predefined fields like color, color-velocity, etc you only had to supply the the ones needed in any order. The def-particle-gen macro would take the ones you supplied and reorder them at compile time into the order most efficient for the particle code.

As you can see, something like that would be nearly impossible in C++.

But, arguably it was the wrong solution. The correct solution would have been some kind of tool an artist could use to tweak particles, not some fancy code level macro.

What else did I learn? I learned it's nearly impossible to write lisp without help from your editor because of all the parens. The guy who created it was an emacs fan and so he was used to emacs auto formatting all his lisp. At first I tried to hand format more like C/C++ but that failed. I wasn't about to switch to emacs so I re-created all the auto-formatting for Slickedit. That at least solved that problem.

Also learned that meta-programming in lisp can also be one of the biggest problems. The issue was that basically you are expanding the language through macros. That's fine if you are the only programmer but with 7 or 8 programmers each inventing new langauges for their own solutions it quickly turned into a big mess of trying to figure out what all these crazy macros did. Maybe some lisp gurus have guidelines for this but my impression at the time was that the complexity was a direct result of meta-programming being so easy.

Other takeways: Conditional compilation sucked. I'm used to doing #if DEBUG or #if PROGRAMMER_GREGG. In C/C++ because #if is a pre-processor directive it doesn't matter what's inside the #if/#endif. Lisp doesn't have a pre-processor. The lisp guru suggested creating a macro to conditionally compile stuff out. The problem is that requires the code inside the macro to actually compile even when it's going to be compiled out which never fit real use cases.

To give an example try to convert this C++ to lisp including the conditional compilation parts

void func(int x)
{
#if DEBUG
if (x < 10) // check some limit
{
#endif
printf("%d\n", x);
#if DEBUG
}
#endif
}

I'm sure some lisp guru might have an answer. All I could figure out was to create yet more and more custom macros. Of course that example is not a good example because you can figure out a better way to code it in the first place but rather then pick a apart the specifics look at it's pattern. The stuff inside the first #if/#endif block can't be translated to balanced parens for lisp.

In my experience, all the benefits we got from GOAL had nothing to do with it being Lisp based and everything to do with it being our own custom compiler. For example, during development we could compile individual functions on the fly while the game was running. But, that is an issue of environment, not language. Virtools for example can do this. All of the shadered editors compile shaders on the fly and shading is not in lisp. In other words our own C++ compiler could have achieved the same thing.

Another was we could write our own extentions so adding true 128bit support for SIMD or allowing us to specify the byte offets of fields or integrating a better inline assembler with more knowledge of the language around it. But again, all those are because we had our own compiler. Not because it was lisp.

Charlie

Hey, I never said you should write *games* in a functional language! I said it's worth practicing with them, because then your code tends to have fewer heap allocations and fewer side-effects.

Games are inherently state-heavy, and their drawing is inherently side-effect-heavy; both of those things tend to be a pain in functional languages (unless of course you're in a Lisp dialect and you built yourself a huge pile of macros on top of the base language. Which is the whole reason to use Lisp - you can twist it into any other language you can imagine.)

Functional languages shine when you have an application that can be expressed as a function; the classical examples are raytracers (function that takes a scene description and returns an image) and compilers (takes a source file, returns an object file.)

That last is why language dorks love functional languages. It really is an order of magnitude easier to write a compiler in Ocaml than in C++.

Actually, it's also struck me that functional languages would be great for a game build pipeline, if they didn't depend heavily on libraries written in C++.

If I was going to pick a language to develop a game in, though, and it compiled to native machine code instead of .NET bytecode, my choice would probably be Nemerle. ( http://nemerle.org/Main_Page ) I've only started getting to know it, but "C# with type inferencing, variants and pattern matching, and Lisp-inspired metaprogamming" sounds like heaven to me.

Oh, and it's impossible for a human being to write Scheme without a paren-matching editor. That's why all Lispy code has long strings of close-parens everywhere; you just bang the close-paren key until the paren you want to close lights up.

Ignorant Bystander

You can cut a lot of those lambdas out by defining a function like this:

(define (myfunc arg1 arg2) ...)

instead of this:

(define myfunc (lamdba (arg1 arg2)) ...)

Sebastian Wagner

I'm not very good with Scheme and LISP myself, but a few days cannot be enough to get comfortable in any language much less a different paradigm.

How about Lua? Interfacing it with C++ works well and you get a nice mixture of declarative and functional programming support. Best is: everything is kept so simple it's probably the only language and implementation this powerful one can really understand top to bottom.

Jamie Fristrom

Ah...good discourse.

Bryan,

I can get around in Perl but I remember you were horrified by my code when I tried to do something with two dimensional arrays.

Why do you consider Scheme only "loosely functional"?

Gregg,

Sure, but I bet writing your own C++ compiler would take a lot longer than writing your own Lisp compiler.

I have another theory about why Lisp was beneficial at Naughty Dog, which is: it raises the bar on programmer hires. You guys were best-of-the-best - you had to be.

Charlie,

Good to know I'm not somehow deficient in my paren-matching abilities. Yeah, I probably should have written a sample program more suited to the terrain.

Ignorant Bystander,

I like the lambdas. The docs I read were mixed about whether they were good style or not. I felt like they made my thinking more clear - "I'm declaring a nameless function and binding it to a variable."

Although I also thought that whoever decided to use "lambda" for the keyword instead of something like "function" was engaging in the ultimate pretentious academic masturbation.

Sebastian,

I'll give Lua a look after Python. Maybe every weekend I'll write Spacewar in a new language.

On the productivity front, I could easily see myself spending so much time evaluating and experimenting with new tech that I'd never actually do anything.

Parveen Kaler

Greggman said:
"Other takeways: Conditional compilation sucked. I'm used to doing #if DEBUG or #if PROGRAMMER_GREGG. In C/C++ because #if is a pre-processor directive it doesn't matter what's inside the #if/#endif. Lisp doesn't have a pre-processor. The lisp guru suggested creating a macro to conditionally compile stuff out. The problem is that requires the code inside the macro to actually compile even when it's going to be compiled out which never fit real use cases."

I don't get it. Lisp expressions are evaluated lazily. You're debug code should never be evaluated if you have a higher-level expression that toggles between release and debug mode.

And in C++, you're example is eventually going to bite you in the ass. That's just bad form. If you can't boil you're debug code into one nice, clean macro that is conditionally compiled out, it just becomes a maintenance nightmare.

Bryan McNett

'Why do you consider Scheme only "loosely functional"?'

Very functional languages forbid side effects or constrain their use. This is because when there are truly zero side effects, a program can be reorganized and analyzed very aggressively for cheap.

The LISP family of languages have no beef with side effects, however. You can program in a functional style, but you don't get the benefits of zero side effects.

Except for macros, Perl and Python do everything Lisp and Scheme do nowadays, and with syntax that is more friendly to C++ programmers.

andy

Are you sure that "every language except C++ lets you define your function objects on the fly"?

Boost provides the lambda library, and the functor library (both described in overarching detail in "Beyond the C++ Standard Library: An Introduction to Boost" ISBN 0321133544) which allows you to write your code in-line without interrupting your flow.

Bryan McNett

Boost does this, though it is about as rough on compilers now as STL was about ten years ago.

Even nicer than functions inline are closures. Lisp and Perl do this - I don't know about Python etc.

In case you don't know, a closure is an inline function that "captures" local variables of its enclosing scope:

sub foo
{
my( $x ) = @_;
return sub { ++$x; };
}

my $x = 1;
my $code = foo( $x );
print $x;
&$code();
print $x;

OUTPUT:

1
2

Bryan McNett

That wasn't quite right, let me try again.

sub foo
{
my( $reference_to_x ) = @_;
return sub { ++$$reference_to_x; };
}

my $x = 1;
my $code = foo( \$x );
print $x;
&$code();
print $x;

OUTPUT:

1
2

guest

That scheme code you've written is very imperative in style.

I highly recommend that you learn haskell very thoroughly. Once you "get" it, I believe that you will have that same feeling you had when you moved from asm to c.

Tim Sweeney gave a talk recently "The Next Mainstream Programming Language: A Game Developer's Perspective", where he mentions a lot of ideas from haskell.

Paul Sinnett

I've spent some time looking into functional languages too. My take is that anonymous functions and closures are occasionally useful, but not enough to make a difference. And I think it's a bad idea to fixate on syntactic sugar because there are wider, more general benefits.

You say that writing functions and function objects (the usual C++ solution to these problems) breaks your flow. I agree that it can, but it doesn't have to. If you change your composition style to programming by intention, flow is not interrupted. On the other hand, writing functions inline breaks two other principles: abstraction; and cohesion. I'm not suggesting that breaking these is always bad, but I think always breaking them is. Alternatively, always weighing up the cost / benefit as these instances arise would break my flow just as effectively as switching to write a separate function.

My attraction to pure functional style programming comes from the removal of side-effects and explicit sequencing of instructions. I recently analysed bugs I wrote that got through compilation and code review. Almost all were hidden side effects of functions, or operations unintentionally carried out in the wrong order. In pure functional languages, functions aren't allowed side-effects, and instructions are executed in arbitrary order or even in parallel. This prevents me from making one of my most common mistakes. And it forces me to specify temporal cohesion rather than implying it through an instruction's relative position on the page. I suspect (I haven't tested this theory yet) I will find that type of bug harder to write by accident.

But even without those benefits, I think that pure functional programming style will play a greater part in the future of games development. Both consoles and PCs have moved to multi-core processors. This is an environment where pure functional languages generally shine.

Jamie

I learn so much from my blog - the downside is I parade my ignorance in front of the world. "Better to be ridiculed than ignored" I suppose.

Jamie Fristrom

And seems like Python does indeed have closures.

# closure test

def outerfunc(localvariable):
def innerfunc(x)
return x+localvariable
return innerfunc

def main():
addtwo = outerfunc(2)
addthree = outerfunc(3)

print "addtwo(2):" + str(addtwo(2))
print "addtwo(0):" + str(addtwo(0))
print "addthree(2):" + str(addthree(2))
print "addthree(0):" + str(addthree(0))

addtwo(2):4
addtwo(0):2
addthree(2):5
addthree(0):3

Jamie Fristrom

Rats, it removed my tabs and now the syntax is wrong. Not crazy about that aspect of python.

Paul Sinnett

Jamie: 'I learn so much from my blog - the downside is I parade my ignorance in front of the world. "Better to be ridiculed than ignored" I suppose.'

I don't think anybody wants to ridicule (I hope so anyway.) I fear the day I don't learn something new - that's why I come here.

PS: perhaps there's an option to turn on formatting for comments? That would cool for swapping code ideas.

PPS: I disagree with Anonymous about the black background. I prefer it. I'm looking for a good light on dark style for my own blog.

Greggman

Parveen:
To your first point. Lisp requires the parens be balanced even if the code inside the parens will eventually be compiled out. That limitation is not true with the preprocessor in C/C++
To your second point that my style sucks. That might be true. I don't have a better example to show and even if I did that doesn't mean it couldn't be reworked. But, so far, something about my coding style sometimes lends itself to non balanced conditional compilation and that was something I couldn't do in lisp and found frustrating.

Bryan McNett

in response to Paul Sinnett above:

I'm also a big fan of functional programming for its lack of side effects, but I do most of my functional programming on the GPU.

Vertex and pixel shaders forbid side effects, and are therefore easily parallelized. That's why they've been beating Moore's law lately...

Graphics systems written to a "stateless" (functional) model also tend to be simpler, run faster, and scale better than "stateful" counterparts.

If there's a problem I've had with stateless graphics, it's that solutions sometimes feel "sideways." Beyond a certain trivial level of complexity, tasks that in a stateful model require high school algebra, in a stateless model begin to require college-level calculus.

One advantage to a stateless model is that it forces one to consider the gestalt of a problem - to see it as a "wave" - rather than as made of "particles."

snk_kid

Jamie i'm going to second guest's post, the best thing to do is to learn how to program in a purely functional language like haskell so you learn and eventually get it properly.

Also you'll learn one method of how to (elegantly) emulate stateful computations and/or imperative features in purely functional languages using monads and monadic programming.

Other reasons to learn haskell is:

1. It is a statically typed and completely type infered langauge.

2. It is a non-strict language be default, lazy programs are beautiful, infinite data structures and programming with them make code alot more elegant and natural. This will open your mind to so much.

3. Aswell as support for parametric polymorphism haskell also supports ad-hoc polymorphism in a less ad-hoc manner.

4. Haskell's operator overloading model is superior to virtually all other languages.

5. Haskell's syntax is aesthetically pleasing, it's a sexy language.

snk_kid

Jamie: Oh yeah i forget to mention, if you are interested and looking for a book i recommend either:

Introduction to Functional Programming using Haskell by Richard Bird

or

Haskell The Craft of Functional Programming
Second Edition by Simon Thompson

After that you might want to look into OCaml for a serious alternative to C++.

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

The Games

  • Energy Hook
    3D grappling-and-swinging-and-running-on-walls-and-doing-tricks ... with a jetpack ... for style!

Jamie's Bragging Rights

  • Spider-Man 2
    The best superhero games of all time Game Informer
    Top five games of all time Yahtzee Croshaw
    Top five superhero games of all time MSNBC
    Top 100 PS2 games of all time Official Playstation 2 Magazine
    1001 Games You Must Play Before You Die Nomination for Excellence in Gameplay Engineering Academy of Interactive Arts & Sciences
  • Schizoid
    Penny Arcade PAX 10 Award
    Nominated for XBLA Best Original Game
    Nominated for XBLA Best Co-Op Game