- Intensional Programming Languages: Had a moment recently. Johannes Bader's website on tree calculus popularized work on intensional rewriting systems spearheaded by Dr. Barry Jay. They have developed variants like SF calculus, tree calculus, triage calculus, etc.
Joy: A concatenative programming language trying to capture its essence. It has a stack-based language or a system of rewriting rules. Syntax consists of zero or more commands (quotations or operators like
dup,swap,pop,cat,quote,eval).- Stack-based Semantics: Each command has a specific behavior on the stack. For example,
dupduplicates the top element,swapswaps the top two,popremoves the top,catconcatenates,quotewraps in quotation, andevalexecutes the top program. - Rewriting Semantics: The execution of a Joy program can be described by a sequence of rewrites. For example,
[a] dup→\[a\] \[a\],[a] \[b\] swap→\[b\] \[a\], etc. Applying the leftmost rewrite gives a notion of “applicative order reduction” simulating stack-based semantics.
- Stack-based Semantics: Each command has a specific behavior on the stack. For example,
Making Joy Intensional: Joy is extensional and has no way to “take apart” a quotation. An intensional operator
mapwas described by @olus2000 which maps over every element of a program applying an operator or a quotation. Another operatorquotapops a single program and surrounds every command in it with a quotation.- Equivalence of
mapandquota: It was shown that these two operators can be expressed in terms of each other. To implementmap, a way to distinguishdupfrom a quotation was found usingquotato introspect.
- Equivalence of
- Conclusions: Presented two operators
mapandquotafor intensional programming in a concatenative language.quotais simple but complex to use, whilemapis easy to use but more complex. Each operator's behavior can be captured by the other, but in an intensional setting, equivalence is more complicated. These operators can be brought into richer languages with similar syntactic structures as long as they don't have variable binding. Dr. Jay's research also leans on conceptual simplification based on combinatory calculi. - Full Versions of Reductions: Encouraged readers to try implementing
mapin terms ofquotaand vice versa in real Joy code.
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用。你还可以使用@来通知其他用户。