Write an interpreter: functions

This post is the third in a series. Previously, we wrote a toy interpreter for a language of arithmetic expressions, then extended the language to include variables. This time, we’ll extend the language to handle functions and make our interpreter handle the extended language.

As it stands now, our interpreter knows how to evaluate expressions containing variables, like this:

(10 + (x + y))

How do we know what the value of (10 + (x + y)) is supposed to be? We also have to provide an environment — something that maps variables to their values. So our interpreter expects two things: an expression to be evaluated, and an environment that tells us what variables in the expression mean. In an environment where x is bound to 42 and y to 5 the expression evaluates to 57.

*Main Map> (interp . parser . lexer) "(10 + (x + y))" (Map.fromList [("x", 42), ("y", 5)])

But what if we want to add (10 + (x + y)), but we want to do so twice, with different things plugged in for x and y, and then add all the results together? Sure, we could write ((10 + (x + y)) + (10 + (z + q)) and then pass in an environment that binds all of x, y, z, and q. But what if we wanted to do it four times, or four million times? that would get old fast.

Moreover, what if we wanted to write programs without knowing in advance what the values of variables are? For instance, maybe the value of a variable that depends on user input, or on some other information that’s only present at the time the program runs.

What we really want is the ability to write (10 + (x + y)), just once, but make it possible for x and y to stand for different things.