Appendix A
DDK: The D Development Kit

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.

A.1 Installing the DDK

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:


$ mkdir ddk_tmp
$ mv ddk-0.1-byte.tar.gz ddk_tmp
$ cd ddk_tmp
$ gunzip -c ddk-0.1-byte.tar.gz | tar x

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.

A.2 Using D and DSR

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


$ DSR --help

to see the correct usage.

A.2.1 The Toplevel

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


$ DSR

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,


# 3 + 4;;
==> 7
# (Function x -> x + 1) 5;;
==> 6
# True Or False;;
==> True

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,


# (Function x -> Function y -> Function z -> x + y + z) 4 5;;
==> Function z ->
      4 + 5 + z

Notice how we can see the full result of the currying. This is useful for debugging large functions.

A.2.2 File-Based Intrepretation

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


$ DSR myprogram.dsr

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.


$ DSR mergesort.dsr
{l=1; r={l=2; r={l=3; r={l=4; r={l=5; r={l=6; r=
{l=7; r={l=8; r={l=9; r={l=10; r=-1}}}}}}}}}}

A.3 The DDK Source Code

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).

A.3.1 $DDK_SRC/src/ddk.ml

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.

module type LANGUAGE = sig
  val name: string

  module Ast: sig
    type expr
  end

  module Parser: sig
    type token
    val main:
     (Lexing.lexbuf -> token) -> Lexing.lexbuf -> Ast.expr
  end

  module Lexer: sig
    val token: Lexing.lexbuf -> Parser.token
  end

  module Pp: sig
    val pretty_print: Ast.expr -> string
    val pp: Ast.expr -> string -> string
  end

  module Interpreter: sig
    val eval: Ast.expr -> Ast.expr
  end

end;;

A.3.2 $DDK_SRC/src/application.ml

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


module MyApplication = Application.Make(MyLanguage);;
MyApplication.main();;

The code for the Application module is as follows.

module type S =
  sig
    val main: unit -> unit
  end

module Make(Lang: Ddk.LANGUAGE) =
  struct

    let toplevel_loop () =
      Printf.printf "\t%s version %s\n\n"
        Lang.name Version.version;
      flush stdout;
      while true do
        Printf.printf "# ";
        flush stdout;
        let lexbuf = Lexing.from_channel stdin in
        let ast = Lang.Parser.main Lang.Lexer.token lexbuf in
        let result = Lang.Interpreter.eval ast in
        Printf.printf "==> %s\n" (Lang.Pp.pp result "    ");
        flush stdout
      done


    let run_file filename =
      let fin = open_in filename in
      let lexbuf = Lexing.from_channel fin in
      let ast = Lang.Parser.main Lang.Lexer.token lexbuf in
      let result = Lang.Interpreter.eval ast in
      Printf.printf "%s\n" (Lang.Pp.pretty_print result);
      flush stdout

    let print_version () =
      Printf.printf "%s version %s\nBuild Date: %s\n"
        Lang.name Version.version Version.date

    let main () =
      let filename = ref "" in
      let toplevel = ref true in
      let version = ref false in
      Arg.parse
        [("--version",
          Arg.Set(version),
          "show version information")]
        (function fname ->
          filename := fname;
          version := false;
          toplevel := false)
        ("Usage: " ^
         Lang.name ^
         " [ options ] [ filename ]\noptions:");

      if !version then
        print_version ()
      else if !toplevel then
        toplevel_loop ()
      else
        run_file !filename

  end

A.3.3 $DDK_SRC/src/D/d.ml

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.

module Language = struct

  let name = "D"
  module Parser = Dparser
  module Lexer = Dlexer
  module Ast = Dast
  module Pp = Dpp
  module Interpreter = Dinterp

end;;

module Application = Application.Make(Language);;

Application.main ();;

A.3.4 $DDK_SRC/src/D/dast.ml

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.

type ident = Ident of string

type expr =
 Var of ident | Function of ident * expr | Appl of expr * expr |
 Letrec of ident * ident * expr * expr |
 Plus of expr * expr | Minus of expr * expr | Equal of expr * expr |
 And of expr * expr| Or of expr * expr | Not of expr |
 If of expr * expr * expr | Int of int | Bool of bool

A.3.5 $DDK_SRC/src/D/dpp.ml

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.

open Dast;;

let rec pp e pad =
  match e with
    Bool(true) -> "True"
  | Bool(false) -> "False"
  | Int(x) -> string_of_int x
  | Plus(e1, e2) ->
      pp e1 pad ^ " + " ^ pp e2 pad
  | Minus(e1, e2) ->
      pp e1 pad ^ " - " ^ pp e2 pad
  | Equal(e1, e2) ->
      pp e1 pad ^ " = " ^ pp e2 pad
  | And(e1, e2) ->
      pp e1 pad ^ " And " ^ pp e2 pad
  | Or(e1, e2) ->
      pp e1 pad ^ " Or " ^ pp e2 pad
  | Not(e1) ->
      "Not " ^ pp e1 pad
  | Appl(e1, e2) ->
      "(" ^ pp e1 pad ^ ") (" ^ pp e2 pad ^ ")"
  | Var(Ident(x)) -> x
  | Function(Ident(i), x) ->
      let newpad = pad ^ "  " in
      "Function " ^ i ^ " ->\n" ^ newpad ^ pp x newpad
  | If(e1, e2, e3) ->
      let newpad = pad ^ "  " in
      "If " ^ pp e1 pad ^ " Then\n" ^ newpad ^ pp e2 newpad ^
      "\n" ^ pad ^ "Else\n" ^ newpad ^ pp e3 newpad
  | Letrec(Ident(i1), Ident(i2), e1, e2) ->
      let newpad = pad ^ "  " in
      "Let Rec " ^ i1 ^ " " ^ i2 ^ " =\n" ^ newpad ^
      pp e1 newpad ^ "\n" ^ pad ^ "In\n" ^ newpad ^
      pp e2 newpad

let pretty_print e = (pp e "") ^ "\n"

A.3.6 Scanning and Parsing Concrete Syntax

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.

A.3.7 Writing an Interpreter

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.

Building DDK

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


$ ./configure

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

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


$ ./DSR

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.

Suggested Strategy for Writing the 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


$ ./D

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


# 3+4;;
==> 3 + 4

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.

open Dast;;

(*
 * Replace this with your interpreter code.
 *)
let rec eval e = e

Make the following modifications to dinterp.ml.


open Dast;;

exception TypeMismatch;;
exception NotImplemented;;

(*
 * Replace this with your interpreter code.
 *)
let rec eval e =
  match e with
    Int x -> Int x

  | Plus(e1, e2) ->
      (match (eval e1, eval e2) with
        (Int(x), Int(y)) -> Int(x + y)
      | _ -> raise TypeMismatch)

  | _ -> raise NotImplemented

Now, rebuild DDK by typing make in the $DDK_SRC directory again. Run the D toplevel. Now, we can evaluate addition expressions:


# 3+4;;
==> 7

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.