KLIC User’s Manual

March 1995

(Revised at June 1997)

This manual corresponds to KLIC version 3.002

Copyright © 1994, 1995 Institute for New Generation Computer Technology

 — The Detailed Node Listing —

Introduction

Description of Predicates and Methods

KL1 Language

Generic Objects

Shorthand Notation for Argument Pairs

Inserting C Language Code Inline

Builtin and Library Features

Common Operations

Atomic Data

Symbolic Atoms

Integer Atoms

Floating Point Numbers

Structured Data

Functor Structures

Lists

Vectors

Strings

Handling Program Code as Data

Unix Interface

Input and Output

Input and Output with C-like Interface

Input and Output with Prolog-like Interface

Using KLIC

Compiling Programs with KLIC

Running Programs Compiled with KLIC

Tracing Program Execution

Trace Controlling Commands

Installation

Distributed Memory Parallel Implementation of KLIC

Running Programs of Distributed KLIC

Shared-Memory Implementation of KLIC 

Running Programs of Shared-Memory KLIC

Terms and Conditions for Use of ICOT Free Software

1. Purposes and Background of ICOT Free Software.

The Institute for New Generation Computer Technology (ICOT) had been promoting the Fifth Generation Computer Systems project under the commitment of the Ministry of International Trade and Industry of Japan (the MITI). Since April 1993, ICOT has been promoting the Follow-on project to the FGCS project. This follow-on project aims to disseminate and further develop FGCS technology. The FGCS project and the Follow-on project (collectively, the Project) have been aimed at creating basic technology for novel computers that realizes parallel inference processing as their core mechanism, and contributing toward the progress of computer science by sharing innovative knowledge and technology with the research community worldwide.

Innovative hardware and software parallel inference technology has been under development through the Project, which involves varieties of advanced software for experiments and evaluation. This software, being at a basic stage of research and development, should be disseminated widely to the research community.

According to the aims of the Project, ICOT has made this software, the copyright of which does not belong to the government but to ICOT itself, available to the public in order to contribute to the world, and, moreover, has removed all restrictions on its usage that may have impeded further research and development in order that large number of researchers can use it freely to begin a new era of computer science.

This program together with any attached documentation (collectively, the Program) is being distributed by ICOT free of charge as ICOT Free Software.

2. Free Use, Modification, Copying and Distribution

Persons wanting to use the Program (Users) may freely do so and may also freely modify and copy the Program. The term "modify," as used here, includes, but is not limited to, any act to improve or expand the Program for the purposes of enhancing and/or improving its function, performance and/or quality as well as to add one or more programs or documents developed by Users of the Program.

Each User may also freely distribute the Program, whether in its original form or modified, to any third party or parties, PROVIDED that the provisions of Section 3 (NO WARRANTY) will ALWAYS appear on, or be attached to, the Program, which is distributed substantially in the same form as set out herein and that such intended distribution, if actually made, will neither violate or otherwise contravene any of the laws and regulations of the countries having jurisdiction over the User or the intended distribution itself.

3. NO WARRANTY

The program was produced on an experimental basis in the course of the research and development conducted during the project and is provided to users as so produced on an experimental basis. Accordingly, the program is provided without any warranty whatsoever, whether express, implied, statutory or otherwise. The term “warranty” used herein includes, but is not limited to, any warranty of the quality, performance, merchantability and fitness for a particular purpose of the program and the nonexistence of any infringement or violation of any right of any third party.

Each user of the program will agree and understand, and be deemed to have agreed and understood, that there is no warranty whatsoever for the program and, accordingly, the entire risk arising from or otherwise connected with the program is assumed by the user.

Therefore, neither ICOT, the copyright holder, or any other organization that participated in or was otherwise related to the development of the program and their respective officials, directors, officers and other employees shall be held liable for any and all damages, including, without limitation, general, special, incidental and consequential damages, arising out of or otherwise in connection with the use or inability to use the program or any product, material or result produced or otherwise obtained by using the program, regardless of whether they have been advised of, or otherwise had knowledge of, the possibility of such damages at any time during the project or thereafter. Each user will be deemed to have agreed to the foregoing by his or her commencement of use of the program. The term "use" as used herein includes, but is not limited to, the use, modification, copying and distribution of the program and the production of secondary products from the program.

In the case where the program, whether in its original form or modified, was distributed or delivered to or received by a user from any person, organization or entity other than ICOT, unless it makes or grants independently of ICOT any specific warranty to the user in writing, such person, organization or entity, will also be exempted from and not be held liable to the user for any such damages as noted above as far as the program is concerned.

1 Introduction

This manual describes a portable implementation of KL1 called KLIC, developed at Institute for New Generation Computer Technology as a part of the Fifth Generation Computer national project of Japan and its follow-on project.

KL1 is a concurrent logic programming language based on Guarded Horn Clauses (GHC, in short). KL1 has very simple and concise syntax and semantics and yet provides very powerful features for concurrent computation.

KLIC compiles KL1 programs to C programs. A C compiler of the host system then compiles the C programs to relocatable objects, which will then be linked together with the runtime library of KLIC (see section How KLIC Compiler Works). Thus, the system is independent from the hardware architecture of the host system. Also, the system is written so that only minimal features of Unix are used to assure portability.

1.1 Description of Predicates and Methods

1.1.1 Predicates and Methods

Unlike other logic programming language systems, KLIC provides two kinds of procedures, predicates and generic methods. Predicates define relations on their arguments and their semantics is fixed. Generic methods, (or methods, simply) are defined by objects they are applied to. Thus, their semantics depends on the object applied.

Sometimes the same operation is provided by both predicates and methods. For example, obtaining an element of a string can be done by either of the following two.

Body Predicate on builtin: string_element +String +Index -Element

Body Method on string: element +String +Index -Element

The former is a builtin predicate of the system. Predicate invocations are written as follows.

ModuleName:PredicateName(Arguments, …)

In case of the predicate string_element mentioned above, it is defined as a builtin predicate and thus no module name is needed in its invocation. Thus, an invocation is written as follows.

string_element(String, Index, Element)

In general, a module name may come first with a colon before the predicate name. Some predicates do not have any arguments. In such cases, parentheses enclosing arguments are also omitted.

The latter is a generic method defined on the objects of class string. Method invocation is written as follows.

generic:MethodName(Object, OtherArguments, …)

In case of the method element mentioned above, its invocation is written as follows.

generic:element(String, Index, Element)

The same operation may be effected using either a predicate or a method. For example, obtaining the third element (element number 2) of a string S into E can be done by either of the following invocations.

string_element(S, 2, E)
generic:element(S, 2, E)

Note that, while the predicate string_element is only for obtaining an element of a string, a generic method invocation can also be used to obtain an element of similar object. For example, an element of a vector (one-dimensional array) can also be obtained by the same invocation.

1.1.2 Messages

KL1 programs often consist of many processes. Processes often communicate one another using streams. Streams are actually lists of messages. Lists are made of cells called cons cells with two fields car and cdr, just as in Lisp or similar languages. Thus, when used as message streams, the car part of a cons cell contains the message and the cdr contains the rest of the stream.

Some standard features of the KLIC system are also provided as processes with message stream interface. An example of such message described in this manual follows.

Message on C-like I/O: putc +C

This means that a message named putc is accepted as a message to a C-like I/O process interface stream. The message has one argument called C in this case.

To send a message to a message stream, the variable referring to the message stream should be instantiated with a cons cell whose car contains the message and cdr contains the rest of the stream. Thus, when S is a stream to C-like I/O and character with code 10 is to be output, the following unification should be made.

S = [putc(10)|T]

Here, the variable T is given the rest of the stream and thus any following messages to the stream should be sent to this variable.

1.1.3 Argument Modes

Arguments of predicates, methods or messages may have specific input/output mode. Input arguments are read by invocation of predicates or methods; the invocation will be suspended if any of the input arguments are left undefined. Output arguments are given a value by the invocation.

In the description of predicates and methods, input arguments are marked with a + and output arguments are marked with a -. Some arguments are not either read or given value. Such arguments are marked with a ?.

1.2 Reporting Bugs and Sending Comments

Please report bugs and comments on the KLIC system and this document to the following mail address.

klic-bugs@icot.or.jp.

There is a mailing list for users of KLIC. This mailing list is used for announcement from the developers on known bugs, fixes or availability of new releases. The same mailing list can also be used for communication among users. To subscribe to the mailing list, please send your request to the following address.

klic-requests@icot.or.jp

2 KL1 Language

KL1 is a programming language for describing concurrent computation based on Guarded Horn Clauses (GHC, in short). GHC belongs to a family of languages called concurrent logic programming languages or committed-choice logic programming languages. Languages that belong to the family are, for example, Concurrent Prolog, Parlog, Fleng, Strand and Janus. These languages have simple and concise syntax and semantics and yet provide very powerful features for concurrent computation.

Here, a very rough and informal description of the KL1 language is given. More detailed and accurate specification are planned to be supplied in future (hopefully).

2.1 Basic Execution Mechanism

The following is an example of a small KL1 program that defines a part of quicksort program.

Example 1: Quicksort

:- module quicksort.

sort(X, Y) :- sort(X, Y, []).

sort([], Y, Z) :- Y = Z.
sort([P|X], Y, Z) :-
    partition(P, X, X1, X2),
    sort(X1, Y, [P|Y1]),
    sort(X2, Y1, Z).

partition(_, [], S, L) :-
    S = [],
    L = [].
partition(P, [W|X], S, L) :- W =< P |
    S = [W|S1],
    partition(P, X, S1, L).
partition(P, [W|X], S, L) :- W >= P |
    L = [W|L1],
    partition(P, X, S, L1).

The first line, :- module quicksort declares that this program module will be called quicksort (see section Modules).

Execution of a KL1 program is a (possibly parallel) repetitive reduction of given goals using program clauses. Each clause has the following form.

PredicateName(Argument pattern …) :- Guard | Body.

When a goal is to be reduced, clauses for the predicate of the goal will be inspected. For clauses with matching argument pattern, their guard parts are tested. All the clauses with matching argument pattern and satisfied guard conditions are candidates to be used in the reduction. Only one of them, arbitrarily chosen, will be used and the original goal will be replaced by the goals in the body of the clause chosen.

If no guard condition tests are required, the guard part along with the vertical bar can be omitted.

2.2 Predicates

Predicates of KL1 corresponds to subroutines of Fortran or functions of C. Predicates are defined by a collection of clauses with the same predicate name and the same number of arguments in their heads. Unlike in some other languages, predicates are identified not only by their names but also by their arities (numbers of arguments). To identify predicates with the same name but different arities, the notation Predicate/Arity is used in this manual.

In the example of the quicksort program, two predicates with the same name sort, with 2 and 3 arguments respectively, are defined (see section Basic Execution Mechanism). Such predicates are referred to as sort/2 and sort/3 respectively.

The order of clauses defining a predicate does not affect the meaning. For example, a predicate for computing maximum of two integer values can be defined as follows.

max(X, Y, M) :- X >= Y | M = X.
max(X, Y, M) :- X =< Y | M = Y.

Exactly the same predicate can be defined by reversing the order of the clauses as follows.

max(X, Y, M) :- X =< Y | M = Y.
max(X, Y, M) :- X >= Y | M = X.

When a set of clauses are to be used only when another set of clauses are known not to be applicable, the keyword otherwise should be put in between the two sets of clauses. For example, the above ‘max’ predicate may be defined as follows.

max(X, Y, M) :- X >= Y | M = X.
otherwise.
max(X, Y, M) :- M = Y.

The meaning of the predicate is almost the same except that this version succeeds after unifying ‘M’ with ‘Y’ even when ‘X’ or ‘Y’ does not have an integer value, while the two previous versions will fail.

The otherwise directive specifies that clauses after the directive should not be applied unless all the clauses preceding the directive are known not to be applicable, even with any information (variable bindings) may become available afterwards. This feature should not be confounded with the alternatively directive, which specifies that clauses preceding the directive should be given priority to the clauses following (see section Clause Preference).

2.3 Modules

KL1 provides module structure for dividing large programs into many modules. A module consists of one or more predicates. Definition of a module starts with a module declaration of the form :- module Module. Clauses defining predicates in the module will follow. The end of the file or another module declaration ends the definition of the module.

In the quicksort example, the first line:

:- module quicksort

declares that this program module is called quicksort (see section Basic Execution Mechanism).

Predicates defined with the same name and arity but in different modules are considered to be different predicates. Thus, when necessary, the notation Module:Predicate/Arity is used to explicitly specify the module name.

2.4 Goals

A Goal is a unit of execution of KL1. Goals are associated with a predicate. A goal is reduced to zero or more simpler goals by applying one of the clauses defining the predicate.

Goals are written as:

Predicate(Arguments, …)

or simply as the following.

Predicate

when the predicate has no arguments.

When the predicate is not in the same module, the syntax is either:

Module:Predicate(Arguments, …)

or as the following.

Module:Predicate

For example, a module named main that uses the quicksort module might be defined as follows (see section Basic Execution Mechanism).

Example 2: Module using quicksort

:- module main.

main :-
    X = [9,2,8,3,6,7,4,1,5],
    builtin:print(X),
    quicksort:sort(X, Y),
    builtin:print(Y).

Here, the body goal quicksort:sort(X, Y) is associated with the predicate sort/2 of the module quicksort.

2.5 Initial Goal

All KLIC programs start from the initial goal main:main, i.e., the predicate main with no arguments defined in the module main. The example of the module main (see section Goals) is an example of a main program.

Command line arguments are not passed to the initial goal. Predicates to access command line arguments are provided separately (see section Predicate Interface).

2.6 Generic Objects

Generic objects provide a framework to extend the KL1 language with new data types and their operations. There are three kinds of generic objects, namely, data objects, consumer objects and generator objects.

Generic objects are created by pseudo-predicates generic:new. Generic data objects are similar to usual KL1 data. Operations on data objects are defined by their generic methods. Methods are invoked by pseudo-predicates generic:Method. Consumer and generator objects look like variables to normal KL1 programs and operations on them are implicit by unification.

Many of the standard types of KLIC, vectors and strings, for example, are actually implemented as generic data objects. For them, builtin predicates can also be used as aliases for generic methods. For example, set_vector_element(Original, Index, NewElement, New) means the same as generic:set_element(Original, Index, NewElement, New).

2.6.1 Creating Generic Objects

Generic objects are created by the following pseudo-predicate.

generic:new(ClassName, Object, Args, …)

ClassName should be a symbolic atom which names the object class. By this invocation, a new generic object is created and associated with Object. Parameters for creation can be specified by Args. The meaning of Args depends on each object class.

2.6.2 Guard Methods of Generic Data Objects

Clause selection depending on generic data objects can be done by calling guard methods. Guard methods have the following format.

generic:Method(Object, Input, …):Output:…

Input, … specify input arguments. If any of the input arguments are left undefined, this invocation will be suspended. Output:… specify output arguments, which are returned from the method. If some concrete value is specified as an Output, guard unification of the specified and returned values will be made. Some guard methods have no output arguments, in which case colon and following Output are omitted.

2.6.3 Body Methods of Generic Data Objects

Operations on generic data objects can be done by calling body methods. Body methods have the following format.

generic:Method(Object, Args, …)

Unlike guard methods, input and output arguments are not syntactically distinguished. The method to be called can be determined in runtime. To do that, an alternative format is provided.

generic:generic(Object, Functor)

With this format, Functor should be (or become in runtime) a functor structure of the format Method(Args, …). Invocation will be suspended until Functor will become instantiated.

2.7 Priority Specification

Goals have execution priority associated with them. Execution priority is specified by a positive integer value. Goals with larger priority values are (usually) executed earlier than goals with smaller priority values. However, priority specifications are no more than suggestions and actual implementations may or may not strictly obey them.

Body goals can have execution priority specification in one of the following formats.

Goal@priority(AbsPrio)
Goal@lower_priority(RelPrio)
Goal@lower_priority

Here, AbsPrio and RelPrio should be a non-negative integer constant, or a variable which should be instantiated to a non-negative integer later. In the current implementation, negative priority values are interpreted as zero.

With the absolute priority specification, the goal with the specification will have the priority value specified by AbsPrio. With the relative priority specification, the goal will have priority less than the priority of the parent goal by the amount specified by RelPrio. The specification Goal@lower_priority has the same effect as Goal@lower_priority(1). Goals without any priority specifications will have the same priority as their parents.

The highest possible priority is the largest possible integer value, which depends on host systems (see section Integer Atoms). The initial goal main:main has the maximum priority possible for the host system (see section Initial Goal).

2.8 Clause Preference

Predicates of KL1 may have nondeterminacy; more than one clause may be applicable. In such cases, preference among clauses may be specified using the alternatively directive.

When the keyword alternatively is put in between two sets of clauses, clauses preceding it are preferred to those following it. However, when clauses preceding the alternatively directive cannot be applied directly due to lack of information (insufficient instantiation of variable values), the clauses following it may be used. This feature is often useful in controlling speculative computation depending on progress of computation.

The feature is not be confounded with the otherwise feature (see section Predicates). For example, consider the following two predicates.

p(1, Y, R) :- R = a.
alternatively.
p(X, 2, R) :- R = b.

q(1, Y, R) :- R = a.
otherwise.
q(X, 2, R) :- R = b.

When the first argument is still undefined and the second is 2, the predicate p may return b to the third argument using its second clause. The predicate q will wait until the value of the first argument becomes available. Thus, if the first argument eventually becomes 1, the predicate q is guaranteed to return a, but the predicate p may return either a or b.

2.9 Shorthand Notation for Argument Pairs

KL1 programs often require passing two arguments as a pair to a predicate: one as input and the other as output. KLIC provides a shorthand notation for such cases.

2.9.1 Paired Arguments and their Expansion

The head and goals in both guard and body parts of a clause can have argument pairs specified by a single variable name attached to the head or goals by a hyphen character. We call such pseudo variable an argument pair name. An example is shown here.

p(X,Y)-Pair :- q(X)-Pair, s(Z)-Pair, r(Pair,Y), t(Z)-Pair.

The pseudo-variable Pair is an argument pair name. Such a clause is interpreted the same as the following clause.

p(X,Y,P0,P) :- q(X,P0,P1), s(Z,P1,P2), r(P2,Y), t(Z,P2,P).

Occurrences of argument pair names attached to the head or goals by a hyphen character are interpreted as a pair of two different variables added at the end of the argument lists. In what follows, we call the two variables generated from an paired argument an expanded pair.

The second of an expanded pair of a goal is the same as the first of the expanded pair of the next goal with the same argument pair name. In the example above, P1 appearing as the third argument of the goal of q/3 also appears as the second argument of s/3, as originally they both have the same argument pair name Pair.

The first of an expanded pair in the head will be the same as the first of the expanded pair in the first goal in the clause with the same argument pair name. The second of an expanded pair in the head will be the same as the second of the expanded pair in the last goal with the same argument pair name.

In the above example, the first of the expanded pair P0 in the head appears again as the second argument of the first goal calling q/3, and P, the second of the expanded pair in the head, appears again as the third argument of the last goal of t/3.

If the argument pair name appears only in the head, two variables of the expanded pair are unified in the body. For example, a clause:

p(X)-Y :- q(X).

is expanded into the following.

p(X,Y0,Y) :- Y0=Y, q(X).

An argument pair name may appear at a usual argument position rather than being attached to the head or goals, as does the first argument of the goal for r/2 in the above example. In such a case, it is expanded to a single variable. This variable is the same as the second of the last expanded pair and is also the same as the first of the next expanded pair. Thus, in the above example, Pair appearing as the first argument of r/2 is expanded into P2, which is the same as the third argument of s/3 and the second argument of t/3.

Arbitrarily many argument pair names can be specified for a head or a goal. For example, a clause such as:

p-X-Y :- q-X, r-Y, s-Y-X.

is interpreted as follows.

p(X0,X,Y0,Y) :- q(X0,X1), r(Y0,Y1), s(Y1,Y,X1,X).

Sometimes, specifying normal arguments after some argument pair names is desirable. This can be done by connecting them with a plus (+) character. For example:

p-X+Y :- q-X+35, r(Y), s+Y-X.

is interpreted as follows.

p(X0,X,Y) :- q(X0,X1,35), r(Y), s(Y,X1,X).

Note that the expansion rules for paired arguments described above are position sensitive for goals. However, this does not at all mean that the execution order of body goals are constrained anyhow.

Also note that the argument pair notation is no more than macro expansion of clauses. One predicate may have clauses some of which written in the argument pair notation and others in the usual notation.

2.9.2 Macros for Paired Arguments

To fascilitate the usage of paired arguments, KLIC provides the following macros to be used in place of a goal.

S <= M

Expanded to S0 = [M|S1] where S0 and S1 are expanded pair for the argument pair name S.

M => S

Expanded to [M|S0] = S1 where S0 and S1 are the expanded pair for the argument pair name S.

S += E

S -= E

S *= E

S /= E

Expanded to S1 := S0 + E0 etc, where S0 and S1 are the expanded pair for the argument pair name S.

S <== X

Expanded to S1 = X, where S0 and S1 are the expanded pair for the argument pair name S. S0 does not appear in the expansion; the original value of the paired argument for S will be lost, and the next occurrence of S will mean X instead. This feature is normally used with a non-paired occurrence of the argument pair name. For example:

…, p-S, q(S), S <== X, r-S, …

means the following.

…, p(S0,S1), q(S1), S2 = X, r(S2,S3), …

2.9.3 Usage of Paired Arguments

Some examples of typical usage of paired arguments are given here.

The following program is for summing up elements of a list of integers.

sum(List,Sum) :- sum(List)+0+Sum.

sum([])-Acc.
sum([H|T])-Acc :- Acc += H, sum(T)-Acc.

Here, the paired argument Acc plays the role of an accumulator.

The following program inverts the sign of the elements of a list of integers.

inv(List,Inv) :- inv(List)+Inv-[].

inv([])-Inv.
inv([H|T])-Inv :- MH := -H, Inv <= MH, inv(T)-Inv.

2.10 Inserting C Language Code Inline

The inline C code feature allows specifying C programs to be inserted in the object code within KL1 programs. This feature is somewhat similar to the asm statements of C.

Appropriateness of inserted C code totally depends on internal implementation schemes of the KLIC system, which may be altered in future. Thus, general users are not recommended to use this feature.

2.10.1 Inline Insertion at the Top of Files

At the top of a source file, strings to be inserted in the object C program can be specified in the following way.

:- inline:"C Program Text to be Inserted".

The specified text is inserted in the object C program after standard declarations and before any user-defined modules.

There can be any number of such inline specification. A typical example is as follows.

:- inline:"#include <stdio.h>"

As inserted C programs are written as string constants of KLIC, doubleqoute characters have to be escaped with a backslash character. A typical example is as follows.

:- inline:"#include \"myheader.h\""

It might also be a good idea to define macros and functions here, that are invoked from the inline code in clause guards.

2.10.2 Inline Insertion in the Guard

Inline insertion specification can also appear as a guard goal with one of the following forms.

inline:"C Program Text"
inline:"C Program Text":[ArgSpec, …]

With either format, the C program text is literally inserted in the object code corresponding to the guard part, except that percent signs (%) in the program text string specify special formatting. The following table lists special format characters after percent signs and what they mean.

<digit>

The name of the C variable corresponding to the <digit>-th ArgSpec (zero origin). Note that only up to 10 such arguments are allowed.

f

The name of the C label to goto when this clause should fail or suspend.

%

The percent character itself, i.e., percent characters should be doubled. Be careful when you specify format strings for printf.

ArgSpec has one of the following formats.

Variable+Type

Specifies that the value of the variable is used within the inserted program text. Object code for synchronization with availability of the variable value and checking of the value type is generated by the compiler.

Variable-Type

Specifies that variable is given a value within the inserted program text. This has to be the first occurence of the variable. The compiler assumes that, after executing the inserted code, the variable will have value of Type.

The Type field should be one of the following.

any

Anything, including uninstantiated variables

bound

Any bound value

atomic

An atomic value (a symbolic atom or an integer)

int

An integer

atom

An symbolic atom

list

A list structure

functor

A functor structure (including generic object)

object

A generic data object

object(Class)

A generic data object of Class

Values are referenced without any indirections for all types except for any. For an input (+) mode argument, the generated code makes sure that, before executing the inserted program text, the argument will have the value of the specified type directly, without indirect references. For an output (-) mode argument, the compiler assumes that, after executing the inserted program text, the variable will have the value of the specified type directly, without any indirect references, and uses that information for optimization. If you cannot be sure of this for output mode arguments, specify any, which may be less efficient but safe.

2.10.3 C-Level Representation of KL1 Terms

Note that C language types of the C variables and KL1 language types of corresponding KL1 values are not the same. All the C variables corresponding to a KL1 value have the type q which means almost nothing except that it occupies a single word. KL1 values are somehow encoded (with attached tag etc). For example, an integer 3 of KL1 is not represented by the bit pattern corresponding to integer 3 in of the language C.

This document is not intended to describe all the details of the data representation scheme of KLIC. Such description and programs depending on it will be obsoleted anyway by future revisions of the KLIC system. However, manipulation of integer values may be the easiest and useful in most C programs written inline. Thus, we’ll describe macros for data conversion for integers. They are unlikely to be changed in future versions.

To obtain the integer value of a variable corresponding to an integer value of KL1, use the macro intval(X). To obtain KL1 representation of integer in C, use the macro makeint(N).

2.10.4 Examples

Example 1: Adding Two Integers

Two integers can be added by the following clause.

    p(X,Y,Z) :- W := X+Y | Z = W.

The same function can be realized using the inline insertion feature as follows.

p(X,Y,Z) :-
  inline:"%2 = makeint(intval(%0)+intval(%1));":
    [X+int, Y+int, W-int] | Z=W.

The inserted text will be as follows.

x0 = makeint(intval(a0)+intval(a1));

Where variables a0 and a1 correspond to X and Y, and x0 to W in the KL1 program. Note that the Z and W are unified in the body.

Example 2: Comparing Two Integers

Two integers can be compared by the following clause.

p(X,Y) :- X > Y | …

The same function can be realized using the inline insertion feature as follows.

p(X,Y) :-
  inline:"if (intval(%0) <= intval(%1)) goto %f;":
    [X+int, Y+int] | …

The inserted text will be as follows.

if (intval(a0) <= intval(a1)) goto p_2_interrupt;

Where variables a0 and a1 correspond to X and Y in the KL1 program, and p_2_interrupt is a label automatically generated by the compiler.

2.10.5 Some Hints on Using the Inline C Code Feature

• Whenever possible, avoid using the inline feature. Revisions of the KLIC system may obsolete your code.
• If multiple lines are to be inserted consecutively, specify all of them in one single inline specification. Otherwise, they might be interleaved by other code for the guard. Newlines are allowed within the inserted program text.
• Do not forget to prefix doublequotes and backslahes with a backslash. Do not forget also to write two percent signs to insert one. If you would like to say hello to the world, you should write such a program as follows.

  hello :-
      inline:"printf(\"Hello, world\\n\");" |
      …
  

  Note the backslashes before doublequotes within the inlined code and doubled backslash before n. If you put only one backslash before n, it will become a newline code after inline expansion; it will appear within a string constant in the expanded C program. It fortunately works the same in this case, except that some C compilers may generate a warning message.

• If your program with inline code does not work as you expect it to, the best way to find the problem may be to look into the C code generated.

3 Builtin and Library Features

This chapter describes builtin and library features of KLIC.

3.1 Common Operations

Some predicates are used commonly for all the data types or are independent from any data types.

3.1.1 Unification

Guard Predicate on builtin: = ?X ?Y

Checks whether X and Y are unifiable without giving values to variables outside the clause.

Body Predicate on builtin: = ?X ?Y

Unifies X and Y. If X has no value yet and Y already has some defined value, the value of Y is given to X. If Y has no value and X has some, the reverse takes place. If both do not have values yet, two variables are made to mean the same variable. If both have values, they are matched. If both are the data structures of the same kind, this unification operation is made recursively to corresponding elements of two structures.

3.1.2 Synchronization

Guard Predicate on builtin: wait +X

Waits until instantiation of X.

3.1.3 Comparison and Hashing

Guard Predicate on builtin: compare +X +Y -R

Compares X and Y, and returns the result in R. The result is an integer value less than, equal to, or greater than 0, when X is less than, equal to, or greater than Y, respectively.

The comparison is made by the standard order. This predicate can compare data of any types. If both X and Y are of the same numeric type, normal numerical comparison is made. Note that integer and floating point numbers are not of the same type; their comparison may not be meaningful. Two strings are compared in (so-called) dictionary order.

The order of any two data of different types is somehow defined by the system. However, the ordering is guaranteed to be kept only within a single executable program. If some data sequence is saved into a permanent file using the ordering provided by this predicate, the same program recompiled or linked with some other programs may or may not recognize the sequence as ordered. Different programs, of course, may use different ordering.

Both X and Y have to be instantiated enough for making the comparison. For example ‘f(V) @< f(W)’ will suspend if not both ‘V’ and ‘W’ are instantiated. On the other hand, ‘f(1,V) @< f(2,W)’ will succeed immediately, as the order can be determined without looking into values of ‘V’ or ‘W’.

The absolute value of the result R may have some meaning for certain data types. When comparing two strings, the absolute value of the result is one more than the index of the first differng element (a la strcmp of C).

Some generic objects may not implement their comparison methods, and, in such cases, their comparison will result in a fatal error.

Guard Predicate on builtin: @< +X +Y

Guard Predicate on builtin: @=< +X +Y

Guard Predicate on builtin: @>= +X +Y

Guard Predicate on builtin: @> +X +Y

Compares X and Y with the standard order. If the condition is not satisfied, the invocation of the predicate fails.

Guard Predicate on builtin: \= +X +Y

Compares X and Y and succeeds if and only if their principal functors are different. For atomic values, it means that they are different; for functor structures, it means that either they have different functor names or different arity. For generic objects, the predicate succeeds when two objects are of different classes.

Note that ‘f(a) \= f(b)’ fails, as the two terms have the same principal functor. Note also that, floating point numbers are generic objects and thus ‘X \= Y’ fails for any two floating point numbers, as they are objects of the same class.

Guard Predicate on builtin: hash +X -H

Computes the hash value of X and returns it in H. The hash value is a non-negative integer value.

Hashing function may look into elements of structured data recursively. X has to be instantiated enough to compute hash value. Some generic objects may not implement hash methods, and, in such cases, their hash value becomes a constant.

3.1.4 Execution Status

Guard Predicate on builtin: current_priority -P

Returns the priority value of the reduced goal to P. See section Priority Specification, for further details on the priority mechanism.

Body Predicate on builtin: current_node -Node -NumNodes

On a parallel implementation, the predicate returns the processor number executing the predicate in Node and the total number of (pseudo-) processors available in NumNodes. Processor numbers have zero origin. Thus, the maximum value returned to Node is one less than the value returned to NumNodes. On a sequential implementation, 0 is returned to Node and 1 to NumNodes.

3.1.5 Debugging

Body Predicate on builtin: unbound ?X -Result

Checks whether X is already bound to some concrete value or not and returns the Result.

If the toplevel of X is already defined, Result is unified with a single-element vector of the form {X}. When X is bound to a structured value, its elements may or may not be bound yet.

If X is not bound yet, Result is unified with a three element vector of the form {Addr1, Addr2, X}, where Addr1 and Addr2 are integers indicating the current address of the variable X somehow. Note that variable addresses may change in time by garbage collection, automatic data migration in parallel implementations or any such low level implementational reasons; they are no more than debugging hints.

Do not use this predicate in normal application programs. Unlike the var/1 feature of sequential Prolog, variables once judged as unbound can be bound in the next instance on parallel implementations. Thus, usage of this predicate should be restricted to programs that have to go into low level details of the system implementation, such as debugging tools.

3.2 Atomic Data

KLIC provides two kinds of atomic data types, numerical and symbolic.

For numerical data, KLIC provides integer and floating point number data types and operations to manipulate them. Floating point numbers are implemented as generic objects and thus actually are not an atom.

Note that implicit type conversions between integer and floating point data are never made. Integer numbers and floating point numbers are treated completely separately.

Whether given data is atomic or not can be tested by the following guard predicates.

Guard Predicate on builtin: atomic +X

Tests whether X is atomic or not. Floating point numbers are not judged as atomic by this predicate.

3.2.1 Symbolic Atoms

Symbolic atoms are atomic data objects that give names to notions. Symbolic atoms with the same name are the same and with different names are different.

3.2.1.1 Notation of Symbolic Atoms

The notation of symbolic atoms is similar to Edinburgh Prolog, which is one of the following.

• A lower case letter followed by a sequence of any number (including zero) of letters, digits or underlines.

  Examples:

  icot   kl1   a_symbolic_atom_with_a_long_name
  

• A sequence of special characters (some of ~, +, -, *, /, \, ^, <, >, =, ` (backquote), :, ., ?, @, #, $, &).

  Examples:

  +   >=   :-   =:=
  

• A sequence of any characters quoted by single quotes. If single quote characters are to be included, they should be doubled or escaped by a backslash.

  Examples:

  'Hello world'    'an atom with \'singlequotes\' in it'
  

• Special one-character atoms. There are three of them, which are !, | and ;. Also, | has a special meaning in list notation (See section Notation of Lists).
• A special atom [], which usually is used to represent ends of lists (see section Lists). Spaces can be in between [ and ].

Important differences with Edinburgh Prolog syntax are the following.

• A vertical bar (|) means a one-character atom. Even when it is used as an operator, it is not treated the same as a semicolon (;) but as a different atom.
• A pair of curly braces ({}) does not stand for a symbolic atom. It means a vector with no elements (see section Notation of Vectors).

3.2.1.2 Operations on Symbolic Atoms

Whether a given data object is a symbolic atom or not can be tested by the following guard predicate.

Guard Predicate on builtin: atom +X

Tests whether X is a symbolic atom or not.

To maintain the uniqueness of atoms, the system gives a unique number to each atom and maintains the association between atom name strings and atom numbers. Association of symbolic atoms and their names can be known by the following predicates defined in the module atom_table.

Predicate on atom_table: make_atom +String -Atom

When given a String, returns Atom with that name. If such an atom does not exist, a new atom is registered.

Predicate on atom_table: atom_number +Atom -Number

Internal serial number for Atom is returned to Number as an integer value.

Predicate on atom_table: get_atom_string +Atom -String

The name string of Atom is returned to String.

Predicate on atom_table: intern +String -Result

The same as atom_table:make_atom, except that the returned value is a functor structure of the form normal(Atom).

Predicate on atom_table: get_atom_name +Atom -Result

The same as atom_table:get_atom_string, except that the returned value is a functor structure of the form normal(String).

Although symbolic atoms are associated with their name strings, do not use them for string manipulation. String data objects provide much more functionality and better performance (see section Strings).

3.2.2 Integer Atoms

KLIC provides integer data with usually 28 or 60 bits as its basic standard feature. The width depends on the C compiler you use. It is 4 bits shorter than the width of type long int.

Guard Predicate on builtin: integer +X

Tests whether X is an integer atom.

3.2.2.1 Notation of Integers

KLIC provides several ways to denote integer constants.

• Usual decimal notation: optional minus sign followed by a sequence of decimal digits. Examples: ‘123’, ‘-35’.
• Based notation: optional minus sign followed by a sequence of decimal digits specifying the base (1 to 36), an apostrophe, and then a sequence of digits of the base, that are digits and alphabets (case insensitive). Examples: ‘2'1010’, ‘16'0D0a’. Value of an integer with base 1 is the number of ones in the digit sequence; for example ‘1'10110’ means 3.
• Character code notation: optional minus sign followed by a digit 0, an apostrophe and a character. Examples: ‘0'a’ means the character code of lowercase letter a.

The above listed constant notations can be used in both KL1 programs and KL1 data read in by Prolog-like I/O interface (see section Input and Output with Prolog-like Interface).

The following are also allowed in KL1 programs for compatility with PIMOS system on PIM machines.

• Based notation: optional minus sign followed by a sequence of decimal digits specifying the base (1 to 36), a sharp sign, and then a charcter string of digits of the base, that are digits and alphabets (case insensitive), surrounded by doublequotes. Examples: ‘2#"1010"’, ‘16#"0D0a"’.
• Character code notation: optional minus sign followed by a sharp sign and a character enclosed within doubleqoutes. Examples: ‘#"a"’ means the character code of lowercase letter a.

3.2.2.2 Integer Arithmetics

Guard Predicate on builtin: := -Var +Expr

Body Predicate on builtin: := -Var +Expr

Computes the value of the integer expression Expr, and unifies it with Var. The following operators are available in the expression.

X + Y

Addition.

+ X

No operation. X is the result.

X - Y

Subtraction.

- X

Sign inversion.

X * Y

Multiplication.

X / Y

Integer division.

X mod Y

Modulo.

\(X)

Bit-wise complement.

X /\ Y

Bit-wise logical AND.

X \/ Y

Bit-wise logical OR.

X xor Y

Bit-wise exclusive OR.

X << Y

Left shift.

X >> Y

Logical right shift.

int(X)

Conversion from floating point to integer. X is a floating point expression (see section Floating Point Arithmetics) and its result is rounded to an integer value.

Arithmetical overflows are ignored, that is, all the arithmetics are done modulo depending on the C compiler used. C compilers with 32-bit long int give 28-bit KLIC integers and those with 64-bit long int give 60-bit KLIC integers.

This predicate is available in both guards and bodies of clauses.

If any of the operands in the expression are uninstantiated, the computation will be suspended until they all get instantiated.

Any operands in the expression can be an expression recursively. However, operands written as a variable in the program should not be instantiated to a compound term such as ‘3 + 5’. They should be instantiated only to an integer. Otherwise, a type mismatch error will be generated.

3.2.2.3 Integer Comparison

Comparison of integer data can be made using the predicates described here. More general comparison predicate is also provided (see section Comparison and Hashing), but predicates and methods described here are more efficient when the operands are known to be integers.

Guard Predicate on builtin: > +X +Y

Guard Predicate on builtin: >= +X +Y

Guard Predicate on builtin: =:= +X +Y

Guard Predicate on builtin: =\= +X +Y

Guard Predicate on builtin: =< +X +Y

Guard Predicate on builtin: < +X +Y

Perform arithmetical comparison of two integer arguments. Use =:= and =\= for equality and non-equality checks. Each side of the comparison can be an arithmetical expression. The same set of operators as in := can be used.

3.2.3 Floating Point Numbers

Floating point numbers with precision of 64 bits are provided as generic objects. The following method and predicate tell whether given data is a floating point number or not.

Guard Method on float: float +X

Guard Predicate on builtin: float +X

Tests whether X is a floating point number.

3.2.3.1 Notation of Floating Point Numbers

Floating point numbers have the following constant notation syntax.

sign integral . fraction e sign exponent

where integral, fraction and exponent are sequence of decimal digits. sign is either +, - or empty (meaning +). The exponent part, that is, character e, sign and exponent, may be omitted altogether.

The following are examples of floating point number constants.

3.14159  -6.02e23  1234.5678e-25

3.2.3.2 Creating New Floating Point Numbers

New floating point numbers can be created by the following. Predicates for floating point arithmetics described in Floating Point Arithmetics also create floating point numbers as the result of arithmetical operations.

Object Creation on float: new -Float +Init

A new floating point number is created and unified with Float. The argument Init should be an integer specifying the value of the floating point number. For example, ‘generic:new(float, F, 3)’ unifies F with 3.0.

3.2.3.3 Floating Point Arithmetics

Body Predicate on builtin: $:= -Var +Expr

Computes the value of the floating point expression Expr, and unifies it with Var. The following operators are available in the expression.

X + Y

Addition.

X - Y

Subtraction.

X * Y

Multiplication.

X / Y

Division.

pow(X, Y)

Y to the power of X.

sin(X), cos(X), tan(X)

Trigonometric functions on X.

asin(X), acos(X), atan(X)

Inverse trigonometric functions on X.

sinh(X), cosh(X), tanh(X)

Hyperbolic functions on X.

exp(X)

Exponential function.

log(X)

Natural logarithm.

sqrt(X)

Square root.

ceil(X)

Ceiling function (rounding toward positive infinity).

floor(X)

Flooring function (rounding toward negative infinity).

float(X)

Conversion from an integer to a floating point number. X is an integer expression (see section Integer Arithmetics) and its result is converted to a floating point number.

This predicate is available in both guards and bodies of clauses.

If any of the operands in the expression are uninstantiated, the computation will suspend until they all get instantiated.

Any operands in the expression can be an expression recursively. However, operands written as a variable in the program should not be instantiated to a compound term such as ‘3.0 + 5.0’. They should be instantiated only to a floating point number. Otherwise, a type mismatch error will be generated.

Operations listed above are also provided as generic methods on floating point number.

Body Method on float: add +X +Y -R

Body Method on float: subtract +X +Y -R

Body Method on float: multiply +X +Y -R

Body Method on float: divide +X +Y -R

Body Method on float: pow +X +Y -R

Body Method on float: sin +X -R

Body Method on float: cos +X -R

Body Method on float: tan +X -R

Body Method on float: asin +X -R

Body Method on float: acos +X -R

Body Method on float: atan +X -R

Body Method on float: sinh +X -R

Body Method on float: cosn +X -R

Body Method on float: tanh +X -R

Body Method on float: exp +X -R

Body Method on float: log +X -R

Body Method on float: sqrt +X -R

Body Method on float: ceil +X -R

Body Method on float: floor +X -R

These methods perform arithmetic operations, specified by the method name, on given operand(s), and return the result in R.

3.2.3.4 Floating Point Comparison

Comparison of floating point data can be made by the predicates described here. More general comparison predicate is also provided (see section Comparison and Hashing), but predicates and methods described here are more efficient when the operands are known to be floating point numbers.

Guard Predicate on builtin: $> +X +Y

Guard Predicate on builtin: $>= +X +Y

Guard Predicate on builtin: $=:= +X +Y

Guard Predicate on builtin: $=\= +X +Y

Guard Predicate on builtin: $=< +X +Y

Guard Predicate on builtin: $< +X +Y

These predicates perform arithmetical comparison of two floating point arguments. Use =:= and =\= for equality and non-equality checks (although they may not be much meaningful for floating point numbers). Each side of the comparison can be a floating point arithmetical expression. The same set of operators as in $:= can be used.

Bug Caution The current version (1.510) has problems with expressions with operators in these predicates. Only simple variables and constants can be used.

Comparison of floating point numbers can also be made by the methods described below.

Guard Method on float: less_than +X +Y

Guard Method on float: not_greater_than +X +Y

Guard Method on float: not_less_than +X +Y

Guard Method on float: greater_than +X +Y

Guard Method on float: equal +X +Y

Guard Method on float: not_equal +X +Y

These methods test whether X is less than Y or not, etc.

3.3 Structured Data

Structured data objects consist of zero or more elements.

3.3.1 Functor Structures

Functor structures are structures with given name and one or more elements, which can be of any type. Functors are conveniently used for representing data structures whose sizes are known beforehand. Functors correspond to record structures of C-like languages.

3.3.1.1 Notation of Functors

Functor constants can be written by the name of the principal functor, a left parenthesis, elements separated by commas, and finally a right parenthesis. Functor names have the same syntax as symbolic atoms. The principal functor name and the following left parenthesis should not be separated by space characters or any other punctuation symbols. Elements can be of any type, including variables or functors themselves.

Examples:

f(a, 3)   'a recursive functor structure'(X, 'child functor'(Y))

3.3.1.2 Operations on Functors

Predicates for manipulation of functor structures are provided as builtin predicates and in the module functor_table, as listed in this section.

In the current implementation, all the body builtin predicates listed here are actually implemented as macros expanded to predicates of the module functor_table. This implementation scheme may be changed in future releases.

Guard Predicate on builtin: functor +X -Functor -Arity

Body Predicate on builtin: functor +X -Functor -Arity

X is a functor with the principal functor whose name being Functor and arity Arity. These predicates can be used for obtaining the the name and/or the arity of principal functors. The guard predicate version can also be used for testing that X has the name Functor and/or the arity Arity. Any instantiated data that are not functor structures, i.e., atomic data, strings, vectors and so on, have zero as their arities and themselves as their principal functor names. Note that list structures consist of functors ./2.

This predicate cannot be used to create a new functor.

Guard Predicate on builtin: arg +Pos +Term -Arg

Body Predicate on builtin: arg +Pos +Term -Arg

The Pos-th argument of Term is Arg. Arguments are numbered from 1. The guard version simply fails if Pos is out of range. As all the data structures except for functor structures have no arguments, this predicate always fails for them.

Body Predicate on builtin: new_functor -Functor +Atom +Arity

A functor structure with its principal functor with name Atom and arity Arity is returned to Functor. Arguments of the created functor are initiated with integer 0.

Body Predicate on builtin: setarg +Pos +Fnct ?NewE -NewFnct

Body Predicate on builtin: setarg +Pos +Fnct ?OldE ?NewE -NewFnct

A new functor structure that is different from Fnct with only one argument at Pos is created and returned to NewFnct. The element with index Pos of NewFnct will be NewE. For five argument versions, the original argument at Pos will be returned to OldE.

Predicate on functor_table: =.. -NewFnct +List

A new functor structure is created and returned to NewFnct. The name of the principal functor is specified by the first element of List, which should be a symbolic atom, and the arguments are specified by the rest of List. If List has only one element, that element is returned to NewFnct.

This predicate can not be used for decomposing a functor structure to a list.

3.3.2 Lists

Lists are arbitrarily long sequences of any data objects. In KL1, List structures are made up of functor structures ./2, that is, functor structures with their name . and arity two. List structures are composed of possibly many of these functor structures (sometimes called cons cells).

The first element of the cons cell, sometimes called the car of the cell, represents the first element of the list. The second element, the cdr of the cell, represents the rest of the list. Termination of the list is indicated by a symbolic atom [] being the cdr.

Whether a given argument is a list or not can be tested by the following guard predicate.

Guard Predicate on builtin: list +X

Tests whether X is a cons cell. Note that, despite its name, this predicate fails for a null list [] for a historical reason.

Incrementally instantiated list structures are conveniently used as message streams.

3.3.2.1 Notation of Lists

As in Lisp, lists of KL1 are constructed using cons data structures, which is actually a functor structure ./2.

The basic notation for lists is [Car | Cdr], which consists of the first element Car and the tail of the list Cdr. This means exactly the same as .(Car, Cdr). An empty list is represented by an atom [].

If Cdr happens to be empty, that is, when the list consists only of one element Car, such a list can be written as .(Car, []) or [Car | []], or, alternatively, as [Car]. That is, the sequence | [] at the tail of a list can be ommitted.

Lists with its car being Car and its cdr being a list [Cadr, …] is [Car | [Cadr, …]], which can be abbreviated as [Car, Cadr, …]. For example, a list consisting of four elements, first, second, third and fourth can be written as [first, second, third, fourth].

A list consisting of four or more elements, but with the first four elements being first, second, third and fourth, can be written as [first, second, third, fourth | Rest]. Here, the variable Rest corresponds to the list beginning with the fifth element, or an empty list if the whole list had only four elements.

Note that, unlike in Ediburgh Prolog, the character sequence ,.. can not be used in place of |.

3.3.2.2 Manipulation of Message Streams

A stream merger is a process that takes multiple message streams represented as lists of messages as input, and passes all the messages from all the input streams to a single output stream also represented as a list.

The output consists of all the messages in the inputs with duplicates preserved. When two messages are ordered in one of the input streams, their order is also preserved in the output. When messages are from different input streams, their order in the output is unpredictable. The order may differ in one execution of the same program from another. The behavior of mergers is thus nondeterministic.

For example, when there are two input streams [1, 2, 3] and [a, b, c], the output can be something like [1, 2, a, b, 3, c] or [1, a, 2, b, c, 3], but will never be [1, a, 3, b, c, 2].

A binary (two-input) stream merger can be defined in KL1 as follows.

merge([M|In1], In2, Out) :- Out=[M|OutT],  merge(In1, In2, OutT).
merge(In1, [M|In2], Out) :- Out=[M|OutT],  merge(In1, In2, OutT).
merge([], In2, Out) :- Out=In2.
merge(In1, [], Out) :- Out=In1.

• The first clause forwards one message coming from the first input stream to the output stream. The first input stream is the first argument and the output stream is the third argument of the predicate. It then calls the predicate merge/3 recursively for repetitive execution.
• The second clause does the same for the second input stream.
• The third clause is used when the first input stream has no more messages in it. In this case, the second input stream is directly connected to the output. As there are no more messages to merge from the first input stream, the result of the merging should be the same as the second input stream.
• The fourth clause provides the corresponding feature when the second input stream has no more messages in it.

When messages come from both the first and the second at the same time, either the first or the second clause is arbitrarily chosen. This is the source of the nondeterminacy of the merger.

Although binary mergers are easy to define in KL1, defining a merger with arbitrarily many input streams is not so easy. It is also desirable to add new input streams dynamically, which makes it still harder. Also, mergers are used quite frequently in KL1 programs and thus should be quite efficient. Thus, the KLIC system provides a merger as one of its standard feature.

A new merger can be created by the following pseudo-predicate.

Object Creation on merge: new ?Input ?Output

A new merger with single input stream is created. Its input stream is Input and its output is Output.

The merger process created by the above pseudo-predicate does not actually start any merging immediately after its creation. It only forwards the messages from Input to Output, without changing the order.

To add a new input stream to a merger, unify the input with a vector whose elements are input streams. For example, if you need a binary merger, do the following.

generic:new(merge, Input, Output),
Input = {In1, In2}

This means the same as the following.

generic:new(merge, {In1, In2}, Output)

After doing the above, the merger will merge messages from two input streams, In1 and In2, to the output stream Output.

Input streams to a merger can be added not only immediately after its creation but at any time on demand. Two more input streams are added, for example, by the following.

In2 = {In2A, In2B, In2C}

After this, the merger will have four input streams, In1, In2A, In2B and In2C.

When one of the input streams is no longer needed, that input stream can be simply closed, by unifying it with an atom [].

The size of the vector unified with an input stream can be arbitrarily large or small. When it has only one element, the number of input streams will not be changed. When the vector has no elements, unifying with it has the same effect as closing the stream.

The output stream will be closed, i.e., the tail of the output list is unified with [], when all the input streams have been closed.

Here are some clues in using the merger.

• Messages merged can be a data structure containing unbound variables. Such messages are sometimes called incomplete messages. Incomplete messages are convenient for constructing a server-client process structure. Giving values to variables in messages can be used for communicating backwards from the server to the client.
• Merging may look deterministic on sequential implementations. Do never rely on it. It will become really nondeterministic on parallel implementations.

3.3.3 Vectors

Vectors are fixed-length one-dimensional array of KL1 data. The length of a vector is determined on its creation. Elements can be any KL1 data and can even be left undefined when the data structure is created.

Elements are indexed by an integer beginning from 0. For example, a vector with 3 elements has elements numbered 0, 1 and 2.

3.3.3.1 Notation of Vectors

Vectors can be denoted by a comma-separated list of elements in a pair of curly braces.

{ 1, a, f(b), X }

A null vector (vectors with no elements at all) is denoted only by a pair of curly braces.

{}

Note that curly braces are used in a way completely different from Edinburgh Prolog, where {} means an atom and {…} means a functor structure {}((…)).

3.3.3.2 Creating New Vectors

In addition to the notation described above, vectors can be dynamically created during program execution. The following predicate can be used to create a new vector.

Object Creation on vector: new -Vector +Init

Body Predicate on builtin: new_vector -Vector +Init

A new vector is created and returned to Vector.

If the argument Init is an integer, it sepcifies the number of elements. The elements are initialized with integer 0 in this case. For example, ‘generic:new(vector, V, 2)’ creates a vector ‘{0, 0}’ and returned it to V.

If Init is a list, the newly created vector is initiated by the elements of the list. Naturally, the number of elements of the vector becomes the same as the length of the list. For example, ‘generic:new(vector, V, [a, b, c])’ creates a vector {a, b, c} and unifies it with V.

3.3.3.3 Predicates on Vectors

Guard Method on vector: vector +Vector -Length

Body Method on vector: size +Vector -Length

Guard Predicate on builtin: vector +Vector -Length

Tests whether Vector is a vector object (if called in guard) and returns the number of elements in Length.

Guard Method on vector: element +Vector +Index -Element

Body Method on vector: element +Vector +Index -Element

Guard Predicate on builtin: vector_element +Vector +Index -Element

Body Predicate on builtin: vector_element +Vector +Index -Element

An element with index Index of the vector Vector is unified with Element. The index is zero origin.

Body Method on vector: set_element +Original +Index ?NewElement -New

Body Predicate on builtin: set_vector_element +Original +Index ?NewElement -New

A new vector is unified with New. The new vector has the same elements as the Original, except that the Index’th element is updated to NewElement. The original vector is left untouched. The index is zero origin.

Body Method on vector: set_element +Original +Index ?Element ?NewElement -New

Body Predicate on builtin: set_vector_element +Original +Index ?Element ?NewElement -New

A new vector is unified with New. The new vector has the same elements as the Original, except that the Index’th element is updated to NewElement. The original vector is left untouched. The index is zero origin. The original Index’th element is returned to Element.

Body Method on vector: split +Original +At -Lower -Upper

The vector Original is split at the index position At and the resultant two vectors are unified with Lower and Upper. At has to be a non-negative integer less than or equal to the size of the original vector. Lower will have elements with indices between 0 and At-1, inclusive. Elements with indices between At and up will be included in Upper.

Body Method on vector: join +Lower +Upper -Joined

Two vectors Lower and Upper are concatenated together to make a new vector Joined.

In KLIC, creating a new vector differing with an existing one by only a single element is implemented with constant time and space overhead, regardless of the size of the vector, by using multiversion array representation.

3.3.4 Strings

Strings are one dimensional arrays of integers in restricted range. The current version provides only strings of 8-bit elements which has elements of the range 0 through 255. They are convenient for representing character strings. Strings with elements of different sizes are planned in future.

Unlike in Edinburgh Prolog, strings are not notational convention for lists of character codes. They are of its own data type.

3.3.4.1 Notation of Strings

In KLIC, character string constants should be denoted by sequence of characters surrounded by a pair of doublequotes, as follows.

"A string of the characters written here"

The following escape sequences (a la ANSI C) are used to specify doublequotes, backslashes and control codes as string elements.

\a

Bell.

\b

Backspace.

\t

Tab.

\n

Newline.

\v

Vertical tab.

\f

Formfeed.

\r

Carriage return.

\'

Singlequote.

\"

Doublequote.

\?

Question mark.

\\

Backslash. Two consecutive backslach characters specifies a single backslash in the string.

\ooo

Code specified by the octal number ooo. Up to three octal digits are recognized.

\xhh

Code specified by the hexadecimal number hh. Arbitrarily many hexadecimal digits may be used.

\<newline>

The backslash character along with the newline code immediately following it are ignored. This sequence results in no characters at all in the string.

Example:

"The character \'\"\' (doublequote)"

The above example is understood as a string containing the following characters.

The character '"' (doublequote)

Strings should not contain newlines nor doublequotes directly. A standard way for including newlines within a string is to end the line with ‘\n\’. By this, a new line code is inserted by the sequence ‘\n’ and the actual newline in the source code following the second ‘\’ is ignored.

Unlike in Edinburgh Prolog, character strings are not lists of character codes.

3.3.4.2 Creating New Strings

In addition to the constant strings described above, strings can be dynamically created during execution. The following predicate can be used to create a new string.

Object Creation on string: new -String +Init +ElemSize

Body Predicate on builtin: new_string -String +Init +ElemSize

A new string is created and unified with String. The last argument ElemSize specifies the bit width of the elements. As only 8-bit strings are available in the current version, this should be 8.

When the argument Init is an integer, it sepcifies the number of elements. In this case, the elements are initialized with integer 0 (null code). For example, ‘generic:new(string, S, 3, 8)’ creates ‘"\0\0\0"’.

If Init is a list of integers, the newly created string is initiated by the elements of the list. Naturally, the number of elements of the string becomes the same as the length of the list. In this case, list elements should have values that fits in the given bit width; between 0 and 255 in case of 8-bit strings. For example, ‘generic:new(string, S, [0'a, 0'b, 0'c], 8)’ creates ‘"abc"’.

3.3.4.3 Predicates on Strings

Guard Method on string: string +String -Length -ElemSize

Body Method on string: string +String -Length -ElemSize

Guard Predicate on builtin: string +String -Length -ElemSize

Tests whether String is a string object (if called in guard). The number of elements of String is returned in Length and the element size (which is always 8 in the current version) is returned in ElemSize.

Body Method on string: size +String -Length

Returns the number of elements of String in Length.

Body Method on string: element_size +String -ElemSize

Returns the the element size of String in ElemSize.

Guard Method on string: element +String +Index -Element

Body Method on string: element +String +Index -Element

Guard Predicate on builtin: string_element +String +Index -Element

Body Predicate on builtin: string_element +String +Index -Element

An element with index Index of the string String is unified with Element. The index is zero origin.

Guard Method on string: less_than +String1 +String2

Guard Predicate on builtin: string_less_than +String1 +String2

Succeeds only when String1 is less than String2 in lexicographical order.

Guard Method on string: not_less_than +String1 +String2

Guard Predicate on builtin: string_not_less_than +String1 +String2

Succeeds only when String1 is not less than String2 in lexicographical order.

Body Method on string: set_element +Original +Index +Element -New

Body Predicate on builtin: set_string_element +Original +Index +Element -New

A new string is unified with New. The new string has the same elements as the Original, except that the Index’th element is updated to Element. The original string is left untouched. The index is zero origin.

Body Method on string: split +Original +At -Lower -Upper

The string Original is split at the index position At and the resultant two strings are unified with Lower and Upper. At has to be a non-negative integer less than or equal to the size of the original string. Lower will have elements with indices between 0 and At-1, inclusive. Elements with indices between At and up will be included in Upper.

Body Method on string: join +Lower +Upper -Joined

Two strings Lower and Upper are concatenated together to make a new string Joined.

Body Method on string: search_character +String +Start +End +Char -Where

Body Predicate on builtin: search_character +String +Start +End +Char -Where

The character Char is searched for in String, beginning from the position Start and ending before End. If such a character is found, its index is unified with Where. If not, Where is unified with -1. The indices are zero origin.

In KLIC, creating a new string differing with only one element from the original is implemented with constant time and space overhead, regardless of the size of the string, by using multiversion array representation.

3.4 Handling Program Code as Data

KLIC allows higher order manipulation of executable code as data objects. Program modules are treated as module data objects and individual predicates are treated as predicate data objects.

3.4.1 Modules

Program modules are treated as data through generic data objects of type module.

Object Creation on module: new -Module +ModuleName

Creates a new object Module corresponding to the program module specified by ModuleName as a symbolic atom. If the specified module is not defined, the symbolic atom itself is returned to Module. See section Creating Generic Objects, for the format of object creation goals.

Guard Method on module: module +Module

Tests whether Module is a module object or not.

Body Method on module: name +Module -ModuleName

The module name of Module is returned to ModuleName as a symbolic atom.

3.4.2 Predicates

Predicates in programs are treated as data through generic data objects of type predicate.

Predicate type data can be either denoted as a constant or created dynamically in runtime. Due to limitations of the features of host systems, dynamic creation may not be supported on some host systems.

The syntax of a predicate constant is as follows.

predicate#(module:predicate/arity)

Where module and predicate should be module and predicate name atoms and arity should be an integer (the number of arguments of the predicate). For example:

predicate#(main:main/0)  predicate#(quicksort:partition/4)

are valid predicate constants in programs.

Note that predicate constants are recognized by the KLIC compiler and not by the KLIC parser (see section Input and Output with Prolog-like Interface). Thus, the notation described above means a usual data structure when simply read in using the Prolog-like I/O streams.

Object Creation on predicate: new -Predicate +Module +PredName +Arity

Creates a new object Predicate corresponding to the predicate specified by Module (a module object), PredName (a symbolic atom) and Arity (an integer). See section Creating Generic Objects, for the format of object creation goals.

Guard Method on predicate: predicate +Predicate

Tests whether Predicate is a predicate object or not.

Guard Method on predicate: arity +Predicate -Arity

Body Method on predicate: arity +Predicate -Arity

The arity of the predicate Predicate is returned to Arity.

Body Method on predicate: apply +Predicate +ArgVec

Calls the predicate specified by a predicate object Predicate with arguments specified by ArgVec. ArgVec should be a vector of arguments to be passed to Predicate. Thus, the size of the vector should match with the arity of the predicate.

Body Method on predicate: call +Predicate +Args…

Calls the predicate specified by a predicate object Predicate with arguments specified by Args…. The number of the arguments should match with the arity of the predicate.

Body Method on predicate: module +Predicate -Module

The program module that Predicate belongs to is returned to Module as a module data object.

Body Method on predicate: name +Predicate -Name

The name of the predicate Predicate is returned to Name as a symbolic atom.

3.5 Unix Interface

The module named unix makes features of the host operating system (Unix, typically) available to KL1 programs.

Almost all of the features are available as messages to a stream obtained by a predicate unix/1 provided by the module unix. Some features are provided directly by predicates of the module.

3.5.1 Obtaining Unix Interface Stream

The module "unix" interfaces other programs through message streams. The stream can be obtained by calling the following predicate.

Predicate on unix: unix ?Stream

A message stream corresponding to the Unix interface is returned to Stream.

Most of the features of the Unix interface are not provided as predicates, because no ordering is guaranteed between predicate calls.

If the Unix interface were provided as predicates, for example:

unix:cd("a", 0),
unix:cd("b", 0),
unix:system("mkdir ls", 0)

may list the directory a but may possibly list b or even some other directory before doing any cd, depending on the execution order. On the other hand:

unix:unix([cd("a", 0),
           cd("b", 0),
           system("ls", 0)])

will surely try two cd and ls in this order, as what decides the order is not the order of execution but the order of the elements in a list structure.

On parallel implementations, KLIC consists of multiple processes. The process in which the unix stream is obtained will be the process where all the messages are handled. For example, cd(Path) message will change working directory of that single process and none of others.

If you obtain two or more message streams, there will be no automatic synchronization between messages sent to different streams.

3.5.2 Opening Streams for Input and Output Operations

The following messages to the Unix stream open a Unix I/O stream. Messages to be sent to the resulting Unix I/O streams (not the Unix stream stream itself) for actually performing I/O are described in separate places: See section Input and Output with C-like Interface, and Input and Output with Prolog-like Interface.

The following is a KLIC program for saying hello to the world.

main :- unix:unix([stdout(R)]), check_and_write(R).

check_and_write(normal(R)) :- R = [fwrite("hello world\n")].

Message on unix stream: stdin -Result

Message on unix stream: stdout -Result

Message on unix stream: stderr -Result

These messages open a stream associated with process’s standard input, standard output and standard error file respectively, and return normal(Stream) to Result.

Message on unix stream: read_open +Path -Result

Message on unix stream: write_open +Path -Result

Message on unix stream: append_open +Path -Result

Message on unix stream: update_open +Path -Result

These messages open the file named by the string Path, and return normal(Stream) to Result. The opening mode is input, output, append or input/output, respectively. If opening of the file fails, abnormal is returned instead.

3.5.3 Using Sockets

Unix- and Internet-protocol sockets can be obtained using the following messages to the Unix stream. Only sockets of SOCK_STREAM type are provided.

Message on unix stream: connect +Spec -Result

Creates a socket and connects it to socket specified by Spec and returns normal(Stream) to Result. Spec should have either of the following formats.

unix(Path)

A unix domain socket with the pathname Pathis opened.

inet(HostName, Port)

An internet domain socket of the host specified by a string HostName and port number Port is opened.

inet({B1, B2, B3, B4}, Port)

An internet domain socket is opened. The host is specified by the internet address B1 through B4 is opened.

inet6(HostName, Port)

An IPv6 domain socket of the host specified by a string HostName and port number Port is opened.

inet6(Addr, Port)

An IPv6 domain socket is opened. The host is specified by the IPv6 address Addr in presentation format.

The obtained stream handles both input and output messages.

Message on unix stream: bind +Spec -Result

Creates a socket and binds it to a name specified by Spec. The format of Spec is the same for the message connect except that HostName should be omitted for internet domain sockets. What is returned to Result is normal(Stream) but this Stream is a bound socket stream and does not directly handle I/O messages. Rather, it expects accept messages to obtain I/O message streams. When the bound socket stream obtained is closed and the socket type is unix, the named socket specified by Path in Spec will be unlinked.

Message on bound socket: accept -Result

Accepts a connection to the socket and returns normal(Stream) to Result, where Stream is an I/O message stream for both input and output messages.

Sockets provide asynchronous I/O, that is, waiting for a connection or acceptance of a connection will not block other processes in the KLIC system. Trying to read or write to sockets with buffers empty or full respectively will not block the whole computation. Such I/O operations will be postponed until immediate operations become possible.

Limitations: When an operation on a socket is postponed, all the remaining operations to be done on the socket are also postponed until the completion of the postponed operation. This is problematic when both input and output has to be polled. The problem is planned to be solved in a future release.

Limitations on Linux:Asynchronous I/O operations do not work on Linux (at least with Slackware 1.2.0) with the current version.

3.5.4 Files and Directories

The following message to the unix stream handles files and directories.

Message on unix stream: cd +Path -Result

Changes the working directory to Path. If successful, 0 is returned to Result; otherwise, -1 is returned. Corresponds to chdir system call.

Message on unix stream: unlink +Path -Result

Removes the directory entry specified by Path. If successful, 0 is retuned to Result; otherwise, -1 is returned. Corresponds to unlink system call.

Message on unix stream: mkstemp +Template -Result

Makes a unique file name from the given Template. Result is unified with normal(Filename, Stream), where Filename is the generated file name. Stream is an input/output Unix stream. Corresponds to the C library routine mkstemp. Unlike the library routine, the template does not have to have six trailing X characters. If a unique file name cannot be created somehow, abnormal is returned instead.

Message on unix stream: mkdtemp +Template -Dirname

Makes a unique directory name from the given Template and returns it to Filename. Corresponds to the C library routine mkdtemp. Unlike the library routine, the template does not have to have six trailing X characters. If a unique directory name cannot be created somehow, abnormal is returned instead.

Message on unix stream: access +Path +Mode -Result

Checks accessibility of the file with pathname Path with the mode Mode is validate, and returns the result to Result. Corresponds to the C library routine access. If the file is accessible, 0 is returned; otherwise, -1 is returned. Mode is an integer, with the bits of the following meaning.

4

read permission

2

write permission

1

execute permission

0

test existence

Message on unix stream: chmod +Path +Mode -Result

Changes the permission mode of the file with pathname Path to Mode. Corresponds to the system call chmod. If changing the mode is successful, 0 is returned to Result; otherwise, -1 is returned. Mode is an integer with standard Unix permission bits.

Message on unix stream: umask -OldMask

Message on unix stream: umask -OldMask +NewMask

Returns the current file creation mask to OldMask. With two arguments, sets the file creation mask to NewMask. Corresponds to the umask system call.

3.5.5 Handling Signal Interrupts

Unix signals can be converted to a list of integers using the following message to the unix stream.

Message on unix stream: signal_stream +Signal -Result

Unix signals specified by Signal (an integer value) will become caught and reported. The argument Result will become normal(Stream) and whenever a signal of the specified kind is detected, that signal number is sent to Stream. For example, if signal 2 (SIGINT in BSD and SVR4, at least) is detected, Stream becomes [2|Rest]. Further signals are reported to Rest.

Limitations: Signals may be ignored when they occur more than twice before the same kind of signal is detected, due to limitations of Unix.

3.5.6 Miscellaneous Messages to the Unix Stream

Various features of Unix are provided by sending the fllowing messages to the unix stream.

Message on unix stream: system +Command -Result

Executes Command (a string) in a newly created subshell, and returns its exit code to Result. Corresponds to the system system call.

Message on unix stream: getenv +Name -Value

Returns the value of the environment variable with the name Name to Value. Corresponds to the library routine getenv. If such a environment variable does not exist, integer 0 is returned to Value.

Message on unix stream: putenv +String -Result

The first argument String should be of form Name = Value. Adds or updates the environment variable Name with the value Value. Corresponds to the library routine putenv. If addition or updating is successful, 0 is returned to Result. Otherwise, non-zero integer value is returned.

Message on unix stream: kill +Pid +Sig -Result

Sends the signal Sig to a process or a group of processes specified by Pid, and returns 0 on success or -1 on failure to Result.

Message on unix stream: fork -Pid

Forks a new process which is a copy of the current process. Corresponds to the fork system call. If a child process is successfully created, the process ID of the child process is returned to Pid in the parent process, and 0 is returned in the child process.

Message on unix stream: fork_with_pipes -Result

Creates pipes and fork a new process. The new process is a copy of the current process. In the parent process, Result is unified with parent(Pid, In, Out), where Pid is the process ID of the newly created process. In the newly create child process, Result is unified with child(In, Out). In and Out are Unix I/O streams to pipes; parent’s Out is an output stream connected to child’s In, which is an input stream; child’s Out is connected to parent’s In.

Message on unix stream: execve +Command -Result

Replace the current process with an execution of Command. Corresponds to the execve system call. This predicate should never return, but if it fails -1 is returned in Result.

Message on unix stream: execlp +Command -Result

Replace the current process with an execution of Command. Corresponds to the execlp system call. This predicate should never return, but if it fails -1 is returned in Result.

3.5.7 Predicate Interface

Some of the Unix interface are provided as predicates defined in the module unix.

Predicate on unix: argc -Argc

Number of command line arguments not used by the KLIC system is returned to Argc. Such arguments start from the first argument not beginning with - or after -- in the command line.

Predicate on unix: argv -ArgList

Command line arguments nod used by the KLIC system is returned to ArgList as a list of strings.

Predicate on unix: exit +ExitCode

Terminates the process immediately with the exit code ExitCode.

Predicate on unix: times -Utime -Stime -CUtime -CStime

Returns process times in milliseconds. Utime is user time and Stime is system time. CUtime and CStime are those for children processes.

Note that when HZ (clock ticks per second) is not defined in some standard places, the system assumes 60.

3.6 Input and Output

KLIC provides two different sets of I/O operations. One is similar to those available from C language and the other is similar to those available from Prolog language.

C-like features are in a lower level and provide better performance both in speed and code size. However, during prototyping and debugging phases, the Prolog-like higher-level interface, allowing I/O of data structures directly, might be beneficial.

3.6.1 Input and Output with C-like Interface

Input and output operations with interface similar to those available in language C are described in this section.

Such interface are provided as messages to streams to open files, sockets, pipes &c, which are obtained by various messages to the Unix stream. See section Opening Streams for Input and Output Operations.

3.6.1.1 Common Messages with C-like Interface

The following messages are available for both input and output streams for C-like I/O.

Message on C-like I/O: feof -Result

Returns 1 to Result if the stream is at the end of the file; otherwise 0. Corresponds to the library routine feof.

Message on C-like I/O: fseek +Offset +Ptrname -Result

Changes the position of the stream according to the offset and pointer name given as Offset and Ptrname, respectively. The offset is specified as a signed integer by Offset. When Ptrname is 0, the offset is from the beginning of the file; when 1, from the current position; when 2, from the end of file. If successful, 0 is returned Result; otherwise -1.

Note that, due to the range restriction of integer values, this message may not be able to move to arbitrary positions in a very large file (larger than 128MB, on systems with 32-bit long integers).

Message on C-like I/O: ftell -Result

Returns the offset of the current byte position to Result.

Note that, due to the range restriction of integer values, the obtained position may be incorrect for a very large file (larger than 128MB, on systems with 32-bit long integers).

Message on C-like I/O: fclose -Result

Closes the stream. Returns 0 to Result if successful; -1 otherwise. No messages except for sync/1 should be sent to a stream after closing.

Message on C-like I/O: sync -Result

Returns 0 to Result. Useful in making sure that all the preceding messages have already been processed.

Message on C-like I/O: dup2 +NewD -R

Close UNIX file descriptor number NewD, and duplicate the stream such that I/O to/from NewD has the same effect as if it were to/from the stream. Corresponds to the dup2 system call.

3.6.1.2 Input Messages with C-like Interface

The following messages are available for input streams for C-like I/O.

Message on C-like I/O: getc -C

Reads one byte from the stream and returns it to C. At the end of file, -1 is returned.

Message on C-like I/O: ungetc +C

Pushes back one byte C to the stream.

Message on C-like I/O: fread +Max -String

Reads in at most Max bytes from the stream and returns the data as a byte string to String. Only up to 4,096 bytes can be handled in the current implementation. Note that the length of the resultant string may be smaller than the given maximum. This may happen at the end of the file for normal files and at any time for pipes or sockets.

Message on C-like I/O: linecount -Count

Returns to Count the number of newline characters encountered so far. Within the first line of a file, it returns 0, as no newlines have been encountered yet. Conventional one-origin line numbers can be computed by adding one to this.

This line counting can be confused when fseek/2 messages are used.

3.6.1.3 Output Messages with C-like Interface

The following messages are available for output streams for C-like I/O.

Message on C-like I/O: putc +C

Writes one byte C to the stream.

Message on C-like I/O: Number

Writes one byte Number to the stream. This is synonymous to putc(Number).

Message on C-like I/O: fwrite +String -Result

Writes out the contents of the byte string String to the stream and returns number of bytes actually written to Result. Note that the number of bytes actually written may be smaller than the length of String.

Message on C-like I/O: fwrite +String

Writes out the contents of the byte string String to the stream. Unlike the fwrite message with Result argument, it waits for all the bytes in String to be output. This may be undesirable for streams that require unpredictable time period for output, such as internet sockets and pipes.

Message on C-like I/O: fflush -Result

Flushes any output remaining on the stream. Returns 0 to Result if successful; -1 otherwise.

3.6.2 Input and Output with Prolog-like Interface

Unix interface streams with features to handle Prolog-like terms based on a operator precedence grammar can be obtained by the following predicate of module klicio.

The syntax of terms of KLIC is very close to that of Edinburgh Prolog but with subtle differences. See section Notation of Symbolic Atoms, Notation of Integers, Notation of Floating Point Numbers, Notation of Functors, Notation of Lists, Notation of Vectors, and Notation of Strings, for details.

3.6.2.1 Opening Prolog-like I/O Streams

Predicate on klicio: klicio ?Stream

A message stream corresponding to the Prolog-like term interface is returned to Stream. The obtained stream works the similar to a unix interface stream, which is used in turn to obtain message streams for actual I/O. I/O streams obtained through this stream accepts messages for Prolog-like term I/O described in this section in addition to ordinary C-like I/O messages.

This klicio stream is provided separately so that programs without the need of Prolog-like term I/O can be executable without modules for parsing and unparsing, as these modules have non-negligible sizes.

Message on klicio stream: stdin -Result

Message on klicio stream: stdout -Result

Message on klicio stream: stderr -Result

Message on klicio stream: read_open +Path -Result

Message on klicio stream: write_open +Path -Result

Message on klicio stream: append_open +Path -Result

Message on klicio stream: update_open +Path -Result

These messages open Prolog-like I/O streams. Messages to be sent to the resulting Prolog-like I/O streams (not the klicio stream itself) for actually performing I/O are described below.

These messages work exactly the same as the corresponding messages for unix streams, except that returned I/O streams understand messages for Prolog-like term I/O in addition to the messages for C-like I/O streams.

Prolog-like I/O streams are associated with operator definitions. Different operator definitions may be associated with each stream. Thus, adding or removing an operator to one stream will not affect operators used in other streams. Immediately after creation, each stream has a default set of operators.

3.6.2.2 Common Messages with Prolog-like Interface

The following messages for C-like I/O streams can be used for Prolog-like I/O streams.

Message on Prolog-like I/O: feof -Result

Message on Prolog-like I/O: fseek +Offset +Ptrname -Result

Message on Prolog-like I/O: ftell -Result

Message on Prolog-like I/O: fclose -Result

Message on Prolog-like I/O: sync -Result

See section Common Messages with C-like Interface, for details.

Message on Prolog-like I/O: addop +Op +Type +Prec

Adds an operator Op of type Type with precedence Prec.

Message on Prolog-like I/O: rmop +Op +Type

Removes an operator Op of type Type.

3.6.2.3 Input Messages with Prolog-like Interface

Message on Prolog-like I/O: gett -Term

Reads in a KLIC syntax term from the associated input stream to Term. On parsing errors, a message is output to stderr and another term is read in. At the end of the file, it returns an atom end_of_file.

Message on Prolog-like I/O: getwt -Result

Reads in a KLIC syntax term from the associated input stream and returns the result to Result. Result will have the form normal(WrappedTerm) if parsing completes without errors. Here, WrappedTerm is a ground term representation of the term read in, where variables are represented as a ground term with the information on their names. On parsing errors, a message is output to stderr and another term is read in. At the end of file, it returns normal(end_of_file).

See section Wrapped Terms for manipulation of wrapped terms.

The following messages for C-like I/O streams can also be used for Prolog-like I/O streams.

Message on Prolog-like I/O: getc -C

Message on Prolog-like I/O: ungetc +C

Message on Prolog-like I/O: fread +Max -String

Message on Prolog-like I/O: linecount -Count

See section Input Messages with C-like Interface, for details.

3.6.2.4 Output Messages with Prolog-like Interface

Message on Prolog-like I/O: putt +Term

Message on Prolog-like I/O: puttq +Term

Message on Prolog-like I/O: putwt +WrappedTerm

Message on Prolog-like I/O: putwtq +WrappedTerm

A term Term or a wrapped term WrappedTerm is written out to the associated output stream.

Messages without the character q are supposed to omit two quotes around symbolic atoms even when they are required to be correctly read in again. However, currently they work exactly the same as the messages with q.

With the current version, the output format is meant only to be machine-readable and not so readable for humans. That is, no operators are used and all atoms are enclosed within parentheses.

See section Wrapped Terms for manpulation of wrapped terms.

The following messages for C-like I/O streams can also be used for Prolog-like I/O streams.

Message on Prolog-like I/O: putc +C

Message on Prolog-like I/O: Number

Message on Prolog-like I/O: fwrite +String -Result

Message on Prolog-like I/O: fwrite +String

Message on Prolog-like I/O: fflush -Result

See section Output Messages with C-like Interface, for details.

Note that a period to end a term is not written out by these messages. Thus, writing out a period and a space or a newline character is usually required for the output to be read in again. The following goal sequence opens the file named /tmp/foo.bar, waits full instantiation of the variable X, and then outputs the value in a Prolog-like format followed by a period and a newline.

klicio:klicio([write_open("/tmp/foo.bar", normal(S))]),
S = [putt(X), putc(0'.), nl].

Message on Prolog-like I/O: nl

Outputs a newline code. This is synonymous to sending a message putc(10) to the same stream.

Note that Prolog-like I/O streams also accept all the messages accepted by C-like I/O such as putc/1 or getc/1 (see section Input and Output with C-like Interface).

3.6.2.5 Wrapped Terms

To allow metalevel manipulation of terms including variables, KLIC provides a data representation called wrapped term. A wrapped term is a ground term without any variables in it. A wrapped term has one of the following forms.

variable(VarName)

a variable with its name string VarName

atom(Atom)

a symbolic atom Atom

integer(Int)

an integer Int

floating_point(Float)

a floating point number Float

list([Car|Cdr])

a cons cell consisting of Car and Cdr, which are wrapped terms recursively

functor(Functor(Arg, …)

a functor structure; its arguments (Arg, etc) are wrapped terms recursively

vector({Elem, …})

a vector; its elements (Elem, etc) are wrapped terms recursively

string(Str)

a string Str

unknown(Term)

some unknown data; wrapping may be inprecise in this case

For example, the wrapped representation of a term:

f(a, X, {3, ["abc"|X]}, 3.14)

is the following.

functor(f(atom(a),
        variable("X"),
        vector({integer(3), list([string("abc")|variable("X")])}),
        floating_point(3.14))).

The following predicate convert wrapped terms to normal terms.

Predicate on variable: unwrap -Wrapped ?Term

Converts a wrapped term Wrapped to a normal term Term.

Wrapped terms are normally obtained as a result of input operations (see section Input Messages with Prolog-like Interface). Wrapped terms can also be constructed by usual user programs, as they are nothing more than a usual KL1 term. The following predicate that converts normal terms to wrapped terms may also be useful in certain cases.

Predicate on variable: wrap ?Term -Wrapped

Converts a normal term Term to a wrapped term Wrapped.

In the current version, all variables are given the same name _. Thus, by wrapping a term and then unwrapping its result, all the variables in the original term will become references to the same variable. This is a bug and is planned to be fixed in a future version.

When Term contains multiple references of a same variable, computation on-going concurrently may instantiate the variable. In such cases, this predicate may yield a wrapped term in which two original occurrences of the same variable are converted differently; one as a variable and another as a non-variable term. This is an inherent problem of the specification of this predicate and probably will never be fixed. Thus, applying this predicate to non-ground terms should be restricted to certain metalevel programs, such as debugging utilities.

3.7 Controlling System Behavior

The following predicates are provided in the module system_control.

Predicate on system_control: postmortem +Module +Goal -Result

Registers postmortem processing after normal or abnormal termination of the main program. Goal should be a functor structure specifying the predicate and arguments of the postmortem processing goal. Module should be a symbolic atom specifying the module of the postmortem processing predicate. Only a single goal can be specified; comma-separated sequences of goals are not allowed.

When the registration is done, Result is unified with []. Waiting for this will prevent further processing to be executed before the completion of the registration.

If this predicate is called many times, the last registration will be effective.

Predicate on system_control: gc -Before -After

Requests garbage collection and returns the heap size in words before and after the garbage collection to Before and After respectively. The size of a word is the same as the size of type long of the C language system used in the installation.

In parallel implementations, only garbage collection for local storage is requested. Requesting of global garbage collection is not available.

3.8 Timer

KLIC provides real-time timers. Although Unix provides only one timer per process, KLIC virtualizes the mechanism and provides as many timers as needed.

Implementations on host systems where real-time timers are not available do not provide the feature.

Time values (both times and time intervals) are represented by a term of the form time(Day, Sec, Usec), where Day, Sec and Usec are non-negative integers representing days, seconds and microseconds. Sec should be less than 86,000 (one day) and Usec should be less than 1,000,000 (one second).

The following predicates are provided in the module timer.

Predicate on timer: get_time_of_day -Time

The current time expressed in seconds and microseconds since midnight of January 1, 1970 GMT is returned to Time.

The time obtained is that of when a goal of this predicate is actually executed. Note that ordering of goal execution is up to the KLIC system. The time reported is only guaranteed to be the time between two observable events: when the parent goal of this goal is reduced, and when the value of Time is inspected.

Note also that the reported time is what is returned by the underlying operating system of the worker task. On a distributed system, clocks of constituting systems may not agree completely.

Predicate on timer: add Time1 Time2 -Time

Predicate on timer: sub Time1 Time2 -Time

Computes sum and difference of two time values, respectively.

Predicate on timer: compare Time1 Time2 -Result

Compares two time values Time1 and Time2 and returns the result in Result. The result is < if Time1 is smaller than (or before) Time2, = if they are the same, > if Time1 is larger than (or after) Time2.

Predicate on timer: instantiate_at Time -Var

Predicate on timer: instantiate_after Interval -Var

Unifies Var with a symbolic atom [] at the time specified. The former predicate does this at the specified time, while the latter does this after the specified time interval. If the specified time has already passed, the variable may be instantiated immediately.

Note that instantiation may be delayed arbitrarily long. Reasonable implementations should have short delays.

Predicate on timer: instantiate_every Interval Stop -Var

Incrementally instantiate Var with a list of symbolic atom []. The first element is instantiated after the time interval specified, the second after time twice the specified value, etc. It will be repeated forever unless the argument Stop becomes instantiated, on that occasion, the list will be terminated.

Note that instantiation may be delayed arbitrarily long. Reasonable implementations should have short delays.

3.9 Random Number Generator

Pseudo-random numbers can be generated using the object class random_numbers. This random number generator is based on nrand48. The random number genrator feature is not availble if nrand48 is not on the host system.

Object Creation on random_numbers: new -Randoms Range

Object Creation on random_numbers: new -Randoms Range Seed

An infinitely long list of pseudo-random integers ranging between 0 and Range - 1, inclusive, is returned to Randoms. Range should be a positive integer. The optional argument Seed specifies the seed for random number generation. The list elements are guaranteed to be the same if the same seed is given.

Note that, although the list is virtually infinite, elements are computed lazily on demand as programs incrementally inspect their values.

4 Using KLIC

This chapter describes how to use the KLIC system.

4.1 Compiling Programs with KLIC

After proper installation, KL1 programs can be compiled into C program and then to executables by the command klic. klic is a compiler driver that allows various options.

4.1.1 Command for Compilation

By simply running klic command with the name of KL1 program source file with the trailing .kl1 as an argument, that program will be compiled into C and then to an executable format.

For example, to compile XXX.kl1, type in:

% klic XXX.kl1

The compilation result will be found in a.out. If you want the compilation result to be named YYY, do the following.

% klic -o YYY XXX.kl1

If your program is divided into several files, say XXX.kl1, YYY.kl1 and ZZZ.kl1, you can compile and link them together by the following.

% klic XXX.kl1 YYY.kl1 ZZZ.kl1

It is also possible to separately compile several KL1 source files and link them afterwards. To avoid linkage errors, you have to stop before linkage by giving the -c flag, as follows.

% klic -c XXX.kl1
% klic -c YYY.kl1
% klic -c ZZZ.kl1

Finally, you have to link all of them together by the following.

% klic XXX.o YYY.o ZZZ.o

See See section Compiler Options, for details of compilation flags.

If you want to link program pieces written directly in C, say CCC.c and DDD.c, with pieces written in KL1, XXX.kl1 and YYY.kl1, simply do the following.

% klic CCC.c DDD.c XXX.kl1 YYY.kl1

The order of files specified does not matter. C functions can be invoked from within inline-expanded codes (see section Inserting C Language Code Inline).

4.1.2 Compiler Options

Options available for the compilation command klic are listed below.

-c

Stop after generating relocatable object and don’t link the program.

-C

Stop after translation into C.

-d

Don’t try any compilation (dry run). Implies -v.

-D database_manager

Use the specified database manager program.

-g

Debug flag passed to the C compiler.

-I directory

Use the additional include directory specified for C compilation.

-K klic_compiler

Use the speicfied KL1 to C translator program.

-l library

Use the additional library specified for linking.

-L directory

Use the additional directory specified to be searched for -l.

-o file

Use the file name for the generated executable file.

-O

-Olevel

Use the specified optimization level. When a non-zero optimization level is specified, some additional optimization flags may be also passed to the C compiler. Such Additional optimization flags are system dependent and determined on KLIC system installation procedure.

For this option, no spaces are allowed between -O and level.

-P parallel

Run subtasks (C compilers &c) in parallel. At most parallel subtasks are forked at a time.

-R

Do recompilation regardless of file dates.

-S

Stop after generating assembly code output.

-n

Link with the non-debugging version of the runtime library. By default, the debugging version is used.

-v

Run in verbose mode. All the commands executed through the compielr driver will be output to standard error.

-xdirectory

Use database file klic.db in the specified directory and also place atom.c, funct.c and predicates.c and their corresponding objects in the same directory. This flag is useful when programs to be linked together are distributed to multiple directories.

-Xdirectory

Initiate the database file klic.db from the database initiation file klicdb.init under the specified directory, when the database file does not exist yet. It defaults to the default library directory.

The following environment variables can change the default behavior of the compiler. Options given at compilation time supersede the environment variable values.

KLIC_LIBRARY

Directory for runtime libraries. Superseded by the -X option.

KLIC_DBINIT

Directory for initial database. Defaults to the directory for runtime libraries.

KLIC_COMPILER

KL1 to C translator program. Superseded by the -K option.

KLIC_DBMAKER

Database manager program. Superseded by the -D option.

KLIC_INCLUDE

Additional include directory for C compilation. Superseded by the -I option.

KLIC_CC

C compiler to be used.

KLIC_CC_OPTIONS

Additional option flags for the C compiler.

KLIC_LD

Linker to be used.

KLIC_LD_OPTIONS

Additional option flags for the linker.

4.1.3 How KLIC Compiler Works

Understanding how KL1 programs are compiled and executed may help understanding the usage of KLIC in further depth.

The system consists of the following three modules.

• KLIC compiler
• KLIC database manager
• KLIC runtime system

KL1 programs are compiled using the KLIC compiler into C programs. It also generates files FILE.ext containing information on atoms and functors used in the program. The information in .ext files for programs to be linked together is merged together later by the database manager, into files atom.h, funct.h, atom.c, funct.c and predicates.c.

The object C program is then compiled by a C compiler, with headers provided by the KLIC runtime system, atom.h and funct.h. The files atom.c, funct.c and predicates.c are also compiled, and linked together with the runtime system (predicates.c is linked only with debugging runtime).

Compilation, database management and linkage are governed by a driver program named klic. This program klic plays a role similar to cc and make combined. cc controls the C preprocessor, the C compiler kernel and the linker; klic controls the KL1-to-C compiler, the C compiler, the KL1 program database manager and the linker. make selectively executes compilation only when needed by examining the file dates; klic works similarly.

4.2 Running Programs Compiled with KLIC

You can simply run the compiled excutable. If you compiled your program into the file a.out, you simply give the file name ./a.out to the shell you are using.

The predicate main with no arguments in the module main will be the initial goal to be executed (see section Initial Goal).

4.2.1 Runtime Switches for Programs Compiled with KLIC

The following options are available on running the compiled executable.

-h size

Specifies initial heap size in words. As copying garbage collection is used, memory size actually used for heap will be twice this size. The size can be specified directly (such as 2097152) or with a postfix k or m (as 2048k or 2m) to specify units of 2^10 or 2^20 words. The default heap size is determined by the macro HEAPSIZE, which is 24k in the original distribution. The length of one word is the same as the length of the type long int in C, that depends on the hardware and the C compiler you use. The heap size will be increased automatically according to options -H and -a.

-H size

Specifies maximum heap size in words. Automatic heap expansion mechanism will never try to expand the heap above the size specified by this option. The default value is infinite.

-a ratio

Specifies threashold active cell ratio as a floating point number. If the ratio of the space occupied by active (non-garbage) cells in the heap space is above this threshold, the heap size will be doubled in the next garbage collection, as far as the size doesn’t exceed the maximum size specified by the -H option. The default value is 0.5.

-g

Specifies that time required for garbage collection is to be measured. As garbage collection will not take long for small heap sizes, the measurement overhead can be more than that. Thus, by default, garbage collection timing is disabled.

-s

Specifies suspension statistics. After execution of the program, suspended predicates and numbers of their suspensions are reported. This option is available when the debugging version of the runtime library is linked, which is the default setting (see section Compiler Options).

-t

Specifies to start execution with tracing (see section Tracing Program Execution). Tracing is only possible when the debugging version of the runtime library is linked, which is the default setting. The non-debugging version of the runtime library can be specified by compilation time options (see section Compiler Options).

When all the ready goals have been executed, the program will stop. If there remain any goals awaiting for input data and if the program is linked with the debugging runtime library, it will try to detect which goal is problematic and report such a goal. Otherwise, if the linked library is a non-debugging version, only the number of such remaining goals is reported.

4.3 Tracing Program Execution

KLIC provides a debugging tracer with spying (break point) feature.