As usual, we invite the reader to follow along with the source code from this blog’s Google Code page, and to test programs with the interactive online interpreter.
Reserved Words, Values, and Ifs
In our last version of Chai we noticed a few things that needed fixing, so we’ll address those before moving on. First, consider the following chai program:
(with true false (or true true))
The user, being as odd as users will be, wants to bind the value “false” to the variable whose name is “true,” in a dirty attempt to trick somebody. The last version of Chai (see, Chai – Environments and Variables) interpreted this expression as “true,” and rightfully so in this mathematician’s opinion, since truth is not something which can be changed!
On the other hand, something just doesn’t feel right about this program. We can either allow such programs to be written (and wag a stern finger at all those who do!), or forbid the program from continuing once we find such a transgression. The latter makes more sense, and it introduces reserved words into Chai. As of the end of this post, our list of reserved words contains:
true false with if end pair fun
And we will add to this list as necessary. It’s ambiguous whether we should include things like +, -, *, /, etc. Someone may want to redefine what “plus” means, and that might not be an awful thing, say, once every two thousand years. For now, we will leave it alone. At least, we may stop someone from writing the appalling program:
(with with 1 (with with (with with with with) with))
All this requires to our code is that during parsing, whenever we inspect a variable binding (or list of variable bindings, or list of function arguments), we must ensure none are reserved words. This is straightforward enough, and the interested reader may inspect the source code.
Next, we realized ahead of time the need to discriminate between the input to our interpreter and its output. This is a direct result of our desire to add support for functions and basic lists. Now we have a new EBNF for “Chai values”:
chai-value = number | boolean | string | (pair chai-value chai-value) | end
One might notice that we have added strings, pairs (lists are nested series of pairs), and end, a null-value, named so to signify the terminating value of a list. In addition, we’ve added primitives for a whole host of operations, including: =, !=, <=, >=, <, >, pair (pair construction), end (list termination), first and rest (pair extraction), and end? (testing if a list is empty). We will certainly add more in the future, but for now this is enough.
In Racket code, we have the following new data type:
(define-type chai-value [num-v (val number?)] [bool-v (val boolean?)] [str-v (val string?)] [pair-v (head chai-value?) (tail chai-value?)] [end-v])
The new discrimination between Chai expressions and Chai values affects every branch of our interpreter and in every primitive operation, but only in how we accept and package up our data types. The interested reader can check out the changes in the source code; we will not discuss them here. (But we will mention that none of the changes occur in the type-checker. Nice.)
Finally, we’ve added “if” expressions for control flow. In the EBNF, an if looks like:
expr = ... | (if expr expr expr)
Where the first expression is the “test” expression, and the second is the “then” expression, and the third is the “else” expression. This translates directly to Racket as:
(define-type chai-expr ... [if? (test chai-expr?) (then-branch chai-expr?) (else-branch chai-expr?)])
Because the symbol ‘if’ conflicts with the Racket language form, we rename it ‘if?’; note that in Chai programs, the language form is still “if”. The parser is straightforward for if expressions, so we’ll jump straight to the interpreter. The new clause is:
(define (interp input-expr env) (type-case chai-expr input-expr ... [if? (test-expr then-branch else-branch) (let ([test-result (interp test-expr env)]) (type-case chai-value test-result [bool-v (test-value) (interp (if test-value then-branch else-branch) env)] [else (error 'interp "test expression was not a boolean: ~a" (chai-expr->string test-expr))]))]))
Note that we need to ensure the result of evaluating the test-expression is a boolean, and we ignore the unevaluated branch. For instance, the following program will run in Chai:
(if true 7 (/ 1 0))
even when the else branch will throw an error as a standalone program.
Finally, we’ve reached a very important milestone in Chai: figuring out what to do with functions. Let’s start with the basic syntax. In EBNF, a function has the form
expr = ... | (fun (vars ...) expr)
Where “vars …” indicates the presence of zero or more identifiers representing input variables, which are collectively referred to as “vars”. For instance, here is a Chai program which evaluates to the identity function:
(fun (x) x)
In Chai, we will treat functions the same way we treat any other primitive value. One can pass them around as if they were a number. For instance, here is a function which accepts one argument $ x$, and returns a function which accepts one argument $ y$ and adds $ x$ to $ y$:
(fun (x) (fun (y) (+ x y)))
Applying this function to a number returns a new function. In some languages, functions are required to be defined “at the top level,” i.e., given special names and put in special places. Since Chai expressions still consist of a single expression, we don’t have anywhere else to put them. So if one wants to “name” a function one can, but as it is most functions will be “anonymous.”
Speaking of function applications, they look like:
expr = ... | (expr expr ...)
Where the first expression should result in a function, and the remaining zero or more results should result in arguments to the function. Note that syntactically, these “shoulds” are irrelevant.
So here is a program which applies the previous example, which we name “make+=”, to some values:
(with make+= (fun (x) (fun (y) (+ x y))) (with +=7 (make+= 7) (pair (+=7 9) (pair (+=7 14) end))))
The advanced readers will recognize this as an explicit form of “currying” (accepting a partial list of arguments). We may in the future decide to have Chai support implicit currying, so that we may rewrite the above program as something like:
(with +=7 (+ 7) (pair (+=7 9) (pair (+=7 14) end)))
But for now let’s focus on the implementation.
In the parser, our new branches look like:
[(and (equal? 'fun first-thing) (equal? 3 list-len) (list? (second input-expr))) (let ([vars (check-vars (second input-expr))] [body (parse-expr (third input-expr))]) (function vars body))] [else (app (parse-expr first-thing) (map parse-expr (rest input-expr)))]))]
To elaborate, these two branches are wrapped within the condition that the expression is a list. If the first element of the list is not a reserved keyword like “with”, “if”, or “fun”, we assume the expression is a function application. Indeed, we could have some weird expressions that evaluate to functions, so we can’t discriminate any further here.
For functions, we have to ensure some things about the list of input variables. For instance, we can’t allow the user to repeat the same variable name twice, or use any reserved words, so we encapsulate both of those checks into a function called “check-vars”:
;; check-vars: listof symbol -> listof symbol ;; check a list of variable names for invalidity (define (check-vars names) (begin (map (λ (name) (when (reserved? name) (parse:bad-identifier name))) names) (when (has-duplicates? names) (error 'parse "list of variables has duplicates: ~a" names)) names))
We leave the implementation of has-duplicates? as an exercise to the reader (with the solution in chai-utils.rkt), and reserved? is just a membership test in a list of symbols (in chai-ast.rkt).
While it has its details, the parser is the easy part of implementing functions. We didn’t actually have to make any important decisions. We’ll see the semantics are a bit more complicated.
Scope, and Closures
In general, the scope of a variable $ x$ refers to the places in the program where we can inspect the value of $ x$. For instance, in the following program $ x$ is only in scope within the “with” expression.
(with y (+ x y) (with x 7) y)
So, in fact, the reference to $ x$ before the nested with statement is invalid, and this program will raise an error upon evaluation. Note that $ y$ is in scope in the nested with. Recalling how our interpreter works, this is obvious, because we only augment the environment with new variables after encountering their definition in a with.
To illustrate the confusion arising in discussions about scope, we have to investigate functions. In particular, the definition of a function can refer to a variable defined somewhere else, but the body of the function isn’t evaluated until it’s actually called. Since functions can be passed around like numbers, it raises ambiguity as to which variable we should refer to during a function application.
For instance, we could write the following program and ask what it should do:
(with my-function (with x 33 (fun (y) (+ x y))) (with x 44 (my-function 55)))
Should this program evaluate to 88 or 99? Before continuing, make a guess as to what will happen (and try to argue why your choice is the best option), and verify it by running the program through our interactive interpreter.
In fact, there is no completely “correct” answer to this question, and it highlights the differences between lexical and dynamic scope. In the latter, a variable will always refer to the most recent binding which is in scope. In other words, if Chai had dynamic binding, the program above would evaluate to 99. On the other hand, if we implemented lexical scope, “my-function” would retain the information about what variables were in scope during its definition, and so the resulting call would evaluate to 88.
The engaged reader will have by now verified that Chai has lexical scope, and not dynamic scope (in the future, we may provide an alternative version of Chai which has dynamic scope). Most contemporary programming languages implement lexical scope, because it just so happens that otherwise the logic flow in a program is harder to determine just by reading it. However, some popular languages originally had dynamic scope, and later decided to tack on support for lexical scoping. Sometimes lexical scope is referred to as static scope.
In order to support lexical scope in Chai, we have to now discriminate between a function definition, and the function definition combined with the variables that are in scope during definition. In other words, we need the result of interpreting a function definition to contain both pieces of information. In particular, we call this piece of data a closure.
Now the chai-value datatype has an additional branch:
chai-value = number | boolean | string | (pair chai-value chai-value) | end | (closure environment (vars...) chai-expr)
Where the environment is our datatype for variable bindings, the vars… is the same list of function variables from our function definitions, and the chai-expr is the body expression, in unevaluated form. (Indeed, we can’t evaluate the body until it’s applied to some arguments!)
So this adds one more branch to our type-case:
(define-type chai-value ... [closure-v (env environment?) (vars (listof symbol?)) (body chai-expr?)])
Now we are ready to interpret functions, and see what we can do with them.
In fact, interpreting function definitions is easy! Since we have already been keeping track of the environment all along, we can package it up in a closure in a single line:
(define (interp input-expr env) (type-case chai-expr input-expr ... [function (vars body) (closure-v env vars body)]))
Applying a function is quite a bit more work. In particular, we have two things we need to check before believing that the user knows how to write programs:
- Is the first thing in a function application a function? (Does it evaluate to a closure?)
- Does the number of provided arguments match the number of accepted arguments?
If neither of these are the case, we need to raise an error. Assuming these requirements are met, we can perform the actual function application as follows:
(let* ([interped-args (map (λ (arg) (interp arg env)) args)] [new-env (foldl add-binding closure-env vars interped-args)]) (interp body new-env))
where args, vars, closure-env, and body are all the expected parts of our function application and closure. Note that we are very specific to augment the closure environment with the new bindings for the function arguments. This is the key of lexical scope, whereas dynamic scope would use the standard environment.
With all of the case-checking, the branch in our interpreter is a bit longer:
(define (interp input-expr env) (type-case chai-expr input-expr ... [app (clo args) (let ([expected-clo (interp clo env)]) (type-case chai-value expected-clo [closure-v (closure-env vars body) (let ([arg-count (length args)] [var-count (length vars)]) (when (not (eq? arg-count var-count)) (error 'interp "expected ~a args for a function application, but got ~a" var-count arg-count)) (let* ([interped-args (map (λ (arg) (interp arg env)) args)] [new-env (foldl add-binding closure-env vars interped-args)]) (interp body new-env)))] [else (error 'interp "invalid function in function application: ~a" (chai-expr->string expected-clo))]))]))
Try to follow the logic above. Even for the author, determining what someone else’s code does is a nontrivial process, so don’t worry if it’s overwhelming at first. Just remember that most of it is error-checking, and the key part is the three lines where we actually perform the function application. Of course, to get an even better understanding, try to run programs in our interactive interpreter which hit every error case, and compare that with the flow of logic in the code above.
Recursion, But Not Quite Easy Enough
The experienced reader might be asking herself “Why haven’t we implemented any loops yet? We can’t really do anything interesting without loops.” And she is correct! A programming language cannot be Turing-complete (informally, have the true power of a computer) if it can’t branch out, or make programs which run indefinitely.
As of now, we couldn’t, say, write the function map (see our functional programming primer, A Taste of Racket, for a definition). If we try, we get a nasty error:
(with map (fun (f list) (if (end? list) end (pair (f (first list)) (map f (rest list))))) (map (fun (x) (+ 1 x)) (pair 7 (pair 6 (pair 5 end)))))
It complains that “map” is not bound in the current environment, which is a shame, because map is a really great function to have around, and we can’t build it yet (well, that’s not quite true, but it wouldn’t be as straightforward as what we have above).
It turns out that even though we can’t quite do this kind of recursion with names, we can still achieve infinite loops in Chai! We challenge the reader to figure out how to do it, and see what our interactive interpreter does in response. As a hint, the shortest solution the author has found is a mere 33 characters long, including spaces and parentheses, and it only requires functions and applications.
Some Further Issues to Address
We recall saying we would like the user to be able to redefine what “+” means via a with expression. However, upon trying to evaluate the following program which “adds” two functions, we get an error:
(with + (fun (f g) (fun (arg) (+ (f arg) (g arg)))) ((+ (fun (x) (+ x 1)) (fun (y) (* y 2))) 7))
In order to fix this, we need to stop distinguishing between primitive operations and functions which are bound to symbols in our environment. In other words, we want to pre-populate the environment with bindings for primitive functions, which can be overwritten by the programmer. This will simplify our code significantly, since we can move even more of the logic outside of the interpreter and parser, and think of everything as a function application. This is something we have to look forward to in the future.
As long as we’re thinking of everything as a function application, why don’t we simplify Chai even further so that we only have functions and applications? No numbers, no primitives, no conditionals. What sort of language would we get? We’ll see just what happens with a little intermezzo next time. Of course, we will only do this temporarily to explore its theoretical properties, and then we’ll return to the civilized world.
“Of course, we will only do this temporarily to explore its theoretical properties, and then we’ll return to the civilized world.”
Really a nice conclusion, but what if we stuck in the underground, under the “hood”?
I’m not sure what you mean. The next post in the series will be about the lambda calculus, which is a model of computation that only knows about functions and function applications, and theoretically can do everything that any computer can do. It would be unfeasible to work entirely in the lambda calculus without any abstractions, because it’s quite inefficient for a lot of tasks.