3 ms·

Intensional Joy (a concatenative account of internal structure)

60 points by g0xA52A2A 2y ago

mrbluecoat 2y ago
[flagged]
- deleted 2y ago
  [deleted]
noelwelsh 2y ago
A nice read. The intensional / extensional duality is echoed in the data / codata duality that is core to how I currently view program design.
- deleted 2y ago
  [deleted]
- JadeNB 2y ago
  Could you say more about your point of view? (Also, this looks an awful lot like the old notion of fexprs (https://en.wikipedia.org/wiki/Fexpr https://en.wikipedia.org/wiki/Fexpr), from which Lisp has seemed to move away (although there's https://web.cs.wpi.edu/~jshutt/kernel.html https://web.cs.wpi.edu/~jshutt/kernel.html). I wonder if they're more suited to a concatenative environment?)
  - skulk 2y ago
    According to the wiki article on fexprs, they lost favor because they make it hard to statically determine whether a function call evaluates its parameters, which makes it hard for a compiler to optimize. > At the 1980 [Conference], Kent Pitman presented a paper "Special Forms in Lisp" in which he discussed the advantages and disadvantages of macros and fexprs, and ultimately condemned fexprs. His central objection was that, in a Lisp dialect that allows fexprs, static analysis cannot determine generally whether an operator represents an ordinary function or a fexpr — therefore, static analysis cannot determine whether or not the operands will be evaluated. In particular, the compiler cannot tell whether a subexpression can be safely optimized, since the subexpression might be treated as unevaluated data at run-time. I imagine this issue would persist in a compiled concatenative language. However, I don't think Joy is trying to be particularly fast or efficient.
    - kazinator 2y ago
      Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. The main problem is that a language with fexprs is inherently not compilable. A second problem is that for some fexprs, compilation semantics cannot be found. A fexpr definition adds a new special operator to an interpreter. The existence of fexprs means that the repertoire of special operators is open-ended. But a compiler depends on there being a fixed set of special operators known in advance. For each kind of form the compiler has a case, which implements the translation scheme. Someone wrote that translation scheme by understanding what that special form does. When a compiler hits a form that is a fexpr invocation, there is no translation scheme for that. It is defined by piece of code in the program itself, which gives the interpretive semantics for the form. The compiler would have to read that code, understand it, and come up with a translation scheme for it from interpreted to compiled semantics. In other words do the job of a compiler writer. It requires advanced artificial intelligence. Some fexprs are not compilable. A compiler writing expert can look at the application code which defines the fexpr, and come to the conclusion that the code doesn't make sense outside of the interpreted world. Fexprs that can be compiled correspond to those forms which can be written as macros. A strategy is possible whereby for each fexpr, the application must supply a macro definition, if that application is to be compilable. The interpreter will use the fexpr, and the compiler will instead expand the macro and use that. But what is the point. You have to maintain two implementations of the same thing. Interpreters can use macros just fine. Fexprs do have an advantage over macros: lack of hygiene issues. The local variables in a fexpr are clearly in a different lexical environment from the variables of the form that it operates on/with. The fexpr function has the lexical environment of the fexpr form as an argument. When the interpreter invokes a fexpr, it hands the fexpr the current lexical environment, and the fexpr form. Whenever the fexpr code needs to evaluate some part of that form, like a variable reference, it explicitly calls eval, and passes eval that lexical environment. In no way does that get mixed up with the interpretation of the fexpr itself. There can be no capture issue. An fexpr would never need gensyms, or contain a mistake you cannot use them. Macros also don't have hygiene issues between their own variables and those in the generated code. But fexprs can you use their own variables as runtime temporaries to hold intermediate values needed by the calculation that they are interpreting. Macros cannot use their own variables this way because they are not executing at run time. They have to introduce variables into the generated code. These variables are then in the same lexical environment as that code and must be given unique symbols in order to hide these introduced variables, protecting them from conflicts. Some newcomers into the Lisp world still become fascinated by fexprs for, I suspect, mainly this reason. The lack of hygiene concerns somehow gives fexprs a kind of dignified air so to speak, like they are clean and fundamental. This view is further bolstered by that any macro could be a fexpr, but the converse isn't true. There's a kind of magic in allowing interpreter code the dynamically extended interpreter in arbitrary ways, seemingly bounded only by the limits of computation.
  - noelwelsh 2y ago
    In programming language theory there are two ways to represent programs: * data, which has intensional equality (you understand it by what it is) * codata, which has extensional equality (you understand it by what it does) For data think data in a normal programming language. (Algebraic data types, if that means anything.) For codata think functions (or objects). These are duals, meaning you can map on to the other. If you have a design using data you can transform it to codata and vice versa. This opens up a lot design opportunities by exploiting this duality. There is more in the book I'm writing if this is your kind of thing: https://scalawithcats.com/ https://scalawithcats.com/
    - turtleyacht 2y ago
      The newsletter link at that page may not be working. Maybe the book is finished, though? The error message is No newsletter with the name of scalawithcats
      - noelwelsh 2y ago
        Thanks for letting me know! I've fixed it now. The (second edition of the) book is very much in progress.
kayo_20211030 2y ago
I'm always intrigued by this. What's the upside of stack based languages for a developer? They all seem opaque (even confusing), have little tooling, and seem designed for an era of limited resources. There's probably value in the investigation in some academic sense; well, who knows where that might lead? But, what's the value to a working dev trying to deliver a solution? Only first order effects are valid in this context. Saying it'll make you a better programmer isn't. That's, at best, a second order effect. Lisp will do that also, I'm told. That, I believe. Stack based languages; well, not so much.
- deleted 2y ago
  [deleted]

60 points by g0xA52A2A 2y ago

mrbluecoat 2y ago

[flagged]

deleted 2y ago
[deleted]

noelwelsh 2y ago

A nice read. The intensional / extensional duality is echoed in the data / codata duality that is core to how I currently view program design.

deleted 2y ago
[deleted]
JadeNB 2y ago
Could you say more about your point of view? (Also, this looks an awful lot like the old notion of fexprs (https://en.wikipedia.org/wiki/Fexpr https://en.wikipedia.org/wiki/Fexpr), from which Lisp has seemed to move away (although there's https://web.cs.wpi.edu/~jshutt/kernel.html https://web.cs.wpi.edu/~jshutt/kernel.html). I wonder if they're more suited to a concatenative environment?)
- skulk 2y ago
  According to the wiki article on fexprs, they lost favor because they make it hard to statically determine whether a function call evaluates its parameters, which makes it hard for a compiler to optimize. > At the 1980 [Conference], Kent Pitman presented a paper "Special Forms in Lisp" in which he discussed the advantages and disadvantages of macros and fexprs, and ultimately condemned fexprs. His central objection was that, in a Lisp dialect that allows fexprs, static analysis cannot determine generally whether an operator represents an ordinary function or a fexpr — therefore, static analysis cannot determine whether or not the operands will be evaluated. In particular, the compiler cannot tell whether a subexpression can be safely optimized, since the subexpression might be treated as unevaluated data at run-time. I imagine this issue would persist in a compiled concatenative language. However, I don't think Joy is trying to be particularly fast or efficient.
  - kazinator 2y ago
    Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. The main problem is that a language with fexprs is inherently not compilable. A second problem is that for some fexprs, compilation semantics cannot be found. A fexpr definition adds a new special operator to an interpreter. The existence of fexprs means that the repertoire of special operators is open-ended. But a compiler depends on there being a fixed set of special operators known in advance. For each kind of form the compiler has a case, which implements the translation scheme. Someone wrote that translation scheme by understanding what that special form does. When a compiler hits a form that is a fexpr invocation, there is no translation scheme for that. It is defined by piece of code in the program itself, which gives the interpretive semantics for the form. The compiler would have to read that code, understand it, and come up with a translation scheme for it from interpreted to compiled semantics. In other words do the job of a compiler writer. It requires advanced artificial intelligence. Some fexprs are not compilable. A compiler writing expert can look at the application code which defines the fexpr, and come to the conclusion that the code doesn't make sense outside of the interpreted world. Fexprs that can be compiled correspond to those forms which can be written as macros. A strategy is possible whereby for each fexpr, the application must supply a macro definition, if that application is to be compilable. The interpreter will use the fexpr, and the compiler will instead expand the macro and use that. But what is the point. You have to maintain two implementations of the same thing. Interpreters can use macros just fine. Fexprs do have an advantage over macros: lack of hygiene issues. The local variables in a fexpr are clearly in a different lexical environment from the variables of the form that it operates on/with. The fexpr function has the lexical environment of the fexpr form as an argument. When the interpreter invokes a fexpr, it hands the fexpr the current lexical environment, and the fexpr form. Whenever the fexpr code needs to evaluate some part of that form, like a variable reference, it explicitly calls eval, and passes eval that lexical environment. In no way does that get mixed up with the interpretation of the fexpr itself. There can be no capture issue. An fexpr would never need gensyms, or contain a mistake you cannot use them. Macros also don't have hygiene issues between their own variables and those in the generated code. But fexprs can you use their own variables as runtime temporaries to hold intermediate values needed by the calculation that they are interpreting. Macros cannot use their own variables this way because they are not executing at run time. They have to introduce variables into the generated code. These variables are then in the same lexical environment as that code and must be given unique symbols in order to hide these introduced variables, protecting them from conflicts. Some newcomers into the Lisp world still become fascinated by fexprs for, I suspect, mainly this reason. The lack of hygiene concerns somehow gives fexprs a kind of dignified air so to speak, like they are clean and fundamental. This view is further bolstered by that any macro could be a fexpr, but the converse isn't true. There's a kind of magic in allowing interpreter code the dynamically extended interpreter in arbitrary ways, seemingly bounded only by the limits of computation.
- noelwelsh 2y ago
  In programming language theory there are two ways to represent programs: * data, which has intensional equality (you understand it by what it is) * codata, which has extensional equality (you understand it by what it does) For data think data in a normal programming language. (Algebraic data types, if that means anything.) For codata think functions (or objects). These are duals, meaning you can map on to the other. If you have a design using data you can transform it to codata and vice versa. This opens up a lot design opportunities by exploiting this duality. There is more in the book I'm writing if this is your kind of thing: https://scalawithcats.com/ https://scalawithcats.com/
  - turtleyacht 2y ago
    The newsletter link at that page may not be working. Maybe the book is finished, though? The error message is No newsletter with the name of scalawithcats
    - noelwelsh 2y ago
      Thanks for letting me know! I've fixed it now. The (second edition of the) book is very much in progress.

kayo_20211030 2y ago

I'm always intrigued by this. What's the upside of stack based languages for a developer? They all seem opaque (even confusing), have little tooling, and seem designed for an era of limited resources. There's probably value in the investigation in some academic sense; well, who knows where that might lead? But, what's the value to a working dev trying to deliver a solution? Only first order effects are valid in this context. Saying it'll make you a better programmer isn't. That's, at best, a second order effect. Lisp will do that also, I'm told. That, I believe. Stack based languages; well, not so much.

deleted 2y ago
[deleted]