Listy a return
V minulém článku jsme přidali Garbage Collector. Ten nám umožní v do paměti ukládat reference na ostatní paměť, což je potřeba pro ukládání listů a objektů.
Listy
Nejdříve přidáme listy. Budeme chtít zfunkčnit následující kód:
let array = [1,2,print];
let second = array[1];
array[array[0]] = 3;
array[2](second); // print 2
Náš list bude umět ukládat různorodé typy, indexovat ze spočítaných hodnot a ukládat hodnoty později.
Lexer a TokenStream již správně pracují s ruznými druhy závorek, naše úpravy proto budou jen v parseru a executoru.
Definice je obdoba závorky (val) ve formátu [1,2,3]. Rozdělení přes , je stejné jako u argumentů, a proto zde budou minimální změny kódu parseru (krom typů).
Indexace je zase obdoba volání funkce thing(1,2,3) ve formátu thing[1]. Zde naopak nebudeme rozdělovat přes ,.
Definice
V parseru přidáme nový typ Array pro uložení listu Expression.
#[derive(Debug)]
pub struct Array {
pub values: Vec<Expression>
}
#[derive(Debug)]
pub enum Expression {
Identifier(String),
String(String),
Number(i64),
Operation(Operation),
FunctionCall(FunctionCall),
Array(Array)
}A ve funkci parse_simple_value přidáme kód pro zpracování []:
pub fn parse_simple_value(mut tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
if let Some(token) = tt.next() {
match token {
TokenTree::Identifier(ident) => {
Some(Expression::Identifier(ident))
},
TokenTree::String(string) => {
Some(Expression::String(string))
},
TokenTree::Number(num) => {
Some(Expression::Number(num))
},
TokenTree::Group { mode, tokens } => {
match mode {
GroupMode::Parens => {
parse_expr(tokens)
},
GroupMode::Bracket => {
Expression::Array(Array {
values: parse_args(tokens)
}).into()
}
_ => panic!("unexpected group mode in value\n: {:?}", mode)
}
},
token => panic!("unexpected token in value: {:?}", token)
}
} else { None }
}To je z parseru pro definici arrayu vše - hezky jsme si připravili kód minule a tak je jednoduché přidávat tyto konstrukty později. V modulu exec přidáme do HeapType Array
#[derive(Debug, Trace, Finalize)]
pub enum HeapType {
Function(Function),
Array(Vec<Type>)
}A patřičně upravíme ToString implementaci. V naši implementaci spojíme jednotlivé hodnoty , a to celé vložíme do []. Můžeme na to použít format! macro, které funguje obdobně jako print!, jen vrací String místo aby text vypsal do výstupu. Poté jen základní iterator metody - map a join.
impl ToString for Type {
fn to_string(&self) -> String {
match self {
Type::Number(num) => num.to_string(),
Type::String(string) => string.clone(),
Type::Void => "void".to_string(),
Type::Heap(heap) => match heap.0.as_ref().borrow().deref() {
HeapType::Function(func) => match func {
Function::Native(native) => format!("<native function {}>", native.name),
Function::UserDefined(defined) => format!("<user defined function {}>", defined.def.ident)
},
HeapType::Array(array) => {
format!("[{}]", array.iter().map(|t| t.to_string()).join(", "))
}
}
}
}
}Nakonec zaimplementujeme převod z AST do Type při evaluaci Array definice, obdobně jako to má číslo či string.
impl Exec for Expression {
fn exec(&self, ctx: &mut Context) -> Type {
if ctx.returning.is_some() {
return Type::Void;
}
match self {
Expression::Number(num) => Type::Number(*num),
Expression::String(string) => Type::String(string.clone()),
Expression::Identifier(ident) => ctx.get(ident).expect("variable not found"),
Expression::Operation(op) => op.exec(ctx),
Expression::FunctionCall(call) => call.exec(ctx),
Expression::Array(array) => array.exec(ctx),
}
}
}
impl Exec for Array {
fn exec(&self, ctx: &mut Context) -> Type {
Type::Heap(HeapCell::new(HeapType::Array(self.values.iter().map(|v| v.exec(ctx)).collect())))
}
} To by mělo být vše potřebné pro to, aby se kód opět zkompiloval a uměl zpracovat definice listu. Například:
print([1,2]);
let a = ["world", "!"];
print("hello " + a); // hello world!Indexace
Přidáme nový typ Index, který bude obdobou FunctionCall:
#[derive(Debug)]
pub struct FunctionCall {
pub func: Box<Expression>,
pub args: Vec<Expression>
}
#[derive(Debug)]
pub struct Index {
pub value: Box<Expression>,
pub index: Box<Expression>
} A upravíme Expression enum:
#[derive(Debug)]
pub enum Expression {
Identifier(String),
String(String),
Number(i64),
Operation(Operation),
FunctionCall(FunctionCall),
Array(Array),
Index(Index),
}Nakonec pouze upravíme parse_fn_call aby místo jednoduchého ifu měl další match a rozparzoval na Index nebo FunctionCall podle "mode":
pub fn parse_fn_call(mut tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
let first = tt.next().unwrap();
let mut value = parse_op_dot([first].into_iter());
if value.is_some() {
while let Some(token) = tt.next() {
match token {
TokenTree::Group { mode, tokens } if mode == GroupMode::Parens => {
value = Some(Expression::FunctionCall(FunctionCall {
func: Box::new(value.unwrap()),
args: parse_args(tokens)
}))
},
TokenTree::Group { mode, tokens } => {
match mode {
GroupMode::Parens => {
value = Some(Expression::FunctionCall(FunctionCall {
func: Box::new(value.unwrap()),
args: parse_args(tokens)
}))
},
GroupMode::Bracket => {
value = Some(Expression::Index(Index {
value: Box::new(value.unwrap()),
index: Box::new(parse_expr(tokens).expect("expected index"))
}))
},
GroupMode::Curly => {
panic!("unexpected curly tokens after value")
}
}
},
token => panic!("unexpected tokens in value (call): {:?}", token)
}
}
}
value
}To by opět bylo vše z parseru. V exekutoru však musíme řešit dvě situace - získávání hodnoty a nastavení hodnoty.
Získávání hodnoty
Přidáme směrování Exec traity:
impl Exec for Expression {
fn exec(&self, ctx: &mut Context) -> Type {
if ctx.returning.is_some() {
return Type::Void;
}
match self {
Expression::Number(num) => Type::Number(*num),
Expression::String(string) => Type::String(string.clone()),
Expression::Identifier(ident) => ctx.get(ident).expect("variable not found"),
Expression::Operation(op) => op.exec(ctx),
Expression::FunctionCall(call) => call.exec(ctx),
Expression::Array(array) => array.exec(ctx),
Expression::Index(index) => index.exec(ctx),
}
}
}Dále zaimplementujeme Exec pro Index.
Zkontrolujeme, že hodnota vlevo je Array (tedy Heap(HeapCell(Array))), a hodnota uvnitř závorek je číslo, a poté zaindexujeme array.
impl Exec for Index {
fn exec(&self, ctx: &mut Context) -> Type {
let array = self.value.exec(ctx);
let Type::Heap(HeapCell(ptr)) = &array else {
panic!("expected array in index expression")
};
let borrow = ptr.borrow();
let HeapType::Array(array) = borrow.deref() else {
panic!("expected array in index expression")
};
let index = self.index.exec(ctx);
let index = match index {
Type::Number(num) => num as usize,
_ => panic!("expected number as index")
};
array[index].clone()
}
}Zde nutno podotknout že je lze více možnost panic než jen těch explicitní, je tu jeden z mála implicitních rust paniců. Indexace v rustu je vždy kontrolována pro existenci prvku, i.e. že list je dost dlouhý. Například [1][2] by crashnul na posledním řádku této funkce, jelikož v arrayi [1] není třetí prvek.
Protože nemáme pořádný handling chyb, máme v podstatě dve varianty - crashnout, i když třeba s lepší chybovou hláškou, nebo vrátit Void. Rozhodneme-li se pro vrácení Void, může výsledný kód vypadat například takto:
impl Exec for Index {
fn exec(&self, ctx: &mut Context) -> Type {
let array = self.value.exec(ctx);
let Type::Heap(HeapCell(ptr)) = &array else {
panic!("expected array in index expression")
};
let borrow = ptr.borrow();
let HeapType::Array(array) = borrow.deref() else {
panic!("expected array in index expression")
};
let index = self.index.exec(ctx);
let index = match index {
Type::Number(num) => num as usize,
_ => panic!("expected number as index")
};
if index >= array.len() {
Type::Void
} else {
array[index].clone()
}
}
}Tím by měl fungovat kód
let a = [1, 2];
print(a[1]);Nastavení hodnoty
Nakonec nám už stačí pouze případ nastavení hodnoty, tedy a[0] = 1 a podobně.
= je Operation s op = Op::Equal.
impl Exec for Operation {
fn exec(&self, ctx: &mut Context) -> Type {
let left = self.left.exec(ctx);
let right = self.right.exec(ctx);
match self.op {
Op::Plus => left + right,
Op::Minus => left - right,
Op::Multiply => left * right,
Op::Division => left / right,
Op::EqualTo => (left == right).into(),
Op::NotEqual => (left != right).into(),
Op::LessThan => (left < right).into(),
Op::GreaterThan => (left > right).into(),
Op::Equal => {
let left = self.left.as_ref();
match left {
Expression::Identifier(ident) => {
if !ctx.update(ident.clone(), right.clone()) {
panic!("variable not found: {}", ident);
}
right
},
Expression::Index(index) => {
let array = index.value.exec(ctx);
let Type::Heap(HeapCell(ptr)) = &array else {
panic!("expected array in index expression")
};
let mut borrow = ptr.borrow_mut();
let HeapType::Array(array) = borrow.deref_mut() else {
panic!("expected array in index expression")
};
let index = index.index.exec(ctx);
let index = match index {
Type::Number(num) => num as usize,
_ => panic!("expected number as index")
};
array[index] = right.clone();
array[index].clone()
},
_ => panic!("expected identifier or array index on left side of equal operator")
}
},
Op::Dot => todo!(),
}
}
}Return
Z minulé části si pamatujete že není zcela jednoduché vracet hodnotu - náš jazyk momentálně nemá return.
Ten je, obdobně jako listy, primárně úkolem pro exekutor. Lexer již umí jednoslovné keywordy, tam je úprava na dva řádky. A náš return bude mít formát return [expression];, tedy keyword return a možnost specifikovat hodnotu přes expression. Parsování expression již parser umí, a tak i tam bude úprava na pár řádků.
V exekutoru budeme však muset řešit zrušení spouštění kódu než se kód "vrátí".
Přidání slova
Je potřeba přidat nový keyword Return do enum Token:
#[derive(Debug)]
pub enum Token {
Let,
If,
While,
Function,
Return,
Comma, // ,
Colon, // :
SemiColon, // ;
ParensOpen, // (
ParensClose, // )
CurlyOpen, // {
CurlyClose, // }
BracketOpen, // [
BracketClose, // ]
Identifier(String),
String(String),
Number(i64),
Op(Op)
}Dále se return přidá do stejné části jako ostatní keywordy.
impl Iterator for LexerCursor<'_> {
type Item = Token;
fn next(&mut self) -> Option<Self::Item> {
self.eat_while(|c| c.is_ascii_whitespace());
let pos = self.pos();
let c = self.bump()?;
match c {
// ...
'a'..='z' | 'A'..='Z' | '_' => {
self.eat_while(|c| c.is_alphanumeric() || c == '_');
let ident = &self.str[pos..self.pos()];
match ident {
"let" => Some(Token::Let),
"if" => Some(Token::If),
"while" => Some(Token::While),
"function" => Some(Token::Function),
"return" => Some(Token::Return),
_ => Some(Token::Identifier(ident.to_string()))
}
},
}
}
}Parser
return může ale nemusí vracet hodnotu. V AST tudíž bude obsahovat Option<Expression>.
#[derive(Debug)]
pub enum Statement {
Let(LetDefinition),
Function(Rc<FunctionDefinition>),
If(IfStatement),
While(WhileStatement),
Return(Option<Expression>),
Block(Vec<Statement>),
Value(Expression)
}Přečteme všechny hodnoty do příštího středníku a ty rozparzujeme jako expression.
První value je impl Iterator<Item = TokenTree> - jedná se o iterátor, nikoliv o array, a funkce nealokuje nový array, místo toho akorát omezuje kolik prvků se vrátí z původního streamu. Je proto efektivní ale zároveň čitelné, pracuje se s ním obdobně jako s listem.
fn parse_statement(mut tt: impl Iterator<Item = TokenTree>) -> Option<Statement> {
let statement = match tt.next()? {
// ...
TokenTree::Return => {
let value = tt.take_while(|tt| !matches!(tt, TokenTree::SemiColon));
let value = parse_expr(value);
Statement::Return(value)
},
}
}Executor
Musíme zajistit aby nám správně fungoval například kód
function test() {
return;
print("1");
}
test();
print("2");tedy aby se vypsala pouze číslice 2. Nejjednodušší způsob je přidat nový stav do Context - každá funkce v exec jej již dostává a může s ním pracovat (má na něj mut přístup). Základ je jednoduchý, Return statement jej nastaví a FunctionCall jej přečte, resetuje, a vrátí.
Nejdříve si nadefinujeme novou proměnnou uvnitř Context. Jelikož Type má prázdnou hodnotu, Void, nemusíme řešit stav prázdného return speciálně - nastavená hodnota bude Some(Void).
#[derive(Default)]
pub struct Context {
scopes: Vec<Gc<GcCell<HashMap<String, Type>>>>,
returning: Option<Type>
}Dále ji nastavíme uvnitř Return statement:
impl Exec for Statement {
fn exec(&self, ctx: &mut Context) -> Type {
match self {
Statement::Let(definition) => definition.exec(ctx),
Statement::Value(value) => value.exec(ctx),
Statement::Function(function) => function.exec(ctx),
Statement::If(if_statement) => if_statement.exec(ctx),
Statement::While(while_statement) => while_statement.exec(ctx),
Statement::Return(expr) => {
ctx.returning = Some(expr.as_ref().map(|t| t.exec(ctx)).unwrap_or(Type::Void));
Type::Void
},
Statement::Block(stmts) => {
ctx.add_scope();
stmts.exec(ctx);
ctx.pop_scope();
Type::Void
}
}
}
}A použijeme uvnitř FunctionCall:
impl Exec for FunctionCall {
fn exec(&self, ctx: &mut Context) -> Type {
let func = self.func.exec(ctx);
let args = self.args.iter().map(|arg| arg.exec(ctx)).collect();
match &func {
Type::Heap(HeapCell(ptr)) => match ptr.borrow().deref() {
HeapType::Function(func) => match func {
Function::Native(native) => (native.body.lock().unwrap())(args),
Function::UserDefined(defined) => {
ctx.add_scope();
for ident in defined.def.args.iter() {
ctx.define(ident.clone(), Type::Void);
}
for (ident, value) in defined.def.args.iter().zip(args.iter()) {
ctx.define(ident.clone(), value.clone());
}
ctx.scopes.extend_from_slice(&defined.scopes);
let result = defined.def.body.exec(ctx);
defined.def.body.exec(ctx);
let result = ctx.returning.take().unwrap_or(Type::Void);
ctx.scopes.truncate(ctx.scopes.len() - defined.scopes.len());
ctx.pop_scope();
result
}
},
_ => panic!("expected function in function call")
}
_ => panic!("expected function in function call")
}
}
}take vezme hodnotu Option a nastaví Option na None. Jelikož však není garance že hodnota byla Some, sám vrací Option. Proto se použije unwrap s fallbackem na Void.
Nyní nám naprostý základ bude fungovat, ale bude mít jednu chybu - stále se spustí kód po return. Nemáme totiž jednoduchou možnost jak zrušit spouštění následujícího kódu - v jiných jazycích by se dala použít vyjímka, ale ta přináší neviditelnou změnu toku kódu, které se rust snaží vyvarovat.
Místo toho musíme toto řešení přidat explicitně. Jedna možnost by byla do všech Exec implementací přidat kontrolu že kontext nemá nastavený returning. Alternativa k první možnosti by byla přidat default implementaci do Exec pro kontrolu spustitelnosti která by se volala místo přímé implementace. Avšak dle mého názoru je nejjednodušší a nejčitelnější varianta přidat kontrolu pouze na nutná místa - všechny spouštění kódu se směrují přes Statement nebo Expression, a tudíž stačí přidat kontrolu tam.
impl Exec for Statement {
fn exec(&self, ctx: &mut Context) -> Type {
if ctx.returning.is_some() {
return Type::Void;
}
match self {
Statement::Let(definition) => definition.exec(ctx),
Statement::Value(value) => value.exec(ctx),
Statement::Function(function) => function.exec(ctx),
Statement::If(if_statement) => if_statement.exec(ctx),
Statement::While(while_statement) => while_statement.exec(ctx),
Statement::Return(expr) => {
ctx.returning = Some(expr.as_ref().map(|t| t.exec(ctx)).unwrap_or(Type::Void));
Type::Void
},
Statement::Block(stmts) => {
ctx.with_scope(|ctx| stmts.exec(ctx));
Type::Void
}
}
}
}
impl Exec for Expression {
fn exec(&self, ctx: &mut Context) -> Type {
if ctx.returning.is_some() {
return Type::Void;
}
match self {
Expression::Number(num) => Type::Number(*num),
Expression::String(string) => Type::String(string.clone()),
Expression::Identifier(ident) => ctx.get(ident).expect("variable not found"),
Expression::Operation(op) => op.exec(ctx),
Expression::FunctionCall(call) => call.exec(ctx),
Expression::Array(array) => array.exec(ctx),
Expression::Index(index) => index.exec(ctx),
}
}
}Mimochodem - i Expression se směruje přes Statement (Statement::Value) a tak by kontrola stačila i tam. Takto to je pouze robustnější do budoucnosti.
Zakončení
V tomto cyklu jsme si ukázali základy programovacího jazyka a základy implementace interpretovaného jazyka. Ukázali jsme si, které chyby rust řeší, a které je naopak nutné řešit manuálně i nadále.
Náš jazyk je sice malý, ale stačí již na základní programy a scriptování, a ukázali jsme si i jak ho rozšířit o novou funkcionalitu či abstrakce.
Funkcionalita většiny programovacích jazyků je pouze nadstavba nad těmito základy. Například for loop se dá naimplementovat takto:
let array = [1,2,3];
let index = 0;
while(index < 3) {
print(array[index]);
index = index + 1;
}Zde akorát se může přidat syntaxe navíc, například možnost definovat index přímo uvnitř for loopy (for(let index = 0; index < 3; index = index + 1))) či možnost přičíst a uložit v jednom kroku, například index += 1;.