<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Evaluator - Lisp interpreter in Rust</title>
<!-- Custom HTML head -->
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff" />
<link rel="icon" href="favicon.svg">
<link rel="shortcut icon" href="favicon.png">
<link rel="stylesheet" href="css/variables.css">
<link rel="stylesheet" href="css/general.css">
<link rel="stylesheet" href="css/chrome.css">
<link rel="stylesheet" href="css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" href="highlight.css">
<link rel="stylesheet" href="tomorrow-night.css">
<link rel="stylesheet" href="ayu-highlight.css">
<!-- Custom theme stylesheets -->
</head>
<body>
<!-- Provide site root to javascript -->
<script type="text/javascript">
var path_to_root = "";
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
</script>
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script type="text/javascript">
try {
var theme = localStorage.getItem('mdbook-theme');
var sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script type="text/javascript">
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('no-js')
html.classList.remove('light')
html.classList.add(theme);
html.classList.add('js');
</script>
<!-- Hide / unhide sidebar before it is displayed -->
<script type="text/javascript">
var html = document.querySelector('html');
var sidebar = 'hidden';
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
}
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<div class="sidebar-scrollbox">
<ol class="chapter"><li class="chapter-item expanded "><a href="overview.html"><strong aria-hidden="true">1.</strong> Overview</a></li><li class="chapter-item expanded "><a href="introduction.html"><strong aria-hidden="true">2.</strong> Introduction</a></li><li class="chapter-item expanded "><a href="lexer.html"><strong aria-hidden="true">3.</strong> Lexer</a></li><li class="chapter-item expanded "><a href="parser.html"><strong aria-hidden="true">4.</strong> Parser</a></li><li class="chapter-item expanded "><a href="evaluator.html" class="active"><strong aria-hidden="true">5.</strong> Evaluator</a></li><li class="chapter-item expanded "><a href="repl.html"><strong aria-hidden="true">6.</strong> REPL</a></li><li class="chapter-item expanded "><a href="next.html"><strong aria-hidden="true">7.</strong> What's Next</a></li></ol>
</div>
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky bordered">
<div class="left-buttons">
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</button>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Lisp interpreter in Rust</h1>
<div class="right-buttons">
<a href="print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script type="text/javascript">
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="evaluator"><a class="header" href="#evaluator">Evaluator</a></h1>
<p>Now comes the most exciting part of the project. Evaluation is the final step that will produce the result for the Lisp program. At a high level, the evaluator function recursively walks the List-based structure created by the parser and evaluates each atomic object and list (recursively), combines these intermediate values, and produces the final result. </p>
<h2 id="source"><a class="header" href="#source">Source</a></h2>
<p><a href="https://github.com/vishpat/lisp-rs/blob/0.0.1/src/eval.rs">eval.rs</a></p>
<h2 id="code-walk-through"><a class="header" href="#code-walk-through">Code Walk Through</a></h2>
<p>The evaluator is implemented using the recursive <em>eval_obj</em> function. The <em>eval_obj</em> function takes the List object representing the program and the global <em>env</em> variable (a simple hashmap) as the input. The function then starts processing the List object representing the program by iterating over each element of this list </p>
<pre><code class="language-Rust">fn eval_obj(obj: &Object, env: &mut Rc<RefCell<Env>>)
-> Result<Object, String>
{
match obj {
Object::Void => Ok(Object::Void),
Object::Lambda(_params, _body) => Ok(Object::Void),
Object::Bool(_) => Ok(obj.clone()),
Object::Integer(n) => Ok(Object::Integer(*n)),
Object::Symbol(s) => eval_symbol(s, env),
Object::List(list) => eval_list(list, env),
}
}
</code></pre>
<p>In the case of the atomic objects such as an integer and boolean, the evaluator simply returns a copy of the object. In the case of the Void and Lambda (function objects), it returns the Void object. We will now walk through the <em>eval_symbol</em> and <em>eval_list</em> functions which implement most of the functionality of the evaluator.</p>
<h3 id="eval_symbol"><a class="header" href="#eval_symbol">eval_symbol</a></h3>
<p>Before understanding the <em>eval_symbol</em> function, it is important to understand the design of how variables are implemented for the Lisp interpreter.</p>
<p>The variables are just <em>string</em> labels assigned to values and they are created using the <strong>define</strong> keyword. Note a variable can be assigned atomic values such as integer or a boolean or it can be assigned function objects </p>
<pre><code class="language-Lisp">(
(define x 1)
(define sqr (lambda (r) (* r r)))
)
</code></pre>
<p>The above Lisp code defines (or creates) two variables with the names x and sqr that represent an integer and function object respectively. Also, the scope of these variables lies within the <em>list object</em> that they are defined under. This is achieved by storing the mapping from the variable names (strings) to the objects in a map-like data structure called <em>Env</em> as shown below.</p>
<pre><code class="language-Rust">// env.rs
pub struct Env {
parent: Option<Rc<RefCell<Env>>>,
vars: HashMap<String, Object>,
}
</code></pre>
<p>The interpreter creates an instance of <em>Env</em> at the start of the program to store the global variable definitions. In addition, for every function call, the interpreter creates a new instance of env and uses the new instance to evaluate the function call. This new instance of env contains the function parameters as well as a <em>back</em> pointer to the <em>parent</em> env instance from where the function is called as shown below with an example</p>
<pre><code class="language-Lisp">(
(define m 10)
(define n 12)
(define K 100)
(define func1 (lambda (x) (+ x K)))
(define func2 (lambda (x) (- x K)))
(func1 m)
(func2 n)
)
</code></pre>
<p><img src="images/env.png" alt="Function Call" /></p>
<p>This concept will become clearer as we will walk through the code.</p>
<p>The job of <em>eval_symbol</em> is to look up the Object bound to the symbol. This is done by recursively looking up in the passed <em>env</em> variable or any of its parent <em>env</em> until the <em>root env</em> of the program. </p>
<pre><code class="language-Rust">let val = env.borrow_mut().get(s);
if val.is_none() {
return Err(format!("Unbound symbol: {}", s));
}
Ok(val.unwrap().clone())
</code></pre>
<h3 id="eval_list"><a class="header" href="#eval_list">eval_list</a></h3>
<p>The <em>eval_list</em> function is the core of the evaluator and is implemented as shown below.</p>
<pre><code class="language-Rust">let head = &list[0];
match head {
Object::Symbol(s) => match s.as_str() {
"+" | "-" | "*" | "/" | "<" | ">" | "=" | "!=" => {
return eval_binary_op(&list, env);
}
"if" => eval_if(&list, env),
"define" => eval_define(&list, env),
"lambda" => eval_function_definition(&list),
_ => eval_function_call(&s, &list, env),
},
_ => {
let mut new_list = Vec::new();
for obj in list {
let result = eval_obj(obj, env)?;
match result {
Object::Void => {}
_ => new_list.push(result),
}
}
Ok(Object::List(new_list))
}
}
</code></pre>
<p>This function peeks at the head of the list and if the head does not match the symbol object, it iterates all of the elements of the list recursively evaluating each element and returning a new list with the evaluated object values.</p>
<h3 id="variable-definitions"><a class="header" href="#variable-definitions">Variable definitions</a></h3>
<p>If the head of the list in the <em>eval_list</em> function matches the <em>define</em> keyword, for example</p>
<pre><code class="language-Lisp">(define sqr (lambda (x) (* x x)))
</code></pre>
<p>the <em>eval_define</em> function calls <em>eval_obj</em> on the third argument of the list and assigns the evaluated object value to the symbol defined by the second argument in the list. The symbol and its object value are then stored in the current <em>env</em>. </p>
<pre><code class="language-Rust">let sym = match &list[1] {
Object::Symbol(s) => s.clone(),
_ => return Err(format!("Invalid define")),
};
let val = eval_obj(&list[2], env)?;
env.borrow_mut().set(&sym, val);
</code></pre>
<p>In the example above the symbol <em>sqr</em> and the function object representing the lambda will be stored in the current <em>env</em>. Once the function <em>sqr</em> has been defined in this manner, any latter code can access the corresponding function object by looking up the symbol <em>sqr</em> in <em>env</em>.</p>
<h3 id="binary-operations"><a class="header" href="#binary-operations">Binary operations</a></h3>
<p>If the head of the list in the <em>eval_list</em> function matches a binary operator, the list is evaluated on the basis of the type of the binary operator, for example </p>
<pre><code class="language-Lisp">(+ x y)
</code></pre>
<p>the <em>eval_binary_op</em> function calls the <em>eval_obj</em> on the second and third element of the list and performs the binary <strong>sum</strong> operation on the evaluated values.</p>
<h3 id="if-statement"><a class="header" href="#if-statement">If statement</a></h3>
<p>If the head of the list in the <em>eval_list</em> function matches the <em>if</em> keyword, for example</p>
<pre><code class="language-Lisp">(if (> x y) x y)
</code></pre>
<p>the <em>eval_if</em> function calls <strong>eval_obj</strong> on the second element of the list and depending upon whether the evaluated value is true or false, calls the eval_obj on either the third or fourth element of the list and returns the value</p>
<pre><code>let cond_obj = eval_obj(&list[1], env)?;
let cond = match cond_obj {
Object::Bool(b) => b,
_ => return Err(format!("Condition must be a boolean")),
};
if cond == true {
return eval_obj(&list[2], env);
} else {
return eval_obj(&list[3], env);
}
</code></pre>
<h3 id="lambda"><a class="header" href="#lambda">Lambda</a></h3>
<p>As mentioned earlier, the <em>lambda</em> (or function) object consists of two vectors</p>
<pre><code class="language-Rust">Lambda(Vec<String>, Vec<Object>)
</code></pre>
<p>If the head of the list in the <em>eval_list</em> function matches the <em>lambda</em> keyword, for example</p>
<pre><code class="language-Lisp">(lambda (x) (* x x))
</code></pre>
<p>the <em>eval_function_definition</em> function evaluates the second element of the list as a vector of parameter names. </p>
<pre><code class="language-Rust">let params = match &list[1] {
Object::List(list) => {
let mut params = Vec::new();
for param in list {
match param {
Object::Symbol(s) => params.push(s.clone()),
_ => return Err(format!("Invalid lambda parameter")),
}
}
params
}
_ => return Err(format!("Invalid lambda")),
};
</code></pre>
<p>The third element of the list is simply cloned as the function body.</p>
<pre><code class="language-Rust">let body = match &list[2] {
Object::List(list) => list.clone(),
_ => return Err(format!("Invalid lambda")),
};
</code></pre>
<pre><code class="language-Rust">Ok(Object::Lambda(params, body))
</code></pre>
<p>The evaluated parameter and body vector are returned as the <em>lambda</em> object</p>
<h3 id="function-call"><a class="header" href="#function-call">Function Call</a></h3>
<p>If the head of the list is a Symbol object and it does not match any of the aforementioned keywords or binary operators, the interpreter assumes that the Symbol object maps to a Lambda (function object). An example of the function call in Lisp is as follows</p>
<pre><code class="language-Lisp">(find_max a b c)
</code></pre>
<p>To evaluate this list the <em>eval_function_call</em> function is called. This function first performs the lookup for the function object using the function name, <em>find_max</em> in the case of this example.</p>
<pre><code class="language-Rust">let lamdba = env.borrow_mut().get(s);
if lamdba.is_none() {
return Err(format!("Unbound symbol: {}", s));
}
</code></pre>
<p>If the function object is found, a new <em>env</em> object is created. This new <em>env</em> object has a pointer to the parent <em>env</em> object. This is required to get the values of the variables not defined in the scope of the function.</p>
<pre><code class="language-Rust">let mut new_env = Rc::new(
RefCell::new(
Env::extend(env.clone())));
</code></pre>
<p>The next step in evaluating the function call requires preparing the function parameters. This is done by iterating over the remainder of the list and evaluating each parameter. The parameter name and the evaluated object are then set in the new <em>env</em> object.</p>
<pre><code class="language-Rust">for (i, param) in params.iter().enumerate() {
let val = eval_obj(&list[i + 1], env)?;
new_env.borrow_mut().set(param, val);
}
</code></pre>
<p>Finally, the function body is evaluated by passing the new_env, which contains the parameters to the function</p>
<pre><code class="language-Rust">let new_body = body.clone();
return eval_obj(&Object::List(new_body), &mut new_env);
</code></pre>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="parser.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="repl.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="parser.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="repl.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script type="text/javascript">
window.playground_copyable = true;
</script>
<script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
<script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
<script src="searcher.js" type="text/javascript" charset="utf-8"></script>
<script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
<script src="highlight.js" type="text/javascript" charset="utf-8"></script>
<script src="book.js" type="text/javascript" charset="utf-8"></script>
<!-- Custom JS scripts -->
</body>
</html>
