The Forlan Project (Version 4.9)


Introduction

The Forlan Project consists of a toolset (called Forlan) for experimenting with formal languages, a graphical editor for Forlan automata and trees called JForlan, and a draft textbook entitled Formal Language Theory: Integrating Experimentation and Proof. The toolset, graphical editor and book are released under free software/documentation licenses.

The Forlan toolset is a library on top of the Standard ML of New Jersey (SML/NJ) implementation of Standard ML (SML). It's used interactively, and users are able to extend Forlan by defining SML functions.

Announcements Mailing List; Feedback Request

Forlan-Announce is a low-volume announcements mailing list for the Forlan Project.

Feedback concerning the Forlan Project is very welcome. Email: alley.stoughton@icloud.com.

What's New?

Version 4.9
Added two functions for hand-simplification of grammars to Gram module (see the manual and book for descriptions of eliminateVariable and restart). Continuing revision of book.
Version 4.8
Improved documentation of local and global regular expression simplification. Continuing revision of book.
Version 4.7
Added functions to StrSet for prefix, suffix and substring closure. Minor documentation changes. Starting revision of book.
Version 4.6
Bringing Forlan up-to-date with most recent SML/NJ compiler (110.82).
Version 4.5
This release includes Version 2.1 of JForlan, which fixes a minor bug relating to regular expression tree error checking and includes the changes needed to make JForlan build using Apache Ant.
Version 4.4
This release features a new draft (September 2012) of the textbook, as well as some minor changes and additions to the Forlan toolset and manual. The RFA module of the toolset now exports functions for standardizing an RFA and for converting an RFA to a regular expression.
Version 4.3
This release features a new draft (August 2012) of the textbook, as well as some relatively minor changes and additions to the Forlan toolset and manual. Most significantly, the textbook now includes a draft of Chapter 5, which uses a functional programming language to study the recursive and recursively enumerable languages. I believe that the toolset is now in close to final form. The textbook should be usable, but still needs substantial work.
Version 4.2
This release features changes to Forlan, JForlan, the Forlan manual, and the draft textbook. Major changes have been made to Forlan's simplification algorithms for regular expressions, small changes have been made to the simplification algorithms for finite automata and grammars, and the parsing algorithm for context-free grammars has been improved. The new release (Version 2.0) of JForlan contains numerous bug fixes and changes of functionality. Error checking is now always turned on, and if there are no errors, the Forlan syntax of the current project's automaton or tree is displayed. Projects now have a committable boolean attribute, which is true exactly when the project originated from Forlan. Only committable projects may be committed back to Forlan. There is now a full draft of the Forlan manual. The draft textbook is now consistent with the toolset, and contains all the material that was only in the lecture slides in Version 4.1. Those lecture slides are no longer part of the Forlan release.
Version 4.1
This release features small changes to the Forlan toolset's lexical analyzer.
Version 4.0
This release features a completely redesigned and redeveloped version of JForlan (Version 1.0), the graphical editor for Forlan automata and trees.

Papers on Forlan

Textbook

The Forlan toolset has been developed together with an introductory textbook entitled Formal Language Theory: Integrating Experimentation and Proof. An attempt has been made to keep the conceptual and notational distance between the textbook and toolset as small as possible. The book treats most concepts and algorithms both theoretically, especially using proof, and through experimentation, using Forlan. In contrast to some books on formal language theory, the book emphasizes the concrete over the abstract, providing numerous, fully worked-out examples of how regular expressions, finite automata, grammars and programs (its substitute for Turing machines) can be designed and proved correct.

The textbook is still a work-in-progress, but drafts are available. The most recent full draft is from September 2012. But a revision is being made during the fall of 2018, in a series of steps. The LaTeX source for the draft is part of Forlan's distribution. It is released under the GNU Free Documentation License.

Standard ML

Very little knowledge of Standard ML is required in order to use Forlan in simple ways. But users who are more familiar with ML will be able to use Forlan in more sophisticated ways. The book assumes no previous knowledge of Standard ML. In order to understand and extend the implementation of Forlan, though, one must have a good working knowledge of Standard ML.

More information about SML can be obtained from Robert Harper's draft book Programming in Standard ML. Alternatively, one can read one of the following books:

People who are already familiar with Objective Caml (OCaml), can consult a comparison of Objective Caml and Standard ML.

Before installing Forlan, one must first install the Standard ML of New Jersey (SML/NJ) compiler, which can be obtained from www.smlnj.org. Install the most recent version. There are installers for macOS and Windows, and you can build a Linux version from source.

The Standard ML Basis Library is included as part of the SML/NJ distribution and contains many useful functions.

The best way to run ML is as a sub-process of the Emacs text editor, using the SML mode for Emacs.

Forlan Manual

A manual for Version 4.9 of Forlan is available. The manual is also available as a compressed tarball, and as a zip archive. The root HTML file is index.html

Installing Forlan on Linux, macOS and Windows

Here are instructions for downloading and installing Forlan Version 4.9 on a machine running Linux, macOS or Windows.

The instructions assume that SML/NJ has been installed in the following locations:

Linux/macOS Distribution: /usr/local/smlnj
Binary: /usr/local/bin/sml
Windows Distribution: C:\Program Files\SMLNJ
Binary: C:\Program Files\SMLNJ\bin\sml

Copy the SML/NJ binary (sml) from the bin directory of the SML/NJ distribution to the binary directory (folder), if necssary. And make sure the binary directory is on your shell's search path. Test this by running sml, and making sure it starts correctly. (You can exit by typing CTRL-d on Linux/macOS or CTRL-z on Windows.)

If you install SML/NJ somewhere else, you'll have to modify the instructions accordingly. But you'll also have to make appropriate edits to the script forlan (under Linux/macOS) or forlan.bat (under Windows).

Installing Forlan under Linux and macOS

Transfer the compressed tarball forlan-min-src-4.9.tgz to a temporary directory. (This tarball contains the minimum source needed to compile Forlan. If you plan to make changes to Forlan, you should get the full source. See below.) Then, run the following commands, after changing directory to the temporary directory:

  gunzip forlan-min-src-4.9.tgz
  tar xf forlan-min-src-4.9.tar
  cd forlan-min-src-4.9
  ./build-heap-image

This will cause an SML/NJ heap image for Forlan to be written to the file forlan-heap.x86-linux (Linux) or forlan-heap.x86-darwin (macOS Intel). If you get an error saying that sml was not found, refer to the above instructions for making sure sml is on your shell's search path.

Then move the bash shell script forlan to /usr/local/bin, and move the heap image to /usr/local/smlnj/bin/.heap.

Installing Forlan under Windows

Transfer the zip archive forlan-min-src-4.9.zip to a temporary directory. (This zip archive contains the minimum source needed to compile Forlan. If you plan to make changes to Forlan, you should get the full source. See below.) Extract the directory forlan-min-src-4.9 from this archive.

Then, run the following commands, after changing directory to the temporary directory:

  cd forlan-min-src-4.9
  sml
  Control.trackExn := false;
  CM.make "forlan.cm";
  open TopLevel;
  Export.export();

This will cause an SML/NJ heap image for Forlan to be written to the file forlan-heap.x86-win32. If you get an error saying that sml was not found, refer to the above instructions for making sure sml is on your shell's search path.

Then move the shell script forlan.bat to the directory C:\Program Files\SMLNJ\bin, and move the heap image to the directory C:\Program Files\SMLNJ\bin\.heap.

Create a desktop and/or startup menu shortcut to the command

  C:\Program Files\SMLNJ\bin\forlan.bat

Set the working directory for the shortcut to the one where your personal SML and Forlan files will reside.

JForlan — a Java Graphical Editor for Forlan Finite Automata and Trees

JForlan is a Java program for creating and editing Forlan automata and trees: finite automata, regular expression finite automata, parse trees, regular expression trees, and program trees. JForlan automatically maintains the connections between the components of automata and trees, as those components are repositioned using the mouse. And it handles the conversion of diagrams from and to Forlan's concrete syntax. JForlan can be invoked directly (as a standalone applications) or from Forlan.

Forlan Project Distribution

Version 4.9 of the Forlan Project distribution is available as a compressed tarball. The distribution contains:

The Forlan distribution is hosted on GitHub, and may be cloned or forked there: https://github.com/alleystoughton/Forlan/.

The Forlan toolset and JForlan are released under the GNU General Public License, and the textbook is released under the GNU Free Documentation License.

Contributors

Alley Stoughton created the Forlan project, designed, implemented and documented its modules, and wrote the textbook.

Leonard Lee and Jessica Sherrill designed and implemented graphical editors for Forlan finite automata (JFA), and regular expression and parse trees (JTR), respectively. Their work was unified and enhanced (of particular note was the addition of support for program trees) by Srinivasa Aditya Uppu, resulting in an initial version of JForlan. Subsequently, Kenton Born carried out a major redevelopment of JForlan, resulting in JForlan Version 1.0. Further revisions, by Alley Stoughton, led to JForlan Versions 2.0 and 2.1.


Alley Stoughton (alley.stoughton@icloud.com)