4 ms·
Based on my limited knowledge, SSA form is at a higher level than AST (right?). If yes, would SSA be considered an example of HOAS? Regardless, besides the que
by fizixer 10y ago
Based on my limited knowledge, SSA form is at a higher level than AST (right?). If yes, would SSA be considered an example of HOAS?
Regardless, besides the question posed by OP, I wonder what the relation between SSA and HOAS might be?
- mafribe 10y agoASTs and SSA are orthogonal concepts. ASTs are a representation of syntax (including SSA) where immediate subterms are easily accessible (unlike with strings as representation). Easy access to subterms is important for the efficiency of type-checkers and code-generators. In contrast, SSA is a simple programming language that is often used as an intermediate form in code generators. HOAS is a form of embedding a language L with binders into a language L-Base also with binders and functions, but such that L-binders are handled by functions in L-Base and the problem of defining capture-avoiding substitution for L-terms is reduced to reusing L-Base's capture-avoiding substitution. (NB L = L-Base is possible but not required.) HOAS is neat, but (simplifying a bit) prevents you from making inductive definitions on L terms. There are various ways of getting around this shortcoming, the most principled one is probably the nominal approach of A. Pitts et al. Another problem with HOAS is that the representation may contain 'junk'. That means there are L-Base terms that do not represent L-programs.