27739305
Explicit Environments
We introduce λƐ, a simply typed calculus with environments as first class values. As well as the usual constructs of λ and application, we have e[[a]] which evaluates term a in an environment e. Our environments are a set of variable-value pairs, but environments can also be computed by function application and evaluation in some other environments. The notion of environments here is a generalization of explicit substitutions and records. We show that the calculus has desirable properties such as subject reduction, confluence, conservativity over the simply typed λβ-calculus and strong normalizability.
10509424
A Simply Typed Context Calculus with First-class Environments
We introduce a simply typed λ-calculus λϰƐ" which has both contexts and environments as first-class values. In λϰƐ", holes in contexts are represented by ordinary variables of appropriate types and hole filling is represented by the functional application together with a new abstraction mechanism which takes care of packing and unpacking of the term which is used to fill in the holes of the context. λϰƐ" is a conservative extension of the simply typed λβ-calculus, enjoys subject reduction property, is confluent and strongly normalizing. 
 
The traditional method of defining substitution does not work for our calculus. So, we also introduce a new method of defining substitution. Although we introduce the new definition of substitution out of necessity, the new definition turns out to be conceptually simpler than the traditional definition of substitution.
46610662
CAL: A Computer Assisted Learning System for Computation and Logic
In this paper, we describe a computer system CAL which assists students' understanding of a lecture course in logic and computation. We introduce a new foundational theory of expressions, which is inspired by the theory of expressions due to Martin-Lof [6], and use the expressions determined by the theory to implement various syntactic objects in CAL. We also introduce the concept of derivation game, and show that various logical and computational systems given in the lecture course can be defined uniformly by derivation games.
1580777
Classical Brouwer-Heyting-Kolmogorov Interpretation
The Brouwer-Heyting-Kolmogorov interpretation explains the meaning of logical operations as operators that construct proofs from proofs of the operands. The BHK interpretation is usually understood as giving intuitionistic interpretation for the logical operators, but, as pointed out by Troelstra and van Dalen [12], it is possible to understand the BHK interpretation classically. We elaborate this idea and develop a classical theory of proofs as abstract mathematical entities where the truth of a proposition becomes equivalent to the existence of proofs of the proposition.
8686702
Theory of Judgments and Derivations
We propose a computational and logical framework NF (Natural Framework) which is suitable for presenting mathematics formally. Our framework is an extendable framework since it is open-ended both computationally and logically in the sense of Martin-Lof's theory or types. NF is developed in three steps. Firstly, we introduce a theory of expressions and schemata which is used to provide a universe for representing mathematical objects, in particular, judgments and derivations as well as other usual mathematical objects. Secondly, we develop a theory of judgments within the syntactic universe of expressions. Finally, we introduce the notions of derivation and derivation game and will show that we can develop mathematics as derivation games by regarding mathematics as an open-ended process of defining new concepts and deriving new judgments. Our theory is inspired by Martin-Lof's theory of expressions and Edinburgh LF, but conceptually much simpler. Our theory is also influenced by Gentzen's natural deduction systems.
1796136
Strong normalizability of the non-deterministic catch/throw calculi
The catch/throw mechanism in Common Lisp provides a simple control mechanism for non-local exits. We study typed calculi by Nakano and Sato which formalize the catch/throw mechanism. These calculi correspond to classical logic through the Curry-Howard isomorphism, and one of their characteristic points is that they have non-deterministic reduction rules. These calculi can represent various computational meaning of classical proofs. This paper is mainly concerned with the strong normalizability of these calculi. Namely, we prove the strong normalizability of these calculi, which was an open problem. We first formulate a non-deterministic variant of Parigot's λμ-calculus, and show it is strongly normalizing. We then translate the catch/throw calculi to this variant. Since the translation preserves typing and reduction, we obtain the strong normalization of the catch/throw calculi. We also briefly consider second-order extension of the catch/throw calculi. Copyright 2002 Elsevier Science B.V
7223292
Preliminary evaluation of dynamic load balancing using loop re-partitioning on Omni/SCASH
Increasingly large-scale clusters of PC/WS continue to become majority platform in HPC field. Such a commodity cluster environment, there may be incremental upgrade due to several reasons, such as rapid progress in processor technologies, or user needs and it may cause the performance heterogeneity between nodes from which the application programmer will suffer as load imbalances. To overcome these problems, some dynamic load balancing mechanisms are needed. In this paper, we report our ongoing work on dynamic load balancing extension to Omni/SCASH which is an implementation of OpenMP on Software Distributed Shared Memory, SLASH. Using our dynamic load balancing mechanisms, we expect that programmers can have load imbalances adjusted automatically by the runtime system without explicit definition of data and task placements in a commodity cluster environment with possibly heterogeneous performance nodes.
17823591
Network interface active messages for low overhead communication on SMP PC clusters
NICAM is a communication layer for SMP PC clusters connected via Myrinet, designed to reduce overhead and latency by directly utilizing a micro-processor equipped on the network interface. It adopts remote memory operations to reduce much of the overhead found in message passing. NICAM employs an Active Messages framework for flexibility in programming on the network interface, and this flexibility will compensate for the large latency resulting from the relatively slow micro-processor. Running message handlers directly on the network interface reduces the overhead by freeing the main processors from the work of polling incoming messages. The handlers also make synchronizations faster by avoiding the costly interactions between the main processors and the network interface. In addition, this implementation can completely hide latency of barriers in data-parallel programs, because handlers running in the background of the main processors allow reposition of barriers to any place where the latency is not critical.
31025719
Programming with Distributed Data Structure for EM-X Multiprocessor
The EM-X, a new generation of EM-4, is a distributed memory multiprocessor which has a dataflow mechanism. The dataflow mechanism enables a fine-grain communication packet through the network to invoke and synchronize the thread of control dynamically with very small overhead. In this paper, we present programming with a distributed data structure shared by threads, and its implementation for the EM-X multiprocessor. Threads may communicate and coordinate by leaving data in a global address space. A new distributed data structure, called the Q-structure, is introduced. This can be used as a shared queue in the context of thread-based programming in the parallel programming language EM-C. We also discuss related distributed data structures including Liuda'a tuple space, synchronizing data structure in the dataflow computation model.
35864792
Experience with executing shared memory programs using fine-grain communication and multithreading in EM-4
We present our experience and results obtained from executing shared memory application programs using fine-grain remote memory access communication and multithreading in the EM-4 multiprocessor. The EM-4 is a distributed memory multiprocessor which has a dataflow mechanism. The dataflow mechanism enables a fine-grain communication packet through the network to invoke the thread of control dynamically with very small overhead and is extended to access remote memory in different processors. We hide the remote memory access latencies with multithreading. The benchmark results show that shared memory applications achieve reasonable speedup with four to eight threads in the EM-4 prototype. We found that aggressive multithreading can negatively affect its network interface and increase the network contention. We also describe the EM-4 parallel programming language called EM-C, which provides the notion of a global address space and parallel constructs for exploiting medium-grain parallelism to tolerate several remote operation latencies.<<ETX>>
32545241
Ninf: A Network Based Information Library for Global World-Wide Computing Infrastructure
Ninf is an ongoing global network-wide computing infrastructure project which allows users to access computational resources including hardware, software and scientific data distributed across a wide area network. Ninf is intended not only to exploit high performance in network parallel computing, but also to provide high quality numerical computation services and accesses to scientific database published by other researchers. Computational resources are shared as Ninf remote libraries executable at a remote Ninf server. Users can build an application by calling the libraries with the Ninf Remote Procedure Call, which is designed to provide a programming interface similar to conventional function calls in existing languages, and is tailored for scientific computation. In order to facilitate location transparency and network-wide parallelism, Ninf metaserver maintains global resource information regarding computational server and databases, allocating and scheduling coarse-grained computation for global load balancing. Ninf also interfaces with the WWW browsers for easy accessibility.