Forward declaration of types.


#1

I would like to define a set of mutually recursive types.
The simplest way to accommodate this would to have some kind of forward declaration of types. Is this possible?

I can see that this was brought up once https://github.com/JuliaLang/julia/issues/269, but the issue was closed without any action that I can see.

The simplest example would be to represent a grammar that has two mutually recursive sub categories. Consider a language with both expressions (exp) and statements (stmt), with a grammar like.

exp ::= var | f(exp, …, exp), exp + exp, (stmt; stmt; exp)
stmt ::= f(exp, …, exp) | var := exp | if exp then stmt else stmt | while exp do stmt
| begin stmt ; … ; stmt end

The exp (stmt; stmt; exp) allows a user to run a few statements and then return the last exp as the value of the exp. What I want to avoid is mixing categories.
One does not want function calls like f(while exp so stmt). That is the purpose of the separate stmt and exp categories. When we can’t have two types in Julia which both mention each other as internal structures, this only becomes possible by some ugly work arounds. A forward declaration of types would fix. Any thoughts or non-ugly work arounds?.


#2

https://github.com/JuliaLang/julia/issues/269 is open for me.


#3

Perhaps as a newbie, I did not read the status correctly. I am hoping that maybe a fix is forthcomming?


#4

Yes, that issue is still open. Other issues that have referenced it have been merged and/or closed (and appear at the bottom), but none of those impact it directly. It’s currently in the “1.x” milestone, meaning it’ll be a new feature addition in some release after 1.0 (like 1.1 or 1.2 or some such).

There are a number of workarounds that have been posted in that issue — like using abstract types and type parameters.


#5

Here’s one potential workaround: Best way to make has_many/belongs_to relation for structs?

I agree that this would be a nice feature, but I haven’t found it to be a critical missing feature for my work.


#6

This is quite clever, and I’d say it almost works. I have tried to encode my example above as suggested. I include it below so others can see how this works on a medium sized example. All the types work out. But at the end, I’d like have a concrete type which instantiates the type parameters. Now it fails (see the last two lines which are commented out) because I have mutual recursion at the value level. Maybe there is a way do this?

abstract type AbsExp end
abstract type AbsStmt end

type Var
  name::Symbol
end

type ECall{e <: AbsExp}
  fun::Symbol
  args::Array{e,1}
end  
  
type ESeq{e <: AbsExp, s <: AbsStmt}
  effects :: Array{s,1}
  result :: e
end  

type Exp{s <: AbsStmt} <: AbsExp
  exp:: Union{Var,ECall{Exp{s}},ESeq{Exp{s},s}}
end  

type SCall{e <: AbsExp}
  fun::Symbol
  args::Array{e,1}
end  
  
type SSeq{s <: AbsStmt}
  body :: Array{s,1}
end   

type Assign{e <: AbsExp}
  lhs:: Symbol
  rhs:: e
end

type Stmt{e <: AbsExp} <: AbsStmt
  stmt:: Union{SCall{e},SSeq{Stmt{e}},Assign{e}}
end  

# Expression = Exp{Statement} 
# Statement = Stmt{Expression}

#7

Maybe you can make your example minimal? Then you are more likely to get a reply.