_______ _______ __ _ ______ |______ | |______ | \ | | ____ | |_____ |______ | \_| |_____| User Manual Version: 2 I. Introduction This document describes an implementation of the "FLENG" programming language as described in [1]. FLENG is a very minimal and low-leve concurrent logic language descending from Concurrent Prolog. The implementation described here provides a FLENG compiler that generates assembly language for x86-64 and armv7 machines on UNIX or BSD systems. Additionally a front end for "F:at Guarded Hord Clauses" is provided, which is a slightly higher level and more convenient language. II. Usage The compiler is invoked by using the "fleng" driver script: fleng [-Vwhkdc] [CCOPT ...] [-m MODULE] FILENAME [-o OUTFILE] [OBJECTS ...] The script takes FLENG or FGHC source files and generates assembler, buinary object files or executables. The following command line options are supported: -V Print version and exit. -w Disable compiler warnings. -k Keep intermediate files. -c Compile to object file, do not create an executable. -m MODULE Specifies the name of the compiled module. If no module name is given the module name defaults to "" (empty). -o OUTFILE Produce OUTFILE and exit. Depending on the file extension, the compilation process will stop after generating a FLENG source file (.fl or .fleng) an assembler file (.s), a binary object file (.o) or an executable (any other extension). As default output filename the basename of the source file is given and an executable file is created. -d Enable debug information, which shows slightly more information in debug logs and enables some additional error checking. Note that enabling debug information has a small runtime-speed overhead. -h Show usage information. Binary object files can be linked together to produce executables consisting of multiple compiled modules. The "fleng" driver accepts *.o and *.a files on the command line and links them to any generated executable. If the source file name has an .fl or .fleng extension, then the "fleng" driver assumes it contains FLENG code. In all other cases the file is considered to be an FGHC source file. All compiled executables accept a number of runtime command line options to enable debugging output and override internal settings: [+HELP] [+LOG ] [+HEAP ] [+GOALS ] [+TIMESLICE ] [+LOGFILE ] [+THREADS ] [+STATS] [+STAT_TICKS ] [+HEAPSTATS] ... [--] ... +LOG Enable logging for all threads specified by , where bit 1 corresponds to thread 1 and so on. +HEAP Set default heap size for each thread in bytes. The default size is 1000000 bytes. +GOALS Set the default number of goals a thread can have active at the same time. The default number is 10000. +LOGFILE Specifies the location of the log file where debug information is written to, if logging is enabled for one or more threads. By default logging output is written to standard error. +THREADS Specifies the number of threads to be used and defaults to 1. +TIMESLICE Sets the number of goal-invocations after which a process yields, is added to the active process queue and another active process is scheduled. +STATS Write statistics to the log file for all threads selected by the "+LOG" runtime option. The statistics are given in textual format and have the following format: ## G Q S C THREAD gives the ordinal number of the thread, starting at 1. TICKS is the number of internal clock ticks of the thread. ACTUIVE is the number of active goals. SUSPENDED is the number of inactive, suspended threads. CELLS is the number of used cells in the heap. +STAT_TICKS Sets the number of internal clock ticks, after which statistics are written for a thread. The default is 100. Whenever a new process is scheduled, the internal clock is increased. +HEAPSTATS Enable heap statistics, similar to "+STATS". The format is as follows: #$ T L V TUPLES, LISTS and VARS give the number of heap cells storing objects of the corresponding type at the time the statistics where written. +HELP Shows runtime option usage information. -- Disables any further runtime option processing. FLENG and FGHC programs usually spawn many processes that run in parallel. This implementation can utilize native threads to partition process pools into separately executing entities to take advantage of multi-core CPUs. III. The FLENG Language For a full desription of FLENG, see [1]. This implementation provides a superset including additional computation operators for numerical calculations. A very short description of the language is given here. Some familiarity with Prolog is recommended to understand the concepts used. A FLENG program consists of a set of "process definitions", where each definition is a set of clauses of the same name and arity: process_name(Argument1, ...) :- Goal1, ... . Arguments are "matched" to the actual argument given when the process is created. Goals are new processes to be invoked when the clause is selected. When a process is invoked, one clause of its definition that matches the given arguments is selected and executed, by spawning a new process for each goal in the body, for example: % write each element of the given list: walk([]) :- true. walk([_|Y]) :- walk(Y). main :- walk([1, 2, 3]). Each clause must have a list of goals, separated by comma (","). Note that all body goals are truly executed in parallel, not in the order in which they are specified. If no clause matches the arguments, then the process "fails", resulting in a run-time error. Argument variable bindings take place when clause heads are matched, but logic variables can only be bound by explicit unification in the body. If an argument variable (a variable occurring in the clause head) refers to a component of a data structure contained in a currently unbound logic variable, the process selection is suspended until the variable has been bound. Here an example: try([Y]) :- true. main :- try(X), wait(X). wait(X) :- X = 123. Here "try" will suspend until the unification of "X" with 123 is performed. Once a logic variable is bound, all goals suspended on the variable will be made active and are scheduled to be executed at some stage, after which they may continue or suspend on other variables. Once the head of a clause is fully matched, the clause "commits" and the body goals are spawned. All other, alternative clauses will be ignored, there is no "backtracking" as in Prolog. One specific feature of FLENG is the "!" operator. When used in the head of a clause, a variable prefixed with "!" will suspend until the variable is bound, regardless of whether the argument is subsequently used or not: try1([X]) :- true. try2([!X]) :- true. main :- try([Z]). try(Y) :- try1(Y), try2(Y). "try1" will match and complete, but "try2" will suspend forever, since it waits for the first element of the given list to be bound to some value. In FLENG the same argument variable may not appear more than once in a clause head. A FLENG program terminates once there are no more active goals. If there are still suspended goals, then a deadlock has occurred and the program aborts with an error message. The only built-in primitives in FLENG are "compute", "unify", "true", "=" and "foreign_call", described later in this manual. There are further undocumented primitives which are used for translated FGHC code. Toplevel declarations have the following form: -declaration(Argument, ...). Currently supported declarations in FLENG are "initialization/1", and "uses/1", which are described below. FLENG is intentionally minimal to make implementing it easier. For user programming it is recommended to use the FGHC front end described below. IV. The FGHC Language "FGHC" or "Flat Guarded Horn Clauses" is another dialect of Concurrent Prolog, descended from "GHC" which is described in [2]. It provides clause guards, arithmetic expression evaluation and some other syntactically convenient features. See also [3] for a general overview over the many concurrent logic language dialects and how they relate to each other. FGHC is "flag", meaning that only built-in guard-expressions are allowed in the guard part of a clause, no user defined process definitions can be used as guards. An FGHC clause has the following general format: process_name(Argument1, ...) :- Guard1, ... | Goal1, ... . The "Guard1, ... |" part may be omitted. If no guards and no goals exist, the the clause may be written as process_name(Argument1, ...). A guard is one of a set of predefined guard expressions that are executed to determine if the clause commits or not. If a guard expression fails, then another clause is selected until one clause commits or the whole process invocation fails. Both FLENG and FGHC support the following data types: signed integers 123 0xF00F 0'A floating point numbers 1.23 strings (atoms) abc 'one\ntwo' lists [1, 2, 3] [head|tail] "abc" tuples foo(bar, baz) variables Abc _123 _ ports modules The atom "[]" designates the empty list. Anonymous variables ("_") as in Prolog are supported. Character lists enclosed in double quotes are represented as a list of UNICODE code points. "Ports" are identity-preserving stream containers, "modules" are first-class representations of a compiled module interface. Circular data structures are not allowed. This is currently not checked. Care must be taken when having multiple clauses that overlap in the arguments they match: if multiple clauses match at the invocation of the associated process definition, then it is unspecified which of the candidate clauses will "fire" and be committed. You can narrow the set of matching clauses by using guards if you want to avoid this non-determinism: big(N, F) :- N > 1000 | F = yes. big(_, F) :- F = no. In an invocation of "big(1001)" the second clause may match, since matching is non-deterministic. Add another guard or "otherwise" to remove this ambiguity: big(N, F) :- N > 1000 | F = yes. big(_, F) :- N =< 1000 | F = no. % or "otherwise" Declarations as in FLENG are supported. FGHC also allows using the "!" annotation. The restriction that the same variable may not occur more than once in a clause head is lifted and equivalent to binding a renamed variable and adding a "==/2" guard matching both variables. V. Builtin Primitives and Support Libraries This sections describes the available primitive operations available in FGHC code. These primitives may be implemented as calls to the runtime system, as calls to external C libraries, or as library predicates written in FGHC or FLENG. Arguments with the suffix "^" will be unified with a result value, arguments with the suffix "?" are expected to be non-variable ("ground") values. If a primitive is said to "signal an error", then the program will report an error message and terminate. Most library primitives "force" their arguments, if required, by suspending the calling process if an argument is an unbound variable. Notable exceptions are "compute/{3, 4}" and "unify/3". * Primitives by group: Control ,/2 call/1 true/0 when/2 Unification =/2 assign/3 unify/3 deref/2 Conversion number_to_list/3 number_to_list/4 string_to_float/2 string_to_integer/2 string_to_integer/3 string_to_list/3 list_to_string/2 list_to_tuple/2 list_to_number/2 list_to_number/3 utf_encode/2 utf_encode/3 utf_decode/3 read_byte_stream/2 read_char_stream/2 Lists append/3 menber/3 length/2 Input/Output close_file/3 open_file/3 listen/2 writeln/1 writeln/2 write_block/3 write_block/4 read_block/4 Numeric computations compute/3 compute/4 is/2 Program environment command_line/1 halt/1 threads/1 getpid/1 self/1 current_seconds/1 signal/3 timer/2 randomize/2 error/1 log/1 get_module/2 Ports open_port/2 send/2 send/3 Tuples tuple_to_list/3 put_arg/3 put_arg/4 get_arg/3 get_arg/4 make_tuple/2 Foreign Functions foreign_call/1 A number of additional libraries are provided with the system that are written mostly in FGHC and can be accessed by using the "uses" declaration: fmt Formatted output mem Raw memory allocation and access proc Invocation of sub-processes map Balanced AVL trees sort Sorting set Lists as sets lex An FGHC/FLENG lexer parse Parsing of FGHC/FLENG expressions Consult the comments in the relevant library files for information on how to use these modules. The library modules "$rt", "lib" and "sys" are used internally and provide support code for builtin operations and inter-thread communication. * Alphabetic list of primitives: GOAL1, GOAL2 Execute goals in parallel. The goals may not be variables. MODULE:GOAL Invokes GOAL, which must be a tuple or string and be defined in the module with the given name. GOAL@PEER MODULE:GOAL@PEER Invokes the specified non-variable GOAL in the thread designated by PEER, which may be a variable but must be bound. All threads are ordered before execution in ring and torus topologies. PEER specifies what neighbouring thread in a topology should receive the call: fwd bwd previous or next in the ring topology. north south east west neighbours in the torus topology. all broadcast call to all threads. All threads are connected in the ring topology. Some threads may not be connected in the torus topology, depending on the number of threads. Additionally PEER may be an integer thread number (starting at 1) addressing a specific thread in the set of all threads. X = Y Equivalent to "unify(_, X, Y)". See "unify/3" for more information. append(LIST1?, LIST2?, LIST3^) Creates a copy of LIST1 with LIST2 appended and unifies the result with LIST3. assign(VAR^, VAL?, DONE^) Assigns VAL to the variable VAR, which must be unbound and unifies DOEN with the empty list, when the assignment is completed. call(TERM?) Invokes the process specified by TERM which must be a tuple or string or a variable bound to a tuple or string and must refer to a user-defined process definition. close_file(FILE?, DONE^) Closes the open file with the descriptor FILE and unifies DONE with the empty list when the operation is completed. If the file can not be closed an error is signalled. command_line(LIST^) Unifies LIST with a list of strings holding the command line arguments to the currently executing program, not including the program name and any runtime options. compute(OP?, ARG?, RESULT^) compute(OP?, ARG1?, ARG2?, RESULT^) Performs a unary or binary numeric computation. OP must be a string and may be one of the following: Unary Binary Result + - x Sum - - x Difference * - x Product / - x Quotient mod - x Remainder and - x Bitwise AND or - x Bitwise OR xor - x Bitwise XOR shl - x Shift bits left shr - x Arithmetic shift bits right < - x Is ARG1 less than ARG2 @< - x Is ARG1 ordered below ARG2 @> - x Is ARG2 ordered below ARG1 sametype - x Have ARG1 an ARG2 the same type sqrt x - Square root sin x - Sine (radians) cos x - Cosine (radians) integer x - Convert float to integer float x - Convert integer to float truncate x - Truncate float floor x - Round to next lower integer round x - Round float ceiling x - Round to next higher integer +, -, * and / produce float results if one of the arguments is a float. "and", "or", "xor", "shl" and "shr" require integer arguments. With the exception of "sametype" arguments must be bound to numbers. "@<" and "@>" implement a general ordering relation where vars < integers < floats < strings < lists < tuples < ports < modules Integers and floats are compared numerically, lists element by element, strings lexicographically, tuples by size and, if equal, element by element. All other objects are sorted by some arbitrary but stable order. Note that arguments to "compute" are not forced if unbound. Note that integer over- and underflow is not detected and will result in significant bits being silently truncated. See "is/2" for a more expressive way to perform arithmetic computations. current_seconds(SECONDS^) Unifies SECONDS with the current UNIX timestamp in seconds since 00:00, Jan. 1, 1970. deref(OBJECT?, DONE^) Recursively derefences variables in OBJECT until the term is fully ground, possibly suspending. Once all variables inside OBJECT are bound, DONE is unified with the empty list. error(MESSAGE?) Writes MESSAGE to standard error and terminates the program with exit code 1. Message may have any type and will be written as is, even if it contains unbound variables. foreign_call(TERM?) Invokes a builtin or user primitive specified by TERM. TERM must be a tuple. See below for more information about the foreign function interface. get_arg(INDEX?, TUPLE?, ITEM^) get_arg(INDEX?, TUPLE?, ITEM^, DONE^) Unifies ITEM with the INDEXth element of TUPLE, assigning the empty list to DONE, if given. Indexing starts at 1. Signals an error if INDEX is out of range. get_module(NAME?, MODULE^) Unifies MODULE with the module representing the interface to the linked FLENG module with the given name, which should be a string. getpid(PID^) Unifies PID with the UNIX process ID of the currently executing program. halt(EXITCODE?) Terminates the program with the given exit code, which must be an integer. RESULT^ is EXPRESSION Evaluates the numerical expression and unifies RESULT with the result of the computation. EXPRESSION must be an arithmetic expression and may not contain unbound variables. Available operations are: X + Y X - Y X * Y X / Y Usual arithmetic operators X \\ Y Integer remainder +X Identity -X Negation \X Bitwise NOT sqrt(X) integer(X) Truncate and convert to integer float(X) Convert integer to float X /\ Y Bitwise AND X \/ Y Bitwise OR X >< Y Bitwise XOR X << Y X >> Y Shift X by Y rnd Pseudo random float betwwen 0 and 1 floor(X) ceiling(X) round(X) Rounding operations sin(X) cos(X) Trigonometry Random numbers returned by "rnd" are uniformly distributed. Note that variables holding valid arithmetic expressions (as in ISO Prolog) are not supported. Signals an error if any argument is not numeric. length(OBJECT?, LEN^) Unifies LEN with the length of OBJECT, which may be a string, a list or a tuple. list_to_number(LIST?, NUMBER^) list_to_number(LIST?, BASE?, NUMBER^) Unifies NUMBER with the number consisting of the characters in LIST, which must specify a valid integer or floating point number. If LIST designates an integer, BASE determines in what numeric base the conversion should occur. list_to_string(LIST?, STRING^) Unifies STRING with the string holding the UNICODE code points in LIST. list_to_tuple(LIST?, TUPLE^) Unifies TUPLE with the string holding the elements of LIST. listen(FILE?, VAR^) Registers the file descriptor FILE with the internal polling loop and unifies VAR with the empty listonce data can be read from the file. To listen again, invoke "listen/2' again for the same file. log(MESSAGE?) Dereferences MESSAGE fully and writes it into the log file. make_tuple(LENGTH?, TUPLE^) Unifies TUPLE with a fresh tuple of the specified length, the resulting tuple is populated with unbound variables. Signals an error if LENGTH is not between 0 and 127. Creating a tuple of length 0 will unify TUPLE with the empty list. member(VALUE?, LIST?, BOOL^) Unifies BOOL with the string "true" or "false", depending on whether LUST contains a toplevel element that matches VALUE. number_to_list(NUMBER?, LIST^, TAIL?) number_to_list(NUMBER?, BASE?, LIST^, TAIL?) Converts the integer or float NUMBER into a list of character codes terminated by TAIL and unifies it with LIST. open_file(NAME?, MODE?, FILE^) Creates or opens a file with the name NAME in the given MODE, which may be on of the strings "r" (read), "w"(write) or "a" (append). The file descriptor will be unified with FILE. Signals an error if the file can not be opened. open_port(PORT^, LIST^) Creates a "port" object and unifies it with PORT. LIST is unified with a "stream" receiving objects send to PORT using the "send" primitive. When the port is not referenced anymore, the stream is closed by assigning the empty list to its tail. put_arg(INDEX?, TUPLE?, ITEM?) put_arg(INDEX?, TUPLE?, ITEM?, DONE^) Unifies the INDEXth element of TUPLE with ITEM, assigning the emptyx list to DONE, if given. Indexing starts at 1. Signals an error if INDEX is out of range. read_block(FILE?, COUNT?, LIST^, TAIL?) Reads COUNT bytes from the file designated by the file descriptor FILE and unifies LIST with the read data, terminated by TAIL. read_byte_stream(FILE?, LIST^) Reads bytes from the file designated by the file descriptor FILE and writes them into the stream given by LIST until the end of file is reached. read_char_stream(FILE?, LIST^) Reads UNICODE characters from the file designated by the file descriptor FILE and writes them into the stream given by LIST until the end of file is reached. randomize(SEED?, DONE^) Initializes the internal pseudo random number generator. SEED should be a string or a byte list. The buffer holding the random state has a size of 16 machine words. If the byte sequence given by SEED has a smaller size, then initialization "wraps around" to the start of SEED again. Once the random number generator has been initialized, DONE is unified with the empty list. self(ID^) Unifies ID with the thread number of the thread that is executing the current clause. send(PORT?, OBJECT?) send(PORT?, OBJECT?, DONE^) Sends OBJECT (which may be any data objecv whatsoever) to PORT and unifies DONE with the empty list, when given. signal(SIGNAL?, VAR^, DONE^) Installs a signal handler for the signal with the name given by the string SIGNAL, which should a valid uppercase Linux/BSD signal name. If the signal is raised, or was raised since the program started, the number of times the signal was raised is unified with VAR. Once the signal handler was installed, DONE is unified with the empty list. After VAR is bound, the signal handler must be re-established by another call to "signal/2". string_to_float(STRING?, FLOAT^) Converts the atom STRING to a floating-point number. If STRING can not be converted, then an error is signalled. string_to_integer(STRING?, INTEGER^) string_to_integer(STRING?, BASE?, INTEGER^) Converts the atom STRING to an integer, interpreting the characters in STRING in BASE. BASE defaults to 10. If STRING can not be converted, then an error is signalled. string_to_list(STRING?, LIST^, TAIL?) Converts STRING to a list of UNICODE code points, terminated by TAIL. threads(NUMBER^) Unifies NUMBER with the number of threads, as given to the "+THREADS" runtime option on startup. timer(MS?, VAR^) Establishes a single-shot timer that unifies VAR with the empty list after MS milliseconds have passed. true Does nothing. tuple_to_list(TUPLE?, LIST^, TAIL?) Unifies LIST with the elements of TUPLE, terminated by TAIL. unify(RESULT^, X?, Y?) Unifies X with Y and unifies RESULT with the string "true" or "false", depending on whether the unification succeeded or failed. Partial variable bindings on unification failure are not restored. utf_decode(LIST?, OUTLIST^) utf_decode(LIST?, CHAR^, REST^) Converts bytes in LIST to UNICODE code points. The former primitive writes characters into the stream OUTLIST until LIST is exhausted and closes OUTLIST by unifying it with the empty list. The latter primitive converts a single character and unifies REST with the remaining elements of LIST. utf_encode(CHAR?, LIST^, TAIL?) utf_encode(INLIST?, OUTLIST^) Convert UNICODE code points into a stream of bytes. The first primitive takes a character code and unifies LIST with the list of bytes required to encode CHAR, terminated by TAIL. The second primitive receives a stream of code points and produces a stream of bytes until the end of INLIST is reached," after which OUTLIST is unified with the empty list. when(VAR?, GOAL) Executes GOAL, which must not be an unbounded variable, once VAR is bound. write_block(FILE?, DATA?, DONE^) write_block(FILE?, DATA?, COUNT?, DONE^) Writes COUNT bytes of DATA to the file designated by the file descriptor FILE and unifies DONE with the empty list, once all data has been written. DATA may be a string or a byte list. If COUNT is not given, writes DATA completely. writeln(OBJECT?) writeln(OBJECT?, DONE^) Fully dereferences OBJECT and writes it to standard output, followed by a newline character. After writing, DONE is unified with the empty list, if given. * Alphabetical list of guard expressions: X == Y Succeeds if X matches Y. Note that matching never binds logic variables. If an argument variable in a clause head occurs several times, then subsequent occurrences imply an argument match equivalent to using "==/2", e.g. foo(X, [X]) :- ... is the same as foo(X, [Y]) :- X == Y | ... X =\= Y Succeeds if X does not match Y. X =:= Y Succeeds if X is numericall the same as Y, X and Y may be numerical expressions as in "is/2". X \=:= Y Succeeds if X is numerically different to Y. X and Y may be numerical expressions. X > Y Succeeds if X is numerically greater than Y. X and Y may be numerical expressions. X < Y Succeeds if X is numerically less than Y. X and Y may be numerical expressions. X >= Y Succeeds if X is numerically greater than or equal to Y. X and Y may be numerical expressions. X =< Y Succeeds if X is numerically less than or equal to to Y. X and Y may be numerical expressions. X @> Y Succeeds if X is ordered above Y. X @< Y Succeeds if X is ordered below Y X @>= Y Succeeds if X is ordered above or equal to Y. X @=< Y Succeeds if X is ordered below or equal to Y. atomic(X) Succeeds if X is a number or a string. data(X) Suspends if X is an unbound variable. This is identical to qualifying a head variable with "!". float(X) Succeeds if X is a floating point number. idle Suspends the clause until the current thread us "idle", that is, when no active processes are scheduled for execution. Once idle, the process will continue and subsequent matching of an "idle" guard will wait for the next idle cycle. integer(X) Succeeds if X is an integer. known(X) Succeeds if X is a non-variable object or a bound variable, the guard does not suspend in the case that X is bound. list(X) Succeeds if X is a non-empty list. module(X) Succeeds if X is a module. number(X) Succeeds if X is an integer or a floating point number. otherwise Always succeeds. A clause with this guard will only be matched if all textually previous clauses of the same process definition failed to match. port(X) Succeeds if X is a port object, string(X) Succeeds if X is a string. Note that this includes the empty list ("[]"). tuple(X) Succeeds if X is a tuple. unknown(X) Succeeds if X is an unbound variable, the guard does not suspend in that case. * Alphabetical list of declarations: initialization(PROCESSLIST) Declares the on startup, the processes given will be spawned. PROCESSLIST should be a string or a list of strings. uses(MODULELIST) Declares that the modules should be loaded and process definitions be made available for use using the "MODULE:GOAL" notation. MODULELIST may be a string or a list of strings. * Precedence and associativity of infix operators: The precedence and associativity of numerical operators follows the usual ISO Prolog syntax: Operator Associativity + - \ fy Highest precedence * / << >> yfx + - /\ \/ >< yfx : xfy = == =\= =:= \== @< @> @=< @>= is > < >= =< @ xfx , xfy | xfy :- xfx Lowest precedence VI. Debugging To analyse runtime errors, execution can be logged to standard error or a dedicated file using the "+LOG" runtime option. If a FLENG or FGHC file is compiled using the "-d" option, each entry into a clause is written to the log-file. Logging can be enabled for specific threads by using a suitable bit-mask specifying the threads that should be logged. The log-file is never deleted and new information is appended at the end, so you can use "tail -f" to follow the log over mulitple runs. Additionally, information about the overall status of the program is logged. If the "+STATS" or "+HEAPSTATS" run time options are given, statistics about memory use and process load are logged and can be subsequently filtered and analyzed using the "plot" utility included in the distribution which uses gnuplot(1) to show a graph of the collected statistics data like the number of active and suspended goals and an overall breakdown of heap usage. Note that logging has a severe performance impact due to file-system access and thread locking. Configuring the build with "--debug" adds debugging information to the C run time library and enables additional events to be logged. "plot" takes a log file and extracts either heap statistics (when the "-heap" option is given) or one or more of "axis" names that should be plotted in a graph. Only the latest run will be plotted if the log file holds logging data from multiple runs. VII. Data Representation and Interfacing to C Code Memory for all data objects is allocated from the "heap", which holds fixed size "cells". All data is made up from cells and each thread has its own private heap, data is (usually) never shared between threads. Unused memory is reclaimed using a reference counting scheme, where every store of a cell pointer increases the reference count and any release of a cell reduces the count. Once the count reaches zero, the cell is reclaimed and stored in the "freelist" from which new allocations take cells for further use. Cells have 3 fields: a "tag" and reference count cell, a head and a tail. The tag specifies what type of object the cell is representing, the head and tail point to other objects or contain integers. A datum is either a cell-pointer (of type "FL_CELL *), an integer of machine word size or a pointer to a string. Integers and strings are distinguished from pointers by having the lowest and next to lowest bit set, respectively, which means the cells are always located at a word size boundary. Integers are representable in the range of 63 (on 64 bit systems) or 31 bits (on 32 bit machines). The base type on the C level for all objects is "FL_VAL". Cells should never be modified destructively. Strings are "interned" and unique, a string with a given name exists only once in the entire process. Depending on type, the fields of a cell have various meanings: Head Tail List List head List tail Float IEEE double Unused* Variable Value+ Suspensions Tuple Head/name Arguments (list) Port Stream|source Unused Module Internal^ Unused Ref Source% Unused *: on 32 bit systems the head + tail fields contain the double +: points to the variable if unbound ^: internal pointer to module structure, with lowest bit set %: contains a pointer to a variable in another thread, with the lowest bit set A "ref" is a variable-like object referencing a variable in another thread. To call native code from FGHC or FLENG you can use the "foreign_call" form, which generates a call to an external function using the C ABI: foreign_call(my_func(Argument, ...)) will invoke an externally visible C function with the following prototype: void my_func_(FL_TCB *tcb, FL_VAL, ...)) "" is the number of arguments passed to the foreign function, at most 4 arguments can be passed. The "tcb" argument holds a pointer to a "thread control block" designating the thread context in which this foreign function is invoked. Normally, user code should not manipulate the reference counts of arguments or results, this is automatically handled by the compiler. Cell-pointers stored in external memory must have their reference count increased or may be invalidated when their reference count is decremented to zero in other code using the value. The "fleng-util.h" header file, which is installed along with the FLENG/FGHC compilers and runtime libraries, provides a number of macros and static functions to simplify working with data objects: CAR(x) CDR(x) Access the head and tail of the cell "x". COUNT(x) Returns the reference count of "x". TAG(x) Returns the type code of a cell, which is a 32 bit integer with the actual type located in the highest 8 bits. For tuples, the topmost bit is set and bits 25 to 31 contain the arity of the tuple (the number of arguments, not including the head). CHECK_INT(x) CHECK_STRING(x) CHECK_LIST(x) CHECK_NUMBER(x) CHECK_TUPLE(x) CHECK_VAR(x) Perform run-time checks on the type of "x". Note that "x" is not dereferenced. LIST(x, head, tail) Declares local variables of type "FL_VAL" with the names "head" and "tail" and initializes them to the result of extracting and dereferencing the head and tail parts of the list "x". TUPLE(x, name, arity, args) Declares local variables "name", "arity" and "args" of types "FL_VAL", "int" and "FL_VAL", respectively, and initializes them to the result of extracting the name, arity and arguments of the tuple "x". FLOAT(x, n) Declares the local variable "n" of type "double" containing the numerical value of "x", which may be an integer or float. addref(x) Increases the reference count of "x" and returns "x". deref(x) If "x" is not a variable, returns it unchanged. If it is a variable, then "deref" returns the value to which the variable is bound. If unbound, the variable is returned. It is crucial to dereference all arguments passed to a foreign function to make sure variables holding data work as expected. Note that unbound variable accesses do not suspend - this has to be handled in FGHC/FLENG code by using "!" or "data/1". mklist(tcb, car, cdr) Returns a freshly allocated list cell with the given head and tail values. Reference counts for the arguments are automatically increased. mktuple(tcb, name, arity, args) Returns a freshly allocated tuple with the given name, arity and argument list. The reference counts for the argument list is automatically increased. mkvar(tcb) Returns a freshly allocated unbound variable. unref(tcb, x) Decreases the reference count and releases "x" when the count reaches zero. In the latter case the cell is no longer valid and should not be used. "fleng.h" provides the base API for communicating with the runtime system in "libfleng": FL_VAL fl_nil, fl_true, fl_false Global variables holding predefined strings for the empty list and the strings "true" and "false". void fl_unify_result(FL_TCB *tcb, FL_VAL val, FL_VAL dest) Unifies "val" with "dest", increasing reference counts as necessary. void fl_assign(FL_TCB *tcb, FL_VAL x, FL_VAL var) Assigns "x" to "var", which must be an unbounded variable or a variable holding a value identical to "x". The reference count of "x" will be automatically increased on assignment. This function should normally only be used when "var" is expected to be unbound. FL_VAL fl_alloc_cell(FL_TCB *tcb, FL_VAL car, FL_VAL cdr) Allocates a memory cell by taking it from the pool of unused cells of this thread. "car" and "cdr" are the initial values of the head and tail of the cell. The reference count of the returned cell will be zero and the tag will not be initialized, yet. FL_VAL fl_alloc_float(FL_TCB *tcb, double x) Allocate a floating point number. Due to alignment reasons, you should always use this function to allocate floating point values. The reference count of the returned datum is zero. void fl_write(FL_TCB *tcb, FILE *fp, FL_VAL x) Writes the value of "x" to the given file stream. The operation may block the current thread. FL_VAL fl_mkstring(char *str, int len) Create a new string by interning it into the internal string table. "str" should point to the characters of the string and "len" hold the number of characters. The value returned will not share storage with "str". Note that interning is a slow operation and storage for interned strings is never recovered. int fl_nthreads(void) Returns the number of threads in the system. VIII. Bugs and Limitations * System limits: Maximal number of threads: 64 (32 on 32-bit platforms) Maximal number of local variables: 64 Maximal size of message sent to other threads: 4096 bytes Number of uninterrupted goal calls: 10 These settings can be changed using run time options: Default heap size per thread: 1000000 bytes Default timeslice: 10 Maximal number of active or suspended goals: 10000 Number of ticks between logging of statistics: 50 * Known bugs and shortcomings: - No measure is taken if a message sent from one thread to another exceeds the size of the message buffer. To hanle this is technically not a problem but just hasn't been implemented yet. - Unification does not perform an occurs check and the creation of circular data structures is not detected. IX. Further Reading [1] "FLENG Prolog - The Language which turns Supercomputers into Parallel Prolog Machines" Martin Nilsson and Hidehiko Tanaka [2] "Guarded Horn Clauses" PhD Thesis, Kazunori Ueda [3] "The Deevolution of Concurrent Logic Programming Languages" Evan Tick X. License This software is released under the BSD license, see the file "LICENSE" in the distribution archive. XI. Contact Information In case you need help, have suggestions or ideas, please don't hesitate to contact the author at felix AT call-with-current-continuation DOT org