skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on June 10, 2026

Title: Multi-stage Relational Programming
We transport multi-stage programming from functional to relational programming, with novel constructs to give programmers control over staging and non-determinism. We stage interpreters written as relations, in which the programs under interpretation can contain holes representing unknown expressions or values. By compiling the known parts without interpretive overhead and deferring interpretation to run time only for the unknown parts, we compound the benefits of staging (e.g., turning interpreters into compilers) and relational interpretation (e.g., turning functions into relations and synthesizing from sketches). We extend miniKanren with staging constructs and apply the resulting multi-stage language to relational interpreters for subsets of Racket and miniKanren as well as a relational recognizer for context-free grammars. We demonstrate significant performance gains across multiple synthesis problems, systematically comparing unstaged and staged computation, as well as indicatively comparing with an existing hand-tuned relational interpreter.  more » « less
Award ID(s):
2116372 2303983
PAR ID:
10621405
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
ACM Digital Library
Date Published:
Journal Name:
Proceedings of the ACM on Programming Languages
Volume:
9
Issue:
PLDI
ISSN:
2475-1421
Page Range / eLocation ID:
1591 to 1615
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Relational integration is required when multiple explicit representations of relations between entities must be jointly considered to make inferences. We provide an overview of the neural substrate of relational integration in humans and the processes that support it, focusing on work on analogical and deductive reasoning. In addition to neural evidence, we consider behavioral and computational work that has informed neural investigations of the representations of individual relations and of relational integration. In very general terms, evidence from neuroimaging, neuropsychological, and neuromodulatory studies points to a small set of regions (generally left lateralized) that appear to constitute key substrates for component processes of relational integration. These include posterior parietal cortex, implicated in the representation of first-order relations (e.g., A:B); rostrolateral pFC, apparently central in integrating first-order relations so as to generate and/or evaluate higher-order relations (e.g., A:B::C:D); dorsolateral pFC, involved in maintaining relations in working memory; and ventrolateral pFC, implicated in interference control (e.g., inhibiting salient information that competes with relevant relations). Recent work has begun to link computational models of relational representation and reasoning with patterns of neural activity within these brain areas. 
    more » « less
  2. We propose a rigorous modeling and methodological effort that integrates statistical implementation of hydrology models in predicting inland and coastal flood scenarios due to hurricanes and a scenario-based stochastic integer programming model which suggests resource and staging area decisions in the first stage and the evacuation decisions in the second stage. This novel study combines physics-based flood prediction models and stochastic optimization for large- scale multi-facility coordination of hospital and nursing home evacuations before impending hurricanes. The optimization model considers scenario-dependent evacuation demand, transport vehicles with varying capacities, and both critical and non-critical patients. Utilizing Hurricane Harvey of 2017 as a case study and actual healthcare facility locations in southeast Texas, we explore various evacuation policies, demonstrating the impact of routing strategies, staging area decisions, flood thresholds, and receiving facility capacities on evacuation outcomes. One of the findings is that choosing staging area(s) and deploying evacuation vehicles optimally considering the uncertainty of the hurricane’s path at the time of decision making could have significant effect on the total cost of the operation and evacuation time experienced by the evacuees. We also show the non-negligible value of the scenario-based staging and routing solution conservatively calculated in relation to a single scenario solution using the concept of value of stochastic solution. 
    more » « less
  3. At Carlsbad Caverns National Park, park rangers blended traditional personal interpretation with technology to showcase park-based research and to advance science literacy among visitors. Interpreters and Scientists Working on Our Parks (iSWOOP) provided interpreters with professional development and a selection of visualizations from scientists’ research on Brazilian free-tailed bats and their habitat at Carlsbad Caverns. After using tablets containing these visualizations for informal interpretive interactions, the interpreters responded to an open-ended survey. The authors examined interpreters’ responses, finding that interpreters regarded tablets as helpful in accomplishing several interpretive goals, especially in particular locations. Interpreters were strategic in initiating and sustaining interactions. Visitors’ reactions were positive; nevertheless, there were challenges indicating that this new form of interpretation is worthy of further research. 
    more » « less
  4. Abstract In this work, we proposed a two‐stage stochastic programming model for a four‐echelon supply chain problem considering possible disruptions at the nodes (supplier and facilities) as well as the connecting transportation modes and operational uncertainties in form of uncertain demands. The first stage decisions are supplier choice, capacity levels for manufacturing sites and warehouses, inventory levels, transportation modes selection, and shipment decisions for the certain periods, and the second stage anticipates the cost of meeting future demands subject to the first stage decision. Comparing the solution obtained for the two‐stage stochastic model with a multi‐period deterministic model shows that the stochastic model makes a better first stage decision to hedge against the future demand. This study demonstrates the managerial viability of the proposed model in decision making for supply chain network in which both disruption and operational uncertainties are accounted for. 
    more » « less
  5. We see the external world as consisting not only of objects and their parts, but also of relations that hold between them. Visual analogy, which depends on similarities between relations, provides a clear example of how perception supports reasoning. Here we report an experiment in which we quantitatively measured the human ability to find analogical mappings between parts of different objects, where the objects to be compared were drawn either from the same category (e.g., images of two mammals, such as a dog and a horse), or from two dissimilar categories (e.g., a chair image mapped to a cat image). Humans showed systematic mapping patterns, but with greater variability in mapping responses when objects were drawn from dissimilar categories. We simulated the human response of analogical mapping using a computational model of mapping between 3D objects, visiPAM (visual Probabilistic Analogical Mapping). VisiPAM takes point-cloud representations of two 3D objects as inputs, and outputs the mapping between analogous parts of the two objects. VisiPAM consists of a visual module that constructs structural representations of individual objects, and a reasoning module that identifies a probabilistic mapping between parts of the two 3D objects. Model simulations not only capture the qualitative pattern of human mapping performance cross conditions, but also approach human-level reliability in solving visual analogy problems. 
    more » « less