A Tour of Rust - Binary Search Tree

学习Rust已经有一段时间了，最近开始尝试用 Rust 进行一些简单的demo开发进行练手。今天尝试了一下，实现了第一个简单的 Binary Search Tree。必须承认，Rust 的入门曲线确实相当陡峭。本来我的预计是花费2~3小时实现，结果最后花了整整6个小时，比预计的时间超出一倍多。这里记录一下自己的学习心得以及体会。

代码实现

在实现代码的过程中，我使用了两种不同的开发思路：

1. 基于传统的命令式编程语言，使用语言提供的各种控制流语句（如 if, while）来控制逻辑；
2. 基于Rust强大额模式匹配控制逻辑；

act

---
title: act
---
flowchart LR

counter:::prefix
over:::prefix

act:::root

counter --> act --> counteract

counteract --> Counteraction
counteract --> Counteractive
counteract --> Counteractively
counteract --> Counteractant

over --> act --> overact

overact --> Overaction
overact --> Overactivity
overact --> Overacting
overact --> Overactor
overact --> Overacted
overact --> Overactively

classDef root 1,fill:#FFCCCC,stroke:#333;
classDef suffix fill:#969,stroke:#333;
classDef prefix fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5
classDef header fill: #696,color: #fff,font-weight: bold,padding: 10px;

词根/词缀

1. 前缀和词根共同决定单词的意思；
2. 词性由后缀决定；

描述

flowchart TD

subgraph word-form
    direction TB
    col:::prefix
    labor:::front
    ate:::suffix
end

subgraph form
    direction TB
    前缀
    词根
    后缀
end

subgraph descption
    direction TB
    词义
    词性
end

subgraph word-explanation
    direction TB
    一起
    劳动
    动词
end

前缀 --> col
词根 --> labor
后缀 --> ate

col --> 一起:::prefix
labor --> 劳动:::front
ate --> 动词:::suffix

词义 --> 前缀
词性 --> 后缀


word-explanation --> collaborate:::back

classDef back fill:#969,stroke:#333;
classDef front 1,fill:#FFCCCC,stroke:#333;
classDef prefix fill:#90ee90,stroke:#333,stroke-width:4px;
classDef suffix fill:#ff6347,stroke:#333,stroke-width:4px;

前缀

Draw Diagrams in Markdown

I have always been a enthusiast for diagrams because I believe illustrations are a more direct and efficient way to elucidate the truths we want to explore. Meanwhile, I don't need a heavy diagraming tool like PowerPoint. I prefer to a lightweight, cross-platform,easy-to-using tool that can be seamlessly integerated with markdown, and here are several tools build for markdown that I find useful:

• js-sequence-diagrams
• flowchart.js
• mermaid

If you are interested in any one of these tools, just read the tutorial to get started on your journey.

Most Useful Diagrams in Mermaid

A Simple Conclusion for Ownership in Rust

Warm Up

What's my type?

Before we divi into the ownership, there is a essential problem we have to figure out beforehead: What's the type of the variable we just define? Considering the following code snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fn what_is_my_type() {
    let mut num0 = 0;

    let first_value: &mut i32 = &mut num0;
    println!("{first_value}");
    let second_value: &i32 = &mut num0;
    println!("{second_value}");

    let mut third_value: &mut i32 = &mut num0;
    println!("{third_value}");
    let mut fourth_value: &i32 = &mut num0;
    println!("{fourth_value}");

    let &mut fifth_value: &mut i32 = &mut num0;
    let &mut sixth_value = &mut num0;
}

The Crate Package and Moudle in Rust

References

Defining Modules to Control Scope and Privacy

test rust crate

Declaring modules

Strategies of Evaluate Infix Operator

when we are implementing a compiler, there is always a difficult problem we will encounter.

How can we evaluate an infix operator?

What is Infix Operator

An infix operator is an operator placed between two expressions, like minus, plus, asterisk, slash and so forth. Here are some common infix operator:

Strategies of Evaluation

Evaluation is where interpreter implementations diverge the most.There are a lot of different strategies to choose from when evaluating source code.so looking at different options is worthwhile.

Before we start, though, it's also worthy noting again that the line between interpreter and compiler is a blurry one.

tree-walking interpreter

the most obvious and classical choice of what to do with the AST is to just interpret it. Traverse the AST,visit each node and do what the node signifies: print a string,add two number, execute a function's body.Sometimes their evaluation is preceded by small optimization that rewrite the AST(e.g. remove unused variable bindings) or convert it into another intermediate representation(IR) that's more suitable for recursive and repeated evaluation.

使用本文记录学习 Pratt Parser 的过程，全部代码实现基于 go version go1.20.14 darwin/arm64 实现，代码地址位于：0x822a5b87/test-pratt-parsing

什么是 Pratt Parser

在语法解析器（Parser）的工作过程中，我们通常会将一个字符串转换为一个抽象语法树（Abstract Syntax Tree）：

---
title: The workflow of Paser
---
flowchart LR
    Input["0 + 1 + 2! * -3"] -->|Parser| AST
    
    subgraph AST
        Add --> Add2[Add]
        Add2 --> 0
        Add2 --> 1
        Add --> Mul
        Mul --> ! --> 2w
        Mul --> - --> 3
    end

在这个解析过程中，我们会碰到许多问题：

前言

今天，有个朋友突然问了我一个问题，为什么在以下代码中会发生以下这种情况呢？

1. secretId == "" 可以正常的进行比较；
2. printString(secretId) 会提示类型不匹配；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import "fmt"

type Password string

func printString(str string) {
	fmt.Println(str)
}

func testPrint() {
	var secretId Password = "0"

	// 这里不会报错
	if secretId == "" {
		fmt.Println(secretId)
	}

	// Cannot use 'secretId' (type Password) as the type string
	printString(secretId)
}

看到这个问题我的第一反应是由于 类型推导（Type inference），"" 被直接推导为 Password 类型，所以可以直接和 secretId 对象进行比较。可惜的是，在 golang 反编译的代码中已经丢失了类型信息，所以只能慢慢探索了。