Search

The history of atomic and molecular standards of time and frequency is traced from the earliest work on molecular and atomic beam resonance techniques to more recent developments that promise improved standards in the future. The various devices currently used as standards are discussed in detail from an historical prospective. The latter part of the article is devoted to a discussion of prospective developments which hold promise for major improvements in accuracy, stability and reproducibility.

We introduce MRFy, a tool for protein remote homology detection that captures beta-strand dependencies in the Markov random field. Over a set of 11 SCOP beta-structural superfamilies, MRFy shows a 14 percent improvement in mean Area Under the Curve for the motif recognition problem as compared to HMMER, 25 percent improvement as compared to RAPTOR, 14 percent improvement as compared to HHPred, and a 18 percent improvement as compared to CNFPred and RaptorX. MRFy was implemented in the Haskell functional programming language, and parallelizes well on multi-core systems. MRFy is available, as source code as well as an executable, from http://mrfy.cs.tufts.edu/.

Bayesian inference, of posterior knowledge from prior knowledge and observed evidence, is typically defined by Bayes's rule, which says the posterior multiplied by the probability of an observation equals a joint probability. But the observation of a continuous quantity usually has probability zero, in which case Bayes's rule says only that the unknown times zero is zero. To infer a posterior distribution from a zero-probability observation, the statistical notion of disintegration tells us to specify the observation as an expression rather than a predicate, but does not tell us how to compute the posterior. We present the first method of computing a disintegration from a probabilistic program and an expression of a quantity to be observed, even when the observation has probability zero. Because the method produces an exact posterior term and preserves a semantics in which monadic terms denote measures, it composes with other inference methods in a modular way-without sacrificing accuracy or performance.

Haskell gives computational biologists the flexibility and rapid prototyping of a scripting language, plus the performance of native code. In our experience, higher-order functions, lazy evaluation, and monads really worked, but profiling and debugging presented obstacles. Also, Haskell libraries vary greatly: memoization combinators and parallel-evaluation strategies helped us a lot, but other, nameless libraries mostly got in our way. Despite the obstacles and the uncertain quality of some libraries, Haskell's ecosystem made it easy for us to develop new algorithms in computational biology.

We present a novel variation on the standard technique of selecting instructions by tiling an intermediate-code tree. Typical compilers use a different set of tiles for every target machine. By analyzing a formal model of machine-level computation, we have developed a single set of tiles that is machine-independent while retaining the expressive power of machine code. Using this tileset, we reduce the number of tilers required from one per machine to one per architectural family (e.g., register architecture or stack architecture). Because the tiler is the part of the instruction selector that is most difficult to reason about, our technique makes it possible to retarget an instruction selector with significantly less effort than standard techniques. Retargeting effort is further reduced by applying an earlier result which generates the machine-dependent implementation of our tileset automatically from a declarative description of instructions' semantics. Our design has the additional benefit of enabling modular reasoning about three aspects of code generation that are not typically separated: the semantics of the compiler's intermediate representation, the semantics of the target instruction set, and the techniques needed to generate good target code.

Dataflow analysis and transformation of control-flow graphs is pervasive in optimizing compilers, but it is typically entangled with the details of a particular compiler. We describe Hoopl, a reusable library that makes it unusually easy to define new analyses and transformations for any compiler written in Haskell. Hoopl's interface is modular and polymorphic, and it offers unusually strong static guarantees. The implementation encapsulates state-of-the-art algorithms (interleaved analysis and rewriting, dynamic error isolation), and it cleanly separates their tricky elements so that they can be understood independently.

To illustrate the utility of a powerful modules language, this paper presents the embedded interpreter Lua-ML. The interpreter combines extensibility and separate compilation without compromising type safety. Its types are extended by applying a sum constructor to built-in types and to extensions, then tying a recursive knot using a two-level type; the sum constructor is written using an ML functor. The initial basis is extended by composing initialization functions from individual extensions, also using ML functors.

We have revisited the acoustic evidence in the Kennedy assassination--recordings of the two Dallas police radio channels upon which our original NRC report (Ramsey NF et al., Report of the Committee on Ballistic Acoustics. National Research Council (US). Washington: National Academy Press, 1982. Posted at http://www.nap.edu/catalog/10264.html) was based--in response to the assertion by DB Thomas (Echo correlation analysis and the acoustic evidence in the Kennedy assassination revisited. Science and Justice 2001; 41: 21-32) that alleged gunshot sounds (on Channel 1), apparently recorded from a motorcycle officer's stuck-open microphone, occur at the exact time of the assassination (as established by emergency communications on Channel 2). We have critically reviewed these two publications, and have performed additional analyses. In particular we have used recorded 60 Hz hum and correlation methods to obtain accurate speed calibrations for recordings made on both channels, cepstral analysis to seek instances of repeated segments during playback of Channel 2 (which could result from groove jumping), and spectrographic and correlation methods to analyze instances of putative crosstalk used to synchronize the two channels. This paper identifies serious errors in the Thomas paper and corrects errors in the NRC report. We reaffirm the earlier conclusion of the NRC report that the alleged "shot" sounds were recorded approximately one minute after the assassination.

Two different topics are discussed: (1) early (1950) stimulated emission amplification observed with a pure LiF crystal having an inverted population of the nuclear spin system and (2) the atomic H-maser.

When writing a program generator requires considerable intellectual effort, it is valuable to amortize that effort by using the generator to build more than one application. When a program generator serves multiple clients, however, the implementor must address pragmatic questions that implementors of single-use program generators can ignore. In how many languages should generated code be written? How should code be packaged? What should the interfaces to the client code look like? How should a user control variations? This paper elaborates on these questions by means of case studies of the New Jersey Machine-Code Toolkit, the $\lambda$-RTL Translator, and the ASDL program generator. It is hoped that the paper will stimulate the development of better techniques. Most urgently needed are a standard way to support multiple target languages and a simple, clear way to control interfaces to generated code.

A binary translator examines binary code for a source machine and generates code for a target machine. Understanding what to do with delayed branches in binary code can involve tricky case analyses, for example, if there is a branch instruction in a delay slot. This article presents a disciplined method for deriving such case analyses. The method identifies problematic cases, shows the translations for the nonproblematic cases, and gives confidence that all cases are considered. The method supports such common architectures as SPARC, MIPS, and PA-RISC, and it should apply to any tool that analyzes machine instructions. We begin by writing a very simple interpreter for the source machine's code. We then transform the interpreter into an interpreter for a target machine without delayed branches. To maintain the semantics of the program being interpreted, we simultaneously transform the sequence of source-machine instructions into a sequence of target-machine instructions. The transformation of the instructions becomes our algorithm for binary translation.

This paper presents a personal, qualitative case study of a first course using How to Design Programs and its functional teaching languages. The paper reconceptualizes the book's six-step design process as an eight-step design process ending in a new "review and refactor" step. It recommends specific approaches to students' difficulties with function descriptions, function templates, data examples, and other parts of the design process. It connects the process to interactive "world programs." It recounts significant, informative missteps in course design and delivery. Finally, it identifies some unsolved teaching problems and some potential solutions.

Experiments dependent on neutron spin orientation transitions which give fundamental physics information are described. The magnetic moment of the neutron has been measured to be 1.91304275(45) nuclear magnetons by separated oscillatory fields resonant reorientations of the spins of neutrons in a beam passing through a magnetic field. In similar resonance experiments with ultracold neutrons trapped in a bottle, the neutron electric dipole moment has been shown to be less than 9×10 −26 e cm. Neutrons `dressed' with many radiofrequency quanta have been studied. The Berry phases of neutrons that have passed through a helical magnetic field or an oscillatory magnetic field have been observed. In neutron interactions, experiments with condensed matter, small changes in neutron velocities have been measured by changes in the neutron precessions in magnetic fields before and after the interaction. Parity non-conserving spin rotations of neutrons passing through various materials have been observed and measured and new experiments with H 2 and He are in progress.

The early history of magnetic resonance to around 1950 is discussed from the point of view of a participant in it. I. I. Rabi’s theory of space quantization in a gyrating magnetic field and his molecular beam experiments in the 1930s laid the foundation of the magnetic resonance method, which he and his associates subsequently pursued and developed further at Columbia University, leading eventually to the development of NMR after World War II and the invention of the separated oscillatory fields method in 1950.

Many language processors make assumptions after detecting an error. If the assumptions are invalid, processors may issue a cascade of error messages in which only the first represents a true error in the input; later messages are side effects of the original error. Eliminating such spurious error messages requires keeping track of values within the compiler that are not available because of a previously detected error. Examples include symbol-table entries, types, and intermediate code. This paper presents a discipline for tracking unavailable values and avoiding cascading error messages. The discipline itself is unsurprising, but it is both formalized and implemented in terms of a type constructor and combinators expressed in Standard ML, and the ML type rules enforce the discipline. The type constructor distinguishes intermediate results that are unavailable because of a previously detected error. The combinators transform ordinary functions, which assume all intermediate results are available, into functions that silently propagate the unavailability of intermediate results. ML''s type system guides the application of the combinators; if the compiler writer does not account for a potentially unavailable value, the source code of the compiler does not type-check. The techniques presented exploit several features of Standard ML, including exceptions, higher-order functions, parametric polymorphism, and static type checking. Using these features enables the ML type system to ensure that the error-tracking discipline is applied consistently, relieving the programmer of that burden.

Unparsing is the problem of transforming an internal representation of a program into an external, concrete syntax. In conjunction with prettyprinting, it is useful for generating readable programs from internal representations. If the target language uses prefix and postfix operators, the problem is nontrivial. This paper shows how to unparse expressions using a simple, bottom-up tree walk, which keeps track of the least tightly binding operator not enclosed by parentheses. During the tree walk, this operator is compared with the operator of the parent expression, and parentheses are inserted based on the precedence, associativity, and fixity (infix, prefix, or postfix) of the two operators. The paper is a literate program. It includes code for the unparser and for its inverse parser, both of which can handle operators of dynamically chosen precedence and associativity. Supporting such operators is useful for languages like ML, in which programmers may assign precedence and associativity to their own functions. © 1998 John Wiley & Sons, Ltd.

Experiments which reorient neutron spins have been fruitful sources for botyh fundamental and applied physics, including the measurement of the neutron electric dipole moment as a test of time reversal symmetry [4,5]. “Dressed” neutrons [6] and Berry phased [7,8] have been studied with reoriened neutron spins. In neutron interaction condensed matter experiments, small changes in neutron velocity have been sensitively measured by the changes in the precession angle in magnetic fields before and after the interaction [9], or by comparing the direction of the neutron spin with a rotatin g magnetic field whose phase serves as a clock [10].

We present SLED, a specification language for Encoding and Decoding, which describes, abstract, binary, and assembly-language representations of machine instructions. Guided by a SLED specification, the New Jersey Machine-Code Toolkit generates bit-manipulating code for use in applications that process machine code. Programmers can write such applications at an assembly language level of abstraction, and the toolkit enables the applications to recognize and emit the binary representations used by the hardware. SLED is suitable for describing both CISC and RISC machines; we have specified representations of MIPS R3000, SPARC, Alpha, and Intel Pentium instructions, and toolkit users have written specifications for the Power PC and Motorola 68000. The article includes representative excerpts from our SPARC and Pentium specifications. SLED uses four elements; fields and tokens describe parts of instructions; patterns describe binary representations of instructions or group of instructions; and constructors map between the abstract and binary levels. By combining the elements in different ways, SLED supports machine-independent implementations of machine-level concepts like conditional assembly, span-dependent instructions, relocatable addresses, object code, sections, and relocation. SLED specifications can be checked automatically for consistency with existing assemblers. The implementation of the toolkit is largely determined by our representations of patterns and constructors. We use a normal form that facilitates construction of encoders and decoders. The article describes the normal form and its use. The toolkit has been used to help build several applications. We have built a retargetable debugger and a retargetable, optimizing linker. Colleagues have built a dynamic code generator, a decompiler, and an execution-time analyzer. The toolkit generates efficient code; for example, the linker emits binary up to 15% faster than it emits assembly language, making it 1.7-2 times faster to produce an a.out directly than by using the assembler.

This review of the history of early atomic clocks includes early atomic beam magnetic resonance, methods of separated and successive oscillatory fields, microwave absorption, optical pumping and atomic masers.

A definitional interpreter should be clear and easy to write, but it may run 4--10 times slower than a well-crafted bytecode interpreter. In a case study focused on implementation choices, we explore ways of making definitional interpreters faster without expending much programming effort. We implement, in OCaml, interpreters based on three semantics for a simple subset of Lua. We compile the OCaml to x86 native code, and we systematically investigate hundreds of combinations of algorithms and data structures. In this experimental context, our fastest interpreters are based on natural semantics; good algorithms and data structures make them 2--3 times faster than naïve interpreters. Our best interpreter, created using only modest effort, runs only 1.5 times slower than a mature bytecode interpreter implemented in C.

Literate programming tools let you arrange the parts of a program in any order and extract documentation and code from the same source file. The author argues that language-dependence and feature complexity have hampered acceptance of these tools, then offers a simpler alternative. >

In 1937 I. I. Rabi described the fundamental theory for magnetic resonance experiments in his great paper “Space Quantization in a Gyrating Magnetic Field.” This theory stimulated many subsequent developments, including molecular‐beam magnetic resonance, radiofrequency spectroscopy, nuclear magnetic resonance, masers and atomic clocks. Its imprint now stamps a tremendous range of experimental techniques and technological applications.

Despite years of work on retargetable compilers, creating a good, reliable back end for an optimizing compiler still entails a lot of hard work. Moreover, a critical component of the back end---the instruction selector---must be written by a person who is expert in both the compiler's intermediate code and the target machine's instruction set. By generating the instruction selector from declarative machine descriptions we have (a) made it unnecessary for one person to be both a compiler expert and a machine expert, and (b) made creating an optimizing back end easier than ever before.Our achievement rests on two new results. First, finding a mapping from intermediate code to machine code is an undecidable problem. Second, using heuristic search, we can find mappings for machines of practical interest in at most a few minutes of CPU time. Our most significant new idea is that heuristic search should be controlled by algebraic laws. Laws are used not only to show when a sequence of instructions implements part of an intermediate code, but also to limit the search: we drop a sequence of instructions not when it gets too long or when it computes too complicated a result, but when too much reasoning will be required to show that the result computed might be useful.

Descriptions are given of the methods of separated and successive oscillatory fields and of the atomic hydrogen maser. Their applications to precision spectroscopy of atoms and molecules are discussed along with specific examples of fundamental measurements best made with such devices. The applications of these methods to atomic clocks are also discussed. Cesium separated oscillatory fields atomic beam clocks are accurate to 10−13 and hydrogen masers are stable for several hours to 10−15. A discussion is given of fundamental experiments that require highly stable clocks, such as long base line radioastronomy, precise measurements of pulsar frequencies and stabilities, tests of the theories of relativity and accurate navigation both on the earth and in outer space.

In 1947, I.I. Rabi invented the molecular beam magnetic resonance method for the important, but limited purpose, of measuring nuclear magnetic moments and five of us working in his laboratory immediately began such experiments. The first experiments with LiCl gave the expected single resonance for each nucleus, but we were surprised to discover six resonances for the proton in H 2 , which we soon showed was due to the magnetic effects of the other proton and the rotating charged molecule: from these measurements we could also obtain new information on molecular structure. We had another shock when we studied D 2 and found the resonance curves were spread more widely for D 2 than H 2 even though the magnetic interactions should have been much smaller. We found we could explain this by assuming that the deuteron had an electric quadrupole moment and J. Schwinger pointed out that this would require the existence of a previously unsuspected electric tensor force between the neutron and the proton. With this, the resonance method was giving new fundamental information about nuclear forces. In 1944, Rabi and I pointed out that it should be possible by the Dirac theory and our past resonance experiments to calculate exactly the hyperfine interaction between the electron and the proton in the hydrogen atom and we had two graduate students, Nafe and Nelson do the experiment and they found a disagreement which led J. Schwinger to develop the first successful relativistic quantum field theory and QED. In 1964, Purcell, Bloch and others detected magnetic resonance transitions by the effect of the transition on the oscillator, called NMR, making possible measurements on liquids, solids and gases and giving information on chemical shifts and thermal relaxation times T1 and T2. I developed a magnetic resonance method for setting a limit to the EDM of a neutron in a beam and with others for neutrons stored in a suitably coated bottle. Magnetic resonance measurements provide high stability atomic clocks. Both the second and the meter are now defined in terms of atomic clocks. Lauterbuhr, Mansfield, Damadian and others developed the important methods of using inhomogeneous magnetic fields to localize the magnetic resonance in a tissue sample producing beautiful and valuable magnetic resonance images, MRI's, and fMRI's.

Descriptions are given of the methods of separated and successive oscillatory fields and of the atomic hydrogen maser. Their applications to the precision spectroscopy of atoms and molecules are discussed along with specific examples of fundamental measurements best made with such devices. The applications of these methods to atomic clocks are discussed. Cesium-separated oscillatory fields atomic beam clocks are accurate to 10(-13), and hydrogen masers are stable for several hours to 10(-15). A discussion is given of fundamental experiments that require highly stable clocks, such as long-base-line radio astronomy, precise measurement of pulsar frequencies and stabilities, tests of relativity theories, and accurate navigation both on the earth and in outer space.

The sections in this article are 1 Introduction 2 Earliest Searches for a Dependence of Magnetic Susceptibility on Frequency 3 Space Quantization When the Direction of a Magnetic Field Changes 4 First Attempts to Observe Magnetic Resonance in Condensed Matter 5 Transitions Induced by Passage of Molecules Through Differently Oriented Magnetic Fields 6 Molecular Beam Magnetic Resonance Methods 7 Electron Paramagnetic Resonance Experiments in Condensed Matter 8 Nuclear Magnetic Resonance Experiments in Condensed Matter 9 Chemical Shifts, Nuclear Magnetic Shielding and Electron-Coupled Nuclear Spin–Spin Interactions 10 Biographical Sketch

We present staged allocation , a technique for specifying calling conventions by composing tiny allocators called stages . A specification written using staged allocation has a precise, formal semantics, and it can be executed directly inside a compiler. Specifications of nine standard C~calling conventions range in size from 15 to 30 lines each. An implementation of staged allocation takes about 250 lines of ML or 650~lines of C++. Each specification can be used not only to help a compiler implement the calling convention but also to generate a test suite.

Writing an optimizing back end is expensive, in part because it requires mastery of both a target machine and a compiler's internals. We separate these concerns by isolating target-machine knowledge in declarative machine descriptions. We then analyze these descriptions to automatically generate machine-specific components of the back end. In this work, we generate a recognizer; this component, which identifies register transfers that correspond to target-machine instructions, plays a key role in instruction selection in such compilers as vpo, gcc and Quick C–. We present analyses and transformations that address the major challenge in generating a recognizer: accounting for compile-time abstractions not present in a machine description, including variables, pseudo-registers, stack slots, and labels.

A delightful feature of atomic physics is the frequency with which unexpected discoveries and ideas send research off in exciting new directions. These changes make the field interesting, but make predictions of the future unreliable. Nevertheless, speculations on the future of the field can be valuable.

Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when independently developed software components are combined into a larger system, significant relationships arise.To address this shortcoming, we define, as a conservative extension of ML, a language for manipulating interfaces. Our language includes operations for adding, renaming, and removing components; for changing the type associated with a value; for making manifest types abstract and vice versa; and for combining interfaces. These operations can express useful relationships among interfaces. We have defined a formal semantics in which an interface denotes a group of four sets; we show how these sets determine a subtyping relation, and we sketch the elaboration of an interface into its denotation.

For at least 25 years, the most effective way to retarget systems software has been by using machine descriptions. But “machine description” doesn’t mean what you think. A traditional machine description does contain information about the machine, but its utility is compromised in one of two ways: The description is useful only in support of a particular algorithm, such as instruction-set emulation, LR parsing, or bottom-up tree matching. Information about the machine is inextricably intertwined with information about a particular tool’s internal representation, such as a compiler’s intermediate code.

We present techniques that enable source-level debugging for multiple languages at the cost of only modest programming effort. The key idea is to avoid letting debugging requirements constrain the internal structure of the compiler. Constraints are minimized primarily by hiding the source-language type system and target-machine representations from the debugger. This approach enables us to support a new language and compiler while reusing existing elements: a multi-language, multi-platform debugger; the compiler's implementation of source-language types and expressions; information already present in the compiler's private data structures; and our compile-time support library, which helps the compiler meet its obligations to the debugger without exposing language-dependent details. We evaluate our approach using two case studies: the production compiler lcc and an instructional compiler for MiniJava.

Atomic Physics for many has been a fascinating forefront science, due in part to new ideas and discoveries that have renewed the field and sent research off in unexpected new directions. This report reviews some of the principal developments which have contributed to renewing the field.

Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.

Some codes require computations to use fewer bits of precision than are normal for the target machine. For example, Java requires 32-bit arithmetic even on a 64-bit target. To run narrow codes on a wide target machine, we present a widening transformation. Almost every narrow operation can be widened by sign- or zero-extending the operands and using a target-machine instruction at its natural width. But extensions can sometimes be avoided, and our transformation avoids as many as possible. The key idea is knowing what each operation can accept in the high bits of its arguments and what it can guarantee about the high bits of its result. This knowledge is formalized using fill types, which drive the widening transformation.

When a compiler translates a procedure, it must lay out the procedure’s stack frame in a way that respects the calling convention. Many compilers respect the convention either by restricting the order in which slots can be allocated or by using different abstractions ad hoc for allocating in different regions of a frame. Such techniques cause the implementation of the layout to be spread over much of the compiler, making it difficult to maintain and verify. We have concentrated the implementation of layout into a single, unifying abstraction: the block. The block abstraction decouples layout from slot allocation. Stack-frame layout is specified in one central place, and even complex layouts are achieved by composing blocks using only two simple operators. Our implementation is used in the Quick C– compiler to support multiple calling conventions on multiple architectures.

The accuracies of measurements of almost all fundamental physical constants have increased by factors of about 10 000 during the past 60 years. Although some of the improvements are due to greater care, most are due to new techniques based on quantum mechanics. Although the Heisenberg Uncertainty Principle often limits measurement accuracies, in many cases the validity of quantum mechanics makes possible the vastly improved measurement accuracies. Seven quantum features that have a profound influence on the science of measurements are: (1) Existence of discrete quantum states of energy. (2) Energy conservation in transitions between two states. (3) Electromagnetic radiation of frequency v is quantized with energy hv per quantum. (4) The identity principle. (5) The Heisenberg Uncertainty Principle. (6) Addition of probability amplitudes (not probabilities). (7) Wave and coherent phase phenomena. Of these seven quantum features, only the Heisenberg Uncertainty Principle limits the accuracy of measurements, and its affect is often negligibly small. The other six features make possible much more accurate measurements of quantum systems than with almost all classical systems. These effects are discussed and illustrated.

The earliest trapped atom coherent resonance experiments were with material traps or bottles. In the atomic hydrogen maser, the atoms are trapped inside a teflon-coated quartz bulb for about a second. Neutrons have been trapped for hundreds of seconds in suitably coated bottles or in superconducting magnetic traps. Results from experiments with trapped atoms and neutrons are reported.