CODEWITHSUNDEEP
functionf#functional-programmingabstract-syntax-tree
OctarineSorcerer
OctarineSorcerer

Reputation: 445

Functional Programming: Embedding functions in AST?

I'm currently attempting to use F# to model linking functions together as part of an AST (though at the moment it's more of a chain). Each link is a function, which may also have a chain attached to it. However, to specify the type signature of the chain attached to the link, you must also add more type parameters. But you do that, and then one more parameter is added, etc. ad infinitum. An example of this is below.

type Chain<'a, 'b, 'c> =
| Link of ('a -> 'b) * Chain<'c>  // This doesn't work - you need more type params supplied
| End  of 'a

I would like to be able to express the chain as something like Link ((fun x -> x + 5), Link... and so forth until it reaches an End, but I can't see a way to do so without encountering the type explosion problem.

If anybody could point me in a direction that would help create a chain of arbitrary functions, of arbitrary length, I'd appreciate it.

Upvotes: 2

Views: 169

Answers (1)

kvb
kvb

Reputation: 55184

Although the question's a little bit unclear, I think what you're asking for is something more like (hypothetical syntax):

type Chain<'a> =
| Link of ('b -> 'a) * Chain<'b>
| End of 'a

where we introduce a new type parameter 'b inside the case for Link - it can be any type, as long as the domain of the function matches the type argument of the nested Chain<_>. This is related to the idea of an "existential type" (basically the dual notion of universal type quantification by generics).

Bad news: there's no simple syntax to achieve this in F#. Good(?) news: there's an extremely ugly way to encode this, if you really want to.

The upshot is that if you want to express the idea of something like your link type, you can do it by introducing a few auxiliary types in a mechanical way (the type ∃'t.F<'t> can be encoded as ∀'x.(∀'t.F<'t> -> 'x) -> 'x, which can be expressed with the F# type system).

Here's what your example looks like under this encoding:

type 'a Chain =
| End of 'a
| Link of SomeLink<'a>
and SomeLink<'a> = abstract Apply : LinkUser<'a,'x> -> 'x
and LinkUser<'a,'x> = abstract Apply : ('b -> 'a) * Chain<'b> -> 'x

let mkLink (f, c) = Link { new SomeLink<_> with member __.Apply(w) = w.Apply(f, c) }

let chain = mkLink (sprintf "%i", End 1)

let rec applyChain<'a> : 'a Chain -> 'a = function
| End a -> a
| Link l -> l.Apply { new LinkUser<_,_> with member __.Apply(f, c) = f (applyChain c) }

applyChain chain // "1"

Upvotes: 4

Related Questions