Hacker News new | past | comments | ask | show | jobs | submit login
Cakelisp: A Programming Language for Games (macoy.me)
178 points by makuto 11 months ago | hide | past | favorite | 64 comments



See also on /r/gamedev [0].

After years of dealing with points of frustration in C++ land, I've created my own programming language. It emphasizes compile-time code generation, seamless C/C++ interoperability, and easier 3rd-party dependency integration. It's like "C in S-expressions", but offers much more than just that.

I had a hard time trimming this article down because of how excited I am about the language. Feel free to skim and read more in the sections that pique your interest.

I don't expect everyone to love it and adopt it. I do hope that some of the ideas are interesting to fellow programmers. I found it eye-opening to realize how much better my development environment could become once I opened this door.

[0] https://www.reddit.com/r/gamedev/comments/kh1p0a/cakelisp_a_...


Nice! I've always been a proponent of thinking about C++ as "C with templates" rather than "C with classes," and once you realize that templates are just AST expanders, it becomes apparent that C++ is just a bad lisp :)

I made the same thing a while back, and one of the neat simple things you can do is implement function-overloading a la C++. All you need is to define a way to serialize types to strings that are valid identifiers; then you (1) append the string-forms of the types of each function parameter to the name of the function at the definition site, along with a normal function that will do the dispatching in the second part, and (2) do the same thing for the type of the arguments at each call site. Et voila! Function overloading! Not quite as powerful as C++, which takes conversions and stuff into account, but it's an interesting experiment nonetheless. You can see how I did it here: https://github.com/zc1036/ivy/blob/master/src/lib/std/overlo... (DEFUN2 is the version of DEFUN in my language that supports overloading.)


I agree. Templates make some tasks easy (type specialization and generic containers) but become tangled messes with other tasks (function bindings, serialization).

I used something similar to your technique for compile-time variable destruction. The compiler doesn't know the type, so a macro generates a callback which deletes a casted version. These callbacks are named with the type so they can be lazily added and reused.


Very cool project, great to see more s-expression based languages. I maintain a list of lisp-flavored languages [0], so I will add Cakelisp there.

How did you implement the macro expansion? Are you translating the macros to C/C++, then compile it with C/C++ compiler and execute the temporary binary or do you have an interpreter for that?

I work on a somewhat similar project called Liz, which is basically a lisp-flavored dialect of Zig [1]. I did not implement user-defined macros yet, planning to learn more about comptime and its limitations first. But the compiler itself uses macro-expansion to implement many features.

[0] https://github.com/dundalek/awesome-lisp-languages

[1] https://github.com/dundalek/liz


Thanks for maintaining this list, it looks super interesting and it was exactly what I was looking for!


Yes, they are compiled just like the final exe, only they become dynamic libraries that I load with libdl. On subsequent builds, they are loaded again, unless the macro changed.


> Lisp has extremely powerful code generation, but makes serious performance compromises

This is a serious exaggeration.

Common Lisp has extremely good compilers that can meet C performance.

There are plenty of Scheme implementations (I use Chez) with very good performance characteristics too.


I do wish the C compiler was as fast as e.g. SBCL's compiler in terms of compile time, because multiple rounds of dependent macro compilation eats up a lot of time.

I think Lisps tend to optimize for throughput, but games have very strict latency requirements. Garbage collection pauses could cause frame pacing issues (not that C solves that completely, but it is at least not a built in disadvantage of idiomatic use of the language)


Newer concurrent java GCs (shenandoah, zgc) provide consistent ≤1ms pause times independent of heap size. That's a reasonable latency for most soft real-time tasks.


Writing a low latency garbage collector (with decent throughput) is a non-trivial engineering problem and requires both high calibre engineers with specialized skills and a lot of funding. I fear the time lisp community has had either are long gone.

How much did the development of Azul's C4 or Oracle's Shenandoah cost in terms of money, talent and time and how much has this work lowered the barrier for less well resourced languages? I don't get the impression that the answer to this question is: "enough that we will soon see low-latency, high-throughput garbage collectors becoming the norm".


Some older VMs like Erlang's also do very well in avoiding GC pauses.

In Erlang's, the key is that garbage collection is per process. (Note that Erlang processes are analogous to Golang green threads, not OS prcessses.)


And in the BEAM the garbage collector is only invoked when the heap and stack meet which means for most short-lived processes it never runs:

https://erlang.org/doc/apps/erts/GarbageCollection.html#over...

(btw, I'm enjoying the Reactor podcast, keep it up)


> (btw, I'm enjoying the Reactor podcast, keep it up)

Thank you! Since we don't get many comments on reactor.am, it's hard to tell if it's useful for others to share our masterminds.


Can you show some concrete examples? Non-idiotimatic Common Lisp compiled with SBCL can certainly come within a single digit integer factor of C, but your claim is much stronger. As for Chez, I have yet to see some code that compares favorably to even a fast scripting language, let alone a medium or high performance compiled language, and that's even if the code is littered with fixnum version of operators etc. Not what I'd call "very good performance characteristics" unless compared to bash or python.


I have seen tight functions compiled with SBCL matching and occasionally exceeding the speed of the C version. SBCL is a compiler which produces very good code. If you add enough type information so that SBCL can infer the types of all operations, you will get performance which compares very well to C.


There is no such thing as idiomatic Common Lisp.


CL-PPCRE is faster than the C version


It used to be, and when Edi Weitz first wrote it over a decade ago it was a very elegant example of the power of having a language that makes efficient code gen at runtime both possible and easy -- a single developer was able to outperform libraries with dozen of man years of investment over a beer-bet. But I'd be extremely suprised if that were still the case or if it were even within the same order of magnitude as the fastest regexp engines.

Also, despite the fact that scenarios that can leverage "jit-for-free" are both a best case scenario for lisps and not that rare in different fields (from firewall rules to stencil computations) to the best of my knowledge, even in this niche lisp plays absolutely no role in practice. To be clear, I don't think this due to any inherent shortcoming of lisp itself, indeed I suspect it's mostly due to brain-drain.


Rare to see Chez brought up, I've been increasingly integrating it into my own work recently. Its performance¹ and maturity of the runtime keep surprising me.

¹ Frequently on par or even better than LuaJIT, though it can take some work to get it there.


The power of luaJIT is that isn't doesn't take much work to get there. If you do normal things it ends up being very fast by default.


Yeah, no, I agree. But my experience with it has also been that as soon as you start writing anything except simple code, its performance starts to suffer, while Chez handles complex abstractions more gracefully. So I suppose comparing them directly might be a bit unfair both ways.


What kind of things end up being slow in LuaJIT?


Can't claim I remember much detail given how long I haven't worked with it. IIRC one of the issues had to do with tossing around anonymous functions inevitably causing it to give up on JITing and drop out into the interpreter


> Common Lisp has extremely good compilers that can meet C performance.

Provided memory is no object.

In general it takes five times as much memory for a GC'd program to be as performant as one with explicit memory management. See: https://www.cics.umass.edu/~emery/pubs/gcvsmalloc.pdf

There's a reason why the most interesting work these days is being done in and on languages like Rust, which has no GC but still saves you 90% of the work and close to 100% of the pain of bugs that are inherent to explicit memory management.


Usually it boils down to cargo cult against GC based languages instead of learning how to use all their features, including those for C++ like resource management.

https://devblogs.microsoft.com/aspnet/grpc-performance-impro...


While I can't speak for any experimental new garbage collectors, I did analyze the SBCL generational GC's implementation. I encourage anyone interested in performance to look over GC code and realize how much work they are doing.

That GC in particular has to stop the world, traverse the entire fresh heap, guesses whether something is even a pointer (and can guess wrong, causing a memory leak!), and does all this at arbitrary times, unless you do non-idiomatic things like manage your own memory in preallocated arrays, or use C/asm-powered memory mapped buffers [0].

Nothing comes for free, and some domains can't pay the price for GC (and choose to spend those resources elsewhere). Games, in my opinion, are largely still in that category.

[0] https://m.youtube.com/watch?v=S7nEZ3TuFpA


> unless you do non-idiomatic things

I wonder what exactly makes code "idiomatic" in a GC language. It is one of the greatest misconceptions about GC languages that you shouldn't worry about allocations at all. For me, GC mostly means the correctness guarantees which come with it and the convenience, that I don't have to track every single allocation and mange it manually. However, it still means that I should be aware of all the larger allocations and avoid them as in any other language, if I am looking for performance. Not reusing allocated memory where reasonable is detrimental to the performance in any language. And of course, the choice of the right GC approach can also help with applications like games. Lispworks even provided a Lisp environment for a Nasa probe, the GC had real-time capabilities.


Like the ones written in Unreal?

https://docs.unrealengine.com/en-US/ProgrammingAndScripting/...

Just because a language has a GC doesn't mean one needs to use it 100% of the time, which is exactly what is behind the .NET 5 performance improvements that top C++.

By making use of stack allocations, value types, memory slices, native heap allocations.

Features that Common Lisp also supports, and I bet Allegro and LispWorks are better than SBCL in the performance chapter.


It depends on what you talk about with "performance". Some years ago, Allegro had the faster GC than SBCL, but SBCL certainly had the best code generator of the three Lisps. So unless your runtime is constrained by the GC, SBCL really shines for performance. And it gives you a lot of knobs to optimize the memory usage.


SBCL generates the best code for toy benchmarks and number crunching applications. Throw it against a CLOS heavy codebase and you'll be surprised at how it runs VS Clozure CL and the aforementioned implementations.

ACL's GC is still the best hands down (and of course ABCL by virtue of the JVM). I think SBCL is still sporting a conservative GC on x86.


Not sure what you meant by "toy benchmarks", but to me this has a very negative connotation. The SBCL compiler excells at complex code and regularly produces much better output than most Lisp compilers. CLOS is a very bad example for judging the compiler quality, because its performance heavily depends on the implementation. To compare compilers, you would have to use the identical underlying CLOS implementation. A bad one can ruin your performance independantly of the compiler used. To make comparisons, one needs benchmarks where the whole code in question is compiled by the different compilers.

To my knowledge, SBCL switched to a precise GC some time ago. But I still would expect ACL's GC to outperform the SBCL one.


> In general it takes five times as much memory for a GC'd program to be as performant as one with explicit memory management.

In this blanket form, the statement is just wrong. Yes, with GC you need to have a larger heap space, as unreferenced objects will remain on the heap until collected and you want to have enough heap space so collections are infrequent enough, that a lot of objects can be collected (especially with generational GC, you want low survivor rates in the youngest generation).

However, how much space you want to reserve for that depends on many factors. Usually the extra space is proportional to the allocation and deallocation rates, not the total heap size. If you have lots of data on the heap which is long-living, this doesn't count to the extra space. Which leads to the allocation behavior of your program in general. If you want best performance, your program shouldn't blindly create garbage, but only, where it is needed. A lot of data can be stack allocated, so not counting towards the GC. And of course, you can have some amount of memory manually managed (depending on language), for bulk data. Be it entirely allocated outside the GCed heap or by keeping references alive to memory that manually gets reused. In all of these cases, this doesn't really count towards the extra space calculation.

The programming language used plays a huge role in this and the paper you quoted uses Java, which is a quite allocation-happy language, so the heap pressure is higher and you need more extra space to be performant.


At 3x memory you still get comparable performance, and memory is fairly cheap. In particular, memory sizes continue to scale, unlike CPU speeds, making GC an increasingly favourable proposition.


The end result is games that use 8GB of RAM like modded Minecraft. I was perfectly happy with 8GB of RAM for the entire system but no, that one game was so inefficient that I had to upgrade my entire system.

I will keep saying this over and over again. It's only cheap if you don't waste it. Once you are willing to waste it no amount of RAM will be good enough.


Some well-known existing work in this exact area:

https://github.com/kiselgra/c-mera

https://github.com/eudoxia0/cmacro (Written in Common Lisp, doesn't use S-exp syntax)

https://github.com/tomhrr/dale (Prev disc: https://news.ycombinator.com/item?id=14079573)

Newer stuff:

https://github.com/saman-pasha/lcc (No mention of meta-programming)

Lesser known:

https://github.com/deplinenoise/c-amplify (No docs, no update since 2010)


Thanks! I have a list of similar projects, I will add these! https://github.com/makuto/cakelisp/blob/master/doc/VsOtherLa...


Great to see Ferret there! I've used it in some Arduino projects. I'd love to see a comparison.

p.s. Carp is still actively maintained, should be on the other list.


> While languages like Rust offer benefits in terms of security and stability, they cost programmers in terms of productivity. It makes sense to value safety so highly if your code is safety-critical (operating systems, aerospace, automotive, etc.), but it's much less valuable when safety isn't as important (e.g. in games).

Just want to note that there is a large benefit to this kind of safety even if you're not writing safety-critical code: lack of bugs! The biggest benefit I've seen from rust is that entire classes of bugs, some of which can be extremely difficult to root cause and fix, are removed by design. So you spend significantly less time on the later half of the project tracking down bugs, which is more than enough to offset the productivity loss at the beginning.


This has been my experience as well. I'm building an exploratory game project in Rust to test the waters for switching to it from C++ for a professional project. Initially I was hesitant because I didn't really care about memory safety, so I didn't want to pay some mental overhead for something I didn't care about. But after using Rust for a while, I'd hands-down choose it over C++, even for projects where I feel like I don't care about either memory safety or even maintainability like single player games. The ergonomics are just so much better, the package manager exists (and is good), and the constraints placed on the architecture really just result in the program being easier to grow.

So while safety and maintainability are what Rust gets marketed for, the ergonimics and just overall productivity of the language is enough to sell me on it for game dev. Languages like Zig and Jai also seem interesting in this space, but they're far from being ready to do anything in production with. The Rust ecosystem is actually ready for production now, and the language is a pleasure to work with.


Would love to see a comparison with https://gamelisp.rs/


It looks like Cakelisp for Rust! I'll have to look at it in more depth. Thanks for the link!


I have not used it but I think is not written for performance in the same way that Cakelisp appears to be:

https://gamelisp.rs/reference/performance-figures.html#bench...

It seems more intended for scripting glue code in a Rust project


Hello! I'm the developer of GameLisp :)

You're correct that I've chosen safety and convenience over performance. I might eventually consider integrating the Cranelift code generator to try to achieve LuaJIT-like performance, but it's definitely not on the short-term roadmap.

In practice, I find that GameLisp is more than fast enough to script a busy 2D platformer, as long as you're sensible about using Rust for the more CPU-intensive parts of your game engine.

Incidentally, I'm planning to release GameLisp 0.2 within the next few days - happy to field any other questions while I'm here!


This reminds me a lot of c-amplify. I didn't see it in the author's list of languages they tried so I thought I'd mention it, it has a lot of neat ideas for building a lispy C.

https://voodoo-slide.blogspot.com/2010/01/amplifying-c.html https://github.com/deplinenoise/c-amplify


Those projects really need more game examples. The best poster child for lisp based gamedev is crash bandicoot and it is almost 20 years old now.


So many articles on Lisps on the front page. Did I miss something? It is Lispmas?


This looks great. The S-expr syntax is my favourite, though I'd have preferred a Clojure-like one personally, a CL inspired one is still fine.

Some of the downsides mentioned can easily be taken care of by a macro I believe. Like the path traversal can be flattened with a macro most likely. Same thing for the type definitions.


It looks like an interesting project. The syntax for pointers is what grabbed my attention at first. Would really need to spend some time with this to know how it would work in practice.

    const char* myString = "Blah";
    (var my-string (* (const char)) "Blah")


Thanks! It is a bit different, and does require more typing, but I like how unambiguous it is. It also simplifies code modification by making type parsing and changing easier, because you can recursively unwrap multiple pointers, or pointer-ify things easily.


Have you looked at newlisp? It has pretty seamless interop with C pointers.


Looks fantastic. Does it handle typedefs too? So one could write

   (var my-string conststring "Blah")
with the appropriate typedef.


Yes! You can typedef types and function signatures.


It looks how I’d code Lisp if I was C programmer.


That seems to be the explicit intent of the creator; a way to output C/C++ and hit the same use case targets but with much more powerful code generation facilities and a syntax that is much more amenable to that.


That's correct. My goal wasn't to make a CL-compatible Lisp. I imagine the code will start to look less like C as more macros/generators get added.


Is there any reason this couldn't/shouldn't be used for applications besides than games? Other than your motivation/goals coming from solving game development problems, I didn't see anything that makes this useful for _only_ games.

Edit: The GitHub repository implies that this could be used for purposes other than games:

> The goal is a metaprogrammable, hot-reloadable, non-garbage-collected language ideal for high performance, iteratively-developed programs (especially games).


Yes, there's nothing in the language which is specific to games.

Once I get pure C output supported, it should be suitable even for embedded C environments.


How does it compare with Carp, another lisp with C interop?

Why did the creator create this, wont Carp have served the purpose.?


Carp requires writing bindings to call C functions or use types. Additionally, code modification isn't possible in Carp.

When I say seamless, I'm going for as close as possible, I.e. it should feel even easier to use C from Cakelisp than from C itself. The build system especially makes this possible.


As someone who works on Carp, it seems we're going for one level of abstraction higher than what this is aiming for. It's pretty easy to do C interop but the goal isn't to write "C in S-expressions".

Doesn't mean it doesn't perform well, currently writing a GBA game: https://github.com/TimDeve/radicorn


I’m interested in this “comptime” aspect. Zig has it too, but are there any other languages that use this? I’m under the impression that there’s a distinction between comptime evaluation and typical lisp macros.


The big distinction to me is that there is a final executable that eventually gets created, whereas Lisp programs can continue to generate code and self-modify at runtime.

Cakelisp differs from Zig in that arbitrary code modification is supported, which is a step closer to the modifiable environment of Lisps. Very few languages besides lisp allow you to do things like "iterate over every function defined and change their bodies, and create a new function which calls them". Zig does not support that. It's extremely useful for some tasks (e.g. hot-reloading code modification, mentioned in the article)

Jai isn't out yet, but I was inspired by many of the comptime ideas.


I don’t know how comptime works in Zig, but D has nearly unrestricted compile time code execution.


?

Lots of things don't work in d's CTFE.

It's certainly very useful, and much better than e.g. c++ constexpr. But it's still worlds away from proper lisp metaprogramming.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: