pith. sign in

arxiv: 1907.08834 · v1 · pith:NPFB5K6Znew · submitted 2019-07-20 · 💻 cs.PL · cs.LG· cs.LO

Towards meta-interpretive learning of programming language semantics

S\'andor Bartha , James Cheney This is my paper

Pith reviewed 2026-05-24 18:38 UTC · model grok-4.3

classification 💻 cs.PL cs.LGcs.LO
keywords inductive logic programmingprogramming language semanticsmeta-interpretive learningoperational semanticsexample-based learningnonterminating computations
0
0 comments X

The pith

Inductive logic programming can learn the operational semantics of programming languages from sets of example evaluations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a new use case for inductive logic programming by showing how it can derive the rules that define a language's meaning directly from observed program behaviors. It works through a simplified version of the problem to surface three concrete obstacles: treating function symbols as variables rather than fixed names, managing examples that do not terminate, and inferring predicates that never appear explicitly in the data. Extensions to the base learning procedure are offered to meet these obstacles. A sympathetic reader would care because successful automation of semantics acquisition would remove a manual bottleneck in building verified compilers, interpreters, and static analyzers.

Core claim

We introduce a new application for inductive logic programming: learning the semantics of programming languages from example evaluations. In this short paper, we explored a simplified task in this domain using a meta-interpretive learning system. We highlighted the challenging aspects of this scenario, including abstracting over function symbols, nonterminating examples, and learning non-observed predicates, and proposed extensions helpful for overcoming these challenges, which may prove useful in other domains.

What carries the argument

An inductive logic programming procedure that abstracts over function symbols, tolerates nonterminating traces, and invents unobserved predicates while constructing semantic rules from evaluation examples.

If this is right

  • Semantic definitions for simple languages become derivable from test suites rather than hand-written.
  • The same learning procedure may transfer to other rule-induction tasks that involve partial observations and nontermination.
  • Once non-observed predicates can be invented reliably, the approach can capture hidden state or auxiliary relations needed for full semantics.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the method scales, it could be paired with existing test-generation tools to produce candidate semantics that are then checked against a formal specification.
  • The same abstraction-over-symbols technique might apply to learning rewrite systems or type-inference rules from examples.
  • Success on nonterminating examples suggests the learner could eventually handle reactive or concurrent languages whose traces are infinite.

Load-bearing premise

The three listed challenges can be solved by modest extensions to the learning procedure and that the resulting procedure will generalize past the simplified examples.

What would settle it

Run the extended learner on a small set of terminating and nonterminating evaluations for a language with first-order functions; if it produces incorrect or incomplete semantic rules that a human can write by inspection, the claim fails.

read the original abstract

We introduce a new application for inductive logic programming: learning the semantics of programming languages from example evaluations. In this short paper, we explored a simplified task in this domain using the Metagol meta-interpretive learning system. We highlighted the challenging aspects of this scenario, including abstracting over function symbols, nonterminating examples, and learning non-observed predicates, and proposed extensions to Metagol helpful for overcoming these challenges, which may prove useful in other domains.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript introduces a new application area for inductive logic programming: learning the semantics of programming languages from example evaluations. Using the Metagol system on a deliberately simplified task, it identifies three challenges (abstracting over function symbols, handling nonterminating examples, and learning non-observed predicates) and proposes extensions to Metagol that may prove useful in addressing them.

Significance. The paper identifies a novel potential domain for meta-interpretive learning with clear relevance to program analysis and formal methods. Its value lies in the explicit framing of the application and the enumeration of concrete technical challenges rather than in any demonstrated results or implementations.

minor comments (1)
  1. The manuscript is very brief; a short concrete example of the simplified task (even if unsuccessful) would help readers assess the proposed challenges without lengthening the paper substantially.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept. The report contains no major comments requiring a point-by-point reply.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is a short exploratory note that introduces a new ILP application area and identifies three challenges plus proposed Metagol extensions that 'may prove useful.' No equations, fitted parameters, derivations, or load-bearing self-citations appear in the provided text or abstract. The contribution is framed as an application proposal rather than any claim that reduces by construction to prior inputs or self-citations. This is self-contained against external benchmarks and receives the default non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the background assumptions of inductive logic programming and Metagol's meta-interpretive capabilities; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • ad hoc to paper Metagol can be extended to handle abstract function symbols, nonterminating examples, and non-observed predicates
    The abstract proposes extensions without providing implementation details or justification beyond identifying the challenges.

pith-pipeline@v0.9.0 · 5597 in / 1089 out tokens · 18202 ms · 2026-05-24T18:38:04.582364+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    ACM Tra nsactions on Pro- gramming Languages and Systems 30(5), 26:1–26:47 (2008)

    Cheney, J., Urban, C.: Nominal logic programming. ACM Tra nsactions on Pro- gramming Languages and Systems 30(5), 26:1–26:47 (2008)

    work page 2008

  2. [2]

    In: IJCAI

    Cropper, A., Muggleton, S.H.: Learning Higher-order Log ic Programs Through Abstraction and Invention. In: IJCAI. pp. 1418–1424. AAAI P ress (2016)

    work page 2016

  3. [3]

    Cropper, A., Muggleton, S.H.: Metagol System (2016), https://github.com/metagol/metagol

    work page 2016

  4. [4]

    Cropper, A., Tamaddoni-Nezhad, A., Muggleton, S.: Meta- interpretive learning of data transformation programs. In: ILP. pp. 46–59. Springer -Verlag (2015)

    work page 2015

  5. [5]

    In: ILP (2018)

    Cropper, A., Tourret, S.: Derivation reduction of metaru les in meta-interpretive learning. In: ILP (2018)

    work page 2018

  6. [6]

    The MIT Press, 1st edn

    Felleisen, M., Findler, R.B., Flatt, M.: Semantics Engin eering with PLT Redex. The MIT Press, 1st edn. (2009)

    work page 2009

  7. [7]

    In: SNAPL (2019)

    Krishnamurthi, S., Lerner, B.S., Elberty, L.: The Next 70 0 Semantics: A Research Challenge. In: SNAPL (2019)

    work page 2019

  8. [8]

    https://www.doc.ic.ac.uk/~ml1909/ILASP (2015)

    Law, M., Russo, A., Broda, K.: The ILASP system for learnin g answer set pro- grams. https://www.doc.ic.ac.uk/~ml1909/ILASP (2015)

    work page 2015

  9. [9]

    In: ECAI

    Lin, D., Dechter, E., Ellis, K., Tenenbaum, J., Muggleton , S.: Bias Reformulation for One-shot Function Induction. In: ECAI. pp. 525–530 (201 4)

    work page

  10. [10]

    Cambridge Uni- versity Press, New York, NY, USA, 1st edn

    Miller, D., Nadathur, G.: Programming with Higher-Orde r Logic. Cambridge Uni- versity Press, New York, NY, USA, 1st edn. (2012)

    work page 2012

  11. [11]

    The Journal of Logic and Algebraic Programming 60-61, 195 – 228 (2004)

    Mosses, P.D.: Modular structural operational semantic s. The Journal of Logic and Algebraic Programming 60-61, 195 – 228 (2004)

    work page 2004

  12. [12]

    Muggleton, S.H., Lin, D., Pahlavi, N., Tamaddoni-Nezha d, A.: Meta-interpretive Learning: Application to Grammatical Inference. Mach. Lea rn. 94(1), 25–49 (2014). https://doi.org/10.1007/s10994-013-5358-3

    work page doi:10.1007/s10994-013-5358-3 2014

  13. [13]

    Machine Learning 100(1), 49–73 (Jul 2015)

    Muggleton, S.H., Lin, D., Tamaddoni-Nezhad, A.: Meta-i nterpretive learning of higher-order dyadic datalog: predicate invention revis ited. Machine Learning 100(1), 49–73 (Jul 2015)

    work page 2015

  14. [14]

    The Journal of Logic and Algebraic Programming 60-61, 17–139 (2004)

    Plotkin, G.D.: A Structural Approach to Operational Sem antics. The Journal of Logic and Algebraic Programming 60-61, 17–139 (2004)

    work page 2004

  15. [15]

    Ray, O.: Nonmonotonic abductive inductive learning. J. Applied Logic 7(3), 329–340 (2009). https://doi.org/10.1016/j.jal.200 8.10.007, https://doi.org/10.1016/j.jal.2008.10.007

    work page doi:10.1016/j.jal.200 2009