kvalle/diy-lang

A hands-on, test driven guide to implementing a simple programming language

DIY Lang

batteries included, some assembly required

In this tutorial/workshop we'll be implementing our own little language, more or less from scratch.

By the end of the tutorial you will be the proud author of a programming language, and will hopefully better understand how programming languages work on a fundamental level.

What we will be making

We will make a relatively simple, but neat language. We aim for the following features:

• A handful of data types (integers, booleans and symbols)
• Variables
• First class functions with lexical scoping
• That nice homemade quality feeling

We will not have:

• A proper type system
• Error handling
• Good performance
• And much, much more

The language should be able to interpret the following code by the time we are done:

(define fact
    ;; Factorial function
    (lambda (n)
        (if (eq n 0)
            1 ; Factorial of 0 is 1
            (* n (fact (- n 1))))))

;; When parsing the file, the last statement is returned
(fact 5)

The syntax is very similar to languages in the Lisp family. If you find the example unfamiliar, you might want to have a look at a more detailed description of the language.

Prerequisites

First, clone this repo.

git clone https://github.com/kvalle/diy-lang.git
cd diy-lang

Then, depending on your platform:

• Mac: Install Python, either from the webpage or using brew. Then run easy_install nose to install nose, the test runner we'll be using.

  Optional: If you are familiar with virtualenv you might want to install nose in a separate pyenv to keep everything tidy.

• Windows/Linux: Install Python, either from the webpage or your package manager of choice. Then install Pip. Finally, install nose like this: pip install nose.

  Optional: If you are familiar with virtualenv you might want to install nose in a separate pyenv to keep everything tidy.

• Vagrant: If you have Vagrant installed, an easy way to get going is to use the provided Vagrantfile. Use vagrant up to boot the box, and vagrant ssh to log in. The project folder is synced to /home/vagrant/diy-lang.

Test your setup

Once installed, run nosetests --stop see that everything is working properly. This will run the test suite, stopping at the first failure. Expect something like the following:

$ nosetests --stop
E
======================================================================
ERROR: TEST 1.1: Parsing a single symbol.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/local/lib/python2.7/dist-packages/nose/case.py", line 197, in runTest
    self.test(*self.arg)
  File "/home/vagrant/diy-lang/tests/test_1_parsing.py", line 15, in test_parse_single_symbol
    assert_equals('foo', parse('foo'))
  File "/home/vagrant/diy-lang/diylang/parser.py", line 17, in parse
    raise NotImplementedError("DIY")
NotImplementedError: DIY

----------------------------------------------------------------------
Ran 1 test in 0.034s

FAILED (errors=1)

A few tips

Take the time to consider the following points before we get going:

• Keep things simple

  Don't make things more complicated than they need to be. The tests should hopefully guide you every step of the way.

• Read the test descriptions

  Each test has a small text describing what you are going to implement and why. Reading these should make things easier, and you might end up learning more.

• Use the provided functions

  Some of the more boring details are already taken care of. Take the time to look at the functions provided in parser.py, and the various imports in files where you need to do some work.

• The Python cheat sheet in python.md

  Unless you're fluent in Python, there should be some helpful pointers in the Python cheat sheet. Also, if Python is very new to you, the Python tutorial might prove helpful.

• Description of your language

  Read a description of the language you are going to make in language.md.

Get started!

The workshop is split up into eight parts. Each consist of an introduction, and a bunch of unit tests which it is your task to make run. When all the tests run, you'll have implemented that part of the language.

Have fun!

• Part 1: parsing
• Part 2: evaluating simple expressions
• Part 3: evaluating complex expressions
• Part 4: working with variables
• Part 5: functions
• Part 6: working with lists
• Part 7: using your language
• Part 8: final touches

diy-lang's Issues

Missing license

Hi,

Great project! Would it be possible for you to add a license to it (hopefully a permissive one)?

I'm in the process of doing the "tutorial" in NodeJS and I'm porting the tests almost verbatim to JS. When I'm finished I was hoping to create a clone of your project in NodeJS.

repl broken in Python 2

repl doesn't work in Python 2 because input is evaluated as python code immediately (which results in a Python exception). The reason seems to be the port to Python 3 that was done a few weeks ago.

repl.ly:68: line = input(colored(prompt, "grey", "bold"))

Possible workaround could be to use raw_input in Python 2 and input in Python 3 (Add in reply.py somewhere):

try:
   input = raw_input
except NameError:
   pass

Why is eq working only on atoms?

https://github.com/kvalle/diy-lisp/blob/master/tests/test_2_evaluating_simple_expressions.py#L61

I assume that '(1 2 3) isn't the same as '(1 2 3) because it's not an atom, but why such a restriction?

Parser tests don't cover ints

In yesterday's workshop my parser implementation passed the first test series although I cast digit strings to float. It made later tests fail with no apparent reason.

So the parser tests should check that numbers are ints.

Btw thanks for this very interesting workshop! Enjoyed it yesterday!

The ' (quote) symbol is not well defined

I went through the tutorial and it is great!

However, I think the handling of the quote symbol can be better explained. 'quote' is defined as follows in part 2:

quote takes one argument which is returned directly (without being evaluated).

So it is expected that "quote (1 2 3)" should be evaluated to "(1 2 3)".

On the other hand, according to test 6:

assert_equals([1, 2, 3, True], evaluate(parse("'(1 2 3 #t)"), Environment()))

As far as I understand, ' is a shorthand for quote, so it should be evaluated to "(1 2 3 #t)"

Import statements -- qualify with diylisp?

My initial attempt at running tests gave me the following error (following from the instructions):

kevinushey@Kevin-MBP:~/git/diy-lisp$ nosetests tests/test_1_parsing.py --stop

======================================================================
ERROR: Failure: ImportError (cannot import name 'is_boolean')
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/local/lib/python3.4/site-packages/nose/failure.py", line 39, in runTest
    raise self.exc_val.with_traceback(self.tb)
  File "/usr/local/lib/python3.4/site-packages/nose/loader.py", line 414, in loadTestsFromName
    addr.filename, addr.module)
  File "/usr/local/lib/python3.4/site-packages/nose/importer.py", line 47, in importFromPath
    return self.importFromDir(dir_path, fqname)
  File "/usr/local/lib/python3.4/site-packages/nose/importer.py", line 94, in importFromDir
    mod = load_module(part_fqname, fh, filename, desc)
  File "/usr/local/Cellar/python3/3.4.0_1/Frameworks/Python.framework/Versions/3.4/lib/python3.4/imp.py", line 235, in load_module
    return load_source(name, filename, file)
  File "/usr/local/Cellar/python3/3.4.0_1/Frameworks/Python.framework/Versions/3.4/lib/python3.4/imp.py", line 171, in load_source
    module = methods.load()
  File "<frozen importlib._bootstrap>", line 1220, in load
  File "<frozen importlib._bootstrap>", line 1200, in _load_unlocked
  File "<frozen importlib._bootstrap>", line 1129, in _exec
  File "<frozen importlib._bootstrap>", line 1448, in exec_module
  File "<frozen importlib._bootstrap>", line 321, in _call_with_frames_removed
  File "/Users/kevinushey/git/diy-lisp/tests/test_1_parsing.py", line 5, in <module>
    from diylisp.parser import parse, unparse
  File "/Users/kevinushey/git/diy-lisp/diylisp/parser.py", line 4, in <module>
    from ast import is_boolean, is_list
ImportError: cannot import name 'is_boolean'

Should we be using from diylisp.ast import ... instead; ie, qualifying with the directory?

(My lack of proficiency with Python is probably showing here...)

Question about scopes / environments

First, I want to thank you for this amazing project. Right now, I am working on part 8 and I can tell you that I have learnt and enjoyed the process a lot.

I am not sure if this is the right place to ask for help (I could't find any information about where help question should be asked).

Anyway, I am looking for guidance on how should I approach this situation:

def test_let_bindings_overshadow_outer_environment():
    """
    Let bindings should shadow definitions in from outer environments
    """

    interpret("(define foo 1)", env)

    program = """
        (let ((foo 2))
             foo)
    """

My evaluator function creates a new Environment every time it found a "let" special form, which is created by extending the one its belong to:

def eval_let(ast, env):
    let_env = env.extend({})

    bindings = ast[1]

    print bindings

    args = {}
    for b in bindings:
        key = b[0]
        val = evaluate(b[1], let_env)
        args[key] = val
        let_env.set(key, val)

    print args

    return evaluate(ast[2], let_env)

However, this only work if I allow override already defined variables in my Environment (this way I can use the set method to change the value of a variable), but this doesn't seem to be right way to do it because I can also define multiple times the same variable, which of course is wrong.

How should I implement this behaviour correctly?. I need to be able to read variables from the parent environment and at the same time, define a local variable without raising a duplicated definition error.

Thanks!!

Solution tests fails

$ ./run-tests.sh
................................F
======================================================================
FAIL: TEST 2.6: To be able to do anything useful, we need some basic math
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/nix/store/8z65fg9wa4vxi8sa4v55yyx00yj2wcrb-python3.6-nose-1.3.7/lib/python3.6/site-packages/nose/case.py", line 197, in runTest
    self.test(*self.arg)
  File "/home/simendsjo/bekk/fagdag-feb-2019/diy-lang/tests/test_2_evaluating_simple_expressions.py", line 87, in test_basic_math_operators
    assert_equals(3, evaluate(["/", 7, 2], Environment()))
AssertionError: 3 != 3.5

----------------------------------------------------------------------
Ran 33 tests in 0.004s

FAILED (failures=1)