Software Engineers Handbook/Language Dictionary/Qi

Qi is a functional programming language developed by Dr Mark Tarver and introduced in April 2005. A new version was reimplemented and issued as Qi II in November 2008. The first version was free software, licensed under GPL. But, as GPL was perceived as unfriendly to commercial use, Qi II is available via two proprietary licenses: one for personal and educational use, and another for producing closed source software.

Qi is written in Lisp. It includes most of the features common to modern functional programming languages such as pattern-matching, currying, partial applications, guards and (optional) static type checking.

L21 project

Qi was developed as part of the L21 project, which aims to modernise Lisp to meet the challenges of twenty-first century computing. In his lecture, Dr Tarver outlined a series of current challenges to Lisp which he argued were damaging to the wider use of the language. Specifically he identified Common Lisp's lack of pattern-matching, inconsistency with respect to lambda calculus theory (partial applications being missing), procedural contamination and lack of static typing. These deficiencies, Tarver argued, had led to a general abandonment of Lisp as a teaching vehicle at university level with a concomitant lack of graduating Lisp programmers. Tarver characterised this lack of support for teaching Lisp at university as leading to a 'classic vicious cycle', whereby the small number of graduating students fluent in Lisp encouraged a transition away from using Lisp programmers which, in turn, fueled the perception that Lisp was a dying language and fed the decline in the teaching of Lisp.

In the same lecture, Tarver suggested that this problem could either be tackled at the industry or the university end, but that tackling the problem at the industry end required a champion with large amounts of capital to invest in Lisp. Tarver instead proposed to tackle the problem at the university end, by modernising Common Lisp in such a way to make it 'future proof' for at least 25 years. His characterisation of an adequate modernisation of Lisp was summarised in ten requirements which Qi was designed to meet. The solution should:

1. be Lisp compatible—as the most widely used dialect of Lisp, the solution should be written in Common Lisp and run under Common Lisp.
2. be free for non commercial and educational use.
3. be compact—programs should not be any longer than the same programs written in Common Lisp
4. be simple to learn -- Semantics and syntax should be learnable by a child.
5. be efficient -- The solution should generate programs which are at least as fast as their hand-coded Lisp equivalents. In practice, Qi programs have proven to be often faster.
6. have the characteristics of a modern functional programming language. By these Dr. Tarver includes pattern-directed list handling, static typing, currying, and partial applications.
7. not be simply a clone of Haskell or ML—this is part of what constitutes 'future proofing' the solution.
8. be computationally adequate—meaning that the language is 'adequate for the needs of the programmers of the day'. Dr Tarver characterises 'computational adequacy' as 'a large, vague and important notion' and believes that the extension of this concept changes through time. Common Lisp he characterises as 'computationally inadequate' due to the lack of specification for features such as foreign languages interface and graphics. Tarver believes that Qi itself still needs to achieve this goal through the development of standard libraries for graphics, web interfaces and foreign language handling.
9. be [metaprogrammable and customizable—in that the user should be free to program the syntax of the language. To achieve this Qi has both M-expression and S-expression level syntax for all its syntax, as well as an "eval" function that maps M-expressions to S-expressions; which can make it easier to do metaprogramming in Qi than in Lisp. In terms of customization Qi has an explicit "sugar" keyword to allow the user to program the Qi reader to accept custom syntax.
10. be well documented and theoretically secure—Qi is fully documented, with formal correctness proofs and has a canonical textbook which is also online.

Architecture

Qi makes use of the logical notation of sequent calculus to define types. This type notation, under Qi's interpretation, is actually a Turing complete language in its own right. This notation allows Qi to assign extensible type systems to Common Lisp libraries and is thought of as an extremely powerful feature of the language.

Qi compiles sequent calculus to Qi Prolog (which is incorporated into the Qi environment) via the Abstract Unification Machine (AUM). The AUM acts as a functional programming analog to the Warren abstract machine generating virtual instructions from what is essentially an extended lambda calculus. The Qi compiler maps AUM instructions to Common Lisp, and these the Lisp compiler compiles into byte code or machine code depending on the Lisp platform. The Qi environment also includes a compiler-compiler Qi-YACC which is used in the encoding of Qi to handle the parsing and reading of Qi code. Qi is thus bootstrapped or written (largely) in itself apart from a few Common Lisp functions.

Development

As of January 2009, Qi has been updated several times since the first release (6.1) in April 2005, and the current release, Qi II 1.07, released in July, 2009, runs under both Windows and Linux on the CLISP, CMU Common Lisp, Allegro Common Lisp and Steel Bank Common Lisp (SBCL) platforms.

Qi II incorporates the following improvements over the original Qi, as follows (quoted, with minor edits, from the Lambda Associates' Qi II What's New page):

• A complete reimplementation of Qi from the ground up.
• New license.
• Type secure lazy evaluation on demand.
• Improved programmable syntax.
• 4 speed compiler which utilises type information.
• Improved integration with Common Lisp.
• Runs under LispWorks.
• Common functions made polyadic.
• Improved connection to Prolog.
• Rule closures for embedding sequent reasoning into Qi functions.
• Improved handling on dependent types.
• A type secure class system in a library along with Functional Programming in Qi (second edition).
• Completely documented in Functional Programming in Qi (second edition).

Before this, an earlier version, 9.0, incorporated an optional factoring code compiler (Turbo-E) for optimising pattern-matching. In a comparative shoot-out against several Lisp programs and Objective Caml, Qi 9.0 performed at the speed of the fastest and most heavily hand-optimised Lisp version. A release (Qi/Tk) incorporating a type secure version of Tcl/Tk embedded into Qi appeared in March 2009.

In January 2010, a successor version to Qi II was announced designed to implement many of the ideas in Tarver's lectures. The new version is designed to run under Common Lisp, Clojure and Python and is also targeted for the Dalvik Virtual Machine. Contributors include Dr Mark Tarver, Carl Shapiro of Google and Stefan Tampe.

Alternatively, the developers and proponents of the ideas set forth in Qi, have come up with a successor to Qi, dubbed Shen (Programming Language). Shen is a more compact language as compared to Qi, although it is mostly compatible with Qi. As such, further development on Qi may be stalled , with the result being more effort spent on Shen.

Core language

The Qi core language is a simplification of the Lisp language. Functions are written in prefix form. Symbols, variables, booleans, numbers, strings and characters are all self-evaluating if typed at the top level. Here are some examples.

Here is the traditional Hello world program in Qi:

(output "Hello, world~%")

Lists are constructed with [ .... ] with spaces separating the elements of the list.

[76 trombones]

A factorial function using pattern matching:

(define factorial
0 -> 1
N -> (* N (factorial (- N 1))))

A lambda function in Qi that multiplies its input by 2.

(/. X (* X 2))

The membership function using pattern-matching over lists. (Qi largely follows the Edinburgh [Prolog] syntax convention for matching (i.e. variables are headed in uppercase), except that spaces are used instead of commas to separate items.)

(define member
_ [] -> false
X [X | _] -> true
X [_ | Y] -> (member X Y))

A function using guards that finds the first number greater than N in a list.

(define find_greater
N [] -> (error "no number greater than ~A.~%" N)
N [M | _] -> M where (> M N)
N [_ | Ns] -> (find_greater N Ns))

Type checking

Static typing is optional in Qi and is enabled by (tc +) and disabled by (tc -). The type system recognises symbols, variables, strings, booleans, numbers and characters as primitive types. Primitive type operators are list, * (product), --> and array. Here are some examples

(3-) (tc +)
true

(4+) hello
hello : symbol

(5+) "hello"
"hello" : string

(6+) 686.8
686.8 : number

(7+) #\z
#\z : character

(8+) true
true : boolean

(9+) (@p 1 a)
(@p 1 a) : (number * symbol)

(10+) [1 2 | [3]]
[1 2 3] : (list number)

(11+) (* 8)
#<CLOSURE :LAMBDA [X4] [* X3 X4]> : (number --> number)

(12+) X
X : variable

Functions are explicitly typed as with Hope. [A] is an acceptable abbreviation for the type (list A). Here is the polytype signature of member in Qi.

(define member
{A --> [A] --> boolean}
_ [] -> false
X [X | _] -> true
X [_ | Y] -> (member X Y))

User-defined concrete types are defined in Qi sequent calculus. Qi sequent calculus uses a single conclusion formalism. Sequent rules have the form

<side conditions>
S1;
.
.
.
Sn;
____
S0;

where S₀,...,S_n are sequent patterns. Note that S₁, ...,S_n may be empty.

Side conditions in Qi are either (a) boolean tests or (b) local assignments. Here are some examples; the first uses a boolean side-condition to define an enumeration type 'fruit' containing 'apples', 'pears' and 'oranges' as the only inhabitants.

(7+)(datatype fruit

if (element? F [apples pears oranges])
______________________________________
F : fruit;)
fruit : unit

(8+) apples : fruit
apples : fruit

(9+) plums : fruit
error: type error

Here a type 'alphanum' is defined that is the union of the types of symbols and numbers.

(10+) (datatype alphanum

X : number;
___________
X : alphanum;

X : symbol;
___________
X : alphanum;)
alphanum : unit

(11+) [76 trombones]
[76 trombones] : (list alphanum)

Here is a (rather fatuous) use of local assignments in a type.

(12+) (datatype ordering

if (number? X)
if (number? Y)
let Z (* X 2)
if (= Y Z)
__________________
[X Y] : ordering;)
ordering : unit

(13+) [2 3] : ordering
error: type failure

(14+) [2 4] : ordering
[2 4] : ordering

Lastly a more interesting recursive type for binary numbers.

(15+) (datatype binary

if (element? X [0 1])
_____________
X : zero-or-one;

X : zero-or-one;
__________________
[X] : binary;

X : zero-or-one; Y : binary;
____________________________
[X | Y] : binary;

X : zero-or-one, [Y | Z] : binary >> P;
___________________________________________
[X Y | Z] : binary >> P;)
binary

(16+) (define complement
\calculates the complement of a binary number\
{binary --> binary}
[0] -> [1]
[1] -> [0]
[1 N | X] -> [0 | (complement [N | X])]
[0 N | X] -> [1 | (complement [N | X])])
complement : (binary --> binary)

(3+) (complement [0 1 0 1])
[1 0 1 0] : binary

Qi Prolog

Qi Prolog is a version of Prolog implemented in Qi, using a standard Edinburgh syntax, embedding the Prolog program in a string. This is a basic example of Qi Prolog:

(m-prolog
"dog(snoopy).
man(socrates).
man(plato).
mortal(X) :- man(X).")

And this is how to ask questions to the Prolog database:

(prolog? (man plato))
(prolog? (man snoopy))
(prolog? (dog X))
(prolog? (man M))

Here is Einstein's Riddle in Qi Prolog. Under CMU Lisp on a 2.6 GHz Intel machine, Qi Prolog solves (ask [einsteins_riddle M]) in 0.24s (M = German) (300 KLIPS).

(m-prolog

"einsteins_riddle(Fish_Owner) :- einstein(Houses, Fish_Owner).

einstein(Houses, Fish_Owner) :-
=(Houses, house, norwegian, _, [house, _, _, _, milk, _], _, _]),
member([house, brit, _, _, _, red], Houses),
member([house, swede, dog, _, _, _], Houses),
member([house, dane, _, _, tea, _], Houses),
iright([house, _, _, _, _, green], [house, _, _, _, _, white], Houses),
member([house, _, _, _, coffee, green], Houses),
member([house, _, bird, pallmall, _, _], Houses),
member([house, _, _, dunhill, _, yellow], Houses),
next_to([house, _, _, dunhill, _, _], [house, _, horse, _, _, _], Houses),
member([house, _, _, _, milk, _], Houses),
next_to([house, _, _, marlboro, _, _], [house, _, cat, _, _, _], Houses),
next_to([house, _, _, marlboro, _, _], [house, _, _, _, water, _], Houses),
member([house, _, _, winfield, beer, _], Houses),
member([house, German, _, rothmans, _, _], Houses),
next_to([house, norwegian, _, _, _, _], [house, _, _, _, _, blue], Houses),
member([house, Fish_Owner, fish, _, _, _], Houses).

member(X,[X | _]).
member(X,[_ | Z]) :- member(X,Z).

next_to(X, Y, List) :- iright(X, Y, List).
next_to(X, Y, List) :- iright(Y, X, List).

iright(L, R, [L | [R | _]]).
iright(L, R, [_ | Rest]) :- iright(L, R, Rest).")

Qi Prolog includes an interface for calling Qi functions and the possibility of mode declarations in a similar manner to DEC-10 Prolog.

Qi YACC

Qi YACC is an untyped compiler-compiler based on a top-down recursive descent parsing strategy. It is derived from the TDPL (top-down parsing language) and is the basis for much of the inbuilt parsing in Qi. Qi YACC takes Backus–Naur Form code directly as a pseudo-code:

<sentence> := <assignment> | <goto>
<assignment> := goto <symbol>

becomes

(defcc <sentence>
<assignment>;
<goto>;)

(defcc <assignment>
goto <symbol>;)

The following is a Qi-YACC program that parenthesises any input occurring between { ... }s.

(2-) (defcc <paren>
{ <paren> } <paren1> := [<paren> | <paren1>];
<token> <paren> := [<token> | <paren>];
<e> := [];)
<paren>

(3-) (defcc <paren1>
<paren>;)
<paren1>

(4-)(defcc <token>
-*- := (if (element? -*- [{ }]) #\Escape -*-);)
<token>

(5-) (compile <paren> [{ a { b } } c])
[[a [b]] c]

Qi-YACC is more extensively discussed on the home site (see External Links).

External links

• official website of Lambda Associates
• Qi has its own Google group
• Qi sources are also hosted on the Google Code Project Hosting
• Programming Kung Fu Blog for Qi instructional articles