Compile-Time Evaluation in the Zig System Programming Language
andrewkelley.me
andrewkelley.me
In other words, could you replace the C preprocessor / C++ metaprogramming with something like Lua? That is, have Lua/C instead of Lua/Terra.
That would be adopted a lot faster than a brand new language. I think one problem as always is parsing C++, but that should be doable with Clang now.
EDIT: Also, what about it is not ready for prime time?
Lua + C would really confuse at least me. But nothing's really stopping you I guess. Lua, or any script-ish language could be used instead of the C preprocessor. Why not Python? Perl?
This is basically the direction of constexpr in fact with C++.
I would love a new, slightly fixed/incompatible C17 (not D or subpart of C++, just C11) with
- c++17-like constexpr (and its uses anywhere : switch cases, array sizes.. ) - deprecated oldstyle args, undeclared functions, trigraphs - (templates can be mostly done with pure inlining+constexpr) - better keywords (static -> private (by default/explicit public), persist ) - fixed operators precedence (1<<3 +1=16 yay) - typed enums with explicit storage class - reduce preprocessor ability(discourage and just generate from lua/python/C programs if you really need, maybe with a shebang-like line). replace conditional compilation with constexpr ifs,
- sadly, nobody mentions BET MetaOCaml http://okmij.org/ftp/ML/MetaOCaml.html which is probably first place you want to look before you try to build this yourself.
- in Lisp, this is trivial (as explained here : http://www.ymeme.com/hackers-introduction-partial-evaluation... )
Of course, Lisp isn't really a systems language like Zig -- I think it's great that it's tackling the problem its own way.
Recently, I was thinking about a language, where the user could decide which parameters to make comptime. Examples:
Normal function call: foo(a, b)
Function call with comptime: foo(comptime 42, b)
What actually happens at runtime: fooVariant(b)
The compiler makes a duplicate of foo, where the first parameter is removed and the constant 42 used instead. Compiler writers may know this as the transparent "procedure cloning" optimization.
This increases flexibility, because the writer of a function does not have to decide which parameters are comptime and which are not. This sometimes leads to duplications, for example with regular expressions, where the pattern is very often comptime, but not always.
If I have one complex function which calls 50 other functions, do I clone all of them too? And what about functions called indirectly? The amount of cloning could become massive, and it might lead to worse performance (e.g. so much code is cloned that the code no longer fits in the CPU caches.)
Conversely, if I am only cloning the function I am calling, then that might not be a very useful feature, because the function I am calling might do very little – it might just be a thin wrapper around another function.
The advantage of doing it on the function parameter declaration is the function author has to work out the propagation aspect themselves (by deciding whether to make the arguments of the indirectly called functions comptime or not.)
Because it's at least exponential time and space otherwise, and sometimes much more :)
(becasue you may have to duplicate the entire call path rooted at foo)
One of its main drawbacks is it falls under the category of interprocedural optimization (as opposed to intraprocedural) which can quickly balloon into a practically intractable problem for large programs.
Also, it's just difficult to imagine it working in many non-cherry-picked examples. You have to prove that a given parameter is constant over all callsites to a function, which can be difficult e.g. in the presence of indirect/virtual function calls.
[1] http://www.llpe.org/ [2] http://llvm.org/devmtg/2015-04/slides/LLPE.pdf
My question (I'm not a systems coder), is how is this really better than C? How can it be even remotely as efficient as a compiler with decades of optimization witchcraft and sorcery? Is it really that much easier to write? I'd be curious in seeing a small 1/2 page code sample difference and seeing benchmarks on performance, compile times...etc. Nim normally jumps to mind as an easy to write language that transpiles to C and is therefore usually fairly equivalent, but is almost as easy to write as python. How does Zig fit in? Also, good luck on the project!
I don't know enough to say anything myself, but i believe it mostly boils down to C allowing too much freedom, with tok few constructs, with too little communication between programmer and compiler.
The C compiler must derive certain facts from a given block of code to optimize it in a particular fashion; and the derivation must be correct for all edge cases. The witchcraft and sorecery is in these derivations, and handling pathological edge cases.
AFAIK these C-alt languages tend to skirt this problem by adding language constructs that make certain promises to the compiler, like Zig's comptime attribute and rust's borrow checker. They catch up to C, at least for some common classes of problems, by simply giving the programmer more expressive power.
And then, I imagine, they have an easier time taking some sequence of these (stronger) promises and combining them into further sets of optimizations.
Which is also what "higher level" languages do (more by limiting freedom of action, and increasing expressive ability, than communication with the compiler) and how you get ideas like haskell being as fast/faster than C code in the common case (but won't match handwritten optimized C). A Haskell compiler can make bigger steps more safely than a C compiler can, simply because the language offers more/bigger guarantees with each construct.
(If this is an object-manipulating program and not a numeric one, substitute another language so I don't have do memory management.)
The issue is that magic high-level-compiling compilers can't be developed because nobody has time to wait for their compile to finish. This is also why JIT never really optimizes very hard.
[1] or more importantly, less memory-using and live profiling tools and gdb will work.
When you're going low-level like in C, optimizations are famously useless on x86 - you can barely tell if most programs are running at O0 or O3.
Going higher level, they should help, but it's really an interactive process so a fast compile/run cycle is still important. You want to know how well the optimizer understands your program and which idioms are safe to use.
In this case, partial evaluation is a massively more principled and efficient way of doing metaprogramming than preprocessing or macros. There are limitations compared to Lisp-style unrestricted untyped metaprogramming, but not any that I would much miss in practice.
With partial evaluation, we automatically get type and scope safety, and also only need one language instead of several. Optimizations also cascade in a principled way: we can compile code-generating code to fast machine code, which we then use to generate faster code or generate it faster, but the then-resulting code can be also used to generate code, and so on.
Using LLVM (which Zig does) gives you access to the same middle-end and back-end optimizations as clang.
This is just a frontend. The optimization witchcraft and sorcery all lives in the middle/backend, which in this case is LLVM. LLVM can do a decent job optimizing pretty much anything you throw at it, though broadly speaking it works better the more the IR looks like C. For example, Rust does a lot of moves of large structures, unlike C/C++; IIRC pcwalton submitted some optimizations involving those to LLVM, which are language-neutral but which nobody had bothered to implement before because C/C++ didn't need them as much.
Nim, C++, D (and Rust in a very limited fashion) all have compile time function evaluation, but not remotely with such a low overhead syntax.
What is high overhead about D's syntax for compile time function evaluation?
With apologies to jwz.
[1] ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-057.pdf
I don't know if Zig does that. Anyway, having different phases is not conceptually hard, although it can bite you a bit with Macros in Scheme.
If it has a GC, I'd find it even more interesting...
The description indeed leaves a lot open to interpretation. They should have a brief overview that uses some standard terminology to describe Zig.
> There is another thing I noticed, and I hope someone from the Rust community can correct me if I'm wrong, but it looks like Rust also special cased format_args! in the compiler by making it a built-in. If my understanding is correct, this would make Zig stand out as the only language of the three mentioned here which does not special case string formatting in the compiler and instead exposes enough power to accomplish this task in userland.
It depends what you mean by "userland". Rust has long supported procedural macros, albeit not on stable compiler versions until recently (and still only hackily there). Procedural macros, a.k.a. compiler plugins, are written in Rust, but work differently from compile-time function evaluation. With CTFE, the code running at compile time lives in the same "world" as the rest of the code being compiled, in a sort of pretend version of the target environment where you can't do things like call external functions. Rust compiler plugins are just separate libraries that get compiled for the host architecture and loaded into the compiler process (which is less scary than it sounds; the build process "just works" thanks to Cargo, and Rust's safety ensures you don't stomp on random compiler state). You have access to the full language and can call whatever you want, even do things like file I/O if needed; on the other hand, you're in a separate environment and can't just name variables, functions, etc. from the runtime world.
Currently, Rust compiler plugins are purely syntactic: you can look at the tokens of the macro invocation and that's it. You can't, say, ask the compiler for the definition of a type or the value of a named constant; plugins are executed too early for that. I think it'd be nice if that changed in the future, but it would be hard to implement without giving up the ability to emit arbitrary syntax as the output of the macro; there would be trouble with circular dependencies (think type inference).
But what currently exists is enough to implement safe printf, in conjunction with Rust's type system. format_args! is built into the compiler, so it could cheat, but it doesn't; like user-defined macros it's purely syntactic. The following Rust code:
println!("a={} b={}", a, b);
_print(Arguments::new_v1(&["a=", " b=", "\n"],
&[ArgumentV1::new(&a, Display::fmt),
ArgumentV1::new(&b, Display::fmt)]));
Arguably it's nicer to be able to know the types of the arguments within the format parsing routine, and other use cases require that kind of feedback, but Rust's approach works pretty well here.
By the way, Rust also has a Turing-complete type system and a rudimentary form of compile-time function evaluation, which in the future might be powerful enough to express code similar to the Zig implementation, but for now it's not really designed for that sort of thing.
Sidenote: While C's metaprogramming is rather limited, C++14 CTFE is pretty powerful and you can parse format strings at compile time there too:
https://akrzemi1.wordpress.com/2011/05/11/parsing-strings-at...