This paper is to design Dimensional Analysis (DA) algorithms for the multidimensional Lucid, the equational data flow language, which also includes user-defined functions. The significance is that the DA is indispensable for an efficient implementation of multidimensional Lucid and should aid the implementation of other data flow systems, such as Google’s TensorFlow. Data flow is a form of computation in which components of Multidimensional Data-sets (MDDs) travel on communication lines in a network of processing stations. Each processing station incrementally transforms its input MDDs to its output, another (possibly very different) MDD. MDDs are very common in Health Information Systems and data science in general. An important concept is that of a relevant dimension. A dimension is relevant if the coordinate of that dimension is required to extract a value. It is essential that in calculating with MDDs we avoid non-relevant dimensions, otherwise, we duplicate entries (say, in a cache) and waste time and space.For example, if X is the MDD of raw rain measurements, its dimensionality is {location, day, hour}, and that of Y is {location, day}. Note that the dimensionality is more than just the rank, which is simply the number of dimensions. Previously, there was extensive research on data-flow itself, which we summarize. Nevertheless, an exhaustive literature search uncovered no relevant previous DA work. Our methodology is that we proceeded incrementally, solving increasingly difficult instances of DA corresponding to increasingly sophisticated language features. However, in this paper, we solved the DA of multidimensional Data Flow (DF) programs. We also solved the difficult problem (which the GLU (Granular Lucid) team never solved) of determining the dimensionality of the DF programs that include user-defined functions, including recursively defined functions. We do this by adapting the PyLucid interpreter (to produce the DAM interpreter) to evaluate the entire program over the (finite) domain of dimensionalities. As a result, the experimentally validated algorithms in our paper can produce useful upper bounds for the dimensionalities of the variables in multidimensional PyLucid programs. That also includes those with user-defined functions.

Although the language Lucid was not originally intended to support computing with infinite data structures, the notion of (infinite) sequence quickly came to the fore, together with a demand-driven computation model in which demands are propagated for the values of particular values at particular index points. This naturally generalized to sequences of multiple dimensions so that a programmer could, for example, write a program that could be understood as a (nonterminating) loop in which one of the loop variables is an infinite vector. Programmers inevitably found use for more and more dimensions, which led to a problem which is fully solved for the first time in this paper. The problem is that the implementation's cache requires some estimate of the dimensions actually used to compute a value being fetched. This estimate can be difficult or (if dimensions are passed as parameters) impossible to obtain, and the demand-driven evaluation model for Lucid breaks down. We outline the evolution of Lucid which gave rise to this problem, and outline the solution, as used for the implementation of TransLucid, the latest descendant of Lucid.

We propose a purely extensional semantics for higher-order logic programming. In this semantics program predicates denote sets of ordered tuples, and two predicates are equal iff they are equal as sets. Moreover, every program has a unique minimum Herbrand model which is the greatest lower bound of all Herbrand models of the program and the least fixed-point of an immediate consequence operator. We also propose an SLD-resolution proof system which is proven sound and complete with respect to the minimum Herbrand model semantics. In other words, we provide a purely extensional theoretical framework for higher-order logic programming which generalizes the familiar theory of classical (first-order) logic programming.

We propose a novel collaborative recommendation approach to take advantage of the information available in user-created lists. Our approach assumes associations among any two items appearing in a list together. We calculate sum of Bayesian ratings (SBR) of all lists containing an item pair as the strength of item-item associations in that pair. SBR takes into consideration not only the number of lists the items have co-appeared in, but also the quality of the lists. We collected a data set of user ratings for books along with Listmania lists on Amazon.com using Amazon Web Services (AWS). Our method shows superior performance to existing user-based and item-based collaborative filtering approaches according to the resulted MAE, coverage and F-measure.

We present the Eager TransLucid language, an inten- sional programming language in which the value of a variable is a function mapping multidimensional contexts - the "possible worlds" of intensional logic - to ground values or, equivalently, that variables define multidimensional arrays of arbitrary dimensionality. The Eager TransLucid language is a natural generalisation of Wadge and Ashcroft's Lucid dataflow language. Given a specific set of equations and a context, the operational semantics determines the value taken by a variable in that context, which may depend both on the values of dimensions within the context and the values of variables in other contexts. The contexts correspond to tags in tagged-token dataflow systems. The key contribution of the paper is to prove that it is possible to create a warehouse caching the values of already computed (identifier, context) pairs in such a way as to ensure that no reference is made to unnecessary dimensions. The method consists of storing demands for relevant dimensions in the current context as these are needed.

We give a purely model-theoretic characterization of the semantics of logic programs with negation-as-failure allowed in clause bodies. In our semantics, the meaning of a program is, as in the classical case, the unique minimum model in a program-independent ordering. We use an expanded truth domain that has an uncountable linearly ordered set of truth values between False (the minimum element) and True (the maximum), with a Zero element in the middle. The truth values below Zero are ordered like the countable ordinals. The values above Zero have exactly the reverse order. Negation is interpreted as reflection about Zero followed by a step towards Zero ; the only truth value that remains unaffected by negation is Zero . We show that every program has a unique minimum model M P , and that this model can be constructed with a T P iteration which proceeds through the countable ordinals. Furthermore, we demonstrate that M P can alternatively be obtained through a construction that generalizes the well-known model intersection theorem for classical logic programming. Finally, we show that by collapsing the true and false values of the infinite-valued model M P to (the classical) True and False , we obtain a three-valued model identical to the well-founded one.

In this paper we demonstrate that a broad class of higher-order functional programs can be transformed into semantically equivalent multidimensional intensional programs that contain only nullary variable definitions. The proposed algorithm systematically eliminates user-defined functions from the source program, by appropriately introducing context manipulation (i.e. intensional) operators. The transformation takes place in M steps, where M is the order of the initial functional program. During each step the order of the program is reduced by one, and the final outcome of the algorithm is an M -dimensional intensional program of order zero. As the resulting intensional code can be executed in a purely tagged-dataflow way, the proposed approach offers a promising new technique for the implementation of higher-order functional languages.

The purpose of this paper is to demonstrate that first-order functional programs can be transformed into intensional programs of nullary variables, in a semantics preserving way. On the foundational side, the goal of our study is to bring new insights and a better understanding of the nature of functional languages. From a practical point of view, our investigation provides a formal basis for the tagging mechanism that is used in the implementation of first-order functional languages on dataflow machines.

In temporal logic programming, a stream can be specified by a single-valued, time-varying predicate which, at any given moment in time, represents the corresponding element in the stream. However, due to inherent non-determinism in logic programming, time-varying predicates do not necessarily represent single-valued relations at any given moment in time. Choice predicates are also time-varying predicates, but, in principle, they act like a dataflow node with multiple input lines which non-deterministically selects one of its inputs as output. Thus they are guaranteed to be single-valued at all moments in time, and they can be regarded as representing ‘non-deterministic’ streams. Users do not define choice predicates, they are supplied automatically for all predicates defined in temporal logic programs. Inputs to choice predicates are supplied by the corresponding predicates. When the connection between choice predicates and the corresponding predicates is established, we obtain non-Horn temporal logic programs as a result. The model-theoretic semantics of such a program is developed in terms of ‘minimal models’. However, the logical structure of the program dictates which minimal models are constructible from the program. We in particular discuss a characterization of constructible minimal models as limits of alternating chains of models obtained by applications of two new mappings NTP and CP. The paper also outlines a proof procedure for the temporal language Chronolog extended with choice predicates.

Abstract Sloth is a simple Unix‐based tool for creating and maintaining large C programs built from reusable ‘modules’. Sloth is a collection of UNIX shell commands for creating and editing modules, and for producing executables by linking compiled code from the modules comprising a program. Sloth in a sense extends C by providing module facilities similar to those built in to newer languages such as Modula‐II. The Sloth ‘extensions’, however, are at the shell level only. No changes are required in C itself; in fact, the Sloth commands invoke the standard Unix C compiler. A Sloth module contains a set of C procedures and local declarations, a set of global definitions and variable declarations, an initialization routine and an ‘import’ list of other modules containing declarations referred to, but not defined by, the module in question. The Sloth link command has one argument, the name of a ‘root’ directory. The link command automatically identifies all those modules imported directly or indirectly by the root module, checks that the object code for each module is up‐to‐date and recompiles where necessary. It then creates a main program in which the various initialization routines are executed in the correct order (most primitive first), compiles it and links it with all the object files and produces an executable program. Individual modules can be compiled without any knowledge of the application that uses, directly or indirectly, the module in question. Two applications that both use a collection of modules can therefore share the object code for these modules. The use and implementation of Sloth are presented, as are the experience in using it, programming techniques developed to take full advantage of its facilities, as well as several extensions, either completed or planned.

A method for controlling versions of software and other hierarchically structured entities is presented. Using the variant structure principle, a particular version of an entire system is formed by combining the most relevant existing versions of the various components of the system. An algebraic version language that allows histories (numbered series), subversions (or variants), and joins is described. It is shown that the join operation is simply the lattice least upper bound and together with the variant structure principle, provides a systematic framework for recombining divergent variants. The utility of this approach is demonstrated using LEMUR, a programming environment for modular C programs, which was developed using itself. The ways in which this notion of versions is related to the possible world semantics of intensional logic are discussed.>

A constructive criticism of recent work in the semantics of programming languages is offered.The criticism is directed not so much at the techniques and results obtained as at the use to which they are put.The fact that denotational (or "mathematical") semantics plays on the whole a passive ("descriptive") role, whil e operational semantics plays on the whole an active ("prescriptive") role, is seen as the basic problem.It is suggested that these roles be reversed.

In this paper we describe how Lucid can be extended to allow user-defined functions and scope conventions, i.e. conventions for limiting the range or scope of the validity of definitions. This is done using new constructs called clauses which are similar in form to the blocks and procedure declarations of Algol-like languages, but are nevertheless strictly non-imperative, because a clause is actually a compound assertion, i.e. an assertion formed, as a program is, by combining a collection of assertions.Each type of clause (there are four) has a straightforward mathematical semantics together with its own characteristic "manipulation rules" for general program massage. In addition, the informal operational view of (some) Lucid programs (described in a previous paper) can be extended to give an (incomplete) operational understanding of the effect of the clauses. In this framework a "compute" clause defines a block; a "mapping" clause defines a conventional (pointwise) function; a "produce" clause defines a block with persistent memory (or an anonymous 'process' or 'actor'); and a "function" clause defines a sort of procedure with own variables (or a general kind of coroutine).

Lucid is both a programming language and a formal system for proving properties of Lucid programs. The programming language is unconventional in many ways, although programs are readily understood as using assignment statements and loops in a “structured” fashion. Semantically, an assignment statement is really an equation between “histories”, and a whole program is simply an unordered set of such equations. From these equations, properties of the program can be derived by straightforward mathematical reasoning, using the Lucid formal system. The rules of this system are mainly those of first order logic, together with extra axioms and rules for the special Lucid functions. This paper formally describes the syntax and semantics of programs, and justifies the axioms and rules of the formal system.

Non-parametric classification is concerned with the classification of populations of objects when the underlying statistical model is the unknown parameter. The analysis of formal models of non-parametric classification involves the quantification of the stability of individual classes. This problem has not been solved in general. The problem of stability is discussed and a method for computing expectations of certain generalised distance functions is presented. These quantities, while of technical interest to the question of stability, are frequently encountered in general in probabilistic computations in non-parametric classification. A set of techniques is described for reducing generalised distance functions to normal form in which no further variables may be removed algebraically. The techniques involve symbolic methods, linear substitution and gcd reduction. Additional reductions are obtained by fast Fourier transform and determination of appropriate confidence intervals. Finally, it is shown that many of the frequently used distance functions are reducible to the same normal form and that this form involves only variable.