6 ms·

$vau: the ultimate abstraction (2010) [pdf]

106 points by drnewman 8y ago

pronoiac 8y ago
Alt title: "Fexprs as the basis of Lisp function application"
geocar 8y ago
There's a partial list of Kernel implementations (the lisp described in the paper) that I'm aware of: https://axisofeval.blogspot.com/2011/09/kernel-underground.html https://axisofeval.blogspot.com/2011/09/kernel-underground.h...
shawn 8y ago
If anyone wants to implement this, I believe you can do so in Lumen Lisp: https://docs.ycombinator.lol/ https://docs.ycombinator.lol/ In particular, macros like https://imgur.com/C4NL0OB https://imgur.com/C4NL0OB are pretty effortless to write.
jhallenworld 8y ago
I've implemented something like this in a non-LISP syntax language. See: https://github.com/jhallen/joes-sandbox/tree/master/lang/ivy https://github.com/jhallen/joes-sandbox/tree/master/lang/ivy The idea is that in a function call, the arguments are normally evaluated before the call as usual. But if a formal argument in the function's declaration is prefixed with ampersand then during a function call, that argument is not evaluated, but is instead packaged up as a zero-argument lambda function. The argument can be called later using the normal function call syntax, but also there is semantic sugar: the * operator calls a zero-argument function. Further, when a variable is evaluated, you get both its value and a reference to it. This allows variables to be evaluated before being assigned to in assignments. This sounds weird, but it works with the above. You can make a "set" function which does the same thing as assignment: # Define set function fn set(&left, right) { *left = right } # Set x to 10 set x 10 Here is how you could define switch using primitives (if the last argument is prefixed with ampersand, then any extra arguments are treated the same, but can only be accessed via argv): fn switch(&val) { var rtn, x, v = *val x = 1 while x < len(argv) - 1 { if *argv(x) == v { return *argv(x + 1) } x += 2 } if x < len(argv) { return *argv(x) } return void } Example use (8 arguments passed to switch- each set of braces is an argument): switch 2 1 { print "one" } 2 { print "two" } 3 { print "three" } { print "default" } "two" is printed in this case. Right now the delayed arguments are evaluated in the closure of the function call (so they are lexically scoped). The wrap/unwrap concept from this paper gives me ideas on how to make this more versatile...
- amelius 8y ago
  Perhaps a stupid question, but why not introduce an explicit "evaluate" operator, and keep the rest of the language lazy? That would prevent treating function calls as special.
  - jhallenworld 8y ago
    Well the language is not LISP, meaning that the source is immediately compiled (to byte code in this case), and provides no access to an AST that can be manipulated. It's interesting to see how far you can get without eval.
  - kazinator 8y ago
    The evaluate operator would require an environment parameter in order to avoid capture issues in the same way as passing down the lambda. If you're passing around a piece of code with an environment, you effectively have a lambda already: one that is condemned to slow interpretation. Without the environment passing for proper referencing semantics, the implementation wouldn't be a correct call-by-name reference; it would not pass Knuth's Man-or-boy test. https://en.wikipedia.org/wiki/Man_or_boy_test https://en.wikipedia.org/wiki/Man_or_boy_test
- Koshkin 8y ago
  BTW the syntax looks identical to how an argument is passed by reference in C.
  - jhallenworld 8y ago
    Yes, that was intentional. In my language you can pass code by reference, not just data.
- kazinator 8y ago
  This is just Algol-style "call by name". https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_na... Call-by-name in Lisp macros, to implement Knuth's "Man or boy test" program: https://rosettacode.org/wiki/Man_or_boy_test#TXR https://rosettacode.org/wiki/Man_or_boy_test#TXR As you can see, the make-cbn-val constructor packages up the argument as an object ("thunk") that contains zero-argument lambda for getting the value, and a one-argument setter. Inside a call-by-name function, references to all the call-by-name arguments are converted according to the pattern X -> (cbn-val X), using a lexical macro. (cbn-val ...) syntax is treated as a place thanks to the (defplace (cbn-val thunk) ...) definition. In the following, the (inc a) applied on the call-by-name argument a turns into (set-cbn-val #:g0098 (succ (cbn-val #:g0098)))): get the value, find successor, store the value. 4> (expand '(defun-cbn foo (a) (inc a))) (progn (defun #:g0091 ()) (defmacro foo args (list* 'cbn '#:g0091 args)) (let ((#:g0095 (sys:get-fun-getter-setter '#:g0091))) (call (cdr #:g0095) (lambda (#:g0092) (block foo (let ((foo)) (let ((#:g0098 #:g0092)) (set-cbn-val #:g0098 (succ (cbn-val #:g0098)))) foo)))))) An empty function is defined, named by a gensym. Two steps later in the progn, this function binding is overwritten with the real function. A macro called foo is generated which provides the syntactic sugar for calling foo, automatically converting the arguments to thunks. The syntax (foo a b c) turns into (cbn #:g0091 a b c), which is another macro operator for doing call by name. The actual function starts at (lambda (#g:0092) ...). The (let ((foo)) ...) part simulates another Algol feature: returning a value is done by assigning to the function name. Our function returns nil because it doesn't assign anything to foo. The call (foo x) expands like this: 5> (macroexpand '(foo x)) (call (fun #:g0083) (make-cbn-val x)) Or fully: 6> (expand '(foo x)) (call (fun #:g0083) (make-struct 'cbn-thunk (list 'get (lambda () x) 'set (lambda (#:g0099) (sys:setq x #:g0099))))) The make-struct call is an expansion of the new macro operator; that comes from the object system: 11> (macroexpand-1 '(make-cbn-val x)) (new cbn-thunk get (lambda () x) set (lambda (#:g0104) (set x #:g0104))) In action: watch x get incremented by foo: 12> (defvar x 10) x 13> (foo x) nil 14> x 11 Of course, this is objectionably hacky because foo isn't a function; we can't pass it around or anything. The goal was only to solve the Rosetta Code "Man or boy" task, with a focus on actually emulating the language features to some degree of fidelity, so that the program could truly be a transliteration of Knuth's code into Lisp expressions, almost node for node.
ASipos 8y ago
I would like to see a mature language using fexprs. They are what I first thought about when I heard the word homoiconicity. Macros seem inelegant in comparison (since there is a separate layer of code that operates on code, and also you don't get self-modifying code, just compile-time transformations).
- 9214 8y ago
  Rebol family of languages (including Red) uses near equivalents of fexprs. Here's a self-modifying function ;^) >> foo: has [x][append body-of context? 'x [+ 1] 1] == func [/local x][append body-of context? 'x [+ 1] 1] >> loop 3 [probe foo] 1 2 3 == 3 >> ?? foo foo: func [/local x][append body-of context? 'x [+ 1] 1 + 1 + 1 + 1]
openfuture 8y ago
I read maybe a dozen pages, might read more but I'm curious if someone can tell me the type of $vau?
- shawn 8y ago
  According to Racket, the type is 'ultimate-abstraction': $ racket -I swindle Welcome to Racket v6.12. > (class-of 42) #<primitive-class:exact-integer> > (class-of $vau) #<primitive-class:ultimate-abstraction> I guess the paper wasn't lying.
  - chaoticmass 8y ago
    dchaney@sagan:/~$ racket -I swindle Welcome to Racket v6.7. > (class-of 42) #<primitive-class:exact-integer> > (class-of $vau) ; $vau: undefined; ; cannot reference undefined identifier ; [,bt for context] > What did I do wrong? Or did the joke go over my head?
    - shawn 8y ago
      $vau was introduced in Racket v6.11. You'll need to upgrade.
      - leoh 8y ago
        What? No it wasn't.
        shawn 8y ago
        Racket 6.11 release notes: https://racket.ycombinator.lol/v6.11.html https://racket.ycombinator.lol/v6.11.html Racket v6.11 * `$vau` is now a built-in primitive. See "Fexprs as the basis of Lisp function application" * Typed Racket supports refinement types and dependent function types. Previously an experimental feature, refinement types allow types to describe more interesting properties of values, especially integers. For example, this type shows that the `max` function always produces a number at least as big as its inputs: `(-> ([x : Integer] [y : Integer]) (Refine [z : Integer] (and (>= z x) (>= z y))))` * DrRacket's Program Contour is significantly more efficient; using it no longer hurts DrRacket's interactivity. * The `web-server/formlets` library produces formlets that are serializable, facilitating dynamic uses of formlets in stateless #lang web-server servlets. The new `web-server/formlets/stateless` and `web-server/formlets/unsafe` libraries provide additional support with the same API. * The `db` library supports the Cassandra database.
leoh 8y ago
What are interesting uses of this?
gjm11 8y ago
There's a bit of subtext in the title that may be worth drawing attention to. (I dunno, maybe it's all obvious to everyone interested enough in this stuff to be reading the dissertation. But perhaps not, so here goes.) In the 1970s, after their paper introducing Scheme, Sussman and Steele published a series of papers showing how to implement a bunch of things "on top of" a functional-programming substrate, many of them having titles or subtitles of the form "Lambda: the ultimate X". (The first one was "Lambda: the ultimate imperative", the second "Lambda: the ultimate declarative", others "Lambda: the ultimate GOTO" and "Lambda: the ultimate opcode".) The idea of these papers wasn't merely "look, you can implement X in Lisp", but something more like "You might be inclined to think of X as simple and primitive and cheap, and Lisp as sophisticated and complicated and expensive -- but that's mostly prejudice, an accident of the particular hardware we happen to have built first, and using something like Lisp as your lower level and implementing these things on top is better than doing it the other way around". So writing something -- especially something about a Lisp implementation -- with a subtitle of the form "X: the ultimate Y" where X is not lambda -- is pointedly one-upping that. Especially as the thing that $vau is allegedly providing the new best way to do is ... function abstraction, which is exactly what lambda is for.

106 points by drnewman 8y ago

Alt title: "Fexprs as the basis of Lisp function application"

There's a partial list of Kernel implementations (the lisp described in the paper) that I'm aware of: https://axisofeval.blogspot.com/2011/09/kernel-underground.html https://axisofeval.blogspot.com/2011/09/kernel-underground.h...

shawn 8y ago

If anyone wants to implement this, I believe you can do so in Lumen Lisp: https://docs.ycombinator.lol/ https://docs.ycombinator.lol/ In particular, macros like https://imgur.com/C4NL0OB https://imgur.com/C4NL0OB are pretty effortless to write.

jhallenworld 8y ago

I've implemented something like this in a non-LISP syntax language. See: https://github.com/jhallen/joes-sandbox/tree/master/lang/ivy https://github.com/jhallen/joes-sandbox/tree/master/lang/ivy The idea is that in a function call, the arguments are normally evaluated before the call as usual. But if a formal argument in the function's declaration is prefixed with ampersand then during a function call, that argument is not evaluated, but is instead packaged up as a zero-argument lambda function. The argument can be called later using the normal function call syntax, but also there is semantic sugar: the * operator calls a zero-argument function. Further, when a variable is evaluated, you get both its value and a reference to it. This allows variables to be evaluated before being assigned to in assignments. This sounds weird, but it works with the above. You can make a "set" function which does the same thing as assignment: # Define set function fn set(&left, right) { *left = right } # Set x to 10 set x 10 Here is how you could define switch using primitives (if the last argument is prefixed with ampersand, then any extra arguments are treated the same, but can only be accessed via argv): fn switch(&val) { var rtn, x, v = *val x = 1 while x < len(argv) - 1 { if *argv(x) == v { return *argv(x + 1) } x += 2 } if x < len(argv) { return *argv(x) } return void } Example use (8 arguments passed to switch- each set of braces is an argument): switch 2 1 { print "one" } 2 { print "two" } 3 { print "three" } { print "default" } "two" is printed in this case. Right now the delayed arguments are evaluated in the closure of the function call (so they are lexically scoped). The wrap/unwrap concept from this paper gives me ideas on how to make this more versatile...

amelius 8y ago
Perhaps a stupid question, but why not introduce an explicit "evaluate" operator, and keep the rest of the language lazy? That would prevent treating function calls as special.
- jhallenworld 8y ago
  Well the language is not LISP, meaning that the source is immediately compiled (to byte code in this case), and provides no access to an AST that can be manipulated. It's interesting to see how far you can get without eval.
- kazinator 8y ago
  The evaluate operator would require an environment parameter in order to avoid capture issues in the same way as passing down the lambda. If you're passing around a piece of code with an environment, you effectively have a lambda already: one that is condemned to slow interpretation. Without the environment passing for proper referencing semantics, the implementation wouldn't be a correct call-by-name reference; it would not pass Knuth's Man-or-boy test. https://en.wikipedia.org/wiki/Man_or_boy_test https://en.wikipedia.org/wiki/Man_or_boy_test
Koshkin 8y ago
BTW the syntax looks identical to how an argument is passed by reference in C.
- jhallenworld 8y ago
  Yes, that was intentional. In my language you can pass code by reference, not just data.
kazinator 8y ago
This is just Algol-style "call by name". https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_na... Call-by-name in Lisp macros, to implement Knuth's "Man or boy test" program: https://rosettacode.org/wiki/Man_or_boy_test#TXR https://rosettacode.org/wiki/Man_or_boy_test#TXR As you can see, the make-cbn-val constructor packages up the argument as an object ("thunk") that contains zero-argument lambda for getting the value, and a one-argument setter. Inside a call-by-name function, references to all the call-by-name arguments are converted according to the pattern X -> (cbn-val X), using a lexical macro. (cbn-val ...) syntax is treated as a place thanks to the (defplace (cbn-val thunk) ...) definition. In the following, the (inc a) applied on the call-by-name argument a turns into (set-cbn-val #:g0098 (succ (cbn-val #:g0098)))): get the value, find successor, store the value. 4> (expand '(defun-cbn foo (a) (inc a))) (progn (defun #:g0091 ()) (defmacro foo args (list* 'cbn '#:g0091 args)) (let ((#:g0095 (sys:get-fun-getter-setter '#:g0091))) (call (cdr #:g0095) (lambda (#:g0092) (block foo (let ((foo)) (let ((#:g0098 #:g0092)) (set-cbn-val #:g0098 (succ (cbn-val #:g0098)))) foo)))))) An empty function is defined, named by a gensym. Two steps later in the progn, this function binding is overwritten with the real function. A macro called foo is generated which provides the syntactic sugar for calling foo, automatically converting the arguments to thunks. The syntax (foo a b c) turns into (cbn #:g0091 a b c), which is another macro operator for doing call by name. The actual function starts at (lambda (#g:0092) ...). The (let ((foo)) ...) part simulates another Algol feature: returning a value is done by assigning to the function name. Our function returns nil because it doesn't assign anything to foo. The call (foo x) expands like this: 5> (macroexpand '(foo x)) (call (fun #:g0083) (make-cbn-val x)) Or fully: 6> (expand '(foo x)) (call (fun #:g0083) (make-struct 'cbn-thunk (list 'get (lambda () x) 'set (lambda (#:g0099) (sys:setq x #:g0099))))) The make-struct call is an expansion of the new macro operator; that comes from the object system: 11> (macroexpand-1 '(make-cbn-val x)) (new cbn-thunk get (lambda () x) set (lambda (#:g0104) (set x #:g0104))) In action: watch x get incremented by foo: 12> (defvar x 10) x 13> (foo x) nil 14> x 11 Of course, this is objectionably hacky because foo isn't a function; we can't pass it around or anything. The goal was only to solve the Rosetta Code "Man or boy" task, with a focus on actually emulating the language features to some degree of fidelity, so that the program could truly be a transliteration of Knuth's code into Lisp expressions, almost node for node.

ASipos 8y ago

I would like to see a mature language using fexprs. They are what I first thought about when I heard the word homoiconicity. Macros seem inelegant in comparison (since there is a separate layer of code that operates on code, and also you don't get self-modifying code, just compile-time transformations).

9214 8y ago
Rebol family of languages (including Red) uses near equivalents of fexprs. Here's a self-modifying function ;^) >> foo: has [x][append body-of context? 'x [+ 1] 1] == func [/local x][append body-of context? 'x [+ 1] 1] >> loop 3 [probe foo] 1 2 3 == 3 >> ?? foo foo: func [/local x][append body-of context? 'x [+ 1] 1 + 1 + 1 + 1]

openfuture 8y ago

I read maybe a dozen pages, might read more but I'm curious if someone can tell me the type of $vau?

shawn 8y ago
According to Racket, the type is 'ultimate-abstraction': $ racket -I swindle Welcome to Racket v6.12. > (class-of 42) #<primitive-class:exact-integer> > (class-of $vau) #<primitive-class:ultimate-abstraction> I guess the paper wasn't lying.
- chaoticmass 8y ago
  dchaney@sagan:/~$ racket -I swindle Welcome to Racket v6.7. > (class-of 42) #<primitive-class:exact-integer> > (class-of $vau) ; $vau: undefined; ; cannot reference undefined identifier ; [,bt for context] > What did I do wrong? Or did the joke go over my head?
  - shawn 8y ago
    $vau was introduced in Racket v6.11. You'll need to upgrade.
    - leoh 8y ago
      What? No it wasn't.
      - shawn 8y ago
        Racket 6.11 release notes: https://racket.ycombinator.lol/v6.11.html https://racket.ycombinator.lol/v6.11.html Racket v6.11 * `$vau` is now a built-in primitive. See "Fexprs as the basis of Lisp function application" * Typed Racket supports refinement types and dependent function types. Previously an experimental feature, refinement types allow types to describe more interesting properties of values, especially integers. For example, this type shows that the `max` function always produces a number at least as big as its inputs: `(-> ([x : Integer] [y : Integer]) (Refine [z : Integer] (and (>= z x) (>= z y))))` * DrRacket's Program Contour is significantly more efficient; using it no longer hurts DrRacket's interactivity. * The `web-server/formlets` library produces formlets that are serializable, facilitating dynamic uses of formlets in stateless #lang web-server servlets. The new `web-server/formlets/stateless` and `web-server/formlets/unsafe` libraries provide additional support with the same API. * The `db` library supports the Cassandra database.

leoh 8y ago

What are interesting uses of this?

gjm11 8y ago

There's a bit of subtext in the title that may be worth drawing attention to. (I dunno, maybe it's all obvious to everyone interested enough in this stuff to be reading the dissertation. But perhaps not, so here goes.) In the 1970s, after their paper introducing Scheme, Sussman and Steele published a series of papers showing how to implement a bunch of things "on top of" a functional-programming substrate, many of them having titles or subtitles of the form "Lambda: the ultimate X". (The first one was "Lambda: the ultimate imperative", the second "Lambda: the ultimate declarative", others "Lambda: the ultimate GOTO" and "Lambda: the ultimate opcode".) The idea of these papers wasn't merely "look, you can implement X in Lisp", but something more like "You might be inclined to think of X as simple and primitive and cheap, and Lisp as sophisticated and complicated and expensive -- but that's mostly prejudice, an accident of the particular hardware we happen to have built first, and using something like Lisp as your lower level and implementing these things on top is better than doing it the other way around". So writing something -- especially something about a Lisp implementation -- with a subtitle of the form "X: the ultimate Y" where X is not lambda -- is pointedly one-upping that. Especially as the thing that $vau is allegedly providing the new best way to do is ... function abstraction, which is exactly what lambda is for.