Qi (programming language)
Qi is a functional programming language developed by Dr Mark Tarver and introduced in April 2005 under the GNU GPL license. An upgraded version was reimplemented and issued as Qi II in November 2008. Qi II is currently free for personal and educational use and a commercial license for producing closed source is included in the language guide available from the home site.
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.
QI and the 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 [1], 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, fuelled 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 desiderata which Qi was designed to meet. The solution should:
- be Lisp compatible -- as the most widely used dialect of Lisp, the solution should be written in Common Lisp and run under Common Lisp.
- be free for non commercial and educational use.
- be compact -- programs should not be any longer than the same programs written in Common Lisp
- be simple to learn -- Semantics and syntax should be learnable by a child.
- 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. [2]
- have the characteristics of a modern functional programming language. By these Dr. Tarver includes pattern-directed list handling, static typing, currying, and partial applications.
- not be simply a clone of Haskell or ML -- this is part of what constitutes 'future proofing' the solution.
- 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.
- 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.
- be well documented and theoretically secure -- Qi is fully documented, with formal correctness proofs and has a canonical textbook which is also online. [3]
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. [4] 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.
The Qi 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 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 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.6GHz 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).
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 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).
Prior to this, an earlier version, 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 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.
References
External links
- Lambda Associates is the home for Qi.
- What's New is the announcement page for Qi II.
- Discusses Qi-YACC.
- Functional Programming in Qi (second edition) is the new online standard text for Qi II. The printed version comes with a commercial license.
- Functional Programming in Qi is an earlier standard text for the original Qi.
- Discusses Qi Prolog.
- Online code studies in Qi and presentations about Qi are available on the main site.
- Qi has its own Google group.
- Qi sources are also hosted on the Google Code Project Hosting.
- Programming Kung Fu Blog dedicated to instructional articles on Qi
If you like SEOmastering Site, you can support it by - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 and more...
