Qi (programming language) - AbsoluteAstronomy.com

Functional programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

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

Currying

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...

, 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

Common Lisp

Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...

's lack of pattern-matching, inconsistency with respect to lambda calculus

Lambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped 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

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:

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
Formal semantics of programming languages
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...

and syntax should be learnable by a child.
be efficient
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...

-- 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.
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
Metaprogramming
Metaprogramming is the writing of computer programs that write or manipulate other programs as their data, or that do part of the work at compile time that would otherwise be done at runtime...

and customizable—in that the user should be free to program the syntax of the language. To achieve this Qi has both M-expression
M-expression
In computer programming, M-expressions were intended to be the expressions used to write functions in the Lisp programming language. Data to be manipulated using M-expressions was to be written using S-expressions...

and S-expression
S-expression
S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...

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
Syntactic sugar
Syntactic sugar is a computer science term that refers to syntax within a programming language that is designed to make things easier to read or to express....

.
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

Sequent calculus

In proof theory and mathematical logic, sequent calculus is a family of formal systems sharing a certain style of inference and certain formal properties. The first sequent calculi, systems LK and LJ, were introduced by Gerhard Gentzen in 1934 as a tool for studying natural deduction in...

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

Warren abstract machine

In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine and has become the de facto standard target for Prolog compilers.-Purpose:The purpose of...

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

Compiler-compiler

A compiler-compiler or compiler generator is a tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine...

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.

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)
# : (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

Sequent calculus

. Qi sequent calculus uses a single conclusion formalism. Sequent rules have the form

S₁;
.
.
.
S_n;
____
S₀;

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

Zebra Puzzle

The zebra puzzle is a well-known logic puzzle. It is often called Einstein's Puzzle or Einstein's Riddle because it is said to have been invented by Albert Einstein as a boy; it is sometimes claimed that only 2% of the population can solve it....

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

Top-down parsing language

Top-Down Parsing Language is a type of analytic formal grammar developed by Alexander Birman in the early 1970s in order to study formally the behavior of a common class of practical top-down parsers that support a limited form of backtracking...

) and is the basis for much of the inbuilt parsing in Qi. Qi YACC takes Backus–Naur Form

Backus–Naur form

In computer science, BNF is a notation technique for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols.It is applied wherever exact descriptions of...

code directly as a pseudo-code:

:= |
:= goto

becomes

(defcc
;
;)

(defcc
goto ;)

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

(2-) (defcc
{ } := [ | ];
:= [ | ];
:= [];)

(3-) (defcc
;)

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

(5-) (compile [{ 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

Microsoft Windows

Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...

and Linux

Linux

Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

on the CLISP

CLISP

In computing, CLISP is an implementation of the programming language Common Lisp originally developed by Bruno Haible and Michael Stoll for the Atari ST...

, CMU Common Lisp, Allegro Common Lisp

Allegro Common Lisp

Allegro Common Lisp is a commercial implementation of the Common Lisp programming language developed by Franz Inc. Allegro CL provides the full ANSI Common Lisp standard with many extensions...

and Steel Bank Common Lisp

Steel Bank Common Lisp

Steel Bank Common Lisp is a free Common Lisp implementation that features ahigh performance native compiler, Unicode support and threading....

(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

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

(Turbo-E) for optimising pattern-matching. In a comparative shoot-out against several Lisp programs and Objective Caml

Objective Caml

OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...

, 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

Tcl

Tcl is a scripting language created by John Ousterhout. Originally "born out of frustration", according to the author, with programmers devising their own languages intended to be embedded into applications, Tcl gained acceptance on its own...

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

External links

Lambda Associates

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; print version comes with a proprietary 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 for Qi instructional articles

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.