[HN Gopher] Intensional Joy (a concatenative account of internal...
___________________________________________________________________
Intensional Joy (a concatenative account of internal structure)
Author : g0xA52A2A
Score : 52 points
Date : 2025-02-12 08:22 UTC (3 days ago)
(HTM) web link (pithlessly.github.io)
(TXT) w3m dump (pithlessly.github.io)
| noelwelsh wrote:
| A nice read. The intensional / extensional duality is echoed in
| the data / codata duality that is core to how I currently view
| program design.
| JadeNB wrote:
| 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), from which Lisp has
| seemed to move away (although there's
| https://web.cs.wpi.edu/~jshutt/kernel.html). I wonder if
| they're more suited to a concatenative environment?)
| skulk wrote:
| 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 wrote:
| 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.
| MrMcCall wrote:
| Seriously, thank you very much for that excellent
| breakdown.
|
| I never really got into Lisp, as I preferred imperative
| programming with C et al, but it looks like my preference
| is for my programming language requiring up-front a
| complete specification of the semantics of the program,
| i.e. no runtime dynamic parsing of strings into code or
| the like.
|
| From your description, it looks like the Lisp guys
| codified (NPI) how to mix static and dynamic abilities
| into the same language, thus uncovering the analysis
| problems for how the dynamic parts can be processed with
| respect to their interface with its static core.
|
| Thanks again. Learning something like this is a wonderful
| way to start my day in this troubled world. Peace be with
| you, and best of luck in your endeavors!
| tonyg wrote:
| > 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.
|
| I don't think this is the case. Consider Kernel's
| ($lambda (f) (f (+ 3 4)))
|
| Is `f` a fexpr or a closure? We cannot know until
| runtime.
| Xmd5a wrote:
| Can you elaborate ? How do you figure it out at runtime ?
| kazinator wrote:
| At run time, you can inspect the current binding of _f_
| to see whether it is a macro, function or whatever. In an
| interpreter with fexprs, it would be late like this. At
| the time (f ...) is being called, if it was redefined to
| a fexpr, we go with that. If it is still a function, we
| call that.
| kazinator wrote:
| We look it up at compile time. If it has a function
| binding defined at compile time, we go with that
| hypothesis. If it is a macro, we expand it. If it is a
| fexpr, we go with that hypothesis (and then do what?
| check if the application provides compilation semantics
| for the fexpr or abort.)
|
| If it's unbound, we assume that it will be function and
| compile accordingly. We make a note that we did this.
|
| If, by the end of the compilation unit, a definition of f
| has not been seen, we issue a warning. If a conflicting
| definition is seen, like a macro or fexpr, we also issue
| a warning.
|
| (We provide a macro with-compilation-unit that the
| programmer or their build system can use to clump
| together multiple files into one compilation unit for the
| purpose of generating these kinds of diagnostics related
| to definitions.)
|
| We carefully document all of this in our reference
| manual, in a section about how compilation semantics can
| differ from interpretation semantics.
|
| This isn't rocket science. Been there, done that.
| noelwelsh wrote:
| 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/
| kayo_20211030 wrote:
| 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.
___________________________________________________________________
(page generated 2025-02-15 23:02 UTC)