The D Development Kit, or DDK, is a small set set of utilities for working with our example languages, D and DSR. DDK is useful in two ways. First, it provides the binaries D and DSR for toplevel and file-based interpretation. In addition, all of the source code for DDK is available, except for the interpreters. The reader may write his own D or DSR interpreter, and plug it into the DDK source to make a toplevel and file interpreter for testing purposes. This appendix explains how to use the DDK binaries, and gives an overview of the source code.
Before we begin, let’s establish a notation for the examples in this appendix. Shell commands and expressions within the toplevel are typeset in typewriter font. Lines beginning with “$” are shell commands, while lines beginning with “#” are expressions typed within the toplevel. Lastly, lines beginning with “==>” are the resulting values computed by the toplevel.
DDK should run on any platform which supports OCaml and the OCaml development tools. It is recommended, although not strictly necessary, that you compile DDK on a Unix or Unix-like platform which supports GNU Make.
The DDK bytecode binaries are available at
http://www.cs.jhu.edu/~scott/plbook/DDK/downloads/binaries.
Download the bytecode tar archive ddk-0.1-byte.tar.gz. Make a temporary directory, and move the archive there and unpack it:
Now there will be a subdirectory with the same name as the tar archive (without the .tar.gz extension). In this directory are two bytecode files: d.byte and dsr.byte. Now, simply execute the shell command ocamlrun d.byte to run a D top loop, and similarly for DSR.
The DDK source is available at
http://www.cs.jhu.edu/~scott/plbook/DDK/downloads/source
The source requires no installation. Simply unpack the source archive in the directory of your choice. We will discuss how to work with the source code in Section A.3.7.
The D and DSR utilities both have similar syntax and functionality,1 and so without loss of generality, we will discuss only DSR in this section. There are two ways to use DSR: as a toplevel, and as a file-based interpreter. If ever in doubt, type
to see the correct usage.
The DSR toplevel is extremely similar to the Caml toplevel, and should seem quite familiar and intuitive. The toplevel is good for testing small chunks of code. For anything that is too long to type or paste into the toplevel, DSR should be run against a file instead. To run the toplevel, simply type
To exit the toplevel, press CTRL+C at any time.
Once in the toplevel, the # prompt appears. At the # prompt, any DSR expression may be entered, followed by a ;;, just as in Caml. The expression is evaluated and the value is output after a ==>. For example,
The toplevel behaves much like the Caml toplevel, but has a few differences. The main difference is that Let statements must always have an explicit In. This means that DSR programs must be input as one continuous string expression, and evaluation does not begin until the ;; is input. For this reason, larger programs should be written as files, and directly interpreted instead of input at the toplevel.
The second difference is more of an advantage. Unlike the Caml toplevel, the DSR toplevel always outputs a full representation of its result values. This is particular useful for looking at expressions that evaluate to functions. While Caml just reports the value as <fun>, DSR gives a full description. For example,
Notice how we can see the full result of the currying. This is useful for debugging large functions.
In addition to a toplevel, the DSR utility can also directly intrepret a file. This is useful for interpreting larger programs that are difficult to enter into the toplevel. Comments of the form (*...*) are valid in DSR, and can be added to improve the readability of the code. To interpret a file, simply type
The value result of the program will be displayed on standard output. For example, interpreting the merge sort example in Section 4.3.2 would look like this.
In this section, we will give an overview of the DDK source code. DDK is written in Objective Caml 3.07[15]. The main reason to become familiar with the source code is to learn how to write an interpreter than can “plug in” to DDK. Plugging in an interpreter builds a toplevel and file-based interpreter over top of it, and allows the developer to test his interpreter on expressions in the concrete syntax, which is much easier then trying to write abstract syntax out by hand. Let’s begin by surveying the major components od the DDK source. In the following sections, we assume the DDK source code is installed in a directory called $DDK_SRC (this will be the directory that is created when the source archive is expanded).
ddk.ml defines the Ddk module.2 This module contains a single module signature type, LANGUAGE. Any module that implements this signature can be used to create a toplevel of file interpreter.
The Application module implements the toplevel and file interpreter in a language independent way. It contains a functor Make that is parameterized on Ddk.LANGUAGE. A module with signature Application.S is returned, which contains a function main. Therefore, a new toplevel and file interpreter can be trivially written as
The code for the Application module is as follows.
The codebases for D and DSR are, for the most part, parallel, therefore we will examine only the D code, and not DSR. The D module is an implementation of Ddk.LANGUAGE and is very straightforward.
The Dast module contains a type expr that is the type of the abstract syntax tree for our language. It is exactly as we defined it in Section 2.3.
Dpp is a pretty-printer for D. The function pretty_print takes a Dast.expr and returns a string representation in the concrete syntax. In other words, it converts from abstract to concrete syntax. This is used to display the result of a computation.
The scanner and parser are written using the parser generation tools ocamlyacc and ocamllex, which are similar to the C-based yacc and lex tools. Using such tools is beyond the scope of this book, but the interested reader is directed to the source files $DDK_SRC/src/D/dlexer.mly and $DDK_SRC/src/D/dparser.mly for the scanner and parser sources respectively.
The source distribution already contains a “template” for both the D and DSR interpreters. For example, the file $DDK_SRC/src/D/dinterp.ml contains a dummy implementation of Ddk.LANGUAGE.Intreperter in which eval e simply returns e. $DDK_SRC/src/DSR/dsrinterp.ml contains a similar dummy inplementation for DSR. Simply replace the dummy definition of eval with the code for a real interpreter, and rebuild DDK (building DDK is discussed in the next section). Note that supporting functions may and should be used when writing eval. As long as eval is defined, the interpreter will conform to the signature regardless of other functions that are defined.
As a reference point, the directory $DDK_SRC/src/BOOL contains a full implementation of the boolean toplevel and interpreter. The implementation mirrors the D implementation that we looked at above.
The final point we need to discuss is how to actually build DDK. Luckily, doing so is very straightforward. Before building for the first time, you will need to configure the build process for your platform. This is done by going to the $DDK_SRC directory and typing
The configure script checks for the OCaml tools that are needed to build the source, and also determines whether to use a native compiler, or whether to compile to bytecode. Note that the directory containing ocaml, ocamlc, ocamlyacc, etc. should be in your path before running the configure script.
Once the configure script is finished, you should see a Makefile in the $DDK_SRC directory. Once the Makefile is there, configure does not need to be run again, unless you move the source to a different platform.
Now, DDK can be built at any time by going to the $DDK_SRC directory and typing
make will build the binaries D, DSR, and BOOL and copy them to the $DDK_SRC directory, from where then can be run, for example, as
If you platform does not support sh and GNU Make, you can still build DDK. Windows users should use win32Build.bat to build DDK. Note that you can comment out the lines of this file that you don’t need, it builds all three interpreters.
The best strategy for writing the interpreter is probably to add a single clause at a time to the eval function, and then to rebuild and test that clause. Let’s walk through an example. Assuming the configure script has already been run, build DDK without modifying the dummy interpreter by typing make.
Now run the D toplevel by typing
Try entering in an expression into the toplevel. The dummy interpreter simply spits the expression back without evaluating it, so your session will look like
Press CTRL+C to exit the toplevel. Now let’s write the match case for addition. Open the file $DDK_SRC/src/D/dinterp.ml in your favorite text editor. The file should initially look as follows.
Make the following modifications to dinterp.ml.
Now, rebuild DDK by typing make in the $DDK_SRC directory again. Run the D toplevel. Now, we can evaluate addition expressions:
Proceed in this manner, adding one or two match cases, and then testing, then adding some more match cases. This way, if an error occurs, it will be easy to figure out which changes caused it.