Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Collapsing towers of interpreters [pdf]

cs.purdue.edu

Post reply on HN
Print view View original

21–25 of 25 posts

Re: Collapsing towers of interpreters [pdf]

#21

Post by weberc2 »

naasking wrote: post #13
weberc2 wrote: post #12

Earlier quoted context omitted.

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)?

> 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…

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.

Re: Collapsing towers of interpreters [pdf]

#22

Post by tiarkrompf »

phaedrus wrote: post #19
tiarkrompf wrote: post #14

I'm one of the authors. Happy to answer questions.

I've been working on techniques to enable a low-level interpreter engine to present (meta level) user function names in stack traces and (meta level) user variables on the debugger watch window, instead of just spilling the guts of the interpreter when you break into it with a C++ debugger. The basic idea is to design the API of the expression-building library so that the user code is always written in the form of ca…

Sounds interesting. About the role of CPS: for specialization purposes, CPS can have some benefits by splitting control flow. For example, if your input is "if (c) a else b" and c is a staged (=symbolic) value, then a CPS interpreter can ignore the control-flow join that's implied by the if-then-else, and continue processing longer paths independently. However, this also quickly leads to exponential code blow-up, and hence, we do not use CPS for the core model described in the paper.

Re: Collapsing towers of interpreters [pdf]

#23

Post by phaedrus »

tiarkrompf wrote: post #22
phaedrus wrote: post #19

Earlier quoted context omitted.

I've been working on techniques to enable a low-level interpreter engine to present (meta level) user function names in stack traces and (meta level) user variables on the debugger watch window, instead of just spilling the guts of the interpreter when you break into it with a C++ debugger. The basic idea is to design the API of the expression-building library so that the user code is always written in the form of ca…

Sounds interesting. About the role of CPS: for specialization purposes, CPS can have some benefits by splitting control flow. For example, if your input is "if (c) a else b" and c is a staged (=symbolic) value, then a CPS interpreter can ignore the control-flow join that's implied by the if-then-else, and continue processing longer paths independently. However, this also quickly leads to exponential code blow-up, and…

Thanks! The main application I'm looking at is logic programming, so the control flow example you give is apropos. For example a user function which requests A AND B could be written: "if not(A) then fail, else if not(B) then fail, else succ". The first time through, we might want to actually take every branch so that we learn about the whole expression. At this stage it's just building a graph that records edges between variables and constraints, so the exponential factor is averted.

However I keep going back and forth between having the user write logic in a "control flow" representation versus in a "declarative" way (e.g. "return A && B"). The declarative way expresses intent directly, but loses most of the hooks for stepping through in a callback. Expressing it as control flow on the other hand requires some form of custom control flow operators because the built-in ones can't be redefined in C++.

It turns out logical "OR" is very subtle because we want to "actually have taken" exactly one of the options, but we also don't want to fail contexts where the preconditions for both sides are satisfied; we actually just want to arbitrarily pick one (and then the other), but only one per run (except when we're reflecting).

Subtle things like that make me nervous as requirements the user's control flow logic has to abide by. So my main challenge is to either figure out constructs which make this foolproof, or come up with "nearly declarative" forms: code which expresses intent declaratively, but does so in multiple statements so that they can be single-stepped through.

Re: Collapsing towers of interpreters [pdf]

#24

Post by naasking »

weberc2 wrote: post #21
naasking wrote: post #13

Earlier quoted context omitted.

> 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…

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.

> 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.

Re: Collapsing towers of interpreters [pdf]

#25

Post by chriswarbo »

phaedrus wrote: post #20
chriswarbo wrote: post #17

Earlier quoted context omitted.

Forgive my lack of C++ knowledge, but surely inheritance is a separate topic to polymophism? If we think of a classic OOP example, we might say (in some made-up language): Mammals can breathe Mammals can move Dogs are Mammals Dolphins are Mammals From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) { try { m.move(); return "Free"; } catch { try { m.…

C++ supports multiple kinds of polymorphism depending on if and how they can be implemented with no or low runtime overhead. C++ does tend to conflate class inheritance with interface polymorphism, but there is an implementation reason for doing so. In C++, an image of the data members of a base class is embedded verbatim inside a derived object. This means that a function compiled to work with a pointer to a block o…

Thanks for the info. I'm not sure if it's supporting my point, refuting it, or is an aside :)

> Also, C++ doesn't distinguish between interfaces and classes; an interface in C++ is just a class with no data members.

This doesn't invalidate the point about polymorphism being orthogonal to inheritance. The point is that we can choose whether or not to use inheritance: `breathe` could be implemented in `Mammal` and get inherited by `Dog` and `Dolphin`, or Dog and Dolphin could implement `breathe` themselves and there would be no inheritance. Either way, we still have (subclass) polymorphism, so saying "polymorphism should mean inheritance" seems like a bad idea.

Post reply on HN