Why I like programming for #![no_std] in Rust (even without embedded)

栏目: IT技术 · 发布时间: 4年前

内容简介:I noticed that I quite enjoy writing libraries that support no_std environments, even though I myself don't even work on embedded.Its just very fun to try and get as many features done without ever allocating, purely from a challenge point of view.There is

I noticed that I quite enjoy writing libraries that support no_std environments, even though I myself don't even work on embedded.

Its just very fun to try and get as many features done without ever allocating, purely from a challenge point of view.

There is also some benefits one can hope for, the two big ones being usability in more cases, like embedded, and better performance due to less memory management overhead, possibly less indirection and therefore more compiler insight

After a bit of thinking I realized that there is one more, and much more fundamental issue: If im not mistaken Rust without allocations is not Turing complete (for the most part).

What is Turing complete

Basically a Turing machine can solve any problem that we know how to solve at all. A language that is Turing complete is to some degree equivalent to a Turing machine, i.e. can be transformed into one without gaining or loosing functionality. Most programming languages, including Rust, are Turing complete.

Computer science can also reason about "über Turing machines" that can solve problems even Turing machines can't solve, but we have no idea how to build one of those even in theory.

While being most powerful, Turing complete languages also have some drawbacks. They are harder to reason about than their lesser peers. For examples its impossible to tell if a given program is going to run into an endless loop/recursion.

Dual stack automata and Rust

Dual stack automata are constructs that are exactly as powerful as Turing machines. They are finite automata that also have access to two separate stacks. As soon as you have two stacks you can build any kind of data structure, including any number of stacks.

You can consider normal Rust to be one of those. You have the code as the automaton, the call stack as one stack and stuff on the heap as the second stack.

Now no_std, or more specifically Rust without allocations lacks the second stack. Its therefore (mostly) a (single) stack automaton. As such its strictly less powerful than allocating Rust, i.e. there exist problems that can be solved in allocating Rust, but are impossible to express in alloc-free Rust.

Because many tasks actually do not require a Turing machine to solve, actually solving them on a less powerful machine is a fun challenge and I think that is why I like it.

(mostly) a single stack automaton?

How can something be mostly a single stack automaton? Well for one no programming language is actually like really really Turing complete. A dual stack (and even a single stack!) automaton requires two (one) unbounded stacks.

Unbounded as in as large as the problem needs it to be. Real computers have limited hard disk space though, so they fail that requirement for big problems. And in practice fail it even for much smaller problems cause no one wants to use Disk as Memory.

In the same way you could have a second, bounded, stack be an element in your single stack and therefore have "two" stacks. But at this point you are basically building an allocator anyway :).

Also no_std and alloc free Rust still allow for infinite loops and recursions. That's true but basically never a good idea. Since you only have one stack, that at any point has a known number of elements it basically never makes sense to iterate over anything without bounds.

I might also have overlooked some other loophole, just send a pull request with your nit picks. There might also be something wrong with my understanding of the computer science, feel free to correct.

Add your comments on reddit !


以上所述就是小编给大家介绍的《Why I like programming for #![no_std] in Rust (even without embedded)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

掘金大数据

掘金大数据

程新洲、朱常波、晁昆 / 机械工业出版社 / 2019-1 / 59.00元

在数据横向融合的时代,充分挖掘数据金矿及盘活数据资产,是企业发展和转型的关键所在。电信运营商以其数据特殊性,必将成为大数据领域的领航者、生力军。各行业的大数据从业者要如何从电信业的大数据中挖掘价值呢? 本书彻底揭开电信运营商数据的神秘面纱,系统介绍了大数据的发展历程,主要的数据挖掘方法,电信运营商在网络运行及业务运营方面的数据资源特征,基于用户、业务、网络、终端及内在联系的电信运营商大数据分......一起来看看 《掘金大数据》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换