Qi (programming language)

From Wikipedia, the free encyclopedia

 The references in this article would be clearer with a different or consistent style of citation, footnoting, or external linking.

Qi is a functional programming language developed by Dr Mark Tarver and introduced in its current form in April 2005 under the GNU GPL license. Although 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. The combination of all these features within the Lisp environment makes Qi in many senses a rationalization and modernization of Lisp. Qi won its creator a Promising Invention Award from the State University of New York in 2003.

Contents

[edit] Notable Features

Though Qi shares the afore-mentioned features with modern functional programming languages like Standard ML and Haskell, Qi includes features which are quite specific to the language. Qi's most significant divergence from ML and Haskell is the use of sequent calculus notation to define types. Qi incorporates an efficient compiler for compiling sequent calculus notation into an extended Prolog that incorporates embedded function calls. Since Prolog is itself a programming language, the type specification language of Qi is Turing-equivalent, which in practice means that type checking in Qi is not guaranteed to terminate.

This fact initially generated some controversy, but the author pointed out that non-termination was an inevitable by-product of increased expressiveness, and that a preference for a less expressive terminating type system represented a value judgment. In the absence of user-defined types, the Qi type checker will in fact terminate in all cases.

The use of Prolog as an intermediate formalism for the compilation means that Qi includes an embedded Prolog as part of the distribution. Qi also includes an embedded compiler-compiler Qi-YACC which was used to code some of the source for Qi.

Qi also includes backtracking on demand in a manner similar to Screamer.

[edit] The Qi Core Language

The Qi core language is a simplification of the Lisp language. Functions are written in prefix form. Symbols, numbers, strings and characters are all self-evaluating if typed to 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))

[edit] Type Checking

Static typing is optional in Qi and is enabled by (tc +) and disabled by (tc -). The type system recognises symbols, 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)

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 S0,...,Sn are sequent patterns. Note that S1, ...,Sn 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 fatuos) 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

[edit] 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:

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

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

(ask [ man plato ] )
(ask [ man snoopy ] )
(ask [ dog X ] )
(ask [ man M ] )

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

(defprolog 

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

[edit] 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. 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).

[edit] Development

As of October 2007, Qi has been updated several times since the first release (6.1) in April 2005 and the current release, 9.1, released September 2007, runs under both Windows and Linux on the CLisp, CMU Common Lisp, Allegro Common Lisp and SBCL platforms. 9.0 incorporated an optional factorising code compiler (Turbo-E) for optimising pattern-matching. In a comparative shoot-out against several Lisp programs and OCaml, 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 is scheduled to appear later in 2007.

[edit] External links