{ "cells": [ { "cell_type": "markdown", "id": "26524732-e864-4158-a826-9e0772f14cac", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "## Motivation\n", "For many years, C++ used to be my favourite language for performance-critical applications. I find Python much more convenient for many use cases, but I have always enjoyed employing zero-cost abstractions and writing generic code that can be compiled to optimal assembly.\n", "\n", "However, C++ has a number of downsides, such as\n", "* problems that arise from [undefined bahaviour](https://en.cppreference.com/w/c/language/behavior) in the code,[1](#fn:undefined-behavior)\n", "* all the baggage it carries due to its backwards compatibility with almost all C++ code and much of the C code that has ever been written.\n", "A consequence is that C++ is more cumbersome and error-prone to use than more modern languages, and that developers are less productive than they could be.\n", "\n", "Rust tries to address these issues and enable excellent performance at the same time, so I decided that I should give it a try a few years ago. I started playing around with it for [Advent of Code](https://adventofcode.com/) problems, enjoyed it a lot, and wondered what practice project I could try next.\n", "\n", "\n", "\n", "A non-trivial practive project for any programming language is to implement an interpreter. [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) is the simplest language that I can think of, so a Brainfuck interpreter is what I implemented some time ago. Recently, I've improved it a bit and decided to write down the steps that I took.\n", "\n", "Readers who have some experience with Rust will find this post easier to follow, but it does not assume any prior Rust knowledge. It does not aim to explain every concept in great detail though. If you want to know more, you can find a good introduction in [*The Rust Programming Language*](https://doc.rust-lang.org/book/)." ] }, { "cell_type": "markdown", "id": "de08b6aa-8cc8-43f9-9974-a9e740397c3d", "metadata": {}, "source": [ "## Brainfuck\n", "You can read a lot about Brainfuck in its [Wikipedia article](https://en.wikipedia.org/wiki/Brainfuck). Its most important aspects are:\n", "* Brainfuck code operates on memory which is organized as a one-dimensional array of byte cells. I like to call it *tape* because it resembles the tape of a [Turing machine](https://en.wikipedia.org/wiki/Turing_machine).\n", "\n", " Besides the tape itself, there is a *data pointer* which points to the current cell.\n", " \n", "* There are eight instructions, which are represented by a single character each.\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
instructioneffect
-decrement the byte inside the current cell by one
+increment the byte inside the current cell by one
<decrement the data pointer by one, such that it points one cell further to the left
>increment the data pointer by one, such that it points one cell further to the right
.output the byte in the current cell to standard output
,read a byte from standard input and store it in the current cell
[loop start: if the byte in the current cell is zero, jump to the instruction after the matching ']' instruction, otherwise, go to the next instruction
]loop end: if the byte in the current cell is non-zero, jump to the instruction after the matching '[' instruction, otherwise, go to the next instruction
\n", "\n", " All other characters are considered comments and are ignored during execution.\n", " \n", " Loops which would correspond to\n", " \n", " ```C\n", " while (current_cell_value() != 0) {\n", " /* loop body: instructions between [ and ] */\n", " }\n", " ```\n", " \n", " in C-like languages can be built with '`[`' and '`]`'.\n", " A '`[`' and a '`]`' instruction match just like parentheses would in an arithmetic expression, so you can build nested loops with these instructions.\n", " \n", " \n", "\n", "* Brainfuck is Turing complete: it can in principle be used to write programs that perform any computation that you can think of (at least if the tape has infinite size). However, it is not very practical because most programs tend to be very long and convuluted. This makes Brainfuck a [Turing tarpit](https://en.wikipedia.org/wiki/Turing_tarpit)." ] }, { "cell_type": "markdown", "id": "1053a425-2e92-4ca7-bd27-1b6a0d1965f1", "metadata": {}, "source": [ "## How you can experiment with the code in this post\n", "Like many of my posts, this post is a [Jupyter](https://jupyter.org/) notebook, which you can [download](index.ipynb), execute, and modify. You just need Jupyter, [Rust](https://rustup.rs/), and the [evcxr_jupyter crate](https://crates.io/crates/evcxr_jupyter). You can also work with the notebook easily in Binder (it might take a while to start up): [![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/freininghaus/freininghaus.github.io/main?labpath=posts%2F2024-02-04-brainfuck-interpreter-in-rust-part1%2Frust-bf-part1.ipynb)" ] }, { "cell_type": "markdown", "id": "9ab0165c-501a-444a-90f3-d9fae592330c", "metadata": {}, "source": [ "## Modeling the tape in Rust\n", "The original Brainfuck specification uses a finite tape with 30,000 cells. Each cell holds a single byte, which is initialized to zero. Moreover, there is a movable data pointer which points to the leftmost cell initially.\n", "\n", "We could model this with an array with 30,000 bytes:[2](#fn:integers)" ] }, { "cell_type": "code", "execution_count": 2, "id": "d4f1ff9a-7f1d-4614-b9ed-f0420b6b71bf", "metadata": {}, "outputs": [], "source": [ "struct ArrayTape {\n", " data: [u8; 30000],\n", " pos: usize\n", "}" ] }, { "cell_type": "markdown", "id": "b5e52448-85d7-4389-935e-c7083996a4c8", "metadata": {}, "source": [ "We can create a tape with all cells initialized to zero like this:" ] }, { "cell_type": "code", "execution_count": 3, "id": "16d8c5f2-5b5e-4c4a-917c-d39c26c24297", "metadata": {}, "outputs": [], "source": [ "let my_tape = ArrayTape { data: [0; 30000], pos: 0 };" ] }, { "cell_type": "markdown", "id": "7f2cfc4e-cd77-4756-8fa1-d8008e889f69", "metadata": {}, "source": [ "It is common to add a method `new()` to a type, which creates a new instance of this type:" ] }, { "cell_type": "code", "execution_count": 4, "id": "dbe719ad-1bb0-41c2-a68e-59a7cf62e568", "metadata": {}, "outputs": [], "source": [ "impl ArrayTape {\n", " fn new() -> Self {\n", " Self {\n", " data: [0; 30000],\n", " pos: 0\n", " }\n", " }\n", "}\n", "\n", "let my_tape_2 = ArrayTape::new();" ] }, { "cell_type": "markdown", "id": "92c89e98-61fc-4ef6-b800-eee872c8f05d", "metadata": {}, "source": [ "Inside the `impl ArrayTape { ... }` block, `Self` is synonymous to `ArrayTape`, so it can be used as the return type of `new()` (after `->`) and inside the function. Note that no `return` statement is needed: If no `return` is encountered while executing a function, the final expression, which is not terminated with a semicolon, is returned." ] }, { "cell_type": "markdown", "id": "546ce96b-d4f7-4bc0-9eb8-6f9e73299ca8", "metadata": {}, "source": [ "We can make our Brainfuck interpreter more flexible by using a [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html), which is essentially a dynamic resizable array. Then we can handle more than 30,000 cells, and we do not have to allocate space for and initialize cells which we might not need at all during execution: we will just add a new zero at the end whenever the pointer moves off the tape to the right. Initially, we will use just a single cell and initialize the `Vec` with the [`vec!` macro](https://doc.rust-lang.org/std/macro.vec.html):" ] }, { "cell_type": "code", "execution_count": 5, "id": "18e15516-8cf6-48f3-a7a2-528d75f0b32e", "metadata": {}, "outputs": [], "source": [ "struct VecTape {\n", " data: Vec,\n", " pos: usize\n", "}\n", "\n", "impl VecTape {\n", " fn new() -> Self {\n", " Self{\n", " data: vec![0],\n", " pos: 0\n", " }\n", " }\n", "}" ] }, { "cell_type": "markdown", "id": "31868af7-8bcf-4825-9925-0e4b5bd9f828", "metadata": {}, "source": [ "But we will use an even more flexible solution here, namely, a [`VecDeque`](https://doc.rust-lang.org/std/collections/struct.VecDeque.html), which is a double-ended queue that allows efficient addition of items at either end. This enables programs which move the data pointer to the left from the initial position.\n", "\n", "Moreover, we will use the macro [`#[derive(Debug)]`](https://doc.rust-lang.org/rust-by-example/hello/print/print_debug.html), which makes it possible to output the state of a tape easily, as we will see later:" ] }, { "cell_type": "code", "execution_count": 6, "id": "b5cf80e7-7e35-4f79-8d40-fbe12303fb39", "metadata": {}, "outputs": [], "source": [ "use std::collections::VecDeque;\n", "\n", "#[derive(Debug)]\n", "struct Tape {\n", " data: VecDeque,\n", " pos: usize\n", "}\n", "\n", "impl Tape {\n", " fn new() -> Self {\n", " Self{\n", " data: VecDeque::from([0]),\n", " pos: 0\n", " }\n", " }\n", "}" ] }, { "cell_type": "markdown", "id": "c9ac225b-549b-49ad-a967-048a87afc9c4", "metadata": {}, "source": [ "Now we will implement some functions that operate on a `Tape` to make working with it convenient. First, we would like to read and write the value of the current cell. Unlike `new()`, which does not operate on an existing `Tape` instance (in C++, this would be indicated with the `static` keyword), the next functions take a tape by reference and by mutable reference, respectively:[3](#fn:self)" ] }, { "cell_type": "code", "execution_count": 7, "id": "0e9f2c16-f388-4300-9cd0-ac71d4bb2060", "metadata": {}, "outputs": [], "source": [ "impl Tape {\n", " fn get(&self) -> u8 {\n", " self.data[self.pos]\n", " }\n", "\n", " fn set(&mut self, value: u8) {\n", " self.data[self.pos] = value;\n", " }\n", "}" ] }, { "cell_type": "markdown", "id": "90f15aba-485f-478a-99c6-f1d5a61102de", "metadata": {}, "source": [ "We can test that this works as expected. Note how we have to declare the variable as mutable because immutability is the default in Rust:[4](#fn:cell-final-expression)" ] }, { "cell_type": "code", "execution_count": 8, "id": "8b549887-a412-41ec-ae5a-e6d04d85a3e9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let mut t1 = Tape::new();\n", "t1.get()" ] }, { "cell_type": "code", "execution_count": 9, "id": "662d5739-7a8e-4785-9504-1501956be5e6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t1.set(5);\n", "t1.get()" ] }, { "cell_type": "markdown", "id": "4e3b7ccc-86ba-45fa-8071-073eb12db9ee", "metadata": {}, "source": [ "In a unit test, we would not want to look at the output, but prefer to have the expected results verified automatically. This can be done like this:" ] }, { "cell_type": "code", "execution_count": 10, "id": "3e07396c-3cb2-4ae4-a299-ef644a2a1163", "metadata": {}, "outputs": [], "source": [ "let mut t2 = Tape::new();\n", "assert_eq!(t2.get(), 0);\n", "t2.set(17);\n", "assert_eq!(t2.get(), 17);" ] }, { "cell_type": "markdown", "id": "e2490eaa-c048-4fe1-b9ec-b563dfe4028f", "metadata": {}, "source": [ "If such a check fails, the test will panic and output details about which assertion failed and what the expected and actual results were:" ] }, { "cell_type": "code", "execution_count": 11, "id": "7809a7f3-8adb-4d32-bbbc-a53a26526559", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "thread '' panicked at 'assertion failed: `(left == right)`\n", " left: `17`,\n", " right: `1`', src/lib.rs:153:1\n", "stack backtrace:\n", " 0: rust_begin_unwind\n", " at /rustc/5680fa18feaa87f3ff04063800aec256c3d4b4be/library/std/src/panicking.rs:593:5\n", " 1: core::panicking::panic_fmt\n", " at /rustc/5680fa18feaa87f3ff04063800aec256c3d4b4be/library/core/src/panicking.rs:67:14\n", " 2: core::panicking::assert_failed_inner\n", " 3: core::panicking::assert_failed\n", " 4: run_user_code_10\n", " 5: evcxr::runtime::Runtime::run_loop\n", " 6: evcxr::runtime::runtime_hook\n", " 7: evcxr_jupyter::main\n", "note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.\n" ] } ], "source": [ "assert_eq!(t2.get(), 1);" ] }, { "cell_type": "markdown", "id": "1cc805a5-fa6e-4266-a007-e3d8bf30d91f", "metadata": {}, "source": [ "So far, we can only read and write the value of the current cell. To model the entire Brainfuck instruction set, we also need functions that move the data pointer:" ] }, { "cell_type": "code", "execution_count": 12, "id": "fec59776-1c3a-4fc8-8d72-f9d64279650e", "metadata": {}, "outputs": [], "source": [ "impl Tape {\n", " fn right(&mut self) {\n", " self.pos += 1;\n", " if self.pos == self.data.len() {\n", " // The data pointer is moving off the tape:\n", " // add a new zero-valued cell at the back.\n", " self.data.push_back(0);\n", " }\n", " }\n", " \n", " fn left(&mut self) {\n", " if self.pos > 0 {\n", " // We have not reached the leftmost cell yet.\n", " // Just move the data pointer to the left.\n", " self.pos -= 1\n", " } else {\n", " // If self.pos is 0, the data pointer points to the leftmost cell.\n", " // Add a new cell at the front and leave the pointer as it is.\n", " self.data.push_front(0);\n", " }\n", " }\n", "}" ] }, { "cell_type": "markdown", "id": "b292d25c-aee3-4039-8011-0b00133269d9", "metadata": {}, "source": [ "Let's try it, and then print the state of the tape. This can be done easily because we have used `#[derive(Debug)]` when defining the `Tape`:" ] }, { "cell_type": "code", "execution_count": 13, "id": "7fe63782-b992-4d67-b9c2-9c372cb89458", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Tape { data: [1, 2, 3], pos: 0 }" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let mut t3 = Tape::new();\n", "\n", "t3.set(2);\n", "t3.right();\n", "t3.set(3);\n", "t3.left();\n", "t3.left();\n", "t3.set(1);\n", "\n", "t3" ] }, { "cell_type": "markdown", "id": "49f5f9d0-976a-41d1-9e72-9ada30fa7c90", "metadata": {}, "source": [ "## How to model Brainfuck instructions: Rust `enums` are more than just named numbers\n", "Now that we have a data structure for the tape, it's time to model the instructions. We will use an `enum` for that.\n", "\n", "It might be tempting to use a definition like this:" ] }, { "cell_type": "code", "execution_count": 14, "id": "05a0facc-fb97-41a9-aefb-3b51d5cd46b3", "metadata": {}, "outputs": [], "source": [ "enum InstructionFirstTry {\n", " Inc,\n", " Dec,\n", " Left,\n", " Right,\n", " Read,\n", " Write,\n", " LoopStart,\n", " LoopEnd\n", "}" ] }, { "cell_type": "markdown", "id": "532274fa-bd80-4d4d-8e00-1d3d77705326", "metadata": {}, "source": [ "This looks pretty much like an `enum` in C/C++, where the values are mostly synonyms for specific integer values.\n", "\n", "However, even though we have not started to implement the parser and the execution engine of the interpreter yet, we can already sense that this definition\n", "* will make parsing easy, because each character in the set `+-<>.,[]` maps to exactly one instruction, but\n", "* leaves the task of finding matching `LoopStart` and `LoopEnd` instructions to the execution engine, which will thus need to be more complex.\n", "\n", "Here we will do it in a different way and parse the source code into an [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree), which makes execution easy, but requires a bit more work in the parsing step. This design choice is often the more sensible one because\n", "* usually, code is executed a lot more often than it is parsed, so it makes sense to move complex and possibly slow operations like loop delimiter matching to the parsing step,\n", "* matching loop delimiters while parsing ensures that we can reject invalid code immediately, i.e., code where the `[` and `]` instructions do not match, and\n", "* we will see later that a lot of the additional parsing complexity can be delegated to powerful libraries, such as [`nom`](https://docs.rs/nom/latest/nom/).\n", "\n", "How can we implement an abstract syntax tree for Brainfuck in Rust?\n", "\n", "It turns out that Rust's `enum`s can do more than just model integer constants: each *variant* of the `enum` can hold additional data, so we can define an instruction `Loop` that contains a `Vec` with the instructions in the loop body:" ] }, { "cell_type": "code", "execution_count": 15, "id": "d4a8baec-87d4-454f-9eed-daaca07a0db4", "metadata": {}, "outputs": [], "source": [ "#[derive(Debug)]\n", "enum Instruction {\n", " Inc,\n", " Dec,\n", " Left,\n", " Right,\n", " Read,\n", " Write,\n", " Loop(Vec)\n", "}" ] }, { "cell_type": "markdown", "id": "5ed50ab8-0053-4fdb-b1c9-90d4bd5580a6", "metadata": {}, "source": [ "In fact, Rust's `enum`s are [algebraic data types](https://en.wikipedia.org/wiki/Algebraic_data_type) which were pioneered by functional programming languages like Haskell. In principle, C++ has [`std::variant`](https://en.cppreference.com/w/cpp/utility/variant), which does have similar functionality. However, unlike C++, Haskell and Rust provide pattern matching,[5](#fn:cpp-variant-pattern-matching) which is a very powerful and convenient way to interact with these data types with very little code, as we will se in the next post in this series." ] }, { "cell_type": "markdown", "id": "ffe8f9d5-bcb1-40f3-bd96-b3a3c6427efd", "metadata": {}, "source": [ "To use an `Instruction` variant, we have to prefix its name with `Instruction::`:" ] }, { "cell_type": "code", "execution_count": 16, "id": "cf3fdcf5-bd89-4971-b6e8-9ba42b47c62d", "metadata": {}, "outputs": [], "source": [ "let myInstruction = Instruction::Inc;" ] }, { "cell_type": "markdown", "id": "fbc86aa2-1b71-4559-9bd1-a095e8918db6", "metadata": {}, "source": [ "Often it is more convenient if we can omit the `Instruction::` prefix. This can be achieved in this way:" ] }, { "cell_type": "code", "execution_count": 17, "id": "1fbc248c-56d1-4bec-ad62-9a5f510bb827", "metadata": {}, "outputs": [], "source": [ "use Instruction::*;" ] }, { "cell_type": "markdown", "id": "efca50e0-ceb9-4552-b720-9d70e3b59163", "metadata": {}, "source": [ "This is a valid loop instruction:" ] }, { "cell_type": "code", "execution_count": 18, "id": "8879d35c-9663-4e43-84c9-f03b880f3b30", "metadata": {}, "outputs": [], "source": [ "let loopInstruction = Loop(vec![Dec, Right, Inc, Left]);" ] }, { "cell_type": "markdown", "id": "30c4f055-95b4-479d-8be9-eb00063ccce5", "metadata": {}, "source": [ "And this is a full Brainfuck program that reads a byte, and then writes all numbers between 1 and the input byte:" ] }, { "cell_type": "code", "execution_count": 19, "id": "4c9bec31-c8fd-4d16-8da8-d5119b4624b2", "metadata": {}, "outputs": [], "source": [ "let program = vec![Right, Inc, Left, Read, Loop(vec![Right, Write, Inc, Left, Dec])];" ] }, { "cell_type": "markdown", "id": "f58fefb3-327b-4600-9826-c297b65ea1ce", "metadata": {}, "source": [ "Since `Instruction` implements the `Debug` trait, we can also print the program easily:" ] }, { "cell_type": "code", "execution_count": 20, "id": "5be18bbb-70ba-433e-a2b4-87ef4fa134a1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Right, Inc, Left, Read, Loop([Right, Write, Inc, Left, Dec])]" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "program" ] }, { "cell_type": "markdown", "id": "5d15089f-24c7-4ec9-8df0-070c5080a1b7", "metadata": {}, "source": [ "Outside a Jupyter notebook, we would do this with the `println!` macro:" ] }, { "cell_type": "code", "execution_count": 21, "id": "5567124b-1f79-440d-9a9d-b4f9876252e3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[Right, Inc, Left, Read, Loop([Right, Write, Inc, Left, Dec])]\n" ] } ], "source": [ "println!(\"{:?}\", program);" ] }, { "cell_type": "markdown", "id": "41ae8dda-4a23-468c-abf3-a982a228ef55", "metadata": {}, "source": [ "Note that the format specifier '`:?`' inside the braces tells that the automatically implemented `Debug` trait shall be used to print the value. The instruction\n", "```rust\n", "println!(\"{}\", program)\n", "```\n", "would work only if we implemented the `Display` trait for `Instruction`. Then we would have to write some code, but we would be free to choose what a printed instruction should look like.\n", "\n", "There is also a pretty-printing option for types that implement `Debug`, which makes the tree structure of a Brainfuck program clearer:" ] }, { "cell_type": "code", "execution_count": 22, "id": "4ca31b81-4b53-4fad-8835-34beeef414b0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[\n", " Right,\n", " Inc,\n", " Left,\n", " Read,\n", " Loop(\n", " [\n", " Right,\n", " Write,\n", " Inc,\n", " Left,\n", " Dec,\n", " ],\n", " ),\n", "]\n" ] } ], "source": [ "println!(\"{:#?}\", program);" ] }, { "cell_type": "markdown", "id": "c46d91e8-3425-4a45-b11f-9448030f0076", "metadata": {}, "source": [ "## Summary and outlook\n", "We have modeled a tape for our Brainfuck interpreter with a `struct` and implemented the operations that we need. Then we used an `enum` to model Brainfuck instructions as an abstract syntax tree.\n", "\n", "In the next post in this series, we will use these building blocks to implement an execution engine that applies the instructions to the state of the tape.\n", "\n", "---\n", "\n", "1. It is the programmer's responsibility to avoid the following in C and C++, and compilers can only provide very limited help with that:\n", " * reading and writing out of the bounds of an array, an `std::vector`, or similar data structures,\n", " * dereferencing dangling pointers (or references), i.e., pointers that point to data that are not valid any more,\n", " * reading and writing data from different threads at the same time,\n", " * and much more, such as incrementing an `int` that holds the value 2147483647 a.k.a `INT_MAX` by one, or [dereferencing a null pointer, even if the value is never used and the dereference is optimized away completely](https://lwn.net/Articles/342330/).\n", " \n", " All these cause [undefined bahaviour](https://en.cppreference.com/w/c/language/behavior), which means that basically anything can happen. The application might work as the developer expected, or it could yield incorrect results, or it could crash, or it could have a critical security vulnerability. Which of these you get can change at any time, e.g., when changing the optimization level or other compiler options, upgrading to a new compiler version, or modifying something in a different part of the code base.\n", "\n", " A blog series that Chris Lattner wrote in 2011 on undefined behaviour ([part 1](http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html), [part 2](https://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html), [part 3](https://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html)) should still be mandatory reading for anyone who writes code in C and C++.[↩](#fnref:undefined-behavior)\n", "\n", "1. Note how Rust integer types make their bit width and their signedness explicit:\n", "\n", " * signed integer types are `i8`, `i16`, `i32`, `i64`, `i128`, and `isize`,\n", " * unsigned integer types are `u8`, `u16`, `u32`, `u64`, `u128`, and `usize`.\n", "\n", " The size of `isize` and `usize` depends on the platform: 32 bits on 32-bit systems, and 64 bits on 64-bit systems. They correspond to `size_t` and `ssize_t` in C.[↩](#fnref:integers)\n", "\n", "1. Note that `self` must be stated explicitly as a function parameter, and that access to struct members must also be qualified with `self.`, just like in some other languages like, e.g., Python.[↩](#fnref:self)\n", "\n", "1. Note that the cell output is the final expression without trailing semicolon in the cell. This corresponds to the fact that functions return the final expression without trailing semicolon if there is no return statement.[↩](#fnref:cell-final-expression)\n", "\n", "1. One could argue that [`std::visit`](https://en.cppreference.com/w/cpp/utility/variant/visit) can be used as a workaround for pattern matching in C++. This is true, but using it feels more cumbersome and requires more code than proper pattern matching. There is a [library](https://github.com/mpark/patterns) which adds pattern matching to C++ and which might evolve into something that will be added to the C++ standard. Compared to pattern matching in, e.g., Haskell and Rust, it still feels a bit unwieldy though.[↩](#fnref:cpp-variant-pattern-matching)" ] } ], "metadata": { "kernelspec": { "display_name": "Rust", "language": "rust", "name": "rust" }, "language_info": { "codemirror_mode": "rust", "file_extension": ".rs", "mimetype": "text/rust", "name": "Rust", "pygment_lexer": "rust", "version": "" }, "nikola": { "date": "2024-02-04 21:23:02 UTC", "slug": "../../blog/2024/02/04/brainfuck-interpreter-in-rust-part1", "tags": "rust", "title": "Learn Rust by building a Brainfuck interpreter, part 1: implement the tape and model the program as an abstract syntax tree" } }, "nbformat": 4, "nbformat_minor": 5 }