11 ms·

Parsing S-expressions in C (2019)

147 points by azhenley 6y ago

tobyhinloopen 6y ago
And 0 value was added to the actual game. This is exactly how my side projects are never finished
- Bishop_ 6y ago
  Same here, but maybe the goal of his side project is to learn and not ship a product. 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.
  - ThePadawan 6y ago
    They're very different attitudes indeed. E.g. compare OP to the level storage of VVVVVV: https://github.com/TerryCavanagh/VVVVVV/blob/cf53de9ed5cd82a5836cd3592d3c7f33ec139964/desktop_version/src/Spacestation2.cpp#L28 https://github.com/TerryCavanagh/VVVVVV/blob/cf53de9ed5cd82a...
    - emmanueloga_ 6y ago
      Although to be fair I'm sure the author wrote a program that generated that array :-)
      - Ma8ee 6y ago
        I certainly hope so.
    - allenu 6y ago
      I love the reference to this because I'm working on a side project and treating it as "something I definitely want to ship" and have found that I have higher tolerance for code that I just copy/paste and slapdash together. I've worked on lots of side projects in the past where I was more deliberate about every line of code and learned that shipping is more important to me now than learning something new. 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.
- emmanueloga_ 6y ago
  Writing a custom configuration format seems like some prime quality yak shaving :-) Probably flatbuffers would be a good choice for the author needs.
  - makapuf 6y ago
    C literals const struct files are actually a nice format with no runtime. If you compile in .3s a big C file your compile time wont matter.
  - wahern 6y ago
    One of the reasons service configurations on OpenBSD (e.g. pf.conf, ipsec.conf, etc) are so convenient and expressive is because they don't shy away from defining and implementing custom configuration syntax using yacc. 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.
- jstimpfle 6y ago
  With some practice, things like this take between a couple of hours to a couple of days of investment, total. I would say it is a fair price to pay, whenin exchange you get to explore the design space, get to practice some important skills, and get a lot of control over how you want to do things, and get rid of a nasty dependency that might bite you later. Of course, there are some things that you are not going to do that a solid library gets you for free.
- outworlder 6y ago
  0 value may have been added to the game. A lot of value was added to the author.
bigdict 6y ago
Tree is a more natural data structure for s-expressions.
- moonchild 6y ago
  Usually it's called a cons cell in this context, not a tree. The base lisp structure looks something like this: data Obj = | Cons(Obj car * Obj cdr) | Symbol(string) | Nil (Nil is important, cannot be elided.) In c: typedef enum { Cons, Sym, Nil } NodeType; typedef struct Node Node; struct Node { NodeType type; union { struct { Node *car, *cdr; }; const char *symbol; }; };
  - rumanator 6y ago
    You're being needlessly pedantic. A cons cell is basically a node of a binary tree. It has fancy names for the left and right child node because of its relation with lisp, but it's nonetheless a tree node.
    - dependenttypes 6y ago
      It is a list node. It's just that you can implement binary trees trivially out of lists.
      - rumanator 6y ago
        You got it entirely backwards: a cons cell is a tree node which, as a corner case, can represent branches of a binary tree where the left child node (car) points to a child node value and the right child node (cdr) points to another branch (cons cell or nill).
        dependenttypes 6y ago
        I indeed got it incorrect but a cons cell is still not a tree node (it can be one though). It is rather just a pair, like (x, y) in haskell or std::pair in C++.
deleted 6y ago
[deleted]
outworlder 6y ago
I am scratching my head. 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 :)
- codemac 6y ago
  guile for embedding works really nicely.
  - outworlder 6y ago
    Sorry, I keep forgetting about Guile. That thing needs more love indeed.
    - grugagag 6y ago
      As a newbie im getting a bit confused. What is the difference between guile and chicken scheme? There's also chez. Im even more confused
      - deleted 6y ago
        [deleted]
      - outworlder 6y ago
        These are different implementations. The language spec they follow is slightly different so they are not completely compatible (although I've been able to use some OpenGL-ES Racket code with no modifications in Chicken by using macros). 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.
krapp 6y ago
No mention of the game anywhere else on the blog, and this post is from last year. I wonder what happened?
unoti 6y ago
This is fun and interesting, and I'm not sure what to think of it. 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-engines/ https://geometrian.com/programming/tutorials/write-games-not...
- f00zz 6y ago
  For what it's worth, I once wrote a game that had a configuration file parser written in bison/flex (I actually finished that game).
lispm 6y ago
While you follow Greenspun's tenth rule of programming (Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp) you could embed a Lisp system, like ECL -> Embeddable Common Lisp https://common-lisp.net/project/ecl/ 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.
CoolGuySteve 6y ago
It's fine for a personal project, but if you're thinking of writing a custom parser and grammar for configuration for a commercial project: Don't. 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.
- setzer22 6y ago
  To be fair, S-expressions are not a made up format and in fact predate most other formats you mention.
  - CoolGuySteve 6y ago
    You're missing the point, S-expression parsers aren't "batteries included" in most scripting languages. The age of the format is irrelevant.
- outworlder 6y ago
  > It's fine for a personal project, but if you're thinking of writing a custom parser and grammar for configuration for a commercial project: Don't. I would agree. Even more so as parsers for S-expressions have existed... since 1960 or so?
ravenide 6y ago
“Even though I'm never expecting my game to read an empty string in from an s-expression, I didn't want that to be a limitation of the parser.” 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.
- mlatu 6y ago
  > 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.
rsecora 6y ago
Nice, and descriptive. I love the explanation. 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." [0] https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule
- platinumrad 6y ago
  A config file parser is not anywhere close to half of Common Lisp.
codemonkey-zeta 6y ago
Whoa this thread is way more harsh than I would have expected. Coding isn't always about maximizing development speed or avoiding arbitrary dogmas. Some things are just fun to code, and parsing S-expressions is one of those things. I'm glad the author shared their experience and actually plans to use it in a game. Better than writing the parser for fun and then throwing it away. 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....
- dbtc 6y ago
  I think it is responding to a project as if it were a product.
  - platinumrad 6y ago
    Even if it were a product there is simply no justification for embedded a second language when all you want to do is read some config files.
    - wizzwizz4 6y ago
      Sure there is! Shaves a few hours off the initial development time, adds a few milliseconds to execution time (this is scheme we're talking about), adds a few days to later development.
    - deleted 6y ago
      [deleted]
    - fsloth 6y ago
      I don't known what products you have maintained but I've seen that large software products have a tendency to function as embedded-language magnets. 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.
neilv 6y ago
For people not already very familiar with S-expressions, a slightly different way to formulate and format the example from the post is: (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))) A benefit of formatting this way comes when it's not only a nested chain, like in this contrived example, but you have more varied tree structure, like in real-world code and data, and want to be able to grasp the nesting structure visually. And without using too many vertical lines of screen space.
- benrbray 6y ago
  what is the advantage over something more standard like JSON?
  - thelazydogsback 6y ago
    For machine reading/writing, not much. For human reading/writing, sexprs (or Prolog terms) are much nicer as you don't need to quote everything, for example. However, (traditional) sexprs don't have defined literal map or vector/array syntax that's different from a list - for that you need an extension such as EDN format defined by Closure, but usable elsewhere.
  - lokedhs 6y ago
    I'd say there are a few major benefits: 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.
lokl 6y ago
Why not make parsing S-expressions the game? HN crowd would love to play.
mark-probst 6y ago
I wrote a Lisp reader for C a long time ago: https://github.com/schani/lispreader https://github.com/schani/lispreader 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.c#L566 https://github.com/schani/lispreader/blob/master/lispreader....
platinumrad 6y ago
Someone: Here is how I put a sink in my bathroom. 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.
- deleted 6y ago
  [deleted]
- mhh__ 6y ago
  Not mentioned: Subtle (possibly unintentional) humblebragging about how you either spend thousands of dollars a year on Amazon kitchens or that you need an Apple Kitchen because your time is so valuable (Both common motifs I see in discussions of said companies)
- hinkley 6y ago
  If you put the garbage disposal into the tub, you can prepare dinner while showering!
  - bzb4 6y ago
    Hello, Kramer!
- dang 6y ago
  This is the contrarian dynamic at work. I wrote about this yesterday: https://news.ycombinator.com/item?id=24215601 https://news.ycombinator.com/item?id=24215601.
  - Reelin 6y ago
    Contrarian dynamic in action: 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?)
csharptwdec19 6y ago
Expressions are fun. 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
deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
vinkelhake 6y ago
That calloc usage and string copying looks hella broken in the first example.
kasumispencer 6y ago
Too bad this guy wrote it in C. Imagine the overflowing support from this little orange site if he wrote it in Go/Rust.
ColinWright 6y ago
The site seems to be down ... here is the referenced page courtesy of the WayBack machine: https://web.archive.org/web/20200821000640/https://benpaulhanna.com/writing-a-game-in-c-parsing-s-expressions.html https://web.archive.org/web/20200821000640/https://benpaulha...
aidenn0 6y ago
Not a criticism of TFA, but for those who want to parse s-expressions, the algorithm used for common lisp is easy to implement, extensible, and works while only inspecting a single character at at time (no need to mess with formatted input tools like scanf): http://www.lispworks.com/documentation/HyperSpec/Body/02_b.htm http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
ejanus 6y ago
The site is not opening for me. I have tried several times. Is anyone experiencing such?

147 points by azhenley 6y ago

tobyhinloopen 6y ago

And 0 value was added to the actual game. This is exactly how my side projects are never finished

Bishop_ 6y ago
Same here, but maybe the goal of his side project is to learn and not ship a product. 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.
- ThePadawan 6y ago
  They're very different attitudes indeed. E.g. compare OP to the level storage of VVVVVV: https://github.com/TerryCavanagh/VVVVVV/blob/cf53de9ed5cd82a5836cd3592d3c7f33ec139964/desktop_version/src/Spacestation2.cpp#L28 https://github.com/TerryCavanagh/VVVVVV/blob/cf53de9ed5cd82a...
  - emmanueloga_ 6y ago
    Although to be fair I'm sure the author wrote a program that generated that array :-)
    - Ma8ee 6y ago
      I certainly hope so.
  - allenu 6y ago
    I love the reference to this because I'm working on a side project and treating it as "something I definitely want to ship" and have found that I have higher tolerance for code that I just copy/paste and slapdash together. I've worked on lots of side projects in the past where I was more deliberate about every line of code and learned that shipping is more important to me now than learning something new. 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.
emmanueloga_ 6y ago
Writing a custom configuration format seems like some prime quality yak shaving :-) Probably flatbuffers would be a good choice for the author needs.
- makapuf 6y ago
  C literals const struct files are actually a nice format with no runtime. If you compile in .3s a big C file your compile time wont matter.
- wahern 6y ago
  One of the reasons service configurations on OpenBSD (e.g. pf.conf, ipsec.conf, etc) are so convenient and expressive is because they don't shy away from defining and implementing custom configuration syntax using yacc. 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.
jstimpfle 6y ago
With some practice, things like this take between a couple of hours to a couple of days of investment, total. I would say it is a fair price to pay, whenin exchange you get to explore the design space, get to practice some important skills, and get a lot of control over how you want to do things, and get rid of a nasty dependency that might bite you later. Of course, there are some things that you are not going to do that a solid library gets you for free.
outworlder 6y ago
0 value may have been added to the game. A lot of value was added to the author.

bigdict 6y ago

Tree is a more natural data structure for s-expressions.

moonchild 6y ago
Usually it's called a cons cell in this context, not a tree. The base lisp structure looks something like this: data Obj = | Cons(Obj car * Obj cdr) | Symbol(string) | Nil (Nil is important, cannot be elided.) In c: typedef enum { Cons, Sym, Nil } NodeType; typedef struct Node Node; struct Node { NodeType type; union { struct { Node *car, *cdr; }; const char *symbol; }; };
- rumanator 6y ago
  You're being needlessly pedantic. A cons cell is basically a node of a binary tree. It has fancy names for the left and right child node because of its relation with lisp, but it's nonetheless a tree node.
  - dependenttypes 6y ago
    It is a list node. It's just that you can implement binary trees trivially out of lists.
    - rumanator 6y ago
      You got it entirely backwards: a cons cell is a tree node which, as a corner case, can represent branches of a binary tree where the left child node (car) points to a child node value and the right child node (cdr) points to another branch (cons cell or nill).
      - dependenttypes 6y ago
        I indeed got it incorrect but a cons cell is still not a tree node (it can be one though). It is rather just a pair, like (x, y) in haskell or std::pair in C++.

deleted 6y ago

[deleted]

outworlder 6y ago

I am scratching my head. 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 :)

codemac 6y ago
guile for embedding works really nicely.
- outworlder 6y ago
  Sorry, I keep forgetting about Guile. That thing needs more love indeed.
  - grugagag 6y ago
    As a newbie im getting a bit confused. What is the difference between guile and chicken scheme? There's also chez. Im even more confused
    - deleted 6y ago
      [deleted]
    - outworlder 6y ago
      These are different implementations. The language spec they follow is slightly different so they are not completely compatible (although I've been able to use some OpenGL-ES Racket code with no modifications in Chicken by using macros). 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.

krapp 6y ago

No mention of the game anywhere else on the blog, and this post is from last year. I wonder what happened?

unoti 6y ago

This is fun and interesting, and I'm not sure what to think of it. 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-engines/ https://geometrian.com/programming/tutorials/write-games-not...

f00zz 6y ago
For what it's worth, I once wrote a game that had a configuration file parser written in bison/flex (I actually finished that game).

lispm 6y ago

While you follow Greenspun's tenth rule of programming (Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp) you could embed a Lisp system, like ECL -> Embeddable Common Lisp https://common-lisp.net/project/ecl/ 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.

CoolGuySteve 6y ago

It's fine for a personal project, but if you're thinking of writing a custom parser and grammar for configuration for a commercial project: Don't. 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.

setzer22 6y ago
To be fair, S-expressions are not a made up format and in fact predate most other formats you mention.
- CoolGuySteve 6y ago
  You're missing the point, S-expression parsers aren't "batteries included" in most scripting languages. The age of the format is irrelevant.
outworlder 6y ago
> It's fine for a personal project, but if you're thinking of writing a custom parser and grammar for configuration for a commercial project: Don't. I would agree. Even more so as parsers for S-expressions have existed... since 1960 or so?

ravenide 6y ago

“Even though I'm never expecting my game to read an empty string in from an s-expression, I didn't want that to be a limitation of the parser.” 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.

mlatu 6y ago
> 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.

rsecora 6y ago

Nice, and descriptive. I love the explanation. 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." [0] https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

platinumrad 6y ago
A config file parser is not anywhere close to half of Common Lisp.

codemonkey-zeta 6y ago

Whoa this thread is way more harsh than I would have expected. Coding isn't always about maximizing development speed or avoiding arbitrary dogmas. Some things are just fun to code, and parsing S-expressions is one of those things. I'm glad the author shared their experience and actually plans to use it in a game. Better than writing the parser for fun and then throwing it away. 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....

dbtc 6y ago
I think it is responding to a project as if it were a product.
- platinumrad 6y ago
  Even if it were a product there is simply no justification for embedded a second language when all you want to do is read some config files.
  - wizzwizz4 6y ago
    Sure there is! Shaves a few hours off the initial development time, adds a few milliseconds to execution time (this is scheme we're talking about), adds a few days to later development.
  - deleted 6y ago
    [deleted]
  - fsloth 6y ago
    I don't known what products you have maintained but I've seen that large software products have a tendency to function as embedded-language magnets. 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.

neilv 6y ago

For people not already very familiar with S-expressions, a slightly different way to formulate and format the example from the post is: (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))) A benefit of formatting this way comes when it's not only a nested chain, like in this contrived example, but you have more varied tree structure, like in real-world code and data, and want to be able to grasp the nesting structure visually. And without using too many vertical lines of screen space.

benrbray 6y ago
what is the advantage over something more standard like JSON?
- thelazydogsback 6y ago
  For machine reading/writing, not much. For human reading/writing, sexprs (or Prolog terms) are much nicer as you don't need to quote everything, for example. However, (traditional) sexprs don't have defined literal map or vector/array syntax that's different from a list - for that you need an extension such as EDN format defined by Closure, but usable elsewhere.
- lokedhs 6y ago
  I'd say there are a few major benefits: 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.

lokl 6y ago

Why not make parsing S-expressions the game? HN crowd would love to play.

mark-probst 6y ago

I wrote a Lisp reader for C a long time ago: https://github.com/schani/lispreader https://github.com/schani/lispreader 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.c#L566 https://github.com/schani/lispreader/blob/master/lispreader....

platinumrad 6y ago

Someone: Here is how I put a sink in my bathroom. 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.

deleted 6y ago
[deleted]
mhh__ 6y ago
Not mentioned: Subtle (possibly unintentional) humblebragging about how you either spend thousands of dollars a year on Amazon kitchens or that you need an Apple Kitchen because your time is so valuable (Both common motifs I see in discussions of said companies)
hinkley 6y ago
If you put the garbage disposal into the tub, you can prepare dinner while showering!
- bzb4 6y ago
  Hello, Kramer!
dang 6y ago
This is the contrarian dynamic at work. I wrote about this yesterday: https://news.ycombinator.com/item?id=24215601 https://news.ycombinator.com/item?id=24215601.
- Reelin 6y ago
  Contrarian dynamic in action: 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?)

csharptwdec19 6y ago

Expressions are fun. 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

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

vinkelhake 6y ago

That calloc usage and string copying looks hella broken in the first example.

kasumispencer 6y ago

Too bad this guy wrote it in C. Imagine the overflowing support from this little orange site if he wrote it in Go/Rust.

ColinWright 6y ago

The site seems to be down ... here is the referenced page courtesy of the WayBack machine: https://web.archive.org/web/20200821000640/https://benpaulhanna.com/writing-a-game-in-c-parsing-s-expressions.html https://web.archive.org/web/20200821000640/https://benpaulha...

aidenn0 6y ago

Not a criticism of TFA, but for those who want to parse s-expressions, the algorithm used for common lisp is easy to implement, extensible, and works while only inspecting a single character at at time (no need to mess with formatted input tools like scanf): http://www.lispworks.com/documentation/HyperSpec/Body/02_b.htm http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...

ejanus 6y ago

The site is not opening for me. I have tried several times. Is anyone experiencing such?