in Courses

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:

Notes:

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.

Write a Comment

Comment

13 Comments

  1. Thanks, Dmitry, it’s very interesting! Look forward to further explanations.

  2. Awesome!
    That will be definitely something huge!
    Thanks!

  3. 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]));
    
    }
  4. @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!

  5. @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.

  6. 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

  7. @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).

  8. Dmitry, special thanks for exercises. I am as beginner in programming very grateful for them.

  9. Dmitry, did you do all of the SICP exercises? How long did you work with that book?(I mean is it hard for you?)