Show us what factorial would look like in Tenerezza! Or some other simple thing that makes sense. Doesn't have to be a working example, and showing off cool new features is preferred but optional.
I'll give an example in terms of the macro layer and the Era reader so that it's a self-contained language, not cheating with raw JavaScript code or whatnot.
However, I haven't defined any macros yet, and the macro layer would actually be entirely useless without at least one macro to use for bootstrapping. Let's say I've defined a set of macros that corresponds to the same Tenerezza syntax that the macros compile to. (This is almost silly. It's roughly analogous to writing Arc code by defining a bunch of macros that recreate Scheme.)
I'll show you what it might look like, at this point in the design, to define a function (factorial) in terms of existing functions (times factor), (plus term), (negate), (one), and (idfn).
Note that every Tenerezza function takes a single argument, but functions of tag (times factor) must be constructed with an environment that has a "factor" entry, so (times factor) is effectively a two-argument function.
"How about a function to simply add two arguments?"
Tenerezza doesn't have a built-in notion of numbers. Any example of realistically usable performance would have to resort to some native code.
Native code is fine by me, for now. I was actually originally developing Staccato (which has led into Tenerezza) as a language for internal use in my own language implementations, and I don't expect those to be entirely free of native code.
Eventually, Tenerezza (or similar) may be able to handle arithmetic all by itself with sufficiently powerful JIT optimizations or static type specialization. At the least, a JIT optimization could recognize a particular bigint implementation and switch to a native equivalent. :-p
---
"You said everything is a channel? I'm trying to imagine how you'd do addition using channels and why that might be useful."
Yeah, addition doesn't seem very useful. :) It still makes sense as an example, though.
Let's say I'm an addition function invocation. In my whole life, I know nothing except three video chats. Two of them show nothing but a single number each, and the third shows nothing at all. I add the two numbers and show the result to the third chat. Maybe whoever's behind that chat will use my result for something, but I will never know; the lifespan of a function invocation is instantaneous.
Ok, that makes sense. Mu has those channels as well. Here's a scenario (test) from mu[1]:
:(scenario "reply")
recipe main [
3:integer, 4:integer <- f 2:literal
]
recipe f [
12:integer <- next-ingredient
13:integer <- add 1:literal, 12:integer
reply 12:integer, 13:integer
]
+run: instruction main/0
+run: result 0 is 1[2...]
+mem: storing 2 in location 3
+run: result 1 is 1[3...]
+mem: storing 3 in location 4
I'm also trying to come up with a less mathematically-oriented vocabulary, so recipe = function and ingredient = argument. In this test the function f reads an arg from its input channel (analogous to your video chat) and writes its results to its output channel, which is connected by the caller to variables 3 and 4. (Variable names are introduced in a later 'layer', so this test doesn't use them. And the lines beginning with '+' are assertions about what should have happened in the course of the scenario.)
I'm curious, is the 'video chat' simply a mataphor? Will an oracle optimizer be permitted to look inside multiple invocations at once?
In your Mu example, what happens if f replies with a different number of integers than main expects?
I don't know if you got this already, but Tenerezza's channels are input and output channels at the same time, and the fact that they carry orderless sets of information means they can cleanly receive output more than once (which get unioned into a single set).
Here's a quirky increment operator Tenerezza could support: It sees any number of channels, and for each one, it shows that channel's information to all the others but with the numbers incremented by one. In the trivial case where one channel blindly shows a number and another channel listens without response, it's effectively a traditional increment function.
I should probably show you an example of reversing a list, so that at least you can see how Tenerezza can compute on structured information (which could be used for implementing arithmetic)... but I don't have time right at the moment, sorry. XD;
---
"I'm curious, is the 'video chat' simply a mataphor?"
The metaphor breaks down if you think of video as something that changes over time, since the lifespan of a function invocation is instantaneous. However, what we see on a chat may causally depend on what we're sending to it, so it is a sort of chat.
For instance, here's a scenario we're collaborating with people B and C. We send information to B and simultaneously receive some packaged-up summary of our own information, which we send to C. Simultaneously, C sends us a receipt of acknowledgment that we use to justify our request to B in the first place. (Maybe B and C represent different bank accounts, and they each need to know the other account has done correct bookkeeping.)
Programs like these may sometimes be paradoxical, and if they are, a programmer can debug them like they'd debug an infinite loop. I expect many paradoxical-seeming manipulations will turn out to be well-defined, and that this will be a very declarative and expressive way to set up avenues for ongoing feedback between people.
---
"Will an oracle optimizer be permitted to look inside multiple invocations at once?"
Yes. I imagine oracle optimizers would be installed by whoever installs the language runtime. Whether we like it or not, that person has the power to install a hacked runtime that breaks programs' intended semantics however they like, so the optimizers they install might as well have that power too. :)
"That increment example looks like just the thing. Looking forward to it!"
Okay, here it is, finally! :) This is the first time I've actually written Tenerezza code that:
- Iterates sets. To keep each computation step cheap, a set can only be iterated at the time it's taken as a function argument.
- Destructures tagged data. To make control flow branches apparent in traces, destructuring only occurs at the start of a Tenerezza operation (i.e. function call). Since first-class Tenerezza values carry sets that may contain several elements of various tags, Tenerezza's destructuring conditionals are part of the set iteration syntax.
- Manipulates continuations. To keep each computation step cheap, continuations can only be obtained and installed at the time a function takes its continuation argument and its input argument.
- Uses the (save ...) sugar, which required some reinvention now that I've decided (call ...) won't be a primitive syntax.[1]
All right, here's the code:
(let-def
\ This takes a set of inputs, and it returns the same set but with
\ each (nil) or (succ pred) element wrapped in another
\ (succ pred). In other words, it increments unary numbers
\ represented as (nil) and (succ pred).
(def inc-if-nat (var-list/var-list-nil)
/each
/let-element-case pred
/match-element nil (env-pattern-nil)
(singleton return
/env-cons val
(singleton succ /env-cons pred local.pred /env-nil)
/env-nil)
/match-element succ
(env-pattern-cons pred pred-pred /env-pattern-nil)
(singleton return
/env-cons val
(singleton succ /env-cons pred local.pred /env-nil)
/env-nil)
/any-element
/singleton return /env-cons val local.pred /env-nil)
/let-def
\ This takes a set, finds its (yep val) elements to determine who
\ is listening, and sends each of those listeners the given
\ message. This returns an empty set.
(def broadcast (var-list/var-list-cons message /var-list-nil)
/each
/match-element yep
(env-pattern-cons val listener /env-pattern-nil)
(singleton call
/env-cons func
\ This carries a message, and it takes a listener. It sends
\ the message to that listener, and it returns an empty set.
(fn send (var-list-omitted)
/swap-continuation
/any
/singleton return /env-cons val local.message /env-nil)
/env-cons arg
(singleton return /env-cons val local.listener /env-nil)
/env-nil)
/any-element
/empty)
/let-def
\ This takes a set and finds its (yep val) elements to determine
\ who is participating and what (nil) and (succ pred) unary
\ numbers and other values they're giving us. This increments all
\ the unary numbers and sends all the incremented numbers and the
\ other values back to all the listeners. This returns an empty
\ set.
(def inc-to-everyone (var-list/var-list-nil)
/let-case everyone
/each
/match-element yep
(env-pattern-cons val participant /env-pattern-nil)
(save-root sr
/singleton call
/env-cons func
(singleton broadcast
/env-cons message
\ The (save-root ...) and (save ...) sugars pull out part of
\ a complex expression into its own definition, in this
\ case:
\
\ (def inc-to-everyone-intermediate
\ (var-list/var-list-cons everyone /var-list-nil)
\ /let-case message
\ /any
\ <... the code appearing under (save-root ...), but using
\ local.message in place of this (save ...) ...>)
\
\ This lets us keep our code in a rich tree-shaped structure
\ even though we're building a program out of independently
\ cheap computation steps.
\
(save sr call
func inc-to-everyone-intermediate (var-list-omitted)
arg message
/singleton call
/env-cons func (singleton inc-if-nat /env-nil)
/env-cons arg
(singleton return
/env-cons val local.participant
/env-nil)
/env-nil)
/env-nil)
/env-cons arg
(singleton return /env-cons val local.everyone /env-nil)
/env-nil)
/any-element
/empty)
\ This is just boilerplate for leaving the top level environment
\ untouched. The only effect of this command is to add the above
\ definitions.
/singleton return
/env-cons val
(singleton top-level-transformation
/env-cons func (singleton idfn /env-nil)
/env-nil)
/env-nil)
---
[1]
My notes still have (call ...) as a primitive syntax, but by the time I gave you the factorial example, I decided the Tenerezza syntax would not prescribe any particular way to do Turing-complete computation. Instead, that factorial example uses first-class values tagged (call func arg) and (return val) to describe how the computation will proceed. Hypothetically, an environment may refuse to support these tags, or it may support other tags of its choice.
Unfortunately, this design change messed up the meaning of the (save ...) syntax. In my notes, it would have desugared into (call ...) as it currently does in Staccato, but that's no longer an option. Even worse, several syntaxes implicitly set up code boundaries for (save ...) to capture, and (call ...) was one of those. First-class constructions with (singleton ...) should not generally clobber save boundaries, so I've now introduced a dedicated syntax (save-root ...) for setting these boundaries by hand. Meanwhile I've given (save ...) a few more arguments so that it'll work not only with the tag (call func arg) but with any similar tag.
I'm actually taking this chance to do an additional experiment with giving a label to save boundaries (in the above example, "sr"). An expression could appear inside a lambda, but using a label like this, we could compute its value eagerly, even specifying exactly which moment to use for computing the value. This is a lot like like the labeled quasiquotation syntax I've implemented in the Era reader, but with lambda instead of full quotation.
I showed what factorial would look like with some convenience macros in place, and now here's the same thing for this increment example:
(func inc-if-nat () preds
/each
/let-element-case pred
/match-el nil () (return/succ local.pred)
/match-el succ (pred-pred) (return/succ local.pred)
/any-element/return local.pred)
\ This takes a set, finds its (yep val) elements to determine who is
\ listening, and sends each of those listeners the given message.
\ This returns an empty set.
(func broadcast (message) listeners
/each
/match-el yep (listener)
(call
\ This carries a message, and it takes a listener. It sends the
\ message to that listener, and it returns an empty set.
(local-func listener
/swap-continuation
/any
/return local.message)
/return local.listener)
/any-element/empty)
\ This takes a set and finds its (yep val) elements to determine who
\ is participating and what (nil) and (succ pred) unary numbers and
\ other values they're giving us. This increments all the unary
\ numbers and sends all the incremented numbers and the other values
\ back to all the listeners. This returns an empty set.
(func inc-to-everyone () everyone
/each
/match-el yep (participant)
(sr/broadcast (sv/inc-if-nat/return local.participant)
/return local.everyone)
/any-element/empty)
Here's a full roster of the macros used here in the above three commands, aside from the ones that correspond to raw Tenerezza syntax:
- (func ...) expands into (let-def (def ...) /return/top-level-transformation ...), and its top-level transformation introduces a macro corresponding to the function definition.
- (local-func ...) is like (func ...) except it expands into (fn ...), it uses a gensym name, and it uses (var-list-omitted) so the set of captured variables will be inferred.
- (match-el ...) expands into (match-element ...)
- (sr _) and (sv _) expand into (save-root sr ...) and (save sr ...), both using the anaphoric variable "sr" so they can interact with each other.
- (return _), (succ _), (call _ _), and (top-level-transformation _) are macros like the ones (func ...) introduces. They're called with just enough parameters to construct a value of that tag, so they expand into (singleton ...)
- (inc-if-nat _) and (broadcast _ _) are macros like the ones (func ...) introduces. They're called with enough parameters to construct a value and call it as a function, so they expand into (call-singleton ...) which expands into (return/call (singleton ...) _)
---
The ins and outs of this code are probably still hard to read, but at least now there's less trivial boilerplate to distract from the tricky parts. Are there any tricky parts in particular I could clarify?
I reconsidered what kinds of macros to define, and I found a sweet spot this time! Now I can boil down the examples to this:
(defun factorial () n
(times n /call-new factorial () /plus n /negate/one))
(defun inc-if-nat () preds
(each-caselet pred preds
nil () succ.pred
succ (pred-pred) succ.pred
pred))
(defun inc-to-everyone () everyone
(each-case everyone yep (a)
/each-case everyone yep (b)
(link b inc-if-nat.a)))
Here's the same code with thorough comments:
\ Define a type (factorial) that can be called with argument `n`.
(defun factorial () n
\ Since the (factorial ...) macro hasn't been defined yet, we spell
\ it out with (call-new factorial () ...) instead.
(times n /call-new factorial () /plus n /negate/one))
\ Define a type (inc-if-nat) that can be called with argument `preds`.
(defun inc-if-nat () preds
\ For each singleton subset `pred` in `preds`...
(each-caselet pred preds
\ If it's a natural number, return its successor.
nil () succ.pred
succ (pred-pred) succ.pred
\ Otherwise, return it unmodified.
pred))
\ Define a type (inc-to-everyone) that can be called with argument
\ `everyone`.
(defun inc-to-everyone () everyone
\ For each (yep val) in `everyone`...
(each-case everyone yep (a)
\ For each (yep val) in `everyone`...
/each-case everyone yep (b)
\ Connect one channel to the incremented value(s) of the other,
\ and return the empty set.
(link b inc-if-nat.a)))
When using these new macros, every single macro call and subexpression is in a full-powered computation context. This way the programmer doesn't have to convert between time-limited contexts and full-powered contexts using (return ...) and save points. And the macros interpret raw symbol arguments as local variables, so the programmer can say succ.pred rather than (succ/return local.pred).
Meanwhile (each-caselet ...), (each-case ...), and (link ...) make it convenient to do iteration, destructuring, and continuation calls which are usually syntactically restricted to the beginning of a function. These macros simply generate a new function with a gensym name to host the operation.
Overall, this amounts to a really clean functional style, and I'll have to stop saying it's cumbersome to program in Tenerezza. :) These are still just macros, and they're not even code-walking macros, so all the Tenerezza primitives are close at hand when that level of control is needed.
That's the kind of question I want to hear. :) Does this help any?
Here are the relevant syntaxes of the Era reader:
\ A backslash followed by a space starts a line comment.
\ This is the string "this-is-a-string". This string representation
\ can only contain certain characters, but those are all the
\ characters we need for the examples at hand.
this-is-a-string
\ This is a three-element list. Its elements are the string "a", the
\ string "b", and a list of two strings.
(a b (c d))
\ All of the following examples are equivalent to the above list:
\ Forward slashes are just like ( but they don't consume ).
(a b /c d)
\ Dots abbreviate two-element lists.
(a b c.d)
\ Whitespace around parentheses, forward slashes, and dots is ignored.
( a b ( c d ) )
(a b/ c d)
(a b/c d)
(a b
/c d)
(a b c . d)
In Tenerezza code using the macro system, a list that begins with a string is usually a macro call, and it behaves however that macro wants it to behave.
In raw Tenerezza code (without macros), the grammar is very regular. Every list in Tenerezza code is a special form (a list beginning with a particular string), and Tenerezza's special forms always have a particular number of subexpressions. Each subexpression has a particular grammar nonterminal that describes what forms can appear there.
For instance, whereas you might expect most things to be "expressions," Tenerezza draws a distinction between get-exprs and env-exprs, among other things. A get-expr returns first-class values, whereas an env-expr is dedicated to creating (second-class) collections of named values.
Consider this Tenerezza code:
(singleton yep (env-cons val (local x) (env-nil)))
The (singleton ...) special form is an example of a get-expr. This special form takes two arguments: A stack frame name (in this case "yep"), and an env-expr to specify what the variables map to in this instance of that stack frame. Overall, the (singleton ...) expression represents a singleton set containing the specified stack frame instance.
The (env-cons ...) special form is an example of an env-expr. It takes three arguments: An environment key (in this case "val"), a get-expr providing some first-class value to associate with that key, and an env-expr representing the rest of the environment. Overall, this special form represents the same thing as the env-expr, but modified to add the given binding.
The (local ...) special form is an example of a get-expr. It takes one argument: A local variable name (in this case "x"). It represents the value of that variable.
The (env-nil) special form is an example of an env-expr. It takes no arguments. It represents an empty environment.
I might agree with you there, but I'll take it as a question rather than a suggestion. :-p
The "n" is the function's argument, and () is the list of variables in the stack frame's environment.
In most Scheme-like languages, a visualization of the stack would be several levels of function calls. Every expression to the left would have been evaluated already, and every expression to the right would still be waiting. For instance:
Current return value: 3
Remaining stack (starting with the freshest activation):
(plus _ #suspended:(negate (one (nil))))
(factorial _)
(times 3 _)
(times 4 _)
(times 5 _)
Staccato and Tenerezza have a more constrained model of the stack. In particular, the stack can never contain suspended code. As such, the program never quite lands in the above state, but I'll show the states before and after it:
This makes stack frames very simple. They're just tagged collections of values. This meshes into the rest of the language: To call a function is simply to push it onto the stack and to proceed with computing its argument. The (fn ...) syntax is just sugar for writing (def ...) and constructing a stack frame using variables from the surrounding lexical scope.
---
Incidentally, I had a bug in the abbreviated versions of factorial:
(defun factorial () n
- (times n /call-new factorial () /plus n /negate/one))
+ (times n /call-new factorial () /plus n /negate/one/nil))
These fancy macros can be called in two ways, either to construct a value or to call it as a function:
(cons a b) \ creates a (cons car cdr) first-class stack frame
(cons a b c) \ gets the result of (call (cons a b) c)
(one) \ creates a (one) first-class stack frame
(one (nil)) \ gets the result of (call (one) (nil))
When I just wrote (one), I was generating a (one) stack frame, rather than actually retrieving the proper representation of 1. This could still work if the (one) stack frame was a proper representation of 1, but I intended the representation to be flexible.
Right now I'm juggling two ways to pass multiple arguments.
For globally defined functions, such as the ones in the examples, I construct a data structure like (plus term) which holds all but one of the "arguments," and then I call it with the final argument.
For higher-order functions, the call site is using a function that was constructed elsewhere, so it has to use some other method to cram in more than one argument. I think my favorite approach right now is to define a data structure specifically to carry these arguments. This way if the program is refactored and the arguments change, the new code can still be backwards compatible with old stack snapshots that mention the old data structure. All it takes is for the new code to have a conditional where it handles both the old tag and the new one.
The second calling convention could work for global functions too, and it might be a lot less awkward for documentation; when I describe a two-argument function called (plus term) or a four-argument function called (my-func a b c), it looks pretty weird. :) Unfortunately, it really commits us to having messy stack snapshots full of macro-generated steps:
Current return value: (one-args)
Remaining stack:
(one)
(gs-12301) \ will construct (negate-args _)
(negate)
(gs-12302 3) \ will construct (plus-args 3 _)
(plus)
(gs-12303) \ will construct (factorial-args _)
(factorial)
(gs-12304 3) \ will construct (times-args 3 _)
(times)
(gs-12304 4) \ will construct (times-args 4 _)
(times)
(gs-12304 5) \ will construct (times-args 5 _)
(times)
Hmm, maybe this isn't much worse than before. Factorial is a funny example because I can put all the function calls in the last argument, which makes the stack look nice. If I put them all in the first argument instead, we'd see some macro-generated save points:
(defun factorial () n
(times (call-new factorial () /plus (negate/one/nil) n) n))
Current return value: (nil)
Remaining stack:
(one)
(negate)
(gs-12305 3) \ will call (plus _ #suspended:n)
(factorial)
(gs-12306 3) \ will call (times _ #suspended:n)
(gs-12306 4) \ will call (times _ #suspended:n)
(gs-12306 5) \ will call (times _ #suspended:n)
Real code is likely to have a handful of save points per function, so the stack will usually look something like that.
Oh. Actually, if I passed arguments in the form of data structures, that bizarro-factorial would look a little nicer on the stack. You can actually tell that it's going to call (plus) and (times) even if you don't look up the definitions of gensyms:
Current return value: (one-args)
Remaining stack:
(one)
(gs-12301) \ will construct (negate-args _)
(negate)
(gs-12302 3) \ will construct (plus-args _ #suspended:n)
(plus)
(gs-12303) \ will construct (factorial-args _)
(factorial)
(gs-12304 3) \ will construct (times-args _ #suspended:n)
(times)
(gs-12304 4) \ will construct (times-args _ #suspended:n)
(times)
(gs-12304 5) \ will construct (times-args _ #suspended:n)
(times)
Okay, I might settle on using this calling convention for everything in this convenience layer. :) Thanks for prompting me to think about this.
I guess I'll probably use a slightly tweaked set of macros in future examples, taking this calling convention into account.
---
"Or a variable number of them?"
One option is to pass a cons list. Assuming there's a (list ...) macro, it's easy to call (foo ...) with a list:
Oh, yes, I guess Radul's information propagation is related. Aside from the state model, I think Tenerezza and that system could be seen as competitor dialects with some minor technical and philosophical quirks keeping them distinct from each other, like Ruby and Python.
Radul talks about dealing with partially known values, and I don't exactly have partial values in Tenerezza; I just have sets, and a partial set is a set.
Radul talks about the notion of a partially known value that improves with time, and that notion is inherently stateful. But Radul's state nodes are second-class, and for some reason they're intermingled with stateless propagation nodes. I first saw that paper after I had already been hacking along to David Barbour's vision of programming where there are first-class interfaces to state but the state always resides outside the running program. I'm not sure I see the appeal of second-class state nodes, and on the flip side, I'm not sure I see the point of having stateless propagation nodes if the rest of the network can be stateful.
For Tenerezza, I haven't tackled state yet, but I have an approach in mind. I think it's very different from Radul's approach, but maybe not different enough that the Ruby/Python comparison breaks down.
In Tenerezza, state can be accessed via first-class channels, which is naturally justified by the metaphor that you can ask a chat buddy to remember something for you. However, every Tenerezza call has access to a "conscience" channel that appears out of nowhere so that the program can explicitly interact with the language runtime itself. This channel is naturally justified by the fact that the language runtime has the power to disrupt and interact with the program whether the programmer wants it to or not. I call it the conscience because I expect it to be a good channel to consult for advice if there's an error, and it doubles as a good channel to supplicate for call-specific state resources.
I have a very vague plan to support some kind of generic operation for resource reallocation, which would be useful for managing the allocation of existing state resources, randomness resources, robots, and so on. The premise would be that if the two sides of a communication channel pitch in resources and simultaneously agree to the same protocol, then that agreement itself becomes a third entity that the two can communicate with. We understand our world through a process of social reinterpretation, so I'm excited to think that this social reinterpretation operator would singlehandedly be a sufficient protocol to interact with whatever we encounter in the world.
---
"That increment example looks like just the thing. Looking forward to it!"
Okay, I'll try to get that written up at some point. XD;
