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.

Tags: , , ,

 
 
 

11 Comments:

  1. Gravatar of scriptLover scriptLover
    10. August 2011 at 19:19

    very good initiative


  2. Gravatar of Robert Polovsky Robert Polovsky
    10. August 2011 at 23:03

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


  3. Gravatar of John Merge John Merge
    11. August 2011 at 00:41

    Awesome!
    That will be definitely something huge!
    Thanks!


  4. Gravatar of Mathias Bynens Mathias Bynens
    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]));
    
    }

  5. Gravatar of Dmitry A. Soshnikov Dmitry A. Soshnikov
    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!


  6. Gravatar of Quildreen Motta Quildreen Motta
    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


  7. Gravatar of Dmitry A. Soshnikov Dmitry A. Soshnikov
    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.


  8. Gravatar of Owen Densmore Owen Densmore
    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


  9. Gravatar of Dmitry A. Soshnikov Dmitry A. Soshnikov
    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).


  10. Gravatar of Marlon Marlon
    5. July 2013 at 12:42

    Thank you, thank you and thank you


  11. Gravatar of ulbrain ulbrain
    9. July 2014 at 09:48

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


Leave a Reply

Code: For code you can use tags [js], [text], [ruby] and other.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>