Използване на Option като итератор

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Въпрос за графоподобна структура

  1. Здравейте!
    Моля за малко помощ/съвети. :)

    Играя си с IR на език за програмиране в Rust структури и се опитвам да задоволя borrow checker-а. Имам следния набор от структури, с ненужните части изтрити за прегледност:

    struct Runtime<'a> {
    functions: HashMap<String, Function<'a>>
}

struct Function<'a> {
    scope: Scope<'a>,
    code: Block<'a>
}

struct Scope<'a> {
    runtime: &'a Runtime<'a>,
    vars: HashMap<String, Variable>
}

struct Variable {
    name: String
    // + other metadata
}

pub enum Instruction<'a> {
    // Literal(ConstValue),
    VariableRef(&'a Variable),
    // Call(Call<'a>),
    Block(Block<'a>)
}

struct Block<'a> {
    code: Vec<Instruction<'a>>
}

impl<'a> Function<'a> {
    pub fn build(ast: &'a parser::MethodDefAST, runtime: &'a Runtime<'a>) -> Function<'a> {
        // Тук се проявяват проблемите
    }
}

impl<'a> Instruction<'a> {
    pub fn build(ast: &'a AST, scope: &'a Scope<'a>) -> Instruction<'a> {
        // Това конструира Instruction обект, евентуално реферирайки променливи от scope-а
    }
}

    Идеята е следната:

    • Runtime държи всичко - трябва да е owner на всичко по транзитивност.
    • Function описва функция, съответно има scope за локални променливи вътре + код, който трябва да се изпълни.
    • Scope е owner на променливите и му трябва референция към Runtime, за да може да търси функции.
    • Variable не е само име, има други неща вътре, съответно не мога да го приравня към String. Идеята е ако някъде се иска променлива, то тя да се специфицира с референцията към Variable, не само с име. Това е така, защото името може да не е уникално и зависи от scope-а.
    • Instruction е нещо, което може да реферира променливи.

    Проблемите са основно с цикличните зависимости:

    • Runtime държи функции, но функциите имат scope, който реферира Runtime.
    • Функцията държи scope, но и код, който може да реферира променливи от този scope. Като резултат, няма как да конструирам Function обект, защото трябва да взема scope от вече конструирания, за да го реферирам от code.

    Може ли съвет как да променя структурите, така че borrow checker-а да е доволен?

    Четох, че може да се използва Rc<RefCell<T>> в подобни ситуации:

    1. Добра идея ли е това в случая?
    2. Губя ли compile-time проверките, че докато имам Function ще е жив и Runtime-а? Тоест, мога ли да запазя текущите lifetime връзки, или някоя от тях поражда проблемите?
    3. Навсякъде ли е нужно да минава през Rc<RefCell<T>> или има начин да се реферират по този начин само при връзките отдолу-нагоре?
    4. Ако направя Scope и Variable RC-та мисля, че няма да има циклични зависимости между RC обектите (тоест няма да тече памет). Има ли нещо, което пропускам?

    Има ли нещо по-добро от Rc<RefCell<T>> в случая?

    Благодаря предварително :)

  2. За графо-подобни структури при които имаш едно нещо сочено от повече от едно друго нещо - Rc. Ако искаш и да си подаваш стойностите и да ги четеш/променяш лесно - Rc<RefCell>. Та да, идеята е добра. Сега за твоят случай, виждал съм различни импелемтации на различни интерпретатори на Rust, за структура подобна на твоя Runtime (по-често го кръщават Environment поради някава причина) хората си използват Rc<RefCell<T>>.

    Ако не използваш Weak референции, докато имаш Function със scope, която сочи към Runtime, ще си е жив. Използвай Rc<RefCell> само в случаите, когато към едно нещо могат да сочат много неща.

    Сигурно пропускаме нещо, но ако не почне да се имплементира/тества няма как да знаем. Много добра идея си започнал и с интерес ще следя развитието ѝ.

    Може би това, което прави Дельо, ще ти е от помощ: https://github.com/d3lio/lexpar Или пък https://github.com/Geal/nom

  3. Както каза Медъла, трудно е да се прецени, преди да се види някаква по-пълна имплементация на това нещо. Той самия си играе с някви лиспове, така че сигурно е виждАл поне няколко имплементации на подобни неща :). Но е много на проба-грешка, според мен.

    Моите 2 евроцента -- Runtime ми мирише на глобален singleton. Което не че е лошо, просто се чудя дали не може да се прокара "таблицата с функции" като параметър на каквито процедури обработват дървото. Т.е. ако ще пускаш някакъв интерпретатор, вместо да държиш връзки между "обектите" и глобалния Runtime, може да го подаваш като аргумент на evaluator-а. Имай предвид, че досега не съм писал интерпретатор, така че може и просто да ми се губи нещо в разбирането. Take it with a grain of salt, basically.

    Иначе да, ако ти трябва да го държиш, Rc<RefCell<Runtime>> би ти дал споделена собственост и мутабилност. Може все пак да обмислиш, вместо това, един гол, unsafe pointer, от Scope към Runtime. Предвид, че няма да сменяш runtime-а на един scope в движение (мисля?), и само ти трябва да можеш да го достъпиш и да му викаш методи, вероятно няма да е твърде рисковано. Не помня дали присъстваше на тези лекции, но ето една добра статия, която показва подобен подход: http://cglab.ca/~abeinges/blah/too-many-lists/book/fifth-basics.html

  4. Благодаря за съветите, ще пробвам Rc, евентуално с RefCell. Гол pointer ми се струва малко гадно, ще взема да го забравя някъде :)

    Идеята е това после да мине към LLVM с https://bitbucket.org/tari/llvm-sys.rs/ , вместо да се интерпретира директно. Runtime ми трябва, за да държа глобалното състояние на програмата - основно класове и функции - на практика е таблицата с функции :)

  5. Не знам за LLVM, когато си правиш някакъв прост toy интерпретатор. За learning цели си струва, предполагам. Иначе аз си правя прост scheme интерпретатор в момента и имам този код за Runtime структура:

    use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

use interpreter::value::Value;

macro_rules! runtime_node(
    ($($val:tt)*) => (Rc::new(RefCell::new($($val)*)))
);

pub type RuntimeNode = Rc<RefCell<Runtime>>;
pub struct Runtime {
    parent: Option<RuntimeNode>,
    values: HashMap<String, Value>
}

impl Runtime {
    pub fn new() -> RuntimeNode {
        runtime_node!(Runtime { parent: None, values: HashMap::new() })
    }

    pub fn new_scope(parent: RuntimeNode) -> RuntimeNode {
        runtime_node!(Runtime { parent: Some(parent), values: HashMap::new() })
    }

    pub fn set_var_value(&mut self, key: String, value: Value) {
        self.values.insert(key, value);
    }

    pub fn is_var_defined(&self, key: &String) -> bool {
        self.values.contains_key(key)
    }

    pub fn get_var_value(&self, key: &String) -> Option<Value> {
        if let Some(val) = self.values.get(key) {
            Some(val.clone())
        } else {
            if let Some(ref parent) = self.parent {
                parent.borrow().get_var_value(key)
            } else { None }
        }
    }
}

    Value структурката ми в момента е:

    pub enum Value {
    Symbol(String),
    Integer(isize),
    Boolean(bool),
    StringValue(String),
    List(Vec<Value>),
    Func(Vec<String>, Vec<ASTNode>),
}

    Слагам го просто за сравнение, сигурно ще го променям в движение, спрямо потребностите ми. Трябва да видя как да го пазя като стигна до repl-а, не искам да е глобален state...

  6. Това е много полезно, благодаря! pub type е доста добра идея.
    Каква е причината runtime_node! да е макрос, а не функция?

    Правил съм интерпретатор няколко пъти вече с други езици и ми се искаше да поекспериментирам с компилатор най-накрая. Този конкретен език го почвам вече сигурно за 8ми път, 3 от които в C++, 1 в Ruby и останалите в Java, все отказвайки се някъде по пътя. :D Последния път в C++ три дни се опитвах да подкарам ICU за unicode string-ове и ми свърши търпението...

    Засега в Rust ми харесва най-много как се получават нещата, а лесната връзка със C е голям плюс.

  7. Никаква специална причина да е макро, играя си с макрота просто :) Не, че в случая нещо помага.

    Иначе за компилатор... Мен ми е интересна идеята да си направи човек абстрактна машина която си има собствена имплементация на heap/stack, garbage collection, и има собствен bytecode формат, но не съм стигнал до там.

    За LLVM, не знам, ще ми е интересно да видя някакъв прост frontend към LLVM на Rust.

  8. LLVM е много приятен таргет за компилатор, и е доста практичен за опит, ако човек иска да допринася към редица съществуващи open source езици.

    Във връзка с вашата дискусия, се чудех дали са ви попадали проекти, генериращи директно Rust код? Не е много лесен език за тази цел, но за ограничени dsl-и или прототипи, които поддържат подобни memory гаранции, може да е полезен таргет.

  9. Хм, имаш предвид езици, които да се транспилират до Rust? Не знам за такива, ако не друго, доста е млад още езика. Подобни ситуации май обикновено се получават със стари езици, които хората не харесват, ама имат полезни качества :). Rust не е стар, и е харесван!

    Иначе, ако просто говориш за писане на DSL-и, обикновено това се прави с макроси. Има и нещо, което се казва procedural macros, което ти дава възможност програмно да боравиш с AST-то на някакъв код, така че може би за нещо такова си мислиш?

Трябва да сте влезли в системата, за да може да отговаряте на теми.