Why Synereo?

A new decentralized, distributed social network is emerging, and naturally people are curious. Gideon Rosenblatt asks a key question: Why Synereo instead of Facebook?

i provide an answer here in six basic points that cover architecture and information flow consequences for resiliency, autonomy, and privacy, as well as important aspects of the user experience, user compensation and the attention economy.

TL;DR: you are the network, not the product.

1) A distributed, decentralized architecture is more resilient against certain kinds of attacks. From a hacker hacking a centralized service and scooping up all the credit card data from a single database to a government shutting down a service providing information counter to the incumbent narrative, a distributed, decentralized architecture is more resilient against these kinds of attacks. Clearly, this is not the architecture that Facebook enjoys or promotes. It can't because its revenue model wouldn't work well in this setting.

2) Above this architecture, Synereo provides a qualitative notion of identity. This is not about identity as token because that notion of identity doesn't serve individuals who have rich internal multifaceted presence. What is needed is to be able to reveal enough about oneself to participate legitimately in a conversation without necessarily revealing information that is either sensitive or irrelevant. Consider a self-governance or participatory democracy process like the budget games. Were these conducted in an online situation people might be less likely to participate if the games revealed information about their political views that made them the target of unwanted attention. In the US such issues have included healthcare reform and gay marriage. On the other hand, a government representative needs assurances that the online participants are actually registered voters in their districts and not bots. Synereo allows users to reveal enough identity-related information to participate in a variety of processes without necessarily provding personally identifiable information. If someone is pursuing employment from an employer that is ok with them working remotely, then the employment application process doesn't have to reveal the candidates' residential address. Again, this approach doesn't fit with Facebook's revenue model.

3) Synereo makes strong guarantees about never letting Synereo code see user data in the clear (unless users' give explicit permission). Despite these guarantees, Synereo provides a sophisticated search mechanism that allows users to search content throughout the slice of the network visible to them. Facebook just rolled out a graph search. Many people are very concerned about what this means about privacy. If you would like to know more about how Synereo achieves this, awesome! Please contact me and i will personally explain the mechanism in as much detail as you would like. Beyond this Synereo is based on a mathematical model of decentralized and distributed computing that allows for the specification and enforcement of information flow policies. The language for these policies is exceedingly rich -- considerably richer than friends, friends-of-friends, etc. These policies can be autonomously developed and assembled into larger policies. The polices can be checked for desirable properties. This provides the basis for smart contracts that allows for just-in-time assembling of services from subcontractors. In other words, Synereo can help groups assemble temporarily to form an organization to complete a task or provide a service. This level of sophistication just doesn't exist in Facebook. It doesn't even exist in Ethereum. The Synereo white paper describes an example of information flow policies as relates to public health and public safety. We believe Synereo's feature set makes it an ideal mechanism for participatory self-governance.

4) Synereo provides the attention economy model. This allows participants in the network to begin to get some of the reward for their participation. It's not just that the monetization of attention deployed in social networks is commonly estimated in the 10's of billions of USD. Nor that Facebook users never see a penny of that. It's also that as a result of the shift in distribution mechanism the creative classes are under unbearable pressure. When a guitarist of the stature of David Torn gets 8USD from Pandora for 100,000s of plays of one of his tunes, making a living as a guitarist becomes nearly untenable. This is not a one time occurrence. Read Zoe Keating's article about how YouTube is treating her as they roll out their new music service. This same scenario is playing out in journalism, photography, etc. The creative classes are under siege. The attention economy provides a direct way for creative people to earn compensation for their creative outpouring. Facebook simply doesn't have such a model and it would directly undermine their existing revenue model.

5) Synereo provides users with a new level of control over what shows up in their feed. At this level of detail we can say that Synereo identifies two basic types of entities, ports and filters. A port can either be a source of information (like one of your friends from whom you receive posts, or an rss feed to which you are subscribed, or a mailing list to which you are subscribed, or a device on the Internet of things, or ...) or a sink for information (like one of your friends, or an rss feed to which you publish, or ... ). A filter is something applied to the stream of information flowing into or out of a port to further refine what goes into or comes out of the stream. Notice that when you combine a filter with a port you get a new port. This kind of 'algebra' of information flow components gives users a new toolkit for controlling what they see in their feed. It also has fairly natural UI metaphors that have a long history of success as a means of conveying the presentation of streams of events. This leads is to the last point.

6) Synereo provides new UI experiences that allow for users to see more about the dynamics of information flow. As a simple example, Facebook organizes the posts of all your friends into a single interleaved stream. If you were to uninterleave this into several streams that were synced by timestamp you would see how your friends' posts were related to each other in time. Picture in your mind's eye 5 timelines running left to right. One timeline for one of 5 friends. Each timeline provides an iconic representation of that friend's posts. When posts stack up in a near vertical line it means that your friends are posting at the same time. This gives you a way to see into the temporal dynamics of the communications of your group of friends. The reason i chose 5 is because there are 5 lines in a single musical staff. Just as the vertical stacking of notes on a staff represents play these notes at the same time, i.e. play a chord, chords in the 'score' representation of timelines allow for people to see how peoples actions are related in time. Any 6yr old can learn to read the temporal dynamics off of a single staff. A good conductor can read and hear in her mind 7 staves. So, the surface of inborn information processing capacity of the human mind for processing temporal dynamics is not even being scratched, let alone the depths plumbed. Facebook does not actually have a vested interest in users being able to utilize their capacity. They have a vested interest in directing attention in a way that maximizes return for their investors.

Enzymatic interaction

It is traditional for me, around this time of year, to provide holiday (brain) candy for folks in my technical community. This year's offering comes from a conversation with Marius Buliga about chemlambda in which he referred to β-reduction in the λ-calculus as an enzyme. This got me to thinking about explicitly modeling the COMM rule in the π-calculus as an enzyme. It turns out you can do this quite easily and it has a lot of applications!

For simplicity, i'll use the reflective, higher-order π-calculus, but extend the basic calculus with a primitive process, COMM:

P, Q ::= 0 | COMM | x?( y )P | x!( P ) | *x | P|Q
x, y ::= @P

(Note that i've adopted a slightly friendlier syntax since i first developed the reflective π-calculus. Instead of writing « P » and » x «, i now write @P and *x. This echoes the C and C++ programming language notation for acquiring a reference and dereferencing a pointer, respectively -- which is the key insight of the reflective calculus. We can get a kind of pointer arithmetic for channel names if we treat them as quoted process terms.)

Structural equivalence includes alpha-equivalence and makes ( P, | , 0 ) a commutative monoid. Of interest to us is

COMM | P = P | COMM

So, COMM mixes into a parallel composition.

Notice that COMM cannot penetrate an abstraction barrier, i.e. 

x?( y )P | COMM != x?( y )( P | COMM )

Enzymatic reduction in reflective π-calculus

There is an interesting design choice as to whether

x!( Q ) | COMM = x!( Q | COMM ) 

Treating COMM as enzymatic, the COMM-rule

x?( y )P | COMM | x!( Q ) → P{ @Q/y } | COMM 

results in the standard dynamics, if there is just one COMM process in the expression. If there are more COMM processes, then we get a spectrum of so-called true concurrency semantics, with the usual true concurrency semantics identified with the limiting equation

COMM = COMM | COMM

which allows to saturate a parallel composition with COMM in every place where an interaction could take place.

Writing COMMⁱ  for COMM | ... | COMM ( i times ), another set of dynamics arise from rules of the form

x?( y )P | COMMⁿ | x!( Q ) → P{ @Q/y } | COMM^m

with m < n

This bears resemblance to the Ethereum platform's idea of "gas" for a smart contract's calculation. Mike Stay points out that associating a cost with communication makes it look like an action in physics. Notice that you can get some very interesting dynamics with COMM-consuming interaction rules in the presence of COMM-releasing abstractions.

One example interpretation that i think works well and provides significant motivation is to treat COMM as a compute node. A finite number of COMMs represent a finite number of nodes on which processes can run. Likewise, it is possible to model acquisition and release of nodes with cost-based COMM-rules and certain code factorings. For example, call a process inert if P | COMM cannot reduce and purely inert if P inert and P != Q | COMM for any Q. Now, suppose

COMM: x?( y )P | COMMⁿ | x!( Q ) → P{ @( Q | COMM )/y } | COMM^n-1

and only allow purely inert processes in output position, i.e. x!( Q ), with Q inert. Then interaction acquires a node and dereference, *x releases one. For example,

x?( y )( *y ) | COMM | x!( Q ) 

→ 

*@( COMM | Q ) 

≡ 

COMM | Q

In terms of possible higher category theory models, the reification of the 2-cell-like COMM-rule as a 1-cell-like COMM process ought to provide a fairly simple way to make one of Mike Stay's recent higher category models work without suffering too many reductions, which has been the principal stumbling block of late. Notice that in this setting we can treat x?( y )( COMM | P ) as an explicit annotation by the programmer that interaction under an abstraction is admitted. If they want to freeze abstraction contexts, they just don't put COMM under an abstraction where an interaction could take place. In more detail

x?( y )( u?( v )P | COMM | u!( Q ) )

constitutes a programmer-supplied annotation, it's okay to reduce under the ( y )-abstraction, while

x?( y )( u?( v )P | u!( Q ) )

is an indication that the term under this abstraction is frozen, until it is released by communication on x.

Compositional interpretations of physical processes

This very simple insight of Marius' that interaction is enzymatically enabled creates a wide variety of dynamics that have broad range of applications! Merry Christmas to all and a Happy New Year!

Trust the principle

The cryptographic e-cash community was caught off-guard by BitCoin's adoption and success. One group of researchers from PARC and Standford took heed and contemplated what factors contributed to that success. Distribution and decentralization was one of the key features they identified as contributing to BitCoin's adoption and success. From the paper:

No central point of trust. Bitcoin has a completely distributed architecture, without any single trusted entity. Bitcoin assumes that the majority of nodes in its network are honest, and resorts to a majority vote mechanism for double spending avoidance, and dispute resolution. In contrast, most e-cash schemes require a centralized bank who is trusted for purposes of e-cash issuance, and double-spending detection. This greatly appeals to individuals who wish for a freely-traded currency not in control by any governments, banks, or authorities — from libertarians to drug-dealers and other underground economy proponents (note that apart from the aforementioned illegal usages, there are numerous legitimate uses as well, which will be mentioned later). In a spirit similar to the original motivation for a distributed Internet, such a purely decentralized system guarantees that no single entity, no matter how initially benevolent, can succumb to the temptation or be coerced by a government into subverting it for its own benefit.

One way to look at the relationship of trust between individual and network in a distributed and decentralized architecture is that you can trust the network if you trust the underlying, organizing principles of the network. This kind of trust works differently than trust placed on any single or central individual. 

There's a funny twist in this. While, on the one hand, it is possible to be physically present with an individual, to sit together with them, to look at them, hear them, and on the other, principles can seem to be much more abstract, much more removed, principles are often easier to grasp than individuals. As Gandhi's biographer, Louis Fischer, pointed out, the principle of 'an eye for an eye' can have the consequence of leaving everybody blind. Yet, as history shows, the principle of Satyagraha and non-violent, peaceful protest, central to Gandhi's efforts, and a substantial influence on Martin Luther King's plays out differently. We can see into the workings of principles in a way that we often can't with individuals. This is not to say that individuals and even institutions can't embody a quality or principle that we wish to bring into the network. However, we have to see the whole of an individual before we can tell if they do indeed embody that quality or principle. We don't always have that access or that perspective on an individual.

BitCoin's architecture weaves together principles that make the most of individuals more self-centered aspects such desire for personal gain and reticence to trust each other, and puts them in service of a higher aim, a trustworthy network. In short, it lets people be themselves, mostly honest, with some conceit, some deceit, and a need to connect to something greater. This asks for a qualitatively different relationship between the individual and the network: trust the principle that organizes the network by letting people be what they are.

splicious : facebook :: protunity : linkedin

People don't really know what's gone into the development of www.splicious.net. A year before we launched the splicious crowd funding campaign we launched www.protunity.com. This was a test case to drive out the technology. One way to understand the relationships of these networks is via those old SAT-style analogies:

splicious : facebook :: protunity : linkedin 

The underlying technology (barring lots of improvement between when we launched Protunity and now) is the same . Therefore, the splicious campaign is not like other campaigns where what they have is a vision, but no actual solution. We have a solution that's already at a certain level of maturity.

We wanted to wait to bring this offering to market until we had at least that level of maturity. Additionally, we wanted to have an economic model that made sense, one that grows a self-sustaining network, free of ads and free of other corporate sponsorship. That's where the emerging cryptocurrency movement suddenly came into play. With BitCoin and other cryptocurrencies we can provide a distributed network that is self-sustaining.

Really, if you look at the numbers, in terms of capital investment, and person-years, as well as technological innovation, we've provided 99.999% of the solution. We're looking to see if there's enough interest for people to help us with 0.001%. That's what we need to roll out the splicious network.

We're confident that with even that level of engagement we can grow the network to a global alternative to the existing social messaging platforms. One that balances privacy and trust, one that values creativity and engagement, one that puts you back in charge of what you see of your Internet-communications, and who sees what you share.

Imagine all the people...

Humans are social. We have a built-in urge to share observations, insights, thoughts and feelings. We have a need to feel received. The social media with their ubiquity, easy access, and ease of use meet this need relatively well. The simple feedback mechanism, clicking a “like” or “+1” button can be a powerful expression of sentiment and connection.

But, are you concerned about who can see communications meant for your friends, family, or colleagues, from your email to your FB posts?

Are you concerned that your creative output and personally identifiable information are bought and sold by social media companies, advertisers, and whoever else they sell it on to?

Is your feed overrun with ads and TMI that you can’t organize? Or worse, organized by someone else’s algorithm?

Imagine a world where social media served you. Period.

What if the online outlets for your creativity, your music, political commentary, stories, recipes and designs were also outlets for earning money?

What if they could allow you to support yourself and your friends, monetarily?

What if they could make it easy for you to play a more active role in deciding what you see and when, and who sees what you share?

Splicious is a social communications platform designed from the ground up to solve these problems.

Splicious helps you

• focus
• dynamically organize your own ad-free feed,
• label and search your messages and posts
• conduct safe and easy transactions, using popular cryptocurrencies, like BitCoin, to
• buy and sell stuff, or
• raise money for a cause, or
• or support people whose online contributions you value -- so they can keep doing what they love -- and
• and never give a penny to Wall St
• and balance privacy AND trust
• with protocols for meeting new people
• and verifying their claims with mutually trusted friends

We’re not coming to you with just a vision or a bright idea. Other teams have underestimated just how hard this problem is. The Splicious team has worked for 4.5 years to bring you this offering. We know it can be prettier. We know it can be easier to use on mobile platforms like cell phones. We know there are a million ways it can be improved. That’s all a part of rolling out the network for your use. And we would love to do that work. 

We just need to know if the world we imagine is the world you want. That’s why we’re asking for your help to fund this phase of the project. Here’s Mike Stay to tell you how we plan to roll out the network and how you can help us.

What do you lead with in a new offering? How about what enables us to improve our connection?

The Splicious team has wrestled with what to lead with in attempting to get their message out to more people. Recently, someone gave us some outlier feedback that we felt was well worth discussing. He suggested that the biggest differentiator of the Splicious offering was our approach to distributed identity. Of all the engagement from potential users, his is effectively the lone voice. What we've gotten back, repeatedly, from user engagement is that there's a pretty big bifurcation in the market.

• Those that are interested in the use of cryptocurrency to increase their ability to trade with others.
• Those that are concerned about privacy and identity on the Internet.

If our sample size is representative, the first category is many times larger than the second. The second actually decomposes into two subcategories: the hacker/cryptocommunity and the wealthy. Both groups are exceedingly small in numbers. The average person is happy to make wry jokes about the Snowden revelations on FaceBook, but that is more or less the extent of the engagement (and implied level of concern) we are able to observe in most folks. 

Clearly, many people have an in-built urge to share their observations, insights, thoughts and feelings and to feel received through a simple feedback mechanism, an expression of sentiment, such as clicking the "like" or "+1" button. Basically, people have an urge to connect and feel connected. The social media matches this urge relatively well. 

What's especially sticky in the modern social media experience is the ratio of attention to reward. For a small output of attention (read a short post, click the like button; make a short post, check to see who's liked it) people get an enormous pay-off: they feel connected to community. We hypothesize this provides an important indicator for how to take this a little farther: make small increases on the demand for attention at the point of contact.

The feedback we've gotten from people who do engage is that extending the basic social media framework with a small delta, where the action of expressing sentiment is linked to the transfer of a small amount of money -- like a mBTC (roughly 50c) or smaller -- resonates. Once this notion lands people can see other opportunities for themselves: crowdfunding of very simple and small activities, like writing a song, or taking a photo; microfinancing a small project; and, more generally, engaging in a distributed marketplace.

While much of the hard work has been about 

• making the platform truly distributed, 
• addressing privacy and security, 
• working out a mathematically sound model that informs: 
• the programming model, 
• the architecture, and 
• means to express, reason about, and mechanically enforce privacy and security policies

That's not interesting to most people at this point in history. Eventually, it may be; but, to be honest, if all of that work remained as invisible to most people as how their car, or their plumbing, or computer works, i would be perfectly happy. Right now, based on our limited engagement with the market, it seems to us that people are much more interested in how to get more from the experience of connecting. i think there's a great deal of wisdom in that, personally. We are going to have to come together as a global community if we are going to successfully face the challenges coming our way. That, in a nutshell, is why we lead with Splicious for the creative.

Splicious: the role of cryptocurrency in our transition to a new economics

Yesterday, Frank Sheldon, author of Far from the Sea We Know, sent the Splicious team an article about Dogecoin as an alternative to Bitcoin. Mike Stay, one of the developer's on splicious, also brought up the possibility of using Dogecoin for many of the reasons indicated in the article Frank sent.

Our real position at splicious is that cryptocurrency, as a general category of technology, is going to be a big part of the transition to the new economics. As such splicious will support not just BitCoin (BTC), but also others and especially those that attend to privacy and security, like ZeroCoin, as well as ease of use, like Dogecoin.

We ended up choosing BTC as the first cryptocurrency we support largely because of its visibility. Specifically, we felt that if Zuckerberg makes a very public announcement about BitCoin, and Reddit directly supports BitCoin, etc, then this was the best first proxy for the phenomenon. Perhaps this was a lapse in moral judgment on our part.

The challenge we face is that there is so much to explain in our offering -- from that value of the network being distributed; to the value of distributed identity; to the value of the underlying mathematics; to the value of reciprocal maintenance; and how existing capital instruments are now failing to meet this, their designated purpose; and the role of cryptocurrency in being able to realize at least some aspects of this in a functioning Internet-based technology -- that we have to cut something somewhere. Explaining what Dogecoin is and how it compares to BTC and how cryptocurrency, in general, is part of a much larger transition we are undergoing, as a culture, felt like a step too far.

Instead, we were hoping to use a little metonymy, both in our message and in our initial coding efforts. On the other hand, much of what is happening with Dogecoin feels directionally correct. We're very grateful to Frank for reminding us of that! If you like what you're reading, head on over to our crowd funding site and contribute today!

Splicious - your network, your data

It's been a very long time since i posted here. Part of the reason is that for the last four years i've been working with increasing intensity on an exciting project. It's been really fun working on splicious and especially fun to think about what it might mean for communications on the Internet; but, until it reached a certain level of maturity, none of us on the project felt we could really talk very publicly about what we were doing.  Now, we feel we're ready to engage.

Splicious is a distributed social communications platform that provides three core benefits

• a simple approach to distributed identity
• a simple approach to searching message and post level content both in realtime and throughout the history of your communications
• integration with popular cryptocurrency, like BitCoin, so that people can directly support content creators and curators

We feel this directly addresses two social trends we have been observing with some alarm.

• Privacy and information flow in internet-based communications has been severely compromised, with corporate and government agencies being able to access and profit by personally identifiable information and no real corresponding transparency on the part of these agencies to balance the situation.
• Capital has been concentrating in such a small sector of society as to virtually cease to perform its principal function: provide a tool whereby we can all take care of each other and the planet.

Knowing that the corporate exchange of personal information (including personally identifiable information) is a >9B$ market, we feel it should be possible to turn the whole model on its head. We put a novel social media UI on the front end of our communications platform. This UI lets people decide for themselves how much that information is worth to them, and using BitCoin, lets them directly support people who provide them with information they find valuable.

We've been running initial user trials and have gotten some very positive feedback. Here's what Vlad Patryshev, ex-Googler and privacy/security guy for Google's first social network, had to say about his experience with splicious. 

Now we're at the most exciting stage of the project. We've invested 4.5 years of our lives into this effort. The collective capital investment exceeds 2M$. Now we need to see if we're on the mark: if there are enough people who feel that there is a problem worth addressing here; and that splicious comes close enough to the mark that a sufficient number are willing to get behind this solution. That's why really we're running a crowd funding campaign on RocketHub. When enough of us come together to work on something we believe in, that's when change happens.

The reason we've structured the ask in the way we have is due to the high quality bar that splicious has to meet. The fact that a user can search all the communications they have access to; and they can send and receive BitCoin as support for sharing content means that users can suffer a much greater risk if the system fails to deliver as promised. This is why we have to roll the service out in a very careful, step-by-step fashion and why we are only allowing 1000 users initially. That's also why we are asking for new crowd funding at each 10-fold increase in the number of users.

i am not a monad i am a free algebra! (Pt 4)

This post is a part of a series of posts attempting make explicit some folklore and wisdom of the commons that computer scientists enjoy but neither mainstream programmers nor mainstream mathematicians have exposure to. Both of these cultures would benefit from this common wisdom and so it feels like telling this story is of a certain utility. The caveat is that unlike the other posts the pay-off is cumulative not immediate. i'm not going to present some eye-catching bauble as with the post on Conway Games. Instead, you're going to have to steep in this stuff a bit before the goodness kicks in.

It’s worth summarizing what we’ve said so far. A very broad class of algebras, corresponding to what are commonly known as algebraic data types, have purely syntactic presentations in terms of a freely generated structure and a collection of relations. Once we have this general idea in mind, whether we are programmers, computer scientists, mathematicians or logicians, we are probably pretty comfortable with the idea of polymorphism and so are probably pretty comfortable with the idea that ‘freely generated structure’ has potentially many polymorphic interpretations ranging from simple concatenation of symbols to languages generated by (Chomsky) grammars, and that a similar intuition applies to relations. Here’s a little table summarizing some of this content with examples.

	Mainstream mathematics	Computer science
Generators	Symbols	Grammars
Relations	Equations	Structural equivalence
Examples	Monoids, Groups, Rings, Fields, Vector spaces, ...	Lambda calculus, π-calculus, ambient calculus, ...
	Example monoid specification: Generators: ISO character set Relations: s ++ “” == s == “” ++ s s1 ++ ( s2 ++ s3 ) == (s1 ++ s2) ++ s3	Example language specification: Generators are given by the grammar E ::= Var | \ x -> E | E E Relations: alpha-equivalence: \ x -> E ≈ \ y -> (E{y/x})

A smattering of Universal Algebra

There is one thing the mainstream mathematician is likely to have that modern programmer does not, and that is some passing familiarity with the core notions of Universal Algebra. Universal algebra presents a general theory of what an algebra (read algebraic data type) is and spells out for a given algebraic theory what it means to have a presentation and a model and what constitutes a purely syntactic model.

Actually, armed with what we already have we can present the core notions via a simple grammar! Let’s begin with the idea of an algebraic expression.

Operation . AlgebraicExpr ::= Symbol “(” AlgebraicExpr* “)”
Name . Symbol ::= Identifier

This would correspond to the Scala code

trait AlgebraicExpr
case class Operation(
symbol : Symbol,
actuals : List[AlgebraicExp]
) extends AlgebraicExpr

trait Symbol
case class Name( identifier : [| Identifier |] ) extends Symbol

A short detour through 2-level type decomposition

Notice that we have deferred providing a semantic interpretation of the type Identifier. We did this because there was no production for it in the grammar, and our interpretation scheme allows us to be lazy about this. Further notice that Scala gives us a way to be permanently lazy about missing productions. Because our scheme interprets grammatical categories as types, both parametric polymorphism (that’s generics to you!) and type members offer reasonable semantic targets for lazily interpreting missing productions. We parametrize in terms of the type corresponding to the category that is missing a production. In the case above we have

trait Symbol[Identifier]
case class Name[Identifier](
identifier : Identifier
) extends Symbol[Identifier]

Now, if a production (or several!) for Identifier ever gets codified we can inject it into our semantic interpretation. So, suppose we have two types of identifiers, Strings and UUIDs.

LocallyUnique . Identifier ::= String
GloballyUnique . Identifier ::= UUID

These would give rise to the productions above which correspond to the type specifications below.

trait Identifier
case class LocallyUnique( s : String ) extends Identifier
case class GloballyUnique( u : UUID ) extends Identifier

Then we are free to provide the concrete interpretations of Symbol via instantiation of the parametric type. Notice that in Scala we could improve on our interpretation of Symbol and remain lazy with type variance constraints. We don’t want any old type (such as Int) supplied in the type parameter, but only those types that really do act as Identifiers. In other words,

trait Identifier
trait Symbol[ID <: Identifier]
case class Name[ID <: Identifier](
identifier : ID
) extends Symbol[ID]

Now, only the *Unique case classes are available types for substitution in the type parameter. Moreover, if we decide to add path-based identifiers later

Pathbased . Identifier ::= Identifier ( “.” Identifier )*

We can likewise add our semantic interpretation in a similarly lazy, compositional fashion, without perturbing our existing code.

case class Pathbased(
id : Identifier,
p : List[Identifier]
) extends Identifier

Of course, this benefit isn’t entirely for free. If we do use this method, then our AlgebraicExpr type will also have to have been parametric in Identifier because it has a dependency on Symbol which is so parametrized. It’s a small price to pay: it just means that the interpretation needed to be cognizant of this strategy from the outset. Now that we know about the strategy we can incorporate it from the beginning.

trait AlgebraicExpr[ID <: Identifier]
case class Operation[ID <: Identifier](
symbol : Symbol[ID],
actuals : List[AlgebraicExp[ID]]
) extends AlgebraicExpr[ID]

trait Symbol[ID <: Identifier]
case class Name[ID <: Identifier](
identifier : ID
) extends Symbol[ID]

And now you, gentle reader, have a basic understanding of 2-level type decomposition. One last point before returning to the main topic, the use of type parameters as a means of lazily handling missing productions opens another possibility: recursion. In terms of our example, consider the following class of Symbols

case class Quotation[ID <: Identifier](
expr : AlgebraicExpr[ID]
) extends Symbol[ID]

This allows for a wholly new class of Symbols which are quotations of AlgebraicExprs. The general strategy of using recursion in 2-level type decomposition is well known. This specific application to the general area of the creation of symbols is less well known and has some significant implications -- that are beyond the scope of this discussion. Suffice it to say that this technique -- parametrizing syntactic categories in syntactic categories -- can be projected back from our semantic domain (where we introduced it) to the syntactic domain of specifying free(ly generated) structures. This opens up a whole new level of expressiveness at the syntactic level corresponding to the expressiveness we are accustomed to with the introduction of parametric polymorphism. In some very real sense, the type definition language of Haskell can be seen as a model or blueprint for a much richer syntax specification mechanism. Note bene: this is bleeding edge thinking! Apart from Haskell, itself, there does not exist a tool for specifying abstract syntax in this fashion. (Ok, CS community, i know you can take a hint.) (Scala coders beware! Scala generics will not allow you to tie the recursive knot this way without some trouble. Instead, use type members and you will be happier.)

A smattering of Universal Algebra (continued)

With that discussion under our belt we can now reconstruct our grammar for AlgebraicExprs

Operation . AlgebraicExpr ::= Symbol “(” AlgebraicExpr* “)”

Using the same trick as above, we can simply defer any interpretation of Symbol. [Note: from now on, when there’s little risk of confusion, i’m going to drop the use of quotations around elements concrete syntax like the parens in the production above, and use a different font, instead. And, consistent with this, i’ll use font to indicate a variety of categories present in our specification. So, the above production becomes

Operation . AlgebraicExpr ::= Symbol ( AlgebraicExpr* )

Thus endeth the notational convention sidebar.]

trait AlgebraicExpr[Symbol]
case class Operation[Symbol](
symbol : Symbol,
actuals : List[AlgebraicExp[Symbol]]
) extends AlgebraicExpr[Symbol]

So, if s, s1, s2, … are Symbols (whatever those are), then

s(), s1( s() ), s2( s(), s1( s() ) ), s3( s(), s1( s() ), s1( s() ) )

would be recognized by this grammar as AlgebraicExprs. Moving toward an eventual semantic interpretation of these purely syntactic gadgets, we’re going to identify expressions of the form s() as constants. That is, they will eventually be interpreted in much the same way we normally interpret constants in a functional language, as pure functions of zero arity. Likewise, we’d like to interpret expressions of the form s1( s() ) as applications of a unary function, which we’ll write [| s1 |] to the constant [| s |].

By now, you’ve probably spotted the general convention in this posting (which is a convention in programming language semantics at large is) to use [| - |] (pronounced ‘meaning of’) as denoting the compositional semantic interpretation of some piece of syntax to its target semantics. Thus, we have a general specification of the semantic interpretation of our AlgebraicExprs.

[| s( e1, …, eN ) |] = [| s |]( [| e1 |], …, [| eN |] )

In terms of our Scala code we can write this down, too.

trait Semantics[
Symbol,
Value,
Operator <: { def apply [X] ( actuals : List[X] ) : X }
] {
def meaning( s : Symbol ) : Operator
def meaning( expr : AlgebraicExpr[Symbol] ) : Value = {
val op = meaning( expr.symbol )( actuals.map( meaning ) )
}
}

Those familiar with Universal algebra will notice that we have skirted around the issues of syntactic considerations of arity. That is, our grammar allows for both

• the expression s1( s() ) and
• the expression s1( s(), s() ).

If s1 denotes a single function, there’s a potential for a problem. In an era where polymorphism is commonplace, we recognize that s1 probably stands for a whole family of functions each with different arity. We probably ought to give a nod to this (and some related issues) by adjusting the meaning function of our semantics as

def meaning( s : Symbol, arity : Int ) : Operator

to allow us to pick out which Operator in the family a given symbol denotes. As an example, consider our friends the Boolean algebras. It is perfectly reasonable and consistent to interpret true as the zero-ary conjunction and -- because conjunction is associative -- we have a version of it for every possible arity. In other words, we have a reasonably complete presentation of a Boolean algebra with

Conjunction . BooleanExpr ::= And ( BooleanExpr* )
Negation . BooleanExpr ::= ~ BooleanExpr

together with the DeMorgan’s law which we could write

Or( b1, b2 ) := ~ And( ~b1, ~b2 )

This raises interesting points about syntactic sugar and compositional semantics -- but let’s not get too ahead of ourselves, but instead, pop up a level closer to our aim. Even with this we can sketch out what we mean by an algebraic theory and a model. An algebraic theory is going to be given by a collection of Symbols and an assignment of (sets of ) arity (resp., arities). Taken together with a collection of equations. What are those? In the interest of narrative tension, they will have to wait until the next post! ;-) For now, let me close with this: if you've spotted a connection between our AlgebraicExprs and case class instances, this is no accident! It's all part of this underlying structure i'm hoping to expose.