Qi (programming language)

Qi (programming language)

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.

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 [http://www.lambdassociates.org/studies/study03.htm 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.

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))

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

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

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.

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 { } := [ | ] ; := [ | ] ; := [] ;) (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 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 [http://www.lambdassociates.org/studies/study10.htm 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.

External links

* [http://www.lambdassociates.org/ Lambda Associates] is the home for Qi.
* [http://www.lambdassociates.org/yacc.htm] discusses Qi-YACC.
* [http://www.lambdassociates.org/FPQi.pdf Functional Programming in Qi] is the standard text.
* [http://www.lambdassociates.org/prolog.htm] discusses Qi Prolog.
*Online code studies in Qi are available [http://www.lambdassociates.org/studies/index.htm on the main site] .
*Qi has its own [http://groups.google.co.uk/group/Qilang news group] .
*Qi sources are also hosted on the [http://code.google.com/p/qilang/ Google Code Project Hosting] .


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Programming language — lists Alphabetical Categorical Chronological Generational A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that… …   Wikipedia

  • Programming language theory — (commonly known as PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages and programming language features. It is a multi disciplinary field, both… …   Wikipedia

  • Programming Language Design and Implementation — (PLDI) is one of the ACM SIGPLAN s most important conferences. The precursor of PLDI was the Symposium on Compiler Optimization, held July 27–28, 1970 at the University of Illinois at Urbana Champaign and chaired by Robert S. Northcote. That… …   Wikipedia

  • Programming Language for Business — or PL/B is a business oriented programming language originally called DATABUS and designed by Datapoint in the early 1970s as an alternative to COBOL because its 8 bit computers could not fit COBOL into their limited memory, and because COBOL did …   Wikipedia

  • programming language — ➔ language * * * programming language UK US noun [C] ► COMPUTER LANGUAGE(Cf. ↑computer language) …   Financial and business terms

  • programming language — Language Lan guage, n. [OE. langage, F. langage, fr. L. lingua the tongue, hence speech, language; akin to E. tongue. See {Tongue}, cf. {Lingual}.] [1913 Webster] 1. Any means of conveying or communicating ideas; specifically, human speech; the… …   The Collaborative International Dictionary of English

  • Programming Language One — Programming Language One, oft als PL/I (auch PL/1, PL1 oder PLI) abgekürzt ist eine Programmiersprache, die in den 1960er Jahren von IBM entwickelt wurde. Die Bezeichnung PL/1 ist vor allem in Deutschland gebräuchlich. Ursprünglich wurde PL/I… …   Deutsch Wikipedia

  • Programming Language 1 — noun A computer programming language which combines the best qualities of commercial and scientific oriented languages (abbrev PL/1) • • • Main Entry: ↑programme …   Useful english dictionary

  • Programming Language —   [engl.], Programmiersprache …   Universal-Lexikon

  • Programming language specification — A programming language specification is an artifact that defines a programming language so that users and implementors can agree on what programs in that language mean.A programming language specification can take several forms, including the… …   Wikipedia

  • programming language — noun (computer science) a language designed for programming computers • Syn: ↑programing language • Topics: ↑computer science, ↑computing • Hypernyms: ↑artificial language …   Useful english dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”