Introduction This manual introduces the O'Caml Structure Editor Toolkit (OSET). The purpose of OSET is to provide an easy to use and easy to program user interface. There is a video demonstrating the result of the examples presented in this manual, which can be found at http://youtube.com/watch?v=0lsNJw-sXBc. Chapter 1 presents ways to automatically generate structure editors based on datatype definitions. Chapter 2 presents the basics of how to create a custom structure editor and should be used as a kind of reference. Chapter 3 guides the reader through the creation of a structure editor for monomorphic lambda calculus with type inference using the concepts presented in chapter 2. If the focus of the reader is to write his own programming language structure editor, it is recommanded that chapter 2 be quickly read before jumping right into chapter 3.

Automatic node generation

It is possible to automatically generate so called ``type node generators'' using the camlp4 extension.

Automatic generation with ``with seditable''

Structure editor for a calculator

Consider a language for a calculator which can add and subtract. To create a structure editor for such a calculator, simply add ``with seditable'' at the end of the declaration, like so:

(* example location: getting-started/code/1-calculator *)
type calc = 
    | Plus of calc * calc 
    | Minus of calc * calc 
    | Number of int 
        with seditable

This simply creates a function ``seditable_of_calc'' which is of type unit -> node. We call this a ``type node generator''. To obtain a value of type calc you would use the follow snippet:

let value_of_type_calc = SEditable.input (seditable_of_calc)

If you wanted to display something of type calc, you would write

let _ = 
   let foo = Number 5 in 
   let n = 
      SEditable.create_node seditable_of_calc 
   in
      SEditable.load n foo;
      SEditable.show n

The function interpret takes a term of type calc and returns the result of the calculation:

let rec interpret = 
   function
       Plus (a, b)  ->
         interpret a + interpret b
     | Minus (a, b) ->
         interpret a - interpret b
     | Number x -> x

You can now implement a full blown calculator:

let _ = 
  let inp = 
    SEditable.input (seditable_of_calc)
  in
  let n = 
    SEditable.seditable_of_int () 
  in
    SEditable.load n (interpret inp);
    SEditable.show n

A video of the result can be viewed at http://www.youtube.com/watch?v=QqJj2c9Xxo8.

Moving around and inputting

To move around your structure editor, use the arrow keys to change the current location. You can type things in the boxes. If choices are presented to you, press F<number> to select one of the choices. Often times you can press the delete key to clear the current node. Control-s will submit whatever you've written if you have done. Control-c is for copy and Control-v is for paste. when a node is selected, press the ``r'' key to retract it into three dots. Pressing the ``e'' key will expand the current node or all the descendants by one level. If you want to expand all of it, press ``a''. Pressing escape toggles the suggestion window. Insert moves between the source and the menu. You can also use the mouse to select a node or a suggestion. The following table :

up	moves to parent
down	moves to leftmost child
right	moves to right sibling
left	moves to left sibling
F<n>	select the nth suggestion available
delete	delete the current node
Control-s	submit
Control-c	copy
Contral-v	paste
r	retract
e	expand one level
a	expand all
insert	focus menu/source
tab	browse through suggestions
escape	shows/hides suggestion window

Nodes and type nodes

An element of type node can be displayed using the function OsetGUI.run_with_node. Once displayed, the user is free to edit the node using the keyboard and mouse. A type node generator is an automatically generated function of type unit -> OsetNode.type_node. To extract a value from a type node generator you can use the Seditable.input function. If a type node generator is generated from a type ``foo'' then it will be bound to the name seditable_of_foo. For example, nn the previous example the type node seditable_of_calc was generated for type ``calc''. Type nodes are objects and have the following useful methods:

trans	returns an element of the underlying type
load	takes an element of the underlying type and loads it into the
to_string	returns a string representation of the node.

Furthermore, they have the following types:

trans	unit
load	'a -> unit
to_string	?default_string:(unit->string) -> unit -> string

the method to_string takes a default_string optional argument which returns the string with which to fill holes (nodes which have yet to be filled in).

Automatic generation with ``grammar''

A prettier calculator

The previous calculator works, but it's not very pretty. We can use the new grammar construct to create an equivalent calculator:

(* example location: getting-started/code/2-prettier-calculator *)
grammar calc :
      Plus : calc, "*", calc 
    | Minus : calc, "*", calc 
    | Number : "(",int, ")"

This does two things

1. creates a type calc identical to the previous example
2. creates a function seditable_of_calc, which is simply a more user friendly version of the previous example

The grammar construct is especially useful is you already have a context free grammar which you want to model. Simply copy the grammar rule by rule. You can then use the method to_string to create a parseable string. We will soon see how to handle tokens. A video of the result can be viewed at http://www.youtube.com/watch?v=k6N6WcBUVmo.

Tokens and choice

A form

Say you want to create a form where the user must input his name, email, sexe and city. An email is defined by a regular expression and a city is defined by a list of (possibly thousands) of strings. To deal with regular expressions we can us tokens and to deal with lists of string we can use choice_of_strings function like so:

(* example location: getting-started/code/3-form *)
token email = ".+@.+\\..+"
type city = string
let seditable_of_city = 
     SEditable.choice_of_strings ["Montreal";"New York";"Paris";"London"]

Once done, you can write the rest of the form like so:

type sexe = Male | Female with seditable
type form = 
    {
      name : string;
      city : city;
      email: email;
      sexe: sexe;
    } with seditable

You would then, predictably, prompt the user for a term like so:

let _ = 
  let inp = 
    SEditable.input (seditable_of_form)
  in
    print_endline inp.email

Using token and grammar you can model many already defined context free grammars. A video of the result can be viewed at http://www.youtube.com/watch?v=ZAM0lvxJpyw.

Parametric type node generators

If a type is parametric it will generate a parametric type node generator. Parametric type node generators take type nodes as their arguments. For example the list type's type node generator SEditable.seditable_of_list has type (unit -> type_node) -> unit -> type_node so that SEditable.seditable_of_list SEditable.seditable_of_int is a type node for int list. Another parametric type node generator of the same type is SEditable.seditable_of_star which was generated for type star, which is the same as type list. Other examples of parametric type node generators are question and plus. Using star, plus and question we can write grammars which are very similar to EBNF grammars.

SQL

You can generate parts of the structure editor dynamically. The following is an example of a structure editor where the tables names and row names are generated by functions.

(* example location: getting-started/code/4-sql *)
let get_table_names () =  ["table1";"table2"]
let get_row_names () = ["age";"address"]

type table_name = string
let seditable_of_table_name = 
  SEditable.choice_of_strings (get_table_names ())
type row_name = string
let seditable_of_row_name = 
  SEditable.choice_of_strings (get_row_names ())


grammar select :
    Select : "SELECT" , (row_name list) , "FROM", (table_name list)

Then you can call the structure editor like so:

let _ = 
  let res = SEditable.input (select_of_select) 
  in
    match res with 
	Select (tables,rows) ->
	  print_endline 
	    ("SELECT " ^ (String.concat " , " tables) ^
	       " FROM " ^ (String.concat " , " rows))

Generating structure for already defined types

XML

A video of the result can be viewed at http://www.youtube.com/watch?v=KD7kxhz3DD4. If you want to generate a structure editor for an already generated type, you would do the following:

(* example location: getting-started/code/6-prettier-xml *)
open Xml

grammar xml_p (= xml) :
     PCData : "PCData", string
   | Element : "Element", (string * (string * string) list * (xml_p list))

let _ = 
  SEditable.input (seditable_of_xml_p)

OSET will generate a new type xml_p like so:

type xml_p = xml

and will then generate the corresponding seditable_of_xml_p function. Please note that the module in which the constructors are located MUST be opened.

Prettier XML

The previous example works, but it doesn't correspond to the XML grammar we're used to. We can get around this by using the piggyback function.First thing to do is to define the grammar:

open SEditable
grammar xml_grammar :
    Element :  "<", string, attribute star, ">" , 
               xml_grammar star, 
               "</", string, ">"
  | CharData : string
and attribute:
    Attribute : string,"=",string

Notice the star type is used; this type is defined in the module SEditable. The second thing to notice is that you can build mutually recursive types with the ``and'' construct. Now that we have a structure editor, we would like to interface it with the xml-light library. We do this by defining two functions: from_xml and to_xml:

let rec to_xml =
  function
      Element (str,atts,grams,_) ->
	Xml.Element 
	  (str,
	   List.map (function Attribute (x,y) -> (x,y)) atts,
	   List.map to_xml grams)
    | CharData str ->
	Xml.PCData str

let rec from_xml = 
  function
      Xml.Element (str,atts,xmls) ->
	Element 
	  (str,
	   List.map (fun (x,y) -> Attribute (x,y)) atts, 
	   List.map from_xml xmls,
	   str)
    | Xml.PCData str ->
	CharData str

Using these two functions, we can construct a structure editor for Xml.xml like so:

type xml_p = Xml.xml

let seditable_of_xml_p = SEditable.piggyback seditable_of_xml_grammar from_xml to_xml

we can then use the structure editor as a pretty printer for xml documents.

let pretty_print_xml xml = 
  let n = SEditable.create_node seditable_of_xml_p in
    SEditable.load n xml;
    SEditable.to_string n

A video of the result can be viewed at http://www.youtube.com/watch?v=63xkE406tFU.

How to define the star type

The star type itself is built from a piggyback using the epsilon type. The epsilon type corresponds to the empty string.

grammar 'a star_p:
    More : 'a, 'a star
  | Done : epsilon

type 'a star = 'a list

let rec to_star =
  function
      More (a,b) ->
	a :: to_star b
    | Done _ -> []

let rec from_star =
  function
      a :: b -> More (a,from_star b)
    | [] -> Done ()

let seditable_of_star x = piggyback (seditable_of_star_p x) from_star to_star

Writing custom structure editors

We will now investigate how to write your own structure editors from scratch. Structure editors are represented by the abstract class Node, found in the module OsetNode.

Hello World

The hello_world class inherits the simplest_node_implementation virtual class and which simply overrides the render method so that it displays Hello World. The simplest_node_implementation class simply implements most of node's virtual methods as simply as possible. Here is the code:

(* example location: getting-started/code/hello-world *)
open OsetWidgets

class hello_world = 
object
  inherit OsetNode.simplest_node_implementation
  method render = 
    box (label "Hello World")
end

let _ = OsetGUI.run_with_node (new hello_world)

XML

Our first object language will be XML. We will be building this structure editor with the help of the simplest_node_implementation class. Before we start, it is essential to open the module OsetWidgets, a module which includes functions which dictate how a node is drawn on the screen

open OsetWidgets

We will define three mutually recursive functions: iter, pcdata and element. Our first function iter will take an XML.xml and return a node.

(* example location: getting-started/code/custom-xml *)
let rec iter x = 
  match x with
      Xml.PCData str ->
	pcdata str
    | Xml.Element (x,y,z) ->
	element (x,y,z)

then we define our second function, pcdata. We will inherit from the ``simplest_node_implementation'' class, which contains trivial definitions for all the methods of a node except the render method. The render method must return something which is a boxed_widget. There are several ways to create a boxed widget, but the easiest is to call the ``box'' function on a widget, such as the label widget. All the widget functions are found in the OsetWidgets module. The result is the following:

and pcdata str =
  (object (self)
     inherit OsetNode.simplest_node_implementation
     method render = 
       box 
	 (label str)
   end)

Our third and most interesting function is element. This function introduces the ``information_bar'' method to our reader. This method displays text on the top of the screen. In this case we will simply display the element attributes. The function ``node'' takes a node and returns a widget which represents that node. Finally, the left_spacing widget is presented, which simply offsets its child from the left. Here's the result:

and element (x,elems,unprocessed_children)  = 
  let children = List.map (fun a -> (iter a)) unprocessed_children in 	
    (object(self)
       inherit OsetNode.simplest_node_implementation
       method information_bar = 
	 let attributes = List.map (fun (x,y) -> x ^ " = " ^ y) elems in 
	   if attributes = [] 
	   then [],[]
	   else
	     ("attributes:" :: attributes,[])

       method render = 
	 box
	   (vbox
	      (label x :: 
		 (List.map 
		    (fun a -> left_spacing 30 (node (a:>OsetNode.node) )) 
		    (children:>OsetNode.node list))))
     end)

Finally, we include a function make which calls iter

let make x = 
  iter (Xml.parse_file x)

to run a node, call ``OsetGUI.run_with_node'' like so:

let _ = 
   let t = ExampleXML.make "elite.xml"  in
      OsetGUI.run_with_node (t:>OsetNode.node)

OsetWidgets

The return type of the render method is a boxed_widget, which can be constructed using the functions found in the OsetWidgets module. There are two functions to construct a boxed_widget: box and suggestions. A box takes a widget, which can be one of:

hbox	a horizontal list of widgets
vbox	a vertical list of widgets
node	a node
left_spacing	some spacing to the left
frame	a colored frame
text_view	a box of text
staggered_if_big lst	where lst has type ([`FLUSH|`INDENTED] * widget) list

staggered_if_big is expands automatically if one of its subnodes is selected or if it's too big; otherwise it acts like an hbox with spaces in between the widgets. A box can take an optional argument unselected_color which is the colour of the frame when the node is not selected. The suggestion function two arguments: one to store the state of the suggestion box (a string ref) and the other is a list of suggestions.

Suggestion

A suggestion is a term of type

string -> 
    (string * 
        (unit -> [`Stay | `Move_to of 'a | `Search | `Search_from of 'a ])) option

A suggestion takes a string and either returns None if the string doesn't match the suggestion or Some (s,f) where s is the string displayed to the user and f is a function which returns one of the following:

`Stay	stay in place
`Move_to n	move to node n
`Search	search for the next suggestion box
`Search_from n	move to n and then search for the next suggestion box

OsetSuggestion

The OsetSuggestion module provides many functions to automatically create suggestions. For example:

string_and_action_to_suggestion	takes a string and a function unit -> [`Stay|..]
string_and_pridicate_to_suggestion	takes a string, a predicate of type unit -> bool and a function unit -> [`Stay|..]
anystring_suggestion	takes a function of type string -> unit -> [`Stay | ..]
non_empty_string_eating_suggestion	similar to anystring_suggestion, but only accepts nonempty strings
int_suggestion	takes a function of type int -> unit -> [`Stay|..]

Examples of boxed widget

box (label "Hello World!")
box (hbox [label "foo";label "bar"])
box 
  (hbox 
    [label "some vbox"; vbox [label "some node";node some_node]])
box ~unselected_color:Sdlvideo.grey (label "foo")
suggestions 
    str_state 
    [int_suggestion (fun i () -> print_endline i;`Stay)]

Adding a menu

When you automatically generate a type node generator, create a type node and passe it to OsetGUI.run_with_node you are presented with a graphical user interface with a menu box on the top left corner. Clicking on the top left corner (or pressing insert) presents the menu. It is possible to present a custom menu by overriding the get_node_specific_menu method, which has type menu option where

type menu = 
  Environment of 
    string * 
      (string -> 
          (string  *  
              (unit -> 
                  [`Switch_to_menu of menu 
                  | `Switch_to_node of node 
                  |  `Focus_source 
                  | `Focus_source_and_search  
                  | `Focus_menu])) 
           option)

The string in the pair is the text presented to the right of the menu box. The second element of the pair is very much like a suggestion. Like a suggestion it returns None if the string doesn't match and Some(s,f). Unlike a suggestion, f is one of the following:

`Switch_to_menu m	replaces the current menu by m
`Switch_to_node n	focuses node n and gives back the keyboard focus to the node
`Focus_source_and_search	focuses the next hole and transfers keyboard focus
`Search_from n	focus on the next hole after node n

You can use OsetSuggestion.string_and_action_to_suggestion which takes a string and a function unit -> 'a and returns a string -> (string * 'a) option. You can find an example of a menu in the element function definition in simplest-xml.

Adding a global menu

It is possible to add a global menu for all nodes by using run_with_node with the optional argument top_menu_func. The argument is an element of type menu option -> menu which takes the optional local menu (defined by the get_node_specific_menu method) and returns a global menu. You can then switch to the local menu using `Switch_to_menu. In the custom-xml-global-menu directory you can find an example of a global menu which loads an xml file. It uses the function OsetGUI.switch_to_node to load the new node.

Key bindings

Keybindings are added to nodes using the get_node_specific_keybindings method which has type

([ `Unicode of int 
 | `Keysym of Sdlkey.t * Sdlkey.mod_state] * 
       (unit -> 
          [ `Switch_to_menu of node menu_param 
          | `Switch_to_node of node 
          | `Focus_source 
          | `Focus_source_and_search 
          | `Focus_menu])) list

You would typically use `Unicode except for control characters such as backspace and delete.

Miscellaneous examples

Binary tree

The binary tree example is another good example of using suggestions. The code is in the custom-binarytree directory. A never_ending_binarytree is either an internal node with two children or a leaf which is a suggestion box. The suggestion boxes have only one suggestion. The suggestion either accepts any string and creates an internal node whose name matches the string inputted by the user. If the string inputted by the user is empty, it names the internal node ``unnamed''. Notice that the `Leaf constructor takes a string reference. This is so that the suggestion box keeps its contents after a redraw. If you had created a new reference for every call to ``suggestions'', the box would be cleared after every redraw.

Changing fonts

To change the font simply set the OSET_FONT_LOCATION environment variable. In bash you would write something like export OSET_FONT_LOCATION=/foo/bar/baz.ttf

Simply typed lambda calculus

This chapter describes the structure editors located in the simply-typed-lambda-calculus subdirectory. The underlying datatype we wish to focus on is the following:

(* example location: getting-started/code/simply-typed-lambda-calculus *)
type expression = 
      Application of expression * expression
    | Lambda of string * expression
    | Number of int 
    | Boolean of bool
    | String of string
    | Atom of string

type function_definition = 
     string * expression

type program = 
     function_definition list

The reason that we will be building the structure editor from scratch is that we can restrict the user to only inputting correct programs. Another advantage to building it from scratch is that we can decide how to display the nodes. By correct we mean that all variables and function names are bound where they are used. For this purpose, we need a context which propagates throughout the nodes. Our context will have type string list and will contain both variables and function names

A first attempt

To understand this chapter, please look at the code in first-attempt. There are three mutually recursive classes. The first is expression which can be one of 6 things:

`Unset	waiting for user input
`List	a list of expressions
`Atom	a variable or function name
`String	a string
`Number	a number

An expression is initialized as `Unset, as witnessed by the code

  val mutable body :
    [
    | `Unset of string ref
    | `List of expression_list
    | `Atom of (string,string ref) either 
    | `Number of (int,string ref) either
    | `String of (string,string ref) either 
    ] = `Unset (ref "")

rendering

There are several cases for rendering an expression.

      | `Unset str ->

Is when an expression is waiting for user input. It gives the user the option between switching the node to a atom, number, string or list.

      | `List lst ->

renders the list with a margin of 30 pixels. lst has type expression_list

      | `Atom (Right str) ->

represents an unintialized atom. It asks the user to input the name of an atom. The name cannot be an empty string. The other cases are similar.

program

A program represents an expandable list of function definitions. It stores the function definitions already added and a tail node which adds more function definitions.

tail

The tail node keeps prompting the user to add more nodes until the user selects ``done''. When a tail node is done it becomes a small light grey box. Notice that when a node is added the status is reinitialized to `Adding (ref ""). This simply clears the suggestion box.

Adding types, unification, context and error highlighting

This section describes the source found in the directory second-attempt.

Adding types

First we model types with a simple datatype:

type typ = 
  | Arrow of typ * typ
  | Int
  | Bool
  | Variable of (typ option) ref

Then we define a function to convert types to string

let name_of_reference_map : (typ option ref * string) list ref = ref []

let rec string_of_typ =
  function
      Arrow (t,t') ->
	"(" ^ string_of_typ t ^ "->" ^ string_of_typ t' ^ ")"
    | Int -> "int"
    | Bool -> "bool"
    | Variable {contents = Some t} ->
	string_of_typ t
    | Variable v ->
	try
	  List.assoc v !name_of_reference_map
	with
	    _ -> 
	      let name = 
		"x" ^ string_of_int (List.length !name_of_reference_map)
	      in
		name_of_reference_map := (v,name) :: !name_of_reference_map;
		name

Unification

We implement a straightforward reference based unification algorithm.

exception Ununifiable

let rec unify =
  function 
    | (Variable {contents=Some t}, b) ->
	unify (t,b)
    | (Variable a,Variable {contents=Some t}) ->
	unify (Variable a,t)
    | (Variable  a,b) ->
	a := Some b
    | (a,Variable b) -> 
	b := Some a
    | (Arrow (t,t'),Arrow (u,u')) ->
	unify (t,u);
	unify (t',u')
    | (Int,Int) -> ()
    | (Bool,Bool) -> ()
    | _ -> raise Ununifiable

Context

Context is simply a map from names to types, defined like so:

type context = (string * typ) list

Adding to and using the context

Given a context con, we are interested in seeing if an expression is well typed in that context. In the class expression there is a method check which takes a context and an expected type and checks if the expression does indeed have the expected type. If anything goes wrong, the error mutable variable is updated. In the class function_definition there is a method add_to_context which takes a context and checks its underlying expression in that context. If the function_definition has a name, that name is added to the context. In this manner, the context is incrementally expanded and the function definitions are sequentially checked. All this is done in the render method in the program class. The information_bar method in expression displays the current type of the expression if it hadn't encountered an error when checking; otherwise it prints the error. An expression which has an error will have a red box around it, which was achieved by using the ~unselected_color label with box

Final touches

This section describes the source found in the directory final-attempt.

Smarter suggestions

We want the structure editor to suggest only possibilities which would result in a well typed program. We do this by unifying all the possible choices.

Checking unifiability

If an expression is expecting a type t, say Arrow(Int,Variable (ref None)), then the possible suggestions will be those whose type unify with that type. We cannot simply call unify on the type of every element in the context because unify might instantiate the reference in t. The solution to this is to first copy the two types and then unify the copies making sure that equal references in the original types are mapped to equal references in the result, like so:

let copy_type t = 
  let rec iter sofar = 
    function
	Variable {contents=Some t} -> iter sofar t 
      | Variable x ->
	  (try 
	    (sofar,List.assq x sofar)
	  with 
	      _ ->
		let new_var = Variable (ref None) in
		  ((x,new_var)::sofar,new_var))
      | Arrow (t,t') ->
	  let (sofar',u) = iter sofar t in 
	  let (sofar'',u') = iter sofar' t' in 
	    (sofar'',Arrow(u,u'))
      | (Int | Bool | String) as x -> (sofar,x)
  in
    snd (iter [] t)

let are_unifiable t1 t2 = 
  let t1' = copy_type t1 in
  let t2' = copy_type t2 in 
    try
      ignore(unify (t1',t2'));
      true
    with
	_ -> false

Once we have the are_unifiable function, we can change the render method in expression at the `Atom (Right str) and `Unset _ branches. We simply have to see if the current expression satisfies the predicate are_unifiable current_typ t where t is the type we're expecting.

Adding a menu

We will define a menu to save the current program. First we define the abstract datatype like so:

type exp = 
      Application of exp * exp
    | Lambda of string * exp
    | Number of int 
    | Boolean of bool
    | StringLit of string
    | Atom of string

type fundef = 
     string * exp

type prog = 
     fundef list

Then we must define a method trans for the class program whose return value is prog. Once that's done, we can define a menu like so:

let program = new program

let menu _ = 
  let save_suggestion = 
    OsetSuggestion.string_and_action_to_suggestion
      "save"
      (fun _ ->
	 let out = open_out "save_file" in
	   (try
	      output_value out (SEditable.trans program)
	    with
		_ -> ());
	   close_out out;
	   `Focus_source)
  in
  (OsetNode.Environment 
     ("menu",
      [save_suggestion;load_suggestion
      ]))
  
	      
let _ = OsetGUI.run_with_node ~top_menu_func:menu program

Notice how menu takes an argument, being the local menu of the node. Since the nodes do not have a local menu (defined by the get_node_specific_menu method), the argument is ignored. We leave it up to the reader to finish writing this menu by adding a load suggestion; this will require the reader to add a method to the program class.

Adding deletion

Deletion is added by overriding the get_node_specific_keybindings method in a class. In our implementation we override the method in the program class, like so:

  method get_node_specific_keybindings =
    [
      (`Keysym (Sdlkey.KEY_DELETE,Sdlkey.kmod_none),
       fun ()->
          body <- [];
          `Focus_source)
    ]

We leave it up up to the reader to override the get_node_specific_keybindings in the expression and function_definition classes.