Essentials of interpretation. Intro.
“Essentials of interpretation” is a new series which consists of small lessons on interpretation of computer programs. The lessons are implemented in JavaScript and contain detailed comments. The sources can be found on the appropriate GitHub repository.
Available lessons:
- Lesson 1. The simplest arithmetic expressions (AE) evaluator
- Lesson 2. Parsing. Lexer of AE in math infix notation
- Lesson 3. Parsing. Parser of AE in math infix notation
- Lesson 4. Working with environments. Variables and built-in functions
- Lesson 5. Simple user-defined functions
- Lesson 6. Inner functions, lambdas and closures
- Lesson 7. Derived expressions (“Syntactic sugar”)
Notes:
- Note 1. Stack-based evaluation of the simplest AE in the prefix notation
- Note 2. S-expression to AST transformer
- Note 3. Complex data structures: pairs and lists
Currently the first lesson is available where we describe the simplest interpreter of the arithmetic expressions (AE). Every lesson contains also exercises which are proposed to implement improving the understanding of the passed topic.
Besides the code sources from the repository (which are quite compact), the appropriate chapters of the series are planned.
At the end, we’re going to implement a (simple?) language with support of basic expressions, variables stored in environments and functions as closures (that is, quite easily implementing higher-order functions).
A previous work is the implementation of Scheme on Coffee language — an interpreter of Scheme written in CoffeeScript.
The inspiration of the series are two books on programming languages theory (PLT) and interpretation: SICP (Structure and Interpretation of Computer Programs) by Harold Abelson and Gerald Jay Sussman with Julie Sussman, and also PLAI (Programming Languages: Application and Interpretation) by Shriram Krishnamurthi. The books are recommended as additional literature.
Have fun with implementing programming languages
Dmitry Soshnikov, 2011-08-10.
Tags: Essentials of interpretation, Interpreter, PLAI, SICP

10. August 2011 at 19:19
very good initiative
10. August 2011 at 23:03
Thanks, Dmitry, it’s very interesting! Look forward to further explanations.
11. August 2011 at 00:41
Awesome!
That will be definitely something huge!
Thanks!
11. August 2011 at 11:28
My solution to homework assignment #2:
var handle = { '+': function(a, b) { return a + b; }, '-': function(a, b) { return a - b; }, '*': function(a, b) { return a * b; }, '/': function(a, b) { return a / b; }, '_default': function(a) { return +a; } }; function evaluate(exp) { var symbol = +exp; if (exp == symbol) { return symbol; } symbol = exp[0]; return (handle.hasOwnProperty(symbol) && handle[symbol] || handle._default)(evaluate(exp[1]), evaluate(exp[2])); }11. August 2011 at 15:49
@scriptLover, @Robert Polovsky, @John Merge, thanks, guys!
@Mathias Bynens, yes, quite an elegant solution; very good.
And by the way, the second lesson in a source code view is available!
11. August 2011 at 21:00
This be interesting. I love SICP, even though I haven’t worked out through all the exercises yet =/
This is what I’ve come up with for lesson 1′s first two exercises:
https://github.com/killdream/Essentials-of-interpretation/blob/master/solutions/lesson-1.js
11. August 2011 at 21:26
@Quildreen Motta very good solution. I see you also implemented variables using environments — great, congrats! The next step is nested functions and scope chain lookups
We will reach them in the next lessons.
11. September 2011 at 19:11
I’ve been using Sage (sagemath.org) recently for linear algebra and other math work. Their notebooks are quite nice and provide a way for wonderful collaboration.
BUT .. I realize Python is a lovely language but I’ve recently discovered how sophisticated JS is, and how complete it has made the JS world: node.js for servers, JS + HTML5 for clients, and JSON for communications between the two.
So I’ve got two questions relating to your work:
1 – How would I go about implementing operator overloading? It is a pretty important part of mathematics, I think, and keeps the notation uncluttered.
2 – Could you point me to good existing mathematics in JS work?
Thanks,
— Owen
14. September 2011 at 20:25
@Owen Densmore
Sage seems a powerful framework for math (not sure how it correlates in tools with e.g. MatLab, but anyway, seems a good helper).
Python is also very interesting language (actually, it has a similar semantics as JS: also completely dynamic, you may augment objects and classes at runtime, though, not built-in classes as in JS and Ruby).
And about operator overloading, in the simplest way just comparing the types of operands. If they (or one of them) are strings, use concatenation, if operands are floats, use different algorithm, etc.
Unfortunately I’m not aware about mathematics framework such as Sage in JS. But seems Python also fits nice
This series though isn’t about mathematics much, but about interpretation of computer programs in general (though of course we touch some abstract data and operations, including primitive, such as math addition, etc, on them).