## Fexprs as the basis of Lisp function application; or, $vau: the ultimate abstraction John N. Shutt's PhD Thesis is posted. Abstract Abstraction creates custom programming languages that facilitate programming for specific problem domains. It is traditionally partitioned according to a two-phase model of program evaluation, into syntactic abstraction enacted at translation time, and semantic abstraction enacted at run time. Abstractions pigeon-holed into one phase cannot interact freely with those in the other, since they are required to occur at logically distinct times. Fexprs are a Lisp device that subsumes the capabilities of syntactic abstraction, but is enacted at run-time, thus eliminating the phase barrier between abstractions. Lisps of recent decades have avoided fexprs because of semantic ill-behavedness that accompanied fexprs in the dynamically scoped Lisps of the 1960s and 70s. This dissertation contends that the severe difficulties attendant on fexprs in the past are not essential, and can be overcome by judicious coordination with other elements of language design. In particular, fexprs can form the basis for a simple, well-behaved Scheme-like language, subsuming traditional abstractions without a multi-phase model of evaluation. The thesis is supported by a new Scheme-like language called Kernel, created for this work, in which each Scheme-style procedure consists of a wrapper that induces evaluation of operands, around a fexpr that acts on the resulting arguments. This arrangement enables Kernel to use a simple direct style of selectively evaluating subexpressions, in place of most Lisps' indirect quasiquotation style of selectively suppressing subexpression evaluation. The semantics of Kernel are treated through a new family of formal calculi, introduced here, called vau calculi. Vau calculi use direct subexpression-evaluation style to extend lambda calculus, eliminating a long-standing incompatibility between lambda calculus and fexprs that would otherwise trivialize their equational theories. The impure vau calculi introduce non-functional binding constructs and unconventional forms of substitution. This strategy avoids a difficulty of Felleisen's lambda-v-CS calculus, which modeled impure control and state using a partially non-compatible reduction relation, and therefore only approximated the Church-Rosser and Plotkin's Correspondence Theorems. The strategy here is supported by an abstract class of Regular Substitutive Reduction Systems, generalizing Klop's Regular Combinatory Reduction Systems. Related discussions ## Comment viewing options ###$VAUs vs. fexprs

As has been pointed out before, the objects constructed with $VAU aren't realio, trulio, old Lisp fexprs, because they can't be invoked in the same way as ordinary procedures, as by using APPLY. You can only invoke a$VAU object that is not statically known by constructing a Lisp form and using EVAL to evaluate it.

### re $VAUs vs, fexprs (what are you trying to say?) the objects constructed with$VAU aren't realio, trulio, old Lisp fexprs, because they can't be invoked in the same way as ordinary procedures, as by using APPLY.

If I am taking your meaning correctly, one can pretty much define the "APPLY" that you are thinking of perfectly well. You are making a distinction without much difference. Or maybe you can make it more precise?

Is this approximately right? Does it need a primitive $eval as well? I'm sure the metacircular definitions work well enough for those better versed in implementing scheme, but I'd personally find it very instructive to see what a minimal self-contained C definition of Kernel looks like. ### three "special forms" and some primitive applicatives Alas, no. Besides three additional types (two more single-value types, and the all-important applicative type — an applicative being a one-tuple whose element is either an operative or another applicative), you'd also want bindings for a number of other core primitive applicatives (or their underlying operatives, which I take it is what you mean by$eval). All I meant by "usual suspects" was the other operatives that would be primitive in Scheme but are derived in Kernel; and in order to derive those, you also need a bunch of the core primitive applicatives, which cannot themselves be derived from the three core primitive operatives. For example, the usual (non-robust) library derivation of $sequence uses not only$if, $define!, and$vau, but also wrap, null?, eval, and cons.

You'd surely want some of the following bound in your environment:

• Nine core primitive type predicates. (The C program distinguishes ten, because it knows which operatives are primitive versus compound.)
• Two core primitive comparison predicates. (eq?, equal?.)
• Three core primitive constructors. (cons, make-environment, wrap.)
• Two core primitive mutators. (set-car!, set-cdr!.)
• One core primitive accessor. (unwrap.)
• eval.

From the C program's perspective, all those core primitive applicatives appear to be additional core primitive operatives, so there are far more of them than there are Scheme "fundamental special forms". However, conceptually they seem to me analogous not to Scheme's fundamental special forms, but to Scheme's built-in procedures, which is why I didn't count them.

An additional difficulty in the comparison between languages, though, is that if most of the C program's "primitive operatives" are considered analogous to Scheme built-in procedures, why not all of them? If you treat $if,$define!, and $vau as just three more built-in procedures, then Kernel has no "fundamental special forms". It seems that counting Kernel's fundamental special forms is rather like dividing zero by zero: you may assign a value by convention, but it really depends on how you approach it. ### three "special forms" and some primitive applicatives I see. I agree that the number of primitive operatives is most parallel to the number of built-in procedures in Scheme. But mainly this is because I've come to believe that the salient issue as a model for the definitional complexity of the language is the total complexity of the primitive functions in the underlying implementation (in the reference language) plus the total complexity of the library code. Chapter 6 section 6 of your thesis (plus appendixes), then, elegantly demonstrates an upper bound for the complexity of a Kernel evaluator, it being succinctly defined in the language of a minimalistic, Kernel-compatible, macro-free, vanilla Scheme, plus library code. It's of interest to me, then, if there would be economies to shift some of that logic into the underlying implementation, just so that I could pretend that I understand the "whole thing." But I guess the even more pressing issue if one wants to make things practical'' is how to identify a programming idiom / type-system under which compliant user-level code can be compiled into efficient machine code. This suggests to me that it would be important to develop an idiom for staged computation with explicit evaluation, which seems like something Kernel might be particularly good at. However, I've run far beyond my depth so I'll just say thank you and express an earnest interest to see where you take things. ### Well, a SGLR parser with a Well, a SGLR parser with a scanner would just be a GLR parser :) (and fwiw, I have seen pegs with scanners) ### 'both share a common 'both share a common language characteristic in that they both use a basic design trick of eliminating the scanner from the compiler.' A search through the literature will reveal that parsers with one grammar are easier to extend than a parser/scanner combination. Extensible grammars don't play well with fixed lookahead, and most scannerless parsing requires infinite lookahead (roughly). GLR parsers accomodate this through ambiguous parses and breadth first search PEG parsers accomodate this through backtracking and frequently memoization. Neither of these is cheap. GLR has cubic time, but PEGs can have explosive memory requirements. There are other options like parr's dfa approximations of lookahead, but I like left recursion and i'm like that. (and i'm yet to see his method extended to lr parsing) Really, what we want is determinism, linear time and infinite lookahead without backtracks, or resorting to generalized parsing. You might enjoy looking at shift-resolve parsing, which seems to offer a parsing method that satisfies the requirements http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/FSF-ciaa06.pdf ### but PEGs can have explosive but PEGs can have explosive memory requirements Sure, agreed. But... "hey, you gotta try memoize to avoid that, at a minimum." ;) ### well, memoization may not always be the right choice http://www.mercury.csse.unimelb.edu.au/information/papers/packrat.pdf 'This paper argues that (a) packrat parsers can be trivially implemented using a combination of deï¬nite clause grammar rules and memoing, and that (b) packrat parsing may actually be signiï¬cantly less eï¬ƒcient than plain recursive descent with backtracking, but (c) memoing the recognizers of just one or two nonterminals, selected in accordance with Amdahlâ€™s law, can some- times yield speedups. We present experimental evidence to support these claims.' ### Ha, thank you again This paper is indeed another must-read for PEG users like me. Most interesting to me, specifically, and as put in their conclusion, the results they obtained with using DCG vs. classic Packrat parsers with or without memoing against real-size grammars (alike Java's, etc) confirm what I found myself thinking about while implementing that PEG-oriented fluent interface and observing the parsing times I'd get : "Most predicates donâ€™t contribute significantly to the parserâ€™s runtime, so tabling them just adds overhead in both space and time. For memoing to yield a benefit, the memoed predicate must contribute significantly to the runtime of the parser, and the average running time of one of its invocations multiplied by the hit rate of the table (the expected savings), must exceed the time taken by the tabling operations themselves (the cost). We propose that this be the chief consideration in deciding what predicates to memo in a recursive descent parser. This consideration is so important that respecting it, and tabling only a minimal set of predicates (usually only one, sometimes none) leads to a parser that is significantly faster than the one generated by Rats!, even though the Rats! applies a whole host of other optimizations we donâ€™t.". Now I know I shall definitely remember about this useful study when I'll consider refactoring towards better performance (which I knowingly didn't want to yet, as I was more interested in validating other ideas). So, thanks! ### Thank you And very interesting link, too: thank you! I definitely missed that one until now... Ah, and just can't be surprised to see Farre's name among the authors... ### the thesis is also a fun read on the parsing methodology http://www.lsv.ens-cachan.fr/~schmitz/pub/phd.pdf it is a small part of a larger system of approximating context free grammars for parsing and validation. ### fluent operative handling ... [operatives] can't be invoked in the same way as ordinary procedures, as by using APPLY. You can only invoke [an operative] that is not statically known by constructing a Lisp form and using EVAL to evaluate it." This appears to be a straightforward technical misunderstanding. Statically unknown operatives are easily invoked in Kernel without constructing a form and using eval on it. It's even easy to invoke them using apply. You do need to specify what you want done, because Kernel apply has just one uniform behavior, without a discontinuous behavioral provision for operatives. Kernel apply is used in the tail recursion in both tail-recursive derivations of $cond in the Kernel Report. The Kernel Report rationale for apply is also worth a look. Note too that if, for some reason, you actually want an apply-like device with discontinuous behavior, you can easily build one; abstraction, you know.

As the preface to the dissertation notes, although \$vau is flashier, the treatment of applicatives (at the primitive level, wrap/unwrap) is the more elegant and subtler innovation. It empowers quite fluent use of statically unknown operatives.

### Front page

I think this should be posted to the front page, but would rather see this story promoted than start a separate thread. Pretty please?