<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Lisp interpreter in Rust</title>
<meta name="robots" content="noindex" />
<!-- 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"><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="overview"><a class="header" href="#overview">Overview</a></h1>
<p>The <a href="https://github.com/vishpat/lisp-rs">lisp-rs</a> project implements an interpreter, in Rust, for a small subset of <a href="https://en.wikipedia.org/wiki/Scheme_(programming_language)">Scheme</a>, a Lisp dialect. The main goal of this document is to make sure the reader understands the inner details of how the interpreter was implemented.</p>
<p>The project was inspired by Peter Norvig's article <a href="http://www.norvig.com/lispy.html"><strong>(How to Write a (Lisp) Interpreter (in Python))</strong></a> and the book <a href="https://interpreterbook.com"><strong>Writing An Interpreter In Go</strong></a>. This document serves as a commentary on the <a href="https://github.com/vishpat/lisp-rs/tree/0.0.1">code</a> that implements the interpreter. Rust's rich programming constructs such as enum, pattern matching, and error handling make it easy and a joy to implement this bare-bone interpreter. </p>
<h2 id="pre-requistes"><a class="header" href="#pre-requistes">Pre-requistes</a></h2>
<p>To make the most out of this project, it is expected that the user is aware of the following Computer Science concepts</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/List_(abstract_data_type)">Lists</a></li>
<li><a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)">Recursion</a> </li>
</ul>
<p>Rust is a non-trivial language, however, to implement the Lisp interpreter, the reader needs to have moderate experience with the language. Knowing the following four concepts should be enough for the user to understand the whole project </p>
<ul>
<li><a href="https://doc.rust-lang.org/book/ch06-00-enums.html">Enums and Pattern Matching</a></li>
<li><a href="https://doc.rust-lang.org/book/ch15-00-smart-pointers.html">Smart Pointers</a></li>
<li><a href="https://doc.rust-lang.org/book/ch09-00-error-handling.html">Error handling</a></li>
</ul>
<h2 id="lisp-dialect"><a class="header" href="#lisp-dialect">Lisp Dialect</a></h2>
<p>In order to keep the interpreter simple and its implementation easy to understand, the number of features supported by it has been limited on purpose. Following are the data types and statements that will be supported by the interpreter.</p>
<h3 id="data-types"><a class="header" href="#data-types">Data types</a></h3>
<ul>
<li>integer</li>
<li>boolean</li>
</ul>
<h3 id="statements"><a class="header" href="#statements">Statements</a></h3>
<ul>
<li>variable definition and assignment</li>
<li>if-else</li>
<li>function definition using lambdas</li>
<li>function calls</li>
</ul>
<h3 id="keywords"><a class="header" href="#keywords">Keywords</a></h3>
<ul>
<li>define</li>
<li>if-else</li>
<li>lambda</li>
</ul>
<h3 id="examples"><a class="header" href="#examples">Examples</a></h3>
<p>Following are some of the sample programs that you will be able run using the interpreter</p>
<pre><code class="language-lisp"> (
(define factorial (lambda (n) (if (< n 1) 1 (* n (factorial (- n 1))))))
(factorial 5)
)
</code></pre>
<pre><code class="language-lisp"> (
(define pix 314)
(define r 10)
(define sqr (lambda (r) (* r r)))
(define area (lambda (r) (* pix (sqr r))))
(area r)
)
</code></pre>
<h2 id="interpreter"><a class="header" href="#interpreter">Interpreter</a></h2>
<p>The interpreter will be implemented from scratch and without the help of any tools such as <a href="https://docs.rs/nom/latest/nom/">nom</a> or <a href="https://pest.rs/">pest</a>. The interpreter implementation is broken down into four parts</p>
<ul>
<li><a href="./lexer.html">Lexer</a> ~ 20 lines of code</li>
<li><a href="./parser.html">Parser</a> ~ 60 lines of code</li>
<li><a href="./evaluator.html">Evaluator</a> ~ 170 lines of code</li>
<li><a href="./repl.html">REPL</a> ~ 30 lines of code</li>
</ul>
<p>The best way to understand the implementation of the interpreter is to check out the code and walk through it while reading this document. </p>
<pre><code>git clone https://github.com/vishpat/lisp-rs
git checkout 0.0.1
</code></pre>
<p>Once you thoroughly understand the implementation, you will be equipped to add new features to it, such as support for new data types like strings, floating-point numbers, lists, or functional programming constructs such as map, filter, reduce functions, etc. </p>
<h3 id="repl"><a class="header" href="#repl">REPL</a></h3>
<p>To run the interpreter and get its REPL (Read-Eval-Print-Loop)</p>
<pre><code>cargo run
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="introduction"><a class="header" href="#introduction">Introduction</a></h1>
<p>Lisp is an abbreviation for <strong>Lis</strong>t <strong>P</strong>rocessor. Every Lisp program is simply a list. The elements of this list can either be atomic values such as an integer or a string or another list. Thus a Lisp program is a recursive list as shown below. </p>
<p><img src="images/list.png" alt="List Recursion" /></p>
<p>The Lisp interpreter is a software program that parses the <strong>text</strong> of a Lisp program and creates an in-memory List-based recursive data structure. Once the Lisp program is represented as a data structure, interpreting the program involves recursively evaluating these lists. This is the core of what a Lisp interpreter does, there is nothing more to it. Simple and Beautiful.</p>
<p>The following chapters in this book will walk you through the code that implements this interpreter. The interpreting process can be broken down into three phases.</p>
<ul>
<li>Lexing: Converting the Lisp program text into a stream of tokens.</li>
<li>Parsing: Converting the stream of tokens into an in-memory recursive list data structure.</li>
<li>Evaluation: Walking the in-memory recursive list and producing the final result.</li>
</ul>
<p>In addition, the final chapter will implement a simple REPL to evaluate the Lisp program. </p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="lexer"><a class="header" href="#lexer">Lexer</a></h1>
<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/lexer.rs">lexer.rs</a></p>
<h2 id="code-walk-through"><a class="header" href="#code-walk-through">Code Walk Through</a></h2>
<p><strong>Lexer</strong> is a component of the interpreter that takes the program text and converts it to a stream of atomic units known as <strong>tokens</strong>. Every token has a type and may even have a value associated with it. In the case of our interpreter, there are four types of tokens. The four tokens can be represented using a Rust enum as follows.</p>
<pre><code class="language-Rust">pub enum Token {
Integer(i64),
Symbol(String),
LParen,
RParen,
}
</code></pre>
<ul>
<li>Integer: A signed 64-bit integer</li>
<li>Symbol: Any group of characters other than an integer or parenthesis</li>
<li>LParen: Left parenthesis</li>
<li>RParen: Right parenthesis</li>
</ul>
<p>The first step in implementing a lexer is to replace the parenthesis with an extra space before and after it. For example,</p>
<pre><code class="language-Lisp">(define sqr (* x x))
</code></pre>
<p>will get converted to</p>
<pre><code class="language-Lisp">( define sqr ( * x x ) )
</code></pre>
<p>With this simple trick, the process of tokenization involves splitting the Lisp program with whitespace. </p>
<pre><code class="language-Rust"> let program2 = program.replace("(", " ( ")
.replace(")", " ) ");
let words = program2.split_whitespace();
</code></pre>
<p>Once the words for the program are obtained, they can be converted into tokens using Rust's pattern matching as follows</p>
<pre><code class="language-Rust">let mut tokens: Vec<Token> = Vec::new();
for word in words {
match word {
"(" => tokens.push(Token::LParen),
")" => tokens.push(Token::RParen),
_ => {
let i = word.parse::<i64>();
if i.is_ok() {
tokens.push(Token::Integer(
i.unwrap()));
} else {
tokens.push(Token::Symbol(
word.to_string()));
}
}
}
}
</code></pre>
<p>At this point, we have a vector of tokens for the entire Lisp program. Note that a vector in Rust is a stack, hence the tokens are stored in the vector in the reverse order as shown below with an example. </p>
<p><img src="images/token_stack.png" alt="List Recursion" /></p>
<h2 id="testing"><a class="header" href="#testing">Testing</a></h2>
<p>The lexer code can be unit tested as shown below</p>
<pre><code>let tokens = tokenize("(+ 1 2)");
assert_eq!(
tokens,
vec![
Token::LParen,
Token::Symbol("+".to_string()),
Token::Integer(1),
Token::Integer(2),
Token::RParen,
]
);
</code></pre>
<p>To cement your understanding of the Lexing process please go through the remaining tests in <strong>lexer.rs</strong></p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="parser"><a class="header" href="#parser">Parser</a></h1>
<h2 id="source-1"><a class="header" href="#source-1">Source</a></h2>
<p><a href="https://github.com/vishpat/lisp-rs/blob/0.0.1/src/parser.rs">parser.rs</a></p>
<h2 id="code-walk-through-1"><a class="header" href="#code-walk-through-1">Code Walk Through</a></h2>
<p>The job of the parser is to take the vector of tokens and convert it into a recursive list structure (mentioned in the <a href="./introduction.html">introduction</a>). This recursive list structure is an in-memory representation of the Lisp program. </p>
<h2 id="object-model"><a class="header" href="#object-model">Object model</a></h2>
<p>Before diving into the details of how the recursive list structure is created, we need to first define the objects that will make up the elements of the list. This is done in the <em>object</em> Rust module with an enum defined as follows</p>
<pre><code class="language-Rust">pub enum Object {
Void,
Integer(i64),
Bool(bool),
Symbol(String),
Lambda(Vec<String>, Vec<Object>),
List(Vec<Object>),
}
</code></pre>
<ul>
<li><em>Void</em>: An empty object</li>
<li><em>Integer</em>: A signed 64-bit integer</li>
<li><em>Bool</em>: A boolean value</li>
<li><em>Symbol</em>: A Lisp symbol, similar to the Symbol token</li>
<li><em>Lambda</em>: Function object, with the first vector representing the parameter labels and the second vector representing the body of the function. This object is not used during parsing but will be used during the evaluation phase of the interpreter.</li>
<li><em>List</em>: List object</li>
</ul>
<h2 id="parser-1"><a class="header" href="#parser-1">Parser</a></h2>
<p>The parser for the Lisp dialect is a simple recursive function. It takes a vector of tokens (in reverse) generated by the lexer and generates a single <em>List Object</em> representing the entire Lisp program. The core logic of the parser is implemented by the recursive <em>parse_list</em> function as shown below. It expects a vector of tokens, with the first token of the vector being a left parenthesis indicating the start of the list. The function then proceeds to process the elements of the list one at a time. If it encounters atomic tokens such as an integer or symbol it creates corresponding atomic objects and adds them to the list. If it encounters another left parenthesis it recurses with the remaining tokens. Finally, the function returns with the list object when it encounters the right parenthesis. </p>
<pre><code class="language-Rust">let token = tokens.pop();
if token != Some(Token::LParen) {
return Err(ParseError {
err: format!("Expected LParen, found {:?}",
token),
});
}
let mut list: Vec<Object> = Vec::new();
while !tokens.is_empty() {
let token = tokens.pop();
if token == None {
return Err(ParseError {
err: format!("Insufficient tokens"),
});
}
let t = token.unwrap();
match t {
Token::Integer(n) =>
list.push(Object::Integer(n)),
Token::Symbol(s) =>
list.push(Object::Symbol(s)),
Token::LParen => {
tokens.push(Token::LParen);
let sub_list = parse_list(tokens)?;
list.push(sub_list);
}
Token::RParen => {
return Ok(Object::List(list));
}
}
}
</code></pre>
<h2 id="testing-1"><a class="header" href="#testing-1">Testing</a></h2>
<p>The above parsing code can be unit tested as follows</p>
<pre><code class="language-Rust">let list = parse("(+ 1 2)").unwrap();
assert_eq!(
list,
Object::List(vec![
Object::Symbol("+".to_string()),
Object::Integer(1),
Object::Integer(2),
])
);
</code></pre>
<p>To cement your understanding of the parsing process please go through the remaining tests in <strong>parser.rs</strong></p>
<div style="break-before: page; page-break-before: always;"></div><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-2"><a class="header" href="#source-2">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-2"><a class="header" href="#code-walk-through-2">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>
<div style="break-before: page; page-break-before: always;"></div><h1 id="repl-1"><a class="header" href="#repl-1">REPL</a></h1>
<h2 id="source-3"><a class="header" href="#source-3">Source</a></h2>
<p><a href="https://github.com/vishpat/lisp-rs/blob/0.0.1/src/main.rs">main.rs</a></p>
<h2 id="code-walk-through-3"><a class="header" href="#code-walk-through-3">Code Walk Through</a></h2>
<p>The REPL is the simplest part of the interpreter implementation. It uses the <a href="https://crates.io/crates/linefeed">linefeed</a> crate to implement the functionality.</p>
<p>The REPL first creates an instance of <em>env</em> to hold the global variables for the interpreter.</p>
<pre><code>let mut env = Rc::new(RefCell::new(env::Env::new()));
</code></pre>
<p>The REPL is a simple while loop that takes one line as an input from the user, evaluates it, and prints out the evaluated object. The REPL is terminated if the user enters the <strong>exit</strong> keyword. </p>
<pre><code class="language-Rust">while let ReadResult::Input(input) =
reader.read_line().unwrap() {
if input.eq("exit") {
break;
}
let val = eval::eval(input.as_ref(), &mut env)?;
match val {
Object::Void => {}
Object::Integer(n) => println!("{}", n),
Object::Bool(b) => println!("{}", b),
Object::Symbol(s) => println!("{}", s),
Object::Lambda(params, body) => {
println!("Lambda(");
for param in params {
println!("{} ", param);
}
println!(")");
for expr in body {
println!(" {}", expr);
}
}
_ => println!("{}", val),
}
}
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h2 id="whats-next"><a class="header" href="#whats-next">What's next</a></h2>
<p>Congratulations!!! if you have made it so far, you now have a grasp of how to implement a Lisp interpreter in Rust. A few easy things to try next would be to add support for float point numbers, unsigned integers, and strings. Once you are able to successfully make these changes the next thing to try would be to add support for the List datatype followed by support for the functional constructs of map, filter, and reduce.</p>
<p>With this knowledge, you should be then able to implement an interpreter for any non-trivial language. </p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
</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 -->
<script type="text/javascript">
window.addEventListener('load', function() {
window.setTimeout(window.print, 100);
});
</script>
</body>
</html>
