<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Overview - 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"><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>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="next" href="introduction.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="next" href="introduction.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>