LIPL: a Little Idiotic Programming Language

CS731 Software Development Practicum

Author: Sam Lee
Organization: Queens College - CUNY

1   About

This is a term project for cs731, offered in Spring 2008 semester. An interpreter of LIPL, a tiny functional programming language, is designed and its interpreter is implemented in Haskell programming language. The LIPL interpreter has following features:

  • Eager evaluation
  • Hindley-Milner style type inference

Objective of the project is to learn about software development using functional programming style and Haskell programming language.

2   Obtaining the Project

The project can be obtained from: http://www.lipl.googlepages.com/lipl.zip

Otherwise, you can check out the project from svn repository using an svn client. If you don't have an svn client, TortoiseSVN is recommended for Windows.

svn co http://svn2.assembla.com/svn/cs731/lipl/trunk lipl

will check out latest version of LIPL interpreter to the directory called``lipl``.

3   Project Structure

When you unzip the release or check out from the svn repository, you should have the following directory structure:

lipl/
    doc/
    src/
    lib/
  • lipl is project root.
  • doc contains documentations.
  • src contains Haskell source code for the interpreter.
  • lib contains libraries written in LIPL.

4   Installation and Running

4.1   Steps

To install LIPL interpreter, you need to follow the following steps:

  1. Compile the project (using Cabal or GHC).

  2. Add the directory containing the compiled binary to PATH environment variable (or, move the binary to a directory included in PATH environment variable).

  3. Copy lib/core.lipl to a directory where the interpreter can find:

    • any directory listed in LIPLPATH environment variable
    • ~/.lipl directory

4.2   Quick Start

If you already have GHC and Cabal on your computer, you can quickly build and run the LIPL interpreter with following steps (*nix environment assumed):

shell> cd lipl #go to project root
shell> runhaskell Setup.lhs configure --prefix=/usr/local
shell> runhaskell Setup.lhs build
shell> runhaskell Setup.lhs install
shell> mkdir ~/.lipl
shell> cp /usr/local/share/Lipl-0.1/lib/core.lipl ~/.lipl
shell> lipl #assuming /usr/local/bin is in PATH
LIPL> (+ 1 2)
type: Int
3
LIPL> :q
bye
shell>

4.3   Requirements

To build and install the interpreter, a Haskell compiler is required. Since the project is a Cabal package, Cabal can be used to build and install the interpreter. Cabal is included in GHC version 6.8.* , so no separate installation for Cabal is needed.

4.4   Haskell Compiler

The interpreter can be compiled with GHC (the Glasgow Haskell Compiler) version 6.8.*. Other Haskell compilers or different GHC version might be able to compile the interpreter. But, only the specified GHC version is used to test the project.

Windows installer can be downloaded from http://haskell.org/ghc/download_ghc_682.html#windows .

After installing GHC, make sure the bin directory (probably C:\ghc\ghc-6.8.2\bin for Windows) is included in PATH environment variable so that ghc executable can be invoked from anywhere.

GHC comes with several executables:

ghc
compiles Haskell code to native binary. Example usage: ghc --make Main.hs
ghci
is an interactive Haskell interpreter.
runghc
interprets Haskell source code. Example usage: runghc Main.hs
runhaskell
same as runghc

4.5   Build

Building the project can be done in many ways.

4.5.1   Using Cabal

At the project root, type the following:

shell> runhaskell Setup.lhs configure
shell> runhaskell Setup.lhs build
shell> runhaskell Setup.lhs install

First command configures the project. Optionally, you can set installation path by passing --prefix option. For example, if you want to install the LIPL interpreter to C:\lipl:

shell> runhaskell Setup.lhs configure --prefix="C:\lipl"

Then, execute build and install commands:

shell> runhaskell Setup.lhs build
shell> runhaskell Setup.lhs install

If the project has been configured with --prefix="C:\lipl", the interpreter, lipl.exe, can be found in C:\lipl\bin\lipl.exe.

Follow instructions in Installation section to finish installation process.

4.5.2   Manual Build

To manually build the interpreter without using Cabal:

  • go to src directory under project root.
  • type ghc --make -o lipl Main.hs

This will create lipl.exe under src directory. You can move lipl.exe to C:\lipl\bin\lipl.exe if you want.

4.6   Installation

Assuming lipl.exe is under C:\lipl\bin, add C:\lipl\bin to PATH environment variable so that you can start the interpreter from any directory.

The interpreter tries to find and load core.lipl (prelude library) that implements various useful functions. It searches core.lipl in following order:

  1. current working directory
  2. directories listed in LIPLPATH environment variable
  3. in .lipl directory under HOME directory (C:\Users\yourid or C:\Documents and Settings\yourid)

core.lipl is can be found under lib directory, which is under project root (lipl/lib/core.lipl). So, copy it to a directory of your choice. Then set LIPLPATH environment variable to the directory where you copied core.lipl to. Or, copy core.lipl to C:\Users\yourid\.lipl\core.lipl (the directory C:\Users\yourid\.lipl is created when the interpreter is run for the first time).

4.7   Running the Interpreter

After finishing installation, you can type the following to start LIPL REPL (read eval print loop):

shell> lipl
LIPL>

At the LIPL> prompt, you can type LIPL expressions to evaluate them. Or, you can type :? to print help menu:

LIPL> :?
:? help
:s current type environment
:q quit
:e current environment
:c clear environment
:l <file> load <file>
:r <file> load <file> on clean environment
:s
prints types of currently available functions (type substitution environment)
:q
quits the repl
:e
prints identifiers and their values in the current environment. Built-in functions are not shown.
:c
cleans all bound identifiers. You are left with built-in functions only.
:l file.lipl
loads file.lipl . file.lipl should not define a function that is already in the environment.
:r file.lipl
cleans the environment first then loads file.lipl .

5   LIPL Tutorial

LIPL tutorial is a separate document. It can be reached at: this link. It explains how a stack based postfix calculator can be implemented in LIPL. Source code of the calculator, calc.lipl, can be found in lib/calc.lipl.

6   LIPL Reference

LIPL language reference is a separate document, located here.

7   Project Timeline

The project was proposed in the beginning of Spring 2008 semester, during the week of January 27th, 2008. And it was submitted on May 28th, 2008 (total 18 weeks). Below is weekly summary of the project progress.

  • Project proposal and language specification.
    • 1st week (Jan 27): Project proposal. Brainstorm about the language.
    • 2nd week (Feb 3): Specify syntax of the language.
    • 3rd week (Feb 10): Write specification of syntax and semantics.
  • Parser and evaluator.
    • 4th week (Feb 17): Start writing parser.
    • 5th week (Feb 24): Start writing evaluator.
    • 6th week (Mar 2): Adding basic arithmetics functions.
    • 7th week (Mar 9): Deviation from the specification (allowing prefix, postfix, infix).
    • 8th week (Mar 16): Revert back to the specification (stick to prefix only). Adding boolean operations, comparison functions, and conditional expression.
    • 9th week (Mar 23): Adding buggy environment (function definition and let expression).
    • 10th week (Mar 30): Disallowing recursive let expression (recursive definitions only works for function definition).
  • Type inference.
    • 11th week (Apr 6): Start type inference.
    • 12th week (Apr 13): Try to fix buggy type inference for let expressions and lambda expressions (improper variable capture).
    • 13th week (Apr 20): Fix more bugs involving let expressions and lambda expressions.
    • 14th week (Apr 27): Fix bugs for recursive function definitions.
    • 15th week (May 4): Refactoring monad stack.
    • 16th week (May 11): Fix bugs for variable capture.
  • Documentation.
    • 17th week (May 18): Start documentation.
    • 18th week (May 25): Add example programs.

8   Implementation Summary

Each LIPL expression goes through 3 phases:

  1. parse
  2. type inference
  3. evaluation

8.1   Parse

During parse phase, abstract syntax tree is built from string representation of a LIPL expression. The abstract syntax tree is represented with Haskell data structures. For example, (+ 1 2) is parsed into At pos (Expr [PrimFun "+", Int 1, Int 2]) where pos is source position (file name, line number, and column number) where the expression (+ 1 2) is located, and At, Expr, PrimFun, and Int are Haskell data constructors.

By recording source position with actual abstract syntax tree, better error message can be printed.

Actual implementation uses Parsec library that comes with GHC.

8.2   Type Inference

After successfully building abstract syntax tree from an expression, the tree is traversed and its type is inferred. Type inference makes sure ill-formed expressions are rejected before evaluation. For example, type inference phase fails to infer the type of (+ 1 'a') because the function + expects two Ints but a Char is passed to it.

Unification algorithm is used to infer type of each expression. Maintaining substitution (table of type variables and type expressions) and generation of new type variables are implemented in a custom monad.

8.3   Evaluation

Well-typed expressions are evaluated (normalized) in applicative order (eager evaluation). For example, both (g a) are evaluated then passed to function f, in (f (g a) (g a)).

Currying is implemented with closures. For example, (f a b) will be evaluated so that a closure is formed where the 1st formal parameter of f is bound to the actual parameter, a. Then, the closure is applied to the next actual parameter, b.

Evaluation is done inside a monad simulating a stack of environments: key value pairs where key is identifiers appearing in expressions and value is value bound to them.

8.4   Monad Transformer Library

Custom monads and monad transformers are written along with typeclasses to construct a monad (REPL monad) that can perform IO actions, type inference, evaulation, and error reporting. Type inference monad and evaluation monad (custom monads) are written in similar fashion as mtl monads are written, so that those monads can be combined with IO monad and error reporting monad (from base and mtl libraries that come with GHC) to construct the REPL monad used in the interpreter.

9   Source

Source code of the interpreter is written in literate Haskell style. Algorithms in the source code can be buggy and comments faulty.

  1. Settings.lhs
  2. Stack.lhs
  3. Utils.lhs
  4. LangData.lhs
  5. LangUtils.lhs
  6. Error.lhs
  7. Type.lhs
  8. TIMonadClass.lhs
  9. TIMonad.lhs
  10. EvalMonadClass.lhs
  11. EvalMonad.lhs
  12. PosMonadClass.lhs
  13. PosMonad.lhs
  14. REPLMonad.lhs
  15. ParseUtils.lhs
  16. Parser.lhs
  17. TParse.lhs
  18. TCheck.lhs
  19. Evaluator.lhs
  20. CoreLib.lhs
  21. MainUtils.lhs
  22. Main.lhs

Below are example programs written in LIPL:

  1. core.lipl is a prelude library written in LIPL that is loaded when the interpreter starts.
  2. calc.lipl is a postfix calculator written in LIPL. LIPL Tutorial is based on this.

10   Epilogue

Learning Haskell and functional programming was enjoyable experience. Some of the impressions I had as a new comer to Haskell include:

  • Debugging a Haskell program can be difficult
  • Modularity improves debug-ability
  • Monad transformers improve modularity
  • Unwrapping monad transformers and making magic lift work can be tedious (an IDE might help)

Things that I should have done but did not include:

  • Writing unit tests
  • Allowing recursive let expressions in LIPL
  • Adding ADT and pattern matching to LIPL

11   Document Generation

To generate HTML documents (including this), go to lipl/doc/tools directory and run gen.py:

shell> cd lipl # to project root
shell> python doc/tools/gen.py

Python, Docutils, and Pygments are needed to run gen.py.

12   References

To learn about Haskell programming and functional programming in general, these resources were used:

[DAUME]Daumé III, Hal (2002) Yet Another Haskell Tutorial. Retrieved January 1, 2008, from http://darcs.haskell.org/yaht/yaht.pdf
[GRABMULLER]Grabmüller, Martin (2006) Monad Transformers Step by Step. Retrieved March 1, 2008 from http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html
[HUDAK89]Hudak, Paul (1989) Conception, Evolution, and Application of Functional Programming Languages. ACM Computing Surveys 21 (3): 359-411
[HUDAK]Hudak, Paul et al. (2000) A Gentle Introduction to Haskell, Version 98. Retrieved January 1, 2008 from http://www.haskell.org/tutorial/
[NEWBERN]Newbern, Jeff. All About Monads. Retrieved April 1, 2008 from http://www.haskell.org/all_about_monads/html/index.html
[OSULLIVAN]O'Sullivan, Bryan et al. (2007) Real World Haskell (beta). Retrieved May 1, 2008 from http://book.realworldhaskell.org/beta/
[WADLER]Wadler, Philip (1992) The Essence of Functional Programming. Invited Talk, 19th Symposium on Principles of Programming Languages, ACM Press, Albuquerque. Retrieved March 1, 2008 from http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps

For implementation of LIPL evaluator and type inference, these resources were used:

[CARDELLI85]Cardelli, Luca and Wegner, Peter (1985) On Understanding Types, Data Abstraction, and Polymorphism. ACM Computing Surveys 17 (4): 471-522
[CARDELLI]Cardelli, Luca (1987) Basic Polymorphic Typechecking. Retrieved April 1, 2008 from http://lucacardelli.name/Papers/BasicTypechecking.pdf
[HENDERSON]Henderson, Peter (1980) Functional Programming: Application and Implementation. Prentice Hall.
[PEYTONJONES]Peyton Jones, Simon (1987) The Implementation of Functional Programming Languages. Prentice Hall. Retrieved May 1, 2008 from http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm
[PJONES]P. Jones, Mark (2000) Typing Haskell in Haskell. Retrieved April 1, 2008 from http://web.cecs.pdx.edu/~mpj/thih/
[TANG]Tang, Jonathan. Write Yourself a Scheme in 48 Hours: A Haskell Tutorial. Retrieved January 1, 2008 from http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html