Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

Abnormal photoresponses and light-induced apoptosis in rods lacking rhodopsin kinase

Phosphorylation is thought to be an essential first step in the prompt deactivation of photoexcited rhodopsin. In vitro, the phosphorylation can be catalyzed either by rhodopsin kinase (RK) or by protein kinase C (PKC). To investigate the specific role of RK, we inactivated both alleles of the RK gene in mice. This eliminated the light-dependent phosphorylation of rhodopsin and caused the single-photon response to become larger and longer lasting than normal. These results demonstrate that RK is required for normal rhodopsin deactivation. When the photon responses of RK−/− rods did finally turn off, they did so abruptly and stochastically, revealing a first-order backup mechanism for rhodopsin deactivation. The rod outer segments of RK−/− mice raised in 12-hr cyclic illumination were 50% shorter than those of normal (RK+/+) rods or rods from RK−/− mice raised in constant darkness. One day of constant light caused the rods in the RK−/− mouse retina to undergo apoptotic degeneration. Mice lacking RK provide a valuable model for the study of Oguchi disease, a human RK deficiency that causes congenital stationary night blindness.

The diversity and evolutionary relationships of the pregnancy-associated glycoproteins, an aspartic proteinase subfamily consisting of many trophoblast-expressed genes

The pregnancy-associated glycoproteins (PAGs) are structurally related to the pepsins, thought to be restricted to the hooved (ungulate) mammals and characterized by being expressed specifically in the outer epithelial cell layer (chorion/trophectoderm) of the placenta. At least some PAGs are catalytically inactive as proteinases, although each appears to possess a cleft capable of binding peptides. By cloning expressed genes from ovine and bovine placental cDNA libraries, by Southern genomic blotting, by screening genomic libraries, and by using PCR to amplify portions of PAG genes from genomic DNA, we estimate that cattle, sheep, and most probably all ruminant Artiodactyla possess many, possibly 100 or more, PAG genes, many of which are placentally expressed. The PAGs are highly diverse in sequence, with regions of hypervariability confined largely to surface-exposed loops. Nonsynonymous (replacement) mutations in the regions of the genes coding for these hypervariable loop segments have accumulated at a higher rate than synonymous (silent) mutations. Construction of distance phylograms, based on comparisons of PAG and related aspartic proteinase amino acid sequences, suggests that much diversification of the PAG genes occurred after the divergence of the Artiodactyla and Perissodactyla, but that at least one gene is represented outside the hooved species. The results also suggest that positive selection of duplicated genes has acted to provide considerable functional diversity among the PAGs, whose presence at the interface between the placenta and endometrium and in the maternal circulation indicates involvement in fetal–maternal interactions.

The Vibrio cholerae genome contains two unique circular chromosomes

Vibrio cholerae, the etiologic agent of the diarrheal disease cholera, is a Gram-negative bacterium that belongs to the γ subdivision of the family Proteobacteriaceae. The physical map of the genome has been reported, and the genome has been described as a single 3.2-Mb chromosome [Majumder, R., et al. (1996) J. Bacteriol. 178, 1105–1112]. By using pulsed-field gel electrophoresis of genomic DNA immobilized in agarose plugs and digested with the restriction enzymes I-CeuI, SfiI, and NotI, we have also constructed the physical map of V. cholerae. Our analysis estimates the size of the genome at 4.0 Mb, 25% larger than the physical map reported by others. Our most notable finding is, however, that the V. cholerae chromosome appears to be not the single chromosome reported but two unique and separate circular megareplicons.

The thiazide-sensitive Na–Cl cotransporter is an aldosterone-induced protein

Although the collecting duct is regarded as the primary site at which mineralocorticoids regulate renal sodium transport in the kidney, recent evidence points to the distal convoluted tubule as a possible site of mineralocorticoid action. To investigate whether mineralocorticoids regulate the expression of the thiazide-sensitive Na–Cl cotransporter (TSC), the chief apical sodium entry pathway of distal convoluted tubule cells, we prepared an affinity-purified, peptide-directed antibody to TSC. On immunoblots, the antibody recognized a prominent 165-kDa band in membrane fractions from the renal cortex but not from the renal medulla. Immunofluorescence immunocytochemistry showed TSC labeling only in distal convoluted tubule cells. Semiquantitative immunoblotting studies demonstrated a large increase in TSC expression in the renal cortex of rats on a low-NaCl diet (207 ± 21% of control diet). Immunofluorescence localization in tissue sections confirmed the strong increase in TSC expression. Treatment of rats for 10 days with a continuous subcutaneous infusion of aldosterone also increased TSC expression (380 ± 58% of controls). Furthermore, 7-day treatment of rats with an orally administered mineralocorticoid, fludrocortisone, increased TSC expression (656 ± 114% of controls). We conclude that the distal convoluted tubule is an important site of action of the mineralocorticoid aldosterone, which strongly up-regulates the expression of TSC.

Stimulation of β1-Integrin Function by Epidermal Growth Factor and Heregulin-β Has Distinct Requirements for erbB2 but a Similar Dependence on Phosphoinositide 3-OH Kinase

Integrins and growth factor receptors are important participants in cellular adhesion and migration. The EGF receptor (EGFR) family of tyrosine kinases and the β1-integrin adhesion receptors are of particular interest, given the implication for their involvement in the initiation and progression of tumorigenesis. We used adhesion and chemotaxis assays to further elucidate the relationship between these two families of transmembrane signaling molecules. Specifically, we examined integrin-mediated adhesive and migratory characteristics of the metastatic breast carcinoma cell line MDA-MB-435 in response to stimulation with growth factors that bind to and activate the EGFR or erbB3 in these cells. Although ligand engagement of the EGFR stimulated modest β1-dependent increases in cell adhesion and motility, heregulin-β (HRGβ) binding to the erbB3 receptor initiated rapid and potent induction of breast carcinoma cell adhesion and migration and required dimerization of erbB3 with erbB2. Pharmacologic inhibitors of phosphoinositide 3-OH kinase (PI 3-K) or transient expression of dominant negative forms of PI 3-K inhibited both EGF- and HRGβ-mediated adhesion and potently blocked HRGβ- and EGF-induced cell motility. Our results illustrate the critical role of PI 3-K activity in signaling pathways initiated by the EGFR or erbB3 to up-regulate β1-integrin function.

Specific Molecular Chaperone Interactions and an ATP-dependent Conformational Change Are Required during Posttranslational Protein Translocation into the Yeast ER

The posttranslational translocation of proteins across the endoplasmic reticulum (ER) membrane in yeast requires ATP hydrolysis and the action of hsc70s (DnaK homologues) and DnaJ homologues in both the cytosol and ER lumen. Although the cytosolic hsc70 (Ssa1p) and the ER lumenal hsc70 (BiP) are homologous, they cannot substitute for one another, possibly because they interact with specific DnaJ homologues on each side of the ER membrane. To investigate this possibility, we purified Ssa1p, BiP, Ydj1p (a cytosolic DnaJ homologue), and a GST–63Jp fusion protein containing the lumenal DnaJ region of Sec63p. We observed that BiP, but not Ssa1p, is able to associate with GST–63Jp and that Ydj1p stimulates the ATPase activity of Ssa1p up to 10-fold but increases the ATPase activity of BiP by <2-fold. In addition, Ydj1p and ATP trigger the release of an unfolded polypeptide from Ssa1p but not from BiP. To understand further how BiP drives protein translocation, we purified four dominant lethal mutants of BiP. We discovered that each mutant is defective for ATP hydrolysis, fails to undergo an ATP-dependent conformational change, and cannot interact with GST–63Jp. Measurements of protein translocation into reconstituted proteoliposomes indicate that the mutants inhibit translocation even in the presence of wild-type BiP. We conclude that a conformation- and ATP-dependent interaction of BiP with the J domain of Sec63p is essential for protein translocation and that the specificity of hsc70 action is dictated by their DnaJ partners.