Parsing S-expressions in C (2019)
benpaulhanna.com
benpaulhanna.com
Also, the author admits they didn't go to University for CS. You know what you do as part of your CS degree? You write a parser for S-expressions. This is a curious and driven programmer learning CS and sharing their discoveries. No need to berate them for not embedding a scheme....
Sometimes the languages are beautiful domain-specific things that work out of the box and expose a very complex configuration setup in portable format to any platform.
In the worst case they are the most horrible hodge-podge where one party was supposed to do one thing without told what the end result should be, then another party took the existing work and made it work.
I'm using language here in the most wide meaning, thus it includes ad-hoc configuration scripts, inhouse schema parsers, and in-code abstract syntax trees.
This is really beautiful and elegant. First, it does not make my eyes bleed. Second, it does not make me vomit. (I'm only half kidding. The things out in production... shudders).
Third, s-expressions are a succint and extendable way to store configurations. s-expressions are just as portable as XML. Sure, you don't get the xsd schema to verify existing data ... but then again, how many ad-hoc xml configuration files have a schema to go with them.
On HN, people don't need to justify their interests or their pleasures. It is the scolds who are at fault.
The geniuses of news dot ycombinator dot com: I am scratching my head. If you had simply put a kitchen in your bathroom you would have gotten a sink for free. As a bonus, you would now be able to cook your dinner there.
I'm not sure the first part you wrote about "reacting from cache" and "triggered" capture the entire phenomenon.
From personal experience, an empty comments section only leaves the article to comment on with no inspiration for specific content. A poorly written article will obviously provide plenty of fodder (and inspiration!) but hopefully won't end up on the front page. Meanwhile, a well written one (which hopefully does end up on the front page) often doesn't leave me feeling the need to add anything.
Worse, truly brilliant technical articles generally leave me completely out of my depth as far as commenting goes but are really what I come here to read. So the more desirable an article is (to me), the less likely I am to be capable of adding anything of merit.
Assuming the majority are in a similar situation (which could be totally wrong of course), it seems to me that the initial comments will necessarily select for people with less common view points. Of course that includes "triggered" as you say, but I think it's also all sorts of other things - a unique angle, factually incorrect, controversial but correct, a genuine misunderstanding, whatever. (The time constraint would certainly favor "triggered" reactions though.) That would then naturally lead to the rest of what you described.
(Ridiculous idea: Run GPT-3 against each new submission to generate a set of "seed" comments for people to disagree with, elaborate on, make fun of, etc. It would probably just end up derailing things, but who knows?)
Another positive is that it will make modding/shipping custom levels extremely easy. Just ask these that tried to mod (or config) return to castle wolfenstein or wolfenstein: enemy territory.
Also why I am exceedingly unlikely to ever post anything I've done or written as a "Show HN".
There's an old saying in game dev, which is often good advice for business as well: "Build the game, not a library"[1].
Or as applied to this case, that might mean trying to shoot straight for what you need in the game. Arguably, S-expressions might be the smallest possible thing you can do.
But another approach that is often used: Have your game process a binary file format, and build tools that read text files and compile them into the binary format. It's very common in games to have a tools pipeline that prepares assets for production use. Those tools can safely and easily take whatever dependencies help you get the job done, such as a JSON or YAML parser, or even real LISP if that feels right. This kind of approach also fulfills the laudible goal of keeping the dependencies down (for the production game).
The output of the tool chain could be binary files. Or, depending on your situation, the toolchain could produce code which is then run through your compiler, and then it's ready for direct execution, skipping a parsing step entirely.
[1] https://geometrian.com/programming/tutorials/write-games-not...
If we are parsing S-expressions... why not embed Scheme already? This way, not only you get an S-expression parser for 'free', you can easily manipulate S-expressions, you can add macros and so on. And you also get your scripting language out of this deal!
Something like Racket or Chicken (and possibly others) would work nicely. Chicken specifically has a very nice FFI - which you don't even have to use. As an experiment, I have asked Chicken's compiler to stop at the C code generation, added the generated code to my XCode project, and deployed the whole package to iPhone. Not even cross compilation shenanigans were required, since this was handled by XCode.
As a bonus*2, with a few lines of code, I opened a TCP listener, and fed straight to the REPL. Which meant that I could telnet and have a REPL, which could be used to replace functions on the fly and observe the results immediately, while the app was running.
They would have to rename the project at this point, though :)
Where they will differ the most is things like the packaging system (if they have packages, not all Scheme implementations will), as well as their main use-case.
If you are interested, just pick one and start to learn Scheme, using any implementation. Their differences will become apparent quickly.
emacs + evil (optional) + paredit + SLIME/SLY + SBCL + Quicklisp
That said, you might not always need such large runtimes and other lisps can fit the bill. For example, I usually program in CL (with C FFI) for most projects, but for embedding lisps into existing C programs, Guile can be a joy. Once I was programming servo motor controllers that offered C as one of the programming languages, and I embedded a single C file that gave me a tiny little scheme interpreter and I was then able to prototype motor control algorithms and setting in way less time than before. It's just a game changer for learning about a system when you can get a REPL on it and start rapidly digging and experimenting.
Really, if you're wanting to learn Scheme, just pick one and run with it. For learning purposes they're mostly equivalent if you stick to the more popular ones, but be aware of your learning material and the version of Scheme that they're using.
If you're familiar with other programming languages, it's somewhat like the relationship between different compilers. Though usually they adhere a bit more strictly to the same standards. Since Scheme is such a small language, there's more room for differences between implementations. This mostly doesn't affect you as a learner (most learning materials focus on the core parts of the language which all implementations should be consistent on).
Sometimes a purpose-built module that addresses the need and maintains simplicity is preferable over complexity in the interest of some future potential feature that nobody has asked for yet, and may never ask for.
I can guarantee you that a game will need a scripting language. Better get that done already.
That's if you prefer Scheme. You could use Lua too.
Myself and thousands of people before and after me have written games without a scripting language.
However, if every single time you want to change any piece of logic in your game, you have to do the edit/compile cycle, your development will be extremely slow. Especially if you compare with the ability to change code while the game is running.
Not having all the game logic in C or what have you makes the game easier to mod too.
An excellent example most with OpenGL experience may be familiar with is supporting hot reloading of GLSL for fast vfx development iteration. It's a compiled language, it gets compiled at runtime without significant delay, and most of us making games have created simple tools to support live editing of GLSL, maybe even supporting it in-game for dev builds.
The demoscene has even turned it into a form of competitive performance art:
https://github.com/Gargaj/Bonzomatic
Edit:
Forgot to mention Casey also goes through support of hot-reloading game logic using C in the Handmade Hero series on YouTube.
1. I'm working on a game in Unity right now that takes about 10 seconds to compile and reload the assemblies for the scripting language (only about 2 seconds of that is actual compilation, the rest is time that would be applicable to an interpreted scripting language).
2. I've built games in C where the entire project took 4 seconds to compile. Incremental compilation and modular architecture can get that down to near instantaneous for most changes.
>Especially if you compare with the ability to change code while the game is running.
Take a look at handmade hero for an example of an architecture that allows you to hot-reload C code while the game is running.
>Not having all the game logic in C or what have you makes the game easier to mod too.
That's completely architecturally dependent. You can make a game easy to mod for non programmers by storing data in a human readable/editable format. If you want to make it easy for players to write code there's a lot more work that needs to be done than just using a scripting language. For most games worrying about allowing modders to easily edit code is premature optimization.
I was involved in a game project that died extremely quickly a few years ago. The project lead made every decision re: architecture, tooling, etc. somehow involve worrying about modding. As a result, we ended up with nothing to show since everything got derailed by a bizarre obsession by one person with modding before we even had anything to mod. I believe that person doesn't take lead roles on projects any longer...
Is that really so certain?
Embedding a scripting language (e.g. Lua) seemed to be very common around 2010, but I get the feeling that it's much less common today.
Has the use of embedded scripting languages in games declined over the last 10 years? Any particular reasons?
"Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
> I'd rather be as library independent as possible, ideally with my SDL being my only cross-platform dependency to worry about.
I wrote a custom-made script parser... knowing full-well there were many libraries available. (For a goofy program I wrote available at cycell2d.com) Why? Because I enjoyed it!
This sort of nonsense is a good example of how some projects die due to absurd feature creep that no one at all can possibly justify. Who in their right mind would ever want to embed a full blown scripting language if your usecase is... Open a file and input data?
If you want to input data following a document format, you parse the document format. That's it.
Because embedding a mature, well written dependency that fully satisfies all your requirements might well be easier from a technical standpoint. It's certainly likely to reduce your comparative future maintenance burden given that the upstream community is healthy and functional.
What? Are there no mature well written parsers?
Don't be ridiculous.
Granted that in this particular case the point seems to have been the exercise of implementing the parser itself so embedding a dependency wasn't a valid approach to begin with.
I thought you had to restart a scheme’s REPL. Is that just a limitation of Racket?
S-expressions are a widely used standard data format and are not exclusive to Lisps. If this is just to read in configuration files, and the resulting data structures never change after they're read in, he can get away with using calloc instead of a garbage collector, and null-terminated char * C-style strings.
Lisps (including Scheme) have more heavyweight implementations of strings and symbols than Ben has here, with an extra level of indirection: a symbol's name slot points to a string struct, which contains a pointer into an array of chars and a length. He can get away with a null-terminated char * and a struct containing an enum to distinguish them. For Lisp programming, the extra complexity is essential but for reading a config file into a game written in C, it's accidental. I don't know what kind of game he's writing but presumably it isn't anything like Abuse or Crash Bandicoot.
In the first paragraph, he writes, "I turned away from XML because I'd rather be as library independent as possible." This implies that he might have considered embedding a Lisp but decided against it for the same reason.
Once you are no longer dealing with data, but with actual Scheme code that is no longer the case and it becomes virtually impossible to do anything with the code other than directly editing it in a text editor. It's extremely inflexible and every tiny API change will break everything with no automatic way to fix it.
I agree. I just thought the goal of the author was to produce a game, not to parse S expressions. It’s possible that parsing S expressions is the most direct route to get there. But there may be more direct and simple ways to get there.
(sprites (sprite :x 32
:y 104
(animation :texture "assets/idle.bmp"
:frame-length 2
:frame-width 24
:frame-height 24
:frame-span 5
:loop 0)))
1. Distinction between symbols and strings.
2. A well-specified number format (integers are integers). In JSON the precision of a number is unspecified, not something you want from an interchange format.
3. It has comments.
4. It's more concise.
5. Easier to parse.
In the .NET world we have an Expression library that behaves -almost- like S-Expressions. I'd say some things (i.e. currying) are simplified but for the most part it's the same concept. You can look at every part of an expression and do whatever you want based on it. We often see it used either for advanced reflection, or, for Dynamic Method Generation.
But, having written a few different parsers around it (and writing more LISP than I'd care to admit) I think anyone who is poo-pooing this has just never had the literal pleasure of writing a meaningful expression parser.
EDI transforms and XSLTs don't count, folks. S-Expressions are dead simple
https://common-lisp.net/project/ecl/
There are a bunch of applications which include some kind of Lisp implementation in C. From GNU Emacs, Audacity, AutoCAD (and its various clones), and various others.
http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
An interesting problem that came up was freeing deeply nested conses without overflowing the stack. I got a bug report about that from a user. They must have generated the structure in memory, because if they were reading it in, the reader would probably also have overflown the stack. In any case, the simple solution was to rotate the structure to be freed so that it can be freed without stack overflow or using an additional queue or stack:
https://github.com/schani/lispreader/blob/master/lispreader....
https://web.archive.org/web/20200821000640/https://benpaulha...
data Obj =
| Cons(Obj car * Obj cdr)
| Symbol(string)
| Nil
In c:
typedef enum { Cons, Sym, Nil } NodeType;
typedef struct Node Node;
struct Node {
NodeType type;
union {
struct { Node *car, *cdr; };
const char *symbol;
};
};Yep, definitely looks like a tree rather than a pair... not. What was the point in linking to this c2 topic even if it does not agree with you?
Node of a binary tree. Either you have problems keeping track of context or you're trolling. Either way I see no point in continuing this conversation. If you have any interest in learning what a cons cell is then there are plenty of resources to go around. If instead you prefer to push personal misconceptions formed in total ignorance then it's fine by me as well.
std::pair is the node of a binary tree, yeah man. Listen, it is okay to be wrong, just admit it and move on. Pressing on it makes you look like an idiot.
"oh look, a line segment!"
"It's not a line segment, it's a triangle/polygon node"
You can surely see how ridiculous this sounds, right?
This thing is never going to ship. Coming from someone who has written an IDE and wasted a bunch of time on the parser because it was the cool theoretical portion.
That’s fine, I assume learning rather than shipping is the goal here. A fine goal it is.
By the way, the problem is NOT that he wrote his own parser and other homemade tools. This is actually a great thing to do —third party tools usually end up being more trouble than they’re worth. The problem is that he’s ratholing on tiny details that don’t matter.
That's part of some peoples' journeys though: Learning how to work efficiently. Run into traps and find out again.
I applaud OP with full heart. Especially for stepping up and showing it off.
I don't think I could handle all the negativity you can read here. And so, I'll keep my private projects for myself until I'm done with them. Of course, when I'll be ready to release, nobody will care because I couldn't show it off because of all the negativity.
But on the other hand, I'm not doing this for any of you, only for myself, so I couldn't care less to be frank about what any of you think. I just hope the site being down doesn't mean OP took their server offline just because of all the flak he got for handrolling yet another parser.
In any case, you're not wrong, but I assume most people writing a game in C as opposed to leveraging a tool like Unity are more interested in diving in and learning something new rather than shiping something.
I will say most of the choices I'm making with respect to when to go "deep" with good design are very much calculated. I'm designing the architecture with a lot of thought, but when it comes to laying out UI elements, I will copy-paste and not refactor even if there's a good opportunity for it. It's just plumbing to me, so if it's ugly, it's not a big deal.
At some point somebody needs to implement the configuration interface for the human. Punting things by preferring boilerplate, machinable formats and libraries doesn't actually solve the problem.
Of course, there are some things that you are not going to do that a solid library gets you for free.
It's also an example of Greenspun's tenth rule [0]
"Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
There's a lot of flexibility that comes from being able to programmatically generate configs in your scripting language of choice and then ingest them in C++ with little effort. For example, being able to serialize a Python dict as json/ini/yaml/sqlite/whatever and then ingest it in C++ with some library.
It turns your complicated C++ program into a function with a dictionary argument.
I've worked on a few large programs now that have used custom config formats and it sucks. It's a waste of time trying to output correct syntax while fighting through idiosyncratic syntax choices and poorly explained parsing errors in the custom code.
It doesn't create value, it's just a thing you have to do to get to the automation you're trying to accomplish. Avoid it by not making the mistake in the first place.
I would agree. Even more so as parsers for S-expressions have existed... since 1960 or so?