5 ms·

I haven't read this paper yet (I've been meaning to), but: a staged programming language is something like quasiquoting in Lisp, but typically with a typing dis

I haven't read this paper yet (I've been meaning to), but: a staged programming language is something like quasiquoting in Lisp, but typically with a typing discipline: a value can have the type "expression of type T". A two-stage program might have a type like "expression of type (expression of type U)". This helps to efficiently implement embedded languages just as Lisp macros can expand to faster code than runtime-interpreted metaprogramming; presumably the typing helps in that you don't have to start the compiling from "scratch" at the s-expression level. Stage polymorphism I guess means abstracting over how many stages there are till you get to plain old non-code data; hopefully someone will chime in who's more up to date or free to read the paper tonight.

weberc2 9y ago
> (Expression of type U) Isn't this how many statically toed functional languages model their type systems? 'list a' is an expression, is it not?
- abecedarius 9y ago
  Think of this like quoting and eval in Lisp. The type "expression of type U" might work with operations like eval: "expression of type U" -> U quote: U -> "expression of type U" chriswarbo's reply higher up should be taken to supersede my reply -- he's obviously more current on this stuff.
- naasking 9y ago
  > 'list a' is an expression, is it not No, it's a type. 'list' is a type constructor. Staging is a different beast from types altogether. Read up on MetaOCaml for how staging works in a typed language. You're probably confused by the fact that typed languages assign types to expressions, but a value of type "expression" is something different. You're reifying the AST of an expression as a value at runtime, and then you can build further expressions, and then compile them all.
  - weberc2 9y ago
    A type is an expression. The type of an expression is the result of evaluating the type expression, in this case, "list a". In other words, the type constructor invocation that gives the expression its type is itself an expression. In that context, I'm wondering how type expressions differ from "stages"--does the type expression language need to be sufficiently complex (e.g., Turing complete)?
    - naasking 9y ago
      > A type is an expression. A type is not an expression. We wouldn't have two words designating the same concept. Even in dependently typed languages where types and expressions are intermingled, they are still distinct concepts. Now, you can sort of talk about expressions in the "type language", but these are not expressions of the "value language". Even so, an unqualified statement like "a type is an expression" is simply incorrect because "expression" always refers to the value language, so that phrase conveys the completely wrong intention. Finally, as for how to relate staging to concepts you might be more familiar with, I suggest the paper, Closing the Stage: From Staged Code to Typed Closures [1]. [1] http://lambda-the-ultimate.org/node/2575 http://lambda-the-ultimate.org/node/2575
      - weberc2 9y ago
        Types (or "type expressions") are expressions whose type is type. In other words, types are higher order expressions. It's a poor definition or discipline that doesn't capture this basic concept.
        naasking 9y ago
        > Types (or "type expressions") are expressions whose type is type. This is only true in dependently typed languages. And even then, soundness requires stratifying types into universes or something similar. > In other words, types are higher order expressions. This isn't the meaning of higher order as it applies to programming languages or the standard isomorphism to logic.

weberc2 9y ago

> (Expression of type U) Isn't this how many statically toed functional languages model their type systems? 'list a' is an expression, is it not?

abecedarius 9y ago
Think of this like quoting and eval in Lisp. The type "expression of type U" might work with operations like eval: "expression of type U" -> U quote: U -> "expression of type U" chriswarbo's reply higher up should be taken to supersede my reply -- he's obviously more current on this stuff.
naasking 9y ago
> 'list a' is an expression, is it not No, it's a type. 'list' is a type constructor. Staging is a different beast from types altogether. Read up on MetaOCaml for how staging works in a typed language. You're probably confused by the fact that typed languages assign types to expressions, but a value of type "expression" is something different. You're reifying the AST of an expression as a value at runtime, and then you can build further expressions, and then compile them all.
- weberc2 9y ago
  A type is an expression. The type of an expression is the result of evaluating the type expression, in this case, "list a". In other words, the type constructor invocation that gives the expression its type is itself an expression. In that context, I'm wondering how type expressions differ from "stages"--does the type expression language need to be sufficiently complex (e.g., Turing complete)?
  - naasking 9y ago
    > A type is an expression. A type is not an expression. We wouldn't have two words designating the same concept. Even in dependently typed languages where types and expressions are intermingled, they are still distinct concepts. Now, you can sort of talk about expressions in the "type language", but these are not expressions of the "value language". Even so, an unqualified statement like "a type is an expression" is simply incorrect because "expression" always refers to the value language, so that phrase conveys the completely wrong intention. Finally, as for how to relate staging to concepts you might be more familiar with, I suggest the paper, Closing the Stage: From Staged Code to Typed Closures [1]. [1] http://lambda-the-ultimate.org/node/2575 http://lambda-the-ultimate.org/node/2575
    - weberc2 9y ago
      Types (or "type expressions") are expressions whose type is type. In other words, types are higher order expressions. It's a poor definition or discipline that doesn't capture this basic concept.
      - naasking 9y ago
        > Types (or "type expressions") are expressions whose type is type. This is only true in dependently typed languages. And even then, soundness requires stratifying types into universes or something similar. > In other words, types are higher order expressions. This isn't the meaning of higher order as it applies to programming languages or the standard isomorphism to logic.