はじめに

Rustと聞いて一歩後ろに下がる。なぜかRustはおそろしい。。。
でもそんな私がRustをやってみたいと思ったのは
「コンピュータシステムの理論と実装」
というかわいいアライグマの本を勉強会でやることになったのがきっかけでした。

かわいい表紙に似合わず内容はエグいのですが、Nandという論理ゲートからテトリスをつくってしまうというお話です。
そこでスタック、ヒープという言葉がでてくるのですが、想像がむずかしい。なんとなくわかったような気になっても実はわかっていない。
そんな時にしっくりきた説明を見つけてしまった！！！それが「The Rust Progrumming Lunguage」だったのです。

スタックとヒープ
多くのプログラミング言語において、スタックとヒープについて考える機会はそう多くないでしょう。
しかし、Rustのようなシステムプログラミング言語においては、値がスタックに積まれるかヒープに置かれるかは、言語の振る舞い方や、特定の決断を下す理由などに影響以上のものを与えるのです。

全文

Rustを学んで気づいたこと、アライグマを読んで気づいたことを何回かに分けて書いていこうと思います。
気づいたこと、指摘等あればコメントで教えてください。

スタック

まずスタックとは何か。
「高速に計算できる場所（メモリ）」です。

スタックは、得た順番に値を並べ、逆の順で値を取り除いていきます。これは、 last in, first out(訳注: あえて日本語にするなら、「最後に入れたものが最初に出てくる」といったところでしょうか)と呼ばれます。お皿の山を思い浮かべてください: お皿を追加する時には、山の一番上に置き、お皿が必要になったら、一番上から1枚を取り去りますよね。途中や一番下に追加したり、取り除いたりすることもできません。データを追加することは、スタックにpushするといい、データを取り除くことは、スタックからpopすると表現します。

これで理解できる人は天才です。
何を追加し、何を取りのぞくのか、少し詳しくみていきます。
まず、「逆ポーランド記法（後置記法）」というものがあります（まだ我慢💧）
理解するとそんなに難しくありません。
普通の計算は中置記法です。

(1+2)*(3+4)

これは21です。簡単です。
これを逆ポーランド記法で書くと

1　2　+　3　4　+　*

逆ポーランド記法の計算ルールを定義します。
数式の左からスタックにお皿（数字もしくは演算）を乗せていきます。左がお皿の一番上だと思ってください。

数字が来たらお皿を一番上に乗せます（push）。
演算が来たらお皿の一番上２つをその演算で計算します。計算したお皿は取り除き、結果をお皿の一番上に乗せます。
乗せるお皿がない場合は一番上から計算します。

まず"1"は数字なので一番上にのせる。"2"も同じでその上に乗せます。

2　1

次に"+"が来たので計算した"3"をお皿の一番上に乗せます。

次に来るのは"3"です。数字なのでお皿に乗せます。"4"も同じ。この時、上で計算した"3"はお皿の下に行きます。

4　3　3

次に"+"が来たので２つを計算した"7"をお皿の一番上に乗せます。
この状態でお皿は

7　3

最後の演算"*"が来たので計算します。

無事に計算ができました。
コンピュータが計算しやすくする仕組みを簡単に抽象化するとこうなります。
スタックで演算が高速になるのは計算するべきデータを探しにいく必要がないからです。

データへのアクセス方法のおかげで、スタックは高速です: 新しいデータを置いたり、データを取得する場所を探す必要が絶対にないわけです。というのも、その場所は常に一番上だからですね。スタックを高速にする特性は他にもあり、それはスタック上のデータは全て既知の固定サイズでなければならないということです。

ではヒープはなんでしょう？

ヒープ

サイズがわからないデータはヒープに置かれます。
ヒープにデータを確保するためにはOSとの会話が必要になります。

実行コード：メモリを確保したいんだけどいい？
OS：はい。アドレスはここ使ってね。
OS：使ってもいいけど管理は自分でしてよ。使ったら最後片付けてね。
実行コード：ヒープデータ？どうやってメモリの管理すればいいの？サイズがわからないのに。
実行コード：このままだと落ちてしまう！どのメモリは片付けちゃっていいの？
Java,Rubyなど:ではガベージコレクションでお掃除しましょう。
Rust：所有権、Dropトレイトで解決しましょう。

コンパイル時にサイズがわからなかったり、サイズが可変のデータについては、代わりにヒープに格納することができます。ヒープは、もっとごちゃごちゃしています: ヒープにデータを置く時、あるサイズのスペースを求めます。 OSはヒープ上に十分な大きさの空の領域を見つけ、使用中にし、ポインタを返します。ポインタとは、その場所へのアドレスです。この過程は、ヒープに領域を確保する(allocating on the heap)と呼ばれ、時としてそのフレーズを単にallocateするなどと省略したりします。 (訳注: こちらもこなれた日本語訳はないでしょう。allocateは「メモリを確保する」と訳したいところですが) スタックに値を積むことは、メモリ確保とは考えられません。ポインタは、既知の固定サイズなので、スタックに保管することができますが、実データが必要になったら、ポインタを追いかける必要があります。

part1 まとめ

これはRust（C++などのシステム言語に詳しい人はご存知だと思います）で初めてコードを書く時には非常に困惑します。
どのデータがスタックに確保されて、どのデータがヒープに確保されるのか。
プリミティブなデータはスタックに積まれるイメージです。スタックに積まれるデータはコピートレイトを実装しているので参照が必要ない。
ヒープのデータがどこでDropされているかを把握することがRustで大事になってきます。