CODEWITHSUNDEEP
functional-programmingclosureslanguage-agnosticinterpreterself-reference
rwallace
rwallace

Reputation: 33475

Representing closures as finite terms

I am working on a meta-interpreter for a language fragment that needs to be rich enough to support higher-order functions, and running into a problem with closures.

Specifically, I need all values to be representable as finite terms; no infinite recurrence, no objects pointing to each other. This is fine for most kinds of values, numbers, finite lists, maps, abstract syntax trees representing program code. The problem is closures; they contain a reference to their containing environment, but if a closure is stored in a local variable, then that containing environment also contains a reference to the closure. This is fine if you are working with mutable pointers, but it's an infinite recurrence if you are trying to work with finite terms.

Is there a known technique for representing closures as finite terms, or some technique I am missing that bypasses the problem?

Upvotes: 0

Views: 43

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

I once had a similar problem when I wrote a functional language that used reference counting GC, and therefore had to avoid any cyclic references.

My solution was that the environment didn't actually include a pointer to the closure. Instead, it stored a function that would produce the closure when you pass it a pointer to the environment.

The process of looking up a value from the environment would include calling that function to produce the closure if necessary. That function, of course, doesn't need a cyclic pointer to the environment, because the environment will be passed in.

This trick is basically making recursive data structures in the same way that the Y combinator is used to make recursive functions.

Upvotes: 2

Related Questions