Natural Language Semantics as Program Execution

30 concepts20 papers1 proposal

Traditional approaches to linguistics often treat language as a static container. In this "container model," words hold fixed meanings, and sentences are decoded by mapping linguistic symbols directly to truth values or static dictionary definitions.

However, human communication is inherently dynamic, context-dependent, and action-oriented. To capture how language actually functions, a powerful alternative paradigm shifts the focus from what a sentence is to what a sentence does. Instead of viewing an utterance as a static description, this perspective treats natural language as a program composed of computational and cognitive procedures. Understanding a sentence means executing its underlying code to update an internal state, query a database, or interact with the physical world.

The Shift from Static to Operational Meaning

If meaning is a program, then language comprehension is the process of running that program within a structured mental environment. An early foundation for this view appears in an unauthored COLING 1969 preprint, which formalized natural language messages as programs within a nondeterministic system. In this framework, decoding text is not a passive translation but an operational process that transforms the listener's internal state.

This state-transformation model was expanded by Janusz Stanislaw Bien in Toward A Multiple Environments Model Of Natural Language, where utterances act as explicit instructions to update a listener's internal simulation or "environment." Rather than evaluating whether a sentence is true or false in isolation, the cognitive system executes the utterance to see how it alters the current context.

[Static Model]      Sentence ──> Maps to ──> Static Truth Value / Definition
[Procedural Model]  Sentence ──> Acts as ──> Executable Program ──> Updates Context/State

Lexical Items as Executable Functions

In a procedural framework, words are no longer passive labels; they are functions, objects, or subroutines. Jean Pierre Paillet argued in Computational Linguistics and Linguistic Theory that lexical items and the functors that integrate them are computational procedures designed to actively construct meaning structures.

This procedural architecture can be implemented using diverse computational paradigms:

  • Object-Oriented Message Passing: Nishida et al. demonstrated that lexical items can be modeled as computational objects equipped with internal methods. Interpreting a sentence becomes a dynamic process of message passing between these objects.
  • Distributed Lexical Instructions: In sentence production, Parisi et al. showed that the knowledge required to build a sentence can be distributed directly within lexical entries as step-by-step instructions that guide conceptual integration.
  • Context-Sensitive Generation: For natural language generation, David D. McDonald demonstrated that representing linguistic elements as executable procedures allows an AI system to inspect the current discourse state dynamically, making real-time decisions such as choosing between a pronoun or a full noun phrase (Language Generation: The Linguistics Component).

Managing Context and Resolving Ambiguity

One of the greatest challenges for static semantics is context dependency—such as resolving pronouns ("it", "he") or handling presuppositions. When sentences are compiled into programs, however, these challenges become standard computational problems like variable binding and state management.

Bouche et al. showed that translating sentences into executable programs within a dynamic predicate logic (DPL) framework allows a system to handle unbound anaphors and presuppositions naturally. As the program executes line by line, the context updates, making variables available for subsequent instructions.

Furthermore, focusing on the construction rather than the final reference provides deeper analytical power. Tomas Chrz argued in Application of Intensional Logic to Knowledge Representation that representing knowledge by the specific procedure that generates it—rather than its direct denotation—allows computational systems to precisely analyze and disambiguate complex language structures.

Grounding Language in the Physical World

The procedural view provides an elegant solution to the "symbol grounding problem" in robotics and embodied AI. If a robot is told to "pick up the block to the left of the box," a static definition of "left" is useless. The robot needs to know how to find the block.

Spranger et al. demonstrated that representing spatial language as a sequence of cognitive operations allows robotic agents to dynamically compute the reference of an expression based on their immediate physical context. In later work, Spranger et al. showed that these operations can be incrementally assembled into an executable network or program. To ground the phrase, the robot runs the program against its perceptual data—for example, executing a visual filtering operation followed by a spatial relationship calculation to isolate the target object.

"Left of the box" ──> Assembled Program:

1. Locate('box') 
                      2. ApplySpatialRelation('left') 
                      3. FilterEnvironment() 
                      ──> Executed against sensor data

Cognitive Construction and Uncertainty

In human cognition, this procedural assembly relies heavily on internal memory and background knowledge. Trott et al. argue that language understanding requires systems to actively synthesize linguistic inputs with conceptual repertoires to construct a coherent mental scene. This process is highly interactive; Rui Ma frames meaning as a dynamic interaction between language symbols and experiential memory, rejecting the idea that meaning is stored passively inside words (The Cognitive Turn of Translation Study in Artificial Intelligence Era).

Because every individual possesses a unique background environment, these programs can run differently across different listeners. Yueqin Gao used mental space theory to demonstrate that human communication breakdowns often stem from divergent procedural integrations, where the speaker and hearer map and execute the same linguistic signals into entirely different emergent mental structures (Mental Space Theory and Misunderstanding).

Finally, this procedural execution can handle real-world vagueness and uncertainty. Lotfi A. Zadeh demonstrated in PRUF - A Language for the Representation of Meaning in Natural Languages that meaning can be formalized as a computational procedure that calculates fuzzy constraint distributions when executed against a database of relations. Similarly, Cappelli et al. showed that complex conceptual operations can be modeled as domain-independent functions operating on top of structured knowledge networks, simulating cognitive processes rather than merely storing static facts.

By shifting from static representations to executable programs, procedural semantics provides a robust framework for language processing. It explains not only how language conveys abstract information, but how it dynamically interacts with context, resolves ambiguity, and triggers physical action.

Key Foundational Work

International Conference on Computational Linguistics COLING 1969: Preprint No. 29 (1969) — contributed 4 concept elements to this direction.
Towards a Computational Formalization of Natural Language Semantics (1969) — contributed 2 concept elements to this direction.
Computational Linguistics and Linguistic Theory (1973) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_procedural_semantics_4e702645,
  title = {procedural semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/procedural-semantics/rdr_4e702645fdd34cd3977ce98ade1f20b1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_procedural_semantics_4e702645_v1,
  title = {procedural semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/procedural-semantics/rdr_4e702645fdd34cd3977ce98ade1f20b1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake